From: "H.J. Lu" <hjl.tools@gmail.com>
To: Noah Goldstein <goldstein.w.n@gmail.com>
Cc: GNU C Library <libc-alpha@sourceware.org>,
"Carlos O'Donell" <carlos@systemhalted.org>
Subject: Re: [PATCH v4 2/5] string: Improve coverage in test-strcmp.c and test-strncmp.c
Date: Thu, 3 Feb 2022 14:28:41 -0800 [thread overview]
Message-ID: <CAMe9rOo46+PwjyDKU8p4vdsi4CHqzxAT2tUDCLTKZ-0Pqi1Tag@mail.gmail.com> (raw)
In-Reply-To: <20220203214215.3275256-2-goldstein.w.n@gmail.com>
On Thu, Feb 3, 2022 at 1:42 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> Add additional test cases for small / medium sizes.
>
> Add tests in test-strncmp.c where `n` is near ULONG_MAX or LONG_MIN to
> test for overflow bugs in length handling.
>
> Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
> ---
> string/test-strcmp.c | 70 ++++++++++--
> string/test-strncmp.c | 257 +++++++++++++++++++++++++++++++++++++++---
> 2 files changed, 306 insertions(+), 21 deletions(-)
>
> diff --git a/string/test-strcmp.c b/string/test-strcmp.c
> index 97d7bf5043..eacbdc8857 100644
> --- a/string/test-strcmp.c
> +++ b/string/test-strcmp.c
> @@ -16,6 +16,9 @@
> License along with the GNU C Library; if not, see
> <https://www.gnu.org/licenses/>. */
>
> +#define TEST_LEN (4096 * 3)
> +#define MIN_PAGE_SIZE (TEST_LEN + 2 * getpagesize ())
> +
> #define TEST_MAIN
> #ifdef WIDE
> # define TEST_NAME "wcscmp"
> @@ -129,7 +132,7 @@ do_one_test (impl_t *impl,
>
> static void
> do_test (size_t align1, size_t align2, size_t len, int max_char,
> - int exp_result)
> + int exp_result)
> {
> size_t i;
>
> @@ -138,19 +141,22 @@ do_test (size_t align1, size_t align2, size_t len, int max_char,
> if (len == 0)
> return;
>
> - align1 &= 63;
> + align1 &= ~(CHARBYTES - 1);
> + align2 &= ~(CHARBYTES - 1);
> +
> + align1 &= getpagesize () - 1;
> if (align1 + (len + 1) * CHARBYTES >= page_size)
> return;
>
> - align2 &= 63;
> + align2 &= getpagesize () - 1;
> if (align2 + (len + 1) * CHARBYTES >= page_size)
> return;
>
> /* Put them close to the end of page. */
> i = align1 + CHARBYTES * (len + 2);
> - s1 = (CHAR *) (buf1 + ((page_size - i) / 16 * 16) + align1);
> + s1 = (CHAR *)(buf1 + ((page_size - i) / 16 * 16) + align1);
> i = align2 + CHARBYTES * (len + 2);
> - s2 = (CHAR *) (buf2 + ((page_size - i) / 16 * 16) + align2);
> + s2 = (CHAR *)(buf2 + ((page_size - i) / 16 * 16) + align2);
>
> for (i = 0; i < len; i++)
> s1[i] = s2[i] = 1 + (23 << ((CHARBYTES - 1) * 8)) * i % max_char;
> @@ -161,9 +167,10 @@ do_test (size_t align1, size_t align2, size_t len, int max_char,
> s2[len - 1] -= exp_result;
>
> FOR_EACH_IMPL (impl, 0)
> - do_one_test (impl, s1, s2, exp_result);
> + do_one_test (impl, s1, s2, exp_result);
> }
>
> +
> static void
> do_random_tests (void)
> {
> @@ -385,7 +392,7 @@ check3 (void)
> int
> test_main (void)
> {
> - size_t i;
> + size_t i, j;
>
> test_init ();
> check();
> @@ -426,6 +433,55 @@ test_main (void)
> do_test (2 * CHARBYTES * i, CHARBYTES * i, 8 << i, LARGECHAR, -1);
> }
>
> + for (j = 0; j < 160; ++j)
> + {
> + for (i = 0; i < TEST_LEN;)
> + {
> + do_test (getpagesize () - j - 1, 0, i, 127, 0);
> + do_test (getpagesize () - j - 1, 0, i, 127, 1);
> + do_test (getpagesize () - j - 1, 0, i, 127, -1);
> +
> + do_test (getpagesize () - j - 1, j, i, 127, 0);
> + do_test (getpagesize () - j - 1, j, i, 127, 1);
> + do_test (getpagesize () - j - 1, j, i, 127, -1);
> +
> + do_test (0, getpagesize () - j - 1, i, 127, 0);
> + do_test (0, getpagesize () - j - 1, i, 127, 1);
> + do_test (0, getpagesize () - j - 1, i, 127, -1);
> +
> + do_test (j, getpagesize () - j - 1, i, 127, 0);
> + do_test (j, getpagesize () - j - 1, i, 127, 1);
> + do_test (j, getpagesize () - j - 1, i, 127, -1);
> +
> + if (i < 32)
> + {
> + i += 1;
> + }
> + else if (i < 161)
> + {
> + i += 7;
> + }
> + else if (i + 161 < TEST_LEN)
> + {
> + i += 31;
> + i *= 17;
> + i /= 16;
> + if (i + 161 > TEST_LEN)
> + {
> + i = TEST_LEN - 160;
> + }
> + }
> + else if (i + 32 < TEST_LEN)
> + {
> + i += 7;
> + }
> + else
> + {
> + i += 1;
> + }
> + }
> + }
> +
> do_random_tests ();
> return ret;
> }
> diff --git a/string/test-strncmp.c b/string/test-strncmp.c
> index 61a283a0af..1a3cee1792 100644
> --- a/string/test-strncmp.c
> +++ b/string/test-strncmp.c
> @@ -16,6 +16,9 @@
> License along with the GNU C Library; if not, see
> <https://www.gnu.org/licenses/>. */
>
> +#define TEST_LEN (4096 * 3)
> +#define MIN_PAGE_SIZE (TEST_LEN + 2 * getpagesize ())
> +
> #define TEST_MAIN
> #ifdef WIDE
> # define TEST_NAME "wcsncmp"
> @@ -166,11 +169,11 @@ do_test_limit (size_t align1, size_t align2, size_t len, size_t n, int max_char,
> }
>
> static void
> -do_test (size_t align1, size_t align2, size_t len, size_t n, int max_char,
> - int exp_result)
> +do_test_n (size_t align1, size_t align2, size_t len, size_t n, int n_in_bounds,
> + int max_char, int exp_result)
> {
> - size_t i;
> - CHAR *s1, *s2;
> + size_t i, buf_bound;
> + CHAR *s1, *s2, *s1_end, *s2_end;
>
> align1 &= ~(CHARBYTES - 1);
> align2 &= ~(CHARBYTES - 1);
> @@ -178,22 +181,28 @@ do_test (size_t align1, size_t align2, size_t len, size_t n, int max_char,
> if (n == 0)
> return;
>
> - align1 &= 63;
> - if (align1 + (n + 1) * CHARBYTES >= page_size)
> + buf_bound = n_in_bounds ? n : len;
> +
> + align1 &= getpagesize () - 1;
> + if (align1 + (buf_bound + 2) * CHARBYTES >= page_size)
> return;
>
> - align2 &= 63;
> - if (align2 + (n + 1) * CHARBYTES >= page_size)
> + align2 &= getpagesize () - 1;
> + if (align2 + (buf_bound + 2) * CHARBYTES >= page_size)
> return;
>
> - s1 = (CHAR *) (buf1 + align1);
> - s2 = (CHAR *) (buf2 + align2);
> + s1 = (CHAR *)(buf1 + align1);
> + s2 = (CHAR *)(buf2 + align2);
>
> - for (i = 0; i < n; i++)
> + if (n_in_bounds)
> + {
> + s1[n] = 24 + exp_result;
> + s2[n] = 23;
> + }
> +
> + for (i = 0; i < buf_bound; i++)
> s1[i] = s2[i] = 1 + (23 << ((CHARBYTES - 1) * 8)) * i % max_char;
>
> - s1[n] = 24 + exp_result;
> - s2[n] = 23;
> s1[len] = 0;
> s2[len] = 0;
> if (exp_result < 0)
> @@ -203,10 +212,24 @@ do_test (size_t align1, size_t align2, size_t len, size_t n, int max_char,
> if (len >= n)
> s2[n - 1] -= exp_result;
>
> + /* Ensure that both s1 and s2 are valid null terminated strings. This is
> + * required by the standard. */
> + s1_end = (CHAR *)(buf1 + MIN_PAGE_SIZE - CHARBYTES);
> + s2_end = (CHAR *)(buf2 + MIN_PAGE_SIZE - CHARBYTES);
> + *s1_end = 0;
> + *s2_end = 0;
> +
> FOR_EACH_IMPL (impl, 0)
> do_one_test (impl, s1, s2, n, exp_result);
> }
>
> +static void
> +do_test (size_t align1, size_t align2, size_t len, size_t n, int max_char,
> + int exp_result)
> +{
> + do_test_n (align1, align2, len, n, 1, max_char, exp_result);
> +}
> +
> static void
> do_page_test (size_t offset1, size_t offset2, CHAR *s2)
> {
> @@ -400,10 +423,123 @@ check3 (void)
> }
> }
>
> +static void
> +check_overflow (void)
> +{
> + size_t i, j, of_mask, of_idx;
> + const size_t of_masks[]
> + = { ULONG_MAX, LONG_MIN, ULONG_MAX - (ULONG_MAX >> 2),
> + ((size_t)LONG_MAX) >> 1 };
> +
> + for (of_idx = 0; of_idx < sizeof (of_masks) / sizeof (of_masks[0]); ++of_idx)
> + {
> + of_mask = of_masks[of_idx];
> + for (j = 0; j < 160; ++j)
> + {
> + for (i = 1; i <= 161; i += (32 / sizeof (CHAR)))
> + {
> + do_test_n (j, 0, i, of_mask, 0, 127, 0);
> + do_test_n (j, 0, i, of_mask, 0, 127, 1);
> + do_test_n (j, 0, i, of_mask, 0, 127, -1);
> +
> + do_test_n (j, 0, i, of_mask - j / 2, 0, 127, 0);
> + do_test_n (j, 0, i, of_mask - j * 2, 0, 127, 1);
> + do_test_n (j, 0, i, of_mask - j, 0, 127, -1);
> +
> + do_test_n (j / 2, j, i, of_mask, 0, 127, 0);
> + do_test_n (j / 2, j, i, of_mask, 0, 127, 1);
> + do_test_n (j / 2, j, i, of_mask, 0, 127, -1);
> +
> + do_test_n (j / 2, j, i, of_mask - j, 0, 127, 0);
> + do_test_n (j / 2, j, i, of_mask - j / 2, 0, 127, 1);
> + do_test_n (j / 2, j, i, of_mask - j * 2, 0, 127, -1);
> +
> + do_test_n (0, j, i, of_mask - j * 2, 0, 127, 0);
> + do_test_n (0, j, i, of_mask - j, 0, 127, 1);
> + do_test_n (0, j, i, of_mask - j / 2, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, 0, i, of_mask, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i, of_mask, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, 0, i, of_mask, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, 0, i, of_mask - j / 2, 0, 127,
> + 0);
> + do_test_n (getpagesize () - j - 1, 0, i, of_mask - j * 2, 0, 127,
> + 1);
> + do_test_n (getpagesize () - j - 1, 0, i, of_mask - j, 0, 127,
> + -1);
> +
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1, i,
> + of_mask, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1, i,
> + of_mask, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1, i,
> + of_mask, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1, i,
> + of_mask - j, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1, i,
> + of_mask - j / 2, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1, i,
> + of_mask - j * 2, 0, 127, -1);
> + }
> +
> + for (i = 1; i < TEST_LEN; i += i)
> + {
> + do_test_n (j, 0, i - 1, of_mask, 0, 127, 0);
> + do_test_n (j, 0, i - 1, of_mask, 0, 127, 1);
> + do_test_n (j, 0, i - 1, of_mask, 0, 127, -1);
> +
> + do_test_n (j, 0, i - 1, of_mask - j / 2, 0, 127, 0);
> + do_test_n (j, 0, i - 1, of_mask - j * 2, 0, 127, 1);
> + do_test_n (j, 0, i - 1, of_mask - j, 0, 127, -1);
> +
> + do_test_n (j / 2, j, i - 1, of_mask, 0, 127, 0);
> + do_test_n (j / 2, j, i - 1, of_mask, 0, 127, 1);
> + do_test_n (j / 2, j, i - 1, of_mask, 0, 127, -1);
> +
> + do_test_n (j / 2, j, i - 1, of_mask - j, 0, 127, 0);
> + do_test_n (j / 2, j, i - 1, of_mask - j / 2, 0, 127, 1);
> + do_test_n (j / 2, j, i - 1, of_mask - j * 2, 0, 127, -1);
> +
> + do_test_n (0, j, i - 1, of_mask - j * 2, 0, 127, 0);
> + do_test_n (0, j, i - 1, of_mask - j, 0, 127, 1);
> + do_test_n (0, j, i - 1, of_mask - j / 2, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, 0, i - 1, of_mask, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i - 1, of_mask, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, 0, i - 1, of_mask, 0, 127,
> + -1);
> +
> + do_test_n (getpagesize () - j - 1, 0, i - 1, of_mask - j / 2, 0,
> + 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i - 1, of_mask - j * 2, 0,
> + 127, 1);
> + do_test_n (getpagesize () - j - 1, 0, i - 1, of_mask - j, 0, 127,
> + -1);
> +
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1,
> + i - 1, of_mask, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1,
> + i - 1, of_mask, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1,
> + i - 1, of_mask, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1,
> + i - 1, of_mask - j, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1,
> + i - 1, of_mask - j / 2, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, getpagesize () - 2 * j - 1,
> + i - 1, of_mask - j * 2, 0, 127, -1);
> + }
> + }
> + }
> +}
> +
> int
> test_main (void)
> {
> - size_t i;
> + size_t i, j;
>
> test_init ();
>
> @@ -470,6 +606,99 @@ test_main (void)
> do_test_limit (0, 0, 15 - i, 16 - i, 255, -1);
> }
>
> + for (j = 0; j < 160; ++j)
> + {
> + for (i = 0; i < TEST_LEN;)
> + {
> + do_test_n (getpagesize () - j - 1, 0, i, i + 1, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i, i + 1, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, 0, i, i + 1, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, 0, i, i, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i, i - 1, 0, 127, 0);
> +
> + do_test_n (getpagesize () - j - 1, 0, i, ULONG_MAX, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i, ULONG_MAX, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, 0, i, ULONG_MAX, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, 0, i, ULONG_MAX - i, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, 0, i, ULONG_MAX - i, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, 0, i, ULONG_MAX - i, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, j, i, i + 1, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, j, i, i + 1, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, j, i, i + 1, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, j, i, i, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, j, i, i - 1, 0, 127, 0);
> +
> + do_test_n (getpagesize () - j - 1, j, i, ULONG_MAX, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, j, i, ULONG_MAX, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, j, i, ULONG_MAX, 0, 127, -1);
> +
> + do_test_n (getpagesize () - j - 1, j, i, ULONG_MAX - i, 0, 127, 0);
> + do_test_n (getpagesize () - j - 1, j, i, ULONG_MAX - i, 0, 127, 1);
> + do_test_n (getpagesize () - j - 1, j, i, ULONG_MAX - i, 0, 127, -1);
> +
> + do_test_n (0, getpagesize () - j - 1, i, i + 1, 0, 127, 0);
> + do_test_n (0, getpagesize () - j - 1, i, i + 1, 0, 127, 1);
> + do_test_n (0, getpagesize () - j - 1, i, i + 1, 0, 127, -1);
> +
> + do_test_n (0, getpagesize () - j - 1, i, i, 0, 127, 0);
> + do_test_n (0, getpagesize () - j - 1, i, i - 1, 0, 127, 0);
> +
> + do_test_n (0, getpagesize () - j - 1, i, ULONG_MAX, 0, 127, 0);
> + do_test_n (0, getpagesize () - j - 1, i, ULONG_MAX, 0, 127, 1);
> + do_test_n (0, getpagesize () - j - 1, i, ULONG_MAX, 0, 127, -1);
> +
> + do_test_n (0, getpagesize () - j - 1, i, ULONG_MAX - i, 0, 127, 0);
> + do_test_n (0, getpagesize () - j - 1, i, ULONG_MAX - i, 0, 127, 1);
> + do_test_n (0, getpagesize () - j - 1, i, ULONG_MAX - i, 0, 127, -1);
> +
> + do_test_n (j, getpagesize () - j - 1, i, i + 1, 0, 127, 0);
> + do_test_n (j, getpagesize () - j - 1, i, i + 1, 0, 127, 1);
> + do_test_n (j, getpagesize () - j - 1, i, i + 1, 0, 127, -1);
> +
> + do_test_n (j, getpagesize () - j - 1, i, i, 0, 127, 0);
> + do_test_n (j, getpagesize () - j - 1, i, i - 1, 0, 127, 0);
> +
> + do_test_n (j, getpagesize () - j - 1, i, ULONG_MAX, 0, 127, 0);
> + do_test_n (j, getpagesize () - j - 1, i, ULONG_MAX, 0, 127, 1);
> + do_test_n (j, getpagesize () - j - 1, i, ULONG_MAX, 0, 127, -1);
> +
> + do_test_n (j, getpagesize () - j - 1, i, ULONG_MAX - i, 0, 127, 0);
> + do_test_n (j, getpagesize () - j - 1, i, ULONG_MAX - i, 0, 127, 1);
> + do_test_n (j, getpagesize () - j - 1, i, ULONG_MAX - i, 0, 127, -1);
> + if (i < 32)
> + {
> + i += 1;
> + }
> + else if (i < 161)
> + {
> + i += 7;
> + }
> + else if (i + 161 < TEST_LEN)
> + {
> + i += 31;
> + i *= 17;
> + i /= 16;
> + if (i + 161 > TEST_LEN)
> + {
> + i = TEST_LEN - 160;
> + }
> + }
> + else if (i + 32 < TEST_LEN)
> + {
> + i += 7;
> + }
> + else
> + {
> + i += 1;
> + }
> + }
> + }
> +
> + check_overflow ();
> do_random_tests ();
> return ret;
> }
> --
> 2.25.1
>
LGTM.
Reviewed-by: H.J. Lu <hjl.tools@gmail.com>
Thanks.
--
H.J.
next prev parent reply other threads:[~2022-02-03 22:29 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-02-03 21:42 [PATCH v4 1/5] string/test-str*cmp: remove stupid_[strcmp, strncmp, wcscmp, wcsncmp] Noah Goldstein
2022-02-03 21:42 ` [PATCH v4 2/5] string: Improve coverage in test-strcmp.c and test-strncmp.c Noah Goldstein
2022-02-03 22:28 ` H.J. Lu [this message]
2022-02-07 13:59 ` Matheus Castanho
2022-02-07 19:03 ` Noah Goldstein
2022-02-07 20:17 ` Noah Goldstein
2022-02-03 21:42 ` [PATCH v4 3/5] x86: Optimize strcmp-avx2.S Noah Goldstein
2022-02-03 22:29 ` H.J. Lu
2022-02-04 18:57 ` Joseph Myers
2022-02-04 19:13 ` H.J. Lu
2022-05-04 5:40 ` Sunil Pandey
2022-02-03 21:42 ` [PATCH v4 4/5] x86: Optimize strcmp-evex.S Noah Goldstein
2022-02-03 22:30 ` H.J. Lu
2022-05-04 5:38 ` Sunil Pandey
2022-02-03 21:42 ` [PATCH v4 5/5] benchtests: Add more coverage for strcmp and strncmp benchmarks Noah Goldstein
2022-02-03 22:30 ` H.J. Lu
2022-02-03 22:28 ` [PATCH v4 1/5] string/test-str*cmp: remove stupid_[strcmp, strncmp, wcscmp, wcsncmp] H.J. Lu
2022-02-03 23:30 ` Noah Goldstein
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAMe9rOo46+PwjyDKU8p4vdsi4CHqzxAT2tUDCLTKZ-0Pqi1Tag@mail.gmail.com \
--to=hjl.tools@gmail.com \
--cc=carlos@systemhalted.org \
--cc=goldstein.w.n@gmail.com \
--cc=libc-alpha@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).