MFS: bridge/ipfw/dummynet fixes (bridge.c will be committed separately)

8 files changed, 143 insertions, 70 deletions

diff --git a/sys/net/bridge.h b/sys/net/bridge.h
index 246bb87..4f81ebe 100644
--- a/sys/net/bridge.h
+++ b/sys/net/bridge.h
@@ -37,8 +37,43 @@ typedef struct hash_table {
 
 extern bdg_hash_table *bdg_table ;
 
+/*
+ * We need additional info for the bridge. The bdg_ifp2sc[] array
+ * provides a pointer to this struct using the if_index.   
+ * bdg_softc has a backpointer to the struct ifnet, the bridge
+ * flags, and a cluster (bridging occurs only between port of the
+ * same cluster).
+ */
+struct bdg_softc {
+    struct ifnet *ifp ;
+    /* also ((struct arpcom *)ifp)->ac_enaddr is the eth. addr */
+    int flags ;
+#define IFF_BDG_PROMISC 0x0001  /* set promisc mode on this if.  */
+#define IFF_MUTE        0x0002  /* mute this if for bridging.   */
+#define IFF_USED        0x0004  /* use this if for bridging.    */
+    short cluster_id ; /* in network format */
+    u_long magic;
+} ;
+
+extern struct bdg_softc *ifp2sc;
+
+#define BDG_USED(ifp) (ifp2sc[ifp->if_index].flags & IFF_USED)
+#define BDG_MUTED(ifp) (ifp2sc[ifp->if_index].flags & IFF_MUTE)
+#define BDG_MUTE(ifp) ifp2sc[ifp->if_index].flags |= IFF_MUTE
+#define BDG_UNMUTE(ifp) ifp2sc[ifp->if_index].flags &= ~IFF_MUTE
+#define BDG_CLUSTER(ifp) (ifp2sc[ifp->if_index].cluster_id)
+#define BDG_EH(ifp)	((struct arpcom *)ifp)->ac_enaddr
+
+#define BDG_SAMECLUSTER(ifp,src) \
+	(src == NULL || BDG_CLUSTER(ifp) == BDG_CLUSTER(src) )
+
+
 #define BDG_MAX_PORTS 128
-extern unsigned char bdg_addresses[6*BDG_MAX_PORTS];
+typedef struct _bdg_addr {
+    unsigned char etheraddr[6] ;
+    short cluster_id ;
+} bdg_addr ;
+extern bdg_addr bdg_addresses[BDG_MAX_PORTS];
 extern int bdg_ports ;
 
 extern void bdgtakeifaces(void);
@@ -53,7 +88,7 @@ extern void bdgtakeifaces(void);
 
 struct ifnet *bridge_in(struct ifnet *ifp, struct ether_header *eh);
 /* bdg_forward frees the mbuf if necessary, returning null */
-int bdg_forward(struct mbuf **m0, struct ether_header *eh, struct ifnet *dst);
+struct mbuf *bdg_forward(struct mbuf *m0, struct ether_header *eh, struct ifnet *dst);
 
 #ifdef __i386__
 #define BDG_MATCH(a,b) ( \
@@ -108,6 +143,9 @@ struct bdg_stats {
  *	BDG_LOCAL	is for a local address
  *	BDG_DROP	must be dropped
  *	other		ifp of the dest. interface (incl.self)
+ *
+ * We assume this is only called for interfaces for which bridging
+ * is enabled, i.e. BDG_USED(ifp) is true.
  */
 static __inline
 struct ifnet *
@@ -115,7 +153,7 @@ bridge_dst_lookup(struct ether_header *eh)
 {
     struct ifnet *dst ;
     int index ;
-    u_char *eth_addr = bdg_addresses ;
+    bdg_addr *p ;
 
     if (IS_ETHER_BROADCAST(eh->ether_dhost))
 	return BDG_BCAST ;
@@ -124,9 +162,8 @@ bridge_dst_lookup(struct ether_header *eh)
     /*
      * Lookup local addresses in case one matches.
      */
-    for (index = bdg_ports, eth_addr = bdg_addresses ;
-		 index ; index--, eth_addr += 6 )
-	if (BDG_MATCH(eth_addr, eh->ether_dhost) )
+    for (index = bdg_ports, p = bdg_addresses ; index ; index--, p++ )
+	if (BDG_MATCH(p->etheraddr, eh->ether_dhost) )
 	    return BDG_LOCAL ;
     /*
      * Look for a possible destination in table
diff --git a/sys/net/if_ethersubr.c b/sys/net/if_ethersubr.c
index 0bbb2c3..ed7fa57 100644
--- a/sys/net/if_ethersubr.c
+++ b/sys/net/if_ethersubr.c
@@ -362,14 +362,18 @@ ether_output_frame(ifp, m)
 	int error = 0;
 
 #ifdef BRIDGE
-	if (do_bridge) {
-		struct ether_header hdr;
+	if (do_bridge && BDG_USED(ifp) ) {
+		struct ether_header *eh; /* a ptr suffices */
+		struct ifnet *oifp = ifp ;
 
 		m->m_pkthdr.rcvif = NULL;
-		bcopy(mtod(m, struct ether_header *), &hdr, ETHER_HDR_LEN);
+		eh = mtod(m, struct ether_header *);
 		m_adj(m, ETHER_HDR_LEN);
-		ifp = bridge_dst_lookup(&hdr);
-		bdg_forward(&m, &hdr, ifp);
+		ifp = bridge_dst_lookup(eh);
+		if (ifp > BDG_FORWARD && !BDG_SAMECLUSTER(ifp, oifp)) {
+			printf("ether_out_frame: bad output if\n");
+		}
+		m = bdg_forward(m, eh, ifp);
 		if (m != NULL)
 			m_freem(m);
 		return (0);
@@ -408,6 +412,7 @@ ether_input(ifp, eh, m)
 	struct ether_header *eh;
 	struct mbuf *m;
 {
+	struct ether_header save_eh;
 
 	/* Check for a BPF tap */
 	if (ifp->if_bpf != NULL) {
@@ -429,7 +434,7 @@ ether_input(ifp, eh, m)
 
 #ifdef BRIDGE
 	/* Check for bridging mode */
-	if (do_bridge) {
+	if (do_bridge && BDG_USED(ifp) ) {
 		struct ifnet *bif;
 
 		/* Check with bridging code */
@@ -438,14 +443,22 @@ ether_input(ifp, eh, m)
 			return;
 		}
 		if (bif != BDG_LOCAL) {
-			bdg_forward(&m, eh, bif);	/* needs forwarding */
+			struct mbuf *oldm = m ;
+
+			save_eh = *eh ; /* because it might change */
+			m = bdg_forward(&m, eh, bif);	/* needs forwarding */
 			/*
 			 * Do not continue if bdg_forward() processed our
 			 * packet (and cleared the mbuf pointer m) or if
 			 * it dropped (m_free'd) the packet itself.
 			 */
-			if (m == NULL)
-				return;
+			if (m == NULL) {
+			    if (bif == BDG_BCAST || bif == BDG_MCAST)
+				printf("bdg_forward drop MULTICAST PKT\n");
+			    return;
+			}
+			if (m != oldm) /* m changed! */
+			    eh = &save_eh ;
 		}
 		if (bif == BDG_LOCAL
 		    || bif == BDG_BCAST
@@ -454,7 +467,7 @@ ether_input(ifp, eh, m)
 
 		/* If not local and not multicast, just drop it */
 		if (m != NULL)
-			m_freem(m);
+		    m_freem(m);
 		return;
        }
 #endif
diff --git a/sys/netinet/ip_dummynet.c b/sys/netinet/ip_dummynet.c
index 908c064..8060437 100644
--- a/sys/netinet/ip_dummynet.c
+++ b/sys/netinet/ip_dummynet.c
@@ -313,8 +313,10 @@ heap_extract(struct dn_heap *h, void *obj)
     }
 }           
 
+#if 0
 /*
  * change object position and update references
+ * XXX this one is never used!
  */
 static void
 heap_move(struct dn_heap *h, dn_key new_key, void *object)
@@ -350,6 +352,7 @@ heap_move(struct dn_heap *h, dn_key new_key, void *object)
     }
     SET_OFFSET(h, i);
 }
+#endif /* heap_move, unused */
 
 /*
  * heapify() will reorganize data inside an array to maintain the
@@ -450,7 +453,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, eh, pkt->ifp);
+	    m = bdg_forward(&m, eh, pkt->ifp);
 	    if (m)
 		m_freem(m);
 	    }
@@ -577,7 +580,6 @@ 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 */
@@ -595,7 +597,7 @@ ready_event_wfq(struct dn_pipe *p)
      * While we have backlogged traffic AND credit, we need to do
      * something on the queue.
      */
-    while ( blh->elements>0 && p->numbytes >= 0 ) {
+    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_pkt *pkt = q->head;  
@@ -610,7 +612,6 @@ ready_event_wfq(struct dn_pipe *p)
 	    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 */
@@ -620,13 +621,21 @@ ready_event_wfq(struct dn_pipe *p)
 		 */
 		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);
+		if (DN_KEY_LEQ(q->S, p->V))
+		    heap_insert(neh, q->S, q);
+		else
+		    heap_insert(sch, q->F, q);
 	    }
 	}
