Re: glibc qsort() vulnerability

On Fri, Feb 16, 2024 at 9:09 PM Nathan Bossart wrote: > On Fri, Feb 16, 2024 at 01:45:52PM +0100, Mats Kindahl wrote: > > Looks good to me. > > Committed. > Thanks Nathan! > > -- > Nathan Bossart > Amazon Web Services: https://aws.amazon.com >

Re: glibc qsort() vulnerability

On Fri, Feb 16, 2024 at 01:45:52PM +0100, Mats Kindahl wrote: > Looks good to me. Committed. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com

Re: glibc qsort() vulnerability

On Fri, Feb 16, 2024 at 12:32 AM Nathan Bossart wrote: > Here is what I have staged for commit. > Looks good to me. Checked that all of the comparisons are in the expected order, except inside compDESC, cmp_lsn, and resource_priority_cmp, where the order is reversed. Best wishes, Mats Kindahl

Re: glibc qsort() vulnerability

Here is what I have staged for commit. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com >From 8e5a66fb3a0787f15a900a89742862c89da38a1d Mon Sep 17 00:00:00 2001 From: Nathan Bossart Date: Thu, 15 Feb 2024 10:53:11 -0600 Subject: [PATCH v8 1/3] Remove direct calls to pg_qsort().

Re: glibc qsort() vulnerability

On Tue, Feb 13, 2024 at 09:43:18AM +0100, Mats Kindahl wrote: > Maybe we should change to use the original version equivalent to the inline > function above since that works better with surrounding code? I don't think that's necessary. We just need to be cognizant of it when using inlined sorts,

Re: glibc qsort() vulnerability

On Tue, Feb 13, 2024 at 12:41 AM Andres Freund 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

Re: glibc qsort() vulnerability

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 > >

Re: glibc qsort() vulnerability

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

Re: glibc qsort() vulnerability

Hi, On 2024-02-12 14:51:38 -0600, Nathan Bossart wrote: > On Mon, Feb 12, 2024 at 06:09:06PM +0100, Mats Kindahl wrote: > > Here are the two fixed patches. > > These patches look pretty good to me. Barring additional feedback, I'll > plan on committing them in the next few days. One thing

Re: glibc qsort() vulnerability

On Mon, Feb 12, 2024 at 5:51 PM Nathan Bossart wrote: > > On Mon, Feb 12, 2024 at 06:09:06PM +0100, Mats Kindahl wrote: > > Here are the two fixed patches. > > These patches look pretty good to me. Barring additional feedback, I'll > plan on committing them in the next few days. > Also did some

Re: glibc qsort() vulnerability

On Mon, Feb 12, 2024 at 06:09:06PM +0100, Mats Kindahl wrote: > Here are the two fixed patches. These patches look pretty good to me. Barring additional feedback, I'll plan on committing them in the next few days. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com

Re: glibc qsort() vulnerability

On Mon, Feb 12, 2024 at 4:57 PM Nathan Bossart wrote: > On Sun, Feb 11, 2024 at 03:44:42PM +0100, Mats Kindahl wrote: > > On Sat, Feb 10, 2024 at 9:53 PM Nathan Bossart > > > wrote: > >> and I think we should expand on some of the commentary in int.h. > >> For example, the comment at the top of

Re: glibc qsort() vulnerability

On Sun, Feb 11, 2024 at 03:44:42PM +0100, Mats Kindahl wrote: > On Sat, Feb 10, 2024 at 9:53 PM Nathan Bossart > wrote: >> and I think we should expand on some of the commentary in int.h. >> For example, the comment at the top of int.h seems very tailored to the >> existing functions and should

Re: glibc qsort() vulnerability

On Sat, Feb 10, 2024 at 9:53 PM Nathan Bossart wrote: > On Sat, Feb 10, 2024 at 08:59:06AM +0100, Mats Kindahl wrote: > > Split the code into two patches: one that just adds the functions > > (including the new pg_cmp_size()) to common/int.h and one that starts > using > > them. I picked the

