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

/*
 * The mrouted program is covered by the license in the accompanying file
 * named "LICENSE".  Use of the mrouted program represents acceptance of
 * the terms and conditions listed in that file.
 *
 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
 * Leland Stanford Junior University.
 *
 *
 * route.c,v 3.8.4.41 1998/01/15 00:08:34 fenner Exp
 */

#ifndef lint
static const char rcsid[] =
	"$Id: route.c,v 1.10 1998/01/16 07:17:45 charnier Exp $";
#endif /* not lint */

#include "defs.h"

/*
 * This define statement saves a lot of space later
 */
#define RT_ADDR	(struct rtentry *)&routing_table

/*
 * Exported variables.
 */
int routes_changed;			/* 1=>some routes have changed */
int delay_change_reports;		/* 1=>postpone change reports  */


/*
 * The routing table is shared with prune.c , so must not be static.
 */
struct rtentry *routing_table;		/* pointer to list of route entries */

/*
 * Private variables.
 */
static struct rtentry *rtp;		/* pointer to a route entry         */
static struct rtentry *rt_end;		/* pointer to last route entry      */
unsigned int nroutes;			/* current number of route entries  */

/*
 * Private functions.
 */
static int init_children_and_leaves	__P((struct rtentry *r,
						vifi_t parent, int first));
static int find_route		__P((u_int32 origin, u_int32 mask));
static void create_route	__P((u_int32 origin, u_int32 mask));
static void discard_route	__P((struct rtentry *prev_r));
static int compare_rts		__P((const void *rt1, const void *rt2));
static int report_chunk		__P((int, struct rtentry *start_rt, vifi_t vifi,
						u_int32 dst));
static void queue_blaster_report __P((vifi_t, u_int32, u_int32, char *,
					int, u_int32));
static void process_blaster_report __P((void *));

#ifdef SNMP
#include <sys/types.h>
#include "snmp.h"

/*
 * Return pointer to a specific route entry.  This must be a separate
 * function from find_route() which modifies rtp.
 */
struct rtentry *
snmp_find_route(src, mask)
    register u_int32 src, mask;
{
    register struct rtentry *rt;

   for (rt = routing_table; rt; rt = rt->rt_next) {
      if (src == rt->rt_origin && mask == rt->rt_originmask)
         return rt;
   }
   return NULL;
}

/*
 * Find next route entry > specification 
 */
int
next_route(rtpp, src, mask)
   struct rtentry **rtpp;
   u_int32 src;
   u_int32 mask;
{
   struct rtentry *rt, *rbest = NULL;

   /* Among all entries > spec, find "lowest" one in order */
   for (rt = routing_table; rt; rt=rt->rt_next) {
      if ((ntohl(rt->rt_origin) > ntohl(src) 
          || (ntohl(rt->rt_origin) == ntohl(src) 
             && ntohl(rt->rt_originmask) > ntohl(mask)))
       && (!rbest || (ntohl(rt->rt_origin) < ntohl(rbest->rt_origin))
          || (ntohl(rt->rt_origin) == ntohl(rbest->rt_origin)
             && ntohl(rt->rt_originmask) < ntohl(rbest->rt_originmask))))
               rbest = rt;
   }
   (*rtpp) = rbest;
   return (*rtpp)!=0;
}

/*
 * Given a routing table entry, and a vifi, find the next vifi/entry
 */
int
next_route_child(rtpp, src, mask, vifi)
   struct rtentry **rtpp;
   u_int32   src;
   u_int32   mask;
   vifi_t   *vifi;     /* vif at which to start looking */
{
   /* Get (S,M) entry */
   if (!((*rtpp) = snmp_find_route(src,mask)))
      if (!next_route(rtpp, src, mask))
         return 0;

   /* Continue until we get one with a valid next vif */
   do {
      for (; (*rtpp)->rt_children && *vifi<numvifs; (*vifi)++)
         if (VIFM_ISSET(*vifi, (*rtpp)->rt_children))
            return 1;
      *vifi = 0;
   } while( next_route(rtpp, (*rtpp)->rt_origin, (*rtpp)->rt_originmask) );

   return 0;
}
#endif

/*
 * Initialize the routing table and associated variables.
 */
void
init_routes()
{
    routing_table        = NULL;
    rt_end		 = RT_ADDR;
    nroutes		 = 0;
    routes_changed       = FALSE;
    delay_change_reports = FALSE;
}


/*
 * Initialize the children bits for route 'r', along with the
 * associated dominant and subordinate data structures.
 * If first is set, initialize dominants, otherwise keep old
 * dominants on non-parent interfaces.
 * XXX Does this need a return value?
 */
static int
init_children_and_leaves(r, parent, first)
    register struct rtentry *r;
    register vifi_t parent;
    int first;
{
    register vifi_t vifi;
    register struct uvif *v;
    vifbitmap_t old_children;
    nbrbitmap_t old_subords;

    VIFM_COPY(r->rt_children, old_children);
    NBRM_COPY(r->rt_subordinates, old_subords);

    VIFM_CLRALL(r->rt_children);

    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
	if (first || vifi == parent)
	    r->rt_dominants   [vifi] = 0;
	if (vifi == parent || uvifs[vifi].uv_flags & VIFF_NOFLOOD ||
		AVOID_TRANSIT(vifi, r) || (!first && r->rt_dominants[vifi]))
	    NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
	else
	    NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);

	if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED)) &&
	     	!(!first && r->rt_dominants[vifi])) {
	    VIFM_SET(vifi, r->rt_children);
	}
    }

    return (!VIFM_SAME(r->rt_children, old_children) ||
	    !NBRM_SAME(r->rt_subordinates, old_subords));
}


/*
 * A new vif has come up -- update the children bitmaps in all route
 * entries to take that into account.
 */
