svn commit: r201592 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Tue Jan 5 16:49:12 UTC 2010
Author: luigi
Date: Tue Jan 5 16:49:12 2010
New Revision: 201592
URL: http://svn.freebsd.org/changeset/base/201592
Log:
introduce heap_scan() to run a callback on all heap elements.
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/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 5 15:54:09 2010 (r201591)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 5 16:49:12 2010 (r201592)
@@ -1,5 +1,5 @@
/*-
- * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
+ * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa
* All rights reserved
*
* Redistribution and use in source and binary forms, with or without
@@ -180,7 +180,7 @@ heap_extract(struct dn_heap *h, void *ob
* reach the bottom level.
*/
// XXX why removing RESET_OFFSET increases runtime by 10% ?
- //RESET_OFFSET(h, father);
+ RESET_OFFSET(h, father);
while ( (child = HEAP_LEFT(father)) <= max ) {
if (child != max &&
DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
@@ -249,17 +249,37 @@ heap_move(struct dn_heap *h, uint64_t ne
* heapify() will reorganize data inside an array to maintain the
* heap property. It is needed when we delete a bunch of entries.
*/
-void
+static void
heapify(struct dn_heap *h)
{
int i;
- printf("%s on %p for %d elements\n",
- __FUNCTION__, h, h->elements);
for (i = 0; i < h->elements; i++ )
heap_insert(h, i , NULL);
}
+int
+heap_scan(struct dn_heap *h, int (*fn)(void *, uintptr_t),
+ uintptr_t arg)
+{
+ int i, ret, found;
+
+ for (i = found = 0 ; i < h->elements ;) {
+ ret = fn(h->p[i].object, arg);
+ if (ret & HEAP_SCAN_DEL) {
+ h->elements-- ;
+ h->p[i] = h->p[h->elements] ;
+ found++ ;
+ } else
+ i++ ;
+ if (ret & HEAP_SCAN_END)
+ break;
+ }
+ if (found)
+ heapify(h);
+ return found;
+}
+
/*
* cleanup the heap and free data structure
*/
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 5 15:54:09 2010 (r201591)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 5 16:49:12 2010 (r201592)
@@ -66,7 +66,20 @@ struct dn_heap {
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 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.
+ */
+int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t);
#endif /* _IP_DN_HEAP_H */
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Tue Jan 5 15:54:09 2010 (r201591)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Tue Jan 5 16:49:12 2010 (r201592)
@@ -521,6 +521,17 @@ ready_event(struct dn_flow_queue *q, str
transmit_event(p, head, tail);
}
+/* callback to clean the idle heap */
+static int
+clean_fq(void *_q, uintptr_t arg)
+{
+ struct dn_flow_queue *q = _q;
+
+ q->F = 0;
+ q->S = q->F + 1;
+ return HEAP_SCAN_DEL;
+}
+
/*
* Called when we can transmit packets on WF2Q queues. Take pkts out of
* the queues at their start time, and enqueue into the delay line.
@@ -627,16 +638,7 @@ ready_event_wfq(struct dn_pipe *p, struc
* We can get rid of idle-heap.
*/
if (p->idle_heap->elements > 0) {
- int i;
-
- /* XXX do a heap_extract perhaps ? */
- for (i = 0; i < p->idle_heap->elements; i++) {
- struct dn_flow_queue *q;
-
- q = p->idle_heap->p[i].object;
- q->F = 0;
- q->S = q->F + 1;
- }
+ heap_scan(p->idle_heap, clean_fq, 0);
p->sum = 0;
p->V = 0;
p->idle_heap->elements = 0;
@@ -1761,39 +1763,26 @@ config_pipe(struct dn_pipe *p)
* XXX this should be moved to the heap code, as we remove entries
* from the heap under certain conditions.
*/
+static int
+scan_remove_fs(void *_o, uintptr_t fs)
+{
+ struct dn_flow_queue *fq = _o;
+ return (fq->fs == (struct dn_flow_set *)fs) ? HEAP_SCAN_DEL : 0;
+}
+
static void
fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs)
{
- int i, found;
-
- for (i = found = 0 ; i < h->elements ;) {
- if ( ((struct dn_flow_queue *)h->p[i].object)->fs == fs) {
- h->elements-- ;
- h->p[i] = h->p[h->elements] ;
- found++ ;
- } else
- i++ ;
- }
- if (found)
- heapify(h);
+ heap_scan(h, scan_remove_fs, (uintptr_t)fs);
}
/*
* helper function to remove a pipe from a heap (can be there at most once)
*/
-static void
-pipe_remove_from_heap(struct dn_heap *h, struct dn_pipe *p)
+static int
+scan_remove_pipe(void *_o, uintptr_t p)
{
- int i;
-
- for (i=0; i < h->elements ; i++ ) {
- if (h->p[i].object == p) { /* found it */
- h->elements-- ;
- h->p[i] = h->p[h->elements] ;
- heapify(h);
- break ;
- }
- }
+ return (0 == (void *)p) ? HEAP_SCAN_DEL | HEAP_SCAN_END : 0;
}
/*
@@ -1866,8 +1855,8 @@ delete_pipe(struct dn_pipe *p)
fs_remove_from_heap(&ready_heap, &(pipe->fs));
purge_pipe(pipe); /* remove all data associated to this pipe */
/* remove reference to here from extract_heap and wfq_ready_heap */
- pipe_remove_from_heap(&extract_heap, pipe);
- pipe_remove_from_heap(&wfq_ready_heap, pipe);
+ heap_scan(&extract_heap, scan_remove_pipe, (uintptr_t)pipe);
+ heap_scan(&wfq_ready_heap, scan_remove_pipe, (uintptr_t)pipe);
DUMMYNET_UNLOCK();
free_pipe(pipe);
More information about the svn-src-user
mailing list