ldb: avoid out of bounds read and write in ldb_qsort()
If a compare function is non-transitive (for example, if it evaluates
A > B and B > C, but A < C), this implementation of qsort could access
out-of-bounds memory. This was found in glibc's qsort by Qualys, and
their write-up for OSS-Security explains it very well:
https://www.openwall.com/lists/oss-security/2024/01/30/7
An example of a non-transitive compare is one in which does this
int cmp(const void *_a, const void *_b)
{
int a = *(int *)_a;
int b = *(int *)_b;
return a - b;
}
which does the right thing when the magnitude of the numbers is small,
but which will go wrong if a is INT_MIN and b is INT_MAX. Likewise, if
a and b are e.g. uint32_t, the value can wrap when cast to int.
We have functions that are non-transitive regardless of subtraction.
For example, here (which is not used with ldb_qsort):
int codepoint_cmpi(codepoint_t c1, codepoint_t c2)
if (c1 == c2 ||
toupper_m(c1) == toupper_m(c2)) {
return 0;
}
return c1 - c2;
}
The toupper_m() is only called on equality case. Consider {'a', 'A', 'B'}.
'a' == 'A'
'a' > 'B' (lowercase letters come after upper)
'A' < 'B'
BUG: https://bugzilla.samba.org/show_bug.cgi?id=15569
BUG: https://bugzilla.samba.org/show_bug.cgi?id=15625
Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>