path: root/usr.sbin/pim6dd/route.c

/*
 *  Copyright (c) 1998 by the University of Oregon.
 *  All rights reserved.
 *
 *  Permission to use, copy, modify, and distribute this software and
 *  its documentation in source and binary forms for lawful
 *  purposes and without fee is hereby granted, provided
 *  that the above copyright notice appear in all copies and that both
 *  the copyright notice and this permission notice appear in supporting
 *  documentation, and that any documentation, advertising materials,
 *  and other materials related to such distribution and use acknowledge
 *  that the software was developed by the University of Oregon.
 *  The name of the University of Oregon may not be used to endorse or
 *  promote products derived from this software without specific prior
 *  written permission.
 *
 *  THE UNIVERSITY OF OREGON DOES NOT MAKE ANY REPRESENTATIONS
 *  ABOUT THE SUITABILITY OF THIS SOFTWARE FOR ANY PURPOSE.  THIS SOFTWARE IS
 *  PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
 *  INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, TITLE, AND
 *  NON-INFRINGEMENT.
 *
 *  IN NO EVENT SHALL UO, OR ANY OTHER CONTRIBUTOR BE LIABLE FOR ANY
 *  SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES, WHETHER IN CONTRACT,
 *  TORT, OR OTHER FORM OF ACTION, ARISING OUT OF OR IN CONNECTION WITH,
 *  THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 *  Other copyrights might apply to parts of this software and are so
 *  noted when applicable.
 */
/*
 *  Questions concerning this software should be directed to
 *  Kurt Windisch (kurtw@antc.uoregon.edu)
 *
 *  $Id: route.c,v 1.3 1999/10/27 11:40:30 jinmei Exp $
 */
/*
 * Part of this program has been derived from PIM sparse-mode pimd.
 * The pimd program is covered by the license in the accompanying file
 * named "LICENSE.pimd".
 *
 * The pimd program is COPYRIGHT 1998 by University of Southern California.
 *
 * Part of this program has been derived from mrouted.
 * The mrouted program is covered by the license in the accompanying file
 * named "LICENSE.mrouted".
 *
 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
 * Leland Stanford Junior University.
 *
 * $FreeBSD$
 */

#include "defs.h"


static u_int16 max_prune_timeout __P((mrtentry_t *));
static void   process_cache_miss  __P((struct mrt6msg *im));
static void   process_wrong_iif   __P((struct mrt6msg *im));

u_int32         default_source_preference = DEFAULT_LOCAL_PREF;
u_int32         default_source_metric     = DEFAULT_LOCAL_METRIC;


/* Return the iif for given address */
vifi_t
get_iif(address)
    struct sockaddr_in6 *address;
{
    struct rpfctl rpfc;

    k_req_incoming(address, &rpfc);
    if (IN6_IS_ADDR_UNSPECIFIED(&rpfc.rpfneighbor.sin6_addr))
	return (NO_VIF);
    return (rpfc.iif);
}

/* Return the PIM neighbor toward a source */
/* If route not found or if a local source or if a directly connected source,
 * but is not PIM router, or if the first hop router is not a PIM router,
 * then return NULL.
 */
pim_nbr_entry_t *
find_pim6_nbr(source)
    struct sockaddr_in6 *source;
{
    struct rpfctl rpfc;
    pim_nbr_entry_t *pim_nbr;
    struct sockaddr_in6 *next_hop_router_addr;

    if (local_address(source) != NO_VIF)
	return (pim_nbr_entry_t *)NULL;
    k_req_incoming(source, &rpfc);
    if ((IN6_IS_ADDR_UNSPECIFIED(&rpfc.rpfneighbor.sin6_addr))
	|| (rpfc.iif == NO_VIF))
	return (pim_nbr_entry_t *)NULL;
    next_hop_router_addr = &rpfc.rpfneighbor;
    for (pim_nbr = uvifs[rpfc.iif].uv_pim_neighbors;
	 pim_nbr != (pim_nbr_entry_t *)NULL;
	 pim_nbr = pim_nbr->next)
	if (inet6_equal(&pim_nbr->address, next_hop_router_addr))
	    return(pim_nbr);
    return (pim_nbr_entry_t *)NULL;
}