void
add_vif_to_routes(vifi)
    register vifi_t vifi;
{
    register struct rtentry *r;
    register struct uvif *v;

    v = &uvifs[vifi];
    for (r = routing_table; r != NULL; r = r->rt_next) {
	if (r->rt_metric != UNREACHABLE &&
	    !VIFM_ISSET(vifi, r->rt_children)) {
	    VIFM_SET(vifi, r->rt_children);
	    r->rt_dominants   [vifi] = 0;
	    /*XXX isn't uv_nbrmap going to be empty?*/
	    NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
	    update_table_entry(r, r->rt_gateway);
	}
    }
}


/*
 * A vif has gone down -- expire all routes that have that vif as parent,
 * and update the children bitmaps in all other route entries to take into
 * account the failed vif.
 */
void
delete_vif_from_routes(vifi)
    register vifi_t vifi;
{
    register struct rtentry *r;

    for (r = routing_table; r != NULL; r = r->rt_next) {
	if (r->rt_metric != UNREACHABLE) {
	    if (vifi == r->rt_parent) {
		del_table_entry(r, 0, DEL_ALL_ROUTES);
		r->rt_timer    = ROUTE_EXPIRE_TIME;
		r->rt_metric   = UNREACHABLE;
		r->rt_flags   |= RTF_CHANGED;
		routes_changed = TRUE;
	    }
	    else if (VIFM_ISSET(vifi, r->rt_children)) {
		VIFM_CLR(vifi, r->rt_children);
		NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
		update_table_entry(r, r->rt_gateway);
	    }
	    else {
		r->rt_dominants[vifi] = 0;
	    }
	}
    }
}


/*
 * A new neighbor has come up.  If we're flooding on the neighbor's
 * vif, mark that neighbor as subordinate for all routes whose parent
 * is not this vif.
 */
void
add_neighbor_to_routes(vifi, index)
    register vifi_t vifi;
    register int index;
{
    register struct rtentry *r;
    register struct uvif *v;

    v = &uvifs[vifi];
    if (v->uv_flags & VIFF_NOFLOOD)
	return;
    for (r = routing_table; r != NULL; r = r->rt_next) {
	if (r->rt_metric != UNREACHABLE && r->rt_parent != vifi &&
		!AVOID_TRANSIT(vifi, r)) {
	    NBRM_SET(index, r->rt_subordinates);
	    update_table_entry(r, r->rt_gateway);
	}
    }
}


/*
 * A neighbor has failed or become unreachable.  If that neighbor was
 * considered a dominant or subordinate router in any route entries,
 * take appropriate action.  Expire all routes this neighbor advertised
 * to us.
 */
void
delete_neighbor_from_routes(addr, vifi, index)
    register u_int32 addr;
    register vifi_t vifi;
    int index;
{
    register struct rtentry *r;
    register struct uvif *v;

    v = &uvifs[vifi];
    for (r = routing_table; r != NULL; r = r->rt_next) {
	if (r->rt_metric != UNREACHABLE) {
	    if (r->rt_parent == vifi && r->rt_gateway == addr) {
		del_table_entry(r, 0, DEL_ALL_ROUTES);
		r->rt_timer    = ROUTE_EXPIRE_TIME;
		r->rt_metric   = UNREACHABLE;
		r->rt_flags   |= RTF_CHANGED;
		routes_changed = TRUE;
	    } else if (r->rt_dominants[vifi] == addr) {
		VIFM_SET(vifi, r->rt_children);
		r->rt_dominants[vifi] = 0;
		if ((uvifs[vifi].uv_flags & VIFF_NOFLOOD) ||
				AVOID_TRANSIT(vifi, r))
		    NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
		else
		    NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
		update_table_entry(r, r->rt_gateway);
	    } else if (NBRM_ISSET(index, r->rt_subordinates)) {
		NBRM_CLR(index, r->rt_subordinates);
		update_table_entry(r, r->rt_gateway);
	    }
	}
    }
}


/*
 * Prepare for a sequence of ordered route updates by initializing a pointer
 * to the start of the routing table.  The pointer is used to remember our
 * position in the routing table in order to avoid searching from the
 * beginning for each update; this relies on having the route reports in
 * a single message be in the same order as the route entries in the routing
 * table.
 */
void
start_route_updates()
{
    rtp = RT_ADDR;
}


/*
 * Starting at the route entry following the one to which 'rtp' points,
 * look for a route entry matching the specified origin and mask.  If a
 * match is found, return TRUE and leave 'rtp' pointing at the found entry.
 * If no match is found, return FALSE and leave 'rtp' pointing to the route
 * entry preceding the point at which the new origin should be inserted.
 * This code is optimized for the normal case in which the first entry to
 * be examined is the matching entry.
 */
static int
find_route(origin, mask)
    register u_int32 origin, mask;
{
    register struct rtentry *r;

    r = rtp->rt_next;
    while (r != NULL) {
	if (origin == r->rt_origin && mask == r->rt_originmask) {
	    rtp = r;
	    return (TRUE);
	}
	if (ntohl(mask) < ntohl(r->rt_originmask) ||
	    (mask == r->rt_originmask &&
	     ntohl(origin) < ntohl(r->rt_origin))) {
	    rtp = r;
	    r = r->rt_next;
	}
	else break;
    }
    return (FALSE);
}

/*
 * Create a new routing table entry for the specified origin and link it into
 * the routing table.  The shared variable 'rtp' is assumed to point to the
 * routing entry after which the new one should be inserted.  It is left
 * pointing to the new entry.
 *
 * Only the origin, originmask, originwidth and flags fields are initialized
 * in the new route entry; the caller is responsible for filling in the the
 * rest.
 */
