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.5 2005/12/05 00:58:50 swildner 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(u_int32 src, u_int32 mask)
  67 {
  68    struct rtentry *rt;
  69
  70    for (rt = routing_table; rt; rt = rt->rt_next) {
  71       if (src == rt->rt_origin && mask == rt->rt_originmask)
  72          return rt;
  73    }
  74    return NULL;
  75 }
  76
  77 /*
  78  * Find next route entry > specification
  79  */
  80 int
  81 next_route(struct rtentry **rtpp, u_int32 src, u_int32 mask)
  82 {
  83    struct rtentry *rt, *rbest = NULL;
  84
  85    /* Among all entries > spec, find "lowest" one in order */
  86    for (rt = routing_table; rt; rt=rt->rt_next) {
  87       if ((ntohl(rt->rt_origin) > ntohl(src)
  88           || (ntohl(rt->rt_origin) == ntohl(src)
  89              && ntohl(rt->rt_originmask) > ntohl(mask)))
  90        && (!rbest || (ntohl(rt->rt_origin) < ntohl(rbest->rt_origin))
  91           || (ntohl(rt->rt_origin) == ntohl(rbest->rt_origin)
  92              && ntohl(rt->rt_originmask) < ntohl(rbest->rt_originmask))))
  93                rbest = rt;
  94    }
  95    (*rtpp) = rbest;
  96    return (*rtpp)!=0;
  97 }
  98
  99 /*
 100  * Given a routing table entry, and a vifi, find the next vifi/entry
 101  */
 102 int
 103 next_route_child(struct rtentry **rtpp, u_int32 src, u_int32 mask, vifi_t *vifi)
 104 {
 105    /* Get (S,M) entry */
 106    if (!((*rtpp) = snmp_find_route(src,mask)))
 107       if (!next_route(rtpp, src, mask))
 108          return 0;
 109
 110    /* Continue until we get one with a valid next vif */
 111    do {
 112       for (; (*rtpp)->rt_children && *vifi<numvifs; (*vifi)++)
 113          if (VIFM_ISSET(*vifi, (*rtpp)->rt_children))
 114             return 1;
 115       *vifi = 0;
 116    } while( next_route(rtpp, (*rtpp)->rt_origin, (*rtpp)->rt_originmask) );
 117
 118    return 0;
 119 }
 120 #endif
 121
 122 /*
 123  * Initialize the routing table and associated variables.
 124  */
 125 void
 126 init_routes(void)
 127 {
 128     routing_table        = NULL;
 129     rt_end               = RT_ADDR;
 130     nroutes              = 0;
 131     routes_changed       = FALSE;
 132     delay_change_reports = FALSE;
 133 }
 134
 135
 136 /*
 137  * Initialize the children bits for route 'r', along with the
 138  * associated dominant and subordinate data structures.
 139  * If first is set, initialize dominants, otherwise keep old
 140  * dominants on non-parent interfaces.
 141  * XXX Does this need a return value?
 142  */
 143 static int
 144 init_children_and_leaves(struct rtentry *r, vifi_t parent, int first)
 145 {
 146     vifi_t vifi;
 147     struct uvif *v;
 148     vifbitmap_t old_children;
 149     nbrbitmap_t old_subords;
 150
 151     VIFM_COPY(r->rt_children, old_children);
 152     NBRM_COPY(r->rt_subordinates, old_subords);
 153
 154     VIFM_CLRALL(r->rt_children);
 155
 156     for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
 157         if (first || vifi == parent)
 158             r->rt_dominants   [vifi] = 0;
 159         if (vifi == parent || uvifs[vifi].uv_flags & VIFF_NOFLOOD ||
 160                 AVOID_TRANSIT(vifi, r) || (!first && r->rt_dominants[vifi]))
 161             NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 162         else
 163             NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 164
 165         if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED)) &&
 166                 !(!first && r->rt_dominants[vifi])) {
 167             VIFM_SET(vifi, r->rt_children);
 168         }
 169     }
 170
 171     return (!VIFM_SAME(r->rt_children, old_children) ||
 172             !NBRM_SAME(r->rt_subordinates, old_subords));
 173 }
 174
 175
 176 /*
 177  * A new vif has come up -- update the children bitmaps in all route
 178  * entries to take that into account.
 179  */
 180 void
 181 add_vif_to_routes(vifi_t vifi)
 182 {
 183     struct rtentry *r;
 184     struct uvif *v;
 185
 186     v = &uvifs[vifi];
 187     for (r = routing_table; r != NULL; r = r->rt_next) {
 188         if (r->rt_metric != UNREACHABLE &&
 189             !VIFM_ISSET(vifi, r->rt_children)) {
 190             VIFM_SET(vifi, r->rt_children);
 191             r->rt_dominants   [vifi] = 0;
 192             /*XXX isn't uv_nbrmap going to be empty?*/
 193             NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
 194             update_table_entry(r, r->rt_gateway);
 195         }
 196     }
 197 }
 198
 199
 200 /*
 201  * A vif has gone down -- expire all routes that have that vif as parent,
 202  * and update the children bitmaps in all other route entries to take into
 203  * account the failed vif.
 204  */
 205 void
 206 delete_vif_from_routes(vifi_t vifi)
 207 {
 208     struct rtentry *r;
 209
 210     for (r = routing_table; r != NULL; r = r->rt_next) {
 211         if (r->rt_metric != UNREACHABLE) {
 212             if (vifi == r->rt_parent) {
 213                 del_table_entry(r, 0, DEL_ALL_ROUTES);
 214                 r->rt_timer    = ROUTE_EXPIRE_TIME;
 215                 r->rt_metric   = UNREACHABLE;
 216                 r->rt_flags   |= RTF_CHANGED;
 217                 routes_changed = TRUE;
 218             }
 219             else if (VIFM_ISSET(vifi, r->rt_children)) {
 220                 VIFM_CLR(vifi, r->rt_children);
 221                 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 222                 update_table_entry(r, r->rt_gateway);
 223             }
 224             else {
 225                 r->rt_dominants[vifi] = 0;
 226             }
 227         }
 228     }
 229 }
 230
 231
 232 /*
 233  * A new neighbor has come up.  If we're flooding on the neighbor's
 234  * vif, mark that neighbor as subordinate for all routes whose parent
 235  * is not this vif.
 236  */
 237 void
 238 add_neighbor_to_routes(vifi_t vifi, int index)
 239 {
 240     struct rtentry *r;
 241     struct uvif *v;
 242
 243     v = &uvifs[vifi];
 244     if (v->uv_flags & VIFF_NOFLOOD)
 245         return;
 246     for (r = routing_table; r != NULL; r = r->rt_next) {
 247         if (r->rt_metric != UNREACHABLE && r->rt_parent != vifi &&
 248                 !AVOID_TRANSIT(vifi, r)) {
 249             NBRM_SET(index, r->rt_subordinates);
 250             update_table_entry(r, r->rt_gateway);
 251         }
 252     }
 253 }
 254
 255
 256 /*
 257  * A neighbor has failed or become unreachable.  If that neighbor was
 258  * considered a dominant or subordinate router in any route entries,
 259  * take appropriate action.  Expire all routes this neighbor advertised
 260  * to us.
 261  */
 262 void
 263 delete_neighbor_from_routes(u_int32 addr, vifi_t vifi, int index)
 264 {
 265     struct rtentry *r;
 266     struct uvif *v;
 267
 268     v = &uvifs[vifi];
 269     for (r = routing_table; r != NULL; r = r->rt_next) {
 270         if (r->rt_metric != UNREACHABLE) {
 271             if (r->rt_parent == vifi && r->rt_gateway == addr) {
 272                 del_table_entry(r, 0, DEL_ALL_ROUTES);
 273                 r->rt_timer    = ROUTE_EXPIRE_TIME;
 274                 r->rt_metric   = UNREACHABLE;
 275                 r->rt_flags   |= RTF_CHANGED;
 276                 routes_changed = TRUE;
 277             } else if (r->rt_dominants[vifi] == addr) {
 278                 VIFM_SET(vifi, r->rt_children);
 279                 r->rt_dominants[vifi] = 0;
 280                 if ((uvifs[vifi].uv_flags & VIFF_NOFLOOD) ||
 281                                 AVOID_TRANSIT(vifi, r))
 282                     NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 283                 else
 284                     NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 285                 update_table_entry(r, r->rt_gateway);
 286             } else if (NBRM_ISSET(index, r->rt_subordinates)) {
 287                 NBRM_CLR(index, r->rt_subordinates);
 288                 update_table_entry(r, r->rt_gateway);
 289             }
 290         }
 291     }
 292 }
 293
 294
 295 /*
 296  * Prepare for a sequence of ordered route updates by initializing a pointer
 297  * to the start of the routing table.  The pointer is used to remember our
 298  * position in the routing table in order to avoid searching from the
 299  * beginning for each update; this relies on having the route reports in
 300  * a single message be in the same order as the route entries in the routing
 301  * table.
 302  */
 303 void
 304 start_route_updates(void)
 305 {
 306     rtp = RT_ADDR;
 307 }
 308
 309
 310 /*
 311  * Starting at the route entry following the one to which 'rtp' points,
 312  * look for a route entry matching the specified origin and mask.  If a
 313  * match is found, return TRUE and leave 'rtp' pointing at the found entry.
 314  * If no match is found, return FALSE and leave 'rtp' pointing to the route
 315  * entry preceding the point at which the new origin should be inserted.
 316  * This code is optimized for the normal case in which the first entry to
 317  * be examined is the matching entry.
 318  */
 319 static int
 320 find_route(u_int32 origin, u_int32 mask)
 321 {
 322     struct rtentry *r;
 323
 324     r = rtp->rt_next;
 325     while (r != NULL) {
 326         if (origin == r->rt_origin && mask == r->rt_originmask) {
 327             rtp = r;
 328             return (TRUE);
 329         }
 330         if (ntohl(mask) < ntohl(r->rt_originmask) ||
 331             (mask == r->rt_originmask &&
 332              ntohl(origin) < ntohl(r->rt_origin))) {
 333             rtp = r;
 334             r = r->rt_next;
 335         }
 336         else break;
 337     }
 338     return (FALSE);
 339 }
 340
 341 /*
 342  * Create a new routing table entry for the specified origin and link it into
 343  * the routing table.  The shared variable 'rtp' is assumed to point to the
 344  * routing entry after which the new one should be inserted.  It is left
 345  * pointing to the new entry.
 346  *
 347  * Only the origin, originmask, originwidth and flags fields are initialized
 348  * in the new route entry; the caller is responsible for filling in the the
 349  * rest.
 350  */
 351 static void
 352 create_route(u_int32 origin, u_int32 mask)
 353 {
 354     struct rtentry *r;
 355
 356     if ((r = (struct rtentry *) malloc(sizeof(struct rtentry) +
 357                                        (numvifs * sizeof(u_int32)))) == NULL) {
 358         dolog(LOG_ERR, 0, "ran out of memory"); /* fatal */
 359     }
 360     r->rt_origin     = origin;
 361     r->rt_originmask = mask;
 362     if      (((char *)&mask)[3] != 0) r->rt_originwidth = 4;
 363     else if (((char *)&mask)[2] != 0) r->rt_originwidth = 3;
 364     else if (((char *)&mask)[1] != 0) r->rt_originwidth = 2;
 365     else                              r->rt_originwidth = 1;
 366     r->rt_flags        = 0;
 367     r->rt_dominants    = (u_int32 *)(r + 1);
 368     bzero(r->rt_dominants, numvifs * sizeof(u_int32));
 369     r->rt_groups       = NULL;
 370     VIFM_CLRALL(r->rt_children);
 371     NBRM_CLRALL(r->rt_subordinates);
 372     NBRM_CLRALL(r->rt_subordadv);
 373
 374     r->rt_next = rtp->rt_next;
 375     rtp->rt_next = r;
 376     r->rt_prev = rtp;
 377     if (r->rt_next != NULL)
 378       (r->rt_next)->rt_prev = r;
 379     else
 380       rt_end = r;
 381     rtp = r;
 382     ++nroutes;
 383 }
 384
 385
 386 /*
 387  * Discard the routing table entry following the one to which 'prev_r' points.
 388  */
 389 static void
 390 discard_route(struct rtentry *prev_r)
 391 {
 392     struct rtentry *r;
 393
 394     r = prev_r->rt_next;
 395     uvifs[r->rt_parent].uv_nroutes--;
 396     /*???nbr???.al_nroutes--;*/
 397     prev_r->rt_next = r->rt_next;
 398     if (prev_r->rt_next != NULL)
 399       (prev_r->rt_next)->rt_prev = prev_r;
 400     else
 401       rt_end = prev_r;
 402     free((char *)r);
 403     --nroutes;
 404 }
 405
 406
 407 /*
 408  * Process a route report for a single origin, creating or updating the
 409  * corresponding routing table entry if necessary.  'src' is either the
 410  * address of a neighboring router from which the report arrived, or zero
 411  * to indicate a change of status of one of our own interfaces.
 412  */
 413 void
 414 update_route(u_int32 origin, u_int32 mask, u_int metric, u_int32 src,
 415              vifi_t vifi, struct listaddr *n)
 416 {
 417     struct rtentry *r;
 418     u_int adj_metric;
 419
 420     /*
 421      * Compute an adjusted metric, taking into account the cost of the
 422      * subnet or tunnel over which the report arrived, and normalizing
 423      * all unreachable/poisoned metrics into a single value.
 424      */
 425     if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
 426         dolog(LOG_WARNING, 0,
 427             "%s reports out-of-range metric %u for origin %s",
 428             inet_fmt(src, s1), metric, inet_fmts(origin, mask, s2));
 429         return;
 430     }
 431     adj_metric = metric + uvifs[vifi].uv_metric;
 432     if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;
 433
 434     /*
 435      * Look up the reported origin in the routing table.
 436      */
 437     if (!find_route(origin, mask)) {
 438         /*
 439          * Not found.
 440          * Don't create a new entry if the report says it's unreachable,
 441          * or if the reported origin and mask are invalid.
 442          */
 443         if (adj_metric == UNREACHABLE) {
 444             return;
 445         }
 446         if (src != 0 && !inet_valid_subnet(origin, mask)) {
 447             dolog(LOG_WARNING, 0,
 448                 "%s reports an invalid origin (%s) and/or mask (%08x)",
 449                 inet_fmt(src, s1), inet_fmt(origin, s2), ntohl(mask));
 450             return;
 451         }
 452
 453         IF_DEBUG(DEBUG_RTDETAIL)
 454         dolog(LOG_DEBUG, 0, "%s advertises new route %s",
 455                 inet_fmt(src, s1), inet_fmts(origin, mask, s2));
 456
 457         /*
 458          * OK, create the new routing entry.  'rtp' will be left pointing
 459          * to the new entry.
 460          */
 461         create_route(origin, mask);
 462         uvifs[vifi].uv_nroutes++;
 463         /*n->al_nroutes++;*/
 464
 465         rtp->rt_metric = UNREACHABLE;   /* temporary; updated below */
 466     }
 467
 468     /*
 469      * We now have a routing entry for the reported origin.  Update it?
 470      */
 471     r = rtp;
 472     if (r->rt_metric == UNREACHABLE) {
 473         /*
 474          * The routing entry is for a formerly-unreachable or new origin.
 475          * If the report claims reachability, update the entry to use
 476          * the reported route.
 477          */
 478         if (adj_metric == UNREACHABLE)
 479             return;
 480
 481         IF_DEBUG(DEBUG_RTDETAIL)
 482         dolog(LOG_DEBUG, 0, "%s advertises %s with adj_metric %d (ours was %d)",
 483                 inet_fmt(src, s1), inet_fmts(origin, mask, s2),
 484                 adj_metric, r->rt_metric);
 485
 486         /*
 487          * Now "steal away" any sources that belong under this route
 488          * by deleting any cache entries they might have created
 489          * and allowing the kernel to re-request them.
 490          *
 491          * If we haven't performed final initialization yet and are
 492          * just collecting the routing table, we can't have any
 493          * sources so we don't perform this step.
 494          */
 495         if (did_final_init)
 496             steal_sources(rtp);
 497
 498         r->rt_parent   = vifi;
 499         r->rt_gateway  = src;
 500         init_children_and_leaves(r, vifi, 1);
 501
 502         r->rt_timer    = 0;
 503         r->rt_metric   = adj_metric;
 504         r->rt_flags   |= RTF_CHANGED;
 505         routes_changed = TRUE;
 506         update_table_entry(r, r->rt_gateway);
 507     }
 508     else if (src == r->rt_gateway) {
 509         /*
 510          * The report has come either from the interface directly-connected
 511          * to the origin subnet (src and r->rt_gateway both equal zero) or
 512          * from the gateway we have chosen as the best first-hop gateway back
 513          * towards the origin (src and r->rt_gateway not equal zero).  Reset
 514          * the route timer and, if the reported metric has changed, update
 515          * our entry accordingly.
 516          */
 517         r->rt_timer = 0;
 518
 519         IF_DEBUG(DEBUG_RTDETAIL)
 520         dolog(LOG_DEBUG, 0, "%s (current parent) advertises %s with adj_metric %d (ours was %d)",
 521                 inet_fmt(src, s1), inet_fmts(origin, mask, s2),
 522                 adj_metric, r->rt_metric);
 523
 524         if (adj_metric == r->rt_metric)
 525             return;
 526
 527         if (adj_metric == UNREACHABLE) {
 528             del_table_entry(r, 0, DEL_ALL_ROUTES);
 529             r->rt_timer = ROUTE_EXPIRE_TIME;
 530         }
 531         r->rt_metric   = adj_metric;
 532         r->rt_flags   |= RTF_CHANGED;
 533         routes_changed = TRUE;
 534     }
 535     else if (src == 0 ||
 536              (r->rt_gateway != 0 &&
 537               (adj_metric < r->rt_metric ||
 538                (adj_metric == r->rt_metric &&
 539                 (ntohl(src) < ntohl(r->rt_gateway) ||
 540                  r->rt_timer >= ROUTE_SWITCH_TIME))))) {
 541         /*
 542          * The report is for an origin we consider reachable; the report
 543          * comes either from one of our own interfaces or from a gateway
 544          * other than the one we have chosen as the best first-hop gateway
 545          * back towards the origin.  If the source of the update is one of
 546          * our own interfaces, or if the origin is not a directly-connected
 547          * subnet and the reported metric for that origin is better than
 548          * what our routing entry says, update the entry to use the new
 549          * gateway and metric.  We also switch gateways if the reported
 550          * metric is the same as the one in the route entry and the gateway
 551          * associated with the route entry has not been heard from recently,
 552          * or if the metric is the same but the reporting gateway has a lower
 553          * IP address than the gateway associated with the route entry.
 554          * Did you get all that?
 555          */
 556         u_int32 old_gateway;
 557         vifi_t old_parent;
 558         old_gateway = r->rt_gateway;
 559         old_parent = r->rt_parent;
 560         r->rt_gateway = src;
 561         r->rt_parent = vifi;
 562
 563         IF_DEBUG(DEBUG_RTDETAIL)
 564         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)",
 565                 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 566                 adj_metric, inet_fmt(old_gateway, s3), old_parent,
 567                 r->rt_metric);
 568
 569         if (old_parent != vifi) {
 570             init_children_and_leaves(r, vifi, 0);
 571             uvifs[old_parent].uv_nroutes--;
 572             uvifs[vifi].uv_nroutes++;
 573         }
 574         if (old_gateway != src) {
 575             update_table_entry(r, old_gateway);
 576             /*???old_gateway???->al_nroutes--;*/
 577             /*n->al_nroutes++;*/
 578         }
 579         r->rt_timer    = 0;
 580         r->rt_metric   = adj_metric;
 581         r->rt_flags   |= RTF_CHANGED;
 582         routes_changed = TRUE;
 583     }
 584     else if (vifi != r->rt_parent) {
 585         /*
 586          * The report came from a vif other than the route's parent vif.
 587          * Update the children info, if necessary.
 588          */
 589         if (AVOID_TRANSIT(vifi, r)) {
 590             /*
 591              * The route's parent is a vif from which we're not supposed
 592              * to transit onto this vif.  Simply ignore the update.
 593              */
 594             IF_DEBUG(DEBUG_RTDETAIL)
 595             dolog(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored due to NOTRANSIT)",
 596                 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 597                 metric);
 598         } else if (VIFM_ISSET(vifi, r->rt_children)) {
 599             /*
 600              * Vif is a child vif for this route.
 601              */
 602             if (metric  < r->rt_metric ||
 603                 (metric == r->rt_metric &&
 604                  ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
 605                 /*
 606                  * Neighbor has lower metric to origin (or has same metric
 607                  * and lower IP address) -- it becomes the dominant router,
 608                  * and vif is no longer a child for me.
 609                  */
 610                 VIFM_CLR(vifi, r->rt_children);
 611                 r->rt_dominants   [vifi] = src;
 612                 /* XXX
 613                  * We don't necessarily want to forget about subordinateness
 614                  * so that we can become the dominant quickly if the current
 615                  * dominant fails.
 616                  */
 617                 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 618                 update_table_entry(r, r->rt_gateway);
 619                 IF_DEBUG(DEBUG_RTDETAIL)
 620                 dolog(LOG_DEBUG, 0, "%s on vif %d becomes dominant for %s with metric %d",
 621                     inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 622                     metric);
 623             }
 624             else if (metric > UNREACHABLE) {    /* "poisoned reverse" */
 625                 /*
 626                  * Neighbor considers this vif to be on path to route's
 627                  * origin; record this neighbor as subordinate
 628                  */
 629                 if (!NBRM_ISSET(n->al_index, r->rt_subordinates)) {
 630                     IF_DEBUG(DEBUG_RTDETAIL)
 631                     dolog(LOG_DEBUG, 0, "%s on vif %d becomes subordinate for %s with poison-reverse metric %d",
 632                         inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 633                         metric - UNREACHABLE);
 634                     NBRM_SET(n->al_index, r->rt_subordinates);
 635                     update_table_entry(r, r->rt_gateway);
 636                 } else {
 637                     IF_DEBUG(DEBUG_RTDETAIL)
 638                     dolog(LOG_DEBUG, 0, "%s on vif %d confirms subordinateness for %s with poison-reverse metric %d",
 639                         inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 640                         metric - UNREACHABLE);
 641                 }
 642                 NBRM_SET(n->al_index, r->rt_subordadv);
 643             }
 644             else if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
 645                 /*
 646                  * Current subordinate no longer considers this vif to be on
 647                  * path to route's origin; it is no longer a subordinate
 648                  * router.
 649                  */
 650                 IF_DEBUG(DEBUG_RTDETAIL)
 651                 dolog(LOG_DEBUG, 0, "%s on vif %d is no longer a subordinate for %s with metric %d",
 652                     inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 653                     metric);
 654                 NBRM_CLR(n->al_index, r->rt_subordinates);
 655                 update_table_entry(r, r->rt_gateway);
 656             }
 657
 658         }
 659         else if (src == r->rt_dominants[vifi] &&
 660                  (metric  > r->rt_metric ||
 661                   (metric == r->rt_metric &&
 662                    ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
 663             /*
 664              * Current dominant no longer has a lower metric to origin
 665              * (or same metric and lower IP address); we adopt the vif
 666              * as our own child.
 667              */
 668             IF_DEBUG(DEBUG_RTDETAIL)
 669             dolog(LOG_DEBUG, 0, "%s (current dominant) on vif %d is no longer dominant for %s with metric %d",
 670                 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 671                 metric);
 672             VIFM_SET(vifi, r->rt_children);
 673             r->rt_dominants[vifi] = 0;
 674             if (uvifs[vifi].uv_flags & VIFF_NOFLOOD)
 675                 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 676             else
 677                 NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
 678             if (metric > UNREACHABLE) {
 679                 NBRM_SET(n->al_index, r->rt_subordinates);
 680                 NBRM_SET(n->al_index, r->rt_subordadv);
 681             }
 682             update_table_entry(r, r->rt_gateway);
 683         } else {
 684             IF_DEBUG(DEBUG_RTDETAIL)
 685             dolog(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored)",
 686                 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
 687                 metric);
 688         }
 689     }
 690 }
 691
 692
 693 /*
 694  * On every timer interrupt, advance the timer in each routing entry.
 695  */
 696 void
 697 age_routes(void)
 698 {
 699     struct rtentry *r;
 700     struct rtentry *prev_r;
 701     extern u_long virtual_time;         /* from main.c */
 702
 703     for (prev_r = RT_ADDR, r = routing_table;
 704          r != NULL;
 705          prev_r = r, r = r->rt_next) {
 706
 707         if ((r->rt_timer += TIMER_INTERVAL) >= ROUTE_DISCARD_TIME) {
 708             /*
 709              * Time to garbage-collect the route entry.
 710              */
 711             del_table_entry(r, 0, DEL_ALL_ROUTES);
 712             discard_route(prev_r);
 713             r = prev_r;
 714         }
 715         else if (r->rt_timer >= ROUTE_EXPIRE_TIME &&
 716                  r->rt_metric != UNREACHABLE) {
 717             /*
 718              * Time to expire the route entry.  If the gateway is zero,
 719              * i.e., it is a route to a directly-connected subnet, just
 720              * set the timer back to zero; such routes expire only when
 721              * the interface to the subnet goes down.
 722              */
 723             if (r->rt_gateway == 0) {
 724                 r->rt_timer = 0;
 725             }
 726             else {
 727                 del_table_entry(r, 0, DEL_ALL_ROUTES);
 728                 r->rt_metric   = UNREACHABLE;
 729                 r->rt_flags   |= RTF_CHANGED;
 730                 routes_changed = TRUE;
 731             }
 732         }
 733         else if (virtual_time % (ROUTE_REPORT_INTERVAL * 2) == 0) {
 734             /*
 735              * Time out subordinateness that hasn't been reported in
 736              * the last 2 intervals.
 737              */
 738             if (!NBRM_SAME(r->rt_subordinates, r->rt_subordadv)) {
 739                 IF_DEBUG(DEBUG_ROUTE)
 740                 dolog(LOG_DEBUG, 0, "rt %s sub 0x%08x%08x subadv 0x%08x%08x metric %d",
 741                         RT_FMT(r, s1),
 742                         r->rt_subordinates.hi, r->rt_subordinates.lo,
 743                         r->rt_subordadv.hi, r->rt_subordadv.lo, r->rt_metric);
 744                 NBRM_MASK(r->rt_subordinates, r->rt_subordadv);
 745                 update_table_entry(r, r->rt_gateway);
 746             }
 747             NBRM_CLRALL(r->rt_subordadv);
 748         }
 749     }
 750 }
 751
 752
 753 /*
 754  * Mark all routes as unreachable.  This function is called only from
 755  * hup() in preparation for informing all neighbors that we are going
 756  * off the air.  For consistency, we ought also to delete all reachable
 757  * route entries from the kernel, but since we are about to exit we rely
 758  * on the kernel to do its own cleanup -- no point in making all those
 759  * expensive kernel calls now.
 760  */
 761 void
 762 expire_all_routes(void)
 763 {
 764     struct rtentry *r;
 765
 766     for (r = routing_table; r != NULL; r = r->rt_next) {
 767         r->rt_metric   = UNREACHABLE;
 768         r->rt_flags   |= RTF_CHANGED;
 769         routes_changed = TRUE;
 770     }
 771 }
 772
 773
 774 /*
 775  * Delete all the routes in the routing table.
 776  */
 777 void
 778 free_all_routes(void)
 779 {
 780     struct rtentry *r;
 781
 782     r = RT_ADDR;
 783
 784     while (r->rt_next)
 785         discard_route(r);
 786 }
 787
 788
 789 /*
 790  * Process an incoming neighbor probe message.
 791  */
 792 void
 793 accept_probe(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
 794 {
 795     vifi_t vifi;
 796     static struct listaddr *unknowns = NULL;
 797
 798     if ((vifi = find_vif(src, dst)) == NO_VIF) {
 799         struct listaddr *a, **prev;
 800         struct listaddr *match = NULL;
 801         time_t now = time(0);
 802
 803         for (prev = &unknowns, a = *prev; a; a = *prev) {
 804             if (a->al_addr == src)
 805                 match = a;
 806             if (a->al_ctime + 2 * a->al_timer < now) {
 807                 /* We haven't heard from it in a long time */
 808                 *prev = a->al_next;
 809                 free(a);
 810             } else {
 811                 prev = &a->al_next;
 812             }
 813         }
 814         if (match == NULL) {
 815             match = *prev = (struct listaddr *)malloc(sizeof(struct listaddr));
 816             match->al_next = NULL;
 817             match->al_addr = src;
 818             match->al_timer = OLD_NEIGHBOR_EXPIRE_TIME;
 819             match->al_ctime = now - match->al_timer;
 820         }
 821
 822         if (match->al_ctime + match->al_timer <= now) {
 823             dolog(LOG_WARNING, 0,
 824                 "ignoring probe from non-neighbor %s, check for misconfigured tunnel or routing on %s",
 825                 inet_fmt(src, s1), s1);
 826             match->al_timer *= 2;
 827         } else
 828             IF_DEBUG(DEBUG_PEER)
 829             dolog(LOG_DEBUG, 0,
 830                 "ignoring probe from non-neighbor %s (%d seconds until next warning)", inet_fmt(src, s1), match->al_ctime + match->al_timer - now);
 831         return;
 832     }
 833
 834     update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
 835 }
 836
 837 struct newrt {
 838         u_int32 mask;
 839         u_int32 origin;
 840         int metric;
 841         int pad;
 842 };
 843
 844 static int
 845 compare_rts(const void *rt1, const void *rt2)
 846 {
 847     struct newrt *r1 = (struct newrt *)rt1;
 848     struct newrt *r2 = (struct newrt *)rt2;
 849     u_int32 m1 = ntohl(r1->mask);
 850     u_int32 m2 = ntohl(r2->mask);
 851     u_int32 o1, o2;
 852
 853     if (m1 > m2)
 854         return (-1);
 855     if (m1 < m2)
 856         return (1);
 857
 858     /* masks are equal */
 859     o1 = ntohl(r1->origin);
 860     o2 = ntohl(r2->origin);
 861     if (o1 > o2)
 862         return (-1);
 863     if (o1 < o2)
 864         return (1);
 865     return (0);
 866 }
 867
 868 void
 869 blaster_alloc(vifi_t vifi)
 870 {
 871     struct uvif *v;
 872
 873     v = &uvifs[vifi];
 874     if (v->uv_blasterbuf)
 875         free(v->uv_blasterbuf);
 876
 877     v->uv_blasterlen = 64*1024;
 878     v->uv_blasterbuf = malloc(v->uv_blasterlen);
 879     v->uv_blastercur = v->uv_blasterend = v->uv_blasterbuf;
 880     if (v->uv_blastertimer)
 881         timer_clearTimer(v->uv_blastertimer);
 882     v->uv_blastertimer = 0;
 883 }
 884
 885 struct blaster_hdr {
 886     u_int32     bh_src;
 887     u_int32     bh_dst;
 888     u_int32     bh_level;
 889     int         bh_datalen;
 890 };
 891
 892 /*
 893  * Queue a route report from a route-blaster.
 894  * If the timer isn't running to process these reports,
 895  * start it.
 896  */
 897 static void
 898 queue_blaster_report(vifi_t vifi, u_int32 src, u_int32 dst, char *p,
 899                      int datalen, u_int32 level)
 900 {
 901     struct blaster_hdr *bh;
 902     struct uvif *v;
 903     int bblen = sizeof(*bh) + ((datalen + 3) & ~3);
 904
 905     v = &uvifs[vifi];
 906     if (v->uv_blasterend - v->uv_blasterbuf +
 907                         bblen > v->uv_blasterlen) {
 908         int end = v->uv_blasterend - v->uv_blasterbuf;
 909         int cur = v->uv_blastercur - v->uv_blasterbuf;
 910
 911         v->uv_blasterlen *= 2;
 912         IF_DEBUG(DEBUG_IF)
 913         dolog(LOG_DEBUG, 0, "increasing blasterbuf to %d bytes",
 914                         v->uv_blasterlen);
 915         v->uv_blasterbuf = realloc(v->uv_blasterbuf,
 916                                         v->uv_blasterlen);
 917         if (v->uv_blasterbuf == NULL) {
 918             dolog(LOG_WARNING, ENOMEM, "turning off blaster on vif %d", vifi);
 919             v->uv_blasterlen = 0;
 920             v->uv_blasterend = v->uv_blastercur = NULL;
 921             v->uv_flags &= ~VIFF_BLASTER;
 922             return;
 923         }
 924         v->uv_blasterend = v->uv_blasterbuf + end;
 925         v->uv_blastercur = v->uv_blasterbuf + cur;
 926     }
 927     bh = (struct blaster_hdr *)v->uv_blasterend;
 928     bh->bh_src = src;
 929     bh->bh_dst = dst;
 930     bh->bh_level = level;
 931     bh->bh_datalen = datalen;
 932     bcopy(p, (char *)(bh + 1), datalen);
 933     v->uv_blasterend += bblen;
 934
 935     if (v->uv_blastertimer == 0) {
 936         int *i = (int *)malloc(sizeof(int *));
 937
 938         if (i == NULL)
 939                 dolog(LOG_ERR, 0, "out of memory");
 940
 941         *i = vifi;
 942
 943         v->uv_blastertimer = timer_setTimer(5,
 944                                             process_blaster_report, i);
 945     }
 946 }
 947
 948 /*
 949  * Periodic process; process up to 5 of the routes in the route-blaster
 950  * queue.  If there are more routes remaining, reschedule myself to run
 951  * in 1 second.
 952  */
 953 static void
 954 process_blaster_report(void *vifip)
 955 {
 956     vifi_t vifi = *(int *)vifip;
 957     struct uvif *v;
 958     struct blaster_hdr *bh;
 959     int i;
 960
 961     IF_DEBUG(DEBUG_ROUTE)
 962     dolog(LOG_DEBUG, 0, "processing vif %d blasted routes", vifi);
 963     v = &uvifs[vifi];
 964     for (i = 0; i < 5; i++) {
 965         if (v->uv_blastercur >= v->uv_blasterend)
 966                 break;
 967         bh = (struct blaster_hdr *)v->uv_blastercur;
 968         v->uv_blastercur += sizeof(*bh) + ((bh->bh_datalen + 3) & ~3);
 969         accept_report(bh->bh_src, bh->bh_dst, (char *)(bh + 1),
 970                                     -bh->bh_datalen, bh->bh_level);
 971     }
 972
 973     if (v->uv_blastercur >= v->uv_blasterend) {
 974         v->uv_blastercur = v->uv_blasterbuf;
 975         v->uv_blasterend = v->uv_blasterbuf;
 976         v->uv_blastertimer = 0;
 977         free(vifip);
 978         IF_DEBUG(DEBUG_ROUTE)
 979         dolog(LOG_DEBUG, 0, "finish processing vif %d blaster", vifi);
 980     } else {
 981         IF_DEBUG(DEBUG_ROUTE)
 982         dolog(LOG_DEBUG, 0, "more blasted routes to come on vif %d", vifi);
 983         v->uv_blastertimer = timer_setTimer(1,
 984                                             process_blaster_report, vifip);
 985     }
 986 }
 987
 988 /*
 989  * Process an incoming route report message.
 990  * If the report arrived on a vif marked as a "blaster", then just
 991  * queue it and return; queue_blaster_report() will schedule it for
 992  * processing later.  If datalen is negative, then this is actually
 993  * a queued report so actually process it instead of queueing it.
 994  */
 995 void
 996 accept_report(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
 997 {
 998     vifi_t vifi;
 999     int width, i, nrt = 0;
1000     int metric;
1001     u_int32 mask;
1002     u_int32 origin;
1003     struct newrt rt[4096];
1004     struct listaddr *nbr;
1005
1006     if ((vifi = find_vif(src, dst)) == NO_VIF) {
1007         dolog(LOG_INFO, 0,
1008             "ignoring route report from non-neighbor %s", inet_fmt(src, s1));
1009         return;
1010     }
1011
1012     if (uvifs[vifi].uv_flags & VIFF_BLASTER)
1013         if (datalen > 0) {
1014             queue_blaster_report(vifi, src, dst, p, datalen, level);
1015             return;
1016         } else {
1017             datalen = -datalen;
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 }