/* TODO: check again the exact setup if the source is local or directly
 * connected!!!
 */
/* TODO: XXX: change the metric and preference for all (S,G) entries per
 * source?
 */
/* PIMDM TODO - If possible, this would be the place to correct set the
 * source's preference and metric to that obtained from the kernel
 * and/or unicast routing protocol.  For now, set it to the configured
 * default for local pref/metric.
 */
/*
 * Set the iif, upstream router, preference and metric for the route
 * toward the source. Return TRUE is the route was found, othewise FALSE.
 * If srctype==PIM_IIF_SOURCE and if the source is directly connected
 * then the "upstream" is set to NULL.
 * Note that srctype is a hold-over from the PIM-SM daemon and is unused.
 */
int
set_incoming(srcentry_ptr, srctype)
    srcentry_t *srcentry_ptr;
    int srctype;
{
    struct rpfctl rpfc;
    struct sockaddr_in6 *source = &srcentry_ptr->address;
    struct sockaddr_in6 *neighbor_addr;
    register struct uvif *v;
    register pim_nbr_entry_t *n;

    /* Preference will be 0 if directly connected */
    srcentry_ptr->preference = 0;
    srcentry_ptr->metric = 0;

    if ((srcentry_ptr->incoming = local_address(source)) != NO_VIF) {
	/* The source is a local address */
	/* TODO: set the upstream to myself? */
	srcentry_ptr->upstream = (pim_nbr_entry_t *)NULL;
	return (TRUE);
    }

    if ((srcentry_ptr->incoming = find_vif_direct(source)) == NO_VIF) {
    /* TODO: probably need to check the case if the iif is disabled */
	/* Use the lastest resource: the kernel unicast routing table */
	k_req_incoming(source, &rpfc);
	if ((rpfc.iif == NO_VIF) ||
	    IN6_IS_ADDR_UNSPECIFIED(&rpfc.rpfneighbor.sin6_addr)) {
	    /* couldn't find a route */
	    IF_DEBUG(DEBUG_PIM_MRT | DEBUG_RPF)
		log(LOG_DEBUG, 0, "NO ROUTE found for %s",
		    inet6_fmt(&source->sin6_addr));
	    return(FALSE);
	}
	srcentry_ptr->incoming = rpfc.iif;
	neighbor_addr = &rpfc.rpfneighbor;
    }
    else {
	/* The source is directly connected.
	 */
	srcentry_ptr->upstream = (pim_nbr_entry_t *)NULL;
	return (TRUE);
    }

    /* set the preference for sources that aren't directly connected. */
    v = &uvifs[srcentry_ptr->incoming];
    srcentry_ptr->preference = v->uv_local_pref;
    srcentry_ptr->metric = v->uv_local_metric;

    /*
     * The upstream router must be a (PIM router) neighbor, otherwise we
     * are in big trouble ;-)
     */
    for (n = v->uv_pim_neighbors; n != NULL; n = n->next) {
	if (inet6_lessthan(neighbor_addr, &n->address))
	    continue;
	if (inet6_equal(neighbor_addr, &n->address)) {
	    /*
	     *The upstream router is found in the list of neighbors.
	     * We are safe!
	     */
	    srcentry_ptr->upstream = n;
	    IF_DEBUG(DEBUG_RPF)
		log(LOG_DEBUG, 0,
		    "For src %s, iif is %d, next hop router is %s",
		    inet6_fmt(&source->sin6_addr), srcentry_ptr->incoming,
		    inet6_fmt(&neighbor_addr->sin6_addr));
	    return(TRUE);
	}
	else break;
    }

    /* TODO: control the number of messages! */
    log(LOG_INFO, 0,
	"For src %s, iif is %d, next hop router is %s: NOT A PIM ROUTER",
	inet6_fmt(&source->sin6_addr), srcentry_ptr->incoming,
	inet6_fmt(&neighbor_addr->sin6_addr));
    srcentry_ptr->upstream = (pim_nbr_entry_t *)NULL;

    return(FALSE);
}


