Bring dummynet in line with the code that now works in -STABLE.

It compiles, but I cannot test functionality yet.

1 files changed, 125 insertions, 88 deletions

diff --git a/sys/netinet/ip_dummynet.c b/sys/netinet/ip_dummynet.c
index a17b09f..366d447 100644
--- a/sys/netinet/ip_dummynet.c
+++ b/sys/netinet/ip_dummynet.c
@@ -47,8 +47,9 @@
  *
  * Most important Changes:
  *
+ * 010124: Fixed WF2Q behaviour
  * 010122: Fixed spl protection.
- * 000601: WF2Q+ support
+ * 000601: WF2Q support
  * 000106: large rewrite, use heaps to handle very many pipes.
  * 980513:	initial release
  *
@@ -92,7 +93,7 @@ static int dn_hash_size = 64 ;	/* default hash size */
 
 /* statistics on number of queue searches and search steps */
 static int searches, search_steps ;
-static int pipe_expire = 0 ;   /* expire queue if empty */
+static int pipe_expire = 1 ;   /* expire queue if empty */
 static int dn_max_ratio = 16 ; /* max queues/buckets ratio */
 
 static int red_lookup_depth = 256;	/* RED - default lookup table depth */
@@ -100,16 +101,21 @@ static int red_avg_pkt_size = 512;      /* RED - default medium packet size */
 static int red_max_pkt_size = 1500;     /* RED - default max packet size */
 
 /*
- * ready_heap contains all dn_flow_queue's scheduled for action
- * at a given time.
- * wfq_ready_heap contains the schedulable pipe.
- * Extract_heap contains pipes because it is there that packets
- * in the delay line are held.
+ * Three heaps contain queues and pipes that the scheduler handles:
+ *
+ * ready_heap contains all dn_flow_queue related to fixed-rate pipes.
+ *
+ * wfq_ready_heap contains the pipes associated with WF2Q flows
+ *
+ * extract_heap contains pipes associated with delay lines.
+ *
  */
 static struct dn_heap ready_heap, extract_heap, wfq_ready_heap ;
+
 static int heap_init(struct dn_heap *h, int size) ;
 static int heap_insert (struct dn_heap *h, dn_key key1, void *p);
 static void heap_extract(struct dn_heap *h, void *obj);
+
 static void transmit_event(struct dn_pipe *pipe);
 static void ready_event(struct dn_flow_queue *q);
 
@@ -152,6 +158,8 @@ static void dummynet(void *);
 static void dummynet_flush(void);
 void dummynet_drain(void);
 
+int if_tx_rdy(struct ifnet *ifp);
+
 /*
  * ip_fw_chain is used when deleting a pipe, because ipfw rules can
  * hold references to the pipe.
@@ -270,22 +278,22 @@ heap_extract(struct dn_heap *h, void *obj)
 {  
     int child, father, max = h->elements - 1 ;
 
-    if (max < 0)
+    if (max < 0) {
+	printf("warning, extract from empty heap 0x%p\n", h);
 	return ;
+    }
     father = 0 ; /* default: move up smallest child */
     if (obj != NULL) { /* extract specific element, index is at offset */
-	if (h->offset <= 0) {
-	    printf("*** extract from middle not supported!!!\n");
-	    return ; /* or maybe panic... */
-	}
+	if (h->offset <= 0)
+	    panic("*** heap_extract from middle not supported on this heap!!!\n");
 	father = *((int *)((char *)obj + h->offset)) ;
 	if (father < 0 || father >= h->elements) {
 	    printf("dummynet: heap_extract, father %d out of bound 0..%d\n",
 		father, h->elements);
 	    panic("heap_extract");
 	}
-	RESET_OFFSET(h, father); 
     }
