Re: Wrong info in libc comparison

[Markus Wichmann <nullplan@gmx.net>]

On Sat, Sep 16, 2017 at 07:11:54PM +0200, Szabolcs Nagy wrote:
> glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd
> qsort are all O(n^2) worst-case, musl qsort is O(n log(n)).
> 

Yes, sorry, I mixed that up. Quicksort is loglinear only in the average
case. Same for Shell sort being O(sqrt(n^3)).

> i think this is not a sidetrack, but relevant detail
> for a libc comparision page.
> (the openbsd proof of concept stack clash exploit
> relied on the unbounded stack use in qsort, that
> would not work against musl, but all the other libcs
> are affected.)

No, stack usage is not necessarily linear even with quicksort. dietlibc
and avr-libc have linear stack usage (with avr-libc always recursing
into the first subproblem, and dietlibc always recursing into both
subproblems), that's right, but glibc uses a constant amount of stack
(automatic allocation of an array to hold the maximum possible number of
subproblems, which is equal to the number of bits in a machine word),
and newlib uses recursion into the smaller subproblem, thus using a
logarithmic amount of stack (functionally constant, since you can give
an upper limit).

And uclibc also uses a constant amount of stack. Shell sort doesn't need
recursion.

Ciao,
Markus