stdlib: Fix array bounds protection in insertion sort phase of qsort
Checks
Context |
Check |
Description |
redhat-pt-bot/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
redhat-pt-bot/TryBot-32bit |
success
|
Build for i686
|
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_build--master-arm |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_check--master-arm |
success
|
Testing passed
|
Commit Message
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").
Tested on i686-linux-gnu and x86_64-linux-gnu.
Thanks,
Florian
---
stdlib/Makefile | 1 +
stdlib/qsort.c | 2 +-
stdlib/tst-qsort6.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 62 insertions(+), 1 deletion(-)
base-commit: 2e0c0ff95ca0e3122eb5b906ee26a31f284ce5ab
Comments
On 24/11/23 14:01, Florian Weimer wrote:
> 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").
>
> Tested on i686-linux-gnu and x86_64-linux-gnu.
>
> Thanks,
> Florian
> ---
> 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;
The insertion sort is quite convoluted and uses an 'optimization' to avoid
some elements swap that does not leverage the swap_type optimization (it
essentially does a byte-copy).
Also, a threshold of 4 maybe it would be better to use network sort (as
gcc does with gcc_sort).
So I wonder if would be better to just use a simpler algorithm:
static inline void
insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
size_t size, enum swap_type_t swap_type,
__compar_d_fn_t cmp, void *arg)
{
int i = 1;
while (i < total_elems)
{
int j = i;
while (j > 0 && cmp (pbase + ((j - 1) * size), pbase + (j * size), arg)
> 0)
{
do_swap (pbase + ((j - 1) * size), pbase + (j * size), size,
swap_type);
j = j -1;
}
i = i + 1;
}
}
(it shown not regression with your testcase included).
> 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
> + <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>
>
> base-commit: 2e0c0ff95ca0e3122eb5b906ee26a31f284ce5ab
>
* Adhemerval Zanella Netto:
> So I wonder if would be better to just use a simpler algorithm:
>
> static inline void
> insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
> size_t size, enum swap_type_t swap_type,
> __compar_d_fn_t cmp, void *arg)
> {
> int i = 1;
> while (i < total_elems)
> {
> int j = i;
> while (j > 0 && cmp (pbase + ((j - 1) * size), pbase + (j * size), arg)
> > 0)
> {
> do_swap (pbase + ((j - 1) * size), pbase + (j * size), size,
> swap_type);
> j = j -1;
> }
> i = i + 1;
> }
> }
>
> (it shown not regression with your testcase included).
This approach works for me, too.
Thanks,
Florian
On Fri, 24 Nov 2023, Adhemerval Zanella Netto wrote:
> Also, a threshold of 4 maybe it would be better to use network sort (as
> gcc does with gcc_sort).
I've pushed a GCC patch fixing my incorrect use of 'network sort' in favor
of the correct term 'sorting networks':
https://inbox.sourceware.org/gcc-patches/20231126163858.9328-1-amonakov@ispras.ru/T/
Sorry about that.
Alexander
On 24/11/23 14:01, Florian Weimer wrote:
> 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").
>
> Tested on i686-linux-gnu and x86_64-linux-gnu.
>
> Thanks,
> Florian
LGTM, thanks.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
> ---
> 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
> + <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);
These seems superfluous.
> + 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>
>
> base-commit: 2e0c0ff95ca0e3122eb5b906ee26a31f284ce5ab
>
@@ -216,6 +216,7 @@ tests := \
tst-qsort2 \
tst-qsort3 \
tst-qsort5 \
+ tst-qsort6 \
tst-quick_exit \
tst-rand48 \
tst-rand48-2 \
@@ -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;
new file mode 100644
@@ -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>