[PATCH v2 4/7] string: Improve coverage in test-strcmp.c and test-strncmp.c
Noah Goldstein
goldstein.w.n@gmail.com
Mon Jan 10 02:51:23 GMT 2022
On Sun, Jan 9, 2022 at 6:39 PM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Sun, Jan 9, 2022 at 4:30 PM Noah Goldstein via Libc-alpha
> <libc-alpha@sourceware.org> 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.
>
> How long do new tests run?
~5sec for strcmp
~15sec for strncmp
>
> > Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
> > ---
> > string/test-strcmp.c | 70 ++++++++++--
> > string/test-strncmp.c | 248 +++++++++++++++++++++++++++++++++++++++---
> > 2 files changed, 298 insertions(+), 20 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..4fa6106eb4 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,10 +169,10 @@ 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;
> > + size_t i, buf_bound;
> > CHAR *s1, *s2;
> >
> > align1 &= ~(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 + 1) * CHARBYTES >= page_size)
> > return;
> >
> > - align2 &= 63;
> > - if (align2 + (n + 1) * CHARBYTES >= page_size)
> > + align2 &= getpagesize () - 1;
> > + if (align2 + (buf_bound + 1) * 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)
> > @@ -207,6 +216,13 @@ do_test (size_t align1, size_t align2, size_t len, size_t n, int max_char,
> > 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 +416,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 +599,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
> >
>
>
> --
> H.J.
More information about the Libc-alpha
mailing list