From owner-svn-src-all@freebsd.org Wed Feb 10 15:08:45 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 DA604AA4669 for ; Wed, 10 Feb 2016 15:08:44 +0000 (UTC) (envelope-from pfg@FreeBSD.org) Received: from nm20.bullet.mail.bf1.yahoo.com (nm20.bullet.mail.bf1.yahoo.com [98.139.212.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 8FA9917CB for ; Wed, 10 Feb 2016 15:08:44 +0000 (UTC) (envelope-from pfg@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1455116922; bh=HG6NtfK5KSdAbMJgo985p4UzXox9V4TtNhi4C4xb6JE=; h=Subject:To:References:Cc:From:Date:In-Reply-To:From:Subject; b=JJ7/Gon+4uOhf/R+mwJKks8l5xSpnkHShEXfnk2bpwC605Ly9ryQjz+wkQg5CXGpkuecAygRAH8uIJdP9Y8mj6tJzjbSKAhP2MHEbZ5htl710xJlDjk1hkHK/gpb8Q/+rW/4yqmLrqPsCxYpnAeE86GzVHm2jUTSld6f2J4T3BHuC9nHwyTHuQ79ikbMx519PnlihmUVO+uo7350975Ol57DuMwN+vrzfGKT06ZSK4uovTiWyk68BmsbAjsmbwDDbGAPQ3bZ8WS6fbsfjcdHyKXFTtdZyPGl4C+gX9L7bD3gS860jB/ecJB3jEHcU6/dJD2UC4NprF/UX9x2FgIsgw== Received: from [98.139.170.178] by nm20.bullet.mail.bf1.yahoo.com with NNFMP; 10 Feb 2016 15:08:42 -0000 Received: from [68.142.230.71] by tm21.bullet.mail.bf1.yahoo.com with NNFMP; 10 Feb 2016 15:08:42 -0000 Received: from [127.0.0.1] by smtp228.mail.bf1.yahoo.com with NNFMP; 10 Feb 2016 15:08:42 -0000 X-Yahoo-Newman-Id: 780862.37068.bm@smtp228.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: IcuoONEVM1mNEsvhaOG4hgWczuh0o1AdgvQNBDpGKg_M988 dLFS8Hd886UJgfWUnr2eSJIK9il.leN84zg254BEk3_WhMFH._seGTXqevJC JdApNt.0lyySaV1Q6H8L4P_7deGxwVNtrAFlWrzK5Db.pifabOshkPVHsmua EfqR_rUbLx8nivL9yZ1WhJDyqTGGCROdcitFYpipmpWt7y7twEBMzTiiDSeC G5H3NMTWUcg8uvhApstozTRDU5UooksIF838lrKlxOfIqZdaVTsiaJ2j8jnp m4kAl3cyIc2.86.sbD8rkVkRkkzXTuhTzOOZHCLzaEIv7htEkNfbXhWQFVcZ cwjs5H2CZX21Riz_IImanbwjztDQSyC3fMINXC0x.9O.6qQVk3UvDuA0Qitj KiLhdOyQE8qr9JlFgKmuXi0jFApYzHlbP35N0wDU2xfRz5jwxAaQ3EzWQyfk x9qN_brgPIp8hLIRoaVC7j.b4lQ8lgbFAIhjY2fqikd4YNZSODxM4ubeWMev 3J3Fmk3EgM0d9JWA_74.FxRRqmxquS_z. X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Subject: Re: svn commit: r294327 - in head/sys: dev/cxgb dev/cxgbe dev/e1000 dev/hyperv/netvsc dev/ixgbe dev/mxge netinet sys To: Hans Petter Selasky , Ryan Stone References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <56BAE4BC.9000105@selasky.org> Cc: "src-committers@freebsd.org" , "svn-src-all@freebsd.org" , "svn-src-head@freebsd.org" From: Pedro Giffuni Message-ID: <56BB5280.5060609@FreeBSD.org> Date: Wed, 10 Feb 2016 10:08:48 -0500 User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 MIME-Version: 1.0 In-Reply-To: <56BAE4BC.9000105@selasky.org> 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: Wed, 10 Feb 2016 15:08:45 -0000 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 >> >> 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). Pedro.