Date: Wed, 7 Sep 2022 09:55:39 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Xin Li <delphij@FreeBSD.org>, src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: Re: git: c65e42dbde41 - main - libc: add test case for qsort_b(3) Message-ID: <9801581e-ac26-c41b-e987-ee3bb954417d@selasky.org> In-Reply-To: <dfd11cf5-48e8-7eec-deb6-539a4d2d56c3@FreeBSD.org> References: <202209070612.2876C6ko054410@gitrepo.freebsd.org> <ca85bb26-0432-adc8-e8bd-24a6f26890b5@selasky.org> <dfd11cf5-48e8-7eec-deb6-539a4d2d56c3@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
[-- Attachment #1 --] 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 [-- Attachment #2 --] #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); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?9801581e-ac26-c41b-e987-ee3bb954417d>