From owner-svn-src-user@FreeBSD.ORG Tue Jan 5 15:54:10 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 349FF1065670; Tue, 5 Jan 2010 15:54:10 +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 2292C8FC15; Tue, 5 Jan 2010 15:54:10 +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 o05FsAJk042523; Tue, 5 Jan 2010 15:54:10 GMT (envelope-from luigi@svn.freebsd.org) Received: (from luigi@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id o05FsANx042519; Tue, 5 Jan 2010 15:54:10 GMT (envelope-from luigi@svn.freebsd.org) Message-Id: <201001051554.o05FsANx042519@svn.freebsd.org> From: Luigi Rizzo Date: Tue, 5 Jan 2010 15:54:09 +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: r201591 - 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:54:10 -0000 Author: luigi Date: Tue Jan 5 15:54:09 2010 New Revision: 201591 URL: http://svn.freebsd.org/changeset/base/201591 Log: try to isolate the heap code a bit more. Also mark a strange performance problem -- when an apparently innocuous RESET_OFFSET() (equivalent to "if (condition) x++;" ) the runtime decreases by some 10% for no clear reason (I suppose it is related to branch prediction or code alignment). 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:15:15 2010 (r201590) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c Tue Jan 5 15:54:09 2010 (r201591) @@ -24,15 +24,14 @@ * SUCH DAMAGE. */ -#include -__FBSDID("$FreeBSD$"); - /* * A binary heap data structure used in dummynet */ +#include #include #ifdef _KERNEL +__FBSDID("$FreeBSD$"); #include #include #include @@ -104,19 +103,20 @@ heap_init(struct dn_heap *h, int new_siz * bubble-up. * Returns 1 on failure (cannot allocate new heap entry) * - * If offset > 0 the position (index, int) of the element in the heap is + * If ofs > 0 the position (index, int) of the element in the heap is * also stored in the element itself at the given offset in bytes. */ #define SET_OFFSET(heap, node) \ - if (heap->offset > 0) \ - *((int *)((char *)(heap->p[node].object) + heap->offset)) = node; + if (heap->ofs > 0) \ + *((int *)((char *)(heap->p[node].object) + heap->ofs)) = node; /* - * RESET_OFFSET is used for sanity checks. It sets offset + * RESET_OFFSET is used for sanity checks. It sets ofs * to an invalid value. */ #define RESET_OFFSET(heap, node) \ - if (heap->offset > 0) \ - *((int *)((char *)(heap->p[node].object) + heap->offset)) = -1; + if (heap->ofs > 0) \ + *((int *)((char *)(heap->p[node].object) + heap->ofs)) = -1; + int heap_insert(struct dn_heap *h, uint64_t key1, void *p) { @@ -165,10 +165,10 @@ heap_extract(struct dn_heap *h, void *ob if (obj == NULL) father = 0; /* default: move up smallest child */ else { /* extract specific element, index is at offset */ - if (h->offset <= 0) + if (h->ofs <= 0) panic("%s: extract from middle not set on %p\n", __FUNCTION__, h); - father = *((int *)((char *)obj + h->offset)); + father = *((int *)((char *)obj + h->ofs)); if (father < 0 || father >= h->elements) { panic("%s: heap_extract, father %d out of bound 0..%d\n", __FUNCTION__, father, h->elements); @@ -180,8 +180,8 @@ 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); - while ( (child = HEAP_LEFT(father)) <= max) { + //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) ) child++; /* take right child, otherwise left */ @@ -213,10 +213,10 @@ heap_move(struct dn_heap *h, uint64_t ne int max = h->elements-1; struct dn_heap_entry buf; - if (h->offset <= 0) + if (h->ofs <= 0) panic("cannot move items on this heap"); - i = *((int *)((char *)object + h->offset)); + i = *((int *)((char *)object + h->ofs)); if (DN_KEY_LT(new_key, h->p[i].key) ) { /* must move up */ h->p[i].key = new_key; for (; i>0 && 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:15:15 2010 (r201590) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Tue Jan 5 15:54:09 2010 (r201591) @@ -45,7 +45,7 @@ * need to scan the whole array). To this purpose, an object has a * field (int) which contains the index of the object itself into the * heap. When the object is moved, the field must also be updated. - * The offset of the index in the object is stored in the 'offset' + * The offset of the index in the object is stored in the 'ofs' * field in the heap descriptor. The assumption is that this offset * is non-zero if we want to support extract from the middle. */ @@ -57,10 +57,12 @@ struct dn_heap_entry { struct dn_heap { int size; /* the size of the array */ int elements; /* elements in use */ - int offset; /* XXX if > 0 this is the offset of direct ptr to obj */ - struct dn_heap_entry *p ; /* really an array of "size" entries */ + int ofs; /* XXX if > 0 this is the offset of direct ptr to obj */ + struct dn_heap_entry *p; /* really an array of "size" entries */ } ; +/* HEAP_TOP returns the pointer to the top element of the heap */ +#define HEAP_TOP(h) ((h)->p) 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); 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:15:15 2010 (r201590) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Tue Jan 5 15:54:09 2010 (r201591) @@ -568,7 +568,7 @@ ready_event_wfq(struct dn_pipe *p, struc while (p_numbytes >= 0 && (sch->elements > 0 || neh->elements > 0)) { if (sch->elements > 0) { /* Have some eligible pkts to send out. */ - struct dn_flow_queue *q = sch->p[0].object; + struct dn_flow_queue *q = HEAP_TOP(sch)->object; struct mbuf *pkt = q->head; struct dn_flow_set *fs = q->fs; uint64_t len = pkt->m_pkthdr.len; @@ -607,10 +607,10 @@ ready_event_wfq(struct dn_pipe *p, struc * if sch is empty we only need to look at neh. */ if (sch->elements == 0 && neh->elements > 0) - p->V = MAX64(p->V, neh->p[0].key); + p->V = MAX64(p->V, HEAP_TOP(neh)->key); /* Move from neh to sch any packets that have become eligible */ - while (neh->elements > 0 && DN_KEY_LEQ(neh->p[0].key, p->V)) { - struct dn_flow_queue *q = neh->p[0].object; + while (neh->elements > 0 && DN_KEY_LEQ(HEAP_TOP(neh)->key, p->V)) { + struct dn_flow_queue *q = HEAP_TOP(neh)->object; heap_extract(neh, NULL); heap_insert(sch, q->F, q); } @@ -629,6 +629,7 @@ ready_event_wfq(struct dn_pipe *p, struc 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; @@ -738,13 +739,14 @@ dummynet_task(void *context, int pending for (i = 0; i < 3; i++) { h = heaps[i]; - while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time)) { - if (h->p[0].key > curr_time) + while (h->elements > 0 && DN_KEY_LEQ(HEAP_TOP(h)->key, curr_time)) { + // XXX can this happen ? + if (HEAP_TOP(h)->key > curr_time) printf("dummynet: warning, " "heap %d is %d ticks late\n", - i, (int)(curr_time - h->p[0].key)); + i, (int)(curr_time - HEAP_TOP(h)->key)); /* store a copy before heap_extract */ - p = h->p[0].object; + p = HEAP_TOP(h)->object; /* need to extract before processing */ heap_extract(h, NULL); if (i == 0) @@ -765,9 +767,9 @@ dummynet_task(void *context, int pending for (i = 0; i < HASHSIZE; i++) { SLIST_FOREACH(pipe, &pipehash[i], next) { if (pipe->idle_heap->elements > 0 && - DN_KEY_LT(pipe->idle_heap->p[0].key, pipe->V)) { + DN_KEY_LT(HEAP_TOP(pipe->idle_heap)->key, pipe->V)) { struct dn_flow_queue *q = - pipe->idle_heap->p[0].object; + HEAP_TOP(pipe->idle_heap)->object; heap_extract(pipe->idle_heap, NULL); /* Mark timestamp as invalid. */ @@ -1640,8 +1642,7 @@ config_pipe(struct dn_pipe *p) * idle_heap is the only one from which * we extract from the middle. */ - pipe->idle_heap->size = pipe->idle_heap->elements = 0; - pipe->idle_heap->offset = + pipe->idle_heap->ofs = offsetof(struct dn_flow_queue, heap_pos); } else { /* Flush accumulated credit for all queues. */ @@ -1757,6 +1758,8 @@ config_pipe(struct dn_pipe *p) /* * Helper function to remove from a heap queues which are linked to * a flow_set about to be deleted. + * XXX this should be moved to the heap code, as we remove entries + * from the heap under certain conditions. */ static void fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs) @@ -2115,14 +2118,9 @@ ip_dn_init(void) SLIST_INIT(&pipehash[i]); SLIST_INIT(&flowsethash[i]); } - ready_heap.size = ready_heap.elements = 0; - ready_heap.offset = 0; - - wfq_ready_heap.size = wfq_ready_heap.elements = 0; - wfq_ready_heap.offset = 0; - - extract_heap.size = extract_heap.elements = 0; - extract_heap.offset = 0; + bzero(&ready_heap, sizeof(ready_heap)); + bzero(&wfq_ready_heap, sizeof(wfq_ready_heap)); + bzero(&extract_heap, sizeof(extract_heap)); ip_dn_ctl_ptr = ip_dn_ctl; ip_dn_io_ptr = dummynet_io;