usr.sbin/mrouted/route.c

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