text: /*
   * The mrouted program is covered by the license in the accompanying file
   * named "LICENSE".  Use of the mrouted program represents acceptance of
   * the terms and conditions listed in that file.
   *
   * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
   * Leland Stanford Junior University.
   */
  
  #include "defs.h"
  
  /*
   * Private macros.
   */
  #define MAX_NUM_RT   4096
  
  /*
   * Private types.
   */
  struct newrt {
  	u_int32 mask;
  	u_int32 origin;
  	int metric;
  	int pad;
  };
  
  struct blaster_hdr {
      u_int32	bh_src;
      u_int32	bh_dst;
      u_int32	bh_level;
      int		bh_datalen;
  };
  
  /*
   * Exported variables.
   */
  int routes_changed;			/* 1=>some routes have changed */
  int delay_change_reports;		/* 1=>postpone change reports  */
  unsigned int nroutes;			/* current number of route entries  */
  struct rtentry *routing_table;		/* pointer to list of route entries */
  
  /*
   * Private variables.
   */
  static struct rtentry *rtp;		/* pointer to a route entry         */
  static struct rtentry *rt_end;		/* pointer to last route entry      */
  
  /*
   * Private functions.
   */
  static int  init_children_and_leaves (struct rtentry *r, vifi_t parent, int first);
  static int  find_route               (u_int32 origin, u_int32 mask);
  static void create_route             (u_int32 origin, u_int32 mask);
  static void discard_route            (struct rtentry *this);
  static int  compare_rts              (const void *rt1, const void *rt2);
  static int  report_chunk             (int, struct rtentry *start_rt, vifi_t vifi, u_int32 dst);
  static void queue_blaster_report     (vifi_t vifi, u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level);
  static void process_blaster_report   (void *vifip);
  
  #ifdef SNMP
  #include <sys/types.h>
  #include "snmp.h"
  
  /*
   * Return pointer to a specific route entry.  This must be a separate
   * function from find_route() which modifies rtp.
   */
  struct rtentry *snmp_find_route(u_int32 src, u_int32 mask)
  {
      struct rtentry *rt;
  
     for (rt = routing_table; rt; rt = rt->rt_next) {
        if (src == rt->rt_origin && mask == rt->rt_originmask)
           return rt;
     }
  
     return NULL;
  }
  
  /*
   * Find next route entry > specification 
   */
  int next_route(struct rtentry **rtpp, u_int32 src, u_int32 mask)
  {
     struct rtentry *rt, *rbest = NULL;
  
     /* Among all entries > spec, find "lowest" one in order */
     for (rt = routing_table; rt; rt=rt->rt_next) {
        if ((ntohl(rt->rt_origin) > ntohl(src) 
            || (ntohl(rt->rt_origin) == ntohl(src) 
               && ntohl(rt->rt_originmask) > ntohl(mask)))
         && (!rbest || (ntohl(rt->rt_origin) < ntohl(rbest->rt_origin))
            || (ntohl(rt->rt_origin) == ntohl(rbest->rt_origin)
               && ntohl(rt->rt_originmask) < ntohl(rbest->rt_originmask))))
                 rbest = rt;
     }
     (*rtpp) = rbest;
  
     return (*rtpp)!=0;
  }
  
  /*
   * Given a routing table entry, and a vifi, find the next vifi/entry
   */
  int next_route_child(struct rtentry **rtpp, u_int32 src, u_int32 mask, vifi_t vifi)
  {
     /* Get (S,M) entry */
     if (!((*rtpp) = snmp_find_route(src, mask)))
        if (!next_route(rtpp, src, mask))
           return 0;
  
     /* Continue until we get one with a valid next vif */
     do {
        for (; (*rtpp)->rt_children && *vifi<numvifs; (*vifi)++)
           if (VIFM_ISSET(*vifi, (*rtpp)->rt_children))
              return 1;
        *vifi = 0;
     } while (next_route(rtpp, (*rtpp)->rt_origin, (*rtpp)->rt_originmask));
  
     return 0;
  }
  #endif	/* SNMP */
  
  /*
   * Initialize the routing table and associated variables.
   */
  void init_routes(void)
  {
      routing_table        = NULL;
      rt_end		 = NULL;
      nroutes		 = 0;
      routes_changed       = FALSE;
      delay_change_reports = FALSE;
  }
  
  
  /*
   * Initialize the children bits for route 'r', along with the
   * associated dominant and subordinate data structures.
   * If first is set, initialize dominants, otherwise keep old
   * dominants on non-parent interfaces.
   * XXX Does this need a return value?
   */
  static int init_children_and_leaves(struct rtentry *r, vifi_t parent, int first)
  {
      vifi_t vifi;
      struct uvif *v;
      vifbitmap_t old_children;
      nbrbitmap_t old_subords;
  
      VIFM_COPY(r->rt_children, old_children);
      NBRM_COPY(r->rt_subordinates, old_subords);
  
      VIFM_CLRALL(r->rt_children);
  
      for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
  	if (first || vifi == parent)
  	    r->rt_dominants[vifi] = 0;
  	if (vifi == parent || uvifs[vifi].uv_flags & VIFF_NOFLOOD ||
  		AVOID_TRANSIT(vifi, r) || (!first && r->rt_dominants[vifi]))
  	    NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
  	else
  	    NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
  
  	if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED)) &&
  	     	!(!first && r->rt_dominants[vifi])) {
  	    VIFM_SET(vifi, r->rt_children);
  	}
      }
  
      return (!VIFM_SAME(r->rt_children, old_children) ||
  	    !NBRM_SAME(r->rt_subordinates, old_subords));
  }
  
  
  /*
   * A new vif has come up -- update the children bitmaps in all route
   * entries to take that into account.
   */
  void add_vif_to_routes(vifi_t vifi)
  {
      struct rtentry *r;
      struct uvif *v;
  
      v = &uvifs[vifi];
      for (r = routing_table; r != NULL; r = r->rt_next) {
  	if (r->rt_metric != UNREACHABLE &&
  	    !VIFM_ISSET(vifi, r->rt_children)) {
  	    VIFM_SET(vifi, r->rt_children);
  	    r->rt_dominants[vifi] = 0;
  	    /*XXX isn't uv_nbrmap going to be empty?*/
  	    NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
  	    update_table_entry(r, r->rt_gateway);
  	}
      }
  }
  
  
  /*
   * A vif has gone down -- expire all routes that have that vif as parent,
   * and update the children bitmaps in all other route entries to take into
   * account the failed vif.
   */
  void delete_vif_from_routes(vifi_t vifi)
  {
      struct rtentry *r;
  
      for (r = routing_table; r != NULL; r = r->rt_next) {
  	if (r->rt_metric != UNREACHABLE) {
  	    if (vifi == r->rt_parent) {
  		del_table_entry(r, 0, DEL_ALL_ROUTES);
  		r->rt_timer    = ROUTE_EXPIRE_TIME;
  		r->rt_metric   = UNREACHABLE;
  		r->rt_flags   |= RTF_CHANGED;
  		routes_changed = TRUE;
  	    }
  	    else if (VIFM_ISSET(vifi, r->rt_children)) {
  		VIFM_CLR(vifi, r->rt_children);
  		NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
  		update_table_entry(r, r->rt_gateway);
  	    }
  	    else {
  		r->rt_dominants[vifi] = 0;
  	    }
  	}
      }
  }
  
  
  /*
   * A new neighbor has come up.  If we're flooding on the neighbor's
   * vif, mark that neighbor as subordinate for all routes whose parent
   * is not this vif.
   */
  void add_neighbor_to_routes(vifi_t vifi, u_int index)
  {
      struct rtentry *r;
      struct uvif *v;
  
      v = &uvifs[vifi];
      if (v->uv_flags & VIFF_NOFLOOD)
  	return;
      for (r = routing_table; r != NULL; r = r->rt_next) {
  	if (r->rt_metric != UNREACHABLE && r->rt_parent != vifi &&
  		!AVOID_TRANSIT(vifi, r)) {
  	    NBRM_SET(index, r->rt_subordinates);
  	    update_table_entry(r, r->rt_gateway);
  	}
      }
  }
  
  
  /*
   * A neighbor has failed or become unreachable.  If that neighbor was
   * considered a dominant or subordinate router in any route entries,
   * take appropriate action.  Expire all routes this neighbor advertised
   * to us.
   */
  void delete_neighbor_from_routes(u_int32 addr, vifi_t vifi, u_int index)
  {
      struct rtentry *r;
      struct uvif *v = &uvifs[vifi];
  
      for (r = routing_table; r != NULL; r = r->rt_next) {
  	if (r->rt_metric != UNREACHABLE) {
  	    if (r->rt_parent == vifi && r->rt_gateway == addr) {
  		del_table_entry(r, 0, DEL_ALL_ROUTES);
  		r->rt_timer    = ROUTE_EXPIRE_TIME;
  		r->rt_metric   = UNREACHABLE;
  		r->rt_flags   |= RTF_CHANGED;
  		routes_changed = TRUE;
  	    } else if (r->rt_dominants[vifi] == addr) {
  		VIFM_SET(vifi, r->rt_children);
  		r->rt_dominants[vifi] = 0;
  		if ((v->uv_flags & VIFF_NOFLOOD) || AVOID_TRANSIT(vifi, r))
  		    NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
  		else
  		    NBRM_SETMASK(r->rt_subordinates, v->uv_nbrmap);
  		update_table_entry(r, r->rt_gateway);
  	    } else if (NBRM_ISSET(index, r->rt_subordinates)) {
  		NBRM_CLR(index, r->rt_subordinates);
  		update_table_entry(r, r->rt_gateway);
  	    }
  	}
      }
  }
  
  
  /*
   * Prepare for a sequence of ordered route updates by initializing a pointer
   * to the start of the routing table.  The pointer is used to remember our
   * position in the routing table in order to avoid searching from the
   * beginning for each update; this relies on having the route reports in
   * a single message be in the same order as the route entries in the routing
   * table.
   *
   * find_route() expects rtp to be the preceding entry in the linked list
   * where route insertion takes place.  We need to be able to insert routes
   * before at the list head (routing table).
   */
  void start_route_updates(void)
  {
      rtp = NULL;
  }
  
  
  /*
   * Starting at the route entry following the one to which 'rtp' points,
   * look for a route entry matching the specified origin and mask.  If a
   * match is found, return TRUE and leave 'rtp' pointing at the found entry.
   * If no match is found, return FALSE and leave 'rtp' pointing to the route
   * entry preceding the point at which the new origin should be inserted.
   * This code is optimized for the normal case in which the first entry to
   * be examined is the matching entry.
   */
  static int find_route(u_int32 origin, u_int32 mask)
  {
      struct rtentry *r;
  
      /*
       * If rtp is NULL, we are preceding routing_table, so our first search
       * candidate should be the routing_table.
       */
      r = rtp ? rtp : routing_table;
      while (r != NULL) {
  	if (origin == r->rt_origin && mask == r->rt_originmask) {
  	    rtp = r;
  	    return TRUE;
  	}
  	if (ntohl(mask) < ntohl(r->rt_originmask) ||
  	    (mask == r->rt_originmask &&
  	     ntohl(origin) < ntohl(r->rt_origin))) {
  	    rtp = r;
  	    r = r->rt_next;
  	} else {
  	    break;
  	}
      }
      return FALSE;
  }
  
  /*
   * Create a new routing table entry for the specified origin and link it into
   * the routing table.  The shared variable 'rtp' is assumed to point to the
   * routing entry after which the new one should be inserted.  It is left
   * pointing to the new entry.
   *
   * Only the origin, originmask, originwidth and flags fields are initialized
   * in the new route entry; the caller is responsible for filling in the rest.
   */
  static void create_route(u_int32 origin, u_int32 mask)
  {
      size_t len;
      struct rtentry *this;
  
      this = (struct rtentry *)malloc(sizeof(struct rtentry));
      if (!this) {
  	logit(LOG_ERR, errno, "route.c:create_route() - Failed allocating struct rtentry.\n");
  	return;		/* NOTREACHED */
      }
      memset(this, 0, sizeof(struct rtentry));
  
      len = numvifs * sizeof(u_int32);
      this->rt_dominants = (u_int32 *)malloc(len);
      if (!this->rt_dominants) {
  	logit(LOG_ERR, errno, "route.c:create_route() - Failed allocating struct rtentry.\n");
  	free(this);
  	return;		/* NOTREACHED */
      }
      memset(this->rt_dominants, 0, len);
  
      this->rt_origin     = origin;
      this->rt_originmask = mask;
      if      (((char *)&mask)[3] != 0) this->rt_originwidth = 4;
      else if (((char *)&mask)[2] != 0) this->rt_originwidth = 3;
      else if (((char *)&mask)[1] != 0) this->rt_originwidth = 2;
      else                              this->rt_originwidth = 1;
      this->rt_flags = 0;
      this->rt_groups = NULL;
  
      VIFM_CLRALL(this->rt_children);
      NBRM_CLRALL(this->rt_subordinates);
      NBRM_CLRALL(this->rt_subordadv);
  
      /* Link in 'this', where rtp points */
      if (rtp) {
  	this->rt_prev = rtp;
  	this->rt_next = rtp->rt_next;
  	if (this->rt_next)
  	    (this->rt_next)->rt_prev = this;
  	else
  	    rt_end = this;
  	rtp->rt_next = this;
      } else {
  	if (routing_table) {
  	    /* Change existing head to this */
  	    this->rt_next = routing_table;
  	    routing_table->rt_prev = this;
  	}
  	else {
  	    /* this is the first route entry that exists */
  	    rt_end = this;
  	}
  	routing_table = this;
      }
  
      rtp = this;
      ++nroutes;
  }
  
  
  /*
   * Discard the routing table entry following the one to which 'this' points.
   *         [.|prev|.]--->[.|this|.]<---[.|next|.]
   */
  static void discard_route(struct rtentry *this)
  {
      struct rtentry *prev, *next;
  
      if (!this)
  	return;
  
      /* Find previous and next link */
      prev = this->rt_prev;
      next = this->rt_next;
  
      /* Unlink 'this' */
      if (prev)
  	prev->rt_next = next;	/* Handles case when 'this' is last link. */
      else
  	routing_table = next;	/* 'this' is first link. */
      if (next)
  	next->rt_prev = prev;
  
      /* Update the books */
      uvifs[this->rt_parent].uv_nroutes--;
      /*???nbr???.al_nroutes--;*/
      --nroutes;
  
      /* Update meta pointers */
      if (rtp == this)
  	rtp = next;
      if (rt_end == this)
  	rt_end = next;
  
      free(this->rt_dominants);
      free(this);
  }
  
  
  /*
   * Process a route report for a single origin, creating or updating the
   * corresponding routing table entry if necessary.  'src' is either the
   * address of a neighboring router from which the report arrived, or zero
   * to indicate a change of status of one of our own interfaces.
   */
  void update_route(u_int32 origin, u_int32 mask, u_int metric, u_int32 src, vifi_t vifi, struct listaddr *n)
  {
      register struct rtentry *r;
      u_int adj_metric;
  
      /*
       * Compute an adjusted metric, taking into account the cost of the
       * subnet or tunnel over which the report arrived, and normalizing
       * all unreachable/poisoned metrics into a single value.
       */
      if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
  	logit(LOG_WARNING, 0, "%s reports out-of-range metric %u for origin %s",
  	    inet_fmt(src, s1, sizeof(s1)), metric, inet_fmts(origin, mask, s2, sizeof(s2)));
  	return;
      }
      adj_metric = metric + uvifs[vifi].uv_metric;
      if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;
  
      /*
       * Look up the reported origin in the routing table.
       */
      if (!find_route(origin, mask)) {
  	/*
  	 * Not found.
  	 * Don't create a new entry if the report says it's unreachable,
  	 * or if the reported origin and mask are invalid.
  	 */
  	if (adj_metric == UNREACHABLE) {
  	    return;
  	}
  	if (src != 0 && !inet_valid_subnet(origin, mask)) {
  	    logit(LOG_WARNING, 0, "%s reports an invalid origin (%s) and/or mask (%08x)",
  		  inet_fmt(src, s1, sizeof(s1)), inet_fmt(origin, s2, sizeof(s2)), ntohl(mask));
  	    return;
  	}
  
  	IF_DEBUG(DEBUG_RTDETAIL) {
  	    logit(LOG_DEBUG, 0, "%s advertises new route %s",
  		  inet_fmt(src, s1, sizeof(s1)), inet_fmts(origin, mask, s2, sizeof(s2)));
  	}
  
  	/*
  	 * OK, create the new routing entry.  'rtp' will be left pointing
  	 * to the new entry.
  	 */
  	create_route(origin, mask);
  	uvifs[vifi].uv_nroutes++;
  	/*n->al_nroutes++;*/
  
  	rtp->rt_metric = UNREACHABLE;	/* temporary; updated below */
      }
  
      /*
       * We now have a routing entry for the reported origin.  Update it?
       */
      r = rtp;
      if (r->rt_metric == UNREACHABLE) {
  	/*
  	 * The routing entry is for a formerly-unreachable or new origin.
  	 * If the report claims reachability, update the entry to use
  	 * the reported route.
  	 */
  	if (adj_metric == UNREACHABLE)
  	    return;
  
  	IF_DEBUG(DEBUG_RTDETAIL) {
  	    logit(LOG_DEBUG, 0, "%s advertises %s with adj_metric %d (ours was %d)",
  		  inet_fmt(src, s1, sizeof(s1)), inet_fmts(origin, mask, s2, sizeof(s2)),
  		  adj_metric, r->rt_metric);
  	}
  
  	/*
  	 * Now "steal away" any sources that belong under this route
  	 * by deleting any cache entries they might have created
  	 * and allowing the kernel to re-request them.
  	 *
  	 * If we haven't performed final initialization yet and are
  	 * just collecting the routing table, we can't have any
  	 * sources so we don't perform this step.
  	 */
  	if (did_final_init)
  	    steal_sources(rtp);
  
  	r->rt_parent   = vifi;
  	r->rt_gateway  = src;
  	init_children_and_leaves(r, vifi, 1);
  
  	r->rt_timer    = 0;
  	r->rt_metric   = adj_metric;
  	r->rt_flags   |= RTF_CHANGED;
  	routes_changed = TRUE;
  	update_table_entry(r, r->rt_gateway);
      } else if (src == r->rt_gateway) {
  	/*
  	 * The report has come either from the interface directly-connected
  	 * to the origin subnet (src and r->rt_gateway both equal zero) or
  	 * from the gateway we have chosen as the best first-hop gateway back
  	 * towards the origin (src and r->rt_gateway not equal zero).  Reset
  	 * the route timer and, if the reported metric has changed, update
  	 * our entry accordingly.
  	 */
  	r->rt_timer = 0;
  
  	IF_DEBUG(DEBUG_RTDETAIL) {
  	    logit(LOG_DEBUG, 0, "%s (current parent) advertises %s with adj_metric %d (ours was %d)",
  		  inet_fmt(src, s1, sizeof(s1)), inet_fmts(origin, mask, s2, sizeof(s2)),
  		  adj_metric, r->rt_metric);
  	}
  
  	if (adj_metric == r->rt_metric)
  	    return;
  
  	if (adj_metric == UNREACHABLE) {
  	    del_table_entry(r, 0, DEL_ALL_ROUTES);
  	    r->rt_timer = ROUTE_EXPIRE_TIME;
  	}
  	r->rt_metric   = adj_metric;
  	r->rt_flags   |= RTF_CHANGED;
  	routes_changed = TRUE;
      } else if (src == 0 ||
  	       (r->rt_gateway != 0 &&
  		(adj_metric < r->rt_metric ||
  		 (adj_metric == r->rt_metric &&
  		  (ntohl(src) < ntohl(r->rt_gateway) ||
  		   r->rt_timer >= ROUTE_SWITCH_TIME))))) {
  	/*
  	 * The report is for an origin we consider reachable; the report
  	 * comes either from one of our own interfaces or from a gateway
  	 * other than the one we have chosen as the best first-hop gateway
  	 * back towards the origin.  If the source of the update is one of
  	 * our own interfaces, or if the origin is not a directly-connected
  	 * subnet and the reported metric for that origin is better than
  	 * what our routing entry says, update the entry to use the new
  	 * gateway and metric.  We also switch gateways if the reported
  	 * metric is the same as the one in the route entry and the gateway
  	 * associated with the route entry has not been heard from recently,
  	 * or if the metric is the same but the reporting gateway has a lower
  	 * IP address than the gateway associated with the route entry.
  	 * Did you get all that?
  	 */
  	u_int32 old_gateway;
  	vifi_t old_parent;
  
  	old_gateway = r->rt_gateway;
  	old_parent = r->rt_parent;
  	r->rt_gateway = src;
  	r->rt_parent = vifi;
  
  	IF_DEBUG(DEBUG_RTDETAIL) {
  	    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)",
  		  inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  		  adj_metric, inet_fmt(old_gateway, s3, sizeof(s3)), old_parent, r->rt_metric);
  	}
  
  	if (old_parent != vifi) {
  	    init_children_and_leaves(r, vifi, 0);
  	    uvifs[old_parent].uv_nroutes--;
  	    uvifs[vifi].uv_nroutes++;
  	}
  	if (old_gateway != src) {
  	    update_table_entry(r, old_gateway);
  	    /*???old_gateway???->al_nroutes--;*/
  	    /*n->al_nroutes++;*/
  	}
  	r->rt_timer    = 0;
  	r->rt_metric   = adj_metric;
  	r->rt_flags   |= RTF_CHANGED;
  	routes_changed = TRUE;
      } else if (vifi != r->rt_parent) {
  	/*
  	 * The report came from a vif other than the route's parent vif.
  	 * Update the children info, if necessary.
  	 */
  	if (AVOID_TRANSIT(vifi, r)) {
  	    /*
  	     * The route's parent is a vif from which we're not supposed
  	     * to transit onto this vif.  Simply ignore the update.
  	     */
  	    IF_DEBUG(DEBUG_RTDETAIL) {
  		logit(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored due to NOTRANSIT)",
  		      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)), metric);
  	    }
  	} else if (VIFM_ISSET(vifi, r->rt_children)) {
  	    /*
  	     * Vif is a child vif for this route.
  	     */
  	    if (metric  < r->rt_metric ||
  		(metric == r->rt_metric &&
  		 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
  		/*
  		 * Neighbor has lower metric to origin (or has same metric
  		 * and lower IP address) -- it becomes the dominant router,
  		 * and vif is no longer a child for me.
  		 */
  		VIFM_CLR(vifi, r->rt_children);
  		r->rt_dominants[vifi] = src;
  		/* XXX
  		 * We don't necessarily want to forget about subordinateness
  		 * so that we can become the dominant quickly if the current
  		 * dominant fails.
  		 */
  		NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
  		update_table_entry(r, r->rt_gateway);
  		IF_DEBUG(DEBUG_RTDETAIL) {
  		    logit(LOG_DEBUG, 0, "%s on vif %d becomes dominant for %s with metric %d",
  			  inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  			  metric);
  		}
  	    } else if (metric > UNREACHABLE) {	/* "poisoned reverse" */
  		/*
  		 * Neighbor considers this vif to be on path to route's
  		 * origin; record this neighbor as subordinate
  		 */
  		if (!NBRM_ISSET(n->al_index, r->rt_subordinates)) {
  		    IF_DEBUG(DEBUG_RTDETAIL) {
  			logit(LOG_DEBUG, 0, "%s on vif %d becomes subordinate for %s with poison-reverse metric %d",
  			      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  			      metric - UNREACHABLE);
  		    }
  		    NBRM_SET(n->al_index, r->rt_subordinates);
  		    update_table_entry(r, r->rt_gateway);
  		} else {
  		    IF_DEBUG(DEBUG_RTDETAIL) {
  			logit(LOG_DEBUG, 0, "%s on vif %d confirms subordinateness for %s with poison-reverse metric %d",
  			      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  			      metric - UNREACHABLE);
  		    }
  		}
  		NBRM_SET(n->al_index, r->rt_subordadv);
  	    } else if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
  		/*
  		 * Current subordinate no longer considers this vif to be on
  		 * path to route's origin; it is no longer a subordinate
  		 * router.
  		 */
  		IF_DEBUG(DEBUG_RTDETAIL) {
  		    logit(LOG_DEBUG, 0, "%s on vif %d is no longer a subordinate for %s with metric %d",
  			  inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  			  metric);
  		}
  		NBRM_CLR(n->al_index, r->rt_subordinates);
  		update_table_entry(r, r->rt_gateway);
  	    }
  	} else if (src == r->rt_dominants[vifi] &&
  		   (metric  > r->rt_metric ||
  		    (metric == r->rt_metric &&
  		     ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
  	    /*
  	     * Current dominant no longer has a lower metric to origin
  	     * (or same metric and lower IP address); we adopt the vif
  	     * as our own child.
  	     */
  	    IF_DEBUG(DEBUG_RTDETAIL) {
  		logit(LOG_DEBUG, 0, "%s (current dominant) on vif %d is no longer dominant for %s with metric %d",
  		      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  		      metric);
  	    }
  
  	    VIFM_SET(vifi, r->rt_children);
  	    r->rt_dominants[vifi] = 0;
  
  	    if (uvifs[vifi].uv_flags & VIFF_NOFLOOD)
  		NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
  	    else
  		NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
  
  	    if (metric > UNREACHABLE) {
  		NBRM_SET(n->al_index, r->rt_subordinates);
  		NBRM_SET(n->al_index, r->rt_subordadv);
  	    }
  	    update_table_entry(r, r->rt_gateway);
  	} else {
  	    IF_DEBUG(DEBUG_RTDETAIL) {
  		logit(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored)",
  		      inet_fmt(src, s1, sizeof(s1)), vifi, inet_fmts(origin, mask, s2, sizeof(s2)),
  		      metric);
  	    }
  	}
      }
  }
  
  
  /*
   * On every timer interrupt, advance the timer in each routing entry.
   */
  void age_routes(void)
  {
      struct rtentry *r, *next;
      extern u_long virtual_time;		/* from main.c */
  
      r = routing_table;
      while (r != NULL) {
  	next = r->rt_next;
  
  	if ((r->rt_timer += TIMER_INTERVAL) >= ROUTE_DISCARD_TIME) {
  	    /*
  	     * Time to garbage-collect the route entry.
  	     */
  	    del_table_entry(r, 0, DEL_ALL_ROUTES);
  	    discard_route(r);
  	}
  	else if (r->rt_timer >= ROUTE_EXPIRE_TIME &&
  		 r->rt_metric != UNREACHABLE) {
  	    /*
  	     * Time to expire the route entry.  If the gateway is zero,
  	     * i.e., it is a route to a directly-connected subnet, just
  	     * set the timer back to zero; such routes expire only when
  	     * the interface to the subnet goes down.
  	     */
  	    if (r->rt_gateway == 0) {
  		r->rt_timer = 0;
  	    }
  	    else {
  		del_table_entry(r, 0, DEL_ALL_ROUTES);
  		r->rt_metric   = UNREACHABLE;
  		r->rt_flags   |= RTF_CHANGED;
  		routes_changed = TRUE;
  	    }
  	}
  	else if (virtual_time % (ROUTE_REPORT_INTERVAL * 2) == 0) {
  	    /*
  	     * Time out subordinateness that hasn't been reported in
  	     * the last 2 intervals.
  	     */
  	    if (!NBRM_SAME(r->rt_subordinates, r->rt_subordadv)) {
  		IF_DEBUG(DEBUG_ROUTE) {
  		    logit(LOG_DEBUG, 0, "rt %s sub 0x%08x%08x subadv 0x%08x%08x metric %d",
  			  RT_FMT(r, s1), r->rt_subordinates.hi, r->rt_subordinates.lo,
  			  r->rt_subordadv.hi, r->rt_subordadv.lo, r->rt_metric);
  		}
  		NBRM_MASK(r->rt_subordinates, r->rt_subordadv);
  		update_table_entry(r, r->rt_gateway);
  	    }
  	    NBRM_CLRALL(r->rt_subordadv);
  	}
  
  	r = next;
      }
  }
  
  
  /*
   * Mark all routes as unreachable.  This function is called only from
   * hup() in preparation for informing all neighbors that we are going
   * off the air.  For consistency, we ought also to delete all reachable
   * route entries from the kernel, but since we are about to exit we rely
   * on the kernel to do its own cleanup -- no point in making all those
   * expensive kernel calls now.
   */
  void expire_all_routes(void)
  {
      struct rtentry *r;
  
      for (r = routing_table; r != NULL; r = r->rt_next) {
  	r->rt_metric   = UNREACHABLE;
  	r->rt_flags   |= RTF_CHANGED;
  	routes_changed = TRUE;
      }
  }
  
  
  /*
   * Delete all the routes in the routing table.
   */
  void free_all_routes(void)
  {
      struct rtentry *r, *next;
  
      r = routing_table;
      while (r != NULL) {
  	next = r->rt_next;
  	discard_route(r);
  	r = next;
      }
  }
  
  
  /*
   * Process an incoming neighbor probe message.
   */
  void accept_probe(u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level)
  {
      vifi_t vifi;
      static struct listaddr *unknowns = NULL;
  
      if ((vifi = find_vif(src, dst)) == NO_VIF) {
  	struct listaddr *a, **prev;
  	struct listaddr *match = NULL;
  	time_t now = time(0);
  
  	for (prev = &unknowns, a = *prev; a; a = *prev) {
  	    if (a->al_addr == src)
  		match = a;
  	    if (a->al_ctime + 2 * a->al_timer < (u_long)now) {
  		/* We haven't heard from it in a long time */
  		*prev = a->al_next;
  		free(a);
  	    } else {
  		prev = &a->al_next;
  	    }
  	}
  	if (match == NULL) {
  	    match = *prev = (struct listaddr *)malloc(sizeof(struct listaddr));
  	    if (match == NULL) {
  		logit(LOG_ERR, 0, "Malloc failed in route.c:accept_probe()\n");
  		return;		/* NOTREACHED */
  	    }
  
  	    match->al_next = NULL;
  	    match->al_addr = src;
  	    match->al_timer = OLD_NEIGHBOR_EXPIRE_TIME;
  	    match->al_ctime = now - match->al_timer;
  	}
  
  	if (match->al_ctime + match->al_timer <= (u_long)now) {
  	    logit(LOG_WARNING, 0, "Ignoring probe from non-neighbor %s, check for misconfigured tunnel or routing on %s",
  		  inet_fmt(src, s1, sizeof(s1)), s1);
  	    match->al_timer *= 2;
  	} else {
  	    IF_DEBUG(DEBUG_PEER) {
  		logit(LOG_DEBUG, 0, "Ignoring probe from non-neighbor %s (%d seconds until next warning)",
  		      inet_fmt(src, s1, sizeof(s1)), match->al_ctime + match->al_timer - now);
  	    }
  	}
  
  	return;
      }
  
      update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
  }
  
  static int compare_rts(const void *rt1, const void *rt2)
  {
      struct newrt *r1 = (struct newrt *)rt1;
      struct newrt *r2 = (struct newrt *)rt2;
      u_int32 m1 = ntohl(r1->mask);
      u_int32 m2 = ntohl(r2->mask);
      u_int32 o1, o2;
  
      if (m1 > m2)
  	return -1;
      if (m1 < m2)
  	return 1;
  
      /* masks are equal */
      o1 = ntohl(r1->origin);
      o2 = ntohl(r2->origin);
      if (o1 > o2)
  	return -1;
      if (o1 < o2)
  	return 1;
  
      return 0;
  }
  
  void blaster_alloc(vifi_t vifi)
  {
      struct uvif *v;
  
      v = &uvifs[vifi];
      if (v->uv_blasterbuf)
  	free(v->uv_blasterbuf);
  
      v->uv_blasterlen = 64 * 1024;
      v->uv_blasterbuf = malloc(v->uv_blasterlen);
      v->uv_blastercur = v->uv_blasterend = v->uv_blasterbuf;
      if (v->uv_blastertimer)
  	timer_clearTimer(v->uv_blastertimer);
      v->uv_blastertimer = 0;
  }
  
  /*
   * Queue a route report from a route-blaster.
   * If the timer isn't running to process these reports,
   * start it.
   */
  static void queue_blaster_report(vifi_t vifi, u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level)
  {
      struct blaster_hdr *bh;
      struct uvif *v;
      int bblen = sizeof(*bh) + ((datalen + 3) & ~3);
  
      v = &uvifs[vifi];
      if (v->uv_blasterend - v->uv_blasterbuf + bblen > v->uv_blasterlen) {
  	int end = v->uv_blasterend - v->uv_blasterbuf;
  	int cur = v->uv_blastercur - v->uv_blasterbuf;
  
  	v->uv_blasterlen *= 2;
  	IF_DEBUG(DEBUG_IF) {
  	    logit(LOG_DEBUG, 0, "Increasing blasterbuf to %d bytes", v->uv_blasterlen);
  	}
  
  	v->uv_blasterbuf = realloc(v->uv_blasterbuf, v->uv_blasterlen);
  	if (v->uv_blasterbuf == NULL) {
  	    logit(LOG_WARNING, ENOMEM, "Turning off blaster on vif %d", vifi);
  	    v->uv_blasterlen = 0;
  	    v->uv_blasterend = v->uv_blastercur = NULL;
  	    v->uv_flags &= ~VIFF_BLASTER;
  	    return;
  	}
  	v->uv_blasterend = v->uv_blasterbuf + end;
  	v->uv_blastercur = v->uv_blasterbuf + cur;
      }
      bh = (struct blaster_hdr *)v->uv_blasterend;
      bh->bh_src = src;
      bh->bh_dst = dst;
      bh->bh_level = level;
      bh->bh_datalen = datalen;
      memmove((char *)(bh + 1), p, datalen);
      v->uv_blasterend += bblen;
  
      if (v->uv_blastertimer == 0) {
  	int *i;
  
  	i = (int *)malloc(sizeof(int *));
  	if (i == NULL) {
  	    logit(LOG_ERR, 0, "Malloc failed in route.c:queue_blaster_report()\n");
  	    return;		/* NOTREACHED */
  	}
  
  	*i = vifi;
  	v->uv_blastertimer = timer_setTimer(5, process_blaster_report, i);
      }
  }
  
  /*
   * Periodic process; process up to 5 of the routes in the route-blaster
   * queue.  If there are more routes remaining, reschedule myself to run
   * in 1 second.
   */
  static void process_blaster_report(void *vifip)
  {
      vifi_t vifi = *(int *)vifip;
      struct uvif *v;
      struct blaster_hdr *bh;
      int i;
  
      IF_DEBUG(DEBUG_ROUTE) {
  	logit(LOG_DEBUG, 0, "Processing vif %d blasted routes", vifi);
      }
  
      v = &uvifs[vifi];
      for (i = 0; i < 5; i++) {
  	if (v->uv_blastercur >= v->uv_blasterend)
  		break;
  
  	bh = (struct blaster_hdr *)v->uv_blastercur;
  	v->uv_blastercur += sizeof(*bh) + ((bh->bh_datalen + 3) & ~3);
  
  	accept_report(bh->bh_src, bh->bh_dst, (char *)(bh + 1), -bh->bh_datalen, bh->bh_level);
      }
  
      if (v->uv_blastercur >= v->uv_blasterend) {
  	v->uv_blastercur = v->uv_blasterbuf;
  	v->uv_blasterend = v->uv_blasterbuf;
  	v->uv_blastertimer = 0;
  	free(vifip);
  
  	IF_DEBUG(DEBUG_ROUTE) {
  	    logit(LOG_DEBUG, 0, "Finish processing vif %d blaster", vifi);
  	}
      } else {
  	IF_DEBUG(DEBUG_ROUTE) {
  	    logit(LOG_DEBUG, 0, "More blasted routes to come on vif %d", vifi);
  	}
  	v->uv_blastertimer = timer_setTimer(1, process_blaster_report, vifip);
      }
  }
  
  /*
   * Process an incoming route report message.
   * If the report arrived on a vif marked as a "blaster", then just
   * queue it and return; queue_blaster_report() will schedule it for
   * processing later.  If datalen is negative, then this is actually
   * a queued report so actually process it instead of queueing it.
   */
  void accept_report(u_int32 src, u_int32 dst, char *p, size_t datalen, u_int32 level)
  {
      vifi_t vifi;
      size_t width, i, nrt = 0;
      int metric;
      u_int32 mask;
      u_int32 origin;
      static struct newrt rt[MAX_NUM_RT]; /* Use heap instead of stack */
      struct listaddr *nbr;
  
      /*
       * Emulate a stack variable.  We use the heap insted of the stack
       * to prevent stack overflow on systems that cannot do stack realloc
       * at runtime, e.g., non-MMU Linux systems.
       */
      memset(rt, 0, MAX_NUM_RT * sizeof(rt[0]));
  
      if ((vifi = find_vif(src, dst)) == NO_VIF) {
  	logit(LOG_INFO, 0, "Ignoring route report from non-neighbor %s",
  	      inet_fmt(src, s1, sizeof(s1)));
  	return;
      }
  
      if (uvifs[vifi].uv_flags & VIFF_BLASTER) {
  	if (datalen > 0) {
  	    queue_blaster_report(vifi, src, dst, p, datalen, level);
  	    return;
  	} else {
  	    datalen = -datalen;
  	}
      }
  
      nbr = update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level);
      if (!nbr)
  	return;
  
      if (datalen > 2 * 4096) {
  	logit(LOG_INFO, 0, "Ignoring oversized (%d bytes) route report from %s",
  	      datalen, inet_fmt(src, s1, sizeof(s1)));
  	return;
      }
  
      while (datalen > 0  && nrt < MAX_NUM_RT) { /* Loop through per-mask lists. */
  	if (datalen < 3) {
  	    logit(LOG_WARNING, 0, "Received truncated route report from %s", 
  		  inet_fmt(src, s1, sizeof(s1)));
  	    return;
  	}
  
  	((u_char *)&mask)[0] = 0xff;            width = 1;
  	if ((((u_char *)&mask)[1] = *p++) != 0) width = 2;
  	if ((((u_char *)&mask)[2] = *p++) != 0) width = 3;
  	if ((((u_char *)&mask)[3] = *p++) != 0) width = 4;
  	if (!inet_valid_mask(ntohl(mask))) {
  	    logit(LOG_WARNING, 0, "%s reports bogus netmask 0x%08x (%s)",
  		  inet_fmt(src, s1, sizeof(s1)), ntohl(mask), inet_fmt(mask, s2, sizeof(s2)));
  	    return;
  	}
  	datalen -= 3;
  
  	do {			/* Loop through (origin, metric) pairs */
  	    if (datalen < width + 1) {
  		logit(LOG_WARNING, 0, "Received truncated route report from %s", 
  		      inet_fmt(src, s1, sizeof(s1)));
  		return;
  	    }
  	    origin = 0;
  	    for (i = 0; i < width; ++i)
  		((char *)&origin)[i] = *p++;
  	    metric = *p++;
  	    datalen -= width + 1;
  	    rt[nrt].mask   = mask;
  	    rt[nrt].origin = origin;
  	    rt[nrt].metric = (metric & 0x7f);
  	    ++nrt;
  	} while (!(metric & 0x80) && nrt < MAX_NUM_RT);
      }
  
      qsort((char *)rt, nrt, sizeof(rt[0]), compare_rts);
      start_route_updates();
  
      /*
       * If the last entry is default, change mask from 0xff000000 to 0
       */
      if (nrt > 0 && rt[nrt - 1].origin == 0)
  	rt[nrt - 1].mask = 0;
  
      IF_DEBUG(DEBUG_ROUTE) {
  	logit(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt,
  	      inet_fmt(src, s1, sizeof(s1)), inet_fmt(dst, s2, sizeof(s2)));
      }
  
      for (i = 0; i < nrt; ++i) {
  	if (i > 0 && rt[i].origin == rt[i - 1].origin && rt[i].mask == rt[i - 1].mask) {
  	    logit(LOG_WARNING, 0, "%s reports duplicate route for %s",
                    inet_fmt(src, s1, sizeof(s1)), inet_fmts(rt[i].origin, rt[i].mask, s2, sizeof(s2)));
  	    continue;
  	}
  	/* Only filter non-poisoned updates. */
  	if (uvifs[vifi].uv_filter && rt[i].metric < UNREACHABLE) {
  	    struct vf_element *vfe;
  	    int match = 0;
  
  	    for (vfe = uvifs[vifi].uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
  		if (vfe->vfe_flags & VFEF_EXACT) {
  		    if ((vfe->vfe_addr == rt[i].origin) && (vfe->vfe_mask == rt[i].mask)) {
  			match = 1;
  			break;
  		    }
  		} else {
  		    if ((rt[i].origin & vfe->vfe_mask) == vfe->vfe_addr) {
  			match = 1;
  			break;
  		    }
  		}
  	    }
  	    if ((uvifs[vifi].uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
  		(uvifs[vifi].uv_filter->vf_type == VFT_DENY && match == 1)) {
  		IF_DEBUG(DEBUG_ROUTE) {
  		    logit(LOG_DEBUG, 0, "%s skipped on vif %d because it %s %s",
  			  inet_fmts(rt[i].origin, rt[i].mask, s1, sizeof(s1)),
  			  vifi, match ? "matches" : "doesn't match",
  			  match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2, sizeof(s2))
  			  : "the filter");
  		}
  #if 0
  		rt[i].metric += vfe->vfe_addmetric;
  		if (rt[i].metric > UNREACHABLE)
  #endif
  		    rt[i].metric = UNREACHABLE;
  	    }
  	}
  	update_route(rt[i].origin, rt[i].mask, rt[i].metric, src, vifi, nbr);
      }
  
      if (routes_changed && !delay_change_reports)
  	report_to_all_neighbors(CHANGED_ROUTES);
  }
  
  
  /*
   * Send a route report message to destination 'dst', via virtual interface
   * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
   */
  void report(int which_routes, vifi_t vifi, u_int32 dst)
  {
      struct rtentry *this;
      int i;
  
      this = rt_end;
      while (this && this != routing_table) {
  	i = report_chunk(which_routes, this, vifi, dst);
  	while (i-- > 0)
  	    this = this->rt_prev;
      }
  }
  
  
  /*
   * Send a route report message to all neighboring routers.
   * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
   */
  void report_to_all_neighbors(int which_routes)
  {
      vifi_t vifi;
      struct uvif *v;
      struct rtentry *r;
      int routes_changed_before;
  
      /*
       * Remember the state of the global routes_changed flag before
       * generating the reports, and clear the flag.
       */
      routes_changed_before = routes_changed;
      routes_changed = FALSE;
  
  
      for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
  	if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
  	    report(which_routes, vifi, v->uv_dst_addr);
  	}
      }
  
      /*
       * If there were changed routes before we sent the reports AND
       * if no new changes occurred while sending the reports, clear
       * the change flags in the individual route entries.  If changes
       * did occur while sending the reports, new reports will be
       * generated at the next timer interrupt.
       */
      if (routes_changed_before && !routes_changed) {
  	for (r = routing_table; r != NULL; r = r->rt_next) {
  	    r->rt_flags &= ~RTF_CHANGED;
  	}
      }
  
      /*
       * Set a flag to inhibit further reports of changed routes until the
       * next timer interrupt.  This is to alleviate update storms.
       */
      delay_change_reports = TRUE;
  }
  
  /*
   * Send a route report message to destination 'dst', via virtual interface
   * 'vifi'.  'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
   */
  static int report_chunk(int which_routes, struct rtentry *start_rt, vifi_t vifi, u_int32 UNUSED dst)
  {
      struct rtentry *r;
      char *p;
      int i;
      size_t nrt = 0;
      struct uvif *v = &uvifs[vifi];
      int datalen = 0;
      int width = 0;
      u_int32 mask = 0;
      int admetric = v->uv_admetric;
      int metric;
  
      p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
  
      for (r = start_rt; r != routing_table; r = r->rt_prev) {
  	if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED)) {
  	    nrt++;
  	    continue;
  	}
  
  	/*
  	 * Do not poison-reverse a route for a directly-connected
  	 * subnetwork on that subnetwork.  This can cause loops when
  	 * some router on the subnetwork is misconfigured.
  	 */
  	if (r->rt_gateway == 0 && r->rt_parent == vifi) {
  	    nrt++;
  	    continue;
  	}
  
  	if (v->uv_filter && v->uv_filter->vf_flags & VFF_BIDIR) {
  	    struct vf_element *vfe;
  	    int match = 0;
  
  	    for (vfe = v->uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
  		if (vfe->vfe_flags & VFEF_EXACT) {
  		    if ((vfe->vfe_addr == r->rt_origin) &&
  			(vfe->vfe_mask == r->rt_originmask)) {
  			    match = 1;
  			    break;
  		    }
  		} else {
  		    if ((r->rt_origin & vfe->vfe_mask) == vfe->vfe_addr) {
  			    match = 1;
  			    break;
  		    }
  		}
  	    }
  	    if ((v->uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
  		(v->uv_filter->vf_type == VFT_DENY && match == 1)) {
  		IF_DEBUG(DEBUG_ROUTE) {
  		    logit(LOG_DEBUG, 0, "%s not reported on vif %d because it %s %s",
  			  RT_FMT(r, s1), vifi, match ? "matches" : "doesn't match",
  			  match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2, sizeof(s2))
  			  : "the filter");
  		}
  		nrt++;
  		continue;
  	    }
  	}
  
  	/*
  	 * If there is no room for this route in the current message,
  	 * send it & return how many routes we sent.
  	 */
  	if (datalen + ((r->rt_originmask == mask)
  		       ? (width + 1)
  		       : (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
  	    *(p-1) |= 0x80;
  	    send_on_vif(v, 0, DVMRP_REPORT, datalen);
  
  	    return nrt;
  	}
  
  	if (r->rt_originmask != mask || datalen == 0) {
  	    mask  = r->rt_originmask;
  	    width = r->rt_originwidth;
  	    if (datalen != 0) *(p-1) |= 0x80;
  	    *p++ = ((char *)&mask)[1];
  	    *p++ = ((char *)&mask)[2];
  	    *p++ = ((char *)&mask)[3];
  	    datalen += 3;
  	}
  	for (i = 0; i < width; ++i)
  	    *p++ = ((char *)&(r->rt_origin))[i];
  
  	metric = r->rt_metric + admetric;
  	if (metric > UNREACHABLE)
  	    metric = UNREACHABLE;
  
  	if (r->rt_parent != vifi && AVOID_TRANSIT(vifi, r))
  	    metric = UNREACHABLE;
  
  	*p++ = (r->rt_parent == vifi && metric != UNREACHABLE)
  	    ? (char)(metric + UNREACHABLE) /* "poisoned reverse" */
  	    : (char)(metric);
  	++nrt;
  	datalen += width + 1;
      }
      if (datalen != 0) {
  	*(p-1) |= 0x80;
  	send_on_vif(v, 0, DVMRP_REPORT, datalen);
      }
  
      return nrt;
  }
  
  /*
   * send the next chunk of our routing table to all neighbors.
   * return the length of the smallest chunk we sent out.
   */
  int report_next_chunk(void)
  {
      vifi_t vifi;
      struct uvif *v;
      struct rtentry *sr;
      int i, n = 0, min = 20000;
      static int start_rt;
  
      if (nroutes <= 0)
  	return 0;
  
      /*
       * find this round's starting route.
       */
      for (sr = rt_end, i = start_rt; sr && --i >= 0; ) {
  	sr = sr->rt_prev;
  	if (sr == routing_table)
  	    sr = rt_end;
      }
  
      /*
       * send one chunk of routes starting at this round's start to
       * all our neighbors.
       */
      for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
  	if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
  	    n = report_chunk(ALL_ROUTES, sr, vifi, v->uv_dst_addr);
  	    if (n < min)
  		min = n;
  	}
      }
      if (min == 20000)
  	min = 0;	/* Neighborless router didn't send any routes */
  
      n = min;
      IF_DEBUG(DEBUG_ROUTE) {
  	logit(LOG_INFO, 0, "update %d starting at %d of %d",
  	      n, (nroutes - start_rt), nroutes);
      }
  
      start_rt = (start_rt + n) % nroutes;
  
      return n;
  }
  
  
  /*
   * Print the contents of the routing table on file 'fp'.
   */
  void dump_routes(FILE *fp)
  {
      struct rtentry *r;
      vifi_t i;
  
      fprintf(fp, "Multicast Routing Table (%u entr%s)\n", nroutes, nroutes == 1 ? "y" : "ies");
      fputs(" Origin-Subnet      From-Gateway    Metric Tmr Fl In-Vif  Out-Vifs\n", fp);
  
      for (r = routing_table; r; r = r->rt_next) {
  	fprintf(fp, " %-18s %-15s ",
  		inet_fmts(r->rt_origin, r->rt_originmask, s1, sizeof(s1)),
  		(r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway, s2, sizeof(s2)));
  
  	fprintf(fp, (r->rt_metric == UNREACHABLE) ? "  NR " : "%4u ",
  		r->rt_metric);
  
  	fprintf(fp, "  %3u %c%c %3u   ", r->rt_timer,
  		(r->rt_flags & RTF_CHANGED) ? 'C' : '.',
  		(r->rt_flags & RTF_HOLDDOWN) ? 'H' : '.',
  		r->rt_parent);
  
  	for (i = 0; i < numvifs; ++i) {
  	    struct listaddr *n;
  	    char l = '[';
  
  	    if (VIFM_ISSET(i, r->rt_children)) {
  		if ((uvifs[i].uv_flags & VIFF_TUNNEL) &&
  		    !NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
  			/* Don't print out parenthood of a leaf tunnel. */
  			continue;
  
  		fprintf(fp, " %u", i);
  		if (!NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
  		    fprintf(fp, "*");
  
  		for (n = uvifs[i].uv_neighbors; n; n = n->al_next) {
  		    if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
  			fprintf(fp, "%c%d", l, n->al_index);
  			l = ',';
  		    }
  		}
  
  		if (l == ',')
  		    fprintf(fp, "]");
  	    }
  	}
  	fprintf(fp, "\n");
      }
      fprintf(fp, "\n");
  }
  
  struct rtentry *determine_route(u_int32 src)
  {
      struct rtentry *rt;
  
      for (rt = routing_table; rt != NULL; rt = rt->rt_next) {
  	if (rt->rt_origin == (src & rt->rt_originmask) &&
  	    rt->rt_metric != UNREACHABLE) 
  	    break;
      }
  
      return rt;
  }
  
  /**
   * Local Variables:
   *  version-control: t
   *  indent-tabs-mode: t
   *  c-file-style: "ellemtel"
   *  c-basic-offset: 4
   * End:
   */
  