From nobody Wed Sep 7 07:55:39 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4MMvh14grsz4bs2Z; Wed, 7 Sep 2022 07:55:45 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (turbocat.net [88.99.82.50]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4MMvh05fRrz42kF; Wed, 7 Sep 2022 07:55:44 +0000 (UTC) (envelope-from hps@selasky.org) Received: from [10.36.2.165] (unknown [178.232.223.95]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id 7808A26007D; Wed, 7 Sep 2022 09:55:43 +0200 (CEST) Content-Type: multipart/mixed; boundary="------------jv9htCQdi0xpKAaYlIFoqU0I" Message-ID: <9801581e-ac26-c41b-e987-ee3bb954417d@selasky.org> Date: Wed, 7 Sep 2022 09:55:39 +0200 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:91.0) Gecko/20100101 Thunderbird/91.13.0 Subject: Re: git: c65e42dbde41 - main - libc: add test case for qsort_b(3) Content-Language: en-US To: Xin Li , src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org References: <202209070612.2876C6ko054410@gitrepo.freebsd.org> From: Hans Petter Selasky In-Reply-To: X-Rspamd-Queue-Id: 4MMvh05fRrz42kF X-Spamd-Bar: / Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=pass (mx1.freebsd.org: domain of hps@selasky.org designates 88.99.82.50 as permitted sender) smtp.mailfrom=hps@selasky.org X-Spamd-Result: default: False [-0.60 / 15.00]; MIME_BAD_ATTACHMENT(1.60)[c:text/x-csrc]; MIME_BASE64_TEXT_BOGUS(1.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_SHORT(-1.00)[-0.999]; NEURAL_HAM_MEDIUM(-1.00)[-0.999]; R_SPF_ALLOW(-0.20)[+a:mail.turbocat.net:c]; MIME_BASE64_TEXT(0.10)[]; MIME_GOOD(-0.10)[multipart/mixed,text/plain,text/x-csrc]; MLMMJ_DEST(0.00)[dev-commits-src-all@FreeBSD.org,dev-commits-src-main@FreeBSD.org]; R_DKIM_NA(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; ASN(0.00)[asn:24940, ipnet:88.99.0.0/16, country:DE]; MIME_TRACE(0.00)[0:+,1:+,2:+]; TO_DN_SOME(0.00)[]; ARC_NA(0.00)[]; HAS_ATTACHMENT(0.00)[]; MID_RHS_MATCH_FROM(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; RCVD_COUNT_TWO(0.00)[2]; FROM_HAS_DN(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; RCPT_COUNT_THREE(0.00)[4]; DMARC_NA(0.00)[selasky.org]; RCVD_TLS_ALL(0.00)[] X-ThisMailContainsUnwantedMimeParts: N 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--