Fix some problems with multicast forwarding:

Garrett,

  Here are some patches for the rate limiting code.  It should be faster,
and in particular it doesn't leak malloc'd memory any more when rate_limit'ing
a phyint.

  It now uses an mbuf chain at each vif, instead of the static queue array.
This means that the MAXQSIZE is now variable per vif (although there is no
interface to change it other than a debugger); this is an area for more
experimentation.

  Bill

Submitted by:	Bill Fenner <fenner@parc.xerox.com>

2 files changed, 135 insertions, 137 deletions

diff --git a/sys/netinet/ip_mroute.c b/sys/netinet/ip_mroute.c
index 2fc8340..bb46c40 100644
--- a/sys/netinet/ip_mroute.c
+++ b/sys/netinet/ip_mroute.c
@@ -9,7 +9,7 @@
  * Modified by Bill Fenner, PARC, April 1995
  *
  * MROUTING Revision: 3.5
- * $Id: ip_mroute.c,v 1.20 1995/07/24 18:15:13 wollman Exp $
+ * $Id: ip_mroute.c,v 1.21 1995/07/26 18:05:11 wollman Exp $
  */
 
 
@@ -220,11 +220,10 @@ u_int		rsvpdebug = 0;	  /* rsvp debug level   */
 /*
  * Define the token bucket filter structures
  * tbftable -> each vif has one of these for storing info 
- * qtable   -> each interface has an associated queue of pkts 
  */
 
 struct tbf tbftable[MAXVIFS];
-struct pkt_queue qtable[MAXVIFS][MAXQSIZE];
+#define		TBF_REPROCESS	(hz / 100)	/* 100x / second */
 
 /*
  * 'Interfaces' associated with decapsulator (so we can tell
@@ -283,14 +282,12 @@ static int ip_mdq(struct mbuf *, struct ifnet *, struct mfc *,
 		  vifi_t);
 static void phyint_send(struct ip *, struct vif *, struct mbuf *);
 static void encap_send(struct ip *, struct vif *, struct mbuf *);
-static void tbf_control(struct vif *, struct mbuf *, struct ip *, u_long,
-		 struct ip_moptions *);
-static void tbf_queue(struct vif *, struct mbuf *, struct ip *, struct ip_moptions *);
+static void tbf_control(struct vif *, struct mbuf *, struct ip *, u_long);
+static void tbf_queue(struct vif *, struct mbuf *);
 static void tbf_process_q(struct vif *);
-static void tbf_dequeue(struct vif *, int);
 static void tbf_reprocess_q(void *);
 static int tbf_dq_sel(struct vif *, struct ip *);
-static void tbf_send_packet(struct vif *, struct mbuf *, struct ip_moptions *);
+static void tbf_send_packet(struct vif *, struct mbuf *);
 static void tbf_update_tokens(struct vif *);
 static int priority(struct vif *, struct ip *);
 void multiencap_decap(struct mbuf *);
@@ -564,7 +561,6 @@ X_ip_mrouter_done()
 	    (*ifp->if_ioctl)(ifp, SIOCDELMULTI, (caddr_t)&ifr);
 	}
     }
-    bzero((caddr_t)qtable, sizeof(qtable));
     bzero((caddr_t)tbftable, sizeof(tbftable));
     bzero((caddr_t)viftable, sizeof(viftable));
     numvifs = 0;
@@ -726,16 +722,19 @@ add_vif(vifcp)
     s = splnet();
     /* define parameters for the tbf structure */
     vifp->v_tbf = v_tbf;
-    vifp->v_tbf->q_len = 0;
-    vifp->v_tbf->n_tok = 0;
-    vifp->v_tbf->last_pkt_t = 0;
+    GET_TIME(vifp->v_tbf->tbf_last_pkt_t);
+    vifp->v_tbf->tbf_n_tok = 0;
+    vifp->v_tbf->tbf_q_len = 0;
+    vifp->v_tbf->tbf_max_q_len = MAXQSIZE;
+    vifp->v_tbf->tbf_q = vifp->v_tbf->tbf_t = NULL;
 
     vifp->v_flags     = vifcp->vifc_flags;
     vifp->v_threshold = vifcp->vifc_threshold;
     vifp->v_lcl_addr  = vifcp->vifc_lcl_addr;
     vifp->v_rmt_addr  = vifcp->vifc_rmt_addr;
     vifp->v_ifp       = ifp;