+    RESET_OFFSET(h, father);
     child = HEAP_LEFT(father) ;		/* left child */
     while (child <= max) {		/* valid entry */
 	if (child != max && DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
@@ -302,7 +310,7 @@ heap_extract(struct dn_heap *h, void *obj)
 	 */
 	h->p[father] = h->p[max] ;
 	heap_insert(h, father, NULL); /* this one cannot fail */
-    }   
+    }
 }           
 
 /*
@@ -343,8 +351,6 @@ heap_move(struct dn_heap *h, dn_key new_key, void *object)
     SET_OFFSET(h, i);
 }
 
-
-
 /*
  * heapify() will reorganize data inside an array to maintain the
  * heap property. It is needed when we delete a bunch of entries.
@@ -366,7 +372,7 @@ heap_free(struct dn_heap *h)
 {
     if (h->size >0 )
 	free(h->p, M_IPFW);
-    h->elements = h->size = 0 ;
+    bzero(h, sizeof(*h) );
 }
 
 /*
@@ -384,7 +390,7 @@ heap_free(struct dn_heap *h)
  * ready_event() does something similar with fixed-rate queues, and the
  * event handled is the finish time of the head pkt.
  *
- * wfq_ready_event() does something similar with WFQ queues, and the
+ * wfq_ready_event() does something similar with WF2Q queues, and the
  * event handled is the start time of the head pkt.
  *
  * In all cases, we make sure that the data structures are consistent
@@ -426,14 +432,17 @@ transmit_event(struct dn_pipe *pipe)
 #ifdef BRIDGE
 	case DN_TO_BDG_FWD : {
 	    struct mbuf *m = (struct mbuf *)pkt;
-	    struct ether_header hdr;
+	    struct ether_header *eh;
 
 	    if (pkt->dn_m->m_len < ETHER_HDR_LEN
 	      && (pkt->dn_m = m_pullup(pkt->dn_m, ETHER_HDR_LEN)) == NULL) {
 		printf("dummynet/bridge: pullup fail, dropping pkt\n");
 		break;
 	    }
-	    bcopy(mtod(pkt->dn_m, struct ether_header *), &hdr, ETHER_HDR_LEN);
+	    /*
+	     * same as ether_input, make eh be a pointer into the mbuf
+	     */
+	    eh = (void *)pkt->dn_m->m_data ;
 	    m_adj(pkt->dn_m, ETHER_HDR_LEN);
 	    /*
 	     * bdg_forward() wants a pointer to the pseudo-mbuf-header, but
@@ -441,7 +450,7 @@ transmit_event(struct dn_pipe *pipe)
 	     * (originally pkt->dn_m, but could be something else now) if
 	     * it has not consumed it.
 	     */
-	    bdg_forward(&m, &hdr, pkt->ifp);
+	    bdg_forward(&m, eh, pkt->ifp);
 	    if (m)
 		m_freem(m);
 	    }
@@ -569,6 +578,7 @@ ready_event_wfq(struct dn_pipe *p)
     int p_was_empty = (p->head == NULL) ;
     struct dn_heap *sch = &(p->scheduler_heap);
     struct dn_heap *blh = &(p->backlogged_heap);
+    struct dn_heap *neh = &(p->not_eligible_heap) ;
 
     if (p->if_name[0] == 0) /* tx clock is simulated */
 	p->numbytes += ( curr_time - p->sched_time ) * p->bandwidth;
@@ -581,64 +591,71 @@ ready_event_wfq(struct dn_pipe *p)
 	}
     }
 
