Date: Wed, 7 Feb 2024 20:56:20 -0600
From: Nathan Bossart <nathandbossart@gmail.com>
To: Thomas Munro <thomas.munro@gmail.com>
Cc: Andres Freund <andres@anarazel.de>,
	Heikki Linnakangas <hlinnaka@iki.fi>,
	Mats Kindahl <mats@timescale.com>, Tom Lane <tgl@sss.pgh.pa.us>,
	pgsql-hackers@lists.postgresql.org
Subject: Re: glibc qsort() vulnerability
Message-ID: <20240208025620.GC445153@nathanxps13>
References: <642084.1707252958@sss.pgh.pa.us>
 <CA+14425TqyUZ3-O7zYsW6u85yY5diCz-p_TPQ2bZovn-N-fQ9A@mail.gmail.com>
 <cc9b0272-849a-4a88-8200-59786d18b7a1@iki.fi>
 <20240207214857.rjqkutiaapka2xyp@awork3.anarazel.de>
 <20240207222124.GA382832@nathanxps13>
 <20240208004207.aoyrtv577nmhrivy@awork3.anarazel.de>
 <20240208015211.GA445153@nathanxps13>
 <20240208020637.3irwi5vph4fbxw2f@awork3.anarazel.de>
 <CA+hUKGLbC4O56rtFM69Tx6StT3PcVio9K2GisjZp=z6O20Q3sw@mail.gmail.com>
 <CA+hUKGJaOM5ULeXboxV+fGkU-pYHotL5A10hYxdu8_kwRcVEgQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: 
 <CA+hUKGJaOM5ULeXboxV+fGkU-pYHotL5A10hYxdu8_kwRcVEgQ@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/20240208025620.GC445153%40nathanxps13>
Precedence: bulk

On Thu, Feb 08, 2024 at 03:49:03PM +1300, Thomas Munro wrote:
> On Thu, Feb 8, 2024 at 3:38 PM Thomas Munro <thomas.munro@gmail.com> wrote:
>> Perhaps you could wrap it in a branch-free sign() function so you get
>> a narrow answer?
>>
>> https://stackoverflow.com/questions/14579920/fast-sign-of-integer-in-c
> 
> Ah, strike that, it is much like the suggested (a > b) - (a < b) but
> with extra steps...

Yeah, https://godbolt.org/ indicates that the sign approach compiles to

        movsx   rsi, esi
        movsx   rdi, edi
        xor     eax, eax
        sub     rdi, rsi
        test    rdi, rdi
        setg    al
        shr     rdi, 63
        sub     eax, edi
        ret

while the approach Andres suggested compiles to

        xor     eax, eax
        cmp     edi, esi
        setl    dl
        setg    al
        movzx   edx, dl
        sub     eax, edx
        ret

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com