Some dummynet patches that I forgot to commit last summer.

One of them fixes a potential panic when bridging is used and
you run out of mbufs (though i have no idea if the bug has
ever hit anyone).

2 files changed, 75 insertions, 34 deletions

diff --git a/sys/netinet/ip_dummynet.c b/sys/netinet/ip_dummynet.c
index ed43449..f737d0f 100644
--- a/sys/netinet/ip_dummynet.c
+++ b/sys/netinet/ip_dummynet.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1998-2000 Luigi Rizzo, Universita` di Pisa
+ * Copyright (c) 1998-2001 Luigi Rizzo, Universita` di Pisa
  * Portions Copyright (c) 2000 Akamba Corp.
  * All rights reserved
  *
@@ -332,7 +332,7 @@ heapify(struct dn_heap *h)
 
     for (i = 0 ; i < h->elements ; i++ )
 	heap_insert(h, i , NULL) ;
-    }
+}
 
 /*
  * cleanup the heap and free data structure
@@ -401,16 +401,22 @@ transmit_event(struct dn_pipe *pipe)
 
 #ifdef BRIDGE
 	case DN_TO_BDG_FWD : {
-	    struct mbuf *m = (struct mbuf *)pkt ;
+	    struct mbuf *m = (struct mbuf *)pkt;
 	    struct ether_header hdr;
 
 	    if (pkt->dn_m->m_len < ETHER_HDR_LEN
 	      && (pkt->dn_m = m_pullup(pkt->dn_m, ETHER_HDR_LEN)) == NULL) {
-		m_freem(pkt->dn_m);
+		printf("dummynet/bridge: pullup fail, dropping pkt\n");
 		break;
 	    }
 	    bcopy(mtod(pkt->dn_m, struct ether_header *), &hdr, ETHER_HDR_LEN);
 	    m_adj(pkt->dn_m, ETHER_HDR_LEN);
+	    /*
+	     * bdg_forward() wants a pointer to the pseudo-mbuf-header, but
+	     * on return it will supply the pointer to the actual packet
+	     * (originally pkt->dn_m, but could be something else now) if
+	     * it has not consumed it.
+	     */
 	    bdg_forward(&m, &hdr, pkt->ifp);
 	    if (m)
 		m_freem(m);
@@ -484,14 +490,14 @@ ready_event(struct dn_flow_queue *q)
     }
     p_was_empty = (p->head == NULL) ;
 
-	/*
+    /*
      * schedule fixed-rate queues linked to this pipe:
      * Account for the bw accumulated since last scheduling, then
      * drain as many pkts as allowed by q->numbytes and move to
      * the delay line (in p) computing output time.
      * bandwidth==0 (no limit) means we can drain the whole queue,
      * setting len_scaled = 0 does the job.
-	 */
+     */
     q->numbytes += ( curr_time - q->sched_time ) * p->bandwidth;
     while ( (pkt = q->head) != NULL ) {
 	int len = pkt->dn_m->m_pkthdr.len;
@@ -568,12 +574,17 @@ ready_event_wfq(struct dn_pipe *p)
 	/* XXX should we do this at the end of the service ? */
 	/* evaluate normalized service */
 	normalized_service = (len<<MY_M)/p->sum ;
-	if (q->len == 0) { /* session not backlogged any more*/
-	    heap_extract(blh, q); /* remove queue from backlogged heap */
-	    p->sum -= fs->weight;
+	q->S = q->F ; /* update start time */
+	if (q->len == 0) {
+	    /*
+	     * Session not backlogged any more, remove from backlogged
+	     * and insert into idle_heap
+	     */
+	    heap_extract(blh, q);
 	    fs->backlogged-- ;
+	    /* p->sum -= fs->weight; XXX don't do this here ! */
+	    heap_insert(&(p->idle_heap), q->F, q);
 	} else { /* session backlogged again: update values */
-	    q->S = q->F ; /* update start time */
 	    len = (q->head)->dn_m->m_pkthdr.len;
 	    q->F += (len<<MY_M)/(u_int64_t) fs->weight ;
 	    /* update queue position in backlogged_heap */
@@ -642,6 +653,7 @@ dummynet(void * __unused unused)
     int s ;
     struct dn_heap *heaps[3];
     int i;
+    struct dn_pipe *pe ;
 
     heaps[0] = &ready_heap ;		/* fixed-rate queues */
     heaps[1] = &wfq_ready_heap ;	/* wfq queues */
@@ -650,14 +662,14 @@ dummynet(void * __unused unused)
     curr_time++ ;
     for (i=0; i < 3 ; i++) {
 	h = heaps[i];
-    while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time) ) {
+	while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time) ) {
 	    DDB(if (h->p[0].key > curr_time)
 		printf("-- dummynet: warning, heap %d is %d ticks late\n",
 		    i, (int)(curr_time - h->p[0].key));)
 	    p = h->p[0].object ; /* store a copy before heap_extract */
 	    heap_extract(h, NULL); /* need to extract before processing */
 	    if (i == 0)
-        ready_event(p) ;
+		ready_event(p) ;
 	    else if (i == 1) {
 		struct dn_pipe *pipe = p;
 		if (pipe->if_name[0] != '\0')
@@ -666,9 +678,19 @@ dummynet(void * __unused unused)
 		else
 		    ready_event_wfq(p) ;
 	    } else
-        transmit_event(p);
-    }
+		transmit_event(p);
+	}
     }