static void
create_route(origin, mask)
    u_int32 origin, mask;
{
    register struct rtentry *r;

    if ((r = (struct rtentry *) malloc(sizeof(struct rtentry) +
				       (numvifs * sizeof(u_int32)))) == NULL) {
	log(LOG_ERR, 0, "ran out of memory");	/* fatal */
    }
    r->rt_origin     = origin;
    r->rt_originmask = mask;
    if      (((char *)&mask)[3] != 0) r->rt_originwidth = 4;
    else if (((char *)&mask)[2] != 0) r->rt_originwidth = 3;
    else if (((char *)&mask)[1] != 0) r->rt_originwidth = 2;
    else                              r->rt_originwidth = 1;
    r->rt_flags        = 0;
    r->rt_dominants    = (u_int32 *)(r + 1);
    bzero(r->rt_dominants, numvifs * sizeof(u_int32));
    r->rt_groups       = NULL;
    VIFM_CLRALL(r->rt_children);
    NBRM_CLRALL(r->rt_subordinates);
    NBRM_CLRALL(r->rt_subordadv);

    r->rt_next = rtp->rt_next;
    rtp->rt_next = r;
    r->rt_prev = rtp;
    if (r->rt_next != NULL)
      (r->rt_next)->rt_prev = r;
    else 
      rt_end = r;
    rtp = r;
    ++nroutes;
}


/*
 * Discard the routing table entry following the one to which 'prev_r' points.
 */
static void
discard_route(prev_r)
    register struct rtentry *prev_r;
{
    register struct rtentry *r;

    r = prev_r->rt_next;
    uvifs[r->rt_parent].uv_nroutes--;
    /*???nbr???.al_nroutes--;*/
    prev_r->rt_next = r->rt_next;
    if (prev_r->rt_next != NULL)
      (prev_r->rt_next)->rt_prev = prev_r;
    else
      rt_end = prev_r;
    free((char *)r);
    --nroutes;
}


/*
 * Process a route report for a single origin, creating or updating the
 * corresponding routing table entry if necessary.  'src' is either the
 * address of a neighboring router from which the report arrived, or zero
 * to indicate a change of status of one of our own interfaces.
 */
void
update_route(origin, mask, metric, src, vifi, n)
    u_int32 origin, mask;
    u_int metric;
    u_int32 src;
    vifi_t vifi;
    struct listaddr *n;
{
    register struct rtentry *r;
    u_int adj_metric;

