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 <h...@selasky.org> wrote: > On 01/19/16 17:09, Ryan Stone wrote: > >> On Tue, Jan 19, 2016 at 10:33 AM, Hans Petter Selasky < >> hsela...@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 > _______________________________________________ svn-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
