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").

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

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
>