Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 3:56 AM Nathan Bossart <nathandbossart(at)gmail(dot)com>
wrote:

> 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(dot)munro(at)gmail(dot)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
>

Here is a patch that fixes existing cases and introduces a macro for this
comparison (it uses the (a > b) - (a < b) approach). Not sure where to
place the macro nor what a suitable name should be, so feel free to suggest
anything.

I also noted that some functions are duplicated and it might be an idea to
introduce a few standard functions like pg_qsort_strcmp for, e.g., integers
and other common types.

Also noted it is quite common to have this pattern in various places to do
lexicographic sort of multiple values and continue the comparison if they
are equal. Not sure if that is something we should look at.

Best wishes,
Mats Kindahl

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