From owner-svn-src-user@FreeBSD.ORG Fri Jan 8 14:55:10 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 ED4A2106566B; Fri, 8 Jan 2010 14:55:10 +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 DA5DB8FC16; Fri, 8 Jan 2010 14:55:10 +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 o08EtADV004331; Fri, 8 Jan 2010 14:55:10 GMT (envelope-from luigi@svn.freebsd.org) Received: (from luigi@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o08EtAHn004324; Fri, 8 Jan 2010 14:55:10 GMT (envelope-from luigi@svn.freebsd.org) Message-Id: <201001081455.o08EtAHn004324@svn.freebsd.org> From: Luigi Rizzo Date: Fri, 8 Jan 2010 14:55:10 +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: r201789 - in user/luigi/ipfw3-head: sbin/ipfw sys/netinet 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: Fri, 08 Jan 2010 14:55:11 -0000 Author: luigi Date: Fri Jan 8 14:55:10 2010 New Revision: 201789 URL: http://svn.freebsd.org/changeset/base/201789 Log: snapshot for today Modified: user/luigi/ipfw3-head/sbin/ipfw/dummynet.c user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h 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/sbin/ipfw/dummynet.c ============================================================================== --- user/luigi/ipfw3-head/sbin/ipfw/dummynet.c Fri Jan 8 14:33:03 2010 (r201788) +++ user/luigi/ipfw3-head/sbin/ipfw/dummynet.c Fri Jan 8 14:55:10 2010 (r201789) @@ -730,13 +730,13 @@ ipfw_config_pipe(int ac, char **av) char *end; void *par = NULL; struct dn_id *buf, *base; - struct new_sch *sch = NULL, *sch2 = NULL; + struct new_sch *sch = NULL; struct new_pipe *p = NULL; struct new_fs *fs = NULL; + struct new_profile *pf = NULL; struct ipfw_flow_id *mask = NULL; - int lmax = sizeof(*sch)*2 + sizeof(*p) + sizeof(*fs); + int lmax = sizeof(*sch) + sizeof(*p) + sizeof(*fs) + sizeof(*pf); -fprintf(stderr, "configuring %d\n", co.do_pipe); base = buf = calloc(1, lmax); if (buf == NULL) { errx(1, "no memory for pipe buffer"); @@ -752,27 +752,27 @@ fprintf(stderr, "configuring %d\n", co.d switch (co.do_pipe) { case 1: sch = o_next(&buf, sizeof(*sch), DN_SCH); - sch2 = o_next(&buf, sizeof(*sch2), DN_SCH); p = o_next(&buf, sizeof(*p), DN_PIPE); fs = o_next(&buf, sizeof(*fs), DN_FS); mask = &sch->sched_mask; // XXX or both ? - p->pipe_nr = i + DN_PIPEOFFSET; - fs->fs_nr = i; - fs->sched_nr = i; - sch->sched_nr = i; - sch2->sched_nr = i + DN_PIPEOFFSET; + sch->pipe_nr = p->pipe_nr = i; + fs->fs_nr = i + DN_PIPEOFFSET; + fs->sched_nr = sch->sched_nr = i + DN_PIPEOFFSET; break; + case 2: /* flowset */ fs = o_next(&buf, sizeof(*fs), DN_FS); fs->fs_nr = i; mask = &fs->flow_mask; break; + case 3: /* scheduler */ sch = o_next(&buf, sizeof(*sch), DN_SCH); sch->sched_nr = i; mask = &sch->sched_mask; // XXX or both ? break; } + while (ac > 0) { double d; int tok = match_token(dummynet_params, *av); @@ -1003,7 +1003,10 @@ end_mask: #if 0 case TOK_PIPE_PROFILE: + NEED((!pf), "profile already set"); + NEED(p, "profile"); { + pf = o_next(&buf, sizeof(*pf)); int samples[ED_MAX_SAMPLES_NO]; if (co.do_pipe != 1) errx(EX_DATAERR, "extra delay only valid for pipes"); @@ -1015,14 +1018,14 @@ end_mask: break; #endif case TOK_BURST: - NEED(sch, "burst"); + NEED(p, "burst"); NEED1("burst needs argument\n"); errno = 0; - if (expand_number(av[0], (int64_t *)&sch->burst) < 0) + if (expand_number(av[0], (int64_t *)&p->burst) < 0) if (errno != ERANGE) errx(EX_DATAERR, "burst: invalid argument"); - if (errno || sch->burst > (1ULL << 48) - 1) + if (errno || p->burst > (1ULL << 48) - 1) errx(EX_DATAERR, "burst: out of range (0..2^48-1)"); ac--; av++; Modified: user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h Fri Jan 8 14:33:03 2010 (r201788) +++ user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h Fri Jan 8 14:55:10 2010 (r201789) @@ -47,6 +47,7 @@ struct dn_id { uint8_t type; uint8_t subtype; uint32_t id; /* identifier in the sequence */ + struct dn_id *next; /* link field, for kernel */ }; /* @@ -90,15 +91,25 @@ enum sched_flag { DN_SCH_DELETE_DELAY_LINE = 0x0040, /* (k) */ }; -SLIST_HEAD(new_queue_head, new_queue); typedef uint64_t dn_key; +#define ED_MAX_SAMPLES_NO 1024 +struct new_profile { + struct dn_id oid; + /* fields to simulate a delay profile */ +#define ED_MAX_NAME_LEN 32 + char name[ED_MAX_NAME_LEN]; + int loss_level; + int samples_no; + int samples[ED_MAX_SAMPLES_NO]; /* this has actually samples_no slots */ +}; + /* Pipe template * All pipe are linked in a list, there is a 1-1 mapping between * 'ipfw pipe XX ...' commands and pipe XX */ struct new_pipe { - struct dn_id id; + struct dn_id oid; /* these initial fields are set from the command line * pipe N config bw B delay D profile PRF (mask M1 plr P queue Q @@ -112,6 +123,7 @@ struct new_pipe { int32_t pipe_nr ; /* N, number */ int bandwidth; /* B, really, bits/tick. */ int delay ; /* D, really, ticks */ + uint64_t burst; /* burst size, scaled. bits*Hz XXX */ /* * When the tx clock comes from an interface (if_name[0] != '\0'), @@ -119,18 +131,12 @@ struct new_pipe { */ char if_name[IFNAMSIZ]; - /* fields to simulate a delay profile */ -#define ED_MAX_NAME_LEN 32 - char name[ED_MAX_NAME_LEN]; - int loss_level; - int samples_no; - int user_samples[0]; /* this has actually samples_no slots */ + struct new_profile *profile; /* * The following parameters set at runtime and only valid * in the kernel. Userland should not look at these fields. */ - int *samples; /* pointer to memory for user_samples[] */ struct ifnet *ifp; int ready ; /* set if ifp != NULL and we got a signal from it */ @@ -141,7 +147,7 @@ struct new_pipe { * generic text string, in case we need one */ struct new_text { - struct dn_id id; + struct dn_id oid; int len; char text[0]; /* len bytes, NUL terminated */ }; @@ -153,7 +159,7 @@ struct new_text { * (plus there is a FIFO flowset for each pipe) */ struct new_fs { - struct dn_id id; + struct dn_id oid; /* these initial fields are set from the command line * queue N config mask M pipe P buckets B plr PLR queue QSZ ... @@ -181,11 +187,11 @@ struct new_fs { struct new_fs *confnext; /* DN_FS_DELETE - * DN_FS_REENQUEUE - * DN_HAVE_FLOW_MASK - * DN_QSIZE_IS_BYTES - * DN_NOERROR - */ + * DN_FS_REENQUEUE + * DN_HAVE_FLOW_MASK + * DN_QSIZE_IS_BYTES + * DN_NOERROR + */ int flags; /* Number of queues attached to this flowset */ @@ -197,8 +203,8 @@ struct new_fs { /* Scheduler associated with this flowset, set when the * scheduler for the pipe P is defined. */ - struct new_sch *ptr_sched; - int ptr_sched_val; /* to check if the pointer is correct */ + struct new_sch *sched; + int sched_id; /* to check if the pointer is correct */ /* * Pointer to scheduler-specific parameters for this flowset @@ -206,9 +212,42 @@ struct new_fs { */ struct dn_id *alg_fs; /* Pointer to scheduler functions */ - struct scheduler *fp; + struct dn_sched *fp; }; +/* Implementation of the packets queue associated with a scheduler instance */ +struct new_queue { + struct dn_id oid; + + /* Number and pointer to the parent flowset */ + int fs_nr; + struct new_fs *fs; + + u_int lenght; /* Queue lenght, in packets */ + u_int len_bytes; /* Queue lenght, in bytes */ + + uint64_t tot_pkts; /* statistics counters */ + uint64_t tot_bytes; + uint32_t drops; + + /* Used to print the id of the queue */ + int hash_slot; + + /* Pointer to the scheduler instance that the packet belongs */ + void *sch_inst; /* Pointer to scheduler specific data */ + + /* packets queue */ + struct mbuf *head, *tail; + + /* flow id associated with this queue */ + struct ipfw_flow_id id; + + struct new_queue *next; /* Next queue in the bucket */ + + /* Pointer to scheduler functions */ + struct dn_sched *fp; +}; +SLIST_HEAD(new_queue_head, new_queue); /* * Scheduler instance. * Contains variables and all queues relative to a this instance. @@ -221,7 +260,7 @@ struct new_sch_inst { /* Parent scheduler */ int sched_nr; - struct new_sch * ptr_sched; + struct new_sch *sched; int hash_slot; /* used to print the id of the scheduler instance */ @@ -250,14 +289,13 @@ struct new_sch_inst { * (plus there is a FIFO scheduler for each pipe) */ struct new_sch { - struct dn_id id; + struct dn_id oid; /* these initial fields are set from the command line * sched N config mask M ... */ int sched_nr; /* N, scheduler number */ - uint64_t burst; /* burst size, scaled. bits*Hz */ int bucket; /* number of buckets for the instances */ /* mask to select the appropriate scheduler instance */ @@ -281,7 +319,7 @@ struct new_sch { /* Pointer to the parent pipe */ int pipe_nr; - struct new_pipe *ptr_pipe; + struct new_pipe *pipe; /* Copy of command line */ #define DN_MAX_COMMAND 256 @@ -304,7 +342,7 @@ struct new_sch { int flags; /* Pointer to scheduler functions */ - struct scheduler *fp; + struct dn_sched *fp; /* Counter of packets pending to entering in this scheduler. * Used to avoid to delete the scheduler if some packets are in the mutex @@ -507,7 +545,6 @@ struct dn_flow_set { int avg_pkt_size ; /* medium packet size */ int max_pkt_size ; /* max packet size */ }; -SLIST_HEAD(dn_flow_set_head, dn_flow_set); struct dn_heap; /* @@ -567,15 +604,4 @@ struct dn_pipe { /* a pipe */ int *samples; }; -/* dn_pipe_max is used to pass pipe configuration from userland onto - * kernel space and back - */ -#define ED_MAX_SAMPLES_NO 1024 -struct dn_pipe_max { - struct dn_pipe pipe; - int samples[ED_MAX_SAMPLES_NO]; -}; - -SLIST_HEAD(dn_pipe_head, dn_pipe); - #endif /* _IP_DUMMYNET_H */ Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Fri Jan 8 14:33:03 2010 (r201788) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Fri Jan 8 14:55:10 2010 (r201789) @@ -120,10 +120,10 @@ struct dn_sched { int (*config)(char *command, void *sch, int reconfigure); int (*destroy)(void* sch); - int (*new_sched)(void *v); + int (*new_sched)(void *sch_priv, void *sch_t_priv); int (*free_sched)(void *s); - int (*new_fs)(char *command, struct dn_id *g, int reconfigure); + int (*new_fs)(void *command, struct dn_id *g, int reconfigure); int (*free_fs)(struct dn_id *f); int (*new_queue)(struct new_queue *q, struct dn_id *f); Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Fri Jan 8 14:33:03 2010 (r201788) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Fri Jan 8 14:55:10 2010 (r201789) @@ -88,7 +88,7 @@ struct dn_parms dn_cfg = { .red_max_pkt_size = 1500, /* RED - default max packet size */ }; -//static long tick_last; /* Last tick duration (usec). */ +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. */ @@ -133,6 +133,9 @@ MALLOC_DEFINE(M_DUMMYNET, "dummynet", "d struct new_pipe_head pipehash[DN_HASHSIZE]; /* all pipes */ struct new_fs_head flowsethash[DN_HASHSIZE]; /* all flowsets */ +struct new_sch_head schedulerhash[DN_HASHSIZE]; /* all schedulers */ +struct new_fs_head flowsetunlinked; /* all unlinked flowsets */ + extern void (*bridge_dn_p)(struct mbuf *, struct ifnet *); @@ -322,12 +325,13 @@ compute_extra_bits(struct mbuf *pkt, str { int index; dn_key extra_bits; + struct new_profile *pf = p->profile; - if (!p->samples || p->samples_no == 0) + if (!pf || pf->samples_no == 0) return 0; - index = random() % p->samples_no; - extra_bits = div64((dn_key)p->samples[index] * p->bandwidth, 1000); - if (index >= p->loss_level) { + index = random() % pf->samples_no; + extra_bits = div64((dn_key)pf->samples[index] * p->bandwidth, 1000); + if (index >= pf->loss_level) { struct dn_pkt_tag *dt = dn_tag_get(pkt); if (dt) dt->dn_dir = DIR_DROP; @@ -335,14 +339,14 @@ compute_extra_bits(struct mbuf *pkt, str return extra_bits; } -/* Insert packet pkt into delay line */ +/* Insert packet pkt into delay line, adding the delay. + * dt->output_time was already set */ static void -move_pkt(struct mbuf *pkt, struct new_pipe *p, struct delay_line *d, - dn_key l_curr_time) +move_pkt(struct mbuf *pkt, struct new_pipe *p, struct delay_line *d) { struct dn_pkt_tag *dt = dn_tag_get(pkt); - dt->output_time = l_curr_time + p->delay ; + dt->output_time += p->delay ; if (d->head == NULL) d->head = pkt; @@ -459,7 +463,7 @@ mask_are_equals (struct ipfw_flow_id *id * XXX why do we need separate delay lines ? */ static struct new_sch_inst * -create_scheduler_instance(struct new_sch *sch_t, dn_key l_curr_time) +create_scheduler_instance(struct new_sch *sch_t) { struct new_sch_inst *si; int ret; @@ -471,20 +475,13 @@ create_scheduler_instance(struct new_sch if (si == NULL) goto error; - si->dline = malloc(sizeof(struct delay_line), M_DUMMYNET, M_NOWAIT); - if (si->dline == NULL) - goto error; - si->dline->si = si; - set_oid(&si->dline->id, DN_DELAY_LINE, 0, sizeof(struct delay_line)); - si->dline->head = si->dline->tail = NULL; - set_oid(&si->oid, DN_SCH_I, 0, l); si->sched_nr = sch_t->sched_nr; - si->ptr_sched = sch_t; + si->sched = sch_t; /* XXX do we make assumption on this starting with dn_id ? */ - ret = sch_t->fp->new_sched((void *)(si + 1)); + ret = sch_t->fp->new_sched(si + 1, sch_t + 1); if (ret) { msg = "new_sched error"; goto error; @@ -493,9 +490,7 @@ create_scheduler_instance(struct new_sch /* Initialize scheduler instance queues list */ SLIST_INIT(&si->ql_list); - si->oid.subtype = ((struct dn_id*)(si + 1))->subtype; - ((struct dn_id*)(si + 1))->type = DN_SCH_I; - si->idle_time = l_curr_time; + si->idle_time = 0; return si; error: @@ -507,7 +502,7 @@ error: static 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) + struct ipfw_flow_id *id) { struct new_sch_inst *prev, *s; /* returning scheduler instance */ struct ipfw_flow_id *id_t; @@ -544,7 +539,7 @@ find_scheduler(struct new_sch *sch_t, st } if (s == NULL) { /* no match, need to allocate a new entry */ - s = create_scheduler_instance(sch_t, l_curr_time); + s = create_scheduler_instance(sch_t); if (s == NULL) return NULL; /* Link scheduler in front of array */ @@ -559,6 +554,63 @@ find_scheduler(struct new_sch *sch_t, st return s; } +/* + * Send traffic from a scheduler instance. + */ +static struct mbuf * +serve_sched(struct new_sch_inst *s, dn_key now) +{ + struct mbuf *head; + struct new_sch *sch_t = s->sched; + struct mbuf *tosend = NULL; + dn_key len_scaled; + struct new_pipe *pipe = sch_t->pipe; + int delay_line_idle = (s->dline->head == NULL); + int done; + s->flags &= ~DN_SCH_ACTIVE; + + if (pipe->bandwidth > 0) + s->numbytes += (now - s->sched_time) * pipe->bandwidth; + else + s->numbytes = 0; + s->sched_time = now; + done = 0; + while (s->numbytes >= 0 && (tosend = sch_t->fp->dequeue(s + 1)) != NULL) { + done++; + len_scaled = pipe->bandwidth ? tosend->m_pkthdr.len * 8 * hz + + compute_extra_bits(tosend, pipe) * hz : 0; + s->numbytes -= len_scaled; + /* Move packet in the delay line */ + move_pkt(tosend, pipe, s->dline); + } + if (done > 0 && s->numbytes < 0) { + /* credit has become negative, so reinsert the + * instance in the heap for when credit will be + * positive again. Also update the output time + * of the last packet, which is 'tosend' + */ + dn_key t = 0; + if (pipe->bandwidth > 0) + t = (pipe->bandwidth - 1 - s->numbytes) / pipe->bandwidth; + /* Delay the output time because under credit */ + dn_tag_get(tosend)->output_time += t; + + s->sched->inst_counter++; + s->flags |= DN_SCH_ACTIVE; + DN_HEAP_LOCK(); + heap_insert(system_heap, curr_time + t, s); + DN_HEAP_UNLOCK(); + } else { + /* scheduler instance should be idle, because it + * did not return packets while credit was available. + */ + s->idle_time = curr_time; + } + + head = (delay_line_idle && done) ? + transmit_event(s->dline, curr_time) : NULL; + return head; +} /* * The timer handler for dummynet. Time is computed in ticks, but @@ -568,21 +620,13 @@ find_scheduler(struct new_sch *sch_t, st void dummynet_task(void *context, int pending) { -#if 0 - struct mbuf *head = NULL, *tail = NULL; - struct new_pipe *pipe; - struct dn_heap *heaps[3]; - struct dn_heap *h; - void *p; /* generic parameter to handler */ - int i; + struct new_sch_inst *s; + struct new_sch *sch_t; + struct mbuf *head = NULL; struct timeval t; DUMMYNET_LOCK(); - heaps[0] = &ready_heap; /* fixed-rate queues */ - heaps[1] = &wfq_ready_heap; /* wfq queues */ - heaps[2] = &extract_heap; /* delay line */ - /* Update number of lost(coalesced) ticks. */ tick_lost += pending - 1; @@ -617,54 +661,82 @@ dummynet_task(void *context, int pending tick_delta_sum += tick; tick_adjustment++; } + DUMMYNET_UNLOCK(); + for (;;) { + struct dn_id *p; /* generic parameter to handler */ + DN_HEAP_LOCK(); + if (system_heap->elements > 0 && + DN_KEY_LEQ(HEAP_TOP(system_heap)->key, curr_time)) { + p = HEAP_TOP(system_heap)->object; + heap_extract(system_heap, NULL); + } else { + p = NULL; + } + DN_HEAP_UNLOCK(); + if (p == NULL) + break; - for (i = 0; i < 3; i++) { - h = heaps[i]; - while (h->elements > 0 && DN_KEY_LEQ(HEAP_TOP(h)->key, curr_time)) { - // XXX can this happen ? - if (HEAP_TOP(h)->key > curr_time) - printf("dummynet: warning, " - "heap %d is %d ticks late\n", - i, (int)(curr_time - HEAP_TOP(h)->key)); - /* store a copy before heap_extract */ - p = HEAP_TOP(h)->object; - /* need to extract before processing */ - heap_extract(h, NULL); - if (i == 0) - ready_event(p, &head, &tail); - else if (i == 1) { - struct dn_pipe *pipe = p; - if (pipe->if_name[0] != '\0') - printf("dummynet: bad ready_event_wfq " - "for pipe %s\n", pipe->if_name); - else - ready_event_wfq(p, &head, &tail); - } else - transmit_event(p, &head, &tail); + if (p->type == DN_SCH_I) { + /* + * Working with scheduler instances: + * - Remove a scheduler instance from the heap and decrement + * the scheduler counter. + * - If the scheduler is deleting and no other scheduler + * instances (of this scheduler) are into the heap, + * it's now possible to delete scheduler and call the + * function to do this; + * - If the scheduer is deleting and this isn't the last + * instance in the heap, don't call the dequeue() function + * so the instance isn't inserted in the heap + * - Else, call the dequeue() function. + */ + s = (struct new_sch_inst *)p; + sch_t = s->sched; + DN_S_LOCK(sch_t); + + sch_t->inst_counter--; + if (sch_t->flags & DN_SCH_DELETE) { + /* Wait for scheduler->busy == 0 */ + while(sch_t->busy) { /* XXX check */ + DN_S_UNLOCK(sch_t); + DN_S_LOCK(sch_t); + } + /* Scheduler is deleting, don't dequeue packets from + * this instance + */ + if (sch_t->inst_counter == 0) { + /* No other scheduler instance in the heap. + * We can safely delete scheduler + */ + really_deletescheduler(sch_t); + DN_S_UNLOCK(sch_t); /* XXX */ + } + } else { + head = serve_sched(s, curr_time); + DN_S_UNLOCK(sch_t); + if (head != NULL) + dummynet_send(head); } - } - - /* Sweep pipes trying to expire idle flow_queues. */ - for (i = 0; i < DN_HASHSIZE; i++) { - SLIST_FOREACH(pipe, &pipehash[i], next) { - if (pipe->idle_heap->elements > 0 && - DN_KEY_LT(HEAP_TOP(pipe->idle_heap)->key, pipe->V)) { - struct dn_flow_queue *q = - HEAP_TOP(pipe->idle_heap)->object; - - heap_extract(pipe->idle_heap, NULL); - /* Mark timestamp as invalid. */ - q->S = q->F + 1; - pipe->sum -= q->fs->weight; - } + } else { /* extracted a delay line */ + struct delay_line *dline = (struct delay_line *)p; + /* + * Managing delay lines. + * If the pointer to the scheduler instance is NULL, the delay + * line should be deleted because pipe or scheduler was deleted, + * else the transmit event is called to send out packets and + * eventually reinsert the delay line into the heap. + */ + if (dline->si == NULL) + delete_delay_line(dline); + else { + DN_S_LOCK(dline->si->ptr_sched); + head = transmit_event(dline, curr_time); + DN_S_UNLOCK(dline->si->ptr_sched); + if (head != NULL) + dummynet_send(head); } - } - - DUMMYNET_UNLOCK(); - - if (head != NULL) - dummynet_send(head); -#endif + } + } dn_reschedule(); } @@ -1047,19 +1119,6 @@ ipdn_locate_flowset(int fs_nr) return (NULL); } -struct new_pipe * -ipdn_locate_pipe(int pipe_nr) -{ - struct new_pipe *pipe; - - SLIST_FOREACH(pipe, &pipehash[HASH(pipe_nr)], next) - if (pipe->pipe_nr == pipe_nr) - return (pipe); - - return (NULL); -} - - /* * dummynet hook for packets. Below 'pipe' is a pipe or a queue * depending on whether WF2Q or fixed bw is used. @@ -1084,20 +1143,21 @@ dummynet_io(struct mbuf **m0, int dir, s struct new_fs *fs = NULL; struct new_pipe *pipe = NULL; struct new_queue *q = NULL; - int fs_id = fwa->rule.info & IPFW_INFO_MASK; 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 */ + dn_key now; /* save a copy of curr_time */ int delay_line_idle; - - if (fwa->rule.info & IPFW_IS_PIPE) - fs_id += DN_PIPEOFFSET; + int fs_id = (fwa->rule.info & IPFW_INFO_MASK) + + (fwa->rule.info & IPFW_IS_PIPE) ? DN_PIPEOFFSET : 0; KASSERT(m->m_nextpkt == NULL, ("dummynet_io: mbuf queue passed to dummynet")); + /* + * find flowset and schedset, protected by the UH lock + */ DUMMYNET_LOCK(); io_pkt++; fs = ipdn_locate_flowset(fs_id); @@ -1105,7 +1165,7 @@ dummynet_io(struct mbuf **m0, int dir, s if (fs == NULL) goto dropit; /* This queue/pipe does not exist! */ - if (fs->sched_id != dn_cfg.id) { + if (fs->sched_id != dn_cfg.id) { /* fs->sched invalid, update */ /* configuration changed, update */ int ret = dn_fs_config(fs); if (ret) @@ -1119,11 +1179,12 @@ dummynet_io(struct mbuf **m0, int dir, s if (sch == NULL) goto dropit; pipe = sch->pipe; - if (pipe == NULL) /* should not happen ? */ + if (pipe == NULL) { /* should not happen ? */ + printf("%s strange, scheduler without a pipe\n", __FUNCTION__); goto dropit; + } - l_curr_time = curr_time; - sch_inst = find_scheduler(sch, fs, &(fwa->f_id), l_curr_time); + sch_inst = find_scheduler(sch, fs, &(fwa->f_id)); if (sch_inst == NULL) goto dropit; dline = sch_inst->dline; @@ -1148,6 +1209,8 @@ dummynet_io(struct mbuf **m0, int dir, s pkt->rule.info &= IPFW_ONEPASS; /* only keep this info */ pkt->dn_dir = dir; pkt->ifp = fwa->oif; + now = curr_time; /* in case it changes, use the same value */ + pkt->output_time = now; /* XXX rewritten when reaches head */ /* * - 'sch_inst + 1' is the pointer to scheduler instance's @@ -1158,82 +1221,45 @@ dummynet_io(struct mbuf **m0, int dir, s * packet, it must call the queue_packet() */ - ret = sch->fp->enqueue( - (sch_inst + 1), fs->alg_fs, m, - &(fwa->f_id)); + 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; } - /* - * 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)) { + /* + * Now check if the dequeue should be called now. + * If the instance is in the heap, the dequeue() will be called later, + * and we are done. + */ + if (sch_inst->flags & DN_SCH_ACTIVE) + goto done; + // XXX see if we can merge with dummynet task. /* 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) * + sch_inst->numbytes = dn_cfg.io_fast ? pipe->bandwidth : 0; + if (pipe->burst) { + uint64_t burst = (now - 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->dline, 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 (burst > pipe->burst) + burst = pipe->burst; + sch_inst->numbytes += burst; } - } + head = serve_sched(sch_inst, now); - 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; + /* optimization -- pass it back to ipfw for immediate send */ + 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; + } +done: DUMMYNET_UNLOCK(); if (head != NULL) dummynet_send(head); Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Fri Jan 8 14:33:03 2010 (r201788) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Fri Jan 8 14:55:10 2010 (r201789) @@ -61,6 +61,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include //#include /* various ether_* routines */ @@ -72,6 +73,9 @@ static int ip_dn_ctl(struct sockopt *sop static struct callout dn_timeout; static struct task dn_task; static struct taskqueue *dn_tq = NULL; + +static struct dn_sched_head list_of_scheduler; + /* * This is called one tick, after previous run. It is used to * schedule next run. @@ -91,6 +95,23 @@ dn_reschedule(void) /* + * Return a scheduler descriptor given the type. + * If the descriptor isn't found, return NULL. This case shouldn't occur. + */ +static struct dn_sched * +load_scheduler(int type) +{ + struct dn_sched *d = NULL; + + SLIST_FOREACH(d, &list_of_scheduler, next) { + if (d->type == type) + return d; + } + + return NULL; /* error */ +} + +/* * Dispose a list of packet. Use an inline functions so if we * need to free extra state associated to a packet, this is a * central point to do it. @@ -106,11 +127,71 @@ static __inline void dn_free_pkts(struct } } +int +delete_delay_line(struct delay_line *dline) +{ + struct mbuf *m; + + m = dline->head; + dn_free_pkts(m); + free(dline, M_DUMMYNET); + return 0; +} + +static int +delete_scheduler_instance(struct new_sch_inst *si) +{ + struct new_sch *sch_t = si->sched; + + sch_t->fp->free_sched(si + 1); + /* XXX packet from delay line must be freed */ + if (si->dline->head == NULL || sch_t->flags & DN_SCH_DELETE_DELAY_LINE) { + /* Delay line empty, or forced delete, so delete delay line now */ + delete_delay_line(si->dline); + } else { + /* Packet in delay line, will be removed when extracted from heap */ + si->dline->si = NULL; + } + free(si, M_DUMMYNET); + return 0; +} + +/* + * Called when no scheduler instances are in the heap, so it's safe + * to remove the scheduler template, scheduler hash table and scheduler + * instances + */ +int +really_deletescheduler(struct new_sch *sch_t) +{ + int i; + struct new_sch_inst *si, *sid; + + /* XXX checks, maybe all scheduler instance are deleted before */ + for (i = 0; i < sch_t->sch_i_size; i++) { + si = sch_t->sch_i[i]; + while (si) { + sid = si; + si = si->next; + /* remove scheduler instance */ + delete_scheduler_instance(sid); + } + } + sch_t->fp->free_sched(sch_t + 1); + sch_t->fp->ref_count--; + DN_S_LOCK_DESTROY(sch_t); + if (sch_t->sch_i_size > 0) + free(sch_t->sch_i, M_DUMMYNET); + free(sch_t, M_DUMMYNET); + return 0; +} + + static void free_pipe(struct new_pipe *p) { - if (p->samples) - free(p->samples, M_DUMMYNET); + if (p->profile) + free(p->profile, M_DUMMYNET); free(p, M_DUMMYNET); } @@ -322,6 +403,242 @@ do_config(void *p, int l) return 0; } +static struct new_sch * +locate_scheduler(int sch_nr) +{ + struct new_sch *sch; + + SLIST_FOREACH(sch, &schedulerhash[HASH(sch_nr)], next) + if (sch->sched_nr == sch_nr) + return (sch); + + return (NULL); +} + +static struct new_pipe * +locate_pipe(int pipe_nr) +{ + struct new_pipe *pipe; + + SLIST_FOREACH(pipe, &pipehash[HASH(pipe_nr)], next) + if (pipe->pipe_nr == pipe_nr) + return (pipe); + + return (NULL); +} + +/* + * Starting from a flow set, check if pointers are ok. + * First, check if the scheduler exist and eventually if the pipe exists. + * If the scheduler is NULL, the flowset should be inserted in the unlinked + * flowset list and removed from flowset list. So new packet are discarded + * when they arrives, and this flowset become of general type and can be *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***