svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys

[Ryan Stone]

libkern's qsort() is a quicksort implementation. AFAICT it has the worst
case behaviour that I describe.

On Tue, Jan 19, 2016 at 11:54 AM, Hans Petter Selasky <hps at selasky.org>
wrote:

> On 01/19/16 17:09, Ryan Stone wrote:
>
>> On Tue, Jan 19, 2016 at 10:33 AM, Hans Petter Selasky <
>> hselasky at freebsd.org>
>> wrote:
>>
>>
>>> +       qsort(lc->lro_mbuf_data, lc->lro_mbuf_count, sizeof(struct mbuf
>>> *),
>>> +           &tcp_lro_mbuf_compare_header);
>>>
>>>
>> In the worst case, qsort() can take O(n**2) time and consume O(n) stack
>> space.  Is there a DOS concern here?
>>
>>
> Hi Ryan,
>
> Is this the case for the qsort() we have in the FreeBSD kernel?
>
> There are other sorting algorithms which can be used instead of qsort()
> which consume O(n * log(n)) time and O(1) stack, but requires a power of
> two set of elements to sort.
>
> --HPS
>