/*      $NetBSD: route.c,v 1.5 1995/12/10 10:07:12 mycroft Exp $        */

/*
 * 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.
 */


#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);
static int find_route(u_int32_t origin, u_int32_t mask);
static void create_route(u_int32_t origin, u_int32_t mask);
static void discard_route(struct rtentry *prev_r);
static int compare_rts(const void *rt1, const void *rt2);
static int report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst);

/*
 * 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 and leaf bits for route 'r', along with the
 * associated dominant, subordinate, and leaf timing data structures.
 * Return TRUE if this changes the value of either the children or
 * leaf bitmaps for 'r'.
 */
static int
init_children_and_leaves(struct rtentry *r, vifi_t parent)
{
    vifi_t vifi;
    struct uvif *v;
    vifbitmap_t old_children, old_leaves;

    VIFM_COPY(r->rt_children, old_children);
    VIFM_COPY(r->rt_leaves,   old_leaves  );

    VIFM_CLRALL(r->rt_children);
    VIFM_CLRALL(r->rt_leaves);
    r->rt_flags &= ~RTF_LEAF_TIMING;

    for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
        r->rt_dominants   [vifi] = 0;
        r->rt_subordinates[vifi] = 0;

        if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED))) {
            VIFM_SET(vifi, r->rt_children);
            if (v->uv_neighbors == NULL) {
                VIFM_SET(vifi, r->rt_leaves);
                r->rt_leaf_timers[vifi] = 0;
            }
            else {
                r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
                r->rt_flags |= RTF_LEAF_TIMING;
            }
        }
        else {
            r->rt_leaf_timers[vifi] = 0;
        }
    }

    return (!VIFM_SAME(r->rt_children, old_children) ||
            !VIFM_SAME(r->rt_leaves,   old_leaves));
}


/*
 * A new vif has come up -- update the children and leaf 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;
            r->rt_subordinates[vifi] = 0;
            if (v->uv_neighbors == NULL) {
                VIFM_SET(vifi, r->rt_leaves);
                r->rt_leaf_timers[vifi] = 0;
            }
            else {
                VIFM_CLR(vifi, r->rt_leaves);
                r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
                r->rt_flags |= RTF_LEAF_TIMING;
            }
            update_table_entry(r);
        }
    }
}


/*
 * 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);
                VIFM_CLR(vifi, r->rt_leaves);
                r->rt_subordinates[vifi] = 0;
                r->rt_leaf_timers [vifi] = 0;
                update_table_entry(r);
            }
            else {
                r->rt_dominants[vifi] = 0;
            }
        }
    }
}


/*
 * A neighbor has failed or become unreachable.  If that neighbor was
 * considered a dominant or subordinate router in any route entries,
 * take appropriate action.
 */
void
delete_neighbor_from_routes(u_int32_t addr, 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) {
            if (r->rt_dominants[vifi] == addr) {
                VIFM_SET(vifi, r->rt_children);
                r->rt_dominants   [vifi] = 0;
                r->rt_subordinates[vifi] = 0;
                if (v->uv_neighbors == NULL) {
                    VIFM_SET(vifi, r->rt_leaves);
                    r->rt_leaf_timers[vifi] = 0;
                }
                else {
                    VIFM_CLR(vifi, r->rt_leaves);
                    r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
                    r->rt_flags |= RTF_LEAF_TIMING;
                }
                update_table_entry(r);
            }
            else if (r->rt_subordinates[vifi] == addr) {
                r->rt_subordinates[vifi] = 0;
                if (v->uv_neighbors == NULL) {
                    VIFM_SET(vifi, r->rt_leaves);
                    update_table_entry(r);
                }
                else {
                    r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
                    r->rt_flags |= RTF_LEAF_TIMING;
                }
            }
            else if (v->uv_neighbors == NULL &&
                     r->rt_leaf_timers[vifi] != 0) {
                VIFM_SET(vifi, r->rt_leaves);
                r->rt_leaf_timers[vifi] = 0;
                update_table_entry(r);
            }
        }
    }
}


/*
 * 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_t origin, u_int32_t 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 rest.
 */
