From owner-svn-src-all@freebsd.org Fri Jul 10 19:24:38 2015 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 0E30A997706; Fri, 10 Jul 2015 19:24:38 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2001:1900:2254:2068::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 CC63F1DFE; Fri, 10 Jul 2015 19:24:37 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.70]) by repo.freebsd.org (8.14.9/8.14.9) with ESMTP id t6AJOb5R051771; Fri, 10 Jul 2015 19:24:37 GMT (envelope-from luigi@FreeBSD.org) Received: (from luigi@localhost) by repo.freebsd.org (8.14.9/8.14.9/Submit) id t6AJObbg051770; Fri, 10 Jul 2015 19:24:37 GMT (envelope-from luigi@FreeBSD.org) Message-Id: <201507101924.t6AJObbg051770@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: luigi set sender to luigi@FreeBSD.org using -f From: Luigi Rizzo Date: Fri, 10 Jul 2015 19:24:37 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r285362 - 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: Fri, 10 Jul 2015 19:24:38 -0000 Author: luigi Date: Fri Jul 10 19:24:36 2015 New Revision: 285362 URL: https://svnweb.freebsd.org/changeset/base/285362 Log: assorted algorithmic fixes from Paolo Valente (one of my qfq coauthors): - use 1ULL to avoid shift truncations - recompute the sum of weight dynamically to provide better fairness - fix an erroneous constant in the computation of the slot - preserve timestamp correctness when the old timestamp is stale. 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 Fri Jul 10 19:18:49 2015 (r285361) +++ head/sys/netpfil/ipfw/dn_sched_qfq.c Fri Jul 10 19:24:36 2015 (r285362) @@ -172,8 +172,6 @@ for the scheduler: bitmaps and bucket li #define QFQ_MAX_WEIGHT (1<i_wsum) -#define IWSUM ((1<inv_w, cl->lmax); cl->grp = &q->groups[i]; q->wsum += w; + q->iwsum = ONE_FP / q->wsum; /* XXX note theory */ // XXX cl->S = q->V; ? - // XXX compute q->i_wsum return 0; } @@ -325,6 +324,8 @@ qfq_free_queue(struct dn_queue *_q) struct qfq_class *cl = (struct qfq_class *)_q; if (cl->inv_w) { q->wsum -= ONE_FP/cl->inv_w; + if (q->wsum != 0) + q->iwsum = ONE_FP / q->wsum; cl->inv_w = 0; /* reset weight to avoid run twice */ } return 0; @@ -408,7 +409,8 @@ qfq_make_eligible(struct qfq_sched *q, u old_vslot = old_V >> QFQ_MIN_SLOT_SHIFT; if (vslot != old_vslot) { - mask = (2UL << (__fls(vslot ^ old_vslot))) - 1; + /* should be 1ULL not 2ULL */ + mask = (1ULL << (__fls(vslot ^ old_vslot))) - 1; qfq_move_groups(q, mask, IR, ER); qfq_move_groups(q, mask, IB, EB); } @@ -557,7 +559,7 @@ qfq_dequeue(struct dn_sch_inst *si) } NO(q->queued--;) old_V = q->V; - q->V += (uint64_t)m->m_pkthdr.len * IWSUM; + q->V += (uint64_t)m->m_pkthdr.len * q->iwsum; ND("m is %p F 0x%llx V now 0x%llx", m, cl->F, q->V); if (qfq_update_class(q, grp, cl)) { @@ -612,7 +614,7 @@ qfq_update_start(struct qfq_sched *q, st int slot_shift = cl->grp->slot_shift; roundedF = qfq_round_down(cl->F, slot_shift); - limit = qfq_round_down(q->V, slot_shift) + (1UL << slot_shift); + limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift); if (!qfq_gt(cl->F, q->V) || qfq_gt(roundedF, limit)) { /* timestamp was stale */ @@ -620,7 +622,11 @@ qfq_update_start(struct qfq_sched *q, st if (mask) { struct qfq_group *next = qfq_ffs(q, mask); if (qfq_gt(roundedF, next->F)) { - cl->S = next->F; + /* from pv 71261956973ba9e0637848a5adb4a5819b4bae83 */ + if (qfq_gt(limit, next->F)) + cl->S = next->F; + else /* preserve timestamp correctness */ + cl->S = limit; return; } }