-	if (blh->elements > 0)
-	    p->V = MAX64 ( p->V, blh->p[0].key );
-	/* move from not_eligible_heap to scheduler_heap */
+	/*
+	 * now compute V = max(V, min(S_i)). Remember that all elements in sch
+	 * have by definition S_i <= V so if sch is not empty, V is surely
+	 * the max and we must not update it. Conversely, 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 );
+	/* 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 ;
 	    heap_extract(neh, NULL);
@@ -638,7 +647,8 @@ ready_event_wfq(struct dn_pipe *p)
 	    break ;
 	}
     }
-    if (blh->elements == 0 && p->numbytes >= 0 && p->idle_heap.elements > 0) {
+    if (sch->elements == 0 && neh->elements == 0 && p->numbytes >= 0
+	    && p->idle_heap.elements > 0) {
 	/*
 	 * no traffic and no events scheduled. We can get rid of idle-heap.
 	 */
@@ -760,7 +770,7 @@ if_tx_rdy(struct ifnet *ifp)
 	p->numbytes = 0 ; /* mark ready for I/O */
 	ready_event_wfq(p);
     }
-    return 0 ;
+    return 0;
 }
 
 /*
@@ -1064,7 +1074,7 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	goto dropit ;		/* random pkt drop			*/
     if ( fs->flags_fs & DN_QSIZE_IS_BYTES) {
     	if (q->len_bytes > fs->qsize)
-	goto dropit ;		/* queue size overflow			*/
+	    goto dropit ;	/* queue size overflow			*/
     } else {
 	if (q->len >= fs->qsize)
 	    goto dropit ;	/* queue count overflow			*/
@@ -1108,13 +1118,8 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
     q->len++;
     q->len_bytes += len ;
 
-    if ( q->head != pkt ) {	/* flow was not idle, we are done */
-	static int errors = 0 ;
-	if (q->blh_pos >= 0 ) /* good... */
-	    goto done;
-	printf("+++ hey [%d] flow 0x%8p not idle but not in heap\n",
-	    ++errors, q);
-    }
+    if ( q->head != pkt )	/* flow was not idle, we are done */
+	goto done;
     /*
      * If we reach this point the flow was previously idle, so we need
      * to schedule it. This involves different actions for fixed-rate or
@@ -1134,12 +1139,13 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	    heap_insert(&ready_heap, curr_time + t , q );
     } else {
 	/*
-	 * 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.
+	 * WF2Q. First, compute start time S: if the flow was idle (S=F+1)
+	 * set S to the virtual time V for the controlling pipe, and update
+	 * the sum of weights for the pipe; otherwise, remove flow from
+	 * idle_heap and set S to max(F,V).
+	 * Second, compute finish time F = S + len/weight.
+	 * Third, if pipe was idle, update V=max(S, V).
+	 * Fourth, count one more backlogged flow.
 	 */
 	if (DN_KEY_GT(q->S, q->F)) { /* means timestamps are invalid */
 	    q->S = pipe->V ;
@@ -1150,18 +1156,22 @@ dummynet_io(int pipe_nr, int dir,	/* pipe_nr can also be a fs_nr */
 	}
 	q->F = q->S + ( len<<MY_M )/(u_int64_t) fs->weight;
 
-	heap_insert(&(pipe->backlogged_heap), q->S, q);
-	fs->backlogged++ ;
-	if (pipe->backlogged_heap.elements == 1)
+	if (pipe->not_eligible_heap.elements == 0 &&
+		pipe->scheduler_heap.elements == 0)
 	    pipe->V = MAX64 ( q->S, pipe->V );
+	fs->backlogged++ ;
 	/*
 	 * 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
+	 * not_eligible_heap. Otherwise, we store in the scheduler_heap
 	 * and possibly invoke ready_event_wfq() right now if there is
 	 * leftover credit.
+	 * Note that for all flows in scheduler_heap (SCH), S_i <= V,
+	 * and for all flows in not_eligible_heap (NEH), S_i > V .
+	 * So when we need to compute max( V, min(S_i) ) forall i in SCH+NEH,
+	 * we only need to look into NEH.
 	 */
 	if (DN_KEY_GT(q->S, pipe->V) ) { /* not eligible */
 	    if (pipe->scheduler_heap.elements == 0)
@@ -1254,7 +1264,6 @@ 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) );
 }
 
