Re: glibc qsort() vulnerability - Mailing list pgsql-hackers

From Mats Kindahl
Subject Re: glibc qsort() vulnerability
Date
Msg-id CA+14424WBPAsZDk+yq1dMv=aZeF2ePehv+t9rRMur51-FJc0gA@mail.gmail.com
Whole thread Raw
In response to Re: glibc qsort() vulnerability  (Andres Freund <andres@anarazel.de>)
Responses Re: glibc qsort() vulnerability
List pgsql-hackers
On Tue, Feb 13, 2024 at 12:41 AM Andres Freund <andres@anarazel.de> wrote:
Hi,

On 2024-02-12 17:04:23 -0600, Nathan Bossart wrote:
> On Mon, Feb 12, 2024 at 01:31:30PM -0800, Andres Freund wrote:
> > One thing that's worth checking is if this ends up with *worse* code when the
> > comparators are inlined. I think none of the changed comparators will end up
> > getting used with an inlined sort, but ...
>
> Yeah, AFAICT the only inlined sorts are in tuplesort.c and bufmgr.c, and
> the patches don't touch those files.
>
> > The reason we could end up with worse code is that when inlining the
> > comparisons would make less sense for the compiler. Consider e.g.
> >     return DO_COMPARE(a, b) < 0 ?
> >             (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
> >             : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
> >
> > With a naive implementation the compiler will understand it only cares about
> > a < b, not about the other possibilities. I'm not sure that's still true with
> > the more complicated optimized version.
>
> You aren't kidding [0].  Besides perhaps adding a comment in
> sort_template.h, is there anything else you think we should do about this
> now?

I'd add also a comment to the new functions. I think it's fine otherwise. I
wish there were formulation that'd be optimal for both cases, but this way we
can at least adapt all places at once if either find a better formulation or
change all our sorts to happen via an inline implementation of qsort or such.

I suspect that this has to do with the fact that we "abuse" the type system by performing arithmetics on booleans converted to integers and the compilers do not have rules for dealing with these.

For example, with the inline function "static inline cmp(a,b) { return a < b ? -1 : a > b ? 1 : 0; }"

Which trivially can be rewritten by the compiler using very basic rules, as follows:

DO_COMPARE(a,b)
  (a < b ? -1 : a > b ? 1 : 0) < 0
  a < b ? (-1 < 0) : a > b ? (1 < 0) : (0 < 0)
  a < b ? true : a > b ? false : false
  a < b ? true : a > b ? false : false
  a < b ? true : false
  a < b

When it comes to (a < b) - (a > b) there are no such rules added since it is not a very common case.

Clang fares better for this case and at least shows the two alternatives as equal.

Maybe we should change to use the original version equivalent to the inline function above since that works better with surrounding code?

Best wishes,
Mats Kindahl
 

Greetings,

Andres

pgsql-hackers by date:

Previous
From: Michael Paquier
Date:
Subject: Re: Fix incorrect PG_GETARG in pgcrypto
Next
From: Amit Kapila
Date:
Subject: Re: Improve documentation of upgrade for streaming replication section.