[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Sat, 16 Sep 2017 21:34:34 +0200
From: Markus Wichmann <nullplan@....net>
To: musl@...ts.openwall.com
Subject: Re: Wrong info in libc comparison
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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
