Date: Wed, 13 Jan 2010 12:21:58 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r202186 - user/luigi/ipfw3-head/sys/netinet/ipfw Message-ID: <201001131221.o0DCLwis005541@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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 */
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001131221.o0DCLwis005541>