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).
Cheers,
OpenPGP_0x40797F7C95F4834F.asc
Description: OpenPGP public key
OpenPGP_signature
Description: OpenPGP digital signature