/* Set the leaves in a new mrtentry */
void set_leaves(mrtentry_ptr)
     mrtentry_t *mrtentry_ptr;
{
    vifi_t vifi;
    struct uvif *v;

    /* Check for a group report on each vif */
    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v)
	if(check_multicast_listener(v, &mrtentry_ptr->group->group))
	    IF_SET(vifi, &mrtentry_ptr->leaves);
}


/* Handle new receiver
 *
 * TODO: XXX: currently `source` is not used. Will be used with IGMPv3 where
 * we have source-specific Join/Prune.
 */
void
add_leaf(vifi, source, group)
    vifi_t vifi;
    struct sockaddr_in6 *source;
    struct sockaddr_in6 *group;
{
    grpentry_t *grpentry_ptr;
    mrtentry_t *mrtentry_srcs;
    if_set new_leaves;
    int state_change;

    grpentry_ptr = find_group(group);
    if (grpentry_ptr == (grpentry_t *)NULL)
	return;

    /* walk the source list for the group and add vif to oiflist */
    for (mrtentry_srcs = grpentry_ptr->mrtlink;
	 mrtentry_srcs != (mrtentry_t *)NULL;
	 mrtentry_srcs = mrtentry_srcs->grpnext) {

	/* if applicable, add the vif to the leaves */
	if (mrtentry_srcs->incoming == vifi)
	    continue;

	if(!(IF_ISSET(vifi, &mrtentry_srcs->leaves))) {

	    IF_DEBUG(DEBUG_MRT)
		log(LOG_DEBUG, 0, "Adding leaf vif %d for src %s group %s",
		    vifi,
		    inet6_fmt(&mrtentry_srcs->source->address.sin6_addr),
		    inet6_fmt(&group->sin6_addr));

	    IF_COPY(&mrtentry_srcs->leaves, &new_leaves);
	    IF_SET(vifi, &new_leaves);    /* Add the leaf */

	    state_change =
		change_interfaces(mrtentry_srcs,
				  mrtentry_srcs->incoming,
				  &mrtentry_srcs->pruned_oifs,
				  &new_leaves,
				  &mrtentry_srcs->asserted_oifs);

	    /* Handle transition from negative cache */
	    if(state_change == 1)
		trigger_join_alert(mrtentry_srcs);
	}
    }
}


/*
 * TODO: XXX: currently `source` is not used. To be used with IGMPv3 where
 * we have source-specific joins/prunes.
 */
void
delete_leaf(vifi, source, group)
    vifi_t vifi;
    struct sockaddr_in6 *source;
    struct sockaddr_in6 *group;
{
    grpentry_t *grpentry_ptr;
    mrtentry_t *mrtentry_srcs;
    if_set new_leaves;
    int state_change;

    /* mrtentry_t *mrtentry_ptr;
     * mrtentry_t *mrtentry_srcs;
     * vifbitmap_t new_oifs;
     * vifbitmap_t old_oifs;
     * vifbitmap_t new_leaves;
     */

    grpentry_ptr = find_group(group);
    if (grpentry_ptr == (grpentry_t *)NULL)
	return;

    /* walk the source list for the group and delete vif to leaves */
    for (mrtentry_srcs = grpentry_ptr->mrtlink;
	 mrtentry_srcs != (mrtentry_t *)NULL;
	 mrtentry_srcs = mrtentry_srcs->grpnext) {

	/* if applicable, delete the vif from the leaves */
	if (mrtentry_srcs->incoming == vifi)
	    continue;

	if(IF_ISSET(vifi, &mrtentry_srcs->leaves)) {

	    IF_DEBUG(DEBUG_MRT)
		log(LOG_DEBUG, 0, "Deleting leaf vif %d for src %s, group %s",
		    vifi,
		    inet6_fmt(&mrtentry_srcs->source->address.sin6_addr),
		    inet6_fmt(&group->sin6_addr));

	    IF_COPY(&mrtentry_srcs->leaves, &new_leaves);
	    IF_CLR(vifi, &new_leaves);    /* Remove the leaf */

	    state_change =
		change_interfaces(mrtentry_srcs,
				  mrtentry_srcs->incoming,
				  &mrtentry_srcs->pruned_oifs,
				  &new_leaves,
				  &mrtentry_srcs->asserted_oifs);

	    /* Handle transition to negative cache */
	    if(state_change == -1)
		trigger_prune_alert(mrtentry_srcs);
	}
    }
}

