From owner-svn-src-head@freebsd.org Tue Jan 19 17:01:41 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 45B83A89C1A; Tue, 19 Jan 2016 17:01:41 +0000 (UTC) (envelope-from rysto32@gmail.com) Received: from mail-io0-x22d.google.com (mail-io0-x22d.google.com [IPv6:2607:f8b0:4001:c06::22d]) (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 0B11918BD; Tue, 19 Jan 2016 17:01:41 +0000 (UTC) (envelope-from rysto32@gmail.com) Received: by mail-io0-x22d.google.com with SMTP id g73so396048965ioe.3; Tue, 19 Jan 2016 09:01:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=02t3+7PiYzRbGLsJv1e3NT0G56pvw8/SHA+kRsFe+lY=; b=uCrHAEW/WOnWYAwaHTYKT4EaRzI8hIr/oi/2AJdJJ+9NdjPuhSgfAeW04ga/i+wOoz 8sRixhAWZXOq4096KPDwcZ/+IvCaTgM0kg/hpzvebDQz7c8vh+Emwq32El+kt1a8RFUS PTrgmEYipnuousUha/pSInjiyjilNKGWKev6Ut1J1wXOYt3PGAemO+X8nqHkRu0fqkoO rEHzLTGCxtTMzIB6Zu7RcyNnu4L2bfLVdLaf8uSDn//qu0j9pyoIFfZ94hK32pFJpWrD 9346fytX2zfFKbwd1kwjebClj1ylLuh9N3OqdrPP44Abm5Pc6cA7kwd54jdislXu/wRk L7PA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=02t3+7PiYzRbGLsJv1e3NT0G56pvw8/SHA+kRsFe+lY=; b=OanVttUvL3hqp2CEccKywvXcXPrJa42IBmkXvxdvIpEEzSNAQ77vhuG9Tgrevnr5is WLRTuhF8IYYPunGU0LkwsyM2f3MLTVcISnZKRAs6kk3VTELhS+kvRmIx35vh4Luq8r92 3PN5HkLBdXrTRF03OSBaPaUd+54vDqWKKToYlf+VH57qAefMR039mdYi+0mSZZC5N3K4 NbPSykyC0jqrY1RHYuPcMBXmS8CFXpTvF7jmkNxUbTsAS/ptSmv0LisyLbHRT7MfOcEU yJS4f1x36l/GGw5KdX4k2YgzlKOMcIdTpkPmd+Q+72coCRGstoNV2t3/6ywJPPhq6+o1 09rg== X-Gm-Message-State: ALoCoQkBFMth3uwswgJ+R/WcCB86IEBg5JH3OFwJMf9dZgp5UiDg+o2xNxNgoH8LJX5+tY6PAX6qaMXvhNlLROGmA5qqhQVtmQ== MIME-Version: 1.0 X-Received: by 10.107.153.140 with SMTP id b134mr28753113ioe.113.1453222900426; Tue, 19 Jan 2016 09:01:40 -0800 (PST) Received: by 10.107.178.193 with HTTP; Tue, 19 Jan 2016 09:01:40 -0800 (PST) In-Reply-To: <569E6A38.8080108@selasky.org> References: <201601191533.u0JFXSxf037804@repo.freebsd.org> <569E6A38.8080108@selasky.org> Date: Tue, 19 Jan 2016 12:01:40 -0500 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: Ryan Stone To: Hans Petter Selasky Cc: "src-committers@freebsd.org" , "svn-src-all@freebsd.org" , "svn-src-head@freebsd.org" Content-Type: text/plain; charset=UTF-8 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: Tue, 19 Jan 2016 17:01:41 -0000 libkern's qsort() is a quicksort implementation. AFAICT it has the worst case behaviour that I describe. On Tue, Jan 19, 2016 at 11:54 AM, Hans Petter Selasky wrote: > 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 Ryan, > > Is this the case for the qsort() we have in the FreeBSD kernel? > > There are other sorting algorithms which can be used instead of qsort() > which consume O(n * log(n)) time and O(1) stack, but requires a power of > two set of elements to sort. > > --HPS >