svn commit: r203035 - user/luigi/ipfw3-head/sys/netinet/ipfw

[Luigi Rizzo]

Author: luigi
Date: Tue Jan 26 16:47:34 2010
New Revision: 203035
URL: http://svn.freebsd.org/changeset/base/203035

Log:
  fix two bugs in the scheduler
  
  Submitted by:	Riccardo Panicucci

Modified:
  user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c

Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c	Tue Jan 26 16:18:45 2010	(r203034)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c	Tue Jan 26 16:47:34 2010	(r203035)
@@ -182,7 +182,20 @@ wf2qp_dequeue(struct new_sch_inst *_si)
 	idle_check(si, 1, 0);	/* drain something from the idle heap */
 
 	/* make sure at least one element is eligible, bumping V
-	 * and moving entries that have become eligible
+	 * and moving entries that have become eligible.
+	 * We need to repeat the first part twice, before and
+	 * after extracting the candidate, or enqueue() will
+	 * find the data structure in a wrong state.
+	 */
+  pkt = NULL;
+  for(;;) {
+	/*
+	 * Compute V = max(V, min(S_i)). Remember that all elements
+	 * in sch have by definition S_i <= V so if sch is not empty,
+	 * V is surely the max and we must not update it. Conversely,
+	 * if sch is empty we only need to look at neh.
+	 * We don't need to move the queues, as it will be done at the
+	 * next enqueue
 	 */
 	if (sch->elements == 0 && neh->elements > 0) {
 		si->V = MAX64(si->V, HEAP_TOP(neh)->key);
@@ -190,10 +203,12 @@ wf2qp_dequeue(struct new_sch_inst *_si)
 	while (neh->elements > 0 &&
 		    DN_KEY_LEQ(HEAP_TOP(neh)->key, si->V)) {
 		q = HEAP_TOP(neh)->object;
-		alg_fq = (struct wf2qp_queue *)q;
+		alg_fq = (struct wf2qp_queue *)(q + 1);
 		heap_extract(neh, NULL);
 		heap_insert(sch, alg_fq->F, q);
 	}
+	if (pkt) /* pkt found in previous iteration */
+		break;
 	/* ok we have at least one eligible pkt */
 	q = HEAP_TOP(sch)->object;
 	alg_fq = (struct wf2qp_queue *)(q + 1);
@@ -213,18 +228,7 @@ wf2qp_dequeue(struct new_sch_inst *_si)
 			heap_insert(neh, alg_fq->S, q);
 		}
 	}
-
-	/*
-	 * Now compute V = max(V, min(S_i)). Remember that all elements
-	 * in sch have by definition S_i <= V so if sch is not empty,
-	 * V is surely the max and we must not update it. Conversely,
-	 * if sch is empty we only need to look at neh.
-	 * We don't need to move the queues, as it will be done at the
-	 * next enqueue
-	 */
-	if (sch->elements == 0 && neh->elements > 0) {
-		si->V = MAX64(si->V, HEAP_TOP(neh)->key);
-	}
+    }
 	return pkt;
 }