svn commit: r201589 - user/luigi/ipfw3-head/sys/netinet/ipfw

[Luigi Rizzo]

Author: luigi
Date: Tue Jan  5 15:04:08 2010
New Revision: 201589
URL: http://svn.freebsd.org/changeset/base/201589

Log:
  more debugging stuff

Modified:
  user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.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 14:03:46 2010	(r201588)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c	Tue Jan  5 15:04:08 2010	(r201589)
@@ -44,6 +44,7 @@ __FBSDID("$FreeBSD$");
 #include <stdio.h>
 #include <strings.h>
 #include <stdlib.h>
+
 #include  "dn_heap.h"
 #define log(x, arg...)	fprintf(stderr, ## arg)
 #define panic(x...)	fprintf(stderr, ## x), exit(1)
@@ -64,14 +65,10 @@ MALLOC_DEFINE(M_DN_HEAP, "dummynet", "du
  *
  * heap_init() is called to expand the heap when needed.
  * Increment size in blocks of 16 entries.
- * XXX failure to allocate a new element is a pretty bad failure
- * as we basically stall a whole queue forever!!
  * Returns 1 on error, 0 on success
  */
 #define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 )
-#define HEAP_LEFT(x) ( 2*(x) + 1 )
-#define HEAP_IS_LEFT(x) ( (x) & 1 )
-#define HEAP_RIGHT(x) ( 2*(x) + 2 )
+#define HEAP_LEFT(x) ( (x)+(x) + 1 )
 #define	HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; }
 #define HEAP_INCREMENT	15
 
@@ -137,7 +134,8 @@ heap_insert(struct dn_heap *h, uint64_t 
 		h->p[son].key = key1;
 		h->elements++;
 	}
-	while (son > 0) {			/* bubble up */
+	/* make sure that son >= father along the path */
+	while (son > 0) {
 		int father = HEAP_FATHER(son);
 		struct dn_heap_entry tmp;
 
@@ -164,8 +162,9 @@ heap_extract(struct dn_heap *h, void *ob
 		printf("%s: empty heap 0x%p\n", __FUNCTION__, h);
 		return;
 	}
-	father = 0; /* default: move up smallest child */
-	if (obj != NULL) { /* extract specific element, index is at offset */
+	if (obj == NULL)
+		father = 0; /* default: move up smallest child */
+	else { /* extract specific element, index is at offset */
 		if (h->offset <= 0)
 			panic("%s: extract from middle not set on %p\n",
 				__FUNCTION__, h);
@@ -175,16 +174,20 @@ heap_extract(struct dn_heap *h, void *ob
 				__FUNCTION__, father, h->elements);
 		}
 	}
+	/*
+	 * below, father is the index of the empty element, which
+	 * we replace at each step with the smallest child until we
+	 * reach the bottom level.
+	 */
+	// XXX why removing RESET_OFFSET increases runtime by 10% ?
 	RESET_OFFSET(h, father);
-	child = HEAP_LEFT(father);		/* left child */
-	while (child <= max) {		/* valid entry */
+	while ( (child = HEAP_LEFT(father)) <= max) {
 		if (child != max &&
 		    DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
 			child++; /* take right child, otherwise left */
 		h->p[father] = h->p[child];
 		SET_OFFSET(h, father);
 		father = child;
-		child = HEAP_LEFT(child); /* prepare for next loop */
 	}
 	h->elements--;
 	if (father != max) {
@@ -276,23 +279,34 @@ int
 main(int argc, char *argv[])
 {
 	struct dn_heap h;
-	int i, n;
-	struct timeval tv;
-	uint64_t k;
+	int i, n, n2, n3;
 
+	/* n = elements, n2 = cycles */
 	n = (argc > 1) ? atoi(argv[1]) : 0;
-	if (n <= 0 || n > 10000)
+	if (n <= 0 || n > 1000000)
 		n = 100;
+	n2 = (argc > 2) ? atoi(argv[2]) : 0;
+	if (n2 <= 0)
+		n = 1000000;
+	n3 = (argc > 3) ? atoi(argv[3]) : 0;
 	bzero(&h, sizeof(h));
-	gettimeofday(&tv, NULL);
-	srandom(tv.tv_usec);
-	heap_init(&h, 0);
-	for (i=0; i < n; i++)
-		heap_insert(&h, random(), (void *)(100+i));
-	for (i=0; h.elements > 0; i++) {
-		printf("%d key %llu, val %p\n",
-			i, h.p[0].key, h.p[0].object);
-		heap_extract(&h, NULL);
+	heap_init(&h, n);
+	while (n2-- > 0) {
+		uint64_t prevk = 0;
+		for (i=0; i < n; i++)
+			heap_insert(&h, n3 ? n-i: random(), (void *)(100+i));
+		
+		for (i=0; h.elements > 0; i++) {
+			uint64_t k = h.p[0].key;
+			if (k < prevk)
+				panic("wrong sequence\n");
+			prevk = k;
+			if (0)
+			printf("%d key %llu, val %p\n",
+				i, h.p[0].key, h.p[0].object);
+			heap_extract(&h, NULL);
+		}
 	}
+	return 0;
 }
 #endif