+    /* sweep pipes trying to expire idle flow_queues */
+    for (pe = all_pipes; pe ; pe = pe->next )
+	if (pe->idle_heap.elements > 0 &&
+		DN_KEY_LT(pe->idle_heap.p[0].key, pe->V) ) {
+	    struct dn_flow_queue *q = pe->idle_heap.p[0].object ;
+
+	    heap_extract(&(pe->idle_heap), NULL);
+	    q->S = q->F + 1 ; /* mark timestamp as invalid */
+	    pe->sum -= q->fs->weight ;
+	}
     splx(s);
     timeout(dummynet, NULL, 1);
 }
@@ -759,7 +781,7 @@ create_queue(struct dn_flow_set *fs, int i)
     q->fs = fs ;
     q->hash_slot = i ;
     q->next = fs->rq[i] ;
-    q->S = q->F = fs->pipe->V ;		/* set virtual times */
+    q->S = q->F + 1;   /* hack - mark timestamp as invalid */
     fs->rq[i] = q ;
     fs->rq_elements++ ;
     return q ;
@@ -1068,11 +1090,16 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	 * there is some other flow already scheduled for the same pipe.
 	 * If eligible, AND the pipe is idle, then call ready_event_wfq().
 	 */
-	q->S = MAX64(q->F, pipe->V ) ;
+	if (DN_KEY_GT(q->S, q->F)) { /* means timestamps are invalid */
+	    q->S = pipe->V ;
+	    pipe->sum += fs->weight ; /* add weight of new queue */
+	} else {
+	    heap_extract(&(pipe->idle_heap), q);
+	    q->S = MAX64(q->F, pipe->V ) ;
+	}
 	q->F = q->S + ( len<<MY_M )/(u_int64_t) fs->weight;
 
 	heap_insert(&(pipe->backlogged_heap), q->S, q);
-	pipe->sum += fs->weight ;	/* new session backlogged */
 	fs->backlogged++ ;
 	if (DN_KEY_GT(q->S, pipe->V) ) { /* not eligible */
 	    DDB(printf("== not eligible, size %d\n", (int)len);)
@@ -1165,6 +1192,7 @@ purge_pipe(struct dn_pipe *pipe)
     heap_free( &(pipe->scheduler_heap) );
     heap_free( &(pipe->not_eligible_heap) );
     heap_free( &(pipe->backlogged_heap) );
+    heap_free( &(pipe->idle_heap) );
 }
 
 /*
@@ -1349,11 +1377,11 @@ set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src)
     /* configuring RED */
     if ( x->flags_fs & DN_IS_RED )
 	config_red(src, x) ;    /* XXX should check errors */
-	}
+}
 
-	    /*
+/*
  * setup pipe or queue parameters.
-	     */
+ */
 
 static int 
 config_pipe(struct dn_pipe *p)
@@ -1387,8 +1415,14 @@ config_pipe(struct dn_pipe *p)
 	    }
 	    x->pipe_nr = p->pipe_nr;
 	    x->fs.pipe = x ;
