Date: Thu, 11 Feb 2016 09:47:14 -0700 From: Warner Losh <imp@bsdimp.com> To: Pedro Giffuni <pfg@freebsd.org> Cc: Hans Petter Selasky <hps@selasky.org>, Ryan Stone <rysto32@gmail.com>, "src-committers@freebsd.org" <src-committers@freebsd.org>, "svn-src-all@freebsd.org" <svn-src-all@freebsd.org>, "svn-src-head@freebsd.org" <svn-src-head@freebsd.org> Subject: Re: svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys Message-ID: <CANCZdfpmYMGKJkX4uQR6Uet18cffJ4-uXxRSxfbe3Q6p2Pb48Q@mail.gmail.com> In-Reply-To: <56BB5280.5060609@FreeBSD.org> References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <CAFMmRNz3uXim3H3-sGuBUBs45Jy8p260ywothgp4iFkUcnvnEw@mail.gmail.com> <56BAE4BC.9000105@selasky.org> <56BB5280.5060609@FreeBSD.org>
index | next in thread | previous in thread | raw e-mail
On Wed, Feb 10, 2016 at 8:08 AM, Pedro Giffuni <pfg@freebsd.org> wrote: > 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@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). If it is faster, is there any good reason to maintain both qsort and mergesort in the kernel then? Warnerhome | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CANCZdfpmYMGKJkX4uQR6Uet18cffJ4-uXxRSxfbe3Q6p2Pb48Q>