Date: Tue, 12 Jan 2010 13:45:40 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r202151 - user/luigi/ipfw3-head/sys/netinet/ipfw Message-ID: <201001121345.o0CDjeFZ002493@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: luigi Date: Tue Jan 12 13:45:40 2010 New Revision: 202151 URL: http://svn.freebsd.org/changeset/base/202151 Log: save snapshot Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 12 13:45:40 2010 (r202151) @@ -303,14 +303,16 @@ heap_free(struct dn_heap *h) */ struct dn_ht * dn_ht_init(struct dn_ht *ht, int buckets, int ofs, - int (*h)(void *, uintptr_t arg), - int (*match)(void *, void *, uintptr_t arg), - void *(*new)(void *, uintptr_t arg), uintptr_t arg) + int (*h)(uintptr_t, int, void *), + int (*match)(void *, uintptr_t, int, void *), + void *(*new)(uintptr_t, int, void *), void *arg) { int l; - if (h == NULL) + if (h == NULL || match == NULL) { + printf("missing hash or match function"); return NULL; + } if (buckets < 1 || buckets > 65536) return NULL; if (ht) { /* see if we can reuse */ @@ -340,21 +342,29 @@ dn_ht_init(struct dn_ht *ht, int buckets return ht; } -/* lookup and optionally create element */ +/* lookup and optionally create or delete element */ void * -dn_ht_find(struct dn_ht *ht, void *key, int create) +dn_ht_find(struct dn_ht *ht, uintptr_t key, int flags) { int i; - void *p; + void **pp, *p; - i = (ht->buckets == 1) ? 0 : ht->hash(key, ht->arg) % ht->buckets; + i = (ht->buckets == 1) ? 0 : + (ht->hash(key, flags, ht->arg) % ht->buckets); // log(1, "find %p in bucket %d\n", obj, i); - for (p = ht->ht[i]; p; p = *(void **)((char *)p + ht->ofs)) { - if (ht->match(p, key, ht->arg)) + for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) { + if (ht->match(p, key, flags, ht->arg)) break; } - if (p == NULL && create) { - p = ht->new ? ht->new(key, ht->arg) : key; + if (p) { + if (flags & DNHT_REMOVE) { + /* link in the next element */ + *pp = *(void **)((char *)p + ht->ofs); + *(void **)((char *)p + ht->ofs) = NULL; + ht->entries--; + } + } else if (flags & DNHT_INSERT) { + p = ht->new ? ht->new(key, flags, ht->arg) : (void *)key; if (p) { ht->entries++; *(void **)((char *)p + ht->ofs) = ht->ht[i]; @@ -365,7 +375,7 @@ dn_ht_find(struct dn_ht *ht, void *key, } int -dn_ht_scan(struct dn_ht *ht, int (*fn)(void *, uintptr_t), uintptr_t arg) +dn_ht_scan(struct dn_ht *ht, int (*fn)(void *, void *), void *arg) { int i, ret, found = 0; void *p, **prev; @@ -387,30 +397,6 @@ dn_ht_scan(struct dn_ht *ht, int (*fn)(v return found; } -/* - * remove obj from the table, using key to find the slot. - * Returns obj if found, NULL if not found - */ -void * -dn_ht_remove(struct dn_ht *ht, void *obj, void *key) -{ - int i; - void **pp, *p; - - i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets; - // log(1, "find %p in bucket %d\n", obj, i); - for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) { - if (p != obj) - continue; - /* link in the next element */ - *pp = *(void **)((char *)p + ht->ofs); - *(void **)((char *)p + ht->ofs) = NULL; - ht->entries--; - return obj; - } - return NULL; /* failed */ -} - #ifndef _KERNEL /* * testing code for the heap and hash table @@ -422,30 +408,23 @@ struct x { char buf[0]; }; -int hfn1(void *_x, uintptr_t arg) +int hf(uintptr_t key, int flags, void *arg) { - return *(char *)_x; -} -int matchfn1(void *_x, void *_obj, uintptr_t arg) -{ - return (strcmp(((struct x *)_x)->buf, _obj) == 0); + return (flags & DNHT_KEY_IS_OBJ) ? + ((struct x *)key)->buf[0] : *(char *)key; } -int hfn2(void *_x, uintptr_t arg) +int matchf(void *obj, uintptr_t key, int flags, void *arg) { - return ((struct x *)_x)->buf[0]; -} -int matchfn2(void *_x, void *_obj, uintptr_t arg) -{ - return (strcmp(((struct x *)_x)->buf, - ((struct x *)_obj)->buf) == 0); + char *s = (flags & DNHT_KEY_IS_OBJ) ? + ((struct x *)key)->buf : (char *)key; + return (strcmp(((struct x *)obj)->buf, s) == 0); } -void *newfn(void *_x, uintptr_t arg) +void *newfn(uintptr_t key, int flags, void *arg) { - char *s = _x; - struct x *p = malloc(sizeof(*p) + 1 + strlen(s), - M_DN_HEAP, 0); + char *s = (char *)key; + struct x *p = malloc(sizeof(*p) + 1 + strlen(s), M_DN_HEAP, 0); if (p) strcpy(p->buf, s); return p; @@ -470,26 +449,37 @@ test_hash() { char **p; struct dn_ht *h; - void *x = NULL; + uintptr_t x = 0; + uintptr_t x1 = 0; /* first, find and allocate */ - h = dn_ht_init(NULL, 10, 0, hfn1, matchfn1, newfn, 0); + h = dn_ht_init(NULL, 10, 0, hf, matchf, newfn, 0); for (p = strings; *p; p++) { - dn_ht_find(h, *p, 1); + dn_ht_find(h, (uintptr_t)*p, DNHT_INSERT); } dn_ht_scan(h, doprint, 0); printf("/* second -- find without allocate */\n"); - h = dn_ht_init(NULL, 10, 0, hfn2, matchfn2, NULL, 0); + h = dn_ht_init(NULL, 10, 0, hf, matchf, NULL, 0); for (p = strings; *p; p++) { - void **y = newfn(*p, 0); - if (x == NULL) - x = y; - dn_ht_find(h, y, 1); + void **y = newfn((uintptr_t)*p, 0, NULL); + if (x == 0) + x = (uintptr_t)y; + else { + if (x1 == 0) + x1 = (uintptr_t)*p; + } + dn_ht_find(h, (uintptr_t)y, DNHT_INSERT | DNHT_KEY_IS_OBJ); } dn_ht_scan(h, doprint, 0); - printf("remove %p gives %p\n", x, dn_ht_remove(h, x, x)); - printf("remove %p gives %p\n", x, dn_ht_remove(h, x, x)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x1, DNHT_REMOVE)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x1, DNHT_REMOVE)); dn_ht_scan(h, doprint, 0); } Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 12 13:45:40 2010 (r202151) @@ -88,27 +88,32 @@ struct dn_ht { int buckets; /* how many buckets */ int entries; /* how many entries */ int ofs; /* offset of link field */ - uintptr_t arg; /* arg to hash function */ - int (*hash)(void *, uintptr_t arg); - int (*match)(void *, void *, uintptr_t arg); - void *(*new)(void *, uintptr_t arg); /* object create function */ + void *arg; /* argument to the three functions */ + int (*hash)(uintptr_t, int, void *arg); + int (*match)(void *_el, uintptr_t key, int, void *); + void *(*new)(uintptr_t, int, void *); void **ht; /* bucket heads */ }; struct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs, - int (*h)(void *, uintptr_t arg), - int (*match)(void *, void *, uintptr_t arg), - void *(*new)(void *, uintptr_t arg), - uintptr_t arg); + int (*hash)(uintptr_t, int, void *), + int (*match)(void *, uintptr_t, int, void *), + void *(*new)(uintptr_t, int, void *), void *arg); -/* lookup and optionally create element */ -void *dn_ht_find(struct dn_ht *, void *key, int create); -void *dn_ht_remove(struct dn_ht *, void *obj, void *key); +/* lookup and optionally create or remove element. Flags described below */ +void *dn_ht_find(struct dn_ht *, uintptr_t key, int flags); -enum { - DN_HT_SCAN_DEL = 1, - DN_HT_SCAN_END = 2, +enum { /* flags values. + * first two are returned by the scan callback to indicate + * to delete the matching element or to end the scan + */ + DNHT_SCAN_DEL = 0x0001, + DNHT_SCAN_END = 0x0002, + DNHT_KEY_IS_OBJ = 0x0004, /* key is the obj pointer */ + DNHT_INSERT = 0x0008, /* insert if not found */ + DNHT_UNIQUE = 0x0010, /* report error if already there */ + DNHT_REMOVE = 0x0020, /* remove on find */ }; -int dn_ht_scan(struct dn_ht *, int (*)(void *, uintptr_t), uintptr_t); +int dn_ht_scan(struct dn_ht *, int (*)(void *, void *), void *); #endif /* _IP_DN_HEAP_H */ Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Tue Jan 12 13:45:40 2010 (r202151) @@ -115,8 +115,8 @@ 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)(struct new_sch_inst *, struct new_fsk *, - struct mbuf *, struct ipfw_flow_id *); + int (*enqueue)(struct new_sch_inst *, struct new_queue *, + struct mbuf *); struct mbuf * (*dequeue)(struct new_sch_inst *); /* config or destroy the scheduler template */ Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Tue Jan 12 13:45:40 2010 (r202151) @@ -61,43 +61,11 @@ struct fifo_si { }; static int -fifo_enqueue(struct new_sch_inst *_si, struct new_fsk *f, - struct mbuf *m, struct ipfw_flow_id *id) +fifo_enqueue(struct new_sch_inst *_si, struct new_queue *q, struct mbuf *m) { - /* - * The system pass to the enqueue() function 4 parameters: - * - s: scheduler instance which the packet belongs - * - f: flowset scheduler private data - * - m: the packet - * - id: flow id of the packet, the mask is applyed by system - * - * The scheduler should save all data needs into variables in the - * scheduler instance. In the FIFO scheduling algorithm there is only - * one queue, so a queue should be saved in the scheduler instance. - * When the first packet arrives, the queue doesn't exist and the - * scheduler must create it calling the dn_create_queue() function. - * To really enqueue the packet, the scheduler must call the - * dn_queue_packet() function that insert the packet in the queue passes. - * If for some reason (for example the queue is full) the packet can't - * be enqueued, dn_queue_packet() returns 1. - * - * See the enqueue() function for wf2q+ scheduler algorithm for - * another examples of enqueue() - */ - - /* Access to specific scheduler instance data */ - struct fifo_si *si = (struct fifo_si *)(_si+1); - - if (si->q == NULL) { - si->q = dn_create_queue(_si, f, id); - if (si->q == NULL) { - printf("%s dn_create_queue failed\n", __FUNCTION__); - FREE_PKT(m); - return 1; - } - } - /* Now the si->q is valid, so insert the packet in this queue */ - if (dn_queue_packet(si->q, m)) { + /* the queue is actually embedded here */ + q = (struct new_queue *)(_si+1); + if (dn_queue_packet(q, m)) { printf("%s dn_queue_packet failed\n", __FUNCTION__); /* packet was dropped */ return 1; @@ -138,9 +106,9 @@ static int fifo_new_sched(struct new_schk *s, struct new_sch_inst *_si) { /* This scheduler instance only has a queue pointer. */ - struct fifo_si *si = (struct fifo_si *)(_si + 1); + struct new_queue *q = (struct new_queue *)(_si + 1); - si->q = NULL; + q->si = _si; return 0; } @@ -154,8 +122,7 @@ static struct dn_sched fifo_desc = { .type = DN_SCHED_FIFO, .name = "FIFO", - .sch_inst_len = sizeof(struct fifo_si), - .queue_len = sizeof(struct new_queue), + .sch_inst_len = sizeof(struct new_queue), .enqueue = fifo_enqueue, .dequeue = fifo_dequeue, Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Tue Jan 12 13:45:40 2010 (r202151) @@ -62,42 +62,12 @@ struct fifo_si { }; static int -fifo_enqueue(struct new_sch_inst *_si, struct new_fsk *f, - struct mbuf *m, struct ipfw_flow_id *id) +fifo_enqueue(struct new_sch_inst *_si, struct new_queue *q, struct mbuf *m) { - /* - * The system pass to the enqueue() function 4 parameters: - * - s: scheduler instance which the packet belongs - * - f: flowset scheduler private data - * - m: the packet - * - id: flow id of the packet, the mask is applyed by system - * - * The scheduler should save all data needs into variables in the - * scheduler instance. In the FIFO scheduling algorithm there is only - * one queue, so a queue should be saved in the scheduler instance. - * When the first packet arrives, the queue doesn't exist and the - * scheduler must create it calling the dn_create_queue() function. - * To really enqueue the packet, the scheduler must call the - * dn_queue_packet() function that insert the packet in the queue passes. - * If for some reason (for example the queue is full) the packet can't - * be enqueued, dn_queue_packet() returns 1. - * - * See the enqueue() function for wf2q+ scheduler algorithm for - * another examples of enqueue() - */ - - /* Access to specific scheduler instance data */ - struct fifo_si *si = (struct fifo_si *)(_si+1); - - if (si->q == NULL) { - si->q = dn_create_queue(_si, f, id); - if (si->q == NULL) { - FREE_PKT(m); - return 1; - } - } - /* Now the si->q is valid, so insert the packet in this queue */ - if (dn_queue_packet(si->q, m)) { + /* the queue is actually embedded here */ + q = (struct new_queue *)(_si+1); + if (dn_queue_packet(q, m)) { + printf("%s dn_queue_packet failed\n", __FUNCTION__); /* packet was dropped */ return 1; } @@ -137,14 +107,14 @@ static int fifo_new_sched(struct new_schk *s, struct new_sch_inst *_si) { /* This scheduler instance only has a queue pointer. */ - struct fifo_si *si = (struct fifo_si *)(_si + 1); + struct new_queue *q = (struct new_queue *)(_si + 1); - si->q = NULL; + q->si = _si; return 0; } /* - * WF2Q(fake) scheduler descriptor + * FIFO 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 @@ -153,8 +123,7 @@ static struct dn_sched fifo_desc = { .type = DN_SCHED_WF2QP, .name = "WF2Q+", - .sch_inst_len = sizeof(struct fifo_si), - .queue_len = sizeof(struct new_queue), + .sch_inst_len = sizeof(struct new_queue), .enqueue = fifo_enqueue, .dequeue = fifo_dequeue, Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Tue Jan 12 13:45:40 2010 (r202151) @@ -84,7 +84,7 @@ struct dn_parms dn_cfg = { .red_lookup_depth = 256, /* RED - default lookup table depth */ .red_avg_pkt_size = 512, /* RED - default medium packet size */ .red_max_pkt_size = 1500, /* RED - default max packet size */ - .hmask = (1<<4) - 1, + .buckets = 16, }; static long tick_last; /* Last tick duration (usec). */ @@ -320,189 +320,8 @@ extra_bits(struct mbuf *m, struct new_pi return bits; } -/* Do masking depending of flow id */ -static 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; -} - -/* - * Calculate the hash of a flow id. - * XXX we may want a better hash function - */ -static int -do_hash(struct ipfw_flow_id *id) -{ - int i; - int is_v6 = IS_IP6_FLOW_ID(id); - - if (is_v6) { - uint32_t *d = (uint32_t *)&id->dst_ip6; - uint32_t *s = (uint32_t *)&id->src_ip6; - i = (d[0] & 0xffff)^ - (d[1] & 0xffff)^ - (d[2] & 0xffff)^ - (d[3] & 0xffff)^ - - ((d[0] >> 15) & 0xffff)^ - ((d[1] >> 15) & 0xffff)^ - ((d[2] >> 15) & 0xffff)^ - ((d[3] >> 15) & 0xffff)^ - - ((s[0] << 1) & 0xfffff)^ - ((s[1] << 1) & 0xfffff)^ - ((s[2] << 1) & 0xfffff)^ - ((s[3] << 1) & 0xfffff)^ - - ((s[0] << 16) & 0xffff)^ - ((s[1] << 16) & 0xffff)^ - ((s[2] << 16) & 0xffff)^ - ((s[3] << 16) & 0xffff)^ - - (id->dst_port << 1) ^ (id->src_port) ^ - (id->proto ) ^ - (id->flow_id6); - } else { - i = ( (id->dst_ip) & 0xffff ) ^ - ( (id->dst_ip >> 15) & 0xffff ) ^ - ( (id->src_ip << 1) & 0xffff ) ^ - ( (id->src_ip >> 16 ) & 0xffff ) ^ - (id->dst_port << 1) ^ (id->src_port) ^ - (id->proto ); - } - return i; -} - -/* - * Like bcmp, returns 0 if ids match, 1 otherwise. - */ -static int -flow_id_cmp(struct ipfw_flow_id *id1, struct ipfw_flow_id *id2) -{ - int is_v6 = IS_IP6_FLOW_ID(id1); - if (is_v6 != IS_IP6_FLOW_ID(id2)) - return 1; /* a ipv4 and a ipv6 flow */ - - if (!is_v6 && id1->dst_ip == id2->dst_ip && - id1->src_ip == id2->src_ip && - id1->dst_port == id2->dst_port && - id1->src_port == id2->src_port && - id1->proto == id2->proto && - id1->flags == id2->flags) - return 0; - - if (is_v6 && - !bcmp(&id1->dst_ip6,&id2->dst_ip6, sizeof(id1->dst_ip6)) && - !bcmp(&id1->src_ip6,&id2->src_ip6, sizeof(id1->src_ip6)) && - id1->dst_port == id2->dst_port && - id1->src_port == id2->src_port && - id1->proto == id2->proto && - id1->flags == id2->flags && - id1->flow_id6 == id2->flow_id6) - return 0; - - /* Masks differ */ - return 1; -} - -/* - * Create a new scheduler instance for the scheduler 'sch_t'. - * Allocate memory for instance, delay line and scheduler private data. - */ -static struct new_sch_inst * -create_si(struct new_schk *s, int slot) -{ - struct new_sch_inst *si; - int ret; - int l = sizeof(*si) + s->fp->sch_inst_len; - - si = malloc(l, M_DUMMYNET, M_NOWAIT | M_ZERO); - if (si == NULL) - goto error; - /* XXX note we set the length only for the initial part which - * is passed up to userland. - */ - set_oid(&si->ni.oid, DN_SCH_I, 0, sizeof(struct new_inst)); - set_oid(&(si->dline.oid), DN_DELAY_LINE, 0, sizeof(struct delay_line)); - si->ni.oid.id = si->dline.oid.id = -1; /* mark outside scheduler */ - - si->sched = s; - si->dline.si = si; - - if (s->fp->new_sched) { - ret = s->fp->new_sched(s, si); - if (ret) { - printf("%s: new_sched error %d\n", __FUNCTION__, ret); - goto error; - } - } - - /* Initialize list of queues attached here */ - SLIST_INIT(&si->ql_list); - - /* Put entry in front of the hash list of the parent. */ - SLIST_INSERT_HEAD(&s->ht[slot], si, next); - si->ni.hash_slot = slot; - dn_cfg.si_count++; - return si; - -error: - if (si) - free(si, M_DUMMYNET); - return NULL; -} - -/* - * Find the scheduler instance for this packet. If we need to apply - * a mask, do on a local copy of the flow_id to preserve the original. - */ -static struct new_sch_inst * -find_sch_inst(struct new_schk *s, struct ipfw_flow_id *id) -{ - struct new_sch_inst *si; - struct ipfw_flow_id id_t; - int i; - - if ( 0 == (s->sch.flags & DN_HAVE_MASK) ) { - i = 0; - si = SLIST_FIRST(&s->ht[0]); - } else { - id_t = *id; - do_mask(&s->sch.sched_mask, &id_t); - i = do_hash(&id_t); - i = i % s->ht_slots; - /* finally, scan the current hash bucket for a match */ - searches++; - SLIST_FOREACH(si, &s->ht[i], next) { - search_steps++; - if (!flow_id_cmp(&id_t, &si->ni.id)) - break; /* found */ - } - } - - if (si == NULL) { /* no match, allocate a new entry */ - si = create_si(s, i); - if (si && s->sch.flags & DN_HAVE_MASK) - si->ni.id = id_t; - } - return si; -} /* * Send traffic from a scheduler instance due by 'now'. @@ -731,12 +550,7 @@ dummynet_send(struct mbuf *m) struct new_fsk * ipdn_locate_flowset(int fs_nr) { - struct new_fsk *fs = NULL; - - SLIST_FOREACH(fs, &dn_cfg.fshash[HASH(fs_nr)], next) - if (fs->fs.fs_nr == fs_nr) - break; - return (fs); + return dn_ht_find(dn_cfg.fshash, fs_nr, 0); } static inline int @@ -777,6 +591,7 @@ dummynet_io(struct mbuf **m0, int dir, s struct mbuf *m = *m0; struct new_fsk *fs = NULL; struct new_sch_inst *si; + struct new_queue *q; dn_key now; /* save a copy of curr_time */ int fs_id = (fwa->rule.info & IPFW_INFO_MASK) + @@ -790,8 +605,8 @@ dummynet_io(struct mbuf **m0, int dir, s goto dropit; /* This queue/pipe does not exist! */ if (fs->sched == NULL) /* should not happen */ goto dropit; - /* find_sch_inst can be fast */ - si = find_sch_inst(fs->sched, &(fwa->f_id)); + /* dn_si_find can be fast */ + si = ipdn_si_find(fs->sched, &(fwa->f_id)); if (si == NULL) goto dropit; if (tag_mbuf(m, dir, fwa)) @@ -801,9 +616,15 @@ dummynet_io(struct mbuf **m0, int dir, s * call directly with NULL queue. Otherwise find a queue * and pass it. */ - if (fs->kflags & DN_HAVE_MASK) - do_mask(&fs->fs.flow_mask, &(fwa->f_id)); - if (fs->sched->fp->enqueue(si, fs, m, &(fwa->f_id))) { + if (fs->sched->fp->flags & DN_MULTIQUEUE) { + q = dn_ht_find(fs->qht, (uintptr_t)&(fwa->f_id), + DNHT_INSERT); + if (q == NULL) + goto dropit; + } else { + q = NULL; + } + if (fs->sched->fp->enqueue(si, q, m)) { printf("%s dropped by enqueue\n", __FUNCTION__); /* packet was dropped by enqueue() */ *m0 = NULL; Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h Tue Jan 12 13:45:40 2010 (r202151) @@ -77,11 +77,10 @@ struct dn_parms { int fsk_count; int queue_count; - int hmask; /* mask for hashsize, must be 2^n-1 */ - /* fhash and schedhash are hmask+1 entries */ - struct new_fsk_head fsunlinked; - struct new_fsk_head *fshash; - struct new_schk_head *schedhash; + int buckets; /* for the two hash tables */ + struct dn_ht *fshash; + struct dn_ht *schedhash; + struct new_fsk_head fsunlinked; /* use sch_chain */ }; static inline void @@ -111,7 +110,7 @@ struct delay_line { * The kernel side of a flowset. Contains: * - configuration parameters (fs, cmdline); * - kernel info (kflags) - * - link field for the hash chain (next) + * - link field for the hash chain * - reference to the scheduler; * - a refcount (from queues) * - link field for a list of fsk attached to sched (used when sched @@ -123,17 +122,20 @@ struct delay_line { */ struct new_fsk { /* kernel side of a flowset */ struct new_fs fs; - SLIST_ENTRY(new_fsk) next; /* hash chain list */ + SLIST_ENTRY(new_fsk) fsk_next; /* hash chain list */ int kflags; /* kernel-side flags */ /* * Scheduler-specific parameters for this flowset * (for examples, the weight parameter of wf2q+ algorithm goes here) */ - struct dn_id *cfg; + int weight; + int quantum; /* Number of queues attached to this flowset */ int refcnt; + /* hash table of queues, or just our queue if we have no mask */ + struct dn_ht *qht; /* Scheduler associated with this flowset */ struct new_schk *sched; SLIST_ENTRY(new_fsk) sch_chain; /* list of fsk attached to sched */ @@ -150,19 +152,14 @@ struct new_schk { * how many instances are in the heap and can be used * as a reference count. */ - SLIST_ENTRY(new_schk) next; /* List of all templates */ + SLIST_ENTRY(new_schk) schk_next; /* List of all templates */ struct new_fsk_head fsk_list; /* all fsk linked to me */ struct new_pipe pipe; /* the pipe is embedded */ struct dn_id *cfg; /* extra config arguments */ - /* Hash table contains all scheduler instances associated with - * this scheduler. We scan the list when we need to destroy - * the instances. - */ - int ht_slots; /* number of slots */ - struct new_sch_inst_head *ht; - struct new_sch_inst_head h0; /* used if malloc fails */ + /* Hash table of all children. Used to apply the sched_mask */ + struct dn_ht *siht; int kflags; @@ -189,7 +186,7 @@ SLIST_HEAD(new_queue_head, new_queue); */ struct new_sch_inst { struct new_inst ni; /* oid, id and stats */ - SLIST_ENTRY(new_sch_inst) next; /* next item in the bucket */ + SLIST_ENTRY(new_sch_inst) si_next; /* next item in the bucket */ struct delay_line dline; struct new_schk *sched; /* the template */ int kflags; /* DN_SCHED_ACTIVE */ @@ -224,5 +221,6 @@ dn_create_queue(struct new_sch_inst *si, struct ipfw_flow_id *id); +struct new_sch_inst *ipdn_si_find(struct new_schk *s, struct ipfw_flow_id *id); #endif /* _IP_DN_PRIVATE_H */ Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Tue Jan 12 11:11:25 2010 (r202150) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Tue Jan 12 13:45:40 2010 (r202151) @@ -67,7 +67,6 @@ static int ip_dn_ctl(struct sockopt *sop #define DN_C_FS 0x08 #define DN_C_QUEUE 0x10 - static int config_pipe(struct new_pipe *p, struct dn_id *arg); static int config_profile(struct new_profile *p, struct dn_id *arg); static int config_fs(struct new_fs *p, struct dn_id *arg); @@ -122,13 +121,152 @@ static __inline void dn_free_pkts(struct } } +/*---- flow_id mask, hash and compare functions ---*/ +static struct ipfw_flow_id * +flow_id_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; +} + +/* XXX we may want a better hash function */ +static int +flow_id_hash(struct ipfw_flow_id *id) +{ + int i; + int is_v6 = IS_IP6_FLOW_ID(id); + +#define M 0xffff + if (is_v6) { + uint32_t *d = (uint32_t *)&id->dst_ip6; + uint32_t *s = (uint32_t *)&id->src_ip6; + i = (d[0] & M) ^ (d[1] & M) ^ + (d[2] & M) ^ (d[3] & M) ^ + + ((d[0] >> 15) & M) ^ ((d[1] >> 15) & M) ^ + ((d[2] >> 15) & M) ^ ((d[3] >> 15) & M) ^ + + ((s[0] << 1) & M) ^ ((s[1] << 1) & M) ^ + ((s[2] << 1) & M) ^ ((s[3] << 1) & M) ^ + + ((s[0] << 16) & M) ^ ((s[1] << 16) & M) ^ + ((s[2] << 16) & M) ^ ((s[3] << 16) & M) ^ + + (id->dst_port << 1) ^ (id->src_port) ^ + (id->proto ) ^ (id->flow_id6); + } else { + i = ( (id->dst_ip) & M ) ^ + ( (id->dst_ip >> 15) & M ) ^ + ( (id->src_ip << 1) & M ) ^ + ( (id->src_ip >> 16 ) & M ) ^ + (id->dst_port << 1) ^ (id->src_port) ^ + (id->proto ); + } +#undef M + return i; +} + +/* Like bcmp, returns 0 if ids match, 1 otherwise. */ +static int +flow_id_cmp(struct ipfw_flow_id *id1, struct ipfw_flow_id *id2) +{ + int is_v6 = IS_IP6_FLOW_ID(id1); + if (is_v6 != IS_IP6_FLOW_ID(id2)) + return 1; /* a ipv4 and a ipv6 flow */ + + if (!is_v6 && id1->dst_ip == id2->dst_ip && + id1->src_ip == id2->src_ip && + id1->dst_port == id2->dst_port && + id1->src_port == id2->src_port && + id1->proto == id2->proto && + id1->flags == id2->flags) + return 0; + + if (is_v6 && + !bcmp(&id1->dst_ip6,&id2->dst_ip6, sizeof(id1->dst_ip6)) && + !bcmp(&id1->src_ip6,&id2->src_ip6, sizeof(id1->src_ip6)) && + id1->dst_port == id2->dst_port && + id1->src_port == id2->src_port && + id1->proto == id2->proto && + id1->flags == id2->flags && + id1->flow_id6 == id2->flow_id6) + return 0; + + /* Masks differ */ + return 1; +} + +/*--- support functions for the sch_inst hashtable ----*/ + /* - * Delete a scheduler instance and all the queues. - * Also remove from the heap. + * create a new instance for the given 'key' + * Allocate memory for instance, delay line and scheduler private data. + */ +static void * +si_new(uintptr_t key, int flags, void *arg) +{ + struct new_schk *s = arg; + struct new_sch_inst *si; + int l = sizeof(*si) + s->fp->sch_inst_len; + + si = malloc(l, M_DUMMYNET, M_NOWAIT | M_ZERO); + if (si == NULL) + goto error; + /* XXX note we set the length only for the initial part which + * is passed up to userland. + */ + set_oid(&si->ni.oid, DN_SCH_I, 0, sizeof(struct new_inst)); + set_oid(&(si->dline.oid), DN_DELAY_LINE, 0, sizeof(struct delay_line)); + si->ni.oid.id = si->dline.oid.id = -1; /* mark outside scheduler */ + + si->sched = s; + si->dline.si = si; + + if (s->fp->new_sched) { + int ret = s->fp->new_sched(s, si); + if (ret) { + printf("%s: new_sched error %d\n", __FUNCTION__, ret); + goto error; + } + } + + /* Initialize list of queues attached here */ + SLIST_INIT(&si->ql_list); + if (s->sch.flags & DN_HAVE_MASK) + si->ni.id = *(struct ipfw_flow_id *)key; + + dn_cfg.si_count++; + return si; + +error: + if (si) + free(si, M_DUMMYNET); + return NULL; +} + +/* + * Delete a scheduler instance and all the queues. This is a callback + * for the hashtable scan. + * Also remove from the system heap. */ static int -destroy_si(struct new_sch_inst *si) +si_destroy(void *_si, void *arg) { + struct new_sch_inst *si = _si; struct new_schk *s = si->sched; struct delay_line *dl = &si->dline; struct new_queue *q; @@ -150,24 +288,40 @@ destroy_si(struct new_sch_inst *si) } /* - * support to delete a flowset. - * if active (sched != NULL and ! DN_DELETE), put in the unlinked - * (otherwise it is already there). - * Then check refcnt and free when it becomes 0 + * Find the scheduler instance for this packet. If we need to apply + * a mask, do on a local copy of the flow_id to preserve the original. + */ +struct new_sch_inst * +ipdn_si_find(struct new_schk *s, struct ipfw_flow_id *id) +{ + struct new_sch_inst *si; + + if ( 0 == (s->sch.flags & DN_HAVE_MASK) ) { + if (s->siht == NULL) + s->siht = si_new((uintptr_t)id, 0, s); + si = (struct new_sch_inst *)s->siht; + } else { + struct ipfw_flow_id id_t = *id; + flow_id_mask(&s->sch.sched_mask, &id_t); + si = dn_ht_find(s->siht, (uintptr_t)&id_t, DNHT_INSERT); + } + return si; +} + +/*---- support functions for flowset hash table ----*/ +/* + * support to delete a flowset. Mark as delete, + * then check refcnt and free when it becomes 0 */ static void destroy_fs(struct new_fsk *fs) { struct new_schk *s = fs->sched; - if (fs->sched && (fs->kflags & DN_DELETE) == 0) { - SLIST_REMOVE(&dn_cfg.fshash[HASH(fs->fs.fs_nr)], - fs, new_fsk, next); - SLIST_INSERT_HEAD(&dn_cfg.fsunlinked, fs, next); - } fs->kflags |= DN_DELETE; if (fs->refcnt != 0) return; + fs->sched = NULL; dn_cfg.fsk_count--; SLIST_REMOVE(&s->fsk_list, fs, new_fsk, sch_chain); } @@ -177,9 +331,11 @@ create_fs(void) { struct new_fsk *fs; + // XXX we could use the hashtable support fs = malloc(sizeof(*fs), M_DUMMYNET, M_NOWAIT | M_ZERO); if (fs) { - SLIST_INSERT_HEAD(&dn_cfg.fsunlinked, fs, next); + dn_ht_find(dn_cfg.fshash, (uintptr_t)fs, + DNHT_KEY_IS_OBJ | DNHT_INSERT | DNHT_UNIQUE); dn_cfg.fsk_count++; } return fs; @@ -187,6 +343,7 @@ create_fs(void) /* * helper for schedulers. Creates a queue + * XXX actually, maybe only flowsets use this ? */ struct new_queue * dn_create_queue(struct new_sch_inst *si, struct new_fsk *fs, @@ -238,18 +395,9 @@ dn_delete_queue(struct new_queue *q, int static struct new_schk * destroy_schk(struct new_schk *s) { - int i; - struct new_sch_inst *si; struct dn_sched *fp = s->fp; -printf("%s slots %d\n", __FUNCTION__, s->ht_slots); - for (i = 0; i < s->ht_slots; i++) { - struct new_sch_inst_head *h = &s->ht[i]; - while ((si = SLIST_FIRST(h)) != NULL) { - SLIST_REMOVE_HEAD(h, next); - destroy_si(si); - } - } + dn_ht_scan(s->siht, si_destroy, NULL); if (fp->destroy) *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001121345.o0CDjeFZ002493>