svn commit: r202151 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Tue Jan 12 13:45:40 UTC 2010
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 ***
More information about the svn-src-user
mailing list