From owner-svn-src-head@freebsd.org Thu Feb 11 16:47:15 2016 Return-Path: Delivered-To: svn-src-head@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 807EBAA47A7 for ; Thu, 11 Feb 2016 16:47:15 +0000 (UTC) (envelope-from wlosh@bsdimp.com) Received: from mail-ig0-x231.google.com (mail-ig0-x231.google.com [IPv6:2607:f8b0:4001:c05::231]) (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 4780315BD for ; Thu, 11 Feb 2016 16:47:15 +0000 (UTC) (envelope-from wlosh@bsdimp.com) Received: by mail-ig0-x231.google.com with SMTP id 5so40643127igt.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=K4D5DV6kepxwYYj3c2wVscOg1E2Q9lxUbvzRdzc719p1a1T+STvm2AvC2spGwBl9sa Z2Wmt3ntX1lmKNAQr/hnkRBN6+zMaGo7uDl1AHiKGmi43jJ1WKxMKPlQsdzQ2kWQgxzz g95WjYsqDJUnDyb2K9UU66gk4YrEaiIasm2JOPqXyngABDi1ud0PvD8VCv/Wxd5IMyrj sTLPIGlo1afE0jHk/8sMSYaAGZXuLnvPqEfSCbxhaqX4B/KQlGL+fllZ1thRQ5KYobpp PGXHhbrilHv+cSQ6okrXJvmO1WiKWHo8wW91I159iWfNTPovjCypXTDgu/vTjLMMQrmX mvYw== X-Gm-Message-State: AG10YOShEfl8JTZmZaaXCVJ21MqG13qg4DTLp3sfCws/+alYFW0/xw9CPf58BrxQVaKJTK3YLPkZq3xg6PASoA== 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-head@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: SVN commit messages for the src tree for head/-current 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