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

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