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
This is a multi-part message in MIME format. --------------jv9htCQdi0xpKAaYlIFoqU0I Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit 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 --------------jv9htCQdi0xpKAaYlIFoqU0I Content-Type: text/x-csrc; charset=UTF-8; name="mergesort.c" Content-Disposition: attachment; filename="mergesort.c" Content-Transfer-Encoding: base64 I2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGlu dC5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxtYXRoX2Jpbi5oPgoKdWludDMy X3QgY2FsbHM7CgpzdGF0aWMgaW50Cmhwc19jb21wYXJlKGNvbnN0IHZvaWQgKnBhLCBjb25z dCB2b2lkICpwYikKewp1aW50cHRyX3QgYSA9ICh1aW50cHRyX3QpKih2b2lkICoqKXBhOwp1 aW50cHRyX3QgYiA9ICh1aW50cHRyX3QpKih2b2lkICoqKXBiOwoKCWlmIChhID4gYikKCQly ZXR1cm4gKDEpOwoJZWxzZSBpZiAoYSA8IGIpCgkJcmV0dXJuICgtMSk7CgoJcmV0dXJuICgw KTsKfQoKc3RhdGljIHZvaWQKaHBzX2JhZCh2b2lkICoqdiwgdWludDMyX3QgbikKewoJdWlu dDMyX3QgaTsKCglmb3IgKGkgPSAwOyBpIDwgbiAvIDI7IGkrKykKCQl2W2ldID0gKHZvaWQg KikodWludHB0cl90KShuIC8gMiAtIGkpOwoJdltuIC8gMl0gPSAodm9pZCAqKSh1aW50cHRy X3QpKG4gLyAyICsgMSk7Cglmb3IgKGkgPSBuIC8gMiArIDE7IGkgPCBuOyBpKyspCgkJdltp XSA9ICh2b2lkICopKHVpbnRwdHJfdCkobiArIG4gLyAyICsgMSAtIGkpOwp9CgojZGVmaW5l CUNNUCh0LGEsYikgKCgqYSA8ICpiKSA/IC0xIDogKCphID4gKmIpID8gMSA6IDApCgojZGVm aW5lCXN3YXAoYSxiKSBkbyB7CQkJCVwKdm9pZCAqdG1wID0gKmE7CQkJCQlcCiphID0gKmI7 CQkJCQlcCipiID0gdG1wOwkJCQkJXAp9IHdoaWxlKDApCgpzdGF0aWMgdm9pZApocHNfdGVz dCgpCnsKCXVpbnRwdHJfdCBhLCBiLCBjLCBkLCBlLCBmLCBnLCBoOwoJdm9pZCAqYXJyYXlb OF07Cgl2b2lkICpjb3B5WzhdOwoKCWZvciAoYSA9IDA7IGEgIT0gODsgYSsrKSB7CgkJZm9y IChiID0gMDsgYiAhPSA4OyBiKyspIHsKCQkJZm9yIChjID0gMDsgYyAhPSA4OyBjKyspIHsK CQkJCWZvciAoZCA9IDA7IGQgIT0gODsgZCsrKSB7CgkJCQkJZm9yIChlID0gMDsgZSAhPSA4 OyBlKyspIHsKCQkJCQkJZm9yIChmID0gMDsgZiAhPSA4OyBmKyspIHsKCQkJCQkJCWZvciAo ZyA9IDA7IGcgIT0gODsgZysrKSB7CgkJCQkJCQkJZm9yIChoID0gMDsgaCAhPSA4OyBoKysp IHsKCQkJCQkJCQkJYXJyYXlbMF0gPSAodm9pZCAqKSh1aW50cHRyX3QpYTsKCQkJCQkJCQkJ YXJyYXlbMV0gPSAodm9pZCAqKSh1aW50cHRyX3QpYjsKCQkJCQkJCQkJYXJyYXlbMl0gPSAo dm9pZCAqKSh1aW50cHRyX3QpYzsKCQkJCQkJCQkJYXJyYXlbM10gPSAodm9pZCAqKSh1aW50 cHRyX3QpZDsKCQkJCQkJCQkJYXJyYXlbNF0gPSAodm9pZCAqKSh1aW50cHRyX3QpZTsKCQkJ CQkJCQkJYXJyYXlbNV0gPSAodm9pZCAqKSh1aW50cHRyX3QpZjsKCQkJCQkJCQkJYXJyYXlb Nl0gPSAodm9pZCAqKSh1aW50cHRyX3QpZzsKCQkJCQkJCQkJYXJyYXlbN10gPSAodm9pZCAq KSh1aW50cHRyX3QpaDsKCgkJCQkJCQkJCW1lbWNweShjb3B5LCBhcnJheSwgc2l6ZW9mKGNv cHkpKTsKCgkJCQkJCQkJCW1iaW5fc29ydChhcnJheSwgOCwgc2l6ZW9mKHZvaWQgKiksICZo cHNfY29tcGFyZSk7CgkJCQkJCQkJCXFzb3J0KGNvcHksIDgsIHNpemVvZih2b2lkICopLCAm aHBzX2NvbXBhcmUpOwoKCQkJCQkJCQkJaWYgKG1lbWNtcChhcnJheSwgY29weSwgc2l6ZW9m KGFycmF5KSkgIT0gMCkKCQkJCQkJCQkJCXByaW50ZigiJXpkICV6ZCAlemQgJXpkICV6ZCAl emQgJXpkICV6ZFxuIiwKCQkJCQkJCQkJCSAgICAodWludHB0cl90KWFycmF5WzBdLCAodWlu dHB0cl90KWFycmF5WzFdLCAodWludHB0cl90KWFycmF5WzJdLCAodWludHB0cl90KWFycmF5 WzNdLAoJCQkJCQkJCQkJICAgICh1aW50cHRyX3QpYXJyYXlbNF0sICh1aW50cHRyX3QpYXJy YXlbNV0sICh1aW50cHRyX3QpYXJyYXlbNl0sICh1aW50cHRyX3QpYXJyYXlbN10pOwoJCQkJ CQkJCX0KCQkJCQkJCX0KCQkJCQkJfQoJCQkJCX0KCQkJCX0KCQkJfQoJCX0KCX0KfQoKaW50 Cm1haW4oaW50IGFyZ2MsIGNoYXIgKiphcmd2KQp7CiNpZmRlZiBIUFNfVEVTVAoJaHBzX3Rl c3QoKTsKCXJldHVybiAoMCk7CiNlbmRpZgoKCWlmIChhcmdjIDwgNCkKCQlyZXR1cm4gKDAp OwoKCXVpbnQzMl90IExCQVNFID0gYXRvaShhcmd2WzFdKTsKCXVpbnQzMl90IEJBU0UgPSAo MSA8PCBMQkFTRSk7Cgl1aW50MzJfdCBhbGdvID0gYXRvaShhcmd2WzJdKTsKCXVpbnQzMl90 IGRhdGEgPSBhdG9pKGFyZ3ZbM10pOwoKCXZvaWQgKmFycmF5W0JBU0UgKyBCQVNFXTsKCXVu c2lnbmVkIHg7Cgl1bnNpZ25lZCB5OwoJdW5zaWduZWQgejsKCglmb3IgKHogPSAwOyB6ICE9 IDEwMjQ7IHorKykgewoKCQlpZiAoZGF0YSA9PSAwKSB7CgkJCWZvciAoeCA9IDA7IHggIT0g QkFTRTsgeCsrKSB7CgkJCQlpZiAoeCA+IDQgJiYgKHJhbmRvbSgpICYgMSkpIHsKCQkJCQlh cnJheVtCQVNFICsgeF0gPSBhcnJheVtCQVNFICsgeCAtIDRdOwoJCQkJfSBlbHNlCgkJCQkJ YXJyYXlbQkFTRSArIHhdID0gKHZvaWQgKikodWludHB0cl90KSgodWludDMyX3QpKHJhbmRv bSgpIC8qICUgQkFTRSAqLyApKTsKCgkJCQkqKHNob3J0ICopJmFycmF5W0JBU0UgKyB4XSA9 IHg7CgkJCX0KCQl9IGVsc2UgaWYgKGRhdGEgPT0gMSkgewoJCQlmb3IgKHggPSAwOyB4ICE9 IEJBU0U7IHgrKykgewoJCQkJYXJyYXlbQkFTRSArIHhdID0gKHZvaWQgKikodWludHB0cl90 KShyYW5kb20oKSAlIEJBU0UpOwoJCQl9CgkJfSBlbHNlIHsKCQkJaHBzX2JhZChhcnJheSAr IEJBU0UsIEJBU0UpOwoJCX0KCgkJaWYgKGFsZ28gPT0gMCkKCQkJcXNvcnQoYXJyYXkgKyBC QVNFLCBCQVNFLCBzaXplb2Yodm9pZCAqKSwgaHBzX2NvbXBhcmUpOwoJCWVsc2UgaWYgKGFs Z28gPT0gMSkKCQkJcXNvcnQoYXJyYXkgKyBCQVNFLCBCQVNFLCBzaXplb2Yodm9pZCAqKSwg aHBzX2NvbXBhcmUpOwoJCWVsc2UgaWYgKGFsZ28gPT0gMikKCQkJbWJpbl9zb3J0KGFycmF5 ICsgQkFTRSwgQkFTRSwgc2l6ZW9mKHZvaWQgKiksIGhwc19jb21wYXJlKTsKCQllbHNlCgkJ CW1lcmdlc29ydChhcnJheSArIEJBU0UsIEJBU0UsIHNpemVvZih2b2lkICopLCBocHNfY29t cGFyZSk7CgojaWZkZWYgSFBTX1ZFUklGWQoJCW1lbWNweShhcnJheSwgYXJyYXkgKyBCQVNF LCBzaXplb2YoYXJyYXlbMF0pICogQkFTRSk7CgkJZm9yICh4ID0gMDsgeCAhPSBCQVNFOyB4 KyspIHsKCQkJaWYgKHggKyAxIDwgQkFTRSAmJgoJCQkgICAgKHVpbnRwdHJfdClhcnJheVtC QVNFICsgeF0gPiAodWludHB0cl90KWFycmF5W0JBU0UgKyB4ICsgMV0pIHsKCQkJCXByaW50 ZigiV1JBUFxuIik7CgkJCX0KCQl9CgkJZm9yICh4ID0gMDsgeCAhPSBCQVNFOyB4KyspIHsK CQkJZm9yICh5ID0geCArIDE7IHkgIT0gQkFTRTsgeSsrKSB7CgkJCQlpZiAoYXJyYXlbeF0g PT0gYXJyYXlbeV0pIHsKCQkJCQl4Kys7CgkJCQkJaWYgKHggIT0geSkgewoJCQkJCQlwcmlu dGYoIlNPUlQgRVJST1IgJWQgJWRcbiIsIHgsIHkpOwoJCQkJCQlyZXR1cm4gKDApOwoJCQkJ CX0KCQkJCX0KCQkJfQoJCX0KI2VuZGlmCgl9CglyZXR1cm4gKDApOwp9Cg== --------------jv9htCQdi0xpKAaYlIFoqU0I--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?9801581e-ac26-c41b-e987-ee3bb954417d>