On 9/7/22 09:17, Xin Li wrote:
On 9/6/22 23:58, Hans Petter Selasky wrote:
Hi,
Could we also have a test that qsort_b() is not sensitive to the sort
pattern it is given? You are aware about how qsort() works?
Not sure if I'm following... The current qsort_b is essentially a block
version of qsort_r and uses the same code of qsort, so if qsort is
sensitive to certain patterns, it is affected too. The main purpose for
this test case was to verify that qsort_b() actually is sorting and not
a performance test (e.g. it doesn't check for catastrophic cases).
Would you mind elaborating a little bit more about what should be tested?
In my opinion, qsort() should be removed from the kernel. It does
I'm not sure if removing qsort() interface from the kernel is a good
idea, because apparently it's being used in a lot of places. Note that
it doesn't have to be the current implementation, we can always replace
it with something better if available.
sorting, but is not reliable for all kinds of unsorted data! And can
explode into stack usage ...
Speaking for stack usage, I _think_ I've fixed the qsort(3) code to
perform at most log2(N) levels of recursion in 2017 (svn r318515 /
ca1578f0), and before the fix it could potentially recurse N levels, no?
Was this the stack explode that you are referring to, or did you mean
some other cases that we haven't considered (in which case, it can
potentially be SA worthy).
Hi Xin,
I'm not sure about the current state of qsort(), but I have a test
program which you may want to try and it looks like there may still be a
CPU hog issue in there!
Just read the attached code to figure out the meaning of the arguments.
The test program compares mergesort(), qsort() and my mbin_sort()
algorithm, and also includes an exhaustive test trying all kinds of
patters within a certain range.
git clone https://github.com/hselasky/libmbin
cd libmbin
make all install
You need to compile and install my libmbin from github before trying this:
# Ask qsort() in libc to sort the vulnerable pattern:
cc -lmbin1 -lm mergesort.c && time ./a.out 10 2 0
0.241u 0.000s 0:00.24 100.0% 5+170k 0+0io 0pf+0w
# Ask mbin_sort() in libmbin to sort the vulnerable pattern:
cc -lmbin1 -lm mergesort.c && time ./a.out 10 2 2
0.086u 0.000s 0:00.08 100.0% 5+181k 0+0io 0pf+0w
# Ask mergesort() in libc to sort the vulnerable pattern:
cc -lmbin1 -lm mergesort.c && time ./a.out 10 2 3
0.075u 0.007s 0:00.08 87.5% 6+207k 0+0io 0pf+0w
The number 10 means 2 in the power of 10 elements. May be raised. See
attachment!
--HPS
#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math_bin.h>
uint32_t calls;
static int
hps_compare(const void *pa, const void *pb)
{
uintptr_t a = (uintptr_t)*(void **)pa;
uintptr_t b = (uintptr_t)*(void **)pb;
if (a > b)
return (1);
else if (a < b)
return (-1);
return (0);
}
static void
hps_bad(void **v, uint32_t n)
{
uint32_t i;
for (i = 0; i < n / 2; i++)
v[i] = (void *)(uintptr_t)(n / 2 - i);
v[n / 2] = (void *)(uintptr_t)(n / 2 + 1);
for (i = n / 2 + 1; i < n; i++)
v[i] = (void *)(uintptr_t)(n + n / 2 + 1 - i);
}
#define CMP(t,a,b) ((*a < *b) ? -1 : (*a > *b) ? 1 : 0)
#define swap(a,b) do { \
void *tmp = *a; \
*a = *b; \
*b = tmp; \
} while(0)
static void
hps_test()
{
uintptr_t a, b, c, d, e, f, g, h;
void *array[8];
void *copy[8];
for (a = 0; a != 8; a++) {
for (b = 0; b != 8; b++) {
for (c = 0; c != 8; c++) {
for (d = 0; d != 8; d++) {
for (e = 0; e != 8; e++) {
for (f = 0; f != 8; f++) {
for (g = 0; g != 8; g++) {
for (h = 0; h != 8; h++) {
array[0] = (void *)(uintptr_t)a;
array[1] = (void *)(uintptr_t)b;
array[2] = (void *)(uintptr_t)c;
array[3] = (void *)(uintptr_t)d;
array[4] = (void *)(uintptr_t)e;
array[5] = (void *)(uintptr_t)f;
array[6] = (void *)(uintptr_t)g;
array[7] = (void *)(uintptr_t)h;
memcpy(copy, array, sizeof(copy));
mbin_sort(array, 8, sizeof(void *), &hps_compare);
qsort(copy, 8, sizeof(void *), &hps_compare);
if (memcmp(array, copy, sizeof(array)) != 0)
printf("%zd %zd %zd %zd %zd %zd %zd %zd\n",
(uintptr_t)array[0], (uintptr_t)array[1], (uintptr_t)array[2], (uintptr_t)array[3],
(uintptr_t)array[4], (uintptr_t)array[5], (uintptr_t)array[6], (uintptr_t)array[7]);
}
}
}
}
}
}
}
}
}
int
main(int argc, char **argv)
{
#ifdef HPS_TEST
hps_test();
return (0);
#endif
if (argc < 4)
return (0);
uint32_t LBASE = atoi(argv[1]);
uint32_t BASE = (1 << LBASE);
uint32_t algo = atoi(argv[2]);
uint32_t data = atoi(argv[3]);
void *array[BASE + BASE];
unsigned x;
unsigned y;
unsigned z;
for (z = 0; z != 1024; z++) {
if (data == 0) {
for (x = 0; x != BASE; x++) {
if (x > 4 && (random() & 1)) {
array[BASE + x] = array[BASE + x - 4];
} else
array[BASE + x] = (void *)(uintptr_t)((uint32_t)(random() /* % BASE */ ));
*(short *)&array[BASE + x] = x;
}
} else if (data == 1) {
for (x = 0; x != BASE; x++) {
array[BASE + x] = (void *)(uintptr_t)(random() % BASE);
}
} else {
hps_bad(array + BASE, BASE);
}
if (algo == 0)
qsort(array + BASE, BASE, sizeof(void *), hps_compare);
else if (algo == 1)
qsort(array + BASE, BASE, sizeof(void *), hps_compare);
else if (algo == 2)
mbin_sort(array + BASE, BASE, sizeof(void *), hps_compare);
else
mergesort(array + BASE, BASE, sizeof(void *), hps_compare);
#ifdef HPS_VERIFY
memcpy(array, array + BASE, sizeof(array[0]) * BASE);
for (x = 0; x != BASE; x++) {
if (x + 1 < BASE &&
(uintptr_t)array[BASE + x] > (uintptr_t)array[BASE + x + 1]) {
printf("WRAP\n");
}
}
for (x = 0; x != BASE; x++) {
for (y = x + 1; y != BASE; y++) {
if (array[x] == array[y]) {
x++;
if (x != y) {
printf("SORT ERROR %d %d\n", x, y);
return (0);
}
}
}
}
#endif
}
return (0);
}
