Date: Tue, 19 Jan 2016 12:01:40 -0500 From: Ryan Stone <rysto32@gmail.com> To: Hans Petter Selasky <hps@selasky.org> Cc: "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: <CAFMmRNx3zC=mz=TC2Aq5==a5vh0Fqzv1domrCL2uUHnjybZSkQ@mail.gmail.com> In-Reply-To: <569E6A38.8080108@selasky.org> References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <CAFMmRNz3uXim3H3-sGuBUBs45Jy8p260ywothgp4iFkUcnvnEw@mail.gmail.com> <569E6A38.8080108@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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@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@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 >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAFMmRNx3zC=mz=TC2Aq5==a5vh0Fqzv1domrCL2uUHnjybZSkQ>