"Fossies" - the Fresh Open Source Software Archive

Member "mrouted-3.9.8/route.c" (1 Jan 2017, 40755 Bytes) of package /linux/misc/mrouted-3.9.8.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "route.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.9.7_vs_3.9.8.

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