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

["Zack Weinberg" <zack@owlfolio.org>]

On Wed, Feb 7, 2024, at 2:55 PM, Alexander Monakov wrote:
> On Wed, 7 Feb 2024, Zack Weinberg wrote:
>> Still, I think it is likely that some C libraries in
>> the past have failed to implement this requirement (intentionally or not).
>> In the attached patch I revised that suggestion again and I hope it satisfies
>> everyone's expectations now.
>
> 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, 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.

> (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?

zw