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, this cannot overflow, so added a comment there. It might
> > still be a good idea to follow the same pattern for the int16 routines,
> > but since there is no bug there, I did not add them to the patch.
>
> Doesn't hurt to fix the comparison functions, and +1 on using the same
> pattern everywhere.

It actually can hurt - the generated code will often be slower.

E.g.
#include <stdint.h>

int cmp_sub(int16_t a, int16_t b) {
return (int32_t) a - (int32_t) b;
}

int cmp_if(int16_t a, int16_t b) {
if (a < b)
return -1;
if (a > b)
return 1;
return 0;
}

yields

cmp_sub:
movsx eax, di
movsx esi, si
sub eax, esi
ret
cmp_if:
xor eax, eax
cmp di, si
mov edx, -1
setg al
cmovl eax, edx
ret

with gcc -O3. With other compilers, e.g. msvc, the difference is considerably
bigger, due to msvc for some reason not using cmov.

See https://godbolt.org/z/34qerPaPE for a few more details.

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 with
intarray. There's about a 10% difference in performance between using the
existing compASC() and one using
return (int64) *(const int32 *) a - (int64) *(const int32 *) b;

Perhaps we could have a central helper for this somewhere?

Greetings,

Andres Freund

[1]
-- prep
CREATE EXTENSION IF NOT EXISTS intarray;
DROP TABLE IF EXISTS arrays_to_sort;
CREATE TABLE arrays_to_sort AS SELECT array_shuffle(a) arr FROM (SELECT ARRAY(SELECT generate_series(1, 1000000)) a), generate_series(1, 10);
-- bench
SELECT (sort(arr))[1] FROM arrays_to_sort;