From patchwork Mon Jan 10 21:35:37 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 49815 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C45FA3835C1E for ; Mon, 10 Jan 2022 21:38:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C45FA3835C1E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1641850695; bh=eyiK3snG1Frg3QnGaDFXmoH/gnzPo/NhvC6GKIjq55s=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=Fd9UWFJQcFHB6JvzaUWKG1t/n+OG1dpjzhZyHLUp+/JXI7NOlO6mySZLkGPCCc+hr bgFXW9pbNwYVuQb3d+57s+Ty3LP5fi5fsxYcQUpp2fQWaChMLWsKZZYMIi50BZ/fzU KdHI701kSq9qNLYlbpnYIUUou9jVocNTcL7zNN48= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pl1-x634.google.com (mail-pl1-x634.google.com [IPv6:2607:f8b0:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 5CA993858C3A for ; Mon, 10 Jan 2022 21:35:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5CA993858C3A Received: by mail-pl1-x634.google.com with SMTP id x15so14042608plg.1 for ; Mon, 10 Jan 2022 13:35:51 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=eyiK3snG1Frg3QnGaDFXmoH/gnzPo/NhvC6GKIjq55s=; b=KwuE1Vlhg0KTj6ro+nvQxrJ3tCoxKb1ETN3J0M6JHFArhbY3ZRZKM/+8T4JYAn1viS C9cxw1I96xT1LcslmqeX89NQbnUFSz2aYcgyShsHjRYpHBrEMvug/IX+fhG31n5rGCD7 Sm7Bai6uB15g7/ITgIKoK8YKD/LW0Q8NsHLwFpIMXh9TWrihBeYMrf41v8VVK2At/rej DfEAaTOzYTJNTJddvbpexFsOU19gjv47XeFXTg8JW0Qm4M8eAfjoCnixLvakrj2RqM3G UONuWIx35Rbr5yGM1vajCXyiUZ/us/23J7B66KelidQHTY4bKdj/F5dpciSdjJyPUkJU 28vA== X-Gm-Message-State: AOAM533y5c33h4E90L28rONdI4ZCKhrtFDpMYo7rxrl5/vIKRX3fmAwX Ut3o9Lk0vnF1IkW/vABW1RVVKbunAuA= X-Google-Smtp-Source: ABdhPJzHJxxwoWLohVtiOq1YL0gI9MZPlx9uSaMAvj2frMDMIFCei9/DpOUadNxkHG9UVyOPy6Sc8w== X-Received: by 2002:a17:90a:c401:: with SMTP id i1mr1773241pjt.180.1641850550198; Mon, 10 Jan 2022 13:35:50 -0800 (PST) Received: from noah-tigerlake.webpass.net (136-24-166-223.cab.webpass.net. [136.24.166.223]) by smtp.googlemail.com with ESMTPSA id f12sm7996515pfe.127.2022.01.10.13.35.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 10 Jan 2022 13:35:49 -0800 (PST) To: libc-alpha@sourceware.org Subject: [PATCH v3 4/7] string: Improve coverage in test-strcmp.c and test-strncmp.c Date: Mon, 10 Jan 2022 15:35:37 -0600 Message-Id: <20220110213540.1258344-4-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220110213540.1258344-1-goldstein.w.n@gmail.com> References: <20220109122946.2754917-1-goldstein.w.n@gmail.com> <20220110213540.1258344-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.1 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-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" 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 --- 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 . */ +#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 . */ +#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; }