void
calc_oifs(mrtentry_ptr, oifs_ptr)
    mrtentry_t *mrtentry_ptr;
    if_set *oifs_ptr;
{
    if_set oifs;

    /*
     * oifs =
     * ((nbr_ifs - my_prune) + my_leaves) - my_filters - incoming_interface,
     * i.e.`leaves` have higher priority than `prunes`, but lower than `filters'.
     * Asserted oifs (those that lost assert) are handled as pruned oifs.
     * The incoming interface is always deleted from the oifs
     */

    if (mrtentry_ptr == (mrtentry_t *)NULL) {
        IF_ZERO(oifs_ptr);
        return;
    }

    IF_COPY(&nbr_mifs, &oifs);
    IF_CLR_MASK(&oifs, &mrtentry_ptr->pruned_oifs);
    IF_MERGE(&oifs, &mrtentry_ptr->leaves, &oifs);
    IF_CLR_MASK(&oifs, &mrtentry_ptr->asserted_oifs);
    IF_CLR_MASK(&oifs, &mrtentry_ptr->filter_oifs);
    IF_CLR(mrtentry_ptr->incoming, &oifs);
    IF_COPY(&oifs, oifs_ptr);
}


/*
 * Set the iif, join/prune/leaves/asserted interfaces. Calculate and
 * set the oifs.
 * Return 1 if oifs change from NULL to not-NULL.
 * Return -1 if oifs change from non-NULL to NULL
 *  else return 0
 * If the iif change or if the oifs change from NULL to non-NULL
 * or vice-versa, then schedule that mrtentry join/prune timer to
 * timeout immediately.
 */
int
change_interfaces(mrtentry_ptr, new_iif, new_pruned_oifs,
		  new_leaves_, new_asserted_oifs)
    mrtentry_t *mrtentry_ptr;
    vifi_t new_iif;
    if_set *new_pruned_oifs;
    if_set *new_leaves_;
    if_set *new_asserted_oifs;
{
    if_set old_pruned_oifs;	/* unnecessary? */
    if_set old_leaves;		/* unnecessary? */
    if_set new_leaves;
    if_set new_real_oifs;    /* The result oifs */
    if_set old_real_oifs;
    if_set old_asserted_oifs;	/* unnecessary? */
    vifi_t      old_iif;
    int return_value;

    if (mrtentry_ptr == (mrtentry_t *)NULL)
	return (0);

    IF_COPY(new_leaves_, &new_leaves);

    old_iif = mrtentry_ptr->incoming;
    IF_COPY(&mrtentry_ptr->leaves, &old_leaves);
    IF_COPY(&mrtentry_ptr->pruned_oifs, &old_pruned_oifs);
    IF_COPY(&mrtentry_ptr->asserted_oifs, &old_asserted_oifs);

    IF_COPY(&mrtentry_ptr->oifs, &old_real_oifs);

    mrtentry_ptr->incoming = new_iif;
    IF_COPY(new_pruned_oifs, &mrtentry_ptr->pruned_oifs);
    IF_COPY(&new_leaves, &mrtentry_ptr->leaves);
    IF_COPY(new_asserted_oifs, &mrtentry_ptr->asserted_oifs);
    calc_oifs(mrtentry_ptr, &new_real_oifs);

    if (IF_ISEMPTY(&old_real_oifs)) {
	if (IF_ISEMPTY(&new_real_oifs))
	    return_value = 0;
	else
	    return_value = 1;
    } else {
	if (IF_ISEMPTY(&new_real_oifs))
	    return_value = -1;
	else
	    return_value = 0;
    }

    if ((IF_SAME(&new_real_oifs, &old_real_oifs))
	&& (new_iif == old_iif))
	return 0;                  /* Nothing to change */

    IF_COPY(&new_real_oifs, &mrtentry_ptr->oifs);

    k_chg_mfc(mld6_socket, &mrtentry_ptr->source->address,
	      &mrtentry_ptr->group->group, new_iif, &new_real_oifs);

#ifdef RSRR
    rsrr_cache_send(mrtentry_ptr, RSRR_NOTIFICATION_OK);
#endif /* RSRR */

    return (return_value);
}


