svn commit: r202186 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Wed Jan 13 12:21:59 UTC 2010
Author: luigi
Date: Wed Jan 13 12:21:58 2010
New Revision: 202186
URL: http://svn.freebsd.org/changeset/base/202186
Log:
some documentation and API fixes
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 Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Wed Jan 13 12:21:58 2010 (r202186)
@@ -71,8 +71,8 @@ MALLOC_DEFINE(M_DN_HEAP, "dummynet", "du
#define HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; }
#define HEAP_INCREMENT 15
-int
-heap_init(struct dn_heap *h, int new_size)
+static int
+heap_resize(struct dn_heap *h, int new_size)
{
struct dn_heap_entry *p;
@@ -96,6 +96,16 @@ heap_init(struct dn_heap *h, int new_siz
return 0;
}
+int
+heap_init(struct dn_heap *h, int size, int ofs)
+{
+ if (heap_resize(h, size))
+ return 1;
+ h->elements = 0;
+ h->ofs = ofs;
+ return 0;
+}
+
/*
* Insert element in heap. Normally, p != NULL, we insert p in
* a new position and bubble up. If p == NULL, then the element is
@@ -106,16 +116,18 @@ heap_init(struct dn_heap *h, int new_siz
* If ofs > 0 the position (index, int) of the element in the heap is
* also stored in the element itself at the given offset in bytes.
*/
-#define SET_OFFSET(heap, node) \
- if (heap->ofs > 0) \
- *((int *)((char *)(heap->p[node].object) + heap->ofs)) = node;
+#define SET_OFFSET(h, i) do { \
+ if (h->ofs > 0) \
+ *((int32_t *)((char *)(h->p[i].object) + h->ofs)) = i; \
+ } while (0)
/*
* RESET_OFFSET is used for sanity checks. It sets ofs
* to an invalid value.
*/
-#define RESET_OFFSET(heap, node) \
- if (heap->ofs > 0) \
- *((int *)((char *)(heap->p[node].object) + heap->ofs)) = -1;
+#define RESET_OFFSET(h, i) do { \
+ if (h->ofs > 0) \
+ *((int32_t *)((char *)(h->p[i].object) + h->ofs)) = -1; \
+ } while (0)
int
heap_insert(struct dn_heap *h, uint64_t key1, void *p)
@@ -123,12 +135,13 @@ heap_insert(struct dn_heap *h, uint64_t
int son = h->elements;
//log("%s key %llu p %p\n", __FUNCTION__, key1, p);
- if (p == NULL) /* data already there, set starting point */
+ if (p == NULL) { /* data already there, set starting point */
son = key1;
- else {/* insert new element at the end, possibly resize */
+ } else { /* insert new element at the end, possibly resize */
son = h->elements;
if (son == h->size) /* need resize... */
- if (heap_init(h, h->elements+1) )
+ // XXX expand by 16 or so
+ if (heap_resize(h, h->elements+16) )
return 1; /* failure... */
h->p[son].object = p;
h->p[son].key = key1;
@@ -170,7 +183,7 @@ heap_extract(struct dn_heap *h, void *ob
__FUNCTION__, h);
father = *((int *)((char *)obj + h->ofs));
if (father < 0 || father >= h->elements) {
- panic("%s: heap_extract, father %d out of bound 0..%d\n",
+ panic("%s: father %d out of bound 0..%d\n",
__FUNCTION__, father, h->elements);
}
}
@@ -208,33 +221,32 @@ heap_extract(struct dn_heap *h, void *ob
static void
heap_move(struct dn_heap *h, uint64_t new_key, void *object)
{
- int temp;
- int i;
- int max = h->elements-1;
- struct dn_heap_entry buf;
+ int temp, i, max = h->elements-1;
+ struct dn_heap_entry *p, buf;
if (h->ofs <= 0)
panic("cannot move items on this heap");
+ p = h->p; /* shortcut */
i = *((int *)((char *)object + h->ofs));
- if (DN_KEY_LT(new_key, h->p[i].key) ) { /* must move up */
- h->p[i].key = new_key;
+ if (DN_KEY_LT(new_key, p[i].key) ) { /* must move up */
+ p[i].key = new_key;
for (; i>0 &&
- DN_KEY_LT(new_key, h->p[(temp = HEAP_FATHER(i))].key);
+ DN_KEY_LT(new_key, p[(temp = HEAP_FATHER(i))].key);
i = temp ) { /* bubble up */
- HEAP_SWAP(h->p[i], h->p[temp], buf);
+ HEAP_SWAP(p[i], p[temp], buf);
SET_OFFSET(h, i);
}
} else { /* must move down */
- h->p[i].key = new_key;
+ p[i].key = new_key;
while ( (temp = HEAP_LEFT(i)) <= max ) {
/* found left child */
- if ((temp != max) &&
- DN_KEY_GT(h->p[temp].key, h->p[temp+1].key))
+ if (temp != max &&
+ DN_KEY_LT(p[temp+1].key, p[temp].key))
temp++; /* select child with min key */
- if (DN_KEY_GT(new_key, h->p[temp].key)) {
+ if (DN_KEY_LT(>p[temp].key, new_key)) {
/* go down */
- HEAP_SWAP(h->p[i], h->p[temp], buf);
+ HEAP_SWAP(p[i], p[temp], buf);
SET_OFFSET(h, i);
} else
break;
@@ -295,6 +307,16 @@ heap_free(struct dn_heap *h)
* hash table support.
*/
+struct dn_ht {
+ int buckets; /* how many buckets */
+ int entries; /* how many entries */
+ int ofs; /* offset of link field */
+ 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 */
+};
/*
* Initialize, allocating bucket pointers inline.
* Recycle previous record if possible.
@@ -343,6 +365,16 @@ dn_ht_init(struct dn_ht *ht, int buckets
return ht;
}
+void
+dn_ht_free(struct dn_ht *ht, int flags)
+{
+ if (ht == NULL)
+ return;
+ if (ht->ht && ht->ht != (void *)(ht + 1))
+ free(ht->ht, M_DN_HEAP);
+ free(ht, M_DN_HEAP);
+}
+
/* lookup and optionally create or delete element */
void *
dn_ht_find(struct dn_ht *ht, uintptr_t key, int flags)
@@ -517,7 +549,7 @@ main(int argc, char *argv[])
n = 1000000;
n3 = (argc > 3) ? atoi(argv[3]) : 0;
bzero(&h, sizeof(h));
- heap_init(&h, n);
+ heap_init(&h, n, -1);
while (n2-- > 0) {
uint64_t prevk = 0;
for (i=0; i < n; i++)
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Wed Jan 13 12:21:58 2010 (r202186)
@@ -1,5 +1,5 @@
/*-
- * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
+ * Copyright (c) 1998-2010 Luigi Rizzo, Universita` di Pisa
* All rights reserved
*
* Redistribution and use in source and binary forms, with or without
@@ -31,77 +31,137 @@
#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0)
#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0)
-#define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0)
-#define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0)
/*
- * A heap entry is made of a key and a pointer to the actual
- * object stored in the heap.
- * The heap is an array of dn_heap_entry entries, dynamically allocated.
- * Current size is "size", with "elements" actually in use.
- * The heap normally supports only ordered insert and extract from the top.
- * If we want to extract an object from the middle of the heap, we
- * have to know where the object itself is located in the heap (or we
- * need to scan the whole array). To this purpose, an object has a
- * field (int) which contains the index of the object itself into the
- * heap. When the object is moved, the field must also be updated.
- * The offset of the index in the object is stored in the 'ofs'
- * field in the heap descriptor. The assumption is that this offset
- * is non-zero if we want to support extract from the middle.
+ * This module implements a binary heap supporting random extraction.
+ *
+ * A heap entry contains an uint64_t key and a pointer to object.
+ * DN_KEY_LT(a,b) returns true if key 'a' is smaller than 'b'
+ *
+ * The heap is a struct dn_heap plus a dynamically allocated
+ * array of dn_heap_entry entries. 'size' represents the size of
+ * the array, 'elements' count entries in use. The topmost
+ * element has the smallest key.
+ * The heap supports ordered insert, and extract from the top.
+ * To extract an object from the middle of the heap, we the object
+ * must reserve an 'int32_t' to store the position of the object
+ * in the heap itself, and the location of this field must be
+ * passed as an argument to heap_init() -- use -1 if the feature
+ * is not used.
*/
struct dn_heap_entry {
- uint64_t key; /* sorting key. Topmost element is smallest one */
+ uint64_t key; /* sorting key, smallest comes first */
void *object; /* object pointer */
-} ;
+};
struct dn_heap {
int size; /* the size of the array */
int elements; /* elements in use */
- int ofs; /* XXX if > 0 this is the offset of direct ptr to obj */
- struct dn_heap_entry *p; /* really an array of "size" entries */
-} ;
+ int ofs; /* offset in the object of heap index */
+ struct dn_heap_entry *p; /* array of "size" entries */
+};
-/* HEAP_TOP returns the pointer to the top element of the heap */
-#define HEAP_TOP(h) ((h)->p)
-#define SET_HEAP_OFS(h, n) do { (h)->ofs = n; } while (0)
-int heap_init(struct dn_heap *h, int size);
-int heap_insert (struct dn_heap *h, uint64_t key1, void *p);
-void heap_extract(struct dn_heap *h, void *obj);
-/* void heapify(struct dn_heap *h); */
-void heap_free(struct dn_heap *h);
enum {
HEAP_SCAN_DEL = 1,
HEAP_SCAN_END = 2,
};
+
/*
- * heap_scan scans the entire heap calling fn on each entry.
- * fn() can return a combination of HEAP_SCAN_DEL and HEAP_SCAN_END,
- * where HEAP_SCAN_DEL means the current element must be removed,
- * and HEAP_SCAN_END means no further entry need to be analysed.
- * At the end, heap_scan calls heapify() if records are deleted.
- * The function returns the number of matching elements.
+ * heap_init() reinitializes the heap setting the size and the offset
+ * of the index for random extraction (use -1 if not used).
+ * The 'elements' counter is set to 0.
+ *
+ * SET_HEAP_OFS() indicates where, in the object, is stored the index
+ * for random extractions from the heap.
+ *
+ * heap_free() frees the memory associated to a heap.
+ *
+ * heap_insert() adds a key-pointer pair to the heap
+ *
+ * HEAP_TOP() returns a pointer to the top element of the heap,
+ * but makes no checks on its existance (XXX should we change ?)
+ *
+ * heap_extract() removes the entry at the top, returing the pointer.
+ * (the key should have been read before).
+ *
+ * heap_scan() invokes a callback on each entry of the heap.
+ * The callback can return a combination of HEAP_SCAN_DEL and
+ * HEAP_SCAN_END. HEAP_SCAN_DEL means the current element must
+ * be removed, and HEAP_SCAN_END means to terminate the scan.
+ * heap_scan() returns the number of elements removed.
+ * Because the order is not guaranteed, we should use heap_scan()
+ * only as a last resort mechanism.
*/
+#define HEAP_TOP(h) ((h)->p)
+#define SET_HEAP_OFS(h, n) do { (h)->ofs = n; } while (0)
+int heap_init(struct dn_heap *h, int size, int ofs);
+int heap_insert(struct dn_heap *h, uint64_t key1, void *p);
+void heap_extract(struct dn_heap *h, void *obj);
+void heap_free(struct dn_heap *h);
int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t);
-/*--- generic hash table support ---*/
-struct dn_ht {
- int buckets; /* how many buckets */
- int entries; /* how many entries */
- int ofs; /* offset of link field */
- 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 */
-};
+/*------------------------------------------------------
+ * This module implements a generic hash table with support for
+ * running callbacks on the entire table. To avoid allocating
+ * memory during hash table operations, objects must reserve
+ * space for a link field. XXX if the heap is moderately full,
+ * an SLIST suffices, and we can tolerate the cost of a hash
+ * computation on each removal.
+ *
+ * dn_ht_init() initializes the table, setting the number of
+ * buckets, the offset of the link field, the main callbacks,
+ * and an extra argument passed to the callbacks together
+ * with 'flags' which is defined below. Callbacks are:
+ *
+ * hash(key, flags, arg) called to return a bucket index.
+ * match(obj, key, flags, arg) called to determine if key
+ * matches the current 'obj' in the heap
+ * new(key, flags, arg) optional, used to allocate a new
+ * object during insertions.
+ *
+ * dn_ht_free() frees the heap, optionally unlinking elements
+ * (XXX unlink is optional and serves only to avoid stale
+ * pointers in the objects. Probably useless.)
+ *
+ * dn_ht_find() is the main lookup function, which can also be
+ * used to insert or delete elements in the hash table.
+ *
+ * dn_ht_scan() is used to invoke a callback on all entries of
+ * the heap, or possibly on just one bucket. The callback
+ * is invoked with a pointer to the object, and must return
+ * one of DNHT_SCAN_DEL or DNHT_SCAN_END to request the
+ * removal of the object from the heap and the end of the
+ * scan, respectively.
+ *
+ * A combination of flags can be used to modify the operation
+ * of the dn_ht_find(), and of the callbacks:
+ *
+ * DNHT_KEY_IS_OBJ means the key is the object pointer.
+ * It is usally of interest for the hash and match functions.
+ *
+ * DNHT_MATCH_PTR during a lookup, match pointers instead
+ * of calling match(). Normally used when removing specific
+ * entries. XXX should it imply DNHT_KEY_IS_OBJ ?
+ *
+ * DNHT_INSERT insert the element if not found.
+ * Calls new() to allocates a new object unless
+ * DNHT_KEY_IS_OBJ is set.
+ *
+ * DNHT_UNIQUE only insert if object not found.
+ * XXX should it imply DNHT_INSERT ?
+ *
+ * DNHT_REMOVE remove objects if we find them.
+ */
+struct dn_ht; /* should be opaque */
struct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs,
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 or remove element. Flags described below */
void *dn_ht_find(struct dn_ht *, uintptr_t key, int flags);
+int dn_ht_scan(struct dn_ht *, int (*)(void *, void *), void *);
+void dn_ht_free(struct dn_ht *, int flags);
enum { /* flags values.
* first two are returned by the scan callback to indicate
@@ -115,6 +175,5 @@ enum { /* flags values.
DNHT_UNIQUE = 0x0020, /* report error if already there */
DNHT_REMOVE = 0x0040, /* remove on find */
};
-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 Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Wed Jan 13 12:21:58 2010 (r202186)
@@ -57,84 +57,56 @@ struct dn_sched {
size_t schk_len;
/* + per-instance parameters, such as timestamps,
- * ccontainers for queues, etc;
+ * containers for queues, etc;
*/
size_t sch_inst_len;
- /* + per-flowset parameters, such as individual weights,
- * priorities, queue limits, slot sizes...
- */
- size_t fs_len; // fs_arg
-
- /* + per-queue parameters (what for ?)
- */
- size_t queue_len; // queue_arg
+ size_t queue_len; /* per-queue parameters (e.g. S,F) */
SLIST_ENTRY(dn_sched) next; /* Next scheduler in the list */
/*
* Methods implemented by the scheduler:
- * enqueue enqueue packet 'm' on scheduler 's'. 'id' is
- * the flow id of the packet, 'f' contains
- * flowset-specific data. Must returns 1 if the packet
- * is NOT enqueued.
+ * enqueue enqueue packet 'm' on scheduler 's', queue 'q'.
+ * q is NULL for !MULTIQUEUE.
+ * Return 0 on success, 1 on drop (packet consumed anyways).
*
* dequeue Called when scheduler instance 's' can
* dequeue a packet. Return NULL if none are available.
* XXX what about non work-conserving ?
*
- * config called on 'sched X config ...'
- * updates the field sch_arg
+ * config called on 'sched X config ...', normally writes
+ * in the area of size sch_arg
*
* destroy called on 'sched delete', frees everything
* in sch_arg (other parts are handled by more specific
* functions)
*
- * new_sched called when a new instance is
- * created by find_scheduler.
- * Updates sch_runtime
- *
- * free_sched called when deleting an instance
- * cleans everything linked to sch_runtime
- *
- * new_fs called on 'queue XX config', create fs_arg
- * if the reconfigure flag is set, it means that
- * the fs_arg already exists and need to be update
- *
- * free_fs called on 'queue XX delete', frees things in
- * fs_arg. Also called on a 'queue XX config' if the
- * scheduler is different from what was previously.
- *
- * new_queue called to link a new queue to sch_runtime
- * can be used to set queue variables e.g. virtual times,
- * update sum of weights, etc.
+ * new_sched called when a new instance is created, e.g.
+ * to create the local queue for !MULTIQUEUE, set V or
+ * copy parameters for WFQ, and so on.
*
- * free_queue called to unlink a queue from sch_runtime
- * possibly update sum of weights, etc.
+ * free_sched called when deleting an instance, cleans
+ * extra data in the per-instance area.
*
- * drain_queue called to free all idle queues, or possibly all of
- * them (this is a subset of delete_scheduler_instance)
+ * new_queue called to set the per-queue parameters,
+ * e.g. S and F, adjust sum of weights in the parent, etc.
+ *
+ * free_queue actions related to a queue removal, e.g. undo
+ * all the above.
*/
int (*enqueue)(struct new_sch_inst *, struct new_queue *,
struct mbuf *);
struct mbuf * (*dequeue)(struct new_sch_inst *);
- /* config or destroy the scheduler template */
int (*config)(struct new_schk *, int reconfigure);
int (*destroy)(struct new_schk*, int delete);
- /* create, drain or destroy a new scheduler instance */
int (*new_sched)(struct new_schk *, struct new_sch_inst *);
int (*free_sched)(struct new_sch_inst *);
- /* init or deinit a flowset attached to this scheduler */
- int (*new_fs)(void *command, struct dn_id *g, int reconfigure);
- int (*free_fs)(struct new_fsk *);
-
- /* init or destroy a queue attached to this scheduler */
int (*new_queue)(struct new_queue *q);
int (*free_queue)(struct new_queue *q);
-
};
SLIST_HEAD(dn_sched_head, dn_sched);
@@ -142,54 +114,13 @@ SLIST_HEAD(dn_sched_head, dn_sched);
* Additionally, dummynet exports some variables, functions and macros
* to be used by schedulers.
*/
-
/* delete a queue, which we assume nobody references */
int dn_delete_queue(struct new_queue *q);
-
-/* Allocate an hash table.
- * Returns the pointer to the table
- * - rq_size: the returned size of table
- * - rq_elements: the number of elements present in the table
- * - bucket: the desidered size of the table
- */
-struct new_queue ** dn_alloc_hash_queue(int *rq_size, int *rq_elements,
- int bucket);
-
-/* Delete all packets from queue 'q' */
-int dn_purge_queue(struct new_queue *q);
-
-/* Really enqueue the packet 'm' into queue 'q'.
- * If the packet is dropped, the function returns 1
- */
-int dn_queue_packet(struct new_queue *q, struct mbuf* m);
-
-/* Drop a packet 'm' that belong to queue 'q'
- * NOTE: q should be NULL if the queue doesn't exist
- */
-int dn_drop_packet(struct new_queue *q, struct mbuf* m);
-
-/* Returns the index of array of hash table.
- * The hash is done using flowset pointer and the flow id of the packet.
- * - id: flow id
- * - f: pointer to the flowset (private data)
- * - rq_size: size of the hash table
- */
-int dn_i_hash_id(struct ipfw_flow_id *id, struct dn_id *f, int rq_size);
-
-/* Returns the queue that match the flowid at the index i, if exists.
- * Returns NULL if the queue doesn't exist.
- * - id: flow id of the packet
- * - i: index of the hash table
- * - rq: pointer to the hash table
- * - f: pointer to flowset scheduler specific data. Used to access to
- * the flowset generic data
- */
-struct new_queue * dn_q_hash_id(struct ipfw_flow_id *id, int i,
- struct new_queue **rq, struct dn_id *f);
+int dn_queue_packet(struct new_queue *q, struct mbuf* m, int drop);
/*
* Extract the head of a queue, update stats. Must be the very last
- * thing done on a queue as the queue itself may go away.
+ * thing done on a dequeue as the queue itself may go away.
*/
static __inline struct mbuf*
dn_return_packet(struct new_queue *q)
@@ -211,8 +142,7 @@ int dn_sched_modevent(module_t mod, int
static moduledata_t name##_mod = { \
#name, dn_sched_modevent, dnsched \
}; \
- DECLARE_MODULE(name, name##_mod, SI_SUB_DRIVERS, \
- SI_ORDER_MIDDLE); \
+ DECLARE_MODULE(name, name##_mod, \
+ SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY); \
MODULE_DEPEND(name, dummynet, 3, 3, 3);
-
#endif /* _DN_SCHED_H */
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Wed Jan 13 12:21:58 2010 (r202186)
@@ -60,8 +60,8 @@ fifo_enqueue(struct new_sch_inst *_si, s
int ret;
struct new_fsk *fs = (struct new_fsk *)q; /* q contains the fs */
q = (struct new_queue *)(_si+1);
- q->fs = fs;
- ret = dn_queue_packet(q, m);
+ q->fs = fs; // XXX revise
+ ret = dn_queue_packet(q, m, 0);
q->fs = NULL;
if (ret) {
printf("%s dn_queue_packet dropped\n", __FUNCTION__);
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Wed Jan 13 12:21:58 2010 (r202186)
@@ -62,11 +62,8 @@ fifo_enqueue(struct new_sch_inst *_si, s
/* the queue is actually the flowset. */
q = (struct new_queue *)(_si+1);
q->fs = fs;
- if (dn_queue_packet(q, m)) {
- printf("%s dn_queue_packet failed\n", __FUNCTION__);
- /* packet was dropped */
+ if (dn_queue_packet(q, m, 0))
return 1;
- }
/* Ok, the packet is now in the queue.
* The dequeue() function will be called when the scheduler
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Wed Jan 13 12:21:58 2010 (r202186)
@@ -31,8 +31,6 @@
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
-#define DUMMYNET_DEBUG
-
#include "opt_inet6.h"
#include <sys/param.h>
@@ -71,11 +69,6 @@ __FBSDID("$FreeBSD$");
*/
static dn_key curr_time = 0 ; /* current simulation time */
-/* statistics on number of queue searches and search steps */
-static long searches, search_steps ;
-static int pipe_expire = 1 ; /* expire queue if empty */
-static int dn_max_ratio = 16 ; /* max queues/buckets ratio */
-
struct dn_parms dn_cfg = {
.pipe_slot_limit = 100, /* Foot shooting limit for pipe queues. */
.pipe_byte_limit = 1024 * 1024,
@@ -104,28 +97,6 @@ static unsigned long io_pkt_drop;
* The heap is checked at every tick and all entities with expired events
* are extracted.
*/
-
-/*
- * The key for the heap is used for two different values:
- *
- * 1. timer ticks- max 10K/second, so 32 bits are enough;
- *
- * 2. virtual times. These increase in steps of len/x, where len is the
- * packet length, and x is either the weight of the flow, or the
- * sum of all weights.
- * If we limit to max 1000 flows and a max weight of 100, then
- * x needs 17 bits. The packet size is 16 bits, so we can easily
- * overflow if we do not allow errors.
- * So we use a key "dn_key" which is 64 bits. Some macros are used to
- * compare key values and handle wraparounds.
- * MAX64 returns the largest of two key values.
- * MY_M is used as a shift count when doing fixed point arithmetic
- * (a better name would be useful...).
- * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
- * virtual time wraps every 15 days.
- */
-#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
-#define MY_M 16 /* shift for fixed point arithmetic */
MALLOC_DEFINE(M_DUMMYNET, "dummynet", "dummynet heap");
@@ -138,15 +109,6 @@ SYSCTL_DECL(_net_inet_ip);
SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet, CTLFLAG_RW, 0, "Dummynet");
SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, hash_size,
CTLFLAG_RW, &dn_cfg.hash_size, 0, "Default hash table size");
-SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, searches,
- CTLFLAG_RD, &searches, 0, "Number of queue searches");
-SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, search_steps,
- CTLFLAG_RD, &search_steps, 0, "Number of queue search steps");
-SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, expire,
- CTLFLAG_RW, &pipe_expire, 0, "Expire queue if empty");
-SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, max_chain_len,
- CTLFLAG_RW, &dn_max_ratio, 0,
- "Max ratio between dynamic queues and buckets");
SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_lookup_depth,
CTLFLAG_RD, &dn_cfg.red_lookup_depth, 0, "Depth of RED lookup table");
SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_avg_pkt_size,
@@ -230,15 +192,16 @@ mq_append(struct mq *q, struct mbuf *m)
}
/*
- * Enqueue a packet in q, subject to space and queue management policy.
+ * Enqueue a packet in q, subject to space and queue management policy
+ * (whose parameters are in q->fs).
* Update stats for the queue and the scheduler.
* Return 0 on success, 1 on drop. The packet is consumed anyways.
*/
int
-dn_queue_packet(struct new_queue *q, struct mbuf* m)
+dn_queue_packet(struct new_queue *q, struct mbuf* m, int drop)
{
struct new_fs *f;
- struct new_inst *ni;
+ struct new_inst *ni; /* stats for scheduler instance */
uint64_t len;
f = &(q->fs->fs);
@@ -249,6 +212,8 @@ dn_queue_packet(struct new_queue *q, str
q->ni.tot_pkts++;
ni->tot_bytes += len;
ni->tot_pkts++;
+ if (drop)
+ goto drop;
if (f->plr && random() < f->plr)
goto drop;
if (f->flags & DN_QSIZE_BYTES) {
@@ -293,7 +258,7 @@ transmit_event(struct mq *q, struct dela
}
if (m != NULL) {
dline->oid.subtype = 1; /* in heap */
- heap_insert(&dn_cfg.system_heap, pkt->output_time, dline);
+ heap_insert(&dn_cfg.evheap, pkt->output_time, dline);
}
}
@@ -377,7 +342,7 @@ serve_sched(struct mq *q, struct new_sch
if (m)
dn_tag_get(m)->output_time += t;
si->kflags |= DN_ACTIVE;
- heap_insert(&dn_cfg.system_heap, now + t, si);
+ heap_insert(&dn_cfg.evheap, now + t, si);
}
if (delay_line_idle && done)
transmit_event(q, &si->dline, now);
@@ -392,69 +357,67 @@ serve_sched(struct mq *q, struct new_sch
void
dummynet_task(void *context, int pending)
{
- struct timeval t;
- struct mq q = { NULL, NULL }; /* queue to accumulate results */
+ struct timeval t;
+ struct mq q = { NULL, NULL }; /* queue to accumulate results */
- DUMMYNET_LOCK();
+ DUMMYNET_LOCK();
- /* Update number of lost(coalesced) ticks. */
- tick_lost += pending - 1;
-
- getmicrouptime(&t);
- /* Last tick duration (usec). */
- tick_last = (t.tv_sec - dn_cfg.prev_t.tv_sec) * 1000000 +
- (t.tv_usec - dn_cfg.prev_t.tv_usec);
- /* Last tick vs standard tick difference (usec). */
- tick_delta = (tick_last * hz - 1000000) / hz;
- /* Accumulated tick difference (usec). */
- tick_delta_sum += tick_delta;
-
- dn_cfg.prev_t = t;
-
- /*
- * Adjust curr_time if the accumulated tick difference is
- * greater than the 'standard' tick. Since curr_time should
- * be monotonically increasing, we do positive adjustments
- * as required, and throttle curr_time in case of negative
- * adjustment.
- */
- curr_time++;
- if (tick_delta_sum - tick >= 0) {
- int diff = tick_delta_sum / tick;
-
- curr_time += diff;
- tick_diff += diff;
- tick_delta_sum %= tick;
- tick_adjustment++;
- } else if (tick_delta_sum + tick <= 0) {
- curr_time--;
- tick_diff--;
- tick_delta_sum += tick;
- tick_adjustment++;
- }
+ /* Update number of lost(coalesced) ticks. */
+ tick_lost += pending - 1;
- /* serve pending events, accumulate in q */
- for (;;) {
- struct dn_id *p; /* generic parameter to handler */
-
- if (dn_cfg.system_heap.elements > 0 &&
- DN_KEY_LEQ(HEAP_TOP(&dn_cfg.system_heap)->key, curr_time)) {
- p = HEAP_TOP(&dn_cfg.system_heap)->object;
- heap_extract(&dn_cfg.system_heap, NULL);
- } else {
- break;
- }
+ getmicrouptime(&t);
+ /* Last tick duration (usec). */
+ tick_last = (t.tv_sec - dn_cfg.prev_t.tv_sec) * 1000000 +
+ (t.tv_usec - dn_cfg.prev_t.tv_usec);
+ /* Last tick vs standard tick difference (usec). */
+ tick_delta = (tick_last * hz - 1000000) / hz;
+ /* Accumulated tick difference (usec). */
+ tick_delta_sum += tick_delta;
+
+ dn_cfg.prev_t = t;
+
+ /*
+ * Adjust curr_time if the accumulated tick difference is
+ * greater than the 'standard' tick. Since curr_time should
+ * be monotonically increasing, we do positive adjustments
+ * as required, and throttle curr_time in case of negative
+ * adjustment.
+ */
+ curr_time++;
+ if (tick_delta_sum - tick >= 0) {
+ int diff = tick_delta_sum / tick;
+
+ curr_time += diff;
+ tick_diff += diff;
+ tick_delta_sum %= tick;
+ tick_adjustment++;
+ } else if (tick_delta_sum + tick <= 0) {
+ curr_time--;
+ tick_diff--;
+ tick_delta_sum += tick;
+ tick_adjustment++;
+ }
+
+ /* serve pending events, accumulate in q */
+ for (;;) {
+ struct dn_id *p; /* generic parameter to handler */
- if (p->type == DN_SCH_I) {
- serve_sched(&q, (struct new_sch_inst *)p, curr_time);
- } else { /* extracted a delay line */
- transmit_event(&q, (struct delay_line *)p, curr_time);
+ if (dn_cfg.evheap.elements == 0 ||
+ DN_KEY_LT(curr_time, HEAP_TOP(&dn_cfg.evheap)->key))
+ break;
+ p = HEAP_TOP(&dn_cfg.evheap)->object;
+ heap_extract(&dn_cfg.evheap, NULL);
+
+ if (p->type == DN_SCH_I) {
+ serve_sched(&q, (struct new_sch_inst *)p, curr_time);
+ } else { /* extracted a delay line */
+ transmit_event(&q, (struct delay_line *)p, curr_time);
+ }
}
- }
- DUMMYNET_UNLOCK();
- dn_reschedule();
- if (q.head != NULL)
- dummynet_send(q.head);
+ DUMMYNET_UNLOCK();
+ dn_reschedule();
+ if (q.head != NULL)
+ dummynet_send(q.head);
}
/*
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h Wed Jan 13 12:21:58 2010 (r202186)
@@ -68,7 +68,7 @@ struct dn_parms {
int io_fast;
struct timeval prev_t; /* last time dummynet_tick ran */
- struct dn_heap system_heap; /* scheduled events */
+ struct dn_heap evheap; /* scheduled events */
/* counters of objects -- used for reporting space */
int schk_count;
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Wed Jan 13 08:53:23 2010 (r202185)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Wed Jan 13 12:21:58 2010 (r202186)
@@ -287,11 +287,11 @@ si_destroy(void *_si, void *arg)
struct new_queue *q;
if (si->kflags & DN_ACTIVE) /* is in the heap */
- heap_extract(&dn_cfg.system_heap, si);
+ heap_extract(&dn_cfg.evheap, si);
if (s->fp->free_sched)
s->fp->free_sched(si);
if (dl->oid.subtype) /* is in the heap */
- heap_extract(&dn_cfg.system_heap, dl);
+ heap_extract(&dn_cfg.evheap, dl);
dn_free_pkts(dl->mq.head);
while ( (q = SLIST_FIRST(&si->ql_list)) ) {
dn_delete_queue(q);
@@ -501,8 +501,7 @@ dummynet_flush(void)
dn_ht_scan(dn_cfg.schedhash, schk_del_cb, 0);
/* Reinitialize system heap... */
- heap_init(&dn_cfg.system_heap, 16);
- SET_HEAP_OFS(&dn_cfg.system_heap, offsetof(struct dn_id, id));
+ heap_init(&dn_cfg.evheap, 16, offsetof(struct dn_id, id));
DUMMYNET_UNLOCK();
}
@@ -1111,7 +1110,7 @@ ip_dn_destroy(void)
dummynet_flush();
free(dn_cfg.schedhash, M_DUMMYNET);
- heap_free(&dn_cfg.system_heap);
+ heap_free(&dn_cfg.evheap);
DUMMYNET_LOCK_DESTROY();
}
@@ -1123,6 +1122,7 @@ dummynet_modevent(module_t mod, int type
switch (type) {
case MOD_LOAD:
+ printf("%s MODLOAD\n", __FUNCTION__);
if (ip_dn_io_ptr) {
printf("DUMMYNET already loaded\n");
return EEXIST ;
@@ -1217,7 +1217,7 @@ static moduledata_t dummynet_mod = {
};
DECLARE_MODULE(dummynet, dummynet_mod,
- SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY);
+ SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY-1);
MODULE_DEPEND(dummynet, ipfw, 2, 2, 2);
MODULE_VERSION(dummynet, 1);
/* end of file */
More information about the svn-src-user
mailing list