Re: Wrong info in libc comparison

[Szabolcs Nagy <nsz@port70.net>]

* Markus Wichmann <nullplan@gmx.net> [2017-09-16 16:01:10 +0200]:
> On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote:
> > * Markus Wichmann <nullplan@gmx.net> [2017-09-15 21:18:46 +0200]:
> > > On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote:
> > > > If you're considering big-O, where n->infinity (or at least to the
> > > > largest value that can fit in memory), malloc most certainly has
> > > > failed (because the array to be sorted already filled memory) and
> > > > you're looking at the "fallback" case.
> > > > 
> > > 
> > > I think we're getting sidetracked here. Every libc worth its salt uses a
                                              ^^^^^^^^^^
> > > loglinear sorting algorithm. Thus they are all equal in that regard.
      ^^^^^^^^^                         ^^^^^^^^^^^^^^^^^^
> > 
> > that is not true at all.
> > embedded libcs are often optimized for size, not worst case behaviour.
> > note that worst-case behaviour is not just big-O..
> > (e.g. glibc uses mergesort which uses malloc which means it's not as-safe,
> > may introduce arbitrary latency since malloc can be interposed, concurrent
> > mallocs can delay forward progress, large allocation may cause swapping,
> > cancellation or longjmp out of the cmp callback can leak memory etc.)
> > 
> 
> Did you even read what I wrote? Rich talked about big-O, i.e. complexity
> theory, to which I remarked that most algorithms in use are loglinear
> and thus equal _in_that_regard_.
> 

glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd
qsort are all O(n^2) worst-case, musl qsort is O(n log(n)).

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