New GNU C Library (glibc) security flaw reported on 30 Jan 2024

[Alexander Monakov]

On Wed, 7 Feb 2024, Zack Weinberg wrote:

> On Wed, Feb 7, 2024, at 2:55 PM, Alexander Monakov wrote:
> > I don't understand how that is likely: was it common to use merge sort for
> > implementation of qsort? For in-place sorting algorithms that mistake is
> > pretty much impossible to make.
> 
> It's a subtle requirement that conflicts with a textbook optimization to
> *any* sorting algorithm that isn't 100% in-place,

Sorry, can you explain what optimization you mean here?

> and a supermajority of
> comparison functions in the wild won't care if it's violated.  It would be
> *more* surprising to me if nobody could turn up a qsort implementation that
> breaks this rule and always has.
> 
> > In any case it seems unnecessary (and even impolite maybe, towards the authors
> > of those other C libraries) to make such implication in the Glibc manual.
> > It's much nicer to stick to the facts about Glibc itself.
> 
> I see where you're coming from but it is even more important that the manual
> be clear about what portable code can and cannot rely on.

I think it can be done without making uncertain allegations about other C
libraries.

> > (Glibc VCS briefly carried an implementation with such a mistake around 2002
> > when Roger Sayle's "Towers of Hanoi merge sort" was applied and then reverted)
> 
> Was it reverted because of this mistake?  Do you happen to remember what broke?

I wasn't around back then :)  The commit that reverted it references bug 2880 in
the old GNATS bug tracker. I hope someone on the list knows where it is
archived. The commit message makes it clear it's due to the mistake we're
discussing:
https://sourceware.org/git/?p=glibc.git;a=commit;h=fa8d436c87f156d18208df3819fecee9fc1dbd9e

Alexander