ip_mroute.c

RTEMS (Real-Time Executive for Multiprocessor Systems) is a free open source real-time operating sys

/*
 * IP multicast forwarding procedures
 *
 * Written by David Waitzman, BBN Labs, August 1988.
 * Modified by Steve Deering, Stanford, February 1989.
 * Modified by Mark J. Steiglitz, Stanford, May, 1991
 * Modified by Van Jacobson, LBL, January 1993
 * Modified by Ajit Thyagarajan, PARC, August 1993
 * Modified by Bill Fenner, PARC, April 1995
 *
 * MROUTING Revision: 3.5
 * $Id: ip_mroute.c,v 1.2 1998/08/21 13:04:54 joel Exp $
 */

#include "opt_mrouting.h"

#include <sys/param.h>
#include <sys/queue.h>
#include <sys/systm.h>
#include <sys/mbuf.h>
#include <sys/socket.h>
#include <sys/socketvar.h>
#include <sys/protosw.h>
#include <sys/errno.h>
#include <sys/time.h>
#include <sys/kernel.h>
#include <sys/ioctl.h>
#include <sys/syslog.h>
#include <net/if.h>
#include <net/route.h>
#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <netinet/ip_var.h>
#include <netinet/in_pcb.h>
#include <netinet/in_var.h>
#include <netinet/igmp.h>
#include <netinet/igmp_var.h>
#include <netinet/ip_mroute.h>
#include <netinet/udp.h>

#ifndef NTOHL
#if BYTE_ORDER != BIG_ENDIAN
#define NTOHL(d) ((d) = ntohl((d)))
#define NTOHS(d) ((d) = ntohs((u_short)(d)))
#define HTONL(d) ((d) = htonl((d)))
#define HTONS(d) ((d) = htons((u_short)(d)))
#else
#define NTOHL(d)
#define NTOHS(d)
#define HTONL(d)
#define HTONS(d)
#endif
#endif

#ifndef MROUTING
extern u_long	_ip_mcast_src __P((int vifi));
extern int	_ip_mforward __P((struct ip *ip, struct ifnet *ifp,
				  struct mbuf *m, struct ip_moptions *imo));
extern int	_ip_mrouter_done __P((void));
extern int	_ip_mrouter_get __P((int cmd, struct socket *so,
				     struct mbuf **m));
extern int	_ip_mrouter_set __P((int cmd, struct socket *so,
				     struct mbuf *m));
extern int	_mrt_ioctl __P((int req, caddr_t data, struct proc *p));

/*
 * Dummy routines and globals used when multicast routing is not compiled in.
 */

struct socket  *ip_mrouter  = NULL;
/* static u_int		ip_mrtproto = 0; */
/* static struct mrtstat	mrtstat; */
u_int		rsvpdebug = 0;

int
_ip_mrouter_set(cmd, so, m)
	int cmd;
	struct socket *so;
	struct mbuf *m;
{
	return(EOPNOTSUPP);
}

int (*ip_mrouter_set)(int, struct socket *, struct mbuf *) = _ip_mrouter_set;


int
_ip_mrouter_get(cmd, so, m)
	int cmd;
	struct socket *so;
	struct mbuf **m;
{
	return(EOPNOTSUPP);
}

int (*ip_mrouter_get)(int, struct socket *, struct mbuf **) = _ip_mrouter_get;

int
_ip_mrouter_done()
{
	return(0);
}

int (*ip_mrouter_done)(void) = _ip_mrouter_done;

int
_ip_mforward(ip, ifp, m, imo)
	struct ip *ip;
	struct ifnet *ifp;
	struct mbuf *m;
	struct ip_moptions *imo;
{
	return(0);
}

int (*ip_mforward)(struct ip *, struct ifnet *, struct mbuf *,
		   struct ip_moptions *) = _ip_mforward;

int
_mrt_ioctl(int req, caddr_t data, struct proc *p)
{
	return EOPNOTSUPP;
}

int (*mrt_ioctl)(int, caddr_t, struct proc *) = _mrt_ioctl;

void
rsvp_input(m, iphlen)		/* XXX must fixup manually */
	struct mbuf *m;
	int iphlen;
{
    /* Can still get packets with rsvp_on = 0 if there is a local member
     * of the group to which the RSVP packet is addressed.  But in this
     * case we want to throw the packet away.
     */
    if (!rsvp_on) {
	m_freem(m);
	return;
    }
 
    if (ip_rsvpd != NULL) {
	if (rsvpdebug)
	    printf("rsvp_input: Sending packet up old-style socket\n");
	rip_input(m, iphlen);
	return;
    }
    /* Drop the packet */
    m_freem(m);
}

