From owner-svn-src-all@freebsd.org Tue Jan 26 04:48:26 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 5D883A46BA2; Tue, 26 Jan 2016 04:48:26 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (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 2D28C1289; Tue, 26 Jan 2016 04:48:26 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id u0Q4mP9S074251; Tue, 26 Jan 2016 04:48:25 GMT (envelope-from luigi@FreeBSD.org) Received: (from luigi@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id u0Q4mPW2074250; Tue, 26 Jan 2016 04:48:25 GMT (envelope-from luigi@FreeBSD.org) Message-Id: <201601260448.u0Q4mPW2074250@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: luigi set sender to luigi@FreeBSD.org using -f From: Luigi Rizzo Date: Tue, 26 Jan 2016 04:48:25 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r294761 - head/sys/netpfil/ipfw X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 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: Tue, 26 Jan 2016 04:48:26 -0000 Author: luigi Date: Tue Jan 26 04:48:24 2016 New Revision: 294761 URL: https://svnweb.freebsd.org/changeset/base/294761 Log: Revert one chunk from commit 285362, which introduced an off-by-one error in computing a shift index. The error was due to the use of mixed fls() / __fls() functions in another implementation of qfq. To avoid that the problem occurs again, properly document which incarnation of the function we need. Note that the bug only affects QFQ in FreeBSD head from last july, as the patch was not merged to other versions. Modified: head/sys/netpfil/ipfw/dn_sched_qfq.c Modified: head/sys/netpfil/ipfw/dn_sched_qfq.c ============================================================================== --- head/sys/netpfil/ipfw/dn_sched_qfq.c Tue Jan 26 04:41:18 2016 (r294760) +++ head/sys/netpfil/ipfw/dn_sched_qfq.c Tue Jan 26 04:48:24 2016 (r294761) @@ -60,6 +60,10 @@ typedef unsigned long bitmap; /* * bitmaps ops are critical. Some linux versions have __fls * and the bitmap ops. Some machines have ffs + * NOTE: fls() returns 1 for the least significant bit, + * __fls() returns 0 for the same case. + * We use the base-0 version __fls() to match the description in + * the ToN QFQ paper */ #if defined(_WIN32) || (defined(__MIPSEL__) && defined(LINUX_24)) int fls(unsigned int n) @@ -409,8 +413,8 @@ qfq_make_eligible(struct qfq_sched *q, u old_vslot = old_V >> QFQ_MIN_SLOT_SHIFT; if (vslot != old_vslot) { - /* should be 1ULL not 2ULL */ - mask = (1ULL << (__fls(vslot ^ old_vslot))) - 1; + /* must be 2ULL, see ToN QFQ article fig.5, we use base-0 fls */ + mask = (2ULL << (__fls(vslot ^ old_vslot))) - 1; qfq_move_groups(q, mask, IR, ER); qfq_move_groups(q, mask, IB, EB); }