    /*
     * Compute an adjusted metric, taking into account the cost of the
     * subnet or tunnel over which the report arrived, and normalizing
     * all unreachable/poisoned metrics into a single value.
     */
    if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
	log(LOG_WARNING, 0,
	    "%s reports out-of-range metric %u for origin %s",
	    inet_fmt(src, s1), metric, inet_fmts(origin, mask, s2));
	return;
    }
    adj_metric = metric + uvifs[vifi].uv_metric;
    if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;

    /*
     * Look up the reported origin in the routing table.
     */
    if (!find_route(origin, mask)) {
	/*
	 * Not found.
	 * Don't create a new entry if the report says it's unreachable,
	 * or if the reported origin and mask are invalid.
	 */
	if (adj_metric == UNREACHABLE) {
	    return;
	}
	if (src != 0 && !inet_valid_subnet(origin, mask)) {
	    log(LOG_WARNING, 0,
		"%s reports an invalid origin (%s) and/or mask (%08x)",
		inet_fmt(src, s1), inet_fmt(origin, s2), ntohl(mask));
	    return;
	}

	IF_DEBUG(DEBUG_RTDETAIL)
	log(LOG_DEBUG, 0, "%s advertises new route %s",
		inet_fmt(src, s1), inet_fmts(origin, mask, s2));

	/*
	 * OK, create the new routing entry.  'rtp' will be left pointing
	 * to the new entry.
	 */
	create_route(origin, mask);
	uvifs[vifi].uv_nroutes++;
	/*n->al_nroutes++;*/

	rtp->rt_metric = UNREACHABLE;	/* temporary; updated below */
    }

    /*
     * We now have a routing entry for the reported origin.  Update it?
     */
    r = rtp;
    if (r->rt_metric == UNREACHABLE) {
	/*
	 * The routing entry is for a formerly-unreachable or new origin.
	 * If the report claims reachability, update the entry to use
	 * the reported route.
	 */
	if (adj_metric == UNREACHABLE)
	    return;

	IF_DEBUG(DEBUG_RTDETAIL)
	log(LOG_DEBUG, 0, "%s advertises %s with adj_metric %d (ours was %d)",
		inet_fmt(src, s1), inet_fmts(origin, mask, s2),
		adj_metric, r->rt_metric);

	/*
	 * Now "steal away" any sources that belong under this route
	 * by deleting any cache entries they might have created
	 * and allowing the kernel to re-request them.
	 *
	 * If we haven't performed final initialization yet and are
	 * just collecting the routing table, we can't have any
	 * sources so we don't perform this step.
	 */
	if (did_final_init)
	    steal_sources(rtp);

	r->rt_parent   = vifi;
	r->rt_gateway  = src;
	init_children_and_leaves(r, vifi, 1);

	r->rt_timer    = 0;
	r->rt_metric   = adj_metric;
	r->rt_flags   |= RTF_CHANGED;
	routes_changed = TRUE;
	update_table_entry(r, r->rt_gateway);
    }
    else if (src == r->rt_gateway) {
	/*
	 * The report has come either from the interface directly-connected
	 * to the origin subnet (src and r->rt_gateway both equal zero) or
	 * from the gateway we have chosen as the best first-hop gateway back
	 * towards the origin (src and r->rt_gateway not equal zero).  Reset
	 * the route timer and, if the reported metric has changed, update
	 * our entry accordingly.
	 */
	r->rt_timer = 0;

	IF_DEBUG(DEBUG_RTDETAIL)
	log(LOG_DEBUG, 0, "%s (current parent) advertises %s with adj_metric %d (ours was %d)",
		inet_fmt(src, s1), inet_fmts(origin, mask, s2),
		adj_metric, r->rt_metric);

	if (adj_metric == r->rt_metric)
	    return;

	if (adj_metric == UNREACHABLE) {
	    del_table_entry(r, 0, DEL_ALL_ROUTES);
	    r->rt_timer = ROUTE_EXPIRE_TIME;
	}
	r->rt_metric   = adj_metric;
	r->rt_flags   |= RTF_CHANGED;
	routes_changed = TRUE;
    }
    else if (src == 0 ||
	     (r->rt_gateway != 0 &&
	      (adj_metric < r->rt_metric ||
	       (adj_metric == r->rt_metric &&
		(ntohl(src) < ntohl(r->rt_gateway) ||
		 r->rt_timer >= ROUTE_SWITCH_TIME))))) {
	/*
	 * The report is for an origin we consider reachable; the report
	 * comes either from one of our own interfaces or from a gateway
	 * other than the one we have chosen as the best first-hop gateway
	 * back towards the origin.  If the source of the update is one of
	 * our own interfaces, or if the origin is not a directly-connected
	 * subnet and the reported metric for that origin is better than
	 * what our routing entry says, update the entry to use the new
	 * gateway and metric.  We also switch gateways if the reported
	 * metric is the same as the one in the route entry and the gateway
	 * associated with the route entry has not been heard from recently,
	 * or if the metric is the same but the reporting gateway has a lower
	 * IP address than the gateway associated with the route entry.
	 * Did you get all that?
	 */
	u_int32 old_gateway;
	vifi_t old_parent;
	old_gateway = r->rt_gateway;
	old_parent = r->rt_parent;
	r->rt_gateway = src;
	r->rt_parent = vifi;

	IF_DEBUG(DEBUG_RTDETAIL)
	log(LOG_DEBUG, 0, "%s (new parent) on vif %d advertises %s with adj_metric %d (old parent was %s on vif %d, metric %d)",
		inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
		adj_metric, inet_fmt(old_gateway, s3), old_parent,
		r->rt_metric);

	if (old_parent != vifi) {
	    init_children_and_leaves(r, vifi, 0);
	    uvifs[old_parent].uv_nroutes--;
	    uvifs[vifi].uv_nroutes++;
	}
	if (old_gateway != src) {
	    update_table_entry(r, old_gateway);
	    /*???old_gateway???->al_nroutes--;*/
	    /*n->al_nroutes++;*/
	}
	r->rt_timer    = 0;
	r->rt_metric   = adj_metric;
	r->rt_flags   |= RTF_CHANGED;
	routes_changed = TRUE;
    }
    else if (vifi != r->rt_parent) {
	/*
	 * The report came from a vif other than the route's parent vif.
	 * Update the children info, if necessary.
	 */
	if (AVOID_TRANSIT(vifi, r)) {
	    /*
	     * The route's parent is a vif from which we're not supposed
	     * to transit onto this vif.  Simply ignore the update.
	     */
	    IF_DEBUG(DEBUG_RTDETAIL)
	    log(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored due to NOTRANSIT)",
		inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
		metric);
	} else if (VIFM_ISSET(vifi, r->rt_children)) {
	    /*
	     * Vif is a child vif for this route.
	     */
	    if (metric  < r->rt_metric ||
		(metric == r->rt_metric &&
		 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
		/*
		 * Neighbor has lower metric to origin (or has same metric
		 * and lower IP address) -- it becomes the dominant router,
		 * and vif is no longer a child for me.
		 */
		VIFM_CLR(vifi, r->rt_children);
		r->rt_dominants   [vifi] = src;
		/* XXX
		 * We don't necessarily want to forget about subordinateness
		 * so that we can become the dominant quickly if the current
		 * dominant fails.
		 */
		NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
		update_table_entry(r, r->rt_gateway);
		IF_DEBUG(DEBUG_RTDETAIL)
		log(LOG_DEBUG, 0, "%s on vif %d becomes dominant for %s with metric %d",
		    inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
		    metric);
	    }
	    else if (metric > UNREACHABLE) {	/* "poisoned reverse" */
		/*
		 * Neighbor considers this vif to be on path to route's
		 * origin; record this neighbor as subordinate
		 */
		if (!NBRM_ISSET(n->al_index, r->rt_subordinates)) {
		    IF_DEBUG(DEBUG_RTDETAIL)
		    log(LOG_DEBUG, 0, "%s on vif %d becomes subordinate for %s with poison-reverse metric %d",
			inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
			metric - UNREACHABLE);
		    NBRM_SET(n->al_index, r->rt_subordinates);
		    update_table_entry(r, r->rt_gateway);
		} else {
		    IF_DEBUG(DEBUG_RTDETAIL)
		    log(LOG_DEBUG, 0, "%s on vif %d confirms subordinateness for %s with poison-reverse metric %d",
			inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
			metric - UNREACHABLE);
		}
		NBRM_SET(n->al_index, r->rt_subordadv);
	    }
	    else if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
		/*
		 * Current subordinate no longer considers this vif to be on
		 * path to route's origin; it is no longer a subordinate
		 * router.
		 */
		IF_DEBUG(DEBUG_RTDETAIL)
		log(LOG_DEBUG, 0, "%s on vif %d is no longer a subordinate for %s with metric %d",
		    inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
		    metric);
		NBRM_CLR(n->al_index, r->rt_subordinates);
		update_table_entry(r, r->rt_gateway);
	    }

	}
	else if (src == r->rt_dominants[vifi] &&
		 (metric  > r->rt_metric ||
		  (metric == r->rt_metric &&
		   ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
	    /*
	     * Current dominant no longer has a lower metric to origin
	     * (or same metric and lower IP address); we adopt the vif
	     * as our own child.
	     */
	    IF_DEBUG(DEBUG_RTDETAIL)
	    log(LOG_DEBUG, 0, "%s (current dominant) on vif %d is no longer dominant for %s with metric %d",
		inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
		metric);
	    VIFM_SET(vifi, r->rt_children);
	    r->rt_dominants[vifi] = 0;
	    if (uvifs[vifi].uv_flags & VIFF_NOFLOOD)
		NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
	    else
		NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
	    if (metric > UNREACHABLE) {
		NBRM_SET(n->al_index, r->rt_subordinates);
		NBRM_SET(n->al_index, r->rt_subordadv);
	    }
	    update_table_entry(r, r->rt_gateway);
	} else {
	    IF_DEBUG(DEBUG_RTDETAIL)
	    log(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored)",
		inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
		metric);
	}
    }
}