/* TODO: implement it. Required to allow changing of the physical interfaces
 * configuration without need to restart pimd.
 */
int
delete_vif_from_mrt(vifi)
vifi_t vifi;
{
    return TRUE;
}


static u_int16
max_prune_timeout(mrtentry_ptr)
     mrtentry_t *mrtentry_ptr;
{
    vifi_t vifi;
#if 0
    /* XXX: I don't understand how the variable works...(jinmei@kame.net) */
    u_int16 time_left = 0;
#endif
    u_int16 max_holdtime = 0;

    for(vifi=0; vifi < numvifs; ++vifi)
	if(IF_ISSET(vifi, &mrtentry_ptr->pruned_oifs) &&
	   mrtentry_ptr->prune_timers[vifi])
	    /* XXX - too expensive ? */
	    if(mrtentry_ptr->prune_timers[vifi] > max_holdtime)
		    max_holdtime = mrtentry_ptr->prune_timers[vifi];
#if 0
		    /* XXX: This is original. But does it have any meaning? */
		    max_holdtime = time_left;
#endif

    if(max_holdtime == 0)
	max_holdtime = (u_int16)PIM_JOIN_PRUNE_HOLDTIME;

    return(max_holdtime);
}


void
process_kernel_call()
{
    register struct mrt6msg *im; /* igmpmsg control struct */

    im = (struct mrt6msg *) mld6_recv_buf;

    switch (im->im6_msgtype) {
     case MRT6MSG_NOCACHE:
	process_cache_miss(im);
	break;
    case MRT6MSG_WRONGMIF:
	process_wrong_iif(im);
	break;
    default:
	IF_DEBUG(DEBUG_KERN)
	    log(LOG_DEBUG, 0, "Unknown kernel_call code, %d", im->im6_msgtype);
	break;
    }
}


/*
 * Protocol actions:
 *   1. Create (S,G) entry (find_route(CREATE))
 *      a. set iif and oifs
 */
static void
process_cache_miss(im)
    struct mrt6msg *im;
{
    static struct sockaddr_in6 source = {sizeof(source), AF_INET6};
    static struct sockaddr_in6 group = {sizeof(group), AF_INET6};
    mrtentry_t *mrtentry_ptr;

    /*
     * When there is a cache miss, we check only the header of the packet
     * (and only it should be sent up by the kernel.
     */

    group.sin6_addr  = im->im6_dst;
    source.sin6_addr = im->im6_src;
    group.sin6_scope_id = inet6_uvif2scopeid(&group, &uvifs[im->im6_mif]);
    source.sin6_scope_id = inet6_uvif2scopeid(&source, &uvifs[im->im6_mif]);

    IF_DEBUG(DEBUG_MFC)
	log(LOG_DEBUG, 0, "Cache miss, src %s, dst %s",
	    inet6_fmt(&source.sin6_addr), inet6_fmt(&group.sin6_addr));

    /* Don't create routing entries for the LAN scoped addresses */
    if (IN6_IS_ADDR_MC_NODELOCAL(&group.sin6_addr) ||/* sanity? */
	IN6_IS_ADDR_MC_LINKLOCAL(&group.sin6_addr))
	return;

    /* Create the (S,G) entry */
    mrtentry_ptr = find_route(&source, &group, MRTF_SG, CREATE);
    if (mrtentry_ptr == (mrtentry_t *)NULL)
	return;
    mrtentry_ptr->flags &= ~MRTF_NEW;

    /* Set oifs */
    set_leaves(mrtentry_ptr);
    calc_oifs(mrtentry_ptr, &(mrtentry_ptr->oifs));

    /* Add it to the kernel */
    k_chg_mfc(mld6_socket, &source, &group, mrtentry_ptr->incoming,
	      &mrtentry_ptr->oifs);

#ifdef RSRR
    rsrr_cache_send(mrtentry_ptr, RSRR_NOTIFICATION_OK);
#endif /* RSRR */

    /* No need to call change_interfaces, but check for NULL oiflist */
    if(IF_ISEMPTY(&mrtentry_ptr->oifs))
	trigger_prune_alert(mrtentry_ptr);
}


