Skip site navigation (1)Skip section navigation (2) 
Date:      Tue, 5 Jan 2010 16:49:12 +0000 (UTC)
From:      Luigi Rizzo <luigi@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-user@freebsd.org
Subject:   svn commit: r201592 - user/luigi/ipfw3-head/sys/netinet/ipfw
Message-ID:  <201001051649.o05GnCbt054721@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help 
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);

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001051649.o05GnCbt054721>