@@ -1478,14 +1487,10 @@ 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.
+	    /* idle_heap is the only one from which we extract from the middle.
 	     */
-	    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);
+	    x->idle_heap.offset=OFFSET_OF(struct dn_flow_queue, heap_pos);
 	} else
 	    x = b;
 
@@ -1562,7 +1567,7 @@ 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.
-*/
+ */
 static void
 fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs)
 {
@@ -1694,7 +1699,6 @@ delete_pipe(struct dn_pipe *p)
 	if (b->pipe != NULL) {
 	    /* Update total weight on parent pipe and cleanup parent heaps */
 	    b->pipe->sum -= b->weight * b->backlogged ;
-	    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 1	/* XXX should i remove from idle_heap as well ? */
@@ -1856,12 +1860,10 @@ ip_dn_init(void)
     all_pipes = NULL ;
     all_flow_sets = NULL ;
     ready_heap.size = ready_heap.elements = 0 ;
-    /* ready_heap.offset = 0 ; */
-    ready_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos);
+    ready_heap.offset = 0 ;
 
     wfq_ready_heap.size = wfq_ready_heap.elements = 0 ;
-    /* wfq_ready_heap.offset = 0 ; */
-    wfq_ready_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos);
+    wfq_ready_heap.offset = 0 ;
 
     extract_heap.size = extract_heap.elements = 0 ;
     extract_heap.offset = 0 ;