-    while ( sch->elements && p->numbytes >= 0 ) {
-	struct dn_heap *neh ;
-	u_int64_t normalized_service ;
-	struct dn_flow_queue *q = sch->p[0].object ;
-	struct dn_pkt *pkt = q->head;  
-	struct dn_flow_set *fs = q->fs;   
-	u_int64_t len = pkt->dn_m->m_pkthdr.len;
-	int len_scaled = p->bandwidth ? len*8*hz : 0 ;
-
-	heap_extract(sch, NULL); /* remove queue from heap */
-	p->numbytes -= len_scaled ;
-	move_pkt(pkt, q, p, len);
-	    
-	/* XXX should we do this at the end of the service ? */
-	/* evaluate normalized service */
-	normalized_service = (len<<MY_M)/p->sum ;
-	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 */
-	    len = (q->head)->dn_m->m_pkthdr.len;
-	    q->F += (len<<MY_M)/(u_int64_t) fs->weight ;
-	    /* update queue position in backlogged_heap */
-	    heap_move(blh, q->S, q);
+    /*
+     * While we have backlogged traffic AND credit, we need to do
+     * something on the queue.
+     */
+    while ( blh->elements>0 && p->numbytes >= 0 ) {
+	if (sch->elements > 0) { /* have some eligible pkts to send out */
+	    struct dn_flow_queue *q = sch->p[0].object ;
+	    struct dn_pkt *pkt = q->head;  
+	    struct dn_flow_set *fs = q->fs;   
+	    u_int64_t len = pkt->dn_m->m_pkthdr.len;
+	    int len_scaled = p->bandwidth ? len*8*hz : 0 ;
+
+	    heap_extract(sch, NULL); /* remove queue from heap */
+	    p->numbytes -= len_scaled ;
+	    move_pkt(pkt, q, p, len);
+
+	    p->V += (len<<MY_M) / p->sum ; /* update V */
+	    q->S = q->F ; /* update start time */
+	    if (q->len == 0) { /* Flow not backlogged any more */
+		heap_extract(blh, q);
+		fs->backlogged-- ;
+		heap_insert(&(p->idle_heap), q->F, q);
+	    } else { /* still backlogged */
+		/*
+		 * update F and position in backlogged queue, then
+		 * put flow in not_eligible_heap (we will fix this later).
+		 */
+		len = (q->head)->dn_m->m_pkthdr.len;
+		q->F += (len<<MY_M)/(u_int64_t) fs->weight ;
+		heap_move(blh, q->S, q);
+		heap_insert(neh, q->S, q);
+	    }
 	}
-	/* update virtual time */
-	p->V += normalized_service ;
 	if (blh->elements > 0)
 	    p->V = MAX64 ( p->V, blh->p[0].key );
-	DEB(printf("-- %d backlogged, V is %d\n",
-		blh->elements, (int)(p->V >> MY_M) ); )
-
 	/* move from not_eligible_heap to scheduler_heap */
 	neh = &(p->not_eligible_heap) ;
 	while (neh->elements > 0 && DN_KEY_LEQ(neh->p[0].key, p->V) ) {
-	    struct dn_flow_queue *temp = neh->p[0].object ;
+	    struct dn_flow_queue *q = neh->p[0].object ;
 	    heap_extract(neh, NULL);
-	    heap_insert(sch, temp->F, temp);
+	    heap_insert(sch, q->F, q);
 	}
 
-	if (q->len) {/* need to reschedule queue */
-	    if ( DN_KEY_LEQ(q->S, p->V) )
-		heap_insert(sch, q->F, q); /* schedule following packet */
-	    else
-		heap_insert(neh, q->S, q); /* queue in not_eligible_heap */
-	}
 	if (p->if_name[0] != '\0') {/* tx clock is from a real thing */
 	    p->numbytes = -1 ; /* mark not ready for I/O */
 	    break ;
 	}
     }
+    if (blh->elements == 0 && p->numbytes >= 0 && p->idle_heap.elements > 0) {
+	/*
+	 * no traffic and no events scheduled. We can get rid of idle-heap.
+	 */
+	int i ;
+
+	for (i = 0 ; i < p->idle_heap.elements ; i++) {
+	    struct dn_flow_queue *q = p->idle_heap.p[i].object ;
+
+	    q->F = 0 ;
+	    q->S = q->F + 1 ;
+	}
+	p->sum = 0 ;
+	p->V = 0 ;
+	p->idle_heap.elements = 0 ;
+    }
+
     /*
      * If we are getting clocks from dummynet (not a real interface) and
      * If we are under credit, schedule the next ready event.
@@ -745,6 +762,7 @@ if_tx_rdy(struct ifnet *ifp)
 	p->numbytes = 0 ; /* mark ready for I/O */
 	ready_event_wfq(p);
     }
+    return 0 ;
 }
 
 /*
@@ -762,7 +780,7 @@ expire_queues(struct dn_flow_set *fs)
     fs->last_expired = time_second ;
     for (i = 0 ; i <= fs->rq_size ; i++) /* last one is overflow */
 	for (prev=NULL, q = fs->rq[i] ; q != NULL ; )
-	    if (q->head != NULL) {
+	    if (q->head != NULL || q->S != q->F+1) {
   		prev = q ;
   	        q = q->next ;
   	    } else { /* entry is idle, expire it */
@@ -845,8 +863,8 @@ find_queue(struct dn_flow_set *fs)
 	    search_steps++;
 	    if (bcmp(&last_pkt, &(q->id), sizeof(q->id) ) == 0)
 		break ; /* found */
-	    else if (pipe_expire && q->head == NULL) {
-		/* entry is idle, expire it */
+	    else if (pipe_expire && q->head == NULL && q->S == q->F+1 ) {
+		/* entry is idle and not in any heap, expire it */
 		struct dn_flow_queue *old_q = q ;
 
 		if (prev != NULL)
@@ -1017,6 +1035,7 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
     s = splimp();
 
     pipe_nr &= 0xffff ;
+
     if ( (fs = rule->rule->pipe_ptr) == NULL ) {
 	fs = locate_flowset(pipe_nr, rule);
 	if (fs == NULL)
@@ -1033,7 +1052,7 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	    printf("No pipe %d for queue %d, drop pkt\n",
 		fs->parent_nr, fs->fs_nr);
 	    goto dropit ;
-    }
+	}
     }
     q = find_queue(fs);
     if ( q == NULL )
@@ -1095,28 +1114,34 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	static int errors = 0 ;
 	if (q->blh_pos >= 0 ) /* good... */
 	    goto done;
-	printf("+++ hey [%d] flow 0x%08x not idle but not in heap\n",
+	printf("+++ hey [%d] flow 0x%8p not idle but not in heap\n",
 	    ++errors, q);
     }
     /*
-     * The flow was previously idle, so we need to schedule it.
+     * If we reach this point the flow was previously idle, so we need
+     * to schedule it. This involves different actions for fixed-rate or
+     * WF2Q queues.
      */
     if ( (rule->rule->fw_flg & IP_FW_F_COMMAND) == IP_FW_F_PIPE ) {
-	/* fixed-rate queue: just insert into the ready_heap. */
+	/*
+	 * Fixed-rate queue: just insert into the ready_heap.
+	 */
 	dn_key t = 0 ;
 	if (pipe->bandwidth) 
 	    t = SET_TICKS(pkt, q, pipe);
 	q->sched_time = curr_time ;
 	if (t == 0)	/* must process it now */
-	ready_event( q );
+	    ready_event( q );
 	else
 	    heap_insert(&ready_heap, curr_time + t , q );
     } else {
 	/*
-	 * WF2Q: compute start time and put into backlogged list. Then
-	 * look at eligibility -- if not eligibile, it means that
-	 * there is some other flow already scheduled for the same pipe.
-	 * If eligible, AND the pipe is idle, then call ready_event_wfq().
+	 * WF2Q: first compute start time S. If the flow was not in the
+	 * idle_heap (denoted by S=F+1), S is set to the virtual time V
+	 * for that pipe, and we update the sum of weights for the pipe.
+	 * Otherwise, remove flow from idle_heap and set S to max(F,V).
+	 * Then compute finish time F = S + len/weight, and insert into
+	 * backlogged_heap according to S.
 	 */
 	if (DN_KEY_GT(q->S, q->F)) { /* means timestamps are invalid */
 	    q->S = pipe->V ;
@@ -1129,8 +1154,20 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 
 	heap_insert(&(pipe->backlogged_heap), q->S, q);
 	fs->backlogged++ ;
+	if (pipe->backlogged_heap.elements == 1)
+	    pipe->V = MAX64 ( q->S, pipe->V );
+	/*
+	 * Look at eligibility. A flow is not eligibile if S>V (when
+	 * this happens, it means that there is some other flow already
+	 * scheduled for the same pipe, so the scheduler_heap cannot be
+	 * empty). If the flow is not eligible we just store it in the
+	 * appropriate heap. Otherwise, we store in the scheduler_heap
+	 * and possibly invoke ready_event_wfq() right now if there is
+	 * leftover credit.
+	 */
 	if (DN_KEY_GT(q->S, pipe->V) ) { /* not eligible */
-	    DDB(printf("== not eligible, size %d\n", (int)len);)
+	    if (pipe->scheduler_heap.elements == 0)
+		printf("++ ouch! not eligible but empty scheduler!\n");
 	    heap_insert(&(pipe->not_eligible_heap), q->S, q);
 	} else {
 	    heap_insert(&(pipe->scheduler_heap), q->F, q);
@@ -1153,7 +1190,7 @@ dropit:
     if (q)
 	q->drops++ ;
     m_freem(m);
-    return 0 ; /* XXX should I return an error ? */
+    return ENOBUFS ;
 }
 
 /*
@@ -1524,10 +1561,10 @@ config_pipe(struct dn_pipe *p)
     return 0 ;
 }
 
-	    /*
+/*
  * Helper function to remove from a heap queues which are linked to
  * a flow_set about to be deleted.
-	     */
+*/
 static void
 fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs)
 {
@@ -1553,9 +1590,9 @@ pipe_remove_from_heap(struct dn_heap *h, struct dn_pipe *p)
 	int i = 0 ;
 	for (i=0; i < h->elements ; i++ ) {
 	    if (h->p[i].object == p) { /* found it */
-			h->elements-- ;
-			h->p[i] = h->p[h->elements] ;
-		    heapify(h);
+		h->elements-- ;
+		h->p[i] = h->p[h->elements] ;
+		heapify(h);
 		break ;
 	    }
 	}
@@ -1635,8 +1672,8 @@ delete_pipe(struct dn_pipe *p)
 	/* remove reference to here from extract_heap and wfq_ready_heap */
 	pipe_remove_from_heap(&extract_heap, b);
 	pipe_remove_from_heap(&wfq_ready_heap, b);
-	    splx(s);
-	    free(b, M_IPFW);
+	splx(s);
+	free(b, M_IPFW);
     } else { /* this is a dummynet queue (dn_flow_set) */
 	struct dn_flow_set *a, *b;
 
@@ -1662,7 +1699,7 @@ 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 ? */
+#if 1	/* XXX should i remove from idle_heap as well ? */
 	    fs_remove_from_heap(&(b->pipe->idle_heap), b);
 #endif
 	}
@@ -1817,7 +1854,7 @@ ip_dn_ctl(struct sockopt *sopt)
 static void
 ip_dn_init(void)
 {
-    printf("DUMMYNET initialized (010116)\n");
+    printf("DUMMYNET initialized (010124)\n");
     all_pipes = NULL ;
     all_flow_sets = NULL ;
     ready_heap.size = ready_heap.elements = 0 ;