From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1035.google.com (mail-pj1-x1035.google.com [IPv6:2607:f8b0:4864:20::1035]) by sourceware.org (Postfix) with ESMTPS id E05503857C4B for ; Mon, 10 Jan 2022 00:39:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E05503857C4B Received: by mail-pj1-x1035.google.com with SMTP id n30-20020a17090a5aa100b001b2b6509685so14206594pji.3 for ; Sun, 09 Jan 2022 16:39:18 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=HY8zeXWU5v6O5V7nb3k3IClOUt08k61umbGYNydPM7A=; b=AIjRR5BmPPPnGVwHWdeR+fAKfpyoRavJzbdJDiDKtl8LFeW/BFcZgDNMeAl8YNAxFd kdoqtdq2n2ATUtW65+vq1s9R/iMAYP5E/D4vC+M0+o2KkiN+4TCH2dpERBqumuz8PtvY ugWu6cAtdf/wqG2g+X2K+NLk/MFlAHTbATYIFl4mudeygF66onkdLzz9EGdU3KCZGTjm 9Dq1tSIlCX5h3whgPDFgTasOnmQgMP4xKTAryBHxsfaZKdCOFRboE7GKBIisEgghVpEB J9zILEmYoLHOdAdH2jFaa8qXBn0tDHQHqTj8KombZDhBl+u5L199+fGG8RRNd3gIstuN 4u5A== X-Gm-Message-State: AOAM5300ZlxKKcQZuxq/TPSpeoCsqDaXtFg1OGz4QnxkFk/0GPc5UjxY Tm05JMPMbVdC+zEhX5ZeCzIgBqGDBWaPT+nKiN6qgtVt X-Google-Smtp-Source: ABdhPJxns/Wp5TXQ4Mo31jkUjAsjM3j1tN2xnpOc3BB3HgossMa3672eu4cI2UswdbmXjkKNU8eYXBLzNg6BxnLa1gI= X-Received: by 2002:a17:903:191:b0:148:a2e8:2c17 with SMTP id z17-20020a170903019100b00148a2e82c17mr71489479plg.102.1641775157847; Sun, 09 Jan 2022 16:39:17 -0800 (PST) MIME-Version: 1.0 References: <20220109122946.2754917-1-goldstein.w.n@gmail.com> <20220110002746.3653516-1-goldstein.w.n@gmail.com> <20220110002746.3653516-4-goldstein.w.n@gmail.com> In-Reply-To: <20220110002746.3653516-4-goldstein.w.n@gmail.com> From: "H.J. Lu" Date: Sun, 9 Jan 2022 16:38:42 -0800 Message-ID: Subject: Re: [PATCH v2 4/7] string: Improve coverage in test-strcmp.c and test-strncmp.c To: Noah Goldstein Cc: GNU C Library Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-3028.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 10 Jan 2022 00:39:21 -0000 On Sun, Jan 9, 2022 at 4:30 PM Noah Goldstein via Libc-alpha 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? > Signed-off-by: Noah Goldstein > --- > 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 > . */ > > +#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 > . */ > > +#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.