Use optimised complexity safe sort routine instead of the kernel's qsort

[• hselasky]

Summary

The kernels qsort() routine can in worst case spend O(N*N) amount of comparisons before the result is sorted.

Because the sorting key is very small, 64-bits, we can use a bit-slice sorter algorithmn instead, which is faster than mergesort() and comparable() to qsort().

[• hselasky]

Implement suggestion from Drew:

• Keep all data in same array to optimize cache line usage

• Further optimize sorting function.

[kbowling]

sys/netinet/tcp_lro.c

384

Simple typo alorithm >> algorithm

[• hselasky]

Fix spelling. Found by Kevin.

[• hselasky]

Fixed.

[sepherosa_gmail.com]

Looks good to me.

[• hselasky]

Use ffsll() when it is provided by the CPU.

Suggested by Drew.

[• hselasky]

Use flsll() instead of ffsll(). Else sorting result will be bit-reversed.

--HPS

[• hselasky]

Optimize sorting algorithm.

[gallatin]

Great work -- faster AND safer

[gallatin]

BTW, I tested a version of this patch in our Netflix code base. When serving roughly 80Gb/s with 80K TCP connections, the old method (qsort + tcp_lro_mbuf_compare_header) used 1.4% CPU, while the new (tcp_lro_sort) used 1.1% for LRO related sorting as measured by Intel Vtune. This test was done with a sysctl toggle to switch between qsort and the new sort.

That is why I mentioned that in addition to being safer (by limiting recursion), this is also faster.

[rrs]

If Drew says it works I am happy with it as well :-)

[• hselasky]

Committed to head, r300731.