Date: Mon, 18 Jan 2010 09:13:47 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r202554 - user/luigi/ipfw3-head/sys/netinet/ipfw Message-ID: <201001180913.o0I9Dlx0013757@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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, - };
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001180913.o0I9Dlx0013757>