/*
 * On every timer interrupt, advance the timer in each routing entry.
 */
void
age_routes()
{
    register struct rtentry *r;
    register struct rtentry *prev_r;
    extern u_long virtual_time;		/* from main.c */

    for (prev_r = RT_ADDR, r = routing_table;
	 r != NULL;
	 prev_r = r, r = r->rt_next) {

	if ((r->rt_timer += TIMER_INTERVAL) >= ROUTE_DISCARD_TIME) {
	    /*
	     * Time to garbage-collect the route entry.
	     */
	    del_table_entry(r, 0, DEL_ALL_ROUTES);
	    discard_route(prev_r);
	    r = prev_r;
	}
	else if (r->rt_timer >= ROUTE_EXPIRE_TIME &&
		 r->rt_metric != UNREACHABLE) {
	    /*
	     * Time to expire the route entry.  If the gateway is zero,
	     * i.e., it is a route to a directly-connected subnet, just
	     * set the timer back to zero; such routes expire only when
	     * the interface to the subnet goes down.
	     */
	    if (r->rt_gateway == 0) {
		r->rt_timer = 0;
	    }
	    else {
		del_table_entry(r, 0, DEL_ALL_ROUTES);
		r->rt_metric   = UNREACHABLE;
		r->rt_flags   |= RTF_CHANGED;
		routes_changed = TRUE;
	    }
	}
	else if (virtual_time % (ROUTE_REPORT_INTERVAL * 2) == 0) {
	    /*
	     * Time out subordinateness that hasn't been reported in
	     * the last 2 intervals.
	     */
	    if (!NBRM_SAME(r->rt_subordinates, r->rt_subordadv)) {
		IF_DEBUG(DEBUG_ROUTE)
		log(LOG_DEBUG, 0, "rt %s sub 0x%08x%08x subadv 0x%08x%08x metric %d",
			RT_FMT(r, s1),
			r->rt_subordinates.hi, r->rt_subordinates.lo,
			r->rt_subordadv.hi, r->rt_subordadv.lo, r->rt_metric);
		NBRM_MASK(r->rt_subordinates, r->rt_subordadv);
		update_table_entry(r, r->rt_gateway);
	    }
	    NBRM_CLRALL(r->rt_subordadv);
	}
    }
}


/*
 * Mark all routes as unreachable.  This function is called only from
 * hup() in preparation for informing all neighbors that we are going
 * off the air.  For consistency, we ought also to delete all reachable
 * route entries from the kernel, but since we are about to exit we rely
 * on the kernel to do its own cleanup -- no point in making all those
 * expensive kernel calls now.
 */
void
expire_all_routes()
{
    register struct rtentry *r;

    for (r = routing_table; r != NULL; r = r->rt_next) {
	r->rt_metric   = UNREACHABLE;
	r->rt_flags   |= RTF_CHANGED;
	routes_changed = TRUE;
    }
}


/*
 * Delete all the routes in the routing table.
 */
void
free_all_routes()
{
    register struct rtentry *r;

    r = RT_ADDR;

    while (r->rt_next)
	discard_route(r);
}


/*
 * Process an incoming neighbor probe message.
 */
void
accept_probe(src, dst, p, datalen, level)
    u_int32 src;
    u_int32 dst;
    char *p;
    int datalen;
    u_int32 level;
{
    vifi_t vifi;
    static struct listaddr *unknowns = NULL;

    if ((vifi = find_vif(src, dst)) == NO_VIF) {
	struct listaddr *a, **prev;
	struct listaddr *match = NULL;
	time_t now = time(0);

	for (prev = &unknowns, a = *prev; a; a = *prev) {
	    if (a->al_addr == src)
		match = a;
	    if (a->al_ctime + 2 * a->al_timer < now) {
		/* We haven't heard from it in a long time */
		*prev = a->al_next;
		free(a);
	    } else {
		prev = &a->al_next;
	    }
	}
	if (match == NULL) {
	    match = *prev = (struct listaddr *)malloc(sizeof(struct listaddr));
	    match->al_next = NULL;
	    match->al_addr = src;
	    match->al_timer = OLD_NEIGHBOR_EXPIRE_TIME;
	    match->al_ctime = now - match->al_timer;
	}

	if (match->al_ctime + match->al_timer <= now) {
	    log(LOG_WARNING, 0,
		"ignoring probe from non-neighbor %s, check for misconfigured tunnel or routing on %s",
		inet_fmt(src, s1), s1);
	    match->al_timer *= 2;
	} else
	    IF_DEBUG(DEBUG_PEER)
	    log(LOG_DEBUG, 0,
		"ignoring probe from non-neighbor %s (%d seconds until next warning)", inet_fmt(src, s1), match->al_ctime + match->al_timer - now);
	return;
    }

    update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
}

struct newrt {
	u_int32 mask;
	u_int32 origin;
	int metric;
	int pad;
}; 

static int
compare_rts(rt1, rt2)
    const void *rt1;
    const void *rt2;
{
    register struct newrt *r1 = (struct newrt *)rt1;
    register struct newrt *r2 = (struct newrt *)rt2;
    register u_int32 m1 = ntohl(r1->mask);
    register u_int32 m2 = ntohl(r2->mask);
    register u_int32 o1, o2;

    if (m1 > m2)
	return (-1);
    if (m1 < m2)
	return (1);

    /* masks are equal */
    o1 = ntohl(r1->origin);
    o2 = ntohl(r2->origin);
    if (o1 > o2)
	return (-1);
    if (o1 < o2)
	return (1);
    return (0);
}

