svn commit: r202554 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Mon Jan 18 09:13:47 UTC 2010
Author: luigi
Date: Mon Jan 18 09:13:47 2010
New Revision: 202554
URL: http://svn.freebsd.org/changeset/base/202554
Log:
code cleanup (not compiling)
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 Mon Jan 18 09:04:53 2010 (r202553)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Mon Jan 18 09:13:47 2010 (r202554)
@@ -58,32 +58,51 @@
* ne_heap (key is Start time) stores not-eligible queues
* idle_heap (key=start/finish time) stores idle flows. It must
* support extract-from-middle.
- * A flow is normally only in 1 of the three heaps.
+ * A flow is only in 1 of the three heaps.
* XXX todo: use a more efficient data structure, e.g. a tree sorted
* by F with min_subtree(S) in each node
*/
struct wf2qp_si {
- struct dn_heap *sch_heap; /* top extract - key Finish time */
- struct dn_heap *ne_heap; /* top extract - key Start time */
- struct dn_heap *idle_heap; /* random extract - key Start=Finish time */
+ struct dn_heap *sch_heap; /* top extract - key Finish time */
+ struct dn_heap *ne_heap; /* top extract - key Start time */
+ struct dn_heap *idle_heap; /* random extract - key Start=Finish time */
dn_key V ; /* virtual time */
- int sum;
+ uint32_t sum; /* sum of weights */
};
struct wf2qp_queue {
- struct new_queue g;
-
dn_key S,F; /* start time, finish time */
-
int heap_pos; /* position (index) of struct in heap */
-// struct wf2qp_queue *next; /* next queue in the bucket */
};
/*
* This file implements a WF2Q+ scheduler as it has been in dummynet
* since 2000.
* The scheduler supports per-flow queues and has O(log N) complexity.
+ *
+ * WF2Q+ needs to drain entries from the idle heap so that we
+ * can keep the sum of weights up to date. We can do it whenever
+ * we get a chance, or periodically, or following some other
+ * strategy. The function idle_check() drains at most N elements
+ * from the idle heap.
*/
+static void
+idle_check(struct wf2qp_si *siwfq, int n)
+{
+ struct dn_heap *h = si->idle_heap;
+ while (n-- > 0 && h->elements > 0 &&
+ DN_KEY_LT(HEAP_TOP(h)->key, si->V)) {
+ struct dn_queue *q = HEAP_TOP(h)->object;
+ struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)(q+1);
+
+ heap_extract(h, NULL);
+ /* XXX to let the flowset delete the queue we should
+ * mark it as 'unused' by the scheduler.
+ */
+ alg_fq->S = alg_fq->F + 1; /* Mark timestamp as invalid. */
+ si->sum -= q->fs->fs.weight; /* adjust sum of weights */
+ }
+}
static int
wf2qp_enqueue(struct new_sch_inst *_si, struct new_queue *q, struct mbuf *m)
@@ -92,32 +111,30 @@ wf2qp_enqueue(struct new_sch_inst *_si,
struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
struct wf2qp_queue *alg_fq;
uint64_t len = m->m_pkthdr.len;
+ int q_was_idle;
- int q_was_idle = 0;
-
- if (q->mq.head == NULL)
- q_was_idle = 1;
+ q_was_idle = (q->mq.head == NULL)
if (dn_enqueue(q, m, 0)) /* packet was dropped */
return 1;
- if(!q_was_idle)
+ if (!q_was_idle)
return 0;
/* If reach this point, queue q was idle */
- alg_fq = (struct wf2qp_queue *)q;
+ alg_fq = (struct wf2qp_queue *)(q+1);
if (DN_KEY_LT(alg_fq->F, alg_fq->S)) {
/* F<S means timestamps are invalid ->brand new queue. */
- alg_fq->S = si->V;
- si->sum += fs->fs.weight; /* Add weight of new queue. */
+ alg_fq->S = si->V; /* init start time */
+ si->sum += fs->fs.weight; /* add weight of new queue. */
} else { /* if it was idle then it was in the idle heap */
heap_extract(si->idle_heap, q);
- alg_fq->S = MAX64(alg_fq->F, si->V);
+ alg_fq->S = MAX64(alg_fq->F, si->V); /* compute new S */
}
- // XXX use div64
- alg_fq->F = alg_fq->S + (len << MY_M) / (uint64_t)fs->fs.weight;
+ alg_fq->F = alg_fq->S + div64((len << MY_M), fs->fs.weight);
+ /* if nothing is backlogged, make sure this flow is eligible */
if (si->ne_heap->elements == 0 && si->sch_heap->elements == 0)
si->V = MAX64(alg_fq->S, si->V);
@@ -137,233 +154,135 @@ wf2qp_enqueue(struct new_sch_inst *_si,
if (si->sch_heap->elements == 0)
printf("dummynet: ++ ouch! not eligible but empty scheduler!\n");
heap_insert(si->ne_heap, alg_fq->S, q);
- }
- else {
+ } else {
heap_insert(si->sch_heap, alg_fq->F, q);
- /* Pipe *must* be idle. */
-#if 0
- if ((si->sch_heap.elements != 1) && (s->numbytes >= 0))
- printf("dummynet: OUCH! pipe should have been idle!\n");
- DPRINTF(("dummynet: waking up pipe %d at %d\n",
- s->sched_nr, (int)(alg_fq->F >> MY_M)));
-#endif
}
return 0;
}
+/* XXX invariant: sch > 0 || neh == 0 */
static struct mbuf *
wf2qp_dequeue(struct new_sch_inst *_si)
{
/* Access scheduler instance private data */
struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
-
struct mbuf *pkt = NULL;
struct new_queue *qq, *q1, *q = NULL;
-
struct dn_heap *sch = si->sch_heap;
struct dn_heap *neh = si->ne_heap;
-
struct wf2qp_queue *alg_fq = NULL;
-
uint64_t len;
- /* XXX:
- * This block in the previous version were done in the dummynet_task()
- * function. Check if this is the appropriate function to do it.
- */
- if (si->idle_heap->elements > 0 &&
- DN_KEY_LT(HEAP_TOP(si->idle_heap)->key, si->V)) {
- qq = HEAP_TOP(si->idle_heap)->object;
- alg_fq = (struct wf2qp_queue *) qq;
-
- heap_extract(si->idle_heap, NULL);
- /* Mark timestamp as invalid. */
- /* XXX why don't delete the queue now? */
- alg_fq->S = alg_fq->F + 1;
- si->sum -= qq->fs->fs.weight;
- }
-
-
-#if 0
- if (p->if_name[0] == 0) { /* tx clock is simulated */
- s->numbytes += (curr_time - s->sched_time) * p->bandwidth;
- }
- else {
- /* tx clock is for real, the ifq must be empty or this is a NOP. */
- if (p->ifp && p->ifp->if_snd.ifq_head != NULL)
- return NULL;
- else {
- DPRINTF(("dummynet: pipe %d ready from %s --\n",
- p->pipe_nr, p->if_name));
- }
+ if (sch->elements == 0 && neh->elements == 0) {
+ /* we have nothing to do. We could kill the idle heap
+ * altogether and reset V
+ */
+ idle_check(si, 0x7fffffff);
+ si->V = 0;
+ si->sum = 0; /* should be set already */
+ return NULL; /* quick return if nothing to
}
-#endif
- /*
- * While we have backlogged traffic AND credit, we need to do
- * something on the queue.
- * XXX cannot be a 'while --
- */
- while ( sch->elements > 0 || neh->elements > 0) {
- if (sch->elements > 0) {
+ idle_check(si, 1); /* drain something from the idle heap */
+ if (sch->elements > 0) {
/* Have some eligible pkts to send out. */
q = HEAP_TOP(sch)->object;
- alg_fq = (struct wf2qp_queue *)q;
-
+ alg_fq = (struct wf2qp_queue *)(q + 1);
pkt = q->mq.head;
-
heap_extract(sch, NULL); /* Remove queue from heap. */
-
- si->V += (pkt->m_pkthdr.len << MY_M) / si->sum; /* Update V. */
+ si->V += div64(pkt->m_pkthdr.len << MY_M, si->sum);
alg_fq->S = alg_fq->F; /* Update start time. */
-
- if (q->ni.length == 1) /* Flow not backlogged any more. */
- heap_insert(si->idle_heap, alg_fq->F, q);
- else {
- /* Still backlogged. */
- /*
- * Update F and position in backlogged queue,
- * then put flow in ne_heap
- * (we will fix this later).
- */
- /* len = (q->head)->m_pkthdr.len; */
- len = ((q->mq.head)->m_nextpkt)->m_pkthdr.len;
- alg_fq->F += (len << MY_M) / (uint64_t)q->fs->fs.weight;
+ if (q->ni.length == 1) { /* not backlogged any more. */
+ heap_insert(si->idle_heap, alg_fq->F, q);
+ } else { /* Still backlogged. */
+ /* Update F, store in neh or sch */
+ len = pkt->m_nextpkt->m_pkthdr.len;
+ alg_fq->F += div64(len << MY_M, q->fs->fs.weight);
if (DN_KEY_LEQ(alg_fq->S, si->V)) {
- heap_insert(neh, alg_fq->S, q);
- }
- else {
heap_insert(sch, alg_fq->F, q);
+ } else {
+ 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.
- */
- if (sch->elements == 0 && neh->elements > 0)
- si->V = MAX64(si->V, HEAP_TOP(neh)->key);
- /* Move from neh to sch any packets that have become eligible */
- while (neh->elements > 0 && DN_KEY_LEQ(HEAP_TOP(neh)->key, si->V)) {
- qq = HEAP_TOP(neh)->object;
- alg_fq = (struct wf2qp_queue *)qq;
- heap_extract(neh, NULL);
- heap_insert(sch, alg_fq->F, qq);
- }
-#if 0
- if (p->if_name[0] != '\0') { /* Tx clock is from a real thing */
- s->numbytes = -1; /* Mark not ready for I/O. */ /* WARNING*/
- debMes(" %s f\n", __FUNCTION__);
- break;
- }
-#endif
- if (pkt != NULL)
- return dn_dequeue(q);
-
- } /* end of while */
-
- if (sch->elements == 0 && neh->elements == 0 &&
- si->idle_heap->elements > 0) {
- /*
- * No traffic and no events scheduled.
- * We can get rid of idle-heap.
- */
- int i;
- int elem = si->idle_heap->elements;
-
- for (i = 0; i < elem; i++) {
- /* XXX NOTE: before the heap changed, this block extracted
- * all elements
- */
- q1 = HEAP_TOP(si->idle_heap)->object;
- heap_extract(si->idle_heap, NULL);
- alg_fq = (struct wf2qp_queue *)q1;
-
- alg_fq->F = 0;
- alg_fq->S = alg_fq->F + 1;
- /* XXX: why don't call delete queue? */
- }
- si->sum = 0;
- si->V = 0;
-// si->idle_heap.elements = 0;
}
/*
- * If we are getting clocks from dummynet (not a real interface) and
- * If we are under credit, schedule the next ready event.
- * Also fix the delivery time of the last packet.
+ * 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.
*/
-
-#if 0
- if (p->if_name[0]==0 && s->numbytes < 0)
- ...
-#endif
+ if (sch->elements == 0 && neh->elements > 0)
+ si->V = MAX64(si->V, HEAP_TOP(neh)->key);
+ /* Move from neh to sch any packets that have become eligible */
+ while (neh->elements > 0 && DN_KEY_LEQ(HEAP_TOP(neh)->key, si->V)) {
+ qq = HEAP_TOP(neh)->object;
+ alg_fq = (struct wf2qp_queue *)qq;
+ heap_extract(neh, NULL);
+ heap_insert(sch, alg_fq->F, qq);
+ }
+ if (pkt != NULL)
+ return dn_dequeue(q);
return NULL;
}
static int
wf2qp_new_sched(struct new_sch_inst *_si)
{
- struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
- int ofs = offsetof(struct wf2qp_queue, heap_pos);
+ struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
+ int ofs = offsetof(struct wf2qp_queue, heap_pos);
- /* only idle-heap supports extract from middle */
- if (heap_init(si->idle_heap, 16, ofs) ||
- heap_init(si->sch_heap, 16, -1) ||
- heap_init(si->ne_heap, 16, -1)) {
- heap_free(si->ne_heap);
- heap_free(si->sch_heap);
- heap_free(si->idle_heap);
- return ENOMEM;
- }
- return 0;
+ /* only idle-heap supports extract from middle */
+ if (heap_init(si->idle_heap, 16, ofs) ||
+ heap_init(si->sch_heap, 16, -1) ||
+ heap_init(si->ne_heap, 16, -1)) {
+ heap_free(si->ne_heap);
+ heap_free(si->sch_heap);
+ heap_free(si->idle_heap);
+ return ENOMEM;
+ }
+ return 0;
}
static int
wf2qp_free_sched(struct new_sch_inst *_si)
{
- struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
+ struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
- heap_free(si->sch_heap);
- heap_free(si->ne_heap);
- heap_free(si->idle_heap);
+ heap_free(si->sch_heap);
+ heap_free(si->ne_heap);
+ heap_free(si->idle_heap);
- return 0;
+ return 0;
}
static int
-wf2qp_new_queue (struct new_queue *q)
+wf2qp_new_queue(struct new_queue *_q)
{
- struct wf2qp_queue *tmp = (struct wf2qp_queue *) q;
-
- q->ni.oid.subtype = DN_SCHED_WF2QP;
-
- tmp->S = tmp->F + 1; /* hack - mark timestamp as invalid. */
+ struct wf2qp_queue *q = (struct wf2qp_queue *)(_q + 1);
+ _q->ni.oid.subtype = DN_SCHED_WF2QP;
+ q->F = 0; /* not strictly necessary */
+ q->S = q->F + 1; /* mark timestamp as invalid. */
return 0;
}
static int
wf2qp_free_queue(struct new_queue *q)
{
- struct wf2qp_si *si = (struct wf2qp_si *)q->si + 1;
- struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q;
+ struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)(q + 1);
- /* If the queue was valid, decrement the sum value
- * else this was done by dequeue()
- */
- if(alg_fq->S != alg_fq->F + 1)
- si->sum -= q->fs->fs.weight;
-
- return 0;
+ /* If the queue was valid, decrement the sum value */
+ if (alg_fq->S != alg_fq->F + 1) {
+ struct wf2qp_si *si = (struct wf2qp_si *)(q->si + 1);
+ si->sum -= q->fs->fs.weight;
+ }
+ return 0;
}
/*
* WF2Q+ scheduler descriptor
- * contains the type of the scheduler, the name, the size of the various
- * structures and function pointers. If a function is not implemented,
- * the pointer is initialized to NULL
+ * contains the type of the scheduler, the name, the size of the
+ * structures and function pointers.
*/
static struct dn_sched wf2qp_desc = {
.type = DN_SCHED_WF2QP,
@@ -381,7 +300,6 @@ static struct dn_sched wf2qp_desc = {
.new_queue = wf2qp_new_queue,
.free_queue = wf2qp_free_queue,
-
};
More information about the svn-src-user
mailing list