Date: Tue, 5 Jan 2010 15:04:08 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r201589 - user/luigi/ipfw3-head/sys/netinet/ipfw Message-ID: <201001051504.o05F48vG031241@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001051504.o05F48vG031241>