void
blaster_alloc(vifi)
    vifi_t vifi;
{
    register struct uvif *v;

    v = &uvifs[vifi];
    if (v->uv_blasterbuf)
	free(v->uv_blasterbuf);

    v->uv_blasterlen = 64*1024;
    v->uv_blasterbuf = malloc(v->uv_blasterlen);
    v->uv_blastercur = v->uv_blasterend = v->uv_blasterbuf;
    if (v->uv_blastertimer)
	timer_clearTimer(v->uv_blastertimer);
    v->uv_blastertimer = 0;
}

struct blaster_hdr {
    u_int32	bh_src;
    u_int32	bh_dst;
    u_int32	bh_level;
    int		bh_datalen;
};

/*
 * Queue a route report from a route-blaster.
 * If the timer isn't running to process these reports,
 * start it.
 */
static void
queue_blaster_report(vifi, src, dst, p, datalen, level)
    vifi_t vifi;
    u_int32 src, dst, level;
    register char *p;
    register int datalen;
{
    register struct blaster_hdr *bh;
    register struct uvif *v;
    int bblen = sizeof(*bh) + ((datalen + 3) & ~3);

    v = &uvifs[vifi];
    if (v->uv_blasterend - v->uv_blasterbuf +
	    		bblen > v->uv_blasterlen) {
	int end = v->uv_blasterend - v->uv_blasterbuf;
	int cur = v->uv_blastercur - v->uv_blasterbuf;

	v->uv_blasterlen *= 2;
	IF_DEBUG(DEBUG_IF)
	log(LOG_DEBUG, 0, "increasing blasterbuf to %d bytes",
			v->uv_blasterlen);
	v->uv_blasterbuf = realloc(v->uv_blasterbuf,
					v->uv_blasterlen);
	if (v->uv_blasterbuf == NULL) {
	    log(LOG_WARNING, ENOMEM, "turning off blaster on vif %d", vifi);
	    v->uv_blasterlen = 0;
	    v->uv_blasterend = v->uv_blastercur = NULL;
	    v->uv_flags &= ~VIFF_BLASTER;
	    return;
	}
	v->uv_blasterend = v->uv_blasterbuf + end;
	v->uv_blastercur = v->uv_blasterbuf + cur;
    }
    bh = (struct blaster_hdr *)v->uv_blasterend;
    bh->bh_src = src;
    bh->bh_dst = dst;
    bh->bh_level = level;
    bh->bh_datalen = datalen;
    bcopy(p, (char *)(bh + 1), datalen);
    v->uv_blasterend += bblen;

    if (v->uv_blastertimer == 0) {
	int *i = (int *)malloc(sizeof(int *));

	if (i == NULL)
		log(LOG_ERR, 0, "out of memory");

	*i = vifi;

	v->uv_blastertimer = timer_setTimer(5,
					    process_blaster_report, i);
    }
}

/*
 * Periodic process; process up to 5 of the routes in the route-blaster
 * queue.  If there are more routes remaining, reschedule myself to run
 * in 1 second.
 */
static void
process_blaster_report(vifip)
    void *vifip;
{
    vifi_t vifi = *(int *)vifip;
    register struct uvif *v;
    register struct blaster_hdr *bh;
    int i;

    IF_DEBUG(DEBUG_ROUTE)
    log(LOG_DEBUG, 0, "processing vif %d blasted routes", vifi);
    v = &uvifs[vifi];
    for (i = 0; i < 5; i++) {
	if (v->uv_blastercur >= v->uv_blasterend)
		break;
	bh = (struct blaster_hdr *)v->uv_blastercur;
	v->uv_blastercur += sizeof(*bh) + ((bh->bh_datalen + 3) & ~3);
	accept_report(bh->bh_src, bh->bh_dst, (char *)(bh + 1),
				    -bh->bh_datalen, bh->bh_level);
    }

    if (v->uv_blastercur >= v->uv_blasterend) {
	v->uv_blastercur = v->uv_blasterbuf;
	v->uv_blasterend = v->uv_blasterbuf;
	v->uv_blastertimer = 0;
	free(vifip);
	IF_DEBUG(DEBUG_ROUTE)
	log(LOG_DEBUG, 0, "finish processing vif %d blaster", vifi);
    } else {
	IF_DEBUG(DEBUG_ROUTE)
	log(LOG_DEBUG, 0, "more blasted routes to come on vif %d", vifi);
	v->uv_blastertimer = timer_setTimer(1,
					    process_blaster_report, vifip);
    }
}

/*
 * Process an incoming route report message.
 * If the report arrived on a vif marked as a "blaster", then just
 * queue it and return; queue_blaster_report() will schedule it for
 * processing later.  If datalen is negative, then this is actually
 * a queued report so actually process it instead of queueing it.
 */