void ipip_input(struct mbuf *m, int iphlen) { /* XXX must fixup manually */
	rip_input(m, iphlen);
}

int (*legal_vif_num)(int) = 0;

/*
 * This should never be called, since IP_MULTICAST_VIF should fail, but
 * just in case it does get called, the code a little lower in ip_output
 * will assign the packet a local address.
 */
u_long
_ip_mcast_src(int vifi) { return INADDR_ANY; }
u_long (*ip_mcast_src)(int) = _ip_mcast_src;

int
ip_rsvp_vif_init(so, m)
    struct socket *so;
    struct mbuf *m;
{
    return(EINVAL);
}

int
ip_rsvp_vif_done(so, m)
    struct socket *so;
    struct mbuf *m;
{
    return(EINVAL);
}

void
ip_rsvp_force_done(so)
    struct socket *so;
{
    return;
}

#else /* MROUTING */

#define M_HASCL(m)	((m)->m_flags & M_EXT)

#define INSIZ		sizeof(struct in_addr)
#define	same(a1, a2) \
	(bcmp((caddr_t)(a1), (caddr_t)(a2), INSIZ) == 0)

#define MT_MRTABLE MT_RTABLE	/* since nothing else uses it */

/*
 * Globals.  All but ip_mrouter and ip_mrtproto could be static,
 * except for netstat or debugging purposes.
 */
#ifndef MROUTE_LKM
struct socket  *ip_mrouter  = NULL;
struct mrtstat	mrtstat;

int		ip_mrtproto = IGMP_DVMRP;    /* for netstat only */
#else /* MROUTE_LKM */
extern void	X_ipip_input __P((struct mbuf *m, int iphlen));
extern struct mrtstat mrtstat;
static int ip_mrtproto;
#endif

#define NO_RTE_FOUND 	0x1
#define RTE_FOUND	0x2

static struct mbuf    *mfctable[MFCTBLSIZ];
static u_char		nexpire[MFCTBLSIZ];
static struct vif	viftable[MAXVIFS];
static u_int	mrtdebug = 0;	  /* debug level 	*/
#define		DEBUG_MFC	0x02
#define		DEBUG_FORWARD	0x04
#define		DEBUG_EXPIRE	0x08
#define		DEBUG_XMIT	0x10
static u_int  	tbfdebug = 0;     /* tbf debug level 	*/
static u_int	rsvpdebug = 0;	  /* rsvp debug level   */

#define		EXPIRE_TIMEOUT	(hz / 4)	/* 4x / second		*/
#define		UPCALL_EXPIRE	6		/* number of timeouts	*/

/*
 * Define the token bucket filter structures
 * tbftable -> each vif has one of these for storing info 
 */

static struct tbf tbftable[MAXVIFS];
#define		TBF_REPROCESS	(hz / 100)	/* 100x / second */

/*
 * 'Interfaces' associated with decapsulator (so we can tell
 * packets that went through it from ones that get reflected
 * by a broken gateway).  These interfaces are never linked into
 * the system ifnet list & no routes point to them.  I.e., packets
 * can't be sent this way.  They only exist as a placeholder for
 * multicast source verification.
 */
static struct ifnet multicast_decap_if[MAXVIFS];

#define ENCAP_TTL 64
#define ENCAP_PROTO IPPROTO_IPIP	/* 4 */

/* prototype IP hdr for encapsulated packets */
static struct ip multicast_encap_iphdr = {
#if BYTE_ORDER == LITTLE_ENDIAN
	sizeof(struct ip) >> 2, IPVERSION,
#else
	IPVERSION, sizeof(struct ip) >> 2,
#endif
	0,				/* tos */
	sizeof(struct ip),		/* total length */
	0,				/* id */
	0,				/* frag offset */
	ENCAP_TTL, ENCAP_PROTO,	
	0,				/* checksum */
};

/*
 * Private variables.
 */
static vifi_t	   numvifs = 0;
static int have_encap_tunnel = 0;

/*
 * one-back cache used by ipip_input to locate a tunnel's vif
 * given a datagram's src ip address.
 */
static u_long last_encap_src;
static struct vif *last_encap_vif;