static void
create_route(u_int32_t origin, u_int32_t mask)
{
    struct rtentry *r;

    if ((r = malloc(sizeof(struct rtentry) +
        (2 * numvifs * sizeof(u_int32_t)) +
        (numvifs * sizeof(u_int)))) == NULL) {
        logit(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_t *)(r + 1);
    r->rt_subordinates = (u_int32_t *)(r->rt_dominants + numvifs);
    r->rt_leaf_timers  = (u_int *)(r->rt_subordinates + numvifs);
    r->rt_groups       = NULL;

    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;
    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_t origin, u_int32_t mask, u_int metric, u_int32_t src,
    vifi_t vifi)
{
    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)) {
        logit(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)) {
            logit(LOG_WARNING, 0,
                "%s reports an invalid origin (%s) and/or mask (%08x)",
                inet_fmt(src, s1), inet_fmt(origin, s2), ntohl(mask));
            return;
        }

        /*
         * OK, create the new routing entry.  'rtp' will be left pointing
         * to the new entry.
         */
        create_route(origin, mask);

        /*
         * 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.
         */
        steal_sources(rtp);

        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;

        r->rt_parent   = vifi;
        init_children_and_leaves(r, vifi);

        r->rt_gateway  = src;
        r->rt_timer    = 0;
        r->rt_metric   = adj_metric;
        r->rt_flags   |= RTF_CHANGED;
        routes_changed = TRUE;
        update_table_entry(r);
    }
    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 (adj_metric == r->rt_metric)
            return;

        if (adj_metric == UNREACHABLE) {
            del_table_entry(r, 0, DEL_ALL_ROUTES);
            r->rt_timer = ROUTE_EXPIRE_TIME;
        }
        else if (adj_metric < r->rt_metric) {
            if (init_children_and_leaves(r, vifi)) {
                update_table_entry(r);
            }
        }
        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?
         */
        if (r->rt_parent != vifi || adj_metric < r->rt_metric) {
            /*
             * XXX Why do we do this if we are just changing the metric?
             */
            r->rt_parent = vifi;
            if (init_children_and_leaves(r, vifi)) {
                update_table_entry(r);
            }
        }
        r->rt_gateway  = src;
        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 and leaf info, if necessary.
         */
        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);
                VIFM_CLR(vifi, r->rt_leaves);
                r->rt_dominants   [vifi] = src;
                r->rt_subordinates[vifi] = 0;
                r->rt_leaf_timers [vifi] = 0;
                update_table_entry(r);
            }
            else if (metric > UNREACHABLE) {    /* "poisoned reverse" */
                /*
                 * Neighbor considers this vif to be on path to route's
                 * origin; if no subordinate recorded, record this neighbor
                 * as subordinate and clear the leaf flag.
                 */
                if (r->rt_subordinates[vifi] == 0) {
                    VIFM_CLR(vifi, r->rt_leaves);
                    r->rt_subordinates[vifi] = src;
                    r->rt_leaf_timers [vifi] = 0;
                    update_table_entry(r);
                }
            }
            else if (src == r->rt_subordinates[vifi]) {
                /*
                 * Current subordinate no longer considers this vif to be on
                 * path to route's origin; it is no longer a subordinate
                 * router, and we set the leaf confirmation timer to give
                 * us time to hear from other subordinates.
                 */
                r->rt_subordinates[vifi] = 0;
                if (uvifs[vifi].uv_neighbors == NULL ||
                    uvifs[vifi].uv_neighbors->al_next == NULL) {
                    VIFM_SET(vifi, r->rt_leaves);
                    update_table_entry(r);
                }
                else {
                    r->rt_leaf_timers [vifi] = LEAF_CONFIRMATION_TIME;
                    r->rt_flags |= RTF_LEAF_TIMING;
                }
            }

        }
        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.
             */
            VIFM_SET(vifi, r->rt_children);
            r->rt_dominants  [vifi] = 0;
            if (metric > UNREACHABLE) {
                r->rt_subordinates[vifi] = src;
            }
            else if (uvifs[vifi].uv_neighbors == NULL ||
                     uvifs[vifi].uv_neighbors->al_next == NULL) {
                VIFM_SET(vifi, r->rt_leaves);
            }
            else {
                r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
                r->rt_flags |= RTF_LEAF_TIMING;
            }
            update_table_entry(r);
        }
    }
}


/*
 * On every timer interrupt, advance the timer in each routing entry.
 */
void
age_routes(void)
{
    struct rtentry *r;
    struct rtentry *prev_r;
    vifi_t vifi;

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

        if ((r->rt_timer += TIMER_INTERVAL) < ROUTE_EXPIRE_TIME) {
            /*
             * Route is still good; see if any leaf timers need to be
             * advanced.
             */
            if (r->rt_flags & RTF_LEAF_TIMING) {
                r->rt_flags &= ~RTF_LEAF_TIMING;
                for (vifi = 0; vifi < numvifs; ++vifi) {
                    if (r->rt_leaf_timers[vifi] != 0) {
                        /*
                         * Unlike other timers, leaf timers decrement.
                         */
                        if ((r->rt_leaf_timers[vifi] -= TIMER_INTERVAL) == 0){
#ifdef NOTYET
                            /* If the vif is a physical leaf but has neighbors,
                             * it is not a tree leaf.  If I am a leaf, then no
                             * interface with neighbors is a tree leaf. */
                            if (!(((uvifs[vifi].uv_flags & VIFF_LEAF) ||
                                   (vifs_with_neighbors == 1)) &&
                                  (uvifs[vifi].uv_neighbors != NULL))) {
#endif
                                VIFM_SET(vifi, r->rt_leaves);
                                update_table_entry(r);
#ifdef NOTYET
                            }
#endif
                        }
                        else {
                            r->rt_flags |= RTF_LEAF_TIMING;
                        }
                    }
                }
            }
        }
        else if (r->rt_timer >= 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_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;
            }
        }
    }
}


