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