+	    /* a flowset is backlogged only if it has packets queued.
+	     * Otherwise it becomes idle, so we can use the same variable
+	     * to store the position in either heap.
+	     */
 	    x->backlogged_heap.size = x->backlogged_heap.elements = 0 ;
 	    x->backlogged_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos);
+	    x->idle_heap.size = x->idle_heap.elements = 0 ;
+	    x->idle_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos);
 	} else
 	    x = b;
 
@@ -1469,17 +1503,17 @@ config_pipe(struct dn_pipe *p)
 static void
 fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs)
 {
-		int i = 0, found = 0 ;
+    int i = 0, found = 0 ;
     for (; i < h->elements ;)
 	if ( ((struct dn_flow_queue *)h->p[i].object)->fs == fs) {
-			h->elements-- ;
-			h->p[i] = h->p[h->elements] ;
-			found++ ;
-		    } else
-			i++ ;
-		if (found)
-		    heapify(h);
-	    }
+	    h->elements-- ;
+	    h->p[i] = h->p[h->elements] ;
+	    found++ ;
+	} else
+	    i++ ;
+    if (found)
+	heapify(h);
+}
 
 /*
  * helper function to remove a pipe from a heap (can be there at most once)
@@ -1498,7 +1532,7 @@ pipe_remove_from_heap(struct dn_heap *h, struct dn_pipe *p)
 	    }
 	}
     }
-	    }
+}
 
 /*
  * drain all queues. Called in case of severe mbuf shortage.
@@ -1545,7 +1579,7 @@ delete_pipe(struct dn_pipe *p)
 	/* locate pipe */
 	for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
 		 a = b , b = b->next) ;
-	if (b == NULL || b->pipe_nr != p->pipe_nr)
+	if (b == NULL || (b->pipe_nr != p->pipe_nr) )
 	    return EINVAL ; /* not found */
 
 	s = splnet() ;
@@ -1581,7 +1615,7 @@ delete_pipe(struct dn_pipe *p)
 	/* locate set */
 	for (a = NULL, b = all_flow_sets ; b && b->fs_nr < p->fs.fs_nr ;
 		 a = b , b = b->next) ;
-	if (b == NULL || b->fs_nr != p->fs.fs_nr)
+	if (b == NULL || (b->fs_nr != p->fs.fs_nr) )
 	    return EINVAL ; /* not found */
 
 	s = splnet() ;
@@ -1600,12 +1634,15 @@ delete_pipe(struct dn_pipe *p)
 	    fs_remove_from_heap(&(b->pipe->backlogged_heap), b);
 	    fs_remove_from_heap(&(b->pipe->not_eligible_heap), b);
 	    fs_remove_from_heap(&(b->pipe->scheduler_heap), b);
+#if 0	/* XXX should i remove from idle_heap as well ? */
+	    fs_remove_from_heap(&(b->pipe->idle_heap), b);
+#endif
 	}
 	purge_flow_set(b, 1);
 	splx(s);
     }
     return 0 ;
-	}
+}
 
 /*
  * helper function used to copy data from kernel in DUMMYNET_GET
@@ -1752,7 +1789,7 @@ ip_dn_ctl(struct sockopt *sopt)
 static void
 ip_dn_init(void)
 {
-    printf("DUMMYNET initialized (000608)\n");
+    printf("DUMMYNET initialized (010116)\n");
     all_pipes = NULL ;
     all_flow_sets = NULL ;
     ready_heap.size = ready_heap.elements = 0 ;
diff --git a/sys/netinet/ip_dummynet.h b/sys/netinet/ip_dummynet.h
index 9105e967..504995a 100644
--- a/sys/netinet/ip_dummynet.h
+++ b/sys/netinet/ip_dummynet.h
@@ -166,6 +166,9 @@ struct dn_flow_queue {
     dn_key sched_time ; /* current time when queue enters ready_heap */
 
     dn_key S,F ; /* start-time, finishing time */
+    /* setting F < S means the timestamp is invalid. We only need
+     * to test this when the queue is empty.
+     */
 } ;
 
 struct dn_flow_set {
@@ -242,6 +245,7 @@ struct dn_pipe {			/* a pipe */
     struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
     struct dn_heap not_eligible_heap; /* top extract- key Start time */
     struct dn_heap backlogged_heap ; /* random extract - key Start time */
+    struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
 
     dn_key V ; /* virtual time */
     int sum;	/* sum of weights of all active sessions */