Horton

Re: glibc qsort() vulnerability

Mats Kindahl <mats@timescale.com>

View thread
From: Mats Kindahl <mats@timescale.com>
To: Nathan Bossart <nathandbossart@gmail.com>
Cc: Thomas Munro <thomas.munro@gmail.com>, Andres Freund <andres@anarazel.de>, Heikki Linnakangas <hlinnaka@iki.fi>, Tom Lane <tgl@sss.pgh.pa.us>, pgsql-hackers@lists.postgresql.org
Date: 2024-02-08T13:16:11Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Use new overflow-safe integer comparison functions.

  2. Introduce overflow-safe integer comparison functions.

  3. Replace calls to pg_qsort() with the qsort() macro.

  4. Switch over to using our own qsort() all the time, as has been proposed

Attachments

On Thu, Feb 8, 2024 at 3:56 AM Nathan Bossart <nathandbossart@gmail.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.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
>

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
>