From owner-svn-src-user@FreeBSD.ORG Tue Jan 5 15:04:08 2010 Return-Path: Delivered-To: svn-src-user@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id CE68E1065679; Tue, 5 Jan 2010 15:04:08 +0000 (UTC) (envelope-from luigi@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id BD1E78FC21; Tue, 5 Jan 2010 15:04:08 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id o05F48Kc031243; Tue, 5 Jan 2010 15:04:08 GMT (envelope-from luigi@svn.freebsd.org) Received: (from luigi@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o05F48vG031241; Tue, 5 Jan 2010 15:04:08 GMT (envelope-from luigi@svn.freebsd.org) Message-Id: <201001051504.o05F48vG031241@svn.freebsd.org> From: Luigi Rizzo Date: Tue, 5 Jan 2010 15:04:08 +0000 (UTC) To: src-committers@freebsd.org, svn-src-user@freebsd.org X-SVN-Group: user MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r201589 - user/luigi/ipfw3-head/sys/netinet/ipfw X-BeenThere: svn-src-user@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the experimental " user" src tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 05 Jan 2010 15:04:09 -0000 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 #include #include + #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