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