-    vifp->v_rate_limit= vifcp->vifc_rate_limit;
+    /* scaling up here allows division by 1024 in critical code */
+    vifp->v_rate_limit= vifcp->vifc_rate_limit * 1024 / 1000;
     vifp->v_rsvp_on   = 0;
     vifp->v_rsvpd     = NULL;
     /* initialize per vif pkt counters */
@@ -769,6 +768,7 @@ del_vif(vifip)
 {
     register struct vif *vifp = viftable + *vifip;
     register vifi_t vifi;
+    register struct mbuf *m;
     struct ifnet *ifp;
     struct ifreq ifr;
     int s;
@@ -790,8 +790,15 @@ del_vif(vifip)
 	last_encap_src = 0;
     }
 
-    bzero((caddr_t)qtable[*vifip],
-	  sizeof(qtable[*vifip]));
+    /*
+     * Free packets queued at the interface
+     */
+    while (vifp->v_tbf->tbf_q) {
+	m = vifp->v_tbf->tbf_q;
+	vifp->v_tbf->tbf_q = m->m_act;
+	m_freem(m);
+    }
+
     bzero((caddr_t)vifp->v_tbf, sizeof(*(vifp->v_tbf)));
     bzero((caddr_t)vifp, sizeof (*vifp));
 
@@ -1518,7 +1525,6 @@ phyint_send(ip, vifp, m)
 {
     register struct mbuf *mb_copy;
     register int hlen = ip->ip_hl << 2;
-    register struct ip_moptions *imo;
 
     /*
      * Make a new reference to the packet; make sure that
@@ -1531,22 +1537,10 @@ phyint_send(ip, vifp, m)
     if (mb_copy == NULL)
 	return;
 
-    MALLOC(imo, struct ip_moptions *, sizeof *imo, M_IPMOPTS, M_NOWAIT);
-    if (imo == NULL) {
-	m_freem(mb_copy);
-	return;
-    }
-
-    imo->imo_multicast_ifp  = vifp->v_ifp;
-    imo->imo_multicast_ttl  = ip->ip_ttl - 1;
-    imo->imo_multicast_loop = 1;
-    imo->imo_multicast_vif  = -1;
-
     if (vifp->v_rate_limit <= 0)
-	tbf_send_packet(vifp, mb_copy, imo);
+	tbf_send_packet(vifp, mb_copy);
     else
-	tbf_control(vifp, mb_copy, mtod(mb_copy, struct ip *), ip->ip_len,
-		    imo);
+	tbf_control(vifp, mb_copy, mtod(mb_copy, struct ip *), ip->ip_len);
 }
 
 static void
@@ -1610,9 +1604,9 @@ encap_send(ip, vifp, m)
 #endif
 
     if (vifp->v_rate_limit <= 0)
-	tbf_send_packet(vifp, mb_copy, 0);
+	tbf_send_packet(vifp, mb_copy);
     else
-	tbf_control(vifp, mb_copy, ip, ip_copy->ip_len, 0);
+	tbf_control(vifp, mb_copy, ip, ip_copy->ip_len);
 }
 
 /*
@@ -1706,14 +1700,23 @@ ipip_input(m, iphlen)
 /*
  * Token bucket filter module
  */
+
 static void
-tbf_control(vifp, m, ip, p_len, imo)
+tbf_control(vifp, m, ip, p_len)
 	register struct vif *vifp;
 	register struct mbuf *m;
 	register struct ip *ip;
 	register u_long p_len;
-	struct ip_moptions *imo;
 {
+    register struct tbf *t = vifp->v_tbf;
+
+    if (p_len > MAX_BKT_SIZE) {
+	/* drop if packet is too large */
+	mrtstat.mrts_pkt2large++;
+	m_freem(m);
+	return;
+    }
+
     tbf_update_tokens(vifp);
 
     /* if there are enough tokens, 
@@ -1721,23 +1724,19 @@ tbf_control(vifp, m, ip, p_len, imo)
      * send this packet out
      */
 
-    if (vifp->v_tbf->q_len == 0) {
-	if (p_len <= vifp->v_tbf->n_tok) {
-	    vifp->v_tbf->n_tok -= p_len;
-	    tbf_send_packet(vifp, m, imo);
-	} else if (p_len > MAX_BKT_SIZE) {
-	    /* drop if packet is too large */
-	    mrtstat.mrts_pkt2large++;
-	    m_freem(m);
-	    return;
+    if (t->tbf_q_len == 0) {
+	/* queue empty, send packet if enough tokens */
+	if (p_len <= t->tbf_n_tok) {
+	    t->tbf_n_tok -= p_len;
+	    tbf_send_packet(vifp, m);
 	} else {
 	    /* queue packet and timeout till later */
-	    tbf_queue(vifp, m, ip, imo);
-	    timeout(tbf_reprocess_q, (caddr_t)vifp, 1);
+	    tbf_queue(vifp, m);
+	    timeout(tbf_reprocess_q, (caddr_t)vifp, TBF_REPROCESS);
 	}
-    } else if (vifp->v_tbf->q_len < MAXQSIZE) {
+    } else if (t->tbf_q_len < t->tbf_max_q_len) {
 	/* finite queue length, so queue pkts and process queue */
-	tbf_queue(vifp, m, ip, imo);
+	tbf_queue(vifp, m);
 	tbf_process_q(vifp);
     } else {
 	/* queue length too much, try to dq and queue and process */
@@ -1746,7 +1745,7 @@ tbf_control(vifp, m, ip, p_len, imo)
 	    m_freem(m);
 	    return;
 	} else {
-	    tbf_queue(vifp, m, ip, imo);
+	    tbf_queue(vifp, m);
 	    tbf_process_q(vifp);
 	}
     }
@@ -1757,24 +1756,33 @@ tbf_control(vifp, m, ip, p_len, imo)
  * adds a packet to the queue at the interface
  */
 static void
-tbf_queue(vifp, m, ip, imo) 
+tbf_queue(vifp, m) 
 	register struct vif *vifp;
 	register struct mbuf *m;
-	register struct ip *ip;
-	struct ip_moptions *imo;
 {
-    register u_long ql;
-    register int index = (vifp - viftable);
     register int s = splnet();
+    register struct tbf *t = vifp->v_tbf;
 
-    ql = vifp->v_tbf->q_len;
+    if (t->tbf_t == NULL) {
+	/* Queue was empty */
+	t->tbf_q = m;
+    } else {
+	/* Insert at tail */
+	t->tbf_t->m_act = m;
+    }
 
-    qtable[index][ql].pkt_m = m;
-    qtable[index][ql].pkt_len = (mtod(m, struct ip *))->ip_len;
-    qtable[index][ql].pkt_ip = ip;
-    qtable[index][ql].pkt_imo = imo;
+    /* Set new tail pointer */
+    t->tbf_t = m;
+
+#ifdef DIAGNOSTIC
+    /* Make sure we didn't get fed a bogus mbuf */
+    if (m->m_act)
+	panic("tbf_queue: m_act");
+#endif
+    m->m_act = NULL;
+
+    t->tbf_q_len++;
 
-    vifp->v_tbf->q_len++;
     splx(s);
 }
 
@@ -1786,65 +1794,39 @@ static void
 tbf_process_q(vifp)
     register struct vif *vifp;
 {
-    register struct pkt_queue pkt_1;
-    register int index = (vifp - viftable);
+    register struct mbuf *m;
+    register int len;
     register int s = splnet();
+    register struct tbf *t = vifp->v_tbf;
 
     /* loop through the queue at the interface and send as many packets
      * as possible
      */
-    while (vifp->v_tbf->q_len > 0) {
-	/* locate the first packet */
-	pkt_1.pkt_len = (qtable[index][0]).pkt_len;
-	pkt_1.pkt_m   = (qtable[index][0]).pkt_m;
-	pkt_1.pkt_ip   = (qtable[index][0]).pkt_ip;
-	pkt_1.pkt_imo = (qtable[index][0]).pkt_imo;
+    while (t->tbf_q_len > 0) {
+	m = t->tbf_q;
+
+	len = mtod(m, struct ip *)->ip_len;
 
 	/* determine if the packet can be sent */
-	if (pkt_1.pkt_len <= vifp->v_tbf->n_tok) {
+	if (len <= t->tbf_n_tok) {
 	    /* if so,
-	     * reduce no of tokens, dequeue the queue,
+	     * reduce no of tokens, dequeue the packet,
 	     * send the packet.
 	     */
-	    vifp->v_tbf->n_tok -= pkt_1.pkt_len;
+	    t->tbf_n_tok -= len;
 
-	    tbf_dequeue(vifp, 0);
+	    t->tbf_q = m->m_act;
+	    if (--t->tbf_q_len == 0)
+		t->tbf_t = NULL;
 
-	    tbf_send_packet(vifp, pkt_1.pkt_m, pkt_1.pkt_imo);
+	    m->m_act = NULL;
+	    tbf_send_packet(vifp, m);
 
 	} else break;
     }
     splx(s);
 }
 
-/* 
- * removes the jth packet from the queue at the interface
- */
-static void
-tbf_dequeue(vifp,j) 
-    register struct vif *vifp;
-    register int j;
-{
-    register u_long index = vifp - viftable;
-    register int i;
-
-    for (i=j+1; i <= vifp->v_tbf->q_len - 1; i++) {
-	qtable[index][i-1].pkt_m   = qtable[index][i].pkt_m;
-	qtable[index][i-1].pkt_len = qtable[index][i].pkt_len;
-	qtable[index][i-1].pkt_ip = qtable[index][i].pkt_ip;
-	qtable[index][i-1].pkt_imo = qtable[index][i].pkt_imo;
-    }		
-    qtable[index][i-1].pkt_m = NULL;
-    qtable[index][i-1].pkt_len = NULL;
-    qtable[index][i-1].pkt_ip = NULL;
-    qtable[index][i-1].pkt_imo = NULL;
-
-    vifp->v_tbf->q_len--;
-
-    if (tbfdebug > 1)
-	log(LOG_DEBUG, "tbf_dequeue: vif# %d qlen %d",vifp-viftable, i-1);
-}
-
 static void
 tbf_reprocess_q(xvifp)
 	void *xvifp;
@@ -1857,13 +1839,12 @@ tbf_reprocess_q(xvifp)
 
     tbf_process_q(vifp);
 
-    if (vifp->v_tbf->q_len)
-	timeout(tbf_reprocess_q, (caddr_t)vifp, 1);
+    if (vifp->v_tbf->tbf_q_len)
+	timeout(tbf_reprocess_q, (caddr_t)vifp, TBF_REPROCESS);
 }
 
 /* function that will selectively discard a member of the queue
- * based on the precedence value and the priority obtained through
- * a lookup table - not yet implemented accurately!
+ * based on the precedence value and the priority
  */
 static int
 tbf_dq_sel(vifp, ip)
@@ -1873,40 +1854,57 @@ tbf_dq_sel(vifp, ip)
     register int i;
     register int s = splnet();
     register u_int p;
+    register struct mbuf *m, *last;
+    register struct mbuf **np;
+    register struct tbf *t = vifp->v_tbf;
 
     p = priority(vifp, ip);
 
-    for(i=vifp->v_tbf->q_len-1;i >= 0;i--) {
-	if (p > priority(vifp, qtable[vifp-viftable][i].pkt_ip)) {
-	    m_freem(qtable[vifp-viftable][i].pkt_m);
-	    tbf_dequeue(vifp,i);
+    np = &t->tbf_q;
+    last = NULL;
+    while ((m = *np) != NULL) {
+	if (p > priority(vifp, mtod(m, struct ip *))) {
+	    *np = m->m_act;
+	    /* If we're removing the last packet, fix the tail pointer */
+	    if (m == t->tbf_t)
+		t->tbf_t = last;
+	    m_freem(m);
+	    /* it's impossible for the queue to be empty, but
+	     * we check anyway. */
+	    if (--t->tbf_q_len == 0)
+		t->tbf_t = NULL;
 	    splx(s);
 	    mrtstat.mrts_drop_sel++;
 	    return(1);
 	}
+	np = &m->m_act;
+	last = m;
     }
     splx(s);
     return(0);
 }
 
 static void
-tbf_send_packet(vifp, m, imo)
+tbf_send_packet(vifp, m)
     register struct vif *vifp;
     register struct mbuf *m;
-    struct ip_moptions *imo;
 {
+    struct ip_moptions imo;
     int error;
     int s = splnet();
 
     if (vifp->v_flags & VIFF_TUNNEL) {
 	/* If tunnel options */
 	ip_output(m, (struct mbuf *)0, (struct route *)0,
-		  IP_FORWARDING, imo);
+		  IP_FORWARDING, (struct ip_moptions *)0);
     } else {
-	/* if physical interface option, extract the options and then send */
+	imo.imo_multicast_ifp  = vifp->v_ifp;
+	imo.imo_multicast_ttl  = mtod(m, struct ip *)->ip_ttl - 1;
+	imo.imo_multicast_loop = 1;
+	imo.imo_multicast_vif  = -1;
+
 	error = ip_output(m, (struct mbuf *)0, (struct route *)0,
-			  IP_FORWARDING, imo);
-	FREE(imo, M_IPMOPTS);
+			  IP_FORWARDING, &imo);
 
 	if (mrtdebug & DEBUG_XMIT)
 	    log(LOG_DEBUG, "phyint_send on vif %d err %d", vifp-viftable, error);
@@ -1923,20 +1921,28 @@ tbf_update_tokens(vifp)
     register struct vif *vifp;
 {
     struct timeval tp;
-    register u_long t;
-    register u_long elapsed;
+    register u_long tm;
     register int s = splnet();
+    register struct tbf *t = vifp->v_tbf;
 
     GET_TIME(tp);
 
-    t = tp.tv_sec*1000 + tp.tv_usec/1000;
+    TV_DELTA(tp, t->tbf_last_pkt_t, tm);
 
-    elapsed = (t - vifp->v_tbf->last_pkt_t) * vifp->v_rate_limit /8;
-    vifp->v_tbf->n_tok += elapsed;
-    vifp->v_tbf->last_pkt_t = t;
+    /*
+     * This formula is actually
+     * "time in seconds" * "bytes/second".
+     *
+     * (tm / 1000000) * (v_rate_limit * 1000 * (1000/1024) / 8)
+     *
+     * The (1000/1024) was introduced in add_vif to optimize
+     * this divide into a shift.
+     */
+    t->tbf_n_tok += tm * vifp->v_rate_limit / 1024 / 8;
+    t->tbf_last_pkt_t = tp;
 
-    if (vifp->v_tbf->n_tok > MAX_BKT_SIZE)
-	vifp->v_tbf->n_tok = MAX_BKT_SIZE;
+    if (t->tbf_n_tok > MAX_BKT_SIZE)
+	t->tbf_n_tok = MAX_BKT_SIZE;
 
     splx(s);
 }
diff --git a/sys/netinet/ip_mroute.h b/sys/netinet/ip_mroute.h
index fd5ef37..d425993 100644
--- a/sys/netinet/ip_mroute.h
+++ b/sys/netinet/ip_mroute.h
@@ -35,7 +35,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)ip_mroute.h	8.1 (Berkeley) 6/10/93
- * $Id: ip_mroute.h,v 1.6 1995/03/16 18:14:59 bde Exp $
+ * $Id: ip_mroute.h,v 1.8 1995/06/13 17:51:13 wollman Exp $
  */
 
 #ifndef _NETINET_IP_MROUTE_H_
@@ -236,24 +236,16 @@ struct rtdetq {
 #define MAXQSIZE        10                /* max # of pkts in queue 	*/
 
 /*
- * queue structure at each vif
- */
-struct pkt_queue 
-{
-    u_long pkt_len;               /* length of packet in queue 	*/
-    struct mbuf *pkt_m;           /* pointer to packet mbuf	*/
-    struct ip  *pkt_ip;           /* pointer to ip header	*/
-    struct ip_moptions *pkt_imo; /* IP multicast options assoc. with pkt */
-};
-
-/*
  * the token bucket filter at each vif
  */
 struct tbf
 {
-    u_long last_pkt_t;	/* arr. time of last pkt 	*/
-    u_long n_tok;      	/* no of tokens in bucket 	*/
-    u_long q_len;    	/* length of queue at this vif	*/
+    struct timeval tbf_last_pkt_t; /* arr. time of last pkt 	*/
+    u_long tbf_n_tok;      	/* no of tokens in bucket 	*/
+    u_long tbf_q_len;    	/* length of queue at this vif	*/
+    u_long tbf_max_q_len;	/* max. queue length		*/
+    struct mbuf *tbf_q;		/* Packet queue			*/
+    struct mbuf *tbf_t;		/* tail-insertion pointer	*/
 };
 
 extern int	(*ip_mrouter_set) __P((int, struct socket *, struct mbuf *));