mbox series

[0/3] Various qsort fixes

Message ID cover.1700246487.git.fweimer@redhat.com
Headers
Series Various qsort fixes |

Message

Florian Weimer Nov. 17, 2023, 6:44 p.m. UTC 
  The first patch is basically a repost, with the condition tweaked for
consistency with the other self-comparison avoidance we have.

The second patch addresses Stepan's observation regarding incorrect
node-index computation in the fallback heapsort heapsort implementation.

The third patch activates the heapsort fallback in more cases, to avoid
denial-of-service issues.

Thanks,
Florian

Florian Weimer (3):
  stdlib: Avoid another self-comparison in qsort
  stdlib: Handle various corner cases in the fallback heapsort for qsort
  stdlib: The qsort implementation needs to use heapsort in more cases

 stdlib/Makefile     |   4 ++
 stdlib/qsort.c      |  74 +++++++++++++------
 stdlib/tst-qsort4.c | 134 ++++++++++++++++++++++++++++++++++
 stdlib/tst-qsort5.c | 171 ++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 361 insertions(+), 22 deletions(-)
 create mode 100644 stdlib/tst-qsort4.c
 create mode 100644 stdlib/tst-qsort5.c


base-commit: dae3cf4134d476a4b4ef86fd7012231d6436c15e

Comments

Adhemerval Zanella Nov. 20, 2023, 2:15 p.m. UTC | #1 
On 17/11/23 15:44, Florian Weimer wrote:
> The first patch is basically a repost, with the condition tweaked for
> consistency with the other self-comparison avoidance we have.
> 
> The second patch addresses Stepan's observation regarding incorrect
> node-index computation in the fallback heapsort heapsort implementation.
> 
> The third patch activates the heapsort fallback in more cases, to avoid
> denial-of-service issues.

I will review these today, thanks!

> 
> Thanks,
> Florian
> 
> Florian Weimer (3):
>   stdlib: Avoid another self-comparison in qsort
>   stdlib: Handle various corner cases in the fallback heapsort for qsort
>   stdlib: The qsort implementation needs to use heapsort in more cases
> 
>  stdlib/Makefile     |   4 ++
>  stdlib/qsort.c      |  74 +++++++++++++------
>  stdlib/tst-qsort4.c | 134 ++++++++++++++++++++++++++++++++++
>  stdlib/tst-qsort5.c | 171 ++++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 361 insertions(+), 22 deletions(-)
>  create mode 100644 stdlib/tst-qsort4.c
>  create mode 100644 stdlib/tst-qsort5.c
> 
> 
> base-commit: dae3cf4134d476a4b4ef86fd7012231d6436c15e