From owner-svn-src-head@freebsd.org  Wed Feb 10 07:18:11 2016
Return-Path: <owner-svn-src-head@freebsd.org>
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 26B03AA3F23;
 Wed, 10 Feb 2016 07:18:11 +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 E741E189D;
 Wed, 10 Feb 2016 07:18:10 +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 1F9D51FE023;
 Wed, 10 Feb 2016 08:18:07 +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: Ryan Stone <rysto32@gmail.com>
References: <201601191533.u0JFXSxf037804@repo.freebsd.org>
 <CAFMmRNz3uXim3H3-sGuBUBs45Jy8p260ywothgp4iFkUcnvnEw@mail.gmail.com>
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>
From: Hans Petter Selasky <hps@selasky.org>
Message-ID: <56BAE4BC.9000105@selasky.org>
Date: Wed, 10 Feb 2016 08:20:28 +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: <CAFMmRNz3uXim3H3-sGuBUBs45Jy8p260ywothgp4iFkUcnvnEw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
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
 <svn-src-head.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/svn-src-head>,
 <mailto:svn-src-head-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/svn-src-head/>
List-Post: <mailto:svn-src-head@freebsd.org>
List-Help: <mailto:svn-src-head-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/svn-src-head>,
 <mailto:svn-src-head-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 10 Feb 2016 07:18:11 -0000

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%)"

See:

https://reviews.freebsd.org/D5200

And:

https://reviews.freebsd.org/D4994

--HPS