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 <adhemerval.zanella@linaro.org>

diff --git a/stdlib/Makefile b/stdlib/Makefile
index 6194d1cb22cee59c5f924b797fddfddb3d9fca7f..0b154e57c586f65b6ad989225791a9b9788b0d42 100644 (file)
--- 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 be01fb5598de2257ceaebf967826c15fab2ef398..62477010b627024642c7ba58eb52c8e7c9cd49ce 100644 (file)
--- 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 (file)
index 0000000..8ec0a6b
--- /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
+   <http://www.gnu.org/licenses/>.  */
+
+#include <array_length.h>
+#include <stdlib.h>
+#include <support/check.h>
+
+/* 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 <support/test-driver.c>