svn commit: r203276 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Sun Jan 31 11:36:04 UTC 2010
Author: luigi
Date: Sun Jan 31 11:36:04 2010
New Revision: 203276
URL: http://svn.freebsd.org/changeset/base/203276
Log:
rr: less verbose debugging, use par[1] as quantum size
wf2q+: multiply by inverse of weight instead of dividing by weight;
this saves about 50ns per packet.
Modified:
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c Sun Jan 31 11:34:44 2010 (r203275)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c Sun Jan 31 11:36:04 2010 (r203276)
@@ -198,11 +198,12 @@ static int
rr_config(struct new_schk *_schk)
{
struct rr_schk *schk = (struct rr_schk *)(_schk + 1);
- D("called");
+ ND("called");
- schk->min_q = 1;
- schk->max_q = 1000;
- schk->q_bytes = 50;
+ /* use reasonable quantums (64..2k bytes, default 1500) */
+ schk->min_q = 64;
+ schk->max_q = 2048;
+ schk->q_bytes = 1500; /* quantum */
return 0;
}
@@ -212,7 +213,7 @@ rr_new_sched(struct new_sch_inst *_si)
{
struct rr_si *si = (struct rr_si *)(_si + 1);
- D("called");
+ ND("called");
si->head = si->tail = NULL;
return 0;
@@ -221,7 +222,7 @@ rr_new_sched(struct new_sch_inst *_si)
static int
rr_free_sched(struct new_sch_inst *_si)
{
- D("called");
+ ND("called");
/* Nothing to do? */
return 0;
}
@@ -230,7 +231,10 @@ static int
rr_new_fsk(struct new_fsk *fs)
{
struct rr_schk *schk = (struct rr_schk *)(fs->sched + 1);
- ipdn_bound_var(&fs->fs.par[0], schk->min_q,
+ /* par[0] is the weight, par[1] is the quantum step */
+ ipdn_bound_var(&fs->fs.par[0], 1,
+ 1, 65536, "RR weight");
+ ipdn_bound_var(&fs->fs.par[1], schk->q_bytes,
schk->min_q, schk->max_q, "RR quantum");
return 0;
}
@@ -239,12 +243,11 @@ static int
rr_new_queue(struct new_queue *_q)
{
struct rr_queue *q = (struct rr_queue *)_q;
- struct rr_schk *schk = (struct rr_schk *)(_q->_si->sched + 1);
- D("called, schk->quantum=%d", schk->q_bytes);
_q->ni.oid.subtype = DN_SCHED_RR;
- q->quantum = _q->fs->fs.par[0] * schk->q_bytes;
+ q->quantum = _q->fs->fs.par[0] * _q->fs->fs.par[1];
+ ND("called, q->quantum %d", q->quantum);
q->credit = q->quantum;
q->status = 0;
@@ -260,7 +263,7 @@ rr_free_queue(struct new_queue *_q)
{
struct rr_queue *q = (struct rr_queue *)_q;
- D("called");
+ ND("called");
if (q->status == 1) {
struct rr_si *si = (struct rr_si *)(_q->_si + 1);
remove_queue_q(q, si);
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Sun Jan 31 11:34:44 2010 (r203275)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Sun Jan 31 11:36:04 2010 (r203276)
@@ -48,8 +48,20 @@
#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
#endif
-#ifndef MY_M
-#define MY_M 16 /* shift for fixed point arithmetic */
+/*
+ * timestamps are computed on 64 bit using fixed point arithmetic.
+ * LMAX_BITS, WMAX_BITS are the max number of bits for the packet len
+ * and sum of weights, respectively. FRAC_BITS is the number of
+ * fractional bits. We want FRAC_BITS >> WMAX_BITS to avoid too large
+ * errors when computing the inverse, FRAC_BITS < 32 so we can do 1/w
+ * using an unsigned 32-bit division, and to avoid wraparounds we need
+ * LMAX_BITS + WMAX_BITS + FRAC_BITS << 64
+ * As an example
+ * FRAC_BITS = 26, LMAX_BITS=14, WMAX_BITS = 19
+ */
+#ifndef FRAC_BITS
+#define FRAC_BITS 28 /* shift for fixed point arithmetic */
+#define ONE_FP (1UL << FRAC_BITS)
#endif
/*
@@ -67,11 +79,14 @@ struct wf2qp_si {
struct dn_heap ne_heap; /* top extract - key Start time */
struct dn_heap idle_heap; /* random extract - key Start=Finish time */
uint64_t V; /* virtual time */
- uint32_t sum; /* sum of weights */
+ uint32_t inv_wsum; /* inverse of sum of weights */
+ uint32_t wsum; /* sum of weights */
};
struct wf2qp_queue {
+ struct new_queue _q;
uint64_t S, F; /* start time, finish time */
+ uint32_t inv_w; /* ONE_FP / weight */
int32_t heap_pos; /* position (index) of struct in heap */
};
@@ -93,14 +108,16 @@ idle_check(struct wf2qp_si *si, int n, i
while (n-- > 0 && h->elements > 0 &&
(force || DN_KEY_LT(HEAP_TOP(h)->key, si->V))) {
struct new_queue *q = HEAP_TOP(h)->object;
- struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)(q+1);
+ struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q;
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.par[0]; /* adjust sum of weights */
+ si->wsum -= q->fs->fs.par[0]; /* adjust sum of weights */
+ if (si->wsum > 0)
+ si->inv_wsum = ONE_FP/si->wsum;
}
}
@@ -120,17 +137,18 @@ wf2qp_enqueue(struct new_sch_inst *_si,
}
/* If reach this point, queue q was idle */
- alg_fq = (struct wf2qp_queue *)(q+1);
+ alg_fq = (struct wf2qp_queue *)q;
if (DN_KEY_LT(alg_fq->F, alg_fq->S)) {
/* F<S means timestamps are invalid ->brand new queue. */
alg_fq->S = si->V; /* init start time */
- si->sum += fs->fs.par[0]; /* add weight of new queue. */
+ si->wsum += fs->fs.par[0]; /* add weight of new queue. */
+ si->inv_wsum = ONE_FP/si->wsum;
} 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); /* compute new S */
}
- alg_fq->F = alg_fq->S + div64((len << MY_M), fs->fs.par[0]);
+ alg_fq->F = alg_fq->S + len * alg_fq->inv_w;
/* if nothing is backlogged, make sure this flow is eligible */
if (si->ne_heap.elements == 0 && si->sch_heap.elements == 0)
@@ -164,7 +182,7 @@ wf2qp_dequeue(struct new_sch_inst *_si)
{
/* Access scheduler instance private data */
struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
- struct mbuf *pkt;
+ struct mbuf *m;
struct new_queue *q;
struct dn_heap *sch = &si->sch_heap;
struct dn_heap *neh = &si->ne_heap;
@@ -176,7 +194,7 @@ wf2qp_dequeue(struct new_sch_inst *_si)
*/
idle_check(si, 0x7fffffff, 1);
si->V = 0;
- si->sum = 0; /* should be set already */
+ si->wsum = 0; /* should be set already */
return NULL; /* quick return if nothing to do */
}
idle_check(si, 1, 0); /* drain something from the idle heap */
@@ -187,7 +205,7 @@ wf2qp_dequeue(struct new_sch_inst *_si)
* after extracting the candidate, or enqueue() will
* find the data structure in a wrong state.
*/
- pkt = NULL;
+ m = NULL;
for(;;) {
/*
* Compute V = max(V, min(S_i)). Remember that all elements
@@ -203,25 +221,25 @@ 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 + 1);
+ alg_fq = (struct wf2qp_queue *)q;
heap_extract(neh, NULL);
heap_insert(sch, alg_fq->F, q);
}
- if (pkt) /* pkt found in previous iteration */
+ if (m) /* 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);
- pkt = dn_dequeue(q);
+ alg_fq = (struct wf2qp_queue *)q;
+ m = dn_dequeue(q);
heap_extract(sch, NULL); /* Remove queue from heap. */
- si->V += div64(pkt->m_pkthdr.len << MY_M, si->sum);
+ si->V += (uint64_t)(m->m_pkthdr.len) * si->inv_wsum;
alg_fq->S = alg_fq->F; /* Update start time. */
if (q->mq.head == 0) { /* not backlogged any more. */
heap_insert(&si->idle_heap, alg_fq->F, q);
} else { /* Still backlogged. */
/* Update F, store in neh or sch */
uint64_t len = q->mq.head->m_pkthdr.len;
- alg_fq->F += div64(len << MY_M, q->fs->fs.par[0]);
+ alg_fq->F += len * alg_fq->inv_w;
if (DN_KEY_LEQ(alg_fq->S, si->V)) {
heap_insert(sch, alg_fq->F, q);
} else {
@@ -229,14 +247,14 @@ wf2qp_dequeue(struct new_sch_inst *_si)
}
}
}
- return pkt;
+ return m;
}
static int
wf2qp_new_sched(struct new_sch_inst *_si)
{
struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
- int ofs = sizeof(*_si) + offsetof(struct wf2qp_queue, heap_pos);
+ int ofs = offsetof(struct wf2qp_queue, heap_pos);
/* all heaps support extract from middle */
if (heap_init(&si->idle_heap, 16, ofs) ||
@@ -274,11 +292,12 @@ wf2qp_new_fsk(struct new_fsk *fs)
static int
wf2qp_new_queue(struct new_queue *_q)
{
- struct wf2qp_queue *q = (struct wf2qp_queue *)(_q + 1);
+ struct wf2qp_queue *q = (struct wf2qp_queue *)_q;
_q->ni.oid.subtype = DN_SCHED_WF2QP;
q->F = 0; /* not strictly necessary */
q->S = q->F + 1; /* mark timestamp as invalid. */
+ q->inv_w = ONE_FP / _q->fs->fs.par[0];
if (_q->mq.head != NULL) {
wf2qp_enqueue(_q->_si, _q, _q->mq.head);
}
@@ -294,13 +313,15 @@ wf2qp_new_queue(struct new_queue *_q)
static int
wf2qp_free_queue(struct new_queue *q)
{
- struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)(q + 1);
+ struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q;
struct wf2qp_si *si = (struct wf2qp_si *)(q->_si + 1);
printf("%s called\n", __FUNCTION__);
if (alg_fq->S >= alg_fq->F + 1)
return 0; /* nothing to do, not in any heap */
- si->sum -= q->fs->fs.par[0];
+ si->wsum -= q->fs->fs.par[0];
+ if (si->wsum > 0)
+ si->inv_wsum = ONE_FP/si->wsum;
/* extract from the heap. XXX TODO we may need to adjust V
* to make sure the invariants hold.
@@ -327,7 +348,7 @@ static struct dn_alg wf2qp_desc = {
/* we need extra space in the si and the queue */
.si_datalen = sizeof(struct wf2qp_si),
- .q_datalen = sizeof(struct wf2qp_queue),
+ .q_datalen = sizeof(struct wf2qp_queue) - sizeof(struct new_queue),
.enqueue = wf2qp_enqueue,
.dequeue = wf2qp_dequeue,
More information about the svn-src-user
mailing list