/*
 * 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_t src, u_int32_t dst, char *p, int datalen,
    u_int32_t level)
{
    vifi_t vifi;

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

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

struct newrt {
        u_int32_t mask;
        u_int32_t 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_t m1 = ntohl(r1->mask);
    u_int32_t m2 = ntohl(r2->mask);
    u_int32_t 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);
}

/*
 * Process an incoming route report message.
 */
void
accept_report(u_int32_t src, u_int32_t dst, char *p, int datalen,
    u_int32_t level)
{
    vifi_t vifi;
    int width, i, nrt = 0;
    int metric;
    u_int32_t mask;
    u_int32_t origin;
    struct newrt rt[4096];

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

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

    if (datalen > 2*4096) {
        logit(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) {
            logit(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))) {
            logit(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) {
                logit(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;

    logit(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) {
            logit(LOG_WARNING, 0, "%s reports duplicate route for %s",
                inet_fmt(src, s1), inet_fmts(rt[i].origin, rt[i].mask, s2));
            continue;
        }
        update_route(rt[i].origin, rt[i].mask, rt[i].metric,
                     src, vifi);
    }

    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_t dst)
{
    struct rtentry *r;
    char *p;
    int i;
    int datalen = 0;
    int width = 0;
    u_int32_t mask = 0;
    u_int32_t src;
    u_int32_t nflags;

    src = uvifs[vifi].uv_lcl_addr;

    p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;

#ifdef NOTYET
    /* If I'm not a leaf, but the neighbor is a leaf, only advertise default */
    if ((vifs_with_neighbors != 1) && (uvifs[vifi].uv_flags & VIFF_LEAF)) {
      *p++ = 0;       /* 0xff000000 mask */
      *p++ = 0;
      *p++ = 0;
      *p++ = 0;       /* class A net 0.0.0.0 == default */
      *p++ = 0x81;    /*XXX metric 1, is this safe? */
      datalen += 5;
      send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
                htonl(MROUTED_LEVEL), datalen);
      return;
    }
#endif

    nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS;

    for (r = rt_end; r != RT_ADDR; r = r->rt_prev) {

        if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED))
            continue;

        /*
         * If there is no room for this route in the current message,
         * send the message and start a new one.
         */
        if (datalen + ((r->rt_originmask == mask) ?
                       (width + 1) :
                       (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
            *(p-1) |= 0x80;
            send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
                      htonl(MROUTED_LEVEL | nflags), datalen);

            p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
            datalen = 0;
            mask = 0;
        }

        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];

        *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ?
            (char)(r->rt_metric + UNREACHABLE) :  /* "poisoned reverse" */
                (char)(r->rt_metric);

        datalen += width + 1;
    }

    if (datalen != 0) {
        *(p-1) |= 0x80;
        send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
                  htonl(MROUTED_LEVEL | nflags), datalen);
    }
}


/*
 * 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 (v->uv_neighbors != NULL) {
            report(which_routes, vifi,
                   (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr
                   : dvmrp_group);
        }
    }

    /*
     * 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(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst)
{
    struct rtentry *r;
    char *p;
    int i;
    int nrt = 0;
    int datalen = 0;
    int width = 0;
    u_int32_t mask = 0;
    u_int32_t src;
    u_int32_t nflags;

    src = uvifs[vifi].uv_lcl_addr;
    p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;

    nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS;

    for (r = start_rt; r != RT_ADDR; r = r->rt_prev) {

#ifdef NOTYET
        /* Don't send poisoned routes back to parents if I am a leaf */
        if ((vifs_with_neighbors == 1) && (r->rt_parent == vifi)
                && (r->rt_metric > 1)) {
            ++nrt;
            continue;
        }
#endif

        /*
         * 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_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
                      htonl(MROUTED_LEVEL | nflags), 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];

        *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ?
            (char)(r->rt_metric + UNREACHABLE) :  /* "poisoned reverse" */
                (char)(r->rt_metric);
        ++nrt;
        datalen += width + 1;
    }
    if (datalen != 0) {
        *(p-1) |= 0x80;
        send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
                  htonl(MROUTED_LEVEL | nflags), 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 ((v->uv_neighbors != NULL)
#ifdef NOTYET
        && !(v->uv_flags & VIFF_LEAF)
#endif
                ) {
            n = report_chunk(sr, vifi,
                             (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr
                             : dvmrp_group);
            if (n < min)
                min = n;
        }
    }
    if (min == 20000)
        min = 0;        /* Neighborless router didn't send any routes */

    n = min;
    logit(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 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 %3u   ", r->rt_timer, r->rt_parent);

        for (i = 0; i < numvifs; ++i) {
            if (VIFM_ISSET(i, r->rt_children)) {
                fprintf(fp, " %u%c",
                        i, VIFM_ISSET(i, r->rt_leaves) ? '*' : ' ');
            }
        }
        fprintf(fp, "\n");
    }
    fprintf(fp, "\n");
}

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

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