From owner-svn-src-all@freebsd.org Thu Feb 11 16:47:15 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 58010AA47A6 for ; Thu, 11 Feb 2016 16:47:15 +0000 (UTC) (envelope-from wlosh@bsdimp.com) Received: from mail-ig0-x233.google.com (mail-ig0-x233.google.com [IPv6:2607:f8b0:4001:c05::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 28BA415BB for ; Thu, 11 Feb 2016 16:47:15 +0000 (UTC) (envelope-from wlosh@bsdimp.com) Received: by mail-ig0-x233.google.com with SMTP id 5so40643144igt.0 for ; Thu, 11 Feb 2016 08:47:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bsdimp-com.20150623.gappssmtp.com; s=20150623; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=mot0Rcd4g+lAfmKiCJFEXccWbhuIsoUFlLB2gG5VZrI=; b=ffljmO7IaH6z06wENKBSzWRy1rWp/Eq3mDNxQ7ynt4nR4f/KmKjI/Y/YuCJ8zw0xo/ utFLOSrGhGdqur4h3Y/XxzxaWjZZi+kAkhW4Wf6PKLur9Mo3nhWlDZK+fhbl8mZbVewS 5jPceCTrBgXxcufAixvlTYgEc9EMxaEt8Xz4QtBat7xt0xPyT8VZO+w37G3fEnohtaIA 5X5nHEi42W12hrz/jE9t2AvOU6r3TvrX46ZCLikMm3OcVuCyg0QCLvWjX43jc0oz7txw ve0oV2rCyv4OSzUzfTcUdetSyK7jgBOgJkNcZKs+23iQbit9L6eU7Ux0wgh6n1QZ2oYO iMBg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=mot0Rcd4g+lAfmKiCJFEXccWbhuIsoUFlLB2gG5VZrI=; b=XDf0AkMyHPN4gqka0INV7FSK30wLGNLUhaMbAiYViCsZDPjj+E/m1mPpqIuCuSTyOH Xn2hy3hsCz2i7SSkXH9YdOkBralXzZBp1kvXfQ0C1Gp/+G6vpT+2hPptl2Qnuxf792hC GHyQfNFEgN+oXj/zK5j7e5YLfHDTFpGIRXytAC+5il4FYnn6yMzMkEwwTYDUL37qZofl g8IDpRKZuja+8wTxQPYsUP60Cj2scasEDUDnCjRX0fELHfHh7z53fWMhbaIuhAXfOyY7 1FmEL7ihXXeA87orIsCEmAKktrkyRv3691LFiAaWesqlcGRoQdDTAJHrdP+RCl6LaUU8 JqeQ== X-Gm-Message-State: AG10YOQraOCnWkqEM8KsA4ZDADBz8lLsrq8zOdE0/0pH361Z7PE8S7RDC0Ucy9qsPsip0nJqqGe6w8F7j0IhsQ== MIME-Version: 1.0 X-Received: by 10.50.109.137 with SMTP id hs9mr17640414igb.55.1455209234451; Thu, 11 Feb 2016 08:47:14 -0800 (PST) Sender: wlosh@bsdimp.com Received: by 10.79.67.193 with HTTP; Thu, 11 Feb 2016 08:47:14 -0800 (PST) X-Originating-IP: [69.53.245.22] In-Reply-To: <56BB5280.5060609@FreeBSD.org> References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <56BAE4BC.9000105@selasky.org> <56BB5280.5060609@FreeBSD.org> Date: Thu, 11 Feb 2016 09:47:14 -0700 X-Google-Sender-Auth: Bcjh4YPa9Qxx-6UZoq7HzvIPip0 Message-ID: Subject: Re: svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys From: Warner Losh To: Pedro Giffuni Cc: Hans Petter Selasky , Ryan Stone , "src-committers@freebsd.org" , "svn-src-all@freebsd.org" , "svn-src-head@freebsd.org" Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.20 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: Thu, 11 Feb 2016 16:47:15 -0000 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=C3=B3: > >> 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 mbu= f >>>> *), >>>> + &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 exhibi= t >> the so-called QuickSort worst case behaviour of O(N**2) sorting time. Th= is >> 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=3Drevision&revision=3D279663 > > 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? Warner