Annotation of embedaddon/mrouted/route.c, revision 1.1.1.2.2.1

1.1       misho       1: /*
                      2:  * The mrouted program is covered by the license in the accompanying file
                      3:  * named "LICENSE".  Use of the mrouted program represents acceptance of
                      4:  * the terms and conditions listed in that file.
                      5:  *
                      6:  * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
                      7:  * Leland Stanford Junior University.
                      8:  */
                      9: 
                     10: #include "defs.h"
                     11: 
                     12: /*
                     13:  * Private macros.
                     14:  */
                     15: #define MAX_NUM_RT   4096
                     16: 
                     17: /*
                     18:  * Private types.
                     19:  */
                     20: struct newrt {
                     21:        u_int32 mask;
                     22:        u_int32 origin;
                     23:        int metric;
                     24:        int pad;
                     25: };
                     26: 
                     27: struct blaster_hdr {
                     28:     u_int32    bh_src;
                     29:     u_int32    bh_dst;
                     30:     u_int32    bh_level;
                     31:     int                bh_datalen;
                     32: };
                     33: 
                     34: /*
                     35:  * Exported variables.
                     36:  */
                     37: int routes_changed;                    /* 1=>some routes have changed */
                     38: int delay_change_reports;              /* 1=>postpone change reports  */
                     39: unsigned int nroutes;                  /* current number of route entries  */
                     40: struct rtentry *routing_table;         /* pointer to list of route entries */
                     41: 
                     42: /*
                     43:  * Private variables.
                     44:  */
                     45: static struct rtentry *rtp;            /* pointer to a route entry         */
                     46: static struct rtentry *rt_end;         /* pointer to last route entry      */
                     47: 
                     48: /*
                     49:  * Private functions.
                     50:  */
                     51: static int  init_children_and_leaves (struct rtentry *r, vifi_t parent, int first);
                     52: static int  find_route               (u_int32 origin, u_int32 mask);
                     53: static void create_route             (u_int32 origin, u_int32 mask);
                     54: static void discard_route            (struct rtentry *this);
                     55: static int  compare_rts              (const void *rt1, const void *rt2);
                     56: static int  report_chunk             (int, struct rtentry *start_rt, vifi_t vifi, u_int32 dst);
                     57: static void queue_blaster_report     (vifi_t vifi, u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level);
                     58: static void process_blaster_report   (void *vifip);
                     59: 
                     60: #ifdef SNMP
                     61: #include <sys/types.h>
                     62: #include "snmp.h"
                     63: 
                     64: /*
                     65:  * Return pointer to a specific route entry.  This must be a separate
                     66:  * function from find_route() which modifies rtp.
                     67:  */
                     68: struct rtentry *snmp_find_route(u_int32 src, u_int32 mask)
                     69: {
                     70:     struct rtentry *rt;
                     71: 
                     72:    for (rt = routing_table; rt; rt = rt->rt_next) {
                     73:       if (src == rt->rt_origin && mask == rt->rt_originmask)
                     74:          return rt;
                     75:    }
                     76: 
                     77:    return NULL;
                     78: }
                     79: 
                     80: /*
                     81:  * Find next route entry > specification 
                     82:  */
                     83: int next_route(struct rtentry **rtpp, u_int32 src, u_int32 mask)
                     84: {
                     85:    struct rtentry *rt, *rbest = NULL;
                     86: 
                     87:    /* Among all entries > spec, find "lowest" one in order */
                     88:    for (rt = routing_table; rt; rt=rt->rt_next) {
                     89:       if ((ntohl(rt->rt_origin) > ntohl(src) 
                     90:           || (ntohl(rt->rt_origin) == ntohl(src) 
                     91:              && ntohl(rt->rt_originmask) > ntohl(mask)))
                     92:        && (!rbest || (ntohl(rt->rt_origin) < ntohl(rbest->rt_origin))
                     93:           || (ntohl(rt->rt_origin) == ntohl(rbest->rt_origin)
                     94:              && ntohl(rt->rt_originmask) < ntohl(rbest->rt_originmask))))
                     95:                rbest = rt;
                     96:    }
                     97:    (*rtpp) = rbest;
                     98: 
                     99:    return (*rtpp)!=0;
                    100: }
                    101: 
                    102: /*
                    103:  * Given a routing table entry, and a vifi, find the next vifi/entry
                    104:  */
                    105: int next_route_child(struct rtentry **rtpp, u_int32 src, u_int32 mask, vifi_t vifi)
                    106: {
                    107:    /* Get (S,M) entry */
                    108:    if (!((*rtpp) = snmp_find_route(src, mask)))
                    109:       if (!next_route(rtpp, src, mask))
                    110:          return 0;
                    111: 
                    112:    /* Continue until we get one with a valid next vif */
                    113:    do {
                    114:       for (; (*rtpp)->rt_children && *vifi<numvifs; (*vifi)++)
                    115:          if (VIFM_ISSET(*vifi, (*rtpp)->rt_children))
                    116:             return 1;
                    117:       *vifi = 0;
                    118:    } while (next_route(rtpp, (*rtpp)->rt_origin, (*rtpp)->rt_originmask));
                    119: 
                    120:    return 0;
                    121: }
                    122: #endif /* SNMP */
                    123: 
                    124: /*
                    125:  * Initialize the routing table and associated variables.
                    126:  */
                    127: void init_routes(void)
                    128: {
                    129:     routing_table        = NULL;
                    130:     rt_end              = NULL;
                    131:     nroutes             = 0;
                    132:     routes_changed       = FALSE;
                    133:     delay_change_reports = FALSE;
                    134: }
                    135: 
                    136: 
                    137: /*
                    138:  * Initialize the children bits for route 'r', along with the
                    139:  * associated dominant and subordinate data structures.
                    140:  * If first is set, initialize dominants, otherwise keep old
                    141:  * dominants on non-parent interfaces.
                    142:  * XXX Does this need a return value?
                    143:  */
                    144: static int init_children_and_leaves(struct rtentry *r, vifi_t parent, int first)
                    145: {
                    146:     vifi_t vifi;
                    147:     struct uvif *v;
                    148:     vifbitmap_t old_children;
                    149:     nbrbitmap_t old_subords;
                    150: 
                    151:     VIFM_COPY(r->rt_children, old_children);
                    152:     NBRM_COPY(r->rt_subordinates, old_subords);
                    153: 
                    154:     VIFM_CLRALL(r->rt_children);
                    155: 
                    156:     for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
                    157:        if (first || vifi == parent)
                    158:            r->rt_dominants[vifi] = 0;
                    159:        if (vifi == parent || uvifs[vifi].uv_flags & VIFF_NOFLOOD ||
                    160:                AVOID_TRANSIT(vifi, r) || (!first && r->rt_dominants[vifi]))
                    161:            NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
                    162:        else
                    163:            NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
                    164: 
                    165:        if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED)) &&
                    166:                !(!first && r->rt_dominants[vifi])) {
                    167:            VIFM_SET(vifi, r->rt_children);
                    168:        }
                    169:     }
                    170: 
                    171:     return (!VIFM_SAME(r->rt_children, old_children) ||
                    172:            !NBRM_SAME(r->rt_subordinates, old_subords));
                    173: }
                    174: 
                    175: 
                    176: /*
                    177:  * A new vif has come up -- update the children bitmaps in all route
                    178:  * entries to take that into account.
                    179:  */
                    180: void add_vif_to_routes(vifi_t vifi)
                    181: {
                    182:     struct rtentry *r;
                    183:     struct uvif *v;
                    184: 
                    185:     v = &uvifs[vifi];
                    186:     for (r = routing_table; r != NULL; r = r->rt_next) {
                    187:        if (r->rt_metric != UNREACHABLE &&
                    188:            !VIFM_ISSET(vifi, r->rt_children)) {
                    189:            VIFM_SET(vifi, r->rt_children);
                    190:            r->rt_dominants[vifi] = 0;
                    191:            /*XXX isn't uv_nbrmap going to be empty?*/
                    192:            NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
                    193:            update_table_entry(r, r->rt_gateway);
                    194:        }
                    195:     }
                    196: }
                    197: 
                    198: 
                    199: /*
                    200:  * A vif has gone down -- expire all routes that have that vif as parent,
                    201:  * and update the children bitmaps in all other route entries to take into
                    202:  * account the failed vif.
                    203:  */
                    204: void delete_vif_from_routes(vifi_t vifi)
                    205: {
                    206:     struct rtentry *r;
                    207: 
                    208:     for (r = routing_table; r != NULL; r = r->rt_next) {
                    209:        if (r->rt_metric != UNREACHABLE) {
                    210:            if (vifi == r->rt_parent) {
                    211:                del_table_entry(r, 0, DEL_ALL_ROUTES);
                    212:                r->rt_timer    = ROUTE_EXPIRE_TIME;
                    213:                r->rt_metric   = UNREACHABLE;
                    214:                r->rt_flags   |= RTF_CHANGED;
                    215:                routes_changed = TRUE;
                    216:            }
                    217:            else if (VIFM_ISSET(vifi, r->rt_children)) {
                    218:                VIFM_CLR(vifi, r->rt_children);
                    219:                NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
                    220:                update_table_entry(r, r->rt_gateway);
                    221:            }
                    222:            else {
                    223:                r->rt_dominants[vifi] = 0;
                    224:            }
                    225:        }
                    226:     }
                    227: }
                    228: 
                    229: 
                    230: /*
                    231:  * A new neighbor has come up.  If we're flooding on the neighbor's
                    232:  * vif, mark that neighbor as subordinate for all routes whose parent
                    233:  * is not this vif.
                    234:  */
                    235: void add_neighbor_to_routes(vifi_t vifi, u_int index)
                    236: {
                    237:     struct rtentry *r;
                    238:     struct uvif *v;
                    239: 
                    240:     v = &uvifs[vifi];
                    241:     if (v->uv_flags & VIFF_NOFLOOD)
                    242:        return;
                    243:     for (r = routing_table; r != NULL; r = r->rt_next) {
                    244:        if (r->rt_metric != UNREACHABLE && r->rt_parent != vifi &&
                    245:                !AVOID_TRANSIT(vifi, r)) {
                    246:            NBRM_SET(index, r->rt_subordinates);
                    247:            update_table_entry(r, r->rt_gateway);
                    248:        }
                    249:     }
                    250: }
                    251: 
                    252: 
                    253: /*
                    254:  * A neighbor has failed or become unreachable.  If that neighbor was
                    255:  * considered a dominant or subordinate router in any route entries,
                    256:  * take appropriate action.  Expire all routes this neighbor advertised
                    257:  * to us.
                    258:  */
                    259: void delete_neighbor_from_routes(u_int32 addr, vifi_t vifi, u_int index)
                    260: {
                    261:     struct rtentry *r;
1.1.1.2   misho     262:     struct uvif *v = &uvifs[vifi];
1.1       misho     263: 
                    264:     for (r = routing_table; r != NULL; r = r->rt_next) {
                    265:        if (r->rt_metric != UNREACHABLE) {
                    266:            if (r->rt_parent == vifi && r->rt_gateway == addr) {
                    267:                del_table_entry(r, 0, DEL_ALL_ROUTES);
                    268:                r->rt_timer    = ROUTE_EXPIRE_TIME;
                    269:                r->rt_metric   = UNREACHABLE;
                    270:                r->rt_flags   |= RTF_CHANGED;
                    271:                routes_changed = TRUE;
                    272:            } else if (r->rt_dominants[vifi] == addr) {
                    273:                VIFM_SET(vifi, r->rt_children);
                    274:                r->rt_dominants[vifi] = 0;
1.1.1.2   misho     275:                if ((v->uv_flags & VIFF_NOFLOOD) || AVOID_TRANSIT(vifi, r))
                    276:                    NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
1.1       misho     277:                else
1.1.1.2   misho     278:                    NBRM_SETMASK(r->rt_subordinates, v->uv_nbrmap);
1.1       misho     279:                update_table_entry(r, r->rt_gateway);
                    280:            } else if (NBRM_ISSET(index, r->rt_subordinates)) {
                    281:                NBRM_CLR(index, r->rt_subordinates);
                    282:                update_table_entry(r, r->rt_gateway);
                    283:            }
                    284:        }
                    285:     }
                    286: }
                    287: 
                    288: 
                    289: /*
                    290:  * Prepare for a sequence of ordered route updates by initializing a pointer
                    291:  * to the start of the routing table.  The pointer is used to remember our
                    292:  * position in the routing table in order to avoid searching from the
                    293:  * beginning for each update; this relies on having the route reports in
                    294:  * a single message be in the same order as the route entries in the routing
                    295:  * table.
1.1.1.2   misho     296:  *
                    297:  * find_route() expects rtp to be the preceding entry in the linked list
                    298:  * where route insertion takes place.  We need to be able to insert routes
                    299:  * before at the list head (routing table).
1.1       misho     300:  */
                    301: void start_route_updates(void)
                    302: {
1.1.1.2   misho     303:     rtp = NULL;
1.1       misho     304: }
                    305: 
                    306: 
                    307: /*
                    308:  * Starting at the route entry following the one to which 'rtp' points,
                    309:  * look for a route entry matching the specified origin and mask.  If a
                    310:  * match is found, return TRUE and leave 'rtp' pointing at the found entry.
                    311:  * If no match is found, return FALSE and leave 'rtp' pointing to the route
                    312:  * entry preceding the point at which the new origin should be inserted.
                    313:  * This code is optimized for the normal case in which the first entry to
                    314:  * be examined is the matching entry.
                    315:  */
                    316: static int find_route(u_int32 origin, u_int32 mask)
                    317: {
                    318:     struct rtentry *r;
                    319: 
1.1.1.2   misho     320:     /*
                    321:      * If rtp is NULL, we are preceding routing_table, so our first search
                    322:      * candidate should be the routing_table.
                    323:      */
                    324:     r = rtp ? rtp : routing_table;
1.1       misho     325:     while (r != NULL) {
                    326:        if (origin == r->rt_origin && mask == r->rt_originmask) {
                    327:            rtp = r;
                    328:            return TRUE;
                    329:        }
                    330:        if (ntohl(mask) < ntohl(r->rt_originmask) ||
                    331:            (mask == r->rt_originmask &&
                    332:             ntohl(origin) < ntohl(r->rt_origin))) {
                    333:            rtp = r;
                    334:            r = r->rt_next;
                    335:        } else {
                    336:            break;
                    337:        }
                    338:     }
                    339:     return FALSE;
                    340: }
                    341: 
                    342: /*
                    343:  * Create a new routing table entry for the specified origin and link it into
                    344:  * the routing table.  The shared variable 'rtp' is assumed to point to the
                    345:  * routing entry after which the new one should be inserted.  It is left
                    346:  * pointing to the new entry.
                    347:  *
                    348:  * Only the origin, originmask, originwidth and flags fields are initialized
                    349:  * in the new route entry; the caller is responsible for filling in the rest.
                    350:  */
                    351: static void create_route(u_int32 origin, u_int32 mask)
                    352: {
                    353:     size_t len;
                    354:     struct rtentry *this;
                    355: 
                    356:     this = (struct rtentry *)malloc(sizeof(struct rtentry));
                    357:     if (!this) {
                    358:        logit(LOG_ERR, errno, "route.c:create_route() - Failed allocating struct rtentry.\n");
                    359:        return;         /* NOTREACHED */
                    360:     }
                    361:     memset(this, 0, sizeof(struct rtentry));
                    362: 
                    363:     len = numvifs * sizeof(u_int32);
                    364:     this->rt_dominants = (u_int32 *)malloc(len);
                    365:     if (!this->rt_dominants) {
                    366:        logit(LOG_ERR, errno, "route.c:create_route() - Failed allocating struct rtentry.\n");
                    367:        free(this);
                    368:        return;         /* NOTREACHED */
                    369:     }
                    370:     memset(this->rt_dominants, 0, len);
                    371: 
                    372:     this->rt_origin     = origin;
                    373:     this->rt_originmask = mask;
                    374:     if      (((char *)&mask)[3] != 0) this->rt_originwidth = 4;
                    375:     else if (((char *)&mask)[2] != 0) this->rt_originwidth = 3;
                    376:     else if (((char *)&mask)[1] != 0) this->rt_originwidth = 2;
                    377:     else                              this->rt_originwidth = 1;
                    378:     this->rt_flags = 0;
                    379:     this->rt_groups = NULL;
                    380: 
                    381:     VIFM_CLRALL(this->rt_children);
                    382:     NBRM_CLRALL(this->rt_subordinates);
                    383:     NBRM_CLRALL(this->rt_subordadv);
                    384: 
                    385:     /* Link in 'this', where rtp points */
                    386:     if (rtp) {
                    387:        this->rt_prev = rtp;
                    388:        this->rt_next = rtp->rt_next;
                    389:        if (this->rt_next)
                    390:            (this->rt_next)->rt_prev = this;
                    391:        else
                    392:            rt_end = this;
                    393:        rtp->rt_next = this;
                    394:     } else {
1.1.1.2   misho     395:        if (routing_table) {
                    396:            /* Change existing head to this */
                    397:            this->rt_next = routing_table;
                    398:            routing_table->rt_prev = this;
                    399:        }
                    400:        else {
                    401:            /* this is the first route entry that exists */
                    402:            rt_end = this;
                    403:        }
1.1       misho     404:        routing_table = this;
                    405:     }
                    406: 
                    407:     rtp = this;
                    408:     ++nroutes;
                    409: }
                    410: 
                    411: 
                    412: /*
                    413:  * Discard the routing table entry following the one to which 'this' points.
                    414:  *         [.|prev|.]--->[.|this|.]<---[.|next|.]
                    415:  */
                    416: static void discard_route(struct rtentry *this)
                    417: {
                    418:     struct rtentry *prev, *next;
                    419: 
                    420:     if (!this)
                    421:        return;
                    422: 
                    423:     /* Find previous and next link */
                    424:     prev = this->rt_prev;
                    425:     next = this->rt_next;
                    426: 
                    427:     /* Unlink 'this' */
                    428:     if (prev)
                    429:        prev->rt_next = next;   /* Handles case when 'this' is last link. */
                    430:     else
                    431:        routing_table = next;   /* 'this' is first link. */
                    432:     if (next)
                    433:        next->rt_prev = prev;
                    434: 
                    435:     /* Update the books */
                    436:     uvifs[this->rt_parent].uv_nroutes--;
                    437:     /*???nbr???.al_nroutes--;*/
                    438:     --nroutes;
                    439: 
                    440:     /* Update meta pointers */
                    441:     if (rtp == this)
                    442:        rtp = next;
                    443:     if (rt_end == this)
                    444:        rt_end = next;
                    445: 
                    446:     free(this->rt_dominants);
                    447:     free(this);
                    448: }
                    449: 
                    450: 
                    451: /*
                    452:  * Process a route report for a single origin, creating or updating the
                    453:  * corresponding routing table entry if necessary.  'src' is either the
                    454:  * address of a neighboring router from which the report arrived, or zero
                    455:  * to indicate a change of status of one of our own interfaces.
                    456:  */
                    457: void update_route(u_int32 origin, u_int32 mask, u_int metric, u_int32 src, vifi_t vifi, struct listaddr *n)
                    458: {
                    459:     register struct rtentry *r;
                    460:     u_int adj_metric;
                    461: 
                    462:     /*
                    463:      * Compute an adjusted metric, taking into account the cost of the
                    464:      * subnet or tunnel over which the report arrived, and normalizing
                    465:      * all unreachable/poisoned metrics into a single value.
                    466:      */
                    467:     if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
                    468:        logit(LOG_WARNING, 0, "%s reports out-of-range metric %u for origin %s",
                    469:            inet_fmt(src, s1, sizeof(s1)), metric, inet_fmts(origin, mask, s2, sizeof(s2)));
                    470:        return;
                    471:     }
                    472:     adj_metric = metric + uvifs[vifi].uv_metric;
                    473:     if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;
                    474: 
                    475:     /*
                    476:      * Look up the reported origin in the routing table.
                    477:      */
                    478:     if (!find_route(origin, mask)) {
                    479:        /*
                    480:         * Not found.
                    481:         * Don't create a new entry if the report says it's unreachable,
                    482:         * or if the reported origin and mask are invalid.
                    483:         */
                    484:        if (adj_metric == UNREACHABLE) {
                    485:            return;
                    486:        }
                    487:        if (src != 0 && !inet_valid_subnet(origin, mask)) {
                    488:            logit(LOG_WARNING, 0, "%s reports an invalid origin (%s) and/or mask (%08x)",
                    489:                  inet_fmt(src, s1, sizeof(s1)), inet_fmt(origin, s2, sizeof(s2)), ntohl(mask));
                    490:            return;
                    491:        }
                    492: 
                    493:        IF_DEBUG(DEBUG_RTDETAIL) {
                    494:            logit(LOG_DEBUG, 0, "%s advertises new route %s",
                    495:                  inet_fmt(src, s1, sizeof(s1)), inet_fmts(origin, mask, s2, sizeof(s2)));
                    496:        }
                    497: 
                    498:        /*
                    499:         * OK, create the new routing entry.  'rtp' will be left pointing
                    500:         * to the new entry.
                    501:         */
                    502:        create_route(origin, mask);
                    503:        uvifs[vifi].uv_nroutes++;
                    504:        /*n->al_nroutes++;*/
                    505: 
                    506:        rtp->rt_metric = UNREACHABLE;   /* temporary; updated below */
                    507:     }
                    508: 
                    509:     /*
                    510:      * We now have a routing entry for the reported origin.  Update it?
                    511:      */
                    512:     r = rtp;
                    513:     if (r->rt_metric == UNREACHABLE) {
                    514:        /*
                    515:         * The routing entry is for a formerly-unreachable or new origin.
                    516:         * If the report claims reachability, update the entry to use
                    517:         * the reported route.
                    518:         */
                    519:        if (adj_metric == UNREACHABLE)
                    520:            return;
                    521: 
                    522:        IF_DEBUG(DEBUG_RTDETAIL) {
                    523:            logit(LOG_DEBUG, 0, "%s advertises %s with adj_metric %d (ours was %d)",
                    524:                  inet_fmt(src, s1, sizeof(s1)), inet_fmts(origin, mask, s2, sizeof(s2)),
                    525:                  adj_metric, r->rt_metric);
                    526:        }
                    527: 
                    528:        /*
                    529:         * Now "steal away" any sources that belong under this route
                    530:         * by deleting any cache entries they might have created
                    531:         * and allowing the kernel to re-request them.
                    532:         *
                    533:         * If we haven't performed final initialization yet and are
                    534:         * just collecting the routing table, we can't have any
                    535:         * sources so we don't perform this step.
                    536:         */
                    537:        if (did_final_init)
                    538:            steal_sources(rtp);
                    539: 
                    540:        r->rt_parent   = vifi;
                    541:        r->rt_gateway  = src;
                    542:        init_children_and_leaves(r, vifi, 1);
                    543: 
                    544:        r->rt_timer    = 0;
                    545:        r->rt_metric   = adj_metric;
                    546:        r->rt_flags   |= RTF_CHANGED;
                    547:        routes_changed = TRUE;
                    548:        update_table_entry(r, r->rt_gateway);
                    549:     } else if (src == r->rt_gateway) {
                    550:        /*
                    551:         * The report has come either from the interface directly-connected
                    552:         * to the origin subnet (src and r->rt_gateway both equal zero) or
                    553:         * from the gateway we have chosen as the best first-hop gateway back
                    554:         * towards the origin (src and r->rt_gateway not equal zero).  Reset
                    555:         * the route timer and, if the reported metric has changed, update
                    556:         * our entry accordingly.
                    557:         */
                    558:        r->rt_timer = 0;
                    559: 
                    560:        IF_DEBUG(DEBUG_RTDETAIL) {
                    561:            logit(LOG_DEBUG, 0, "%s (current parent) advertises %s with adj_metric %d (ours was %d)",
                    562:                  inet_fmt(src, s1, sizeof(s1)), inet_fmts(origin, mask, s2, sizeof(s2)),
                    563:                  adj_metric, r->rt_metric);
                    564:        }
                    565: 
                    566:        if (adj_metric == r->rt_metric)
                    567:            return;
                    568: 
                    569:        if (adj_metric == UNREACHABLE) {
                    570:            del_table_entry(r, 0, DEL_ALL_ROUTES);
                    571:            r->rt_timer = ROUTE_EXPIRE_TIME;
                    572:        }
                    573:        r->rt_metric   = adj_metric;
                    574:        r->rt_flags   |= RTF_CHANGED;
                    575:        routes_changed = TRUE;
                    576:     } else if (src == 0 ||
                    577:               (r->rt_gateway != 0 &&
                    578:                (adj_metric < r->rt_metric ||
                    579:                 (adj_metric == r->rt_metric &&
                    580:                  (ntohl(src) < ntohl(r->rt_gateway) ||
                    581:                   r->rt_timer >= ROUTE_SWITCH_TIME))))) {
                    582:        /*
                    583:         * The report is for an origin we consider reachable; the report
                    584:         * comes either from one of our own interfaces or from a gateway
                    585:         * other than the one we have chosen as the best first-hop gateway
                    586:         * back towards the origin.  If the source of the update is one of
                    587:         * our own interfaces, or if the origin is not a directly-connected
                    588:         * subnet and the reported metric for that origin is better than
                    589:         * what our routing entry says, update the entry to use the new
                    590:         * gateway and metric.  We also switch gateways if the reported
                    591:         * metric is the same as the one in the route entry and the gateway
                    592:         * associated with the route entry has not been heard from recently,
                    593:         * or if the metric is the same but the reporting gateway has a lower
                    594:         * IP address than the gateway associated with the route entry.
                    595:         * Did you get all that?
                    596:         */
                    597:        u_int32 old_gateway;
                    598:        vifi_t old_parent;
                    599: 
                    600:        old_gateway = r->rt_gateway;
                    601:        old_parent = r->rt_parent;
                    602:        r->rt_gateway = src;
                    603:        r->rt_parent = vifi;
                    604: 
                    605:        IF_DEBUG(DEBUG_RTDETAIL) {
                    606:            logit(LOG_DEBUG, 0, "%s (new parent) on vif %d advertises %s with adj_metric %d (old parent was %s on vif %d, metric %d)",
                    607:                  inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    608:                  adj_metric, inet_fmt(old_gateway, s3, sizeof(s3)), old_parent, r->rt_metric);
                    609:        }
                    610: 
                    611:        if (old_parent != vifi) {
                    612:            init_children_and_leaves(r, vifi, 0);
                    613:            uvifs[old_parent].uv_nroutes--;
                    614:            uvifs[vifi].uv_nroutes++;
                    615:        }
                    616:        if (old_gateway != src) {
                    617:            update_table_entry(r, old_gateway);
                    618:            /*???old_gateway???->al_nroutes--;*/
                    619:            /*n->al_nroutes++;*/
                    620:        }
                    621:        r->rt_timer    = 0;
                    622:        r->rt_metric   = adj_metric;
                    623:        r->rt_flags   |= RTF_CHANGED;
                    624:        routes_changed = TRUE;
                    625:     } else if (vifi != r->rt_parent) {
                    626:        /*
                    627:         * The report came from a vif other than the route's parent vif.
                    628:         * Update the children info, if necessary.
                    629:         */
                    630:        if (AVOID_TRANSIT(vifi, r)) {
                    631:            /*
                    632:             * The route's parent is a vif from which we're not supposed
                    633:             * to transit onto this vif.  Simply ignore the update.
                    634:             */
                    635:            IF_DEBUG(DEBUG_RTDETAIL) {
                    636:                logit(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored due to NOTRANSIT)",
                    637:                      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)), metric);
                    638:            }
                    639:        } else if (VIFM_ISSET(vifi, r->rt_children)) {
                    640:            /*
                    641:             * Vif is a child vif for this route.
                    642:             */
                    643:            if (metric  < r->rt_metric ||
                    644:                (metric == r->rt_metric &&
                    645:                 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
                    646:                /*
                    647:                 * Neighbor has lower metric to origin (or has same metric
                    648:                 * and lower IP address) -- it becomes the dominant router,
                    649:                 * and vif is no longer a child for me.
                    650:                 */
                    651:                VIFM_CLR(vifi, r->rt_children);
                    652:                r->rt_dominants[vifi] = src;
                    653:                /* XXX
                    654:                 * We don't necessarily want to forget about subordinateness
                    655:                 * so that we can become the dominant quickly if the current
                    656:                 * dominant fails.
                    657:                 */
                    658:                NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
                    659:                update_table_entry(r, r->rt_gateway);
                    660:                IF_DEBUG(DEBUG_RTDETAIL) {
                    661:                    logit(LOG_DEBUG, 0, "%s on vif %d becomes dominant for %s with metric %d",
                    662:                          inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    663:                          metric);
                    664:                }
                    665:            } else if (metric > UNREACHABLE) {  /* "poisoned reverse" */
                    666:                /*
                    667:                 * Neighbor considers this vif to be on path to route's
                    668:                 * origin; record this neighbor as subordinate
                    669:                 */
                    670:                if (!NBRM_ISSET(n->al_index, r->rt_subordinates)) {
                    671:                    IF_DEBUG(DEBUG_RTDETAIL) {
                    672:                        logit(LOG_DEBUG, 0, "%s on vif %d becomes subordinate for %s with poison-reverse metric %d",
                    673:                              inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    674:                              metric - UNREACHABLE);
                    675:                    }
                    676:                    NBRM_SET(n->al_index, r->rt_subordinates);
                    677:                    update_table_entry(r, r->rt_gateway);
                    678:                } else {
                    679:                    IF_DEBUG(DEBUG_RTDETAIL) {
                    680:                        logit(LOG_DEBUG, 0, "%s on vif %d confirms subordinateness for %s with poison-reverse metric %d",
                    681:                              inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    682:                              metric - UNREACHABLE);
                    683:                    }
                    684:                }
                    685:                NBRM_SET(n->al_index, r->rt_subordadv);
                    686:            } else if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
                    687:                /*
                    688:                 * Current subordinate no longer considers this vif to be on
                    689:                 * path to route's origin; it is no longer a subordinate
                    690:                 * router.
                    691:                 */
                    692:                IF_DEBUG(DEBUG_RTDETAIL) {
                    693:                    logit(LOG_DEBUG, 0, "%s on vif %d is no longer a subordinate for %s with metric %d",
                    694:                          inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    695:                          metric);
                    696:                }
                    697:                NBRM_CLR(n->al_index, r->rt_subordinates);
                    698:                update_table_entry(r, r->rt_gateway);
                    699:            }
                    700:        } else if (src == r->rt_dominants[vifi] &&
                    701:                   (metric  > r->rt_metric ||
                    702:                    (metric == r->rt_metric &&
                    703:                     ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
                    704:            /*
                    705:             * Current dominant no longer has a lower metric to origin
                    706:             * (or same metric and lower IP address); we adopt the vif
                    707:             * as our own child.
                    708:             */
                    709:            IF_DEBUG(DEBUG_RTDETAIL) {
                    710:                logit(LOG_DEBUG, 0, "%s (current dominant) on vif %d is no longer dominant for %s with metric %d",
                    711:                      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    712:                      metric);
                    713:            }
                    714: 
                    715:            VIFM_SET(vifi, r->rt_children);
                    716:            r->rt_dominants[vifi] = 0;
                    717: 
                    718:            if (uvifs[vifi].uv_flags & VIFF_NOFLOOD)
                    719:                NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
                    720:            else
                    721:                NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
                    722: 
                    723:            if (metric > UNREACHABLE) {
                    724:                NBRM_SET(n->al_index, r->rt_subordinates);
                    725:                NBRM_SET(n->al_index, r->rt_subordadv);
                    726:            }
                    727:            update_table_entry(r, r->rt_gateway);
                    728:        } else {
                    729:            IF_DEBUG(DEBUG_RTDETAIL) {
                    730:                logit(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored)",
                    731:                      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
                    732:                      metric);
                    733:            }
                    734:        }
                    735:     }
                    736: }
                    737: 
                    738: 
                    739: /*
                    740:  * On every timer interrupt, advance the timer in each routing entry.
                    741:  */
                    742: void age_routes(void)
                    743: {
                    744:     struct rtentry *r, *next;
                    745:     extern u_long virtual_time;                /* from main.c */
                    746: 
                    747:     r = routing_table;
                    748:     while (r != NULL) {
                    749:        next = r->rt_next;
                    750: 
                    751:        if ((r->rt_timer += TIMER_INTERVAL) >= ROUTE_DISCARD_TIME) {
                    752:            /*
                    753:             * Time to garbage-collect the route entry.
                    754:             */
                    755:            del_table_entry(r, 0, DEL_ALL_ROUTES);
                    756:            discard_route(r);
                    757:        }
                    758:        else if (r->rt_timer >= ROUTE_EXPIRE_TIME &&
                    759:                 r->rt_metric != UNREACHABLE) {
                    760:            /*
                    761:             * Time to expire the route entry.  If the gateway is zero,
                    762:             * i.e., it is a route to a directly-connected subnet, just
                    763:             * set the timer back to zero; such routes expire only when
                    764:             * the interface to the subnet goes down.
                    765:             */
                    766:            if (r->rt_gateway == 0) {
                    767:                r->rt_timer = 0;
                    768:            }
                    769:            else {
                    770:                del_table_entry(r, 0, DEL_ALL_ROUTES);
                    771:                r->rt_metric   = UNREACHABLE;
                    772:                r->rt_flags   |= RTF_CHANGED;
                    773:                routes_changed = TRUE;
                    774:            }
                    775:        }
                    776:        else if (virtual_time % (ROUTE_REPORT_INTERVAL * 2) == 0) {
                    777:            /*
                    778:             * Time out subordinateness that hasn't been reported in
                    779:             * the last 2 intervals.
                    780:             */
                    781:            if (!NBRM_SAME(r->rt_subordinates, r->rt_subordadv)) {
                    782:                IF_DEBUG(DEBUG_ROUTE) {
                    783:                    logit(LOG_DEBUG, 0, "rt %s sub 0x%08x%08x subadv 0x%08x%08x metric %d",
                    784:                          RT_FMT(r, s1), r->rt_subordinates.hi, r->rt_subordinates.lo,
                    785:                          r->rt_subordadv.hi, r->rt_subordadv.lo, r->rt_metric);
                    786:                }
                    787:                NBRM_MASK(r->rt_subordinates, r->rt_subordadv);
                    788:                update_table_entry(r, r->rt_gateway);
                    789:            }
                    790:            NBRM_CLRALL(r->rt_subordadv);
                    791:        }
                    792: 
                    793:        r = next;
                    794:     }
                    795: }
                    796: 
                    797: 
                    798: /*
                    799:  * Mark all routes as unreachable.  This function is called only from
                    800:  * hup() in preparation for informing all neighbors that we are going
                    801:  * off the air.  For consistency, we ought also to delete all reachable
                    802:  * route entries from the kernel, but since we are about to exit we rely
                    803:  * on the kernel to do its own cleanup -- no point in making all those
                    804:  * expensive kernel calls now.
                    805:  */
                    806: void expire_all_routes(void)
                    807: {
                    808:     struct rtentry *r;
                    809: 
                    810:     for (r = routing_table; r != NULL; r = r->rt_next) {
                    811:        r->rt_metric   = UNREACHABLE;
                    812:        r->rt_flags   |= RTF_CHANGED;
                    813:        routes_changed = TRUE;
                    814:     }
                    815: }
                    816: 
                    817: 
                    818: /*
                    819:  * Delete all the routes in the routing table.
                    820:  */
                    821: void free_all_routes(void)
                    822: {
                    823:     struct rtentry *r, *next;
                    824: 
                    825:     r = routing_table;
                    826:     while (r != NULL) {
                    827:        next = r->rt_next;
                    828:        discard_route(r);
                    829:        r = next;
                    830:     }
                    831: }
                    832: 
                    833: 
                    834: /*
                    835:  * Process an incoming neighbor probe message.
                    836:  */
                    837: void accept_probe(u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level)
                    838: {
                    839:     vifi_t vifi;
                    840:     static struct listaddr *unknowns = NULL;
                    841: 
                    842:     if ((vifi = find_vif(src, dst)) == NO_VIF) {
                    843:        struct listaddr *a, **prev;
                    844:        struct listaddr *match = NULL;
                    845:        time_t now = time(0);
                    846: 
                    847:        for (prev = &unknowns, a = *prev; a; a = *prev) {
                    848:            if (a->al_addr == src)
                    849:                match = a;
                    850:            if (a->al_ctime + 2 * a->al_timer < (u_long)now) {
                    851:                /* We haven't heard from it in a long time */
                    852:                *prev = a->al_next;
                    853:                free(a);
                    854:            } else {
                    855:                prev = &a->al_next;
                    856:            }
                    857:        }
                    858:        if (match == NULL) {
                    859:            match = *prev = (struct listaddr *)malloc(sizeof(struct listaddr));
                    860:            if (match == NULL) {
                    861:                logit(LOG_ERR, 0, "Malloc failed in route.c:accept_probe()\n");
                    862:                return;         /* NOTREACHED */
                    863:            }
                    864: 
                    865:            match->al_next = NULL;
                    866:            match->al_addr = src;
                    867:            match->al_timer = OLD_NEIGHBOR_EXPIRE_TIME;
                    868:            match->al_ctime = now - match->al_timer;
                    869:        }
                    870: 
                    871:        if (match->al_ctime + match->al_timer <= (u_long)now) {
                    872:            logit(LOG_WARNING, 0, "Ignoring probe from non-neighbor %s, check for misconfigured tunnel or routing on %s",
                    873:                  inet_fmt(src, s1, sizeof(s1)), s1);
                    874:            match->al_timer *= 2;
                    875:        } else {
                    876:            IF_DEBUG(DEBUG_PEER) {
                    877:                logit(LOG_DEBUG, 0, "Ignoring probe from non-neighbor %s (%d seconds until next warning)",
                    878:                      inet_fmt(src, s1, sizeof(s1)), match->al_ctime + match->al_timer - now);
                    879:            }
                    880:        }
                    881: 
                    882:        return;
                    883:     }
                    884: 
                    885:     update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
                    886: }
                    887: 
                    888: static int compare_rts(const void *rt1, const void *rt2)
                    889: {
                    890:     struct newrt *r1 = (struct newrt *)rt1;
                    891:     struct newrt *r2 = (struct newrt *)rt2;
                    892:     u_int32 m1 = ntohl(r1->mask);
                    893:     u_int32 m2 = ntohl(r2->mask);
                    894:     u_int32 o1, o2;
                    895: 
                    896:     if (m1 > m2)
                    897:        return -1;
                    898:     if (m1 < m2)
                    899:        return 1;
                    900: 
                    901:     /* masks are equal */
                    902:     o1 = ntohl(r1->origin);
                    903:     o2 = ntohl(r2->origin);
                    904:     if (o1 > o2)
                    905:        return -1;
                    906:     if (o1 < o2)
                    907:        return 1;
                    908: 
                    909:     return 0;
                    910: }
                    911: 
                    912: void blaster_alloc(vifi_t vifi)
                    913: {
                    914:     struct uvif *v;
                    915: 
                    916:     v = &uvifs[vifi];
                    917:     if (v->uv_blasterbuf)
                    918:        free(v->uv_blasterbuf);
                    919: 
                    920:     v->uv_blasterlen = 64 * 1024;
                    921:     v->uv_blasterbuf = malloc(v->uv_blasterlen);
                    922:     v->uv_blastercur = v->uv_blasterend = v->uv_blasterbuf;
                    923:     if (v->uv_blastertimer)
                    924:        timer_clearTimer(v->uv_blastertimer);
                    925:     v->uv_blastertimer = 0;
                    926: }
                    927: 
                    928: /*
                    929:  * Queue a route report from a route-blaster.
                    930:  * If the timer isn't running to process these reports,
                    931:  * start it.
                    932:  */
                    933: static void queue_blaster_report(vifi_t vifi, u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level)
                    934: {
                    935:     struct blaster_hdr *bh;
                    936:     struct uvif *v;
                    937:     int bblen = sizeof(*bh) + ((datalen + 3) & ~3);
                    938: 
                    939:     v = &uvifs[vifi];
                    940:     if (v->uv_blasterend - v->uv_blasterbuf + bblen > v->uv_blasterlen) {
                    941:        int end = v->uv_blasterend - v->uv_blasterbuf;
                    942:        int cur = v->uv_blastercur - v->uv_blasterbuf;
                    943: 
                    944:        v->uv_blasterlen *= 2;
                    945:        IF_DEBUG(DEBUG_IF) {
                    946:            logit(LOG_DEBUG, 0, "Increasing blasterbuf to %d bytes", v->uv_blasterlen);
                    947:        }
                    948: 
                    949:        v->uv_blasterbuf = realloc(v->uv_blasterbuf, v->uv_blasterlen);
                    950:        if (v->uv_blasterbuf == NULL) {
                    951:            logit(LOG_WARNING, ENOMEM, "Turning off blaster on vif %d", vifi);
                    952:            v->uv_blasterlen = 0;
                    953:            v->uv_blasterend = v->uv_blastercur = NULL;
                    954:            v->uv_flags &= ~VIFF_BLASTER;
                    955:            return;
                    956:        }
                    957:        v->uv_blasterend = v->uv_blasterbuf + end;
                    958:        v->uv_blastercur = v->uv_blasterbuf + cur;
                    959:     }
                    960:     bh = (struct blaster_hdr *)v->uv_blasterend;
                    961:     bh->bh_src = src;
                    962:     bh->bh_dst = dst;
                    963:     bh->bh_level = level;
                    964:     bh->bh_datalen = datalen;
                    965:     memmove((char *)(bh + 1), p, datalen);
                    966:     v->uv_blasterend += bblen;
                    967: 
                    968:     if (v->uv_blastertimer == 0) {
                    969:        int *i;
                    970: 
                    971:        i = (int *)malloc(sizeof(int *));
                    972:        if (i == NULL) {
                    973:            logit(LOG_ERR, 0, "Malloc failed in route.c:queue_blaster_report()\n");
                    974:            return;             /* NOTREACHED */
                    975:        }
                    976: 
                    977:        *i = vifi;
                    978:        v->uv_blastertimer = timer_setTimer(5, process_blaster_report, i);
                    979:     }
                    980: }
                    981: 
                    982: /*
                    983:  * Periodic process; process up to 5 of the routes in the route-blaster
                    984:  * queue.  If there are more routes remaining, reschedule myself to run
                    985:  * in 1 second.
                    986:  */
                    987: static void process_blaster_report(void *vifip)
                    988: {
                    989:     vifi_t vifi = *(int *)vifip;
                    990:     struct uvif *v;
                    991:     struct blaster_hdr *bh;
                    992:     int i;
                    993: 
                    994:     IF_DEBUG(DEBUG_ROUTE) {
                    995:        logit(LOG_DEBUG, 0, "Processing vif %d blasted routes", vifi);
                    996:     }
                    997: 
                    998:     v = &uvifs[vifi];
                    999:     for (i = 0; i < 5; i++) {
                   1000:        if (v->uv_blastercur >= v->uv_blasterend)
                   1001:                break;
                   1002: 
                   1003:        bh = (struct blaster_hdr *)v->uv_blastercur;
                   1004:        v->uv_blastercur += sizeof(*bh) + ((bh->bh_datalen + 3) & ~3);
                   1005: 
                   1006:        accept_report(bh->bh_src, bh->bh_dst, (char *)(bh + 1), -bh->bh_datalen, bh->bh_level);
                   1007:     }
                   1008: 
                   1009:     if (v->uv_blastercur >= v->uv_blasterend) {
                   1010:        v->uv_blastercur = v->uv_blasterbuf;
                   1011:        v->uv_blasterend = v->uv_blasterbuf;
                   1012:        v->uv_blastertimer = 0;
                   1013:        free(vifip);
                   1014: 
                   1015:        IF_DEBUG(DEBUG_ROUTE) {
                   1016:            logit(LOG_DEBUG, 0, "Finish processing vif %d blaster", vifi);
                   1017:        }
                   1018:     } else {
                   1019:        IF_DEBUG(DEBUG_ROUTE) {
                   1020:            logit(LOG_DEBUG, 0, "More blasted routes to come on vif %d", vifi);
                   1021:        }
                   1022:        v->uv_blastertimer = timer_setTimer(1, process_blaster_report, vifip);
                   1023:     }
                   1024: }
                   1025: 
                   1026: /*
                   1027:  * Process an incoming route report message.
                   1028:  * If the report arrived on a vif marked as a "blaster", then just
                   1029:  * queue it and return; queue_blaster_report() will schedule it for
                   1030:  * processing later.  If datalen is negative, then this is actually
                   1031:  * a queued report so actually process it instead of queueing it.
                   1032:  */
                   1033: void accept_report(u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level)
                   1034: {
                   1035:     vifi_t vifi;
                   1036:     size_t width, i, nrt = 0;
                   1037:     int metric;
                   1038:     u_int32 mask;
                   1039:     u_int32 origin;
                   1040:     static struct newrt rt[MAX_NUM_RT]; /* Use heap instead of stack */
                   1041:     struct listaddr *nbr;
                   1042: 
                   1043:     /*
                   1044:      * Emulate a stack variable.  We use the heap insted of the stack
                   1045:      * to prevent stack overflow on systems that cannot do stack realloc
                   1046:      * at runtime, e.g., non-MMU Linux systems.
                   1047:      */
                   1048:     memset(rt, 0, MAX_NUM_RT * sizeof(rt[0]));
                   1049: 
                   1050:     if ((vifi = find_vif(src, dst)) == NO_VIF) {
                   1051:        logit(LOG_INFO, 0, "Ignoring route report from non-neighbor %s",
                   1052:              inet_fmt(src, s1, sizeof(s1)));
                   1053:        return;
                   1054:     }
                   1055: 
                   1056:     if (uvifs[vifi].uv_flags & VIFF_BLASTER) {
                   1057:        if (datalen > 0) {
                   1058:            queue_blaster_report(vifi, src, dst, p, datalen, level);
                   1059:            return;
                   1060:        } else {
                   1061:            datalen = -datalen;
                   1062:        }
                   1063:     }
                   1064: 
                   1065:     nbr = update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level);
                   1066:     if (!nbr)
                   1067:        return;
                   1068: 
                   1069:     if (datalen > 2 * 4096) {
                   1070:        logit(LOG_INFO, 0, "Ignoring oversized (%d bytes) route report from %s",
                   1071:              datalen, inet_fmt(src, s1, sizeof(s1)));
                   1072:        return;
                   1073:     }
                   1074: 
                   1075:     while (datalen > 0  && nrt < MAX_NUM_RT) { /* Loop through per-mask lists. */
                   1076:        if (datalen < 3) {
                   1077:            logit(LOG_WARNING, 0, "Received truncated route report from %s", 
                   1078:                  inet_fmt(src, s1, sizeof(s1)));
                   1079:            return;
                   1080:        }
                   1081: 
                   1082:        ((u_char *)&mask)[0] = 0xff;            width = 1;
                   1083:        if ((((u_char *)&mask)[1] = *p++) != 0) width = 2;
                   1084:        if ((((u_char *)&mask)[2] = *p++) != 0) width = 3;
                   1085:        if ((((u_char *)&mask)[3] = *p++) != 0) width = 4;
                   1086:        if (!inet_valid_mask(ntohl(mask))) {
                   1087:            logit(LOG_WARNING, 0, "%s reports bogus netmask 0x%08x (%s)",
                   1088:                  inet_fmt(src, s1, sizeof(s1)), ntohl(mask), inet_fmt(mask, s2, sizeof(s2)));
                   1089:            return;
                   1090:        }
                   1091:        datalen -= 3;
                   1092: 
                   1093:        do {                    /* Loop through (origin, metric) pairs */
                   1094:            if (datalen < width + 1) {
                   1095:                logit(LOG_WARNING, 0, "Received truncated route report from %s", 
                   1096:                      inet_fmt(src, s1, sizeof(s1)));
                   1097:                return;
                   1098:            }
                   1099:            origin = 0;
                   1100:            for (i = 0; i < width; ++i)
                   1101:                ((char *)&origin)[i] = *p++;
                   1102:            metric = *p++;
                   1103:            datalen -= width + 1;
                   1104:            rt[nrt].mask   = mask;
                   1105:            rt[nrt].origin = origin;
                   1106:            rt[nrt].metric = (metric & 0x7f);
                   1107:            ++nrt;
                   1108:        } while (!(metric & 0x80) && nrt < MAX_NUM_RT);
                   1109:     }
                   1110: 
                   1111:     qsort((char *)rt, nrt, sizeof(rt[0]), compare_rts);
                   1112:     start_route_updates();
                   1113: 
                   1114:     /*
                   1115:      * If the last entry is default, change mask from 0xff000000 to 0
                   1116:      */
                   1117:     if (nrt > 0 && rt[nrt - 1].origin == 0)
                   1118:        rt[nrt - 1].mask = 0;
                   1119: 
                   1120:     IF_DEBUG(DEBUG_ROUTE) {
                   1121:        logit(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt,
                   1122:              inet_fmt(src, s1, sizeof(s1)), inet_fmt(dst, s2, sizeof(s2)));
                   1123:     }
                   1124: 
                   1125:     for (i = 0; i < nrt; ++i) {
                   1126:        if (i > 0 && rt[i].origin == rt[i - 1].origin && rt[i].mask == rt[i - 1].mask) {
                   1127:            logit(LOG_WARNING, 0, "%s reports duplicate route for %s",
                   1128:                   inet_fmt(src, s1, sizeof(s1)), inet_fmts(rt[i].origin, rt[i].mask, s2, sizeof(s2)));
                   1129:            continue;
                   1130:        }
                   1131:        /* Only filter non-poisoned updates. */
                   1132:        if (uvifs[vifi].uv_filter && rt[i].metric < UNREACHABLE) {
                   1133:            struct vf_element *vfe;
                   1134:            int match = 0;
                   1135: 
                   1136:            for (vfe = uvifs[vifi].uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
                   1137:                if (vfe->vfe_flags & VFEF_EXACT) {
                   1138:                    if ((vfe->vfe_addr == rt[i].origin) && (vfe->vfe_mask == rt[i].mask)) {
                   1139:                        match = 1;
                   1140:                        break;
                   1141:                    }
                   1142:                } else {
                   1143:                    if ((rt[i].origin & vfe->vfe_mask) == vfe->vfe_addr) {
                   1144:                        match = 1;
                   1145:                        break;
                   1146:                    }
                   1147:                }
                   1148:            }
                   1149:            if ((uvifs[vifi].uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
                   1150:                (uvifs[vifi].uv_filter->vf_type == VFT_DENY && match == 1)) {
                   1151:                IF_DEBUG(DEBUG_ROUTE) {
                   1152:                    logit(LOG_DEBUG, 0, "%s skipped on vif %d because it %s %s",
                   1153:                          inet_fmts(rt[i].origin, rt[i].mask, s1, sizeof(s1)),
                   1154:                          vifi, match ? "matches" : "doesn't match",
                   1155:                          match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2, sizeof(s2))
                   1156:                          : "the filter");
                   1157:                }
                   1158: #if 0
                   1159:                rt[i].metric += vfe->vfe_addmetric;
                   1160:                if (rt[i].metric > UNREACHABLE)
                   1161: #endif
                   1162:                    rt[i].metric = UNREACHABLE;
                   1163:            }
                   1164:        }
                   1165:        update_route(rt[i].origin, rt[i].mask, rt[i].metric, src, vifi, nbr);
                   1166:     }
                   1167: 
                   1168:     if (routes_changed && !delay_change_reports)
                   1169:        report_to_all_neighbors(CHANGED_ROUTES);
                   1170: }
                   1171: 
                   1172: 
                   1173: /*
                   1174:  * Send a route report message to destination 'dst', via virtual interface
                   1175:  * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
                   1176:  */
                   1177: void report(int which_routes, vifi_t vifi, u_int32 dst)
                   1178: {
                   1179:     struct rtentry *this;
                   1180:     int i;
                   1181: 
                   1182:     this = rt_end;
                   1183:     while (this && this != routing_table) {
                   1184:        i = report_chunk(which_routes, this, vifi, dst);
                   1185:        while (i-- > 0)
                   1186:            this = this->rt_prev;
                   1187:     }
                   1188: }
                   1189: 
                   1190: 
                   1191: /*
                   1192:  * Send a route report message to all neighboring routers.
                   1193:  * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
                   1194:  */
                   1195: void report_to_all_neighbors(int which_routes)
                   1196: {
                   1197:     vifi_t vifi;
                   1198:     struct uvif *v;
                   1199:     struct rtentry *r;
                   1200:     int routes_changed_before;
                   1201: 
                   1202:     /*
                   1203:      * Remember the state of the global routes_changed flag before
                   1204:      * generating the reports, and clear the flag.
                   1205:      */
                   1206:     routes_changed_before = routes_changed;
                   1207:     routes_changed = FALSE;
                   1208: 
                   1209: 
                   1210:     for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
                   1211:        if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
                   1212:            report(which_routes, vifi, v->uv_dst_addr);
                   1213:        }
                   1214:     }
                   1215: 
                   1216:     /*
                   1217:      * If there were changed routes before we sent the reports AND
                   1218:      * if no new changes occurred while sending the reports, clear
                   1219:      * the change flags in the individual route entries.  If changes
                   1220:      * did occur while sending the reports, new reports will be
                   1221:      * generated at the next timer interrupt.
                   1222:      */
                   1223:     if (routes_changed_before && !routes_changed) {
                   1224:        for (r = routing_table; r != NULL; r = r->rt_next) {
                   1225:            r->rt_flags &= ~RTF_CHANGED;
                   1226:        }
                   1227:     }
                   1228: 
                   1229:     /*
                   1230:      * Set a flag to inhibit further reports of changed routes until the
                   1231:      * next timer interrupt.  This is to alleviate update storms.
                   1232:      */
                   1233:     delay_change_reports = TRUE;
                   1234: }
                   1235: 
                   1236: /*
                   1237:  * Send a route report message to destination 'dst', via virtual interface
                   1238:  * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
                   1239:  */
                   1240: static int report_chunk(int which_routes, struct rtentry *start_rt, vifi_t vifi, u_int32 UNUSED dst)
                   1241: {
                   1242:     struct rtentry *r;
                   1243:     char *p;
                   1244:     int i;
                   1245:     size_t nrt = 0;
                   1246:     struct uvif *v = &uvifs[vifi];
                   1247:     int datalen = 0;
                   1248:     int width = 0;
                   1249:     u_int32 mask = 0;
                   1250:     int admetric = v->uv_admetric;
                   1251:     int metric;
                   1252: 
                   1253:     p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
                   1254: 
                   1255:     for (r = start_rt; r != routing_table; r = r->rt_prev) {
                   1256:        if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED)) {
                   1257:            nrt++;
                   1258:            continue;
                   1259:        }
                   1260: 
                   1261:        /*
                   1262:         * Do not poison-reverse a route for a directly-connected
                   1263:         * subnetwork on that subnetwork.  This can cause loops when
                   1264:         * some router on the subnetwork is misconfigured.
                   1265:         */
                   1266:        if (r->rt_gateway == 0 && r->rt_parent == vifi) {
                   1267:            nrt++;
                   1268:            continue;
                   1269:        }
                   1270: 
                   1271:        if (v->uv_filter && v->uv_filter->vf_flags & VFF_BIDIR) {
                   1272:            struct vf_element *vfe;
                   1273:            int match = 0;
                   1274: 
                   1275:            for (vfe = v->uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
                   1276:                if (vfe->vfe_flags & VFEF_EXACT) {
                   1277:                    if ((vfe->vfe_addr == r->rt_origin) &&
                   1278:                        (vfe->vfe_mask == r->rt_originmask)) {
                   1279:                            match = 1;
                   1280:                            break;
                   1281:                    }
                   1282:                } else {
                   1283:                    if ((r->rt_origin & vfe->vfe_mask) == vfe->vfe_addr) {
                   1284:                            match = 1;
                   1285:                            break;
                   1286:                    }
                   1287:                }
                   1288:            }
                   1289:            if ((v->uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
                   1290:                (v->uv_filter->vf_type == VFT_DENY && match == 1)) {
                   1291:                IF_DEBUG(DEBUG_ROUTE) {
                   1292:                    logit(LOG_DEBUG, 0, "%s not reported on vif %d because it %s %s",
                   1293:                          RT_FMT(r, s1), vifi, match ? "matches" : "doesn't match",
                   1294:                          match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2, sizeof(s2))
                   1295:                          : "the filter");
                   1296:                }
                   1297:                nrt++;
                   1298:                continue;
                   1299:            }
                   1300:        }
                   1301: 
                   1302:        /*
                   1303:         * If there is no room for this route in the current message,
                   1304:         * send it & return how many routes we sent.
                   1305:         */
                   1306:        if (datalen + ((r->rt_originmask == mask)
                   1307:                       ? (width + 1)
                   1308:                       : (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
                   1309:            *(p-1) |= 0x80;
                   1310:            send_on_vif(v, 0, DVMRP_REPORT, datalen);
                   1311: 
                   1312:            return nrt;
                   1313:        }
                   1314: 
                   1315:        if (r->rt_originmask != mask || datalen == 0) {
                   1316:            mask  = r->rt_originmask;
                   1317:            width = r->rt_originwidth;
                   1318:            if (datalen != 0) *(p-1) |= 0x80;
                   1319:            *p++ = ((char *)&mask)[1];
                   1320:            *p++ = ((char *)&mask)[2];
                   1321:            *p++ = ((char *)&mask)[3];
                   1322:            datalen += 3;
                   1323:        }
                   1324:        for (i = 0; i < width; ++i)
                   1325:            *p++ = ((char *)&(r->rt_origin))[i];
                   1326: 
                   1327:        metric = r->rt_metric + admetric;
                   1328:        if (metric > UNREACHABLE)
                   1329:            metric = UNREACHABLE;
                   1330: 
                   1331:        if (r->rt_parent != vifi && AVOID_TRANSIT(vifi, r))
                   1332:            metric = UNREACHABLE;
                   1333: 
                   1334:        *p++ = (r->rt_parent == vifi && metric != UNREACHABLE)
                   1335:            ? (char)(metric + UNREACHABLE) /* "poisoned reverse" */
                   1336:            : (char)(metric);
                   1337:        ++nrt;
                   1338:        datalen += width + 1;
                   1339:     }
                   1340:     if (datalen != 0) {
                   1341:        *(p-1) |= 0x80;
                   1342:        send_on_vif(v, 0, DVMRP_REPORT, datalen);
                   1343:     }
                   1344: 
                   1345:     return nrt;
                   1346: }
                   1347: 
                   1348: /*
                   1349:  * send the next chunk of our routing table to all neighbors.
                   1350:  * return the length of the smallest chunk we sent out.
                   1351:  */
                   1352: int report_next_chunk(void)
                   1353: {
                   1354:     vifi_t vifi;
                   1355:     struct uvif *v;
                   1356:     struct rtentry *sr;
                   1357:     int i, n = 0, min = 20000;
                   1358:     static int start_rt;
                   1359: 
                   1360:     if (nroutes <= 0)
                   1361:        return 0;
                   1362: 
                   1363:     /*
                   1364:      * find this round's starting route.
                   1365:      */
                   1366:     for (sr = rt_end, i = start_rt; sr && --i >= 0; ) {
                   1367:        sr = sr->rt_prev;
                   1368:        if (sr == routing_table)
                   1369:            sr = rt_end;
                   1370:     }
                   1371: 
                   1372:     /*
                   1373:      * send one chunk of routes starting at this round's start to
                   1374:      * all our neighbors.
                   1375:      */
                   1376:     for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
                   1377:        if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
                   1378:            n = report_chunk(ALL_ROUTES, sr, vifi, v->uv_dst_addr);
                   1379:            if (n < min)
                   1380:                min = n;
                   1381:        }
                   1382:     }
                   1383:     if (min == 20000)
                   1384:        min = 0;        /* Neighborless router didn't send any routes */
                   1385: 
                   1386:     n = min;
                   1387:     IF_DEBUG(DEBUG_ROUTE) {
                   1388:        logit(LOG_INFO, 0, "update %d starting at %d of %d",
                   1389:              n, (nroutes - start_rt), nroutes);
                   1390:     }
                   1391: 
                   1392:     start_rt = (start_rt + n) % nroutes;
                   1393: 
                   1394:     return n;
                   1395: }
                   1396: 
                   1397: 
                   1398: /*
                   1399:  * Print the contents of the routing table on file 'fp'.
                   1400:  */
                   1401: void dump_routes(FILE *fp)
                   1402: {
                   1403:     struct rtentry *r;
                   1404:     vifi_t i;
                   1405: 
                   1406:     fprintf(fp, "Multicast Routing Table (%u entr%s)\n", nroutes, nroutes == 1 ? "y" : "ies");
                   1407:     fputs(" Origin-Subnet      From-Gateway    Metric Tmr Fl In-Vif  Out-Vifs\n", fp);
                   1408: 
                   1409:     for (r = routing_table; r; r = r->rt_next) {
                   1410:        fprintf(fp, " %-18s %-15s ",
                   1411:                inet_fmts(r->rt_origin, r->rt_originmask, s1, sizeof(s1)),
                   1412:                (r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway, s2, sizeof(s2)));
                   1413: 
1.1.1.2.2.1! misho    1414:        if (r->rt_metric == UNREACHABLE)
        !          1415:                fprintf(fp, "  NR ");
        !          1416:        else
        !          1417:                fprintf(fp, "%4u ", r->rt_metric);
1.1       misho    1418: 
                   1419:        fprintf(fp, "  %3u %c%c %3u   ", r->rt_timer,
                   1420:                (r->rt_flags & RTF_CHANGED) ? 'C' : '.',
                   1421:                (r->rt_flags & RTF_HOLDDOWN) ? 'H' : '.',
                   1422:                r->rt_parent);
                   1423: 
                   1424:        for (i = 0; i < numvifs; ++i) {
                   1425:            struct listaddr *n;
                   1426:            char l = '[';
                   1427: 
                   1428:            if (VIFM_ISSET(i, r->rt_children)) {
                   1429:                if ((uvifs[i].uv_flags & VIFF_TUNNEL) &&
                   1430:                    !NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
                   1431:                        /* Don't print out parenthood of a leaf tunnel. */
                   1432:                        continue;
                   1433: 
                   1434:                fprintf(fp, " %u", i);
                   1435:                if (!NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
                   1436:                    fprintf(fp, "*");
                   1437: 
                   1438:                for (n = uvifs[i].uv_neighbors; n; n = n->al_next) {
                   1439:                    if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
                   1440:                        fprintf(fp, "%c%d", l, n->al_index);
                   1441:                        l = ',';
                   1442:                    }
                   1443:                }
                   1444: 
                   1445:                if (l == ',')
                   1446:                    fprintf(fp, "]");
                   1447:            }
                   1448:        }
                   1449:        fprintf(fp, "\n");
                   1450:     }
                   1451:     fprintf(fp, "\n");
                   1452: }
                   1453: 
                   1454: struct rtentry *determine_route(u_int32 src)
                   1455: {
                   1456:     struct rtentry *rt;
                   1457: 
                   1458:     for (rt = routing_table; rt != NULL; rt = rt->rt_next) {
                   1459:        if (rt->rt_origin == (src & rt->rt_originmask) &&
                   1460:            rt->rt_metric != UNREACHABLE) 
                   1461:            break;
                   1462:     }
                   1463: 
                   1464:     return rt;
                   1465: }
                   1466: 
                   1467: /**
                   1468:  * Local Variables:
                   1469:  *  version-control: t
                   1470:  *  indent-tabs-mode: t
                   1471:  *  c-file-style: "ellemtel"
                   1472:  *  c-basic-offset: 4
                   1473:  * End:
                   1474:  */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>