From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2178) id 8B59D3858C78; Mon, 4 Dec 2023 05:56:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8B59D3858C78 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1701669364; bh=Bi0PsM9+3MOs7XCsBsWlCXxd06KAOZRIV5pRZIVhdbY=; h=From:To:Subject:Date:From; b=FdSFLkxMgAB5knloVARe2Oc74L4rXEIe01En7Hc6aJHVEGB0Rhq1pzg2qlZ4b0ggx OtVCcoWfKpmpYyykFStczl9dfsZhpWkUYU49B90GTQDCR836JnnWoIjAnZH+SArZuP IJX0wc9gWIZsmHgasYArLvEh4BiLffqR2YK8f/Zk= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Florian Weimer To: glibc-cvs@sourceware.org Subject: [glibc] stdlib: Fix array bounds protection in insertion sort phase of qsort X-Act-Checkin: glibc X-Git-Author: Florian Weimer X-Git-Refname: refs/heads/master X-Git-Oldrev: d776a59723b22192d33557d2127e13cb31905382 X-Git-Newrev: b9390ba93676c4b1e87e218af5e7e4bb596312ac Message-Id: <20231204055604.8B59D3858C78@sourceware.org> Date: Mon, 4 Dec 2023 05:56:04 +0000 (GMT) List-Id: https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=b9390ba93676c4b1e87e218af5e7e4bb596312ac commit b9390ba93676c4b1e87e218af5e7e4bb596312ac Author: Florian Weimer Date: Mon Dec 4 06:35:56 2023 +0100 stdlib: Fix array bounds protection in insertion sort phase of qsort The previous check did not do anything because tmp_ptr already points before run_ptr due to the way it is initialized. Fixes commit e4d8117b82065dc72e8df80097360e7c05a349b9 ("stdlib: Avoid another self-comparison in qsort"). Reviewed-by: Adhemerval Zanella Diff: --- stdlib/Makefile | 1 + stdlib/qsort.c | 2 +- stdlib/tst-qsort6.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 62 insertions(+), 1 deletion(-) diff --git a/stdlib/Makefile b/stdlib/Makefile index 6194d1cb22..0b154e57c5 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -216,6 +216,7 @@ tests := \ tst-qsort2 \ tst-qsort3 \ tst-qsort5 \ + tst-qsort6 \ tst-quick_exit \ tst-rand48 \ tst-rand48-2 \ diff --git a/stdlib/qsort.c b/stdlib/qsort.c index be01fb5598..62477010b6 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -238,7 +238,7 @@ insertion_sort_qsort_partitions (void *const pbase, size_t total_elems, while ((run_ptr += size) <= end_ptr) { tmp_ptr = run_ptr - size; - while (run_ptr != tmp_ptr && cmp (run_ptr, tmp_ptr, arg) < 0) + while (tmp_ptr != base_ptr && cmp (run_ptr, tmp_ptr, arg) < 0) tmp_ptr -= size; tmp_ptr += size; diff --git a/stdlib/tst-qsort6.c b/stdlib/tst-qsort6.c new file mode 100644 index 0000000000..8ec0a6b633 --- /dev/null +++ b/stdlib/tst-qsort6.c @@ -0,0 +1,60 @@ +/* Test qsort with invalid comparison functions. + Copyright (C) 2023 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include + +/* Invalid comparison function that always returns -1. */ +static int +invalid_compare_1 (const void *a1, const void *b1) +{ + const int *a = a1; + const int *b = b1; + /* Check that the marker value matches, which means that we are + likely within the array. */ + TEST_COMPARE (*a, 842523635); + TEST_COMPARE (*b, 842523635); + TEST_VERIFY_EXIT (*a == 842523635); + TEST_VERIFY_EXIT (*b == 842523635); + return -1; +} + +/* Invalid comparison function that always returns 1. */ +static int +invalid_compare_2 (const void *a1, const void *b1) +{ + const int *a = a1; + const int *b = b1; + TEST_COMPARE (*a, 842523635); + TEST_COMPARE (*b, 842523635); + TEST_VERIFY_EXIT (*a == 842523635); + TEST_VERIFY_EXIT (*b == 842523635); + return 1; +} + +static int +do_test (void) +{ + int array[] = {842523635, 842523635, 842523635, 842523635, 842523635}; + qsort (array, array_length (array), sizeof (array[0]), invalid_compare_1); + qsort (array, array_length (array), sizeof (array[0]), invalid_compare_2); + return 0; +} + +#include