Date: Sun, 31 Jan 2010 11:36:04 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r203276 - user/luigi/ipfw3-head/sys/netinet/ipfw Message-ID: <201001311136.o0VBa4CQ011761@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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,
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001311136.o0VBa4CQ011761>