static u_long	X_ip_mcast_src __P((int vifi));
static int	X_ip_mforward __P((struct ip *ip, struct ifnet *ifp, struct mbuf *m, struct ip_moptions *imo));
static int	X_ip_mrouter_done __P((void));
static int	X_ip_mrouter_get __P((int cmd, struct socket *so, struct mbuf **m));
static int	X_ip_mrouter_set __P((int cmd, struct socket *so, struct mbuf *m));
static int	X_legal_vif_num __P((int vif));
static int	X_mrt_ioctl __P((int cmd, caddr_t data));

static int get_sg_cnt(struct sioc_sg_req *);
static int get_vif_cnt(struct sioc_vif_req *);
static int ip_mrouter_init(struct socket *, struct mbuf *);
static int add_vif(struct vifctl *);
static int del_vif(vifi_t *);
static int add_mfc(struct mfcctl *);
static int del_mfc(struct mfcctl *);
static int socket_send(struct socket *, struct mbuf *, struct sockaddr_in *);
static int get_version(struct mbuf *);
static int get_assert(struct mbuf *);
static int set_assert(int *);
static void expire_upcalls(void *);
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);
static void tbf_queue(struct vif *, struct mbuf *);
static void tbf_process_q(struct vif *);
static void tbf_reprocess_q(void *);
static int tbf_dq_sel(struct vif *, struct ip *);
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 *);

/*
 * whether or not special PIM assert processing is enabled.
 */
static int pim_assert;
/*
 * Rate limit for assert notification messages, in usec
 */
#define ASSERT_MSG_TIME		3000000

/*
 * Hash function for a source, group entry
 */
#define MFCHASH(a, g) MFCHASHMOD(((a) >> 20) ^ ((a) >> 10) ^ (a) ^ \
			((g) >> 20) ^ ((g) >> 10) ^ (g))

/*
 * Find a route for a given origin IP address and Multicast group address
 * Type of service parameter to be added in the future!!!
 */

#define MFCFIND(o, g, rt) { \
	register struct mbuf *_mb_rt = mfctable[MFCHASH(o,g)]; \
	register struct mfc *_rt = NULL; \
	rt = NULL; \
	++mrtstat.mrts_mfc_lookups; \
	while (_mb_rt) { \
		_rt = mtod(_mb_rt, struct mfc *); \
		if ((_rt->mfc_origin.s_addr == o) && \
		    (_rt->mfc_mcastgrp.s_addr == g) && \
		    (_mb_rt->m_act == NULL)) { \
			rt = _rt; \
			break; \
		} \
		_mb_rt = _mb_rt->m_next; \
	} \
	if (rt == NULL) { \
		++mrtstat.mrts_mfc_misses; \
	} \
}


/*
 * Macros to compute elapsed time efficiently
 * Borrowed from Van Jacobson's scheduling code
 */
#define TV_DELTA(a, b, delta) { \
	    register int xxs; \
		\
	    delta = (a).tv_usec - (b).tv_usec; \
	    if ((xxs = (a).tv_sec - (b).tv_sec)) { \
	       switch (xxs) { \
		      case 2: \
			  delta += 1000000; \
			      /* fall through */ \
		      case 1: \
			  delta += 1000000; \
			  break; \
		      default: \
			  delta += (1000000 * xxs); \
	       } \
	    } \
}

#define TV_LT(a, b) (((a).tv_usec < (b).tv_usec && \
	      (a).tv_sec <= (b).tv_sec) || (a).tv_sec < (b).tv_sec)

#ifdef UPCALL_TIMING
u_long upcall_data[51];
static void collate(struct timeval *);
#endif /* UPCALL_TIMING */


/*
 * Handle MRT setsockopt commands to modify the multicast routing tables.
 */
static int
X_ip_mrouter_set(cmd, so, m)
    int cmd;
    struct socket *so;
    struct mbuf *m;
{
   if (cmd != MRT_INIT && so != ip_mrouter) return EACCES;

    switch (cmd) {
	case MRT_INIT:     return ip_mrouter_init(so, m);
	case MRT_DONE:     return ip_mrouter_done();
	case MRT_ADD_VIF:  return add_vif (mtod(m, struct vifctl *));
	case MRT_DEL_VIF:  return del_vif (mtod(m, vifi_t *));
	case MRT_ADD_MFC:  return add_mfc (mtod(m, struct mfcctl *));
	case MRT_DEL_MFC:  return del_mfc (mtod(m, struct mfcctl *));
	case MRT_ASSERT:   return set_assert(mtod(m, int *));
	default:             return EOPNOTSUPP;
    }
}

#ifndef MROUTE_LKM
int (*ip_mrouter_set)(int, struct socket *, struct mbuf *) = X_ip_mrouter_set;
#endif

