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<<QFQ_MAX_WSHIFT)
#define QFQ_MAX_WSUM (2*QFQ_MAX_WEIGHT)
-//#define IWSUM (q->i_wsum)
-#define IWSUM ((1<<FRAC_BITS)/QFQ_MAX_WSUM)
#define FRAC_BITS 30 /* fixed point arithmetic */
#define ONE_FP (1UL << FRAC_BITS)
@@ -227,6 +225,7 @@ struct qfq_group {
struct qfq_sched {
uint64_t V; /* Precise virtual time. */
uint32_t wsum; /* weight sum */
+ uint32_t iwsum; /* inverse weight sum */
NO(uint32_t i_wsum; /* ONE_FP/w_sum */
uint32_t _queued; /* debugging */
uint32_t loops; /* debugging */)
@@ -312,8 +311,8 @@ qfq_new_queue(struct dn_queue *_q)
i = qfq_calc_index(cl->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;
}
}
_______________________________________________
svn-src-head@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
