From owner-svn-src-all@freebsd.org Sat Feb 13 07:45:39 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 842F3AA5755; Sat, 13 Feb 2016 07:45:39 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (mail.turbocat.net [IPv6:2a01:4f8:d16:4514::2]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4B92717B7; Sat, 13 Feb 2016 07:45:38 +0000 (UTC) (envelope-from hps@selasky.org) Received: from laptop015.home.selasky.org (unknown [62.141.129.119]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id D5BE41FE022; Sat, 13 Feb 2016 08:45:31 +0100 (CET) Subject: Re: svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys To: Warner Losh , Pedro Giffuni References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <56BAE4BC.9000105@selasky.org> <56BB5280.5060609@FreeBSD.org> Cc: Ryan Stone , "src-committers@freebsd.org" , "svn-src-all@freebsd.org" , "svn-src-head@freebsd.org" From: Hans Petter Selasky Message-ID: <56BEDFA9.9080305@selasky.org> Date: Sat, 13 Feb 2016 08:47:53 +0100 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 13 Feb 2016 07:45:39 -0000 On 02/11/16 17:47, Warner Losh wrote: > On Wed, Feb 10, 2016 at 8:08 AM, Pedro Giffuni 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? > No, I've abandoned the mergesort patch. --HPS