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