/*
 * Handle MRT getsockopt commands
 */
static int
X_ip_mrouter_get(cmd, so, m)
    int cmd;
    struct socket *so;
    struct mbuf **m;
{
    struct mbuf *mb;

    if (so != ip_mrouter) return EACCES;

    *m = mb = m_get(M_WAIT, MT_SOOPTS);
  
    switch (cmd) {
	case MRT_VERSION:   return get_version(mb);
	case MRT_ASSERT:    return get_assert(mb);
	default:            return EOPNOTSUPP;
    }
}

#ifndef MROUTE_LKM
int (*ip_mrouter_get)(int, struct socket *, struct mbuf **) = X_ip_mrouter_get;
#endif

/*
 * Handle ioctl commands to obtain information from the cache
 */
static int
X_mrt_ioctl(cmd, data)
    int cmd;
    caddr_t data;
{
    int error = 0;

    switch (cmd) {
	case (SIOCGETVIFCNT):
	    return (get_vif_cnt((struct sioc_vif_req *)data));
	    break;
	case (SIOCGETSGCNT):
	    return (get_sg_cnt((struct sioc_sg_req *)data));
	    break;
	default:
	    return (EINVAL);
	    break;
    }
    return error;
}

#ifndef MROUTE_LKM
int (*mrt_ioctl)(int, caddr_t) = X_mrt_ioctl;
#endif

/*
 * returns the packet, byte, rpf-failure count for the source group provided
 */
static int
get_sg_cnt(req)
    register struct sioc_sg_req *req;
{
    register struct mfc *rt;
    int s;

    s = splnet();
    MFCFIND(req->src.s_addr, req->grp.s_addr, rt);
    splx(s);
    if (rt != NULL) {
	req->pktcnt = rt->mfc_pkt_cnt;
	req->bytecnt = rt->mfc_byte_cnt;
	req->wrong_if = rt->mfc_wrong_if;
    } else
	req->pktcnt = req->bytecnt = req->wrong_if = 0xffffffff;

    return 0;
}

/*
 * returns the input and output packet and byte counts on the vif provided
 */
static int
get_vif_cnt(req)
    register struct sioc_vif_req *req;
{
    register vifi_t vifi = req->vifi;

    if (vifi >= numvifs) return EINVAL;

    req->icount = viftable[vifi].v_pkt_in;
    req->ocount = viftable[vifi].v_pkt_out;
    req->ibytes = viftable[vifi].v_bytes_in;
    req->obytes = viftable[vifi].v_bytes_out;

    return 0;
}

/*
 * Enable multicast routing
 */
static int
ip_mrouter_init(so, m)
	struct socket *so;
	struct mbuf *m;
{
    int *v;

    if (mrtdebug)
	log(LOG_DEBUG,"ip_mrouter_init: so_type = %d, pr_protocol = %d\n",
		so->so_type, so->so_proto->pr_protocol);

    if (so->so_type != SOCK_RAW ||
	so->so_proto->pr_protocol != IPPROTO_IGMP) return EOPNOTSUPP;

    if (!m || (m->m_len != sizeof(int *)))
	return ENOPROTOOPT;

    v = mtod(m, int *);
    if (*v != 1)
	return ENOPROTOOPT;

    if (ip_mrouter != NULL) return EADDRINUSE;

    ip_mrouter = so;

    bzero((caddr_t)mfctable, sizeof(mfctable));
    bzero((caddr_t)nexpire, sizeof(nexpire));

    pim_assert = 0;

    timeout(expire_upcalls, (caddr_t)NULL, EXPIRE_TIMEOUT);

    if (mrtdebug)
	log(LOG_DEBUG, "ip_mrouter_init\n");

    return 0;
}

/*
 * Disable multicast routing
 */
static int
X_ip_mrouter_done()
{
    vifi_t vifi;
    int i;
    struct ifnet *ifp;
    struct ifreq ifr;
    struct mbuf *mb_rt;
    struct mbuf *m;
    struct rtdetq *rte;
    int s;

    s = splnet();

    /*
     * For each phyint in use, disable promiscuous reception of all IP
     * multicasts.
     */
    for (vifi = 0; vifi < numvifs; vifi++) {
	if (viftable[vifi].v_lcl_addr.s_addr != 0 &&
	    !(viftable[vifi].v_flags & VIFF_TUNNEL)) {
	    ((struct sockaddr_in *)&(ifr.ifr_addr))->sin_family = AF_INET;
	    ((struct sockaddr_in *)&(ifr.ifr_addr))->sin_addr.s_addr