svn commit: r201591 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Tue Jan 5 15:54:10 UTC 2010
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 <sys/cdefs.h>
-__FBSDID("$FreeBSD$");
-
/*
* A binary heap data structure used in dummynet
*/
+#include <sys/cdefs.h>
#include <sys/param.h>
#ifdef _KERNEL
+__FBSDID("$FreeBSD$");
#include <sys/systm.h>
#include <sys/malloc.h>
#include <sys/kernel.h>
@@ -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;
More information about the svn-src-user
mailing list