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.

1 files changed, 13 insertions, 7 deletions

diff --git a/sys/netpfil/ipfw/dn_sched_qfq.c b/sys/netpfil/ipfw/dn_sched_qfq.c
index 5bbff8a..ea27b3e 100644
--- a/sys/netpfil/ipfw/dn_sched_qfq.c
+++ b/sys/netpfil/ipfw/dn_sched_qfq.c
@@ -172,8 +172,6 @@ for the scheduler: bitmaps and bucket lists.
 
 #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, uint64_t old_V)
 	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, struct qfq_class *cl)
 	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, struct qfq_class *cl)
 		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;
 			}
 		}