Re: glibc qsort() vulnerability

On Sat, Feb 10, 2024 at 08:59:06AM +0100, Mats Kindahl wrote: > Split the code into two patches: one that just adds the functions > (including the new pg_cmp_size()) to common/int.h and one that starts using > them. I picked the name "pg_cmp_size" rather than "pg_cmp_size_t" since > "_t" is

Re: glibc qsort() vulnerability

On Fri, Feb 9, 2024 at 9:08 PM Nathan Bossart wrote: > On Fri, Feb 09, 2024 at 08:43:21PM +0100, Mats Kindahl wrote: > > QQ: right now it looks like this: > > > > static inline int > > pg_cmp_u16(uint16 a, uint16 b) > > { > > > > return (int32)a - (int32)b; > > > > } > > > > > > and > > > >

Re: glibc qsort() vulnerability

On Fri, Feb 09, 2024 at 08:43:21PM +0100, Mats Kindahl wrote: > QQ: right now it looks like this: > > static inline int > pg_cmp_u16(uint16 a, uint16 b) > { > > return (int32)a - (int32)b; > > } > > > and > > static inline int > pg_cmp_u32(uint32 a, uint32 b) > { > > return (a > b) - (a <

Re: glibc qsort() vulnerability

On 2024-02-09 14:04:29 -0600, Nathan Bossart wrote: > On Fri, Feb 09, 2024 at 08:40:47PM +0100, Mats Kindahl wrote: > > On Fri, Feb 9, 2024 at 5:27 PM Tom Lane wrote: > >> We do pretty much assume that "int" is "int32". But I agree that > >> assuming anything about the width of size_t is bad. I

Re: glibc qsort() vulnerability

On Fri, Feb 09, 2024 at 08:40:47PM +0100, Mats Kindahl wrote: > On Fri, Feb 9, 2024 at 5:27 PM Tom Lane wrote: >> We do pretty much assume that "int" is "int32". But I agree that >> assuming anything about the width of size_t is bad. I think we need >> a separate pg_cmp_size() or

Re: glibc qsort() vulnerability

On Fri, Feb 9, 2024 at 8:26 PM Mats Kindahl wrote: > On Fri, Feb 9, 2024 at 5:24 PM Nathan Bossart > wrote: > >> On Fri, Feb 09, 2024 at 08:52:26AM +0100, Mats Kindahl wrote: >> > Here is a new version introducing pg_cmp_s32 and friends and use them >> > instead of the INT_CMP macro introduced

Re: glibc qsort() vulnerability

On Fri, Feb 9, 2024 at 5:27 PM Tom Lane wrote: > Nathan Bossart writes: > > On Fri, Feb 09, 2024 at 08:52:26AM +0100, Mats Kindahl wrote: > >> The types "int" and "size_t" are treated as s32 and u32 respectively > since > >> that seems to be the case for most of the code, even if strictly not >

Re: glibc qsort() vulnerability

On Fri, Feb 9, 2024 at 5:27 PM Tom Lane wrote: > Nathan Bossart writes: > > On Fri, Feb 09, 2024 at 08:52:26AM +0100, Mats Kindahl wrote: > >> The types "int" and "size_t" are treated as s32 and u32 respectively > since > >> that seems to be the case for most of the code, even if strictly not >

Re: glibc qsort() vulnerability

On Fri, Feb 9, 2024 at 5:24 PM Nathan Bossart wrote: > On Fri, Feb 09, 2024 at 08:52:26AM +0100, Mats Kindahl wrote: > > Here is a new version introducing pg_cmp_s32 and friends and use them > > instead of the INT_CMP macro introduced before. It also moves the > > definitions to common/int.h and

Re: glibc qsort() vulnerability

Hi, On 2024-02-10 00:02:08 +0500, Andrey Borodin wrote: > > 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

Re: glibc qsort() vulnerability

> On 9 Feb 2024, at 21:32, Nathan Bossart 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,

Re: glibc qsort() vulnerability

Hi, On 2024-02-09 13:19:49 +0500, Andrey M. Borodin wrote: > > On 8 Feb 2024, at 06:52, Nathan Bossart wrote: > > For the same compASC() test, I see an ~8.4% improvement with your int64 > > code and a ~3.4% improvement with this: > > If we care about branch prediction in comparison function,

Re: glibc qsort() vulnerability

On Fri, Feb 09, 2024 at 01:19:49PM +0500, Andrey M. Borodin wrote: > If we care about branch prediction in comparison function, maybe we could > produce sorting that inlines comparator, thus eliminating function call > to comparator? We convert comparison logic to int, to extract comparison > back

Re: glibc qsort() vulnerability

Nathan Bossart writes: > On Fri, Feb 09, 2024 at 08:52:26AM +0100, Mats Kindahl wrote: >> The types "int" and "size_t" are treated as s32 and u32 respectively since >> that seems to be the case for most of the code, even if strictly not >> correct (size_t can be an unsigned long int for some

Re: glibc qsort() vulnerability

On Fri, Feb 09, 2024 at 08:52:26AM +0100, Mats Kindahl wrote: > Here is a new version introducing pg_cmp_s32 and friends and use them > instead of the INT_CMP macro introduced before. It also moves the > definitions to common/int.h and adds that as an include to all locations > using these

Re: glibc qsort() vulnerability

> On 8 Feb 2024, at 06:52, Nathan Bossart wrote: > > For the same compASC() test, I see an ~8.4% improvement with your int64 > code and a ~3.4% improvement with this: If we care about branch prediction in comparison function, maybe we could produce sorting that inlines comparator, thus

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 9:39 PM Tom Lane wrote: > Nathan Bossart writes: > > On Thu, Feb 08, 2024 at 11:59:54AM -0800, Andres Freund wrote: > >> I'd put these static inlines into common/int.h. I don't think this is > common > >> enough to warrant being in c.h. Probably also doesn't hurt to have

Re: glibc qsort() vulnerability

Nathan Bossart writes: > On Thu, Feb 08, 2024 at 11:59:54AM -0800, Andres Freund wrote: >> I'd put these static inlines into common/int.h. I don't think this is common >> enough to warrant being in c.h. Probably also doesn't hurt to have a not >> quite >> as generic name as INT_CMP, I'd not be

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 9:07 PM Nathan Bossart wrote: > On Thu, Feb 08, 2024 at 11:59:54AM -0800, Andres Freund wrote: > > On 2024-02-08 13:44:02 -0500, Tom Lane wrote: > >> Are we okay with using macros that (a) have double evaluation hazards > >> and (b) don't enforce the data types being

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 7:44 PM Tom Lane wrote: > Nathan Bossart writes: > > On Thu, Feb 08, 2024 at 02:16:11PM +0100, Mats Kindahl wrote: > >> +/* > >> + * Compare two integers and return -1, 0, or 1 without risking > overflow. > >> + * > >> + * This macro is used to avoid running into overflow

Re: glibc qsort() vulnerability

On Thu, Feb 08, 2024 at 11:59:54AM -0800, Andres Freund wrote: > On 2024-02-08 13:44:02 -0500, Tom Lane wrote: >> Are we okay with using macros that (a) have double evaluation hazards >> and (b) don't enforce the data types being compared are the same? >> I think static inlines might be a safer

Re: glibc qsort() vulnerability

Hi, On 2024-02-08 13:44:02 -0500, Tom Lane wrote: > Nathan Bossart writes: > > On Thu, Feb 08, 2024 at 02:16:11PM +0100, Mats Kindahl wrote: > >> +/* > >> + * Compare two integers and return -1, 0, or 1 without risking overflow. > >> + * > >> + * This macro is used to avoid running into overflow

Re: glibc qsort() vulnerability

Nathan Bossart writes: > On Thu, Feb 08, 2024 at 02:16:11PM +0100, Mats Kindahl wrote: >> +/* >> + * Compare two integers and return -1, 0, or 1 without risking overflow. >> + * >> + * This macro is used to avoid running into overflow issues because a simple >> + * subtraction of the two values

Re: glibc qsort() vulnerability

On Thu, Feb 08, 2024 at 02:16:11PM +0100, Mats Kindahl wrote: > +/* > + * Compare two integers and return -1, 0, or 1 without risking overflow. > + * > + * This macro is used to avoid running into overflow issues because a simple > + * subtraction of the two values when implementing a cmp function

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 3:56 AM Nathan Bossart 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 > wrote: > >> Perhaps you could wrap it in a branch-free sign() function so you get > >> a narrow answer? > >> > >>

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 12:01 PM Mats Kindahl wrote: > On Wed, Feb 7, 2024 at 9:56 PM Nathan Bossart > wrote: > >> On Wed, Feb 07, 2024 at 08:46:56PM +0200, Heikki Linnakangas wrote: >> > Doesn't hurt to fix the comparison functions, and +1 on using the same >> > pattern everywhere. >> >> I

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 4:08 AM Nathan Bossart wrote: > Mats, I apologize for steamrolling a bit here. I'll take a step back into > a reviewer role. > No worries. :) > > -- > Nathan Bossart > Amazon Web Services: https://aws.amazon.com >

Re: glibc qsort() vulnerability

On Wed, Feb 7, 2024 at 9:56 PM Nathan Bossart wrote: > On Wed, Feb 07, 2024 at 08:46:56PM +0200, Heikki Linnakangas wrote: > > Doesn't hurt to fix the comparison functions, and +1 on using the same > > pattern everywhere. > > I attached a new version of the patch with some small adjustments. I

Re: glibc qsort() vulnerability

Mats, I apologize for steamrolling a bit here. I'll take a step back into a reviewer role. -- Nathan Bossart Amazon Web Services: https://aws.amazon.com

Re: glibc qsort() vulnerability

On Thu, Feb 08, 2024 at 03:49:03PM +1300, Thomas Munro wrote: > On Thu, Feb 8, 2024 at 3:38 PM Thomas Munro 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,

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 3:38 PM Thomas Munro 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

Re: glibc qsort() vulnerability

On Wed, Feb 07, 2024 at 06:06:37PM -0800, Andres Freund wrote: > Another branchless variant is (a > b) - (a < b). It seems to get a similar > improvement as the overflow-checking version. Well, that's certainly more elegant. I updated the patch to that approach for now. -- Nathan Bossart

Re: glibc qsort() vulnerability

On Thu, Feb 8, 2024 at 3:06 PM Andres Freund wrote: > On 2024-02-07 19:52:11 -0600, Nathan Bossart wrote: > > On Wed, Feb 07, 2024 at 04:42:07PM -0800, Andres Freund wrote: > > > On 2024-02-07 16:21:24 -0600, Nathan Bossart wrote: > > >> The assembly for that looks encouraging, but I still need

Re: glibc qsort() vulnerability

Hi, On 2024-02-07 19:52:11 -0600, Nathan Bossart wrote: > On Wed, Feb 07, 2024 at 04:42:07PM -0800, Andres Freund wrote: > > On 2024-02-07 16:21:24 -0600, Nathan Bossart wrote: > >> The assembly for that looks encouraging, but I still need to actually test > >> it... > > > > Possible. For 16bit

Re: glibc qsort() vulnerability

On Wed, Feb 07, 2024 at 04:42:07PM -0800, Andres Freund wrote: > On 2024-02-07 16:21:24 -0600, Nathan Bossart wrote: >> The assembly for that looks encouraging, but I still need to actually test >> it... > > Possible. For 16bit upcasting to 32bit is clearly the best way. For 32 bit > that doesn't

Re: glibc qsort() vulnerability

Hi, On 2024-02-07 16:21:24 -0600, Nathan Bossart wrote: > On Wed, Feb 07, 2024 at 01:48:57PM -0800, Andres Freund wrote: > > Now, in most cases this won't matter, the sorting isn't performance > > critical. But I don't think it's a good idea to standardize on a generally > > slower pattern. > >

Re: glibc qsort() vulnerability

On Wed, Feb 07, 2024 at 01:48:57PM -0800, Andres Freund wrote: > Now, in most cases this won't matter, the sorting isn't performance > critical. But I don't think it's a good idea to standardize on a generally > slower pattern. > > Not that that's a good test, but I did quickly benchmark [1] this

Re: glibc qsort() vulnerability

Hi, On 2024-02-07 20:46:56 +0200, Heikki Linnakangas wrote: > > The routines modified do a subtraction of int:s and return that, which > > can cause an overflow. This method is used for some int16 as well but > > since standard conversions in C will perform the arithmetics in "int" > > precision,

Re: glibc qsort() vulnerability

On Wed, Feb 07, 2024 at 08:46:56PM +0200, Heikki Linnakangas wrote: > Doesn't hurt to fix the comparison functions, and +1 on using the same > pattern everywhere. I attached a new version of the patch with some small adjustments. I haven't looked through all in-tree qsort() comparators to see if

Re: glibc qsort() vulnerability

On 07/02/2024 11:09, Mats Kindahl wrote: On Tue, Feb 6, 2024 at 9:56 PM Tom Lane > wrote: Nathan Bossart mailto:nathandboss...@gmail.com>> writes: > Even if the glibc issue doesn't apply to Postgres, I'm tempted to suggest > that we make it project

Re: glibc qsort() vulnerability

On Tue, Feb 6, 2024 at 9:56 PM Tom Lane wrote: > Nathan Bossart writes: > > Even if the glibc issue doesn't apply to Postgres, I'm tempted to suggest > > that we make it project policy that comparison functions must be > > transitive. There might be no real issues today, but if we write all >

Re: glibc qsort() vulnerability

On Tue, Feb 6, 2024 at 4:11 PM Tom Lane wrote: > Mats Kindahl writes: > > There is a bug in glibc's qsort() algorithm that runs the risk of > creating > > an out-of-bounds error if the comparison function is not transitive, for > > example, if subtraction is used so that it can create an

Re: glibc qsort() vulnerability

On Tue, Feb 06, 2024 at 03:55:58PM -0500, Tom Lane wrote: > A comparison routine that is not is probably broken, agreed. > I didn't look through the details of the patch --- I was more > curious whether we had a version of the qsort bug, because > if we do, we should fix that too. +1 -- Nathan

Re: glibc qsort() vulnerability

Nathan Bossart writes: > Even if the glibc issue doesn't apply to Postgres, I'm tempted to suggest > that we make it project policy that comparison functions must be > transitive. There might be no real issues today, but if we write all > comparison functions the way Mats is suggesting, it

Re: glibc qsort() vulnerability

On Tue, Feb 06, 2024 at 10:11:16AM -0500, Tom Lane wrote: > Mats Kindahl writes: >> There is a bug in glibc's qsort() algorithm that runs the risk of creating >> an out-of-bounds error if the comparison function is not transitive, for >> example, if subtraction is used so that it can create an

Re: glibc qsort() vulnerability

Mats Kindahl writes: > There is a bug in glibc's qsort() algorithm that runs the risk of creating > an out-of-bounds error if the comparison function is not transitive, for > example, if subtraction is used so that it can create an overflow. We don't use glibc's qsort. Have you checked whether

glibc qsort() vulnerability

Hi hackers, There is a bug in glibc's qsort() algorithm that runs the risk of creating an out-of-bounds error if the comparison function is not transitive, for example, if subtraction is used so that it can create an overflow. See