MFC r1.6 r1.30 r1.28 (HEAD):

[dragonfly.git] / 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
 *
 * $FreeBSD: src/usr.sbin/mrouted/route.c,v 1.12 1999/08/28 01:17:08 peter Exp $
 * $DragonFly: src/usr.sbin/mrouted/route.c,v 1.5 2005/12/05 00:58:50 swildner Exp $
 */

#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(struct rtentry *r,
                                                vifi_t parent, int first);
static int find_route   (u_int32 origin, u_int32 mask);
static void create_route(u_int32 origin, u_int32 mask);
static void discard_route(struct rtentry *prev_r);
static int compare_rts  (const void *rt1, const void *rt2);
static int report_chunk         (int, struct rtentry *start_rt, vifi_t vifi,
                                                u_int32 dst);
static void queue_blaster_report(vifi_t, u_int32, u_int32, char *,
                                        int, u_int32);
static void process_blaster_report(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(u_int32 src, u_int32 mask)
{
   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(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(struct rtentry **rtpp, u_int32 src, u_int32 mask, vifi_t *vifi)
{
   /* 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(void)
{
    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(struct rtentry *r, vifi_t parent, int first)
{
    vifi_t vifi;
    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_t vifi)
{
    struct rtentry *r;
    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_t vifi)
{
    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_t vifi, int index)
{
    struct rtentry *r;
    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(u_int32 addr, vifi_t vifi, int index)
{
    struct rtentry *r;
    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(void)
{
    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(u_int32 origin, u_int32 mask)
{
    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(u_int32 origin, u_int32 mask)
{
    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(struct rtentry *prev_r)
{
    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(u_int32 origin, u_int32 mask, u_int metric, u_int32 src,
             vifi_t vifi, struct listaddr *n)
{
    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(void)
{
    struct rtentry *r;
    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(void)
{
    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(void)
{
    struct rtentry *r;

    r = RT_ADDR;

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


/*
 * Process an incoming neighbor probe message.
 */
void
accept_probe(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(const void *rt1, const void *rt2)
{
    struct newrt *r1 = (struct newrt *)rt1;
    struct newrt *r2 = (struct newrt *)rt2;
    u_int32 m1 = ntohl(r1->mask);
    u_int32 m2 = ntohl(r2->mask);
    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_t vifi)
{
    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_t vifi, u_int32 src, u_int32 dst, char *p,
                     int datalen, u_int32 level)
{
    struct blaster_hdr *bh;
    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(void *vifip)
{
    vifi_t vifi = *(int *)vifip;
    struct uvif *v;
    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(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
{
    vifi_t vifi;
    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(int which_routes, vifi_t vifi, u_int32 dst)
{
    struct rtentry *r;
    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(int which_routes)
{
    vifi_t vifi;
    struct uvif *v;
    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(int which_routes, struct rtentry *start_rt, vifi_t vifi,
             u_int32 dst)
{
    struct rtentry *r;
    char *p;
    int i;
    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(void)
{
    vifi_t vifi;
    struct uvif *v;
    struct rtentry *sr;
    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(FILE *fp)
{
    struct rtentry *r;
    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(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;
}