From: Alexander Monakov <amonakov@ispras.ru>
To: Zack Weinberg <zack@owlfolio.org>
Cc: Paul Eggert <eggert@cs.ucla.edu>,
Siddhesh Poyarekar <siddhesh@gotplt.org>,
Vincent Lefevre <vincent@vinc17.net>,
Xi Ruoyao <xry111@xry111.site>,
Adhemerval Zanella <adhemerval.zanella@linaro.org>,
Turritopsis Dohrnii Teo En Ming <teo.en.ming@protonmail.com>,
GNU libc development <libc-alpha@sourceware.org>,
"ceo@teo-en-ming-corp.com" <ceo@teo-en-ming-corp.com>
Subject: Re: New GNU C Library (glibc) security flaw reported on 30 Jan 2024
Date: Thu, 8 Feb 2024 00:53:52 +0300 (MSK) [thread overview]
Message-ID: <9dc814c2-8542-0040-6d07-a96ca898e76a@ispras.ru> (raw)
In-Reply-To: <30c30ef6-7446-46f6-a502-d1c623762121@app.fastmail.com>
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
next prev parent reply other threads:[~2024-02-07 21:54 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-01-31 14:08 New GNU C Library (glibc) security flaw reported on 30 Jan 2024 Turritopsis Dohrnii Teo En Ming
2024-01-31 14:23 ` Xi Ruoyao
2024-01-31 14:55 ` Vincent Lefevre
2024-01-31 15:52 ` Adhemerval Zanella Netto
2024-01-31 16:23 ` Vincent Lefevre
2024-01-31 16:44 ` Siddhesh Poyarekar
2024-01-31 18:47 ` Xi Ruoyao
2024-02-01 0:51 ` Vincent Lefevre
2024-02-01 1:03 ` Vincent Lefevre
2024-02-01 6:41 ` Xi Ruoyao
2024-02-01 9:07 ` Vincent Lefevre
2024-02-01 19:55 ` Paul Eggert
2024-02-01 21:11 ` Siddhesh Poyarekar
2024-02-05 0:58 ` Paul Eggert
2024-02-06 15:00 ` Zack Weinberg
2024-02-06 21:30 ` Paul Eggert
2024-02-06 22:04 ` Xi Ruoyao
2024-02-07 17:07 ` Zack Weinberg
2024-02-07 19:55 ` Alexander Monakov
2024-02-07 20:45 ` Zack Weinberg
2024-02-07 21:53 ` Alexander Monakov [this message]
2024-02-07 22:56 ` Paul Eggert
2024-04-06 17:17 ` Paul Eggert
2024-04-08 8:28 ` Florian Weimer
2024-04-22 14:39 ` Zack Weinberg
2024-04-23 18:09 ` Paul Eggert
2024-04-23 18:26 ` Florian Weimer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/libc/involved.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=9dc814c2-8542-0040-6d07-a96ca898e76a@ispras.ru \
--to=amonakov@ispras.ru \
--cc=adhemerval.zanella@linaro.org \
--cc=ceo@teo-en-ming-corp.com \
--cc=eggert@cs.ucla.edu \
--cc=libc-alpha@sourceware.org \
--cc=siddhesh@gotplt.org \
--cc=teo.en.ming@protonmail.com \
--cc=vincent@vinc17.net \
--cc=xry111@xry111.site \
--cc=zack@owlfolio.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).