void
accept_report(src, dst, p, datalen, level)
    u_int32 src, dst, level;
    register char *p;
    register int datalen;
{
    vifi_t vifi;
    register int width, i, nrt = 0;
    int metric;
    u_int32 mask;
    u_int32 origin;
    struct newrt rt[4096];
    struct listaddr *nbr;

    if ((vifi = find_vif(src, dst)) == NO_VIF) {
	log(LOG_INFO, 0,
    	    "ignoring route report from non-neighbor %s", inet_fmt(src, s1));
	return;
    }

    if (uvifs[vifi].uv_flags & VIFF_BLASTER)
	if (datalen > 0) {
	    queue_blaster_report(vifi, src, dst, p, datalen, level);
	    return;
	} else {
	    datalen = -datalen;
	}

    if (!(nbr = update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level)))
	return;

    if (datalen > 2*4096) {
	log(LOG_INFO, 0,
    	    "ignoring oversize (%d bytes) route report from %s",
	    datalen, inet_fmt(src, s1));
	return;
    }

    while (datalen > 0) {	/* Loop through per-mask lists. */

	if (datalen < 3) {
	    log(LOG_WARNING, 0,
		"received truncated route report from %s", 
		inet_fmt(src, s1));
	    return;
	}
	((u_char *)&mask)[0] = 0xff;            width = 1;
	if ((((u_char *)&mask)[1] = *p++) != 0) width = 2;
	if ((((u_char *)&mask)[2] = *p++) != 0) width = 3;
	if ((((u_char *)&mask)[3] = *p++) != 0) width = 4;
	if (!inet_valid_mask(ntohl(mask))) {
	    log(LOG_WARNING, 0,
		"%s reports bogus netmask 0x%08x (%s)",
		inet_fmt(src, s1), ntohl(mask), inet_fmt(mask, s2));
	    return;
	}
	datalen -= 3;

	do {			/* Loop through (origin, metric) pairs */
	    if (datalen < width + 1) {
		log(LOG_WARNING, 0,
		    "received truncated route report from %s", 
		    inet_fmt(src, s1));
		return;
	    }
	    origin = 0;
	    for (i = 0; i < width; ++i)
		((char *)&origin)[i] = *p++;
	    metric = *p++;
	    datalen -= width + 1;
	    rt[nrt].mask   = mask;
	    rt[nrt].origin = origin;
	    rt[nrt].metric = (metric & 0x7f);
	    ++nrt;
	} while (!(metric & 0x80));
    }

    qsort((char*)rt, nrt, sizeof(rt[0]), compare_rts);
    start_route_updates();
    /*
     * If the last entry is default, change mask from 0xff000000 to 0
     */
    if (rt[nrt-1].origin == 0)
	rt[nrt-1].mask = 0;

    IF_DEBUG(DEBUG_ROUTE)
    log(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt,
		inet_fmt(src, s1), inet_fmt(dst, s2));
    for (i = 0; i < nrt; ++i) {
	if (i != 0 && rt[i].origin == rt[i-1].origin &&
		      rt[i].mask == rt[i-1].mask) {
	    log(LOG_WARNING, 0, "%s reports duplicate route for %s",
		inet_fmt(src, s1), inet_fmts(rt[i].origin, rt[i].mask, s2));
	    continue;
	}
	/* Only filter non-poisoned updates. */
	if (uvifs[vifi].uv_filter && rt[i].metric < UNREACHABLE) {
	    struct vf_element *vfe;
	    int match = 0;

	    for (vfe = uvifs[vifi].uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
		if (vfe->vfe_flags & VFEF_EXACT) {
		    if ((vfe->vfe_addr == rt[i].origin) &&
			(vfe->vfe_mask == rt[i].mask)) {
			    match = 1;
			    break;
		    }
		} else {
		    if ((rt[i].origin & vfe->vfe_mask) == vfe->vfe_addr) {
			    match = 1;
			    break;
		    }
		}
	    }
	    if ((uvifs[vifi].uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
		(uvifs[vifi].uv_filter->vf_type == VFT_DENY && match == 1)) {
		    IF_DEBUG(DEBUG_ROUTE)
		    log(LOG_DEBUG, 0, "%s skipped on vif %d because it %s %s",
			inet_fmts(rt[i].origin, rt[i].mask, s1),
			vifi,
			match ? "matches" : "doesn't match",
			match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2) :
				"the filter");
#if 0
		    rt[i].metric += vfe->vfe_addmetric;
		    if (rt[i].metric > UNREACHABLE)
#endif
			rt[i].metric = UNREACHABLE;
	    }
	}
	update_route(rt[i].origin, rt[i].mask, rt[i].metric, 
		     src, vifi, nbr);
    }

    if (routes_changed && !delay_change_reports)
	report_to_all_neighbors(CHANGED_ROUTES);
}


/*
 * Send a route report message to destination 'dst', via virtual interface
 * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
 */
void
report(which_routes, vifi, dst)
    int which_routes;
    vifi_t vifi;
    u_int32 dst;
{
    register struct rtentry *r;
    register int i;

    r = rt_end;
    while (r != RT_ADDR) {
	i = report_chunk(which_routes, r, vifi, dst);
	while (i-- > 0)
	    r = r->rt_prev;
    }
}


/*
 * Send a route report message to all neighboring routers.
 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
 */
void
report_to_all_neighbors(which_routes)
    int which_routes;
{
    register vifi_t vifi;
    register struct uvif *v;
    register struct rtentry *r;
    int routes_changed_before;

    /*
     * Remember the state of the global routes_changed flag before
     * generating the reports, and clear the flag.
     */
    routes_changed_before = routes_changed;
    routes_changed = FALSE;


    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
	if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
	    report(which_routes, vifi, v->uv_dst_addr);
	}
    }

    /*
     * If there were changed routes before we sent the reports AND
     * if no new changes occurred while sending the reports, clear
     * the change flags in the individual route entries.  If changes
     * did occur while sending the reports, new reports will be
     * generated at the next timer interrupt.
     */
    if (routes_changed_before && !routes_changed) {
	for (r = routing_table; r != NULL; r = r->rt_next) {
	    r->rt_flags &= ~RTF_CHANGED;
	}
    }

    /*
     * Set a flag to inhibit further reports of changed routes until the
     * next timer interrupt.  This is to alleviate update storms.
     */
    delay_change_reports = TRUE;
}

/*
 * Send a route report message to destination 'dst', via virtual interface
 * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
 */