/*
 * A multicast packet has been received on wrong iif by the kernel.
 * If the packet was received on a point-to-point interface, rate-limit
 * prunes.  if the packet was received on a LAN interface, rate-limit
 * asserts.
 */
static void
process_wrong_iif(im)
    struct mrt6msg *im;
{
    static struct sockaddr_in6 source = {sizeof(source), AF_INET6};
    static struct sockaddr_in6 group = {sizeof(group), AF_INET6};
    mifi_t  mifi;
    mrtentry_t *mrtentry_ptr;

    group.sin6_addr  = im->im6_dst;
    source.sin6_addr = im->im6_src;
    mifi   = (mifi_t)im->im6_mif;
    group.sin6_scope_id = inet6_uvif2scopeid(&group, &uvifs[mifi]);
    source.sin6_scope_id = inet6_uvif2scopeid(&source, &uvifs[mifi]);

    /* PIMDM TODO Don't create routing entries for the LAN scoped addresses */
    if (IN6_IS_ADDR_MC_NODELOCAL(&group.sin6_addr) ||/* sanity? */
	IN6_IS_ADDR_MC_LINKLOCAL(&group.sin6_addr))
	return;

    mrtentry_ptr = find_route(&source, &group, MRTF_SG, DONT_CREATE);
    if(mrtentry_ptr == (mrtentry_t *)NULL)
	return;

    /* Ratelimit prunes or asserts */
#ifdef notyet
    if(uvifs[mifi].uv_flags & VIFF_POINT_TO_POINT) {

	/* Wrong vif on P2P interface - rate-limit prunes */

	if(mrtentry_ptr->last_prune[mifi] == virtual_time)
	    /* Skip due to rate-limiting */
	    return;
	mrtentry_ptr->last_prune[mifi] = virtual_time;

	if(uvifs[mifi].uv_rmt_addr)
	    send_pim6_jp(mrtentry_ptr, PIM_ACTION_PRUNE, mifi,
			uvifs[mifi].uv_rmt_addr,
			max_prune_timeout(mrtentry_ptr), 0);
	else
	    log(LOG_WARNING, 0,
		"Can't send wrongvif prune on p2p %s: no remote address",
		uvifs[mifi].uv_lcl_addr);
    } else
#endif
    {

	/* Wrong vif on LAN interface - rate-limit asserts */

	if(mrtentry_ptr->last_assert[mifi] == virtual_time)
	    /* Skip due to rate-limiting */
	    return;
	mrtentry_ptr->last_assert[mifi] = virtual_time;

	/* Send the assert */
	send_pim6_assert(&source, &group, mifi, mrtentry_ptr);
    }
}


void
trigger_prune_alert(mrtentry_ptr)
     mrtentry_t *mrtentry_ptr;
{
    IF_DEBUG(DEBUG_MRT)
	log(LOG_DEBUG, 0, "Now negative cache for src %s, grp %s - pruning",
	    inet6_fmt(&mrtentry_ptr->source->address.sin6_addr),
	    inet6_fmt(&mrtentry_ptr->group->group.sin6_addr));

    /* Set the entry timer to the max of the prune timers */
    SET_TIMER(mrtentry_ptr->timer, max_prune_timeout(mrtentry_ptr));

    /* Send a prune */
    if(mrtentry_ptr->upstream)
	send_pim6_jp(mrtentry_ptr, PIM_ACTION_PRUNE, mrtentry_ptr->incoming,
		     &mrtentry_ptr->upstream->address,
		     max_prune_timeout(mrtentry_ptr), 0);
}

void
trigger_join_alert(mrtentry_ptr)
     mrtentry_t *mrtentry_ptr;
{
    IF_DEBUG(DEBUG_MRT)
	log(LOG_DEBUG, 0, "Now forwarding state for src %s, grp %s - grafting",
	    inet6_fmt(&mrtentry_ptr->source->address.sin6_addr),
	    inet6_fmt(&mrtentry_ptr->group->group.sin6_addr));

    /* Refresh the entry timer */
    SET_TIMER(mrtentry_ptr->timer, PIM_DATA_TIMEOUT);

    /* Send graft */
    send_pim6_graft(mrtentry_ptr);
}