Horton

Re: glibc qsort() vulnerability

Andrey Borodin <x4mmm@yandex-team.ru>

View thread
From: Andrey Borodin <x4mmm@yandex-team.ru>
To: Nathan Bossart <nathandbossart@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 mailing list <pgsql-hackers@lists.postgresql.org>
Date: 2024-02-09T19:02:08Z
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


> On 9 Feb 2024, at 21:32, Nathan Bossart <nathandbossart@gmail.com> wrote:
>  a lot
> of current use-cases require inspecting specific fields of structs
Yes, I'm proposing to pass to sorting routine not a comparator, but value extractor. And then rely on operators <,>,==.
In a pseudocode: instead of sort(array, (a,b)->a.field-b.field) use sort(array, x->x.field). And rely on "field" being comparable.

> If that can be made simple and elegant and
> demonstrates substantial improvements
I'll try to produce a PoC and measure it with Andres' intarray test.

> On 9 Feb 2024, at 23:40, Andres Freund <andres@anarazel.de> wrote:
> 
> We have some infrastructure for that actually, see sort_template.h.  But
> perhaps we should define a static inline of the generic pg_qsort() even. OTOH,
> plenty places that'll just end up to a pointless amount of code emitted to
> sort ~5 elements on average.
I think there might be another benefit. It's easier to think about values order than function comparator that returns -1,0,+1...

>> I bet “call" is more expensive than “if".
> 
> Not really in this case. The call is perfectly predictable - a single qsort()
> will use the same callback for every comparison, whereas the if is perfectly
> *unpredictable*.  A branch mispredict is far more expensive than a correctly
> predicted function call.

Oh, make sense... I did not understand that. But does cpu predicts what instruction to fetch even after a call instruction? These cpus are really neat things... so, probably, yes, it does.


Best regards, Andrey Borodin.