static int
report_chunk(which_routes, start_rt, vifi, dst)
    int which_routes;
    register struct rtentry *start_rt;
    vifi_t vifi;
    u_int32 dst;
{
    register struct rtentry *r;
    register char *p;
    register int i;
    register int nrt = 0;
    struct uvif *v = &uvifs[vifi];
    int datalen = 0;
    int width = 0;
    u_int32 mask = 0;
    u_int32 src;
    int admetric = v->uv_admetric;
    int metric;

    src = v->uv_lcl_addr;
    p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;

    for (r = start_rt; r != RT_ADDR; r = r->rt_prev) {
	if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED)) {
	    nrt++;
	    continue;
	}

	/*
	 * Do not poison-reverse a route for a directly-connected
	 * subnetwork on that subnetwork.  This can cause loops when
	 * some router on the subnetwork is misconfigured.
	 */
	if (r->rt_gateway == 0 && r->rt_parent == vifi) {
	    nrt++;
	    continue;
	}

	if (v->uv_filter && v->uv_filter->vf_flags & VFF_BIDIR) {
	    struct vf_element *vfe;
	    int match = 0;

	    for (vfe = v->uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
		if (vfe->vfe_flags & VFEF_EXACT) {
		    if ((vfe->vfe_addr == r->rt_origin) &&
			(vfe->vfe_mask == r->rt_originmask)) {
			    match = 1;
			    break;
		    }
		} else {
		    if ((r->rt_origin & vfe->vfe_mask) == vfe->vfe_addr) {
			    match = 1;
			    break;
		    }
		}
	    }
	    if ((v->uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
		(v->uv_filter->vf_type == VFT_DENY && match == 1)) {
		    IF_DEBUG(DEBUG_ROUTE)
		    log(LOG_DEBUG, 0, "%s not reported on vif %d because it %s %s",
			RT_FMT(r, s1), vifi,
			match ? "matches" : "doesn't match",
			match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2) :
				"the filter");
		    nrt++;
		    continue;
	    }
	}

	/*
	 * If there is no room for this route in the current message,
	 * send it & return how many routes we sent.
	 */
	if (datalen + ((r->rt_originmask == mask) ?
		       (width + 1) :
		       (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
	    *(p-1) |= 0x80;
	    send_on_vif(v, 0, DVMRP_REPORT, datalen);
	    return (nrt);
	}

	if (r->rt_originmask != mask || datalen == 0) {
	    mask  = r->rt_originmask;
	    width = r->rt_originwidth;
	    if (datalen != 0) *(p-1) |= 0x80;
	    *p++ = ((char *)&mask)[1];
	    *p++ = ((char *)&mask)[2];
	    *p++ = ((char *)&mask)[3];
	    datalen += 3;
	}
	for (i = 0; i < width; ++i)
	    *p++ = ((char *)&(r->rt_origin))[i];

	metric = r->rt_metric + admetric;
	if (metric > UNREACHABLE)
	    metric = UNREACHABLE;
	if (r->rt_parent != vifi && AVOID_TRANSIT(vifi, r))
	    metric = UNREACHABLE;
	*p++ = (r->rt_parent == vifi && metric != UNREACHABLE) ?
	    (char)(metric + UNREACHABLE) :  /* "poisoned reverse" */
	    (char)(metric);
	++nrt;
	datalen += width + 1;
    }
    if (datalen != 0) {
	*(p-1) |= 0x80;
	send_on_vif(v, 0, DVMRP_REPORT, datalen);
    }
    return (nrt);
}

/*
 * send the next chunk of our routing table to all neighbors.
 * return the length of the smallest chunk we sent out.
 */
int
report_next_chunk()
{
    register vifi_t vifi;
    register struct uvif *v;
    register struct rtentry *sr;
    register int i, n = 0, min = 20000;
    static int start_rt;

    if (nroutes <= 0)
	return (0);

    /*
     * find this round's starting route.
     */
    for (sr = rt_end, i = start_rt; --i >= 0; ) {
	sr = sr->rt_prev;
	if (sr == RT_ADDR)
	    sr = rt_end;
    }

    /*
     * send one chunk of routes starting at this round's start to
     * all our neighbors.
     */
    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
	if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
	    n = report_chunk(ALL_ROUTES, sr, vifi, v->uv_dst_addr);
	    if (n < min)
		min = n;
	}
    }
    if (min == 20000)
	min = 0;	/* Neighborless router didn't send any routes */

    n = min;
    IF_DEBUG(DEBUG_ROUTE)
    log(LOG_INFO, 0, "update %d starting at %d of %d",
	n, (nroutes - start_rt), nroutes);

    start_rt = (start_rt + n) % nroutes;
    return (n);
}


/*
 * Print the contents of the routing table on file 'fp'.
 */
void
dump_routes(fp)
    FILE *fp;
{
    register struct rtentry *r;
    register vifi_t i;


    fprintf(fp,
	    "Multicast Routing Table (%u %s)\n%s\n",
	    nroutes, (nroutes == 1) ? "entry" : "entries",
	    " Origin-Subnet      From-Gateway    Metric Tmr Fl In-Vif  Out-Vifs");

    for (r = routing_table; r != NULL; r = r->rt_next) {

	fprintf(fp, " %-18s %-15s ",
		inet_fmts(r->rt_origin, r->rt_originmask, s1),
		(r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway, s2));

	fprintf(fp, (r->rt_metric == UNREACHABLE) ? "  NR " : "%4u ",
		r->rt_metric);

	fprintf(fp, "  %3u %c%c %3u   ", r->rt_timer,
		(r->rt_flags & RTF_CHANGED) ? 'C' : '.',
		(r->rt_flags & RTF_HOLDDOWN) ? 'H' : '.',
		r->rt_parent);

	for (i = 0; i < numvifs; ++i) {
	    struct listaddr *n;
	    char l = '[';

	    if (VIFM_ISSET(i, r->rt_children)) {
		if ((uvifs[i].uv_flags & VIFF_TUNNEL) &&
		    !NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
			/* Don't print out parenthood of a leaf tunnel. */
			continue;
		fprintf(fp, " %u", i);
		if (!NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
		    fprintf(fp, "*");
		for (n = uvifs[i].uv_neighbors; n; n = n->al_next) {
		    if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
			fprintf(fp, "%c%d", l, n->al_index);
			l = ',';
		    }
		}
		if (l == ',')
		    fprintf(fp, "]");
	    }
	}
	fprintf(fp, "\n");
    }
    fprintf(fp, "\n");
}

struct rtentry *
determine_route(src)
    u_int32 src;
{
    struct rtentry *rt;

    for (rt = routing_table; rt != NULL; rt = rt->rt_next) {
	if (rt->rt_origin == (src & rt->rt_originmask) &&
	    rt->rt_metric != UNREACHABLE) 
	    break;
    }
    return rt;
}