Re: git: c65e42dbde41 - main - libc: add test case for qsort_b(3)

From: Xin Li <delphij_at_FreeBSD.org>
Date: Wed, 07 Sep 2022 07:17:57 UTC

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,