From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from wfhigh2-smtp.messagingengine.com (wfhigh2-smtp.messagingengine.com [64.147.123.153]) by sourceware.org (Postfix) with ESMTPS id 1581D3858D33 for ; Tue, 6 Feb 2024 15:03:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1581D3858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=owlfolio.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=owlfolio.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1581D3858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=64.147.123.153 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707231786; cv=none; b=nsFaKJb5rI0/bNrk20Ig9fRO9FSMS/Nk4Nr3bu9cV15x6xav2PFYzdHF1Sphd7tNbf6B3QvC1a6fdFN7M0w8ZrW2yEv7a1DTy9Zt2H4SL9mf/1JXbQKzmtCavHAdKIBpOIUNX9l6qJG6TSXqd5SiDfLRiJLYfFNEpp3pq7C9ME0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707231786; c=relaxed/simple; bh=rkYe54o8VRc9zfxNVj7FVTVXPbAsYRPDde4J7Mochy0=; h=DKIM-Signature:DKIM-Signature:MIME-Version:Message-Id:Date:From: To:Subject; b=eWvkT8BKF8ckCCcqvzUspNfaHGtAIaVgFR5Nw060Hn6i5mwPHYZckhq43iNE09v+YV8ZwqHiOCyPBzIl/7B9IJm+GNEIf05p++GBE4p1Kb6VTHqioWtrq+YWxHZu78p9TqfoMO2yeOItbVlEbG+pVDgNrylagJ/bVD3JP6pWSk4= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailfhigh.west.internal (Postfix) with ESMTP id B6BFA180006C; Tue, 6 Feb 2024 10:03:01 -0500 (EST) Received: from imap45 ([10.202.2.95]) by compute5.internal (MEProxy); Tue, 06 Feb 2024 10:03:02 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=owlfolio.org; h= cc:content-transfer-encoding:content-type:content-type:date:date :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:subject:subject:to:to; s=fm2; t=1707231781; x=1707318181; bh=sIxW+JUbfsjQec+M66Tq43vk/GVL5v/3W2bACmlZj50=; b= LLzgY3bAOJRB3aWuJrhPCgJ5V5Otke+VGVEPZstH26FP/QilIz4Nugd4DgF3lYEb mLF8VHrYRYX00rAYi2icYLBtjfdzsXnFElyJPBWxxIsqHEL0JPnK9C8uT1qYD+y+ l9EuewoHv6Ah/so1JHJvoCws765k76+26v6SjLC/LE2fR1/CWa140dmGk+zObgiy Ak2ZsbHwjBeGpwmMRqeIi71cLytMgnSMA3WuWcnY9Adnz2gzAe2qSoiJNymGtjBV Dg1Ztw4rBvK/g3r55oxKzPvVExEf7oE8DdYcgyhqVj4wDCAWV66NtXRWXSrNakZR scrjnJK7FiU6VxizhfznnA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :content-type:date:date:feedback-id:feedback-id:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm3; t=1707231781; x= 1707318181; bh=sIxW+JUbfsjQec+M66Tq43vk/GVL5v/3W2bACmlZj50=; b=O Glnw8YE2rV94uuueEoHnFbOf4Vy72qTQDLp6GBsPbYCLZNmQetrAI2LtGmxNDK8Z d6CuqIsv+UHEP3dWRAM0CsqfaABBTLdrvfYf1ndC08hgY3JAwmWWScuy1kvh6b57 9kUoA257h4h3h/Xa2nvwD1DMuiziHb3I5Sf8sRbFkjxM/fsMwaFBiL5CT4TZmDFJ ++0SunM57anI0DQ+DYa2P4CaPf8HX41FDaAoP6/Ibs73NOC4T7DwVC1WLPY58f6+ TH920LexaCrtdUBj4G3P1G9oxu0vNdsq30sAV/4DWuxXIwZsV851Wc1FDSpDRyDD I5dNS2W8HGf+ukJkCOz/A== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrtddtgdegvdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefofgggkfgjfhffhffvufgtgfesthhqredtreerjeenucfhrhhomhepfdgkrggt khcuhggvihhnsggvrhhgfdcuoeiirggtkhesohiflhhfohhlihhordhorhhgqeenucggtf frrghtthgvrhhnpeffteffkeehfeevheduleekheeugfekjedtgfejvdefueeujeeghfeu ieeijeekfeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhroh hmpeiirggtkhesohiflhhfohhlihhordhorhhg X-ME-Proxy: Feedback-ID: i876146a2:Fastmail Received: by mailuser.nyi.internal (Postfix, from userid 501) id 2BECA272007D; Tue, 6 Feb 2024 10:03:00 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface User-Agent: Cyrus-JMAP/3.11.0-alpha0-144-ge5821d614e-fm-20240125.002-ge5821d61 MIME-Version: 1.0 Message-Id: In-Reply-To: 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> Date: Tue, 06 Feb 2024 10:00:52 -0500 From: "Zack Weinberg" To: "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 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,JMQ_SPF_NEUTRAL,KAM_MANYTO,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=no 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 Sun, Feb 4, 2024, at 7:58 PM, Paul Eggert wrote: > While we're on the topic, I reviewed the glibc manual's description of=20 > qsort, bsearch and lfind and found other instances where the manual=20 > disagrees with POSIX or is otherwise obviously incorrect. Proposed pat= ch=20 > attached. I have a couple of suggestions for improvement to these changes: [bsearch] ... > +The @var{array} must consist of all elements that compare less than, > +equal to, and greater than @var{key}, in that order. This sentence only makes sense to me because of what you said in the cover letter, about the array not being required to be totally ordered. I=E2=80=99d like to suggest instead @var{array} does not need to be totally ordered according to @var{compare}. However, all of the elements of @var{array} that compare less than @var{key} must be at lower indices than any element that compares equal to @var{key}, and all the elements that compare greater than @var{key} must be at higher indices than any element that compares equal to @var{key}. This is long enough that it should probably be its own paragraph. [qsort] Not related to what you wrote, but: A later paragraph says =E2=80=9Cthe = object addresses passed to the comparison function lie within the array,=E2=80=9D and C2011 7.22.5p2 actually makes this a hard requirement: =E2=80=9CThe implementation shall ensure that both arguments [of the comparison function called by qsort] are pointers to elements of the array.=E2=80=9D It looks to me like there are situations where our implementation doesn=E2=80=99t do this: specifically, whenever we aren=E2=80=99t doing = indirect sorting but we *are* using a scratch array, we may call the comparison function with one argument a pointer into the scratch array. (This might=E2=80=99ve come up in the discussion about changing out the = sort algorithm, I don=E2=80=99t remember for sure.) Since it seems like it w= ould be difficult for _any_ qsort implementation that=E2=80=99s not 100% in-p= lace to hit this requirement, I=E2=80=99d like to suggest these additional ch= anges to the qsort section: @@ search.texi:176 @@ the elements. Two elements with the same sort key may differ in other - respects. + respects. The only way to ensure a stable sort, when @var{compare} do= es + not consider all of the data in the objects being sorted, is to augment + each object with a tie-breaking value, such as its original array inde= x. - Although the object addresses passed to the comparison function lie - within the array, they need not correspond with the original locations - of those objects because the sorting algorithm may swap around objects - in the array before making some comparisons. The only way to perform - a stable sort with @code{qsort} is to first augment the objects with a - monotonic counter of some kind. + @strong{Portability Note:} The result of @var{compare} should not depe= nd + in any way on the @emph{addresses} of the objects it is comparing. + The sorting process might temporarily move objects out of order, so the + relative positions of objects within the array are unpredictable during + the sort. In addition, although ISO C specifies that both addresses + passed to the comparison function should lie within the array, + implementations (including @theglibc{}) often do not fulfill this + requirement. It is common for @code{qsort} to copy objects to tempora= ry + storage outside the array, and then compare those copies to each other + or to objects still within the array. zw