From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.ispras.ru (mail.ispras.ru [83.149.199.84]) by sourceware.org (Postfix) with ESMTPS id C0B9C3858C5F for ; Wed, 7 Feb 2024 21:53:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C0B9C3858C5F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=ispras.ru Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=ispras.ru ARC-Filter: OpenARC Filter v1.0.0 sourceware.org C0B9C3858C5F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=83.149.199.84 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707342835; cv=none; b=LPAvUVl+x141FnfxMMb+M+gTe9kiQSJRedFpSa3nDEAAiH1xexWSn+wnwOiyjTGv81D23ZSMOt30urhy2NyKKYsLnkCybdjqqQMzolb6D6ZGump/p9QrTWHkrHNAlHBHwlBfb7DpVouDbeDG2f9slqPjK67MfY87wz+NwzgsrXo= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707342835; c=relaxed/simple; bh=VZuEXvQkoNcEvvUK+pFyWO7gETPOgP/+Qn4rwHg7ouI=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:MIME-Version; b=NuxYFM+F/3CgQUP8LgcYUYbLYqNVlQA10GtnrHwIDEMdUx++TFKWQfPe3h/uaTwQ9hiwocoScXm62yA87k8ab+QxR8XcbrNsvadmQNLKuTSN3qm1BMiwbKRb9VCqiE1VHtyLvswf7BONSdnExAXOAuBcHvk30MoY2trRqDpLcDo= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.10.3.121] (unknown [10.10.3.121]) by mail.ispras.ru (Postfix) with ESMTPS id 7693C40F1DF3; Wed, 7 Feb 2024 21:53:52 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 mail.ispras.ru 7693C40F1DF3 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ispras.ru; s=default; t=1707342832; bh=KgGVGd1+xr2wXftdCFJxj+xgdXFsbjKm6+/R8fv2saA=; h=Date:From:To:cc:Subject:In-Reply-To:References:From; b=Xs1PxQz5nAdTHCteGb5RSciX/SaZRZCreqzSPp0YeXWyf1I3/I/ZcfkUG+ItmnkFD 8QCknCU5osjX3d7zqxNDb0Pqt8jxaT7uVmItjsiLhvJJDB+7uNdOMl0XGpJb/55Qij vUHyFxlk3Txud12sxPPyWUwDiPj3PrKOvc3YBe5Y= Date: Thu, 8 Feb 2024 00:53:52 +0300 (MSK) From: Alexander Monakov To: Zack Weinberg cc: Paul Eggert , Siddhesh Poyarekar , Vincent Lefevre , Xi Ruoyao , Adhemerval Zanella , Turritopsis Dohrnii Teo En Ming , GNU libc development , "ceo@teo-en-ming-corp.com" Subject: Re: New GNU C Library (glibc) security flaw reported on 30 Jan 2024 In-Reply-To: <30c30ef6-7446-46f6-a502-d1c623762121@app.fastmail.com> Message-ID: <9dc814c2-8542-0040-6d07-a96ca898e76a@ispras.ru> References: <20240131145555.GB2102@cventin.lip.ens-lyon.fr> <96521764f4636c9ea3f3089f369975c12fa8be77.camel@xry111.site> <20240201005155.GF3044@qaa.vinc17.org> <20240201090721.GH3044@qaa.vinc17.org> <5ea9eabb-f047-490f-abe9-43630d79c395@cs.ucla.edu> <7234533a-c8dd-4114-aa64-d4af3b138a3a@gotplt.org> <4d94a528-fe3f-413d-afa0-91a41f8371ff@app.fastmail.com> <4963e3ae-b0d5-d1d7-a986-5709d7a30bbb@ispras.ru> <30c30ef6-7446-46f6-a502-d1c623762121@app.fastmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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