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

[Pedro Giffuni]

Hello;

El 10/02/2016 a las 02:20, Hans Petter Selasky escribió:
> 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,
>
> Our FreeBSD qsort() routine has been specifically modified to not 
> exhibit the so-called QuickSort worst case behaviour of O(N**2) 
> sorting time. This is not documented in our source code, but here:
>
> http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engineering.pdf
>
> So I think DOS w.r.t O(N**2) is not a valid consern.
>
> Thank you for your input Ryan.
>
> BTW:
>
> Drew Gallatin has tested our qsort() v.s. my mergesort() and found that:
>
> "It looks like mergesort is nearly 2x as expensive. (4.7% vs 2.5%)"
>

FWIW, our libc qsort() has an additional enhancement:

http://svnweb.freebsd.org/base?view=revision&revision=279663

In my measurements qsort(3) was now always faster than mergesort(3).

Pedro.