diff --git a/sys/netinet/ip_dummynet.h b/sys/netinet/ip_dummynet.h
index 5578525..fe80718 100644
--- a/sys/netinet/ip_dummynet.h
+++ b/sys/netinet/ip_dummynet.h
@@ -224,7 +224,7 @@ struct dn_flow_queue {
 
     /* WF2Q+ support */
     struct dn_flow_set *fs ; /* parent flow set */
-    int blh_pos ;	/* position in backlogged_heap */
+    int heap_pos ;	/* position (index) of struct in heap */
     dn_key sched_time ; /* current time when queue enters ready_heap */
 
     dn_key S,F ; /* start-time, finishing time */
@@ -319,7 +319,6 @@ struct dn_pipe {			/* a pipe */
     /* WF2Q+ */
     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 */
diff --git a/sys/netinet/ip_fw.c b/sys/netinet/ip_fw.c
index ca112d5..1aefb7a 100644
--- a/sys/netinet/ip_fw.c
+++ b/sys/netinet/ip_fw.c
@@ -1445,10 +1445,8 @@ dropit:
 	/*
 	 * Finally, drop the packet.
 	 */
-	if (*m) {
-		m_freem(*m);
-		*m = NULL;
-	}
+	if (*m)
+		return(IP_FW_PORT_DENY_FLAG);
 	return(0);
 #undef BRIDGED
 }
diff --git a/sys/netinet/ip_fw.h b/sys/netinet/ip_fw.h
index a642d72..3d639d1 100644
--- a/sys/netinet/ip_fw.h
+++ b/sys/netinet/ip_fw.h
@@ -283,6 +283,7 @@ struct ipfw_dyn_rule {
 
 #define IP_FW_PORT_DYNT_FLAG	0x10000
 #define IP_FW_PORT_TEE_FLAG	0x20000
+#define IP_FW_PORT_DENY_FLAG	0x40000
 
 /*
  * Function definitions.
diff --git a/sys/netinet/ip_input.c b/sys/netinet/ip_input.c
index 63e10c8..c73db86 100644
--- a/sys/netinet/ip_input.c
+++ b/sys/netinet/ip_input.c
@@ -419,8 +419,19 @@ iphack:
 		 */
 		i = (*ip_fw_chk_ptr)(&ip,
 		    hlen, NULL, &divert_cookie, &m, &rule, &ip_fw_fwd_addr);
-		if (m == NULL)		/* Packet discarded by firewall */
-			return;
+		if (i & IP_FW_PORT_DENY_FLAG) { /* XXX new interface-denied */
+		    if (m)
+			m_freem(m);
+		    return ;
+		}
+		if (m == NULL) {	/* Packet discarded by firewall */
+		    static int __debug=10;
+		    if (__debug >0) {
+			printf("firewall returns NULL, please update!\n");	
+			__debug-- ;
+		    }
+		    return;
+		}
 		if (i == 0 && ip_fw_fwd_addr == NULL)	/* common case */
 			goto pass;
 #ifdef DUMMYNET
diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c
index 4eff375..1b19fd7 100644
--- a/sys/netinet/ip_output.c
+++ b/sys/netinet/ip_output.c
@@ -465,7 +465,8 @@ sendit:
 		    hlen, ifp, &divert_cookie, &m, &rule, &dst);
                 /*
                  * On return we must do the following:
-                 * m == NULL         -> drop the pkt
+                 * m == NULL         -> drop the pkt (old interface, deprecated)
+                 * (off & 0x40000)   -> drop the pkt (new interface)
                  * 1<=off<= 0xffff   -> DIVERT
                  * (off & 0x10000)   -> send to a DUMMYNET pipe
                  * (off & 0x20000)   -> TEE the packet
@@ -477,9 +478,20 @@ sendit:
                  * unsupported rules), but better play safe and drop
                  * packets in case of doubt.
                  */
+		if (off & IP_FW_PORT_DENY_FLAG) { /* XXX new interface-denied */
+		    if (m)
+			m_freem(m);
+		    error = EACCES ;
+		    goto done;
+		}
 		if (!m) { /* firewall said to reject */
-			error = EACCES;
-			goto done;
+		    static int __debug=10;
+		    if (__debug >0) {
+			printf("firewall returns NULL, please update!\n");	
+			__debug-- ;
+		    }
+		    error = EACCES;
+		    goto done;
 		}
 		if (off == 0 && dst == old) /* common case */
 			goto pass ;
@@ -495,7 +507,7 @@ sendit:
                      * while a pkt is in dummynet, we are in trouble!
                      */ 
 		    error = dummynet_io(off & 0xffff, DN_TO_IP_OUT, m,
-				ifp, ro, dst, rule, flags);
+				ifp,ro,dst,rule, flags);
 		    goto done;
 		}
 #endif