From owner-svn-src-user@FreeBSD.ORG Thu Jan 7 23:17:48 2010 Return-Path: Delivered-To: svn-src-user@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id E9BD21065692; Thu, 7 Jan 2010 23:17:48 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id D76358FC12; Thu, 7 Jan 2010 23:17:48 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id o07NHmBC094665; Thu, 7 Jan 2010 23:17:48 GMT (envelope-from luigi@svn.freebsd.org) Received: (from luigi@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o07NHmnP094661; Thu, 7 Jan 2010 23:17:48 GMT (envelope-from luigi@svn.freebsd.org) Message-Id: <201001072317.o07NHmnP094661@svn.freebsd.org> From: Luigi Rizzo Date: Thu, 7 Jan 2010 23:17:48 +0000 (UTC) To: src-committers@freebsd.org, svn-src-user@freebsd.org X-SVN-Group: user MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r201762 - user/luigi/ipfw3-head/sys/netinet/ipfw X-BeenThere: svn-src-user@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the experimental " user" src tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Jan 2010 23:17:49 -0000 Author: luigi Date: Thu Jan 7 23:17:48 2010 New Revision: 201762 URL: http://svn.freebsd.org/changeset/base/201762 Log: snapshot of current version Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Thu Jan 7 22:59:08 2010 (r201761) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Thu Jan 7 23:17:48 2010 (r201762) @@ -114,7 +114,7 @@ struct dn_sched { * drain_queue called to free all idle queues, or possibly all of * them (this is a subset of delete_scheduler_instance) */ - int (*enqueue)(void *s, struct gen *f, struct mbuf *m, + int (*enqueue)(void *s, struct dn_id *f, struct mbuf *m, struct ipfw_flow_id *id); struct mbuf * (*dequeue)(void *s); @@ -123,15 +123,15 @@ struct dn_sched { int (*new_sched)(void *v); int (*free_sched)(void *s); - int (*new_fs)(char *command, struct gen *g, int reconfigure); - int (*free_fs)(struct gen *f); + int (*new_fs)(char *command, struct dn_id *g, int reconfigure); + int (*free_fs)(struct dn_id *f); - int (*new_queue)(struct new_queue *q, struct gen *f); + int (*new_queue)(struct new_queue *q, struct dn_id *f); int (*free_queue)(struct new_queue *q); int (*drain_queue)(void *s, int flag); }; -SLIST_HEAD(scheduler_head, dn_sched); +SLIST_HEAD(dn_sched_head, dn_sched); /* * Additionally, dummynet exports some variables, functions and macros @@ -158,7 +158,7 @@ int dn_delete_queue (struct new_queue *q * - id: flow id for this queue * - size: size of the queue, including the private data */ -struct new_queue * dn_create_queue(struct gen *f, void *s, int i, +struct new_queue * dn_create_queue(struct dn_id *f, void *s, int i, struct ipfw_flow_id *id); /* Allocate an hash table. @@ -189,7 +189,7 @@ int dn_drop_packet(struct new_queue *q, * - f: pointer to the flowset (private data) * - rq_size: size of the hash table */ -int dn_i_hash_id(struct ipfw_flow_id *id, struct gen *f, int rq_size); +int dn_i_hash_id(struct ipfw_flow_id *id, struct dn_id *f, int rq_size); /* Returns the queue that match the flowid at the index i, if exists. * Returns NULL if the queue doesn't exist. @@ -200,7 +200,7 @@ int dn_i_hash_id(struct ipfw_flow_id *id * the flowset generic data */ struct new_queue * dn_q_hash_id(struct ipfw_flow_id *id, int i, - struct new_queue **rq, struct gen *f); + struct new_queue **rq, struct dn_id *f); int dn_sched_modevent(module_t mod, int cmd, void *arg); Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Thu Jan 7 22:59:08 2010 (r201761) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Thu Jan 7 23:17:48 2010 (r201762) @@ -59,6 +59,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include /* various ether_* routines */ @@ -86,12 +87,11 @@ struct dn_parms dn_cfg = { .red_max_pkt_size = 1500, /* RED - default max packet size */ }; -//static struct timeval t; -static long tick_last; /* Last tick duration (usec). */ -static long tick_delta; /* Last vs standard tick diff (usec). */ -static long tick_delta_sum; /* Accumulated tick difference (usec).*/ -static long tick_adjustment; /* Tick adjustments done. */ -static long tick_lost; /* Lost(coalesced) ticks number. */ +//static long tick_last; /* Last tick duration (usec). */ +static long tick_delta; /* Last vs standard tick diff (usec). */ +static long tick_delta_sum; /* Accumulated tick difference (usec).*/ +static long tick_adjustment; /* Tick adjustments done. */ +static long tick_lost; /* Lost(coalesced) ticks number. */ /* Adjusted vs non-adjusted curr_time difference (ticks). */ static long tick_diff; @@ -100,6 +100,13 @@ static unsigned long io_pkt_fast; static unsigned long io_pkt_drop; /* + * We use a heap to store entities for which we have pending timer events. + * The heap is checked at every tick and all entities with expired events + * are extracted. + */ +static struct dn_heap *system_heap; + +/* * Three heaps contain queues and pipes that the scheduler handles: * * ready_heap contains all dn_flow_queue related to fixed-rate pipes. @@ -125,7 +132,7 @@ static unsigned long io_pkt_drop; * (a better name would be useful...). */ #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) -#define MY_M 16 /* number of left shift to obtain a larger precision */ +#define MY_M 16 /* shift for fixed point arithmetic */ /* * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the @@ -134,16 +141,9 @@ static unsigned long io_pkt_drop; MALLOC_DEFINE(M_DUMMYNET, "dummynet", "dummynet heap"); -static void transmit_event(struct dn_pipe *pipe, struct mbuf **head, - struct mbuf **tail); -static void ready_event(struct dn_flow_queue *q, struct mbuf **head, - struct mbuf **tail); -static void ready_event_wfq(struct dn_pipe *p, struct mbuf **head, - struct mbuf **tail); - struct dn_heap ready_heap, extract_heap, wfq_ready_heap ; -struct dn_pipe_head pipehash[DN_HASHSIZE]; /* all pipes */ -struct dn_flow_set_head flowsethash[DN_HASHSIZE]; /* all flowsets */ +struct new_pipe_head pipehash[DN_HASHSIZE]; /* all pipes */ +struct new_fs_head flowsethash[DN_HASHSIZE]; /* all flowsets */ extern void (*bridge_dn_p)(struct mbuf *, struct ifnet *); @@ -244,11 +244,11 @@ struct dn_pkt_tag { struct ipfw_rule_ref rule; /* matching rule */ /* second part, dummynet specific */ - int dn_dir; /* action when packet comes out. */ - /* see ip_fw_private.h */ - dn_key output_time; /* when the pkt is due for delivery */ - struct ifnet *ifp; /* interface, for ip_output */ - struct _ip6dn_args ip6opt; /* XXX ipv6 options */ + int dn_dir; /* action when packet comes out.*/ + /* see ip_fw_private.h */ + dn_key output_time; /* when the pkt is due for delivery*/ + struct ifnet *ifp; /* interface, for ip_output */ + struct _ip6dn_args ip6opt; /* XXX ipv6 options */ }; /* @@ -268,55 +268,43 @@ dn_tag_get(struct mbuf *m) } /* - * Scheduler functions: - * - * transmit_event() is called when the delay-line needs to enter - * the scheduler, either because of existing pkts getting ready, - * or new packets entering the queue. The event handled is the delivery - * time of the packet. - * - * ready_event() does something similar with fixed-rate queues, and the - * event handled is the finish time of the head pkt. - * - * wfq_ready_event() does something similar with WF2Q queues, and the - * event handled is the start time of the head pkt. - * - * In all cases, we make sure that the data structures are consistent - * before passing pkts out, because this might trigger recursive - * invocations of the procedures. + * It is called when we have some packet from delay line to send. + * If there are leftover packets, this delay line is reinserted into extract + * heap */ -static void -transmit_event(struct dn_pipe *pipe, struct mbuf **head, struct mbuf **tail) +static +struct mbuf * +transmit_event(struct delay_line *dline, dn_key l_curr_time) { - struct mbuf *m; - struct dn_pkt_tag *pkt; - - DUMMYNET_LOCK_ASSERT(); + struct mbuf *m; + struct dn_pkt_tag *pkt; - while ((m = pipe->head) != NULL) { - pkt = dn_tag_get(m); - if (!DN_KEY_LEQ(pkt->output_time, curr_time)) - break; + struct mbuf *head = NULL, *tail = NULL; + /* XXX scheduler lock */ + while ((m = dline->head) != NULL) { + pkt = dn_tag_get(m); + if (!DN_KEY_LEQ(pkt->output_time, l_curr_time)) + break; + dline->head = m->m_nextpkt; + if (tail != NULL) + tail->m_nextpkt = m; + else + head = m; + tail = m; + } - pipe->head = m->m_nextpkt; - if (*tail != NULL) - (*tail)->m_nextpkt = m; - else - *head = m; - *tail = m; - } - if (*tail != NULL) - (*tail)->m_nextpkt = NULL; + if (tail != NULL) + tail->m_nextpkt = NULL; - /* If there are leftover packets, put into the heap for next event. */ - if ((m = pipe->head) != NULL) { - pkt = dn_tag_get(m); - /* - * XXX Should check errors on heap_insert, by draining the - * whole pipe p and hoping in the future we are more successful. - */ - heap_insert(&extract_heap, pkt->output_time, pipe); - } + /* If there are leftover packets, put into the heap for next event. */ + if ((m = dline->head) != NULL) { + pkt = dn_tag_get(m); + //DN_HEAP_LOCK(); + heap_insert(system_heap, pkt->output_time, dline); + //DN_HEAP_UNLOCK(); + } + /* XXX scheduler unlock */ + return head; } #define div64(a, b) ((int64_t)(a) / (int64_t)(b)) @@ -345,7 +333,7 @@ set_ticks(struct mbuf *m, struct dn_flow * so we need to divide by 1000. */ static dn_key -compute_extra_bits(struct mbuf *pkt, struct dn_pipe *p) +compute_extra_bits(struct mbuf *pkt, struct new_pipe *p) { int index; dn_key extra_bits; @@ -362,253 +350,27 @@ compute_extra_bits(struct mbuf *pkt, str return extra_bits; } -/* - * extract pkt from queue, compute output time (could be now) - * and put into delay line (p_queue) - */ +/* Insert packet pkt into delay line of si. */ static void -move_pkt(struct mbuf *pkt, struct dn_flow_queue *q, struct dn_pipe *p, - int len) +move_pkt(struct mbuf *pkt, struct new_pipe *p, struct new_sch_inst *si, + dn_key l_curr_time) { struct dn_pkt_tag *dt = dn_tag_get(pkt); + struct delay_line *d = si->dline; + + dt->output_time = l_curr_time + p->delay ; - q->head = pkt->m_nextpkt ; - q->len-- ; - q->len_bytes -= len ; - - dt->output_time = curr_time + p->delay ; - - if (p->head == NULL) - p->head = pkt; + if (d->head == NULL) + d->head = pkt; else - p->tail->m_nextpkt = pkt; - p->tail = pkt; - p->tail->m_nextpkt = NULL; -} - -/* - * ready_event() is invoked every time the queue must enter the - * scheduler, either because the first packet arrives, or because - * a previously scheduled event fired. - * On invokation, drain as many pkts as possible (could be 0) and then - * if there are leftover packets reinsert the pkt in the scheduler. - */ -static void -ready_event(struct dn_flow_queue *q, struct mbuf **head, struct mbuf **tail) -{ - struct mbuf *pkt; - struct dn_pipe *p = q->fs->pipe; - int p_was_empty; - - DUMMYNET_LOCK_ASSERT(); - - if (p == NULL) { - printf("dummynet: ready_event- pipe is gone\n"); - return; - } - p_was_empty = (p->head == NULL); - - /* - * Schedule fixed-rate queues linked to this pipe: - * account for the bw accumulated since last scheduling, then - * drain as many pkts as allowed by q->numbytes and move to - * the delay line (in p) computing output time. - * bandwidth==0 (no limit) means we can drain the whole queue, - * setting len_scaled = 0 does the job. - */ - q->numbytes += (curr_time - q->sched_time) * p->bandwidth; - while ((pkt = q->head) != NULL) { - int len = pkt->m_pkthdr.len; - dn_key len_scaled = p->bandwidth ? len*8*hz - + q->extra_bits*hz - : 0; - - if (DN_KEY_GT(len_scaled, q->numbytes)) - break; - q->numbytes -= len_scaled; - move_pkt(pkt, q, p, len); - if (q->head) - q->extra_bits = compute_extra_bits(q->head, p); - } - /* - * If we have more packets queued, schedule next ready event - * (can only occur when bandwidth != 0, otherwise we would have - * flushed the whole queue in the previous loop). - * To this purpose we record the current time and compute how many - * ticks to go for the finish time of the packet. - */ - if ((pkt = q->head) != NULL) { /* this implies bandwidth != 0 */ - dn_key t = set_ticks(pkt, q, p); /* ticks i have to wait */ - - q->sched_time = curr_time; - heap_insert(&ready_heap, curr_time + t, (void *)q); - /* - * XXX Should check errors on heap_insert, and drain the whole - * queue on error hoping next time we are luckier. - */ - } else /* RED needs to know when the queue becomes empty. */ - q->idle_time = curr_time; - - /* - * If the delay line was empty call transmit_event() now. - * Otherwise, the scheduler will take care of it. - */ - if (p_was_empty) - transmit_event(p, head, tail); -} - -/* callback to clean the idle heap */ -static int -clean_fq(void *_q, uintptr_t arg) -{ - struct dn_flow_queue *q = _q; - - q->F = 0; - q->S = q->F + 1; - return HEAP_SCAN_DEL; + d->tail->m_nextpkt = pkt; + d->tail = pkt; + d->tail->m_nextpkt = NULL; } -/* - * Called when we can transmit packets on WF2Q queues. Take pkts out of - * the queues at their start time, and enqueue into the delay line. - * Packets are drained until p->numbytes < 0. As long as - * len_scaled >= p->numbytes, the packet goes into the delay line - * with a deadline p->delay. For the last packet, if p->numbytes < 0, - * there is an additional delay. - */ -static void -ready_event_wfq(struct dn_pipe *p, struct mbuf **head, struct mbuf **tail) -{ - int p_was_empty = (p->head == NULL); - struct dn_heap *sch = p->scheduler_heap; - struct dn_heap *neh = p->not_eligible_heap; - int64_t p_numbytes = p->numbytes; - - /* - * p->numbytes is only 32bits in FBSD7, but we might need 64 bits. - * Use a local variable for the computations, and write back the - * results when done, saturating if needed. - * The local variable has no impact on performance and helps - * reducing diffs between the various branches. - */ - - DUMMYNET_LOCK_ASSERT(); - - if (p->if_name[0] == 0) /* tx clock is simulated */ - p_numbytes += (curr_time - p->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; - else { - DPRINTF(("dummynet: pipe %d ready from %s --\n", - p->pipe_nr, p->if_name)); - } - } - - /* - * While we have backlogged traffic AND credit, we need to do - * something on the queue. - */ - while (p_numbytes >= 0 && (sch->elements > 0 || neh->elements > 0)) { - if (sch->elements > 0) { - /* Have some eligible pkts to send out. */ - struct dn_flow_queue *q = HEAP_TOP(sch)->object; - struct mbuf *pkt = q->head; - struct dn_flow_set *fs = q->fs; - uint64_t len = pkt->m_pkthdr.len; - int len_scaled = p->bandwidth ? len * 8 * hz : 0; - - heap_extract(sch, NULL); /* Remove queue from heap. */ - p_numbytes -= len_scaled; - move_pkt(pkt, q, p, len); - - p->V += div64((len << MY_M), p->sum); /* Update V. */ - q->S = q->F; /* Update start time. */ - if (q->len == 0) { - /* Flow not backlogged any more. */ - fs->backlogged--; - heap_insert(p->idle_heap, q->F, q); - } else { - /* Still backlogged. */ - - /* - * Update F and position in backlogged queue, - * then put flow in not_eligible_heap - * (we will fix this later). - */ - len = (q->head)->m_pkthdr.len; - q->F += div64((len << MY_M), fs->weight); - if (DN_KEY_LEQ(q->S, p->V)) - heap_insert(neh, q->S, q); - else - heap_insert(sch, q->F, 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) - p->V = MAX64(p->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, p->V)) { - struct dn_flow_queue *q = HEAP_TOP(neh)->object; - heap_extract(neh, NULL); - heap_insert(sch, q->F, q); - } - - if (p->if_name[0] != '\0') { /* Tx clock is from a real thing */ - p_numbytes = -1; /* Mark not ready for I/O. */ - break; - } - } - if (sch->elements == 0 && neh->elements == 0 && p_numbytes >= 0) { - p->idle_time = curr_time; - /* - * No traffic and no events scheduled. - * We can get rid of idle-heap. - */ - if (p->idle_heap->elements > 0) { - heap_scan(p->idle_heap, clean_fq, 0); - p->sum = 0; - p->V = 0; - p->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. - */ - if (p->if_name[0]==0 && p_numbytes < 0) { /* This implies bw > 0. */ - dn_key t = 0; /* Number of ticks i have to wait. */ - - if (p->bandwidth > 0) - t = div64(p->bandwidth - 1 - p_numbytes, p->bandwidth); - dn_tag_get(p->tail)->output_time += t; - p->sched_time = curr_time; - heap_insert(&wfq_ready_heap, curr_time + t, (void *)p); - /* - * XXX Should check errors on heap_insert, and drain the whole - * queue on error hoping next time we are luckier. - */ - } - - /* Write back p_numbytes (adjust 64->32bit if necessary). */ - p->numbytes = p_numbytes; - - /* - * If the delay line was empty call transmit_event() now. - * Otherwise, the scheduler will take care of it. - */ - if (p_was_empty) - transmit_event(p, head, tail); -} +struct new_sch_inst * +find_scheduler(struct new_sch *sch_t, struct new_fs *fs, + struct ipfw_flow_id *id, dn_key l_curr_time); /* * The timer handler for dummynet. Time is computed in ticks, but @@ -618,8 +380,9 @@ ready_event_wfq(struct dn_pipe *p, struc void dummynet_task(void *context, int pending) { +#if 0 struct mbuf *head = NULL, *tail = NULL; - struct dn_pipe *pipe; + struct new_pipe *pipe; struct dn_heap *heaps[3]; struct dn_heap *h; void *p; /* generic parameter to handler */ @@ -713,7 +476,7 @@ dummynet_task(void *context, int pending if (head != NULL) dummynet_send(head); - +#endif dn_reschedule(); } @@ -800,6 +563,7 @@ dummynet_send(struct mbuf *m) } } +#if 0 /* * Unconditionally expire empty queues in case of shortage. * Returns the number of queues freed. @@ -1081,11 +845,12 @@ red_drops(struct dn_flow_set *fs, struct return (0); /* accept */ } +#endif -struct dn_flow_set * +struct new_fs * ipdn_locate_flowset(int fs_nr) { - struct dn_flow_set *fs; + struct new_fs *fs; SLIST_FOREACH(fs, &flowsethash[HASH(fs_nr)], next) if (fs->fs_nr == fs_nr) @@ -1094,10 +859,10 @@ ipdn_locate_flowset(int fs_nr) return (NULL); } -struct dn_pipe * +struct new_pipe * ipdn_locate_pipe(int pipe_nr) { - struct dn_pipe *pipe; + struct new_pipe *pipe; SLIST_FOREACH(pipe, &pipehash[HASH(pipe_nr)], next) if (pipe->pipe_nr == pipe_nr) @@ -1106,6 +871,31 @@ ipdn_locate_pipe(int pipe_nr) return (NULL); } +struct ipfw_flow_id * +do_mask(struct ipfw_flow_id *mask, struct ipfw_flow_id *id); +/* Do masking depending of flow id */ +struct ipfw_flow_id * +do_mask(struct ipfw_flow_id *mask, struct ipfw_flow_id *id) +{ + int is_v6 = IS_IP6_FLOW_ID(id); + + id->dst_port &= mask->dst_port; + id->src_port &= mask->src_port; + id->proto &= mask->proto; + id->flags = 0; /* we don't care about this one */ + if (is_v6) { + APPLY_MASK(&id->dst_ip6, &mask->dst_ip6); + APPLY_MASK(&id->src_ip6, &mask->src_ip6); + id->flow_id6 &= mask->flow_id6; + } + else { + id->dst_ip &= mask->dst_ip; + id->src_ip &= mask->src_ip; + } + + return id; +} + /* * dummynet hook for packets. Below 'pipe' is a pipe or a queue * depending on whether WF2Q or fixed bw is used. @@ -1124,15 +914,19 @@ ipdn_locate_pipe(int pipe_nr) int dummynet_io(struct mbuf **m0, int dir, struct ip_fw_args *fwa) { - struct mbuf *m = *m0, *head = NULL, *tail = NULL; + struct mbuf *m = *m0, *head = NULL; struct dn_pkt_tag *pkt; struct m_tag *mtag; - struct dn_flow_set *fs = NULL; - struct dn_pipe *pipe = NULL; - uint64_t len = m->m_pkthdr.len; - struct dn_flow_queue *q = NULL; + struct new_fs *fs = NULL; + struct new_pipe *pipe = NULL; + struct new_queue *q = NULL; int fs_id = fwa->rule.info & IPFW_INFO_MASK; - int is_pipe = 0; + struct new_sch *sch; + struct new_sch_inst *sch_inst; + struct delay_line *dline; + int ret; + dn_key l_curr_time; /* save a copy of curr_time */ + int delay_line_idle; if (fwa->rule.info & IPFW_IS_PIPE) fs_id += DN_PIPEOFFSET; @@ -1146,10 +940,10 @@ dummynet_io(struct mbuf **m0, int dir, s if (fs == NULL) goto dropit; /* This queue/pipe does not exist! */ -#if 0 + if (fs->sched_id != dn_cfg.id) { /* configuration changed, update */ - int ret = reconfigure(fs); + int ret = dn_fs_config(fs); if (ret) goto dropit; /* find again, just in case things changed */ @@ -1160,25 +954,19 @@ dummynet_io(struct mbuf **m0, int dir, s sch = fs->sched; if (sch == NULL) goto dropit; -#endif - q = find_queue(fs, &(fwa->f_id)); - if (q == NULL) - goto dropit; /* Cannot allocate queue. */ - - /* Update statistics, then check reasons to drop pkt. */ - q->tot_bytes += len; - q->tot_pkts++; - if (fs->plr && random() < fs->plr) - goto dropit; /* Random pkt drop. */ - if (fs->flags_fs & DN_QSIZE_IS_BYTES) { - if (q->len_bytes > fs->qsize) - goto dropit; /* Queue size overflow. */ - } else { - if (q->len >= fs->qsize) - goto dropit; /* Queue count overflow. */ - } - if (fs->flags_fs & DN_IS_RED && red_drops(fs, q, len)) + pipe = sch->pipe; + if (pipe == NULL) /* should not happen ? */ + goto dropit; + + l_curr_time = curr_time; + sch_inst = find_scheduler(sch, fs, &(fwa->f_id), l_curr_time); + if (sch_inst == NULL) goto dropit; + dline = sch_inst->dline; + delay_line_idle = (dline->head == NULL); + + /* Now do the masking */ + do_mask(&fs->flow_mask, &(fwa->f_id)); /* tag the mbuf */ mtag = m_tag_get(PACKET_TAG_DUMMYNET, @@ -1197,128 +985,96 @@ dummynet_io(struct mbuf **m0, int dir, s pkt->dn_dir = dir; pkt->ifp = fwa->oif; - if (q->head == NULL) - q->head = m; - else - q->tail->m_nextpkt = m; - q->tail = m; - q->len++; - q->len_bytes += len; - - if (q->head != m) /* Flow was not idle, we are done. */ - goto done; - - if (is_pipe) { /* Fixed rate queues. */ - if (q->idle_time < curr_time) { - /* Calculate available burst size. */ - q->numbytes += - (curr_time - q->idle_time - 1) * pipe->bandwidth; - if (q->numbytes > pipe->burst) - q->numbytes = pipe->burst; - if (dn_cfg.io_fast) - q->numbytes += pipe->bandwidth; - } - } else { /* WF2Q. */ - if (pipe->idle_time < curr_time && - pipe->scheduler_heap->elements == 0 && - pipe->not_eligible_heap->elements == 0) { - /* Calculate available burst size. */ - pipe->numbytes += - (curr_time - pipe->idle_time - 1) * pipe->bandwidth; - if (pipe->numbytes > 0 && pipe->numbytes > pipe->burst) - pipe->numbytes = pipe->burst; - if (dn_cfg.io_fast) - pipe->numbytes += pipe->bandwidth; - } - pipe->idle_time = curr_time; - } - /* Necessary for both: fixed rate & WF2Q queues. */ - q->idle_time = curr_time; - /* - * If we reach this point the flow was previously idle, so we need - * to schedule it. This involves different actions for fixed-rate or - * WF2Q queues. + * - 'sch_inst + 1' is the pointer to scheduler instance's + * private data, 'fs->alg_fs' is the flowset's private data, + * 'm' is the packet, 'id' is the masked flowid of the packet + * + * NOTE: If the scheduler function wants really enqueue the + * packet, it must call the queue_packet() */ - if (is_pipe) { - /* Fixed-rate queue: just insert into the ready_heap. */ - dn_key t = 0; - - if (pipe->bandwidth) { - q->extra_bits = compute_extra_bits(m, pipe); - t = set_ticks(m, q, pipe); - } - q->sched_time = curr_time; - if (t == 0) /* Must process it now. */ - ready_event(q, &head, &tail); - else - heap_insert(&ready_heap, curr_time + t , q); - } else { - /* - * WF2Q. First, compute start time S: if the flow was - * idle (S = F + 1) set S to the virtual time V for the - * controlling pipe, and update the sum of weights for the pipe; - * otherwise, remove flow from idle_heap and set S to max(F,V). - * Second, compute finish time F = S + len / weight. - * Third, if pipe was idle, update V = max(S, V). - * Fourth, count one more backlogged flow. - */ - if (DN_KEY_GT(q->S, q->F)) { /* Means timestamps are invalid. */ - q->S = pipe->V; - pipe->sum += fs->weight; /* Add weight of new queue. */ - } else { - heap_extract(pipe->idle_heap, q); - q->S = MAX64(q->F, pipe->V); - } - q->F = q->S + div64(len << MY_M, fs->weight); - if (pipe->not_eligible_heap->elements == 0 && - pipe->scheduler_heap->elements == 0) - pipe->V = MAX64(q->S, pipe->V); - fs->backlogged++; - /* - * Look at eligibility. A flow is not eligibile if S>V (when - * this happens, it means that there is some other flow already - * scheduled for the same pipe, so the scheduler_heap cannot be - * empty). If the flow is not eligible we just store it in the - * not_eligible_heap. Otherwise, we store in the scheduler_heap - * and possibly invoke ready_event_wfq() right now if there is - * leftover credit. - * Note that for all flows in scheduler_heap (SCH), S_i <= V, - * and for all flows in not_eligible_heap (NEH), S_i > V. - * So when we need to compute max(V, min(S_i)) forall i in - * SCH+NEH, we only need to look into NEH. - */ - if (DN_KEY_GT(q->S, pipe->V)) { /* Not eligible. */ - if (pipe->scheduler_heap->elements == 0) - printf("dummynet: ++ ouch! not eligible but empty scheduler!\n"); - heap_insert(pipe->not_eligible_heap, q->S, q); - } else { - heap_insert(pipe->scheduler_heap, q->F, q); - if (pipe->numbytes >= 0) { /* Pipe is idle. */ - if (pipe->scheduler_heap->elements != 1) - printf("dummynet: OUCH! pipe should have been idle!\n"); - DPRINTF(("dummynet: waking up pipe %d at %d\n", - pipe->pipe_nr, (int)(q->F >> MY_M))); - pipe->sched_time = curr_time; - ready_event_wfq(pipe, &head, &tail); - } - } + ret = sch->fp->enqueue( + (sch_inst + 1), fs->alg_fs, m, + &(fwa->f_id)); + + if (ret) { /* packet was dropped by enqueue() */ + *m0 = NULL; + goto dropit; } -done: - if (head == m && (dir & PROTO_LAYER2) == 0 ) { - /* Fast io. */ - io_pkt_fast++; - if (m->m_nextpkt != NULL) - printf("dummynet: fast io: pkt chain detected!\n"); - head = m->m_nextpkt = NULL; - } else - *m0 = NULL; /* Normal io. */ - DUMMYNET_UNLOCK(); - if (head != NULL) - dummynet_send(head); - return (0); + /* + * Now check if the dequeue should be called now. + * If the instance is in the heap, the dequeue() will be called later, + * else if the instance has credit the dequeue() is called now. + */ + if (!(sch_inst->flags & DN_SCH_ACTIVE)) { + /* If the instance is not in the heap, credit must be >= 0 */ + struct mbuf *tosend; + dn_key len_scaled; + + /* If the instance isn't in the heap, it is idle, so we can skip + * some checks XXX + */ + if (sch->burst) { + sch_inst->numbytes = (l_curr_time - sch_inst->idle_time) * + pipe->bandwidth; + if (sch_inst->numbytes > sch->burst) + sch_inst->numbytes = sch->burst; + sch_inst->numbytes += dn_cfg.io_fast ? pipe->bandwidth : 0; + } else + sch_inst->numbytes = dn_cfg.io_fast ? pipe->bandwidth : 0; + + sch_inst->idle_time = l_curr_time; + + /* Doing an 'if' instead of 'while' because only the packet + * just enqueued can be returned by dequeue() */ + tosend = sch->fp->dequeue(sch_inst + 1); + if (tosend) { + len_scaled = pipe->bandwidth ? tosend->m_pkthdr.len * 8 * hz + + compute_extra_bits(tosend, pipe) * hz : 0; + sch_inst->numbytes -= len_scaled; + /* Move packet in the delay line XXX three parameters? */ + move_pkt(tosend, pipe, sch_inst, l_curr_time); + if (sch_inst->numbytes < 0) { + /* + * Credit became negative, so insert the instance in the + * heap so that it will not be wake up until credit come + * back positive + * NOTE: numbytes < 0 implies bandwidth != 0. + */ + dn_key t = 0, tmp; + t = (pipe->bandwidth - 1 - sch_inst->numbytes) / + pipe->bandwidth; + /* Delay the output time because under credit */ + (dn_tag_get(dline->tail))->output_time += t; + + sch_inst->ptr_sched->inst_counter++; + sch_inst->flags |= DN_SCH_ACTIVE; + tmp = l_curr_time + t; + //DN_HEAP_LOCK(); + heap_insert(system_heap, (uint64_t)tmp, sch_inst); + //DN_HEAP_UNLOCK(); + } + if (delay_line_idle) + head = transmit_event(dline, l_curr_time); + } + } + + if (dn_cfg.io_fast && head == m && (dir & PROTO_LAYER2) == 0 ) { + /* fast io */ + io_pkt_fast++; + printf("dummynet TEST: ** IOFAST **\n"); + if (m->m_nextpkt != NULL) + printf("dummynet: fast io: pkt chain detected!\n"); + head = m->m_nextpkt = NULL; + } else + *m0 = NULL; + DUMMYNET_UNLOCK(); + if (head != NULL) + dummynet_send(head); + + return 0; dropit: io_pkt_drop++; @@ -1327,5 +1083,5 @@ dropit: DUMMYNET_UNLOCK(); FREE_PKT(m); *m0 = NULL; - return ((fs && (fs->flags_fs & DN_NOERROR)) ? 0 : ENOBUFS); + return ((fs && (fs->flags & DN_NOERROR)) ? 0 : ENOBUFS); } Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Thu Jan 7 22:59:08 2010 (r201761) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Thu Jan 7 23:17:48 2010 (r201762) @@ -107,7 +107,7 @@ static __inline void dn_free_pkts(struct } static void -free_pipe(struct dn_pipe *p) +free_pipe(struct new_pipe *p) { if (p->samples) free(p->samples, M_DUMMYNET); @@ -121,9 +121,10 @@ free_pipe(struct dn_pipe *p) * For the one in dn_pipe MUST also cleanup ready_heap... */ static void -purge_flow_set(struct dn_flow_set *fs, int all) +purge_flow_set(struct new_fs *fs, int all) { - struct dn_flow_queue *q, *qn; +#if 0 + struct new_queue *q, *qn; int i; DUMMYNET_LOCK_ASSERT(); @@ -148,6 +149,7 @@ purge_flow_set(struct dn_flow_set *fs, i if (fs->pipe == NULL || fs != &(fs->pipe->fs)) free(fs, M_DUMMYNET); } +#endif } /* @@ -156,9 +158,9 @@ purge_flow_set(struct dn_flow_set *fs, i * to be deleted. */ static void -purge_pipe(struct dn_pipe *pipe) +purge_pipe(struct new_pipe *pipe) { - +#if 0 purge_flow_set( &(pipe->fs), 1 ); dn_free_pkts(pipe->head); @@ -166,6 +168,7 @@ purge_pipe(struct dn_pipe *pipe) heap_free( pipe->scheduler_heap ); heap_free( pipe->not_eligible_heap ); heap_free( pipe->idle_heap ); +#endif } /* @@ -175,8 +178,8 @@ purge_pipe(struct dn_pipe *pipe) static void dummynet_flush(void) { - struct dn_pipe *pipe, *pipe1; - struct dn_flow_set *fs, *fs1; + struct new_pipe *pipe, *pipe1; + struct new_fs *fs, *fs1; int i; DUMMYNET_LOCK(); @@ -192,12 +195,12 @@ dummynet_flush(void) */ for (i = 0; i < DN_HASHSIZE; i++) SLIST_FOREACH_SAFE(fs, &flowsethash[i], next, fs1) { - SLIST_REMOVE(&flowsethash[i], fs, dn_flow_set, next); + SLIST_REMOVE(&flowsethash[i], fs, new_fs, next); purge_flow_set(fs, 1); } for (i = 0; i < DN_HASHSIZE; i++) SLIST_FOREACH_SAFE(pipe, &pipehash[i], next, pipe1) { - SLIST_REMOVE(&pipehash[i], pipe, dn_pipe, next); + SLIST_REMOVE(&pipehash[i], pipe, new_pipe, next); purge_pipe(pipe); free_pipe(pipe); } @@ -263,7 +266,8 @@ config_red(struct dn_flow_set *p, struct return (0); } -static int +int alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs); +int alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs) { if (x->flags_fs & DN_HAVE_FLOW_MASK) { /* allocate some slots */ @@ -288,7 +292,8 @@ alloc_hash(struct dn_flow_set *x, struct return 0 ; } -static void +void set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src); +void set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src) { x->flags_fs = src->flags_fs; @@ -333,6 +338,7 @@ do_config(void *p, int l) static int config_pipe(struct dn_pipe *p) { +#if 0 struct dn_flow_set *pfs = &(p->fs); *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***