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.
6 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
7 * Leland Stanford Junior University.
10 * route.c,v 3.8.4.41 1998/01/15 00:08:34 fenner Exp
14 static const char rcsid[] =
15 "$FreeBSD: src/usr.sbin/mrouted/route.c,v 1.12 1999/08/28 01:17:08 peter Exp $";
21 * This define statement saves a lot of space later
23 #define RT_ADDR (struct rtentry *)&routing_table
28 int routes_changed; /* 1=>some routes have changed */
29 int delay_change_reports; /* 1=>postpone change reports */
33 * The routing table is shared with prune.c , so must not be static.
35 struct rtentry *routing_table; /* pointer to list of route entries */
40 static struct rtentry *rtp; /* pointer to a route entry */
41 static struct rtentry *rt_end; /* pointer to last route entry */
42 unsigned int nroutes; /* current number of route entries */
47 static int init_children_and_leaves __P((struct rtentry *r,
48 vifi_t parent, int first));
49 static int find_route __P((u_int32 origin, u_int32 mask));
50 static void create_route __P((u_int32 origin, u_int32 mask));
51 static void discard_route __P((struct rtentry *prev_r));
52 static int compare_rts __P((const void *rt1, const void *rt2));
53 static int report_chunk __P((int, struct rtentry *start_rt, vifi_t vifi,
55 static void queue_blaster_report __P((vifi_t, u_int32, u_int32, char *,
57 static void process_blaster_report __P((void *));
60 #include <sys/types.h>
64 * Return pointer to a specific route entry. This must be a separate
65 * function from find_route() which modifies rtp.
68 snmp_find_route(src, mask)
69 register u_int32 src, mask;
71 register struct rtentry *rt;
73 for (rt = routing_table; rt; rt = rt->rt_next) {
74 if (src == rt->rt_origin && mask == rt->rt_originmask)
81 * Find next route entry > specification
84 next_route(rtpp, src, mask)
85 struct rtentry **rtpp;
89 struct rtentry *rt, *rbest = NULL;
91 /* Among all entries > spec, find "lowest" one in order */
92 for (rt = routing_table; rt; rt=rt->rt_next) {
93 if ((ntohl(rt->rt_origin) > ntohl(src)
94 || (ntohl(rt->rt_origin) == ntohl(src)
95 && ntohl(rt->rt_originmask) > ntohl(mask)))
96 && (!rbest || (ntohl(rt->rt_origin) < ntohl(rbest->rt_origin))
97 || (ntohl(rt->rt_origin) == ntohl(rbest->rt_origin)
98 && ntohl(rt->rt_originmask) < ntohl(rbest->rt_originmask))))
106 * Given a routing table entry, and a vifi, find the next vifi/entry
109 next_route_child(rtpp, src, mask, vifi)
110 struct rtentry **rtpp;
113 vifi_t *vifi; /* vif at which to start looking */
115 /* Get (S,M) entry */
116 if (!((*rtpp) = snmp_find_route(src,mask)))
117 if (!next_route(rtpp, src, mask))
120 /* Continue until we get one with a valid next vif */
122 for (; (*rtpp)->rt_children && *vifi<numvifs; (*vifi)++)
123 if (VIFM_ISSET(*vifi, (*rtpp)->rt_children))
126 } while( next_route(rtpp, (*rtpp)->rt_origin, (*rtpp)->rt_originmask) );
133 * Initialize the routing table and associated variables.
138 routing_table = NULL;
141 routes_changed = FALSE;
142 delay_change_reports = FALSE;
147 * Initialize the children bits for route 'r', along with the
148 * associated dominant and subordinate data structures.
149 * If first is set, initialize dominants, otherwise keep old
150 * dominants on non-parent interfaces.
151 * XXX Does this need a return value?
154 init_children_and_leaves(r, parent, first)
155 register struct rtentry *r;
156 register vifi_t parent;
159 register vifi_t vifi;
160 register struct uvif *v;
161 vifbitmap_t old_children;
162 nbrbitmap_t old_subords;
164 VIFM_COPY(r->rt_children, old_children);
165 NBRM_COPY(r->rt_subordinates, old_subords);
167 VIFM_CLRALL(r->rt_children);
169 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
170 if (first || vifi == parent)
171 r->rt_dominants [vifi] = 0;
172 if (vifi == parent || uvifs[vifi].uv_flags & VIFF_NOFLOOD ||
173 AVOID_TRANSIT(vifi, r) || (!first && r->rt_dominants[vifi]))
174 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
176 NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
178 if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED)) &&
179 !(!first && r->rt_dominants[vifi])) {
180 VIFM_SET(vifi, r->rt_children);
184 return (!VIFM_SAME(r->rt_children, old_children) ||
185 !NBRM_SAME(r->rt_subordinates, old_subords));
190 * A new vif has come up -- update the children bitmaps in all route
191 * entries to take that into account.
194 add_vif_to_routes(vifi)
195 register vifi_t vifi;
197 register struct rtentry *r;
198 register struct uvif *v;
201 for (r = routing_table; r != NULL; r = r->rt_next) {
202 if (r->rt_metric != UNREACHABLE &&
203 !VIFM_ISSET(vifi, r->rt_children)) {
204 VIFM_SET(vifi, r->rt_children);
205 r->rt_dominants [vifi] = 0;
206 /*XXX isn't uv_nbrmap going to be empty?*/
207 NBRM_CLRMASK(r->rt_subordinates, v->uv_nbrmap);
208 update_table_entry(r, r->rt_gateway);
215 * A vif has gone down -- expire all routes that have that vif as parent,
216 * and update the children bitmaps in all other route entries to take into
217 * account the failed vif.
220 delete_vif_from_routes(vifi)
221 register vifi_t vifi;
223 register struct rtentry *r;
225 for (r = routing_table; r != NULL; r = r->rt_next) {
226 if (r->rt_metric != UNREACHABLE) {
227 if (vifi == r->rt_parent) {
228 del_table_entry(r, 0, DEL_ALL_ROUTES);
229 r->rt_timer = ROUTE_EXPIRE_TIME;
230 r->rt_metric = UNREACHABLE;
231 r->rt_flags |= RTF_CHANGED;
232 routes_changed = TRUE;
234 else if (VIFM_ISSET(vifi, r->rt_children)) {
235 VIFM_CLR(vifi, r->rt_children);
236 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
237 update_table_entry(r, r->rt_gateway);
240 r->rt_dominants[vifi] = 0;
248 * A new neighbor has come up. If we're flooding on the neighbor's
249 * vif, mark that neighbor as subordinate for all routes whose parent
253 add_neighbor_to_routes(vifi, index)
254 register vifi_t vifi;
257 register struct rtentry *r;
258 register struct uvif *v;
261 if (v->uv_flags & VIFF_NOFLOOD)
263 for (r = routing_table; r != NULL; r = r->rt_next) {
264 if (r->rt_metric != UNREACHABLE && r->rt_parent != vifi &&
265 !AVOID_TRANSIT(vifi, r)) {
266 NBRM_SET(index, r->rt_subordinates);
267 update_table_entry(r, r->rt_gateway);
274 * A neighbor has failed or become unreachable. If that neighbor was
275 * considered a dominant or subordinate router in any route entries,
276 * take appropriate action. Expire all routes this neighbor advertised
280 delete_neighbor_from_routes(addr, vifi, index)
281 register u_int32 addr;
282 register vifi_t vifi;
285 register struct rtentry *r;
286 register struct uvif *v;
289 for (r = routing_table; r != NULL; r = r->rt_next) {
290 if (r->rt_metric != UNREACHABLE) {
291 if (r->rt_parent == vifi && r->rt_gateway == addr) {
292 del_table_entry(r, 0, DEL_ALL_ROUTES);
293 r->rt_timer = ROUTE_EXPIRE_TIME;
294 r->rt_metric = UNREACHABLE;
295 r->rt_flags |= RTF_CHANGED;
296 routes_changed = TRUE;
297 } else if (r->rt_dominants[vifi] == addr) {
298 VIFM_SET(vifi, r->rt_children);
299 r->rt_dominants[vifi] = 0;
300 if ((uvifs[vifi].uv_flags & VIFF_NOFLOOD) ||
301 AVOID_TRANSIT(vifi, r))
302 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
304 NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
305 update_table_entry(r, r->rt_gateway);
306 } else if (NBRM_ISSET(index, r->rt_subordinates)) {
307 NBRM_CLR(index, r->rt_subordinates);
308 update_table_entry(r, r->rt_gateway);
316 * Prepare for a sequence of ordered route updates by initializing a pointer
317 * to the start of the routing table. The pointer is used to remember our
318 * position in the routing table in order to avoid searching from the
319 * beginning for each update; this relies on having the route reports in
320 * a single message be in the same order as the route entries in the routing
324 start_route_updates()
331 * Starting at the route entry following the one to which 'rtp' points,
332 * look for a route entry matching the specified origin and mask. If a
333 * match is found, return TRUE and leave 'rtp' pointing at the found entry.
334 * If no match is found, return FALSE and leave 'rtp' pointing to the route
335 * entry preceding the point at which the new origin should be inserted.
336 * This code is optimized for the normal case in which the first entry to
337 * be examined is the matching entry.
340 find_route(origin, mask)
341 register u_int32 origin, mask;
343 register struct rtentry *r;
347 if (origin == r->rt_origin && mask == r->rt_originmask) {
351 if (ntohl(mask) < ntohl(r->rt_originmask) ||
352 (mask == r->rt_originmask &&
353 ntohl(origin) < ntohl(r->rt_origin))) {
363 * Create a new routing table entry for the specified origin and link it into
364 * the routing table. The shared variable 'rtp' is assumed to point to the
365 * routing entry after which the new one should be inserted. It is left
366 * pointing to the new entry.
368 * Only the origin, originmask, originwidth and flags fields are initialized
369 * in the new route entry; the caller is responsible for filling in the the
373 create_route(origin, mask)
374 u_int32 origin, mask;
376 register struct rtentry *r;
378 if ((r = (struct rtentry *) malloc(sizeof(struct rtentry) +
379 (numvifs * sizeof(u_int32)))) == NULL) {
380 log(LOG_ERR, 0, "ran out of memory"); /* fatal */
382 r->rt_origin = origin;
383 r->rt_originmask = mask;
384 if (((char *)&mask)[3] != 0) r->rt_originwidth = 4;
385 else if (((char *)&mask)[2] != 0) r->rt_originwidth = 3;
386 else if (((char *)&mask)[1] != 0) r->rt_originwidth = 2;
387 else r->rt_originwidth = 1;
389 r->rt_dominants = (u_int32 *)(r + 1);
390 bzero(r->rt_dominants, numvifs * sizeof(u_int32));
392 VIFM_CLRALL(r->rt_children);
393 NBRM_CLRALL(r->rt_subordinates);
394 NBRM_CLRALL(r->rt_subordadv);
396 r->rt_next = rtp->rt_next;
399 if (r->rt_next != NULL)
400 (r->rt_next)->rt_prev = r;
409 * Discard the routing table entry following the one to which 'prev_r' points.
412 discard_route(prev_r)
413 register struct rtentry *prev_r;
415 register struct rtentry *r;
418 uvifs[r->rt_parent].uv_nroutes--;
419 /*???nbr???.al_nroutes--;*/
420 prev_r->rt_next = r->rt_next;
421 if (prev_r->rt_next != NULL)
422 (prev_r->rt_next)->rt_prev = prev_r;
431 * Process a route report for a single origin, creating or updating the
432 * corresponding routing table entry if necessary. 'src' is either the
433 * address of a neighboring router from which the report arrived, or zero
434 * to indicate a change of status of one of our own interfaces.
437 update_route(origin, mask, metric, src, vifi, n)
438 u_int32 origin, mask;
444 register struct rtentry *r;
448 * Compute an adjusted metric, taking into account the cost of the
449 * subnet or tunnel over which the report arrived, and normalizing
450 * all unreachable/poisoned metrics into a single value.
452 if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
454 "%s reports out-of-range metric %u for origin %s",
455 inet_fmt(src, s1), metric, inet_fmts(origin, mask, s2));
458 adj_metric = metric + uvifs[vifi].uv_metric;
459 if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;
462 * Look up the reported origin in the routing table.
464 if (!find_route(origin, mask)) {
467 * Don't create a new entry if the report says it's unreachable,
468 * or if the reported origin and mask are invalid.
470 if (adj_metric == UNREACHABLE) {
473 if (src != 0 && !inet_valid_subnet(origin, mask)) {
475 "%s reports an invalid origin (%s) and/or mask (%08x)",
476 inet_fmt(src, s1), inet_fmt(origin, s2), ntohl(mask));
480 IF_DEBUG(DEBUG_RTDETAIL)
481 log(LOG_DEBUG, 0, "%s advertises new route %s",
482 inet_fmt(src, s1), inet_fmts(origin, mask, s2));
485 * OK, create the new routing entry. 'rtp' will be left pointing
488 create_route(origin, mask);
489 uvifs[vifi].uv_nroutes++;
492 rtp->rt_metric = UNREACHABLE; /* temporary; updated below */
496 * We now have a routing entry for the reported origin. Update it?
499 if (r->rt_metric == UNREACHABLE) {
501 * The routing entry is for a formerly-unreachable or new origin.
502 * If the report claims reachability, update the entry to use
503 * the reported route.
505 if (adj_metric == UNREACHABLE)
508 IF_DEBUG(DEBUG_RTDETAIL)
509 log(LOG_DEBUG, 0, "%s advertises %s with adj_metric %d (ours was %d)",
510 inet_fmt(src, s1), inet_fmts(origin, mask, s2),
511 adj_metric, r->rt_metric);
514 * Now "steal away" any sources that belong under this route
515 * by deleting any cache entries they might have created
516 * and allowing the kernel to re-request them.
518 * If we haven't performed final initialization yet and are
519 * just collecting the routing table, we can't have any
520 * sources so we don't perform this step.
527 init_children_and_leaves(r, vifi, 1);
530 r->rt_metric = adj_metric;
531 r->rt_flags |= RTF_CHANGED;
532 routes_changed = TRUE;
533 update_table_entry(r, r->rt_gateway);
535 else if (src == r->rt_gateway) {
537 * The report has come either from the interface directly-connected
538 * to the origin subnet (src and r->rt_gateway both equal zero) or
539 * from the gateway we have chosen as the best first-hop gateway back
540 * towards the origin (src and r->rt_gateway not equal zero). Reset
541 * the route timer and, if the reported metric has changed, update
542 * our entry accordingly.
546 IF_DEBUG(DEBUG_RTDETAIL)
547 log(LOG_DEBUG, 0, "%s (current parent) advertises %s with adj_metric %d (ours was %d)",
548 inet_fmt(src, s1), inet_fmts(origin, mask, s2),
549 adj_metric, r->rt_metric);
551 if (adj_metric == r->rt_metric)
554 if (adj_metric == UNREACHABLE) {
555 del_table_entry(r, 0, DEL_ALL_ROUTES);
556 r->rt_timer = ROUTE_EXPIRE_TIME;
558 r->rt_metric = adj_metric;
559 r->rt_flags |= RTF_CHANGED;
560 routes_changed = TRUE;
563 (r->rt_gateway != 0 &&
564 (adj_metric < r->rt_metric ||
565 (adj_metric == r->rt_metric &&
566 (ntohl(src) < ntohl(r->rt_gateway) ||
567 r->rt_timer >= ROUTE_SWITCH_TIME))))) {
569 * The report is for an origin we consider reachable; the report
570 * comes either from one of our own interfaces or from a gateway
571 * other than the one we have chosen as the best first-hop gateway
572 * back towards the origin. If the source of the update is one of
573 * our own interfaces, or if the origin is not a directly-connected
574 * subnet and the reported metric for that origin is better than
575 * what our routing entry says, update the entry to use the new
576 * gateway and metric. We also switch gateways if the reported
577 * metric is the same as the one in the route entry and the gateway
578 * associated with the route entry has not been heard from recently,
579 * or if the metric is the same but the reporting gateway has a lower
580 * IP address than the gateway associated with the route entry.
581 * Did you get all that?
585 old_gateway = r->rt_gateway;
586 old_parent = r->rt_parent;
590 IF_DEBUG(DEBUG_RTDETAIL)
591 log(LOG_DEBUG, 0, "%s (new parent) on vif %d advertises %s with adj_metric %d (old parent was %s on vif %d, metric %d)",
592 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
593 adj_metric, inet_fmt(old_gateway, s3), old_parent,
596 if (old_parent != vifi) {
597 init_children_and_leaves(r, vifi, 0);
598 uvifs[old_parent].uv_nroutes--;
599 uvifs[vifi].uv_nroutes++;
601 if (old_gateway != src) {
602 update_table_entry(r, old_gateway);
603 /*???old_gateway???->al_nroutes--;*/
607 r->rt_metric = adj_metric;
608 r->rt_flags |= RTF_CHANGED;
609 routes_changed = TRUE;
611 else if (vifi != r->rt_parent) {
613 * The report came from a vif other than the route's parent vif.
614 * Update the children info, if necessary.
616 if (AVOID_TRANSIT(vifi, r)) {
618 * The route's parent is a vif from which we're not supposed
619 * to transit onto this vif. Simply ignore the update.
621 IF_DEBUG(DEBUG_RTDETAIL)
622 log(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored due to NOTRANSIT)",
623 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
625 } else if (VIFM_ISSET(vifi, r->rt_children)) {
627 * Vif is a child vif for this route.
629 if (metric < r->rt_metric ||
630 (metric == r->rt_metric &&
631 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
633 * Neighbor has lower metric to origin (or has same metric
634 * and lower IP address) -- it becomes the dominant router,
635 * and vif is no longer a child for me.
637 VIFM_CLR(vifi, r->rt_children);
638 r->rt_dominants [vifi] = src;
640 * We don't necessarily want to forget about subordinateness
641 * so that we can become the dominant quickly if the current
644 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
645 update_table_entry(r, r->rt_gateway);
646 IF_DEBUG(DEBUG_RTDETAIL)
647 log(LOG_DEBUG, 0, "%s on vif %d becomes dominant for %s with metric %d",
648 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
651 else if (metric > UNREACHABLE) { /* "poisoned reverse" */
653 * Neighbor considers this vif to be on path to route's
654 * origin; record this neighbor as subordinate
656 if (!NBRM_ISSET(n->al_index, r->rt_subordinates)) {
657 IF_DEBUG(DEBUG_RTDETAIL)
658 log(LOG_DEBUG, 0, "%s on vif %d becomes subordinate for %s with poison-reverse metric %d",
659 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
660 metric - UNREACHABLE);
661 NBRM_SET(n->al_index, r->rt_subordinates);
662 update_table_entry(r, r->rt_gateway);
664 IF_DEBUG(DEBUG_RTDETAIL)
665 log(LOG_DEBUG, 0, "%s on vif %d confirms subordinateness for %s with poison-reverse metric %d",
666 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
667 metric - UNREACHABLE);
669 NBRM_SET(n->al_index, r->rt_subordadv);
671 else if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
673 * Current subordinate no longer considers this vif to be on
674 * path to route's origin; it is no longer a subordinate
677 IF_DEBUG(DEBUG_RTDETAIL)
678 log(LOG_DEBUG, 0, "%s on vif %d is no longer a subordinate for %s with metric %d",
679 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
681 NBRM_CLR(n->al_index, r->rt_subordinates);
682 update_table_entry(r, r->rt_gateway);
686 else if (src == r->rt_dominants[vifi] &&
687 (metric > r->rt_metric ||
688 (metric == r->rt_metric &&
689 ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
691 * Current dominant no longer has a lower metric to origin
692 * (or same metric and lower IP address); we adopt the vif
695 IF_DEBUG(DEBUG_RTDETAIL)
696 log(LOG_DEBUG, 0, "%s (current dominant) on vif %d is no longer dominant for %s with metric %d",
697 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
699 VIFM_SET(vifi, r->rt_children);
700 r->rt_dominants[vifi] = 0;
701 if (uvifs[vifi].uv_flags & VIFF_NOFLOOD)
702 NBRM_CLRMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
704 NBRM_SETMASK(r->rt_subordinates, uvifs[vifi].uv_nbrmap);
705 if (metric > UNREACHABLE) {
706 NBRM_SET(n->al_index, r->rt_subordinates);
707 NBRM_SET(n->al_index, r->rt_subordadv);
709 update_table_entry(r, r->rt_gateway);
711 IF_DEBUG(DEBUG_RTDETAIL)
712 log(LOG_DEBUG, 0, "%s on vif %d advertises %s with metric %d (ignored)",
713 inet_fmt(src, s1), vifi, inet_fmts(origin, mask, s2),
721 * On every timer interrupt, advance the timer in each routing entry.
726 register struct rtentry *r;
727 register struct rtentry *prev_r;
728 extern u_long virtual_time; /* from main.c */
730 for (prev_r = RT_ADDR, r = routing_table;
732 prev_r = r, r = r->rt_next) {
734 if ((r->rt_timer += TIMER_INTERVAL) >= ROUTE_DISCARD_TIME) {
736 * Time to garbage-collect the route entry.
738 del_table_entry(r, 0, DEL_ALL_ROUTES);
739 discard_route(prev_r);
742 else if (r->rt_timer >= ROUTE_EXPIRE_TIME &&
743 r->rt_metric != UNREACHABLE) {
745 * Time to expire the route entry. If the gateway is zero,
746 * i.e., it is a route to a directly-connected subnet, just
747 * set the timer back to zero; such routes expire only when
748 * the interface to the subnet goes down.
750 if (r->rt_gateway == 0) {
754 del_table_entry(r, 0, DEL_ALL_ROUTES);
755 r->rt_metric = UNREACHABLE;
756 r->rt_flags |= RTF_CHANGED;
757 routes_changed = TRUE;
760 else if (virtual_time % (ROUTE_REPORT_INTERVAL * 2) == 0) {
762 * Time out subordinateness that hasn't been reported in
763 * the last 2 intervals.
765 if (!NBRM_SAME(r->rt_subordinates, r->rt_subordadv)) {
766 IF_DEBUG(DEBUG_ROUTE)
767 log(LOG_DEBUG, 0, "rt %s sub 0x%08x%08x subadv 0x%08x%08x metric %d",
769 r->rt_subordinates.hi, r->rt_subordinates.lo,
770 r->rt_subordadv.hi, r->rt_subordadv.lo, r->rt_metric);
771 NBRM_MASK(r->rt_subordinates, r->rt_subordadv);
772 update_table_entry(r, r->rt_gateway);
774 NBRM_CLRALL(r->rt_subordadv);
781 * Mark all routes as unreachable. This function is called only from
782 * hup() in preparation for informing all neighbors that we are going
783 * off the air. For consistency, we ought also to delete all reachable
784 * route entries from the kernel, but since we are about to exit we rely
785 * on the kernel to do its own cleanup -- no point in making all those
786 * expensive kernel calls now.
791 register struct rtentry *r;
793 for (r = routing_table; r != NULL; r = r->rt_next) {
794 r->rt_metric = UNREACHABLE;
795 r->rt_flags |= RTF_CHANGED;
796 routes_changed = TRUE;
802 * Delete all the routes in the routing table.
807 register struct rtentry *r;
817 * Process an incoming neighbor probe message.
820 accept_probe(src, dst, p, datalen, level)
828 static struct listaddr *unknowns = NULL;
830 if ((vifi = find_vif(src, dst)) == NO_VIF) {
831 struct listaddr *a, **prev;
832 struct listaddr *match = NULL;
833 time_t now = time(0);
835 for (prev = &unknowns, a = *prev; a; a = *prev) {
836 if (a->al_addr == src)
838 if (a->al_ctime + 2 * a->al_timer < now) {
839 /* We haven't heard from it in a long time */
847 match = *prev = (struct listaddr *)malloc(sizeof(struct listaddr));
848 match->al_next = NULL;
849 match->al_addr = src;
850 match->al_timer = OLD_NEIGHBOR_EXPIRE_TIME;
851 match->al_ctime = now - match->al_timer;
854 if (match->al_ctime + match->al_timer <= now) {
856 "ignoring probe from non-neighbor %s, check for misconfigured tunnel or routing on %s",
857 inet_fmt(src, s1), s1);
858 match->al_timer *= 2;
862 "ignoring probe from non-neighbor %s (%d seconds until next warning)", inet_fmt(src, s1), match->al_ctime + match->al_timer - now);
866 update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
877 compare_rts(rt1, rt2)
881 register struct newrt *r1 = (struct newrt *)rt1;
882 register struct newrt *r2 = (struct newrt *)rt2;
883 register u_int32 m1 = ntohl(r1->mask);
884 register u_int32 m2 = ntohl(r2->mask);
885 register u_int32 o1, o2;
892 /* masks are equal */
893 o1 = ntohl(r1->origin);
894 o2 = ntohl(r2->origin);
906 register struct uvif *v;
909 if (v->uv_blasterbuf)
910 free(v->uv_blasterbuf);
912 v->uv_blasterlen = 64*1024;
913 v->uv_blasterbuf = malloc(v->uv_blasterlen);
914 v->uv_blastercur = v->uv_blasterend = v->uv_blasterbuf;
915 if (v->uv_blastertimer)
916 timer_clearTimer(v->uv_blastertimer);
917 v->uv_blastertimer = 0;
928 * Queue a route report from a route-blaster.
929 * If the timer isn't running to process these reports,
933 queue_blaster_report(vifi, src, dst, p, datalen, level)
935 u_int32 src, dst, level;
937 register int datalen;
939 register struct blaster_hdr *bh;
940 register struct uvif *v;
941 int bblen = sizeof(*bh) + ((datalen + 3) & ~3);
944 if (v->uv_blasterend - v->uv_blasterbuf +
945 bblen > v->uv_blasterlen) {
946 int end = v->uv_blasterend - v->uv_blasterbuf;
947 int cur = v->uv_blastercur - v->uv_blasterbuf;
949 v->uv_blasterlen *= 2;
951 log(LOG_DEBUG, 0, "increasing blasterbuf to %d bytes",
953 v->uv_blasterbuf = realloc(v->uv_blasterbuf,
955 if (v->uv_blasterbuf == NULL) {
956 log(LOG_WARNING, ENOMEM, "turning off blaster on vif %d", vifi);
957 v->uv_blasterlen = 0;
958 v->uv_blasterend = v->uv_blastercur = NULL;
959 v->uv_flags &= ~VIFF_BLASTER;
962 v->uv_blasterend = v->uv_blasterbuf + end;
963 v->uv_blastercur = v->uv_blasterbuf + cur;
965 bh = (struct blaster_hdr *)v->uv_blasterend;
968 bh->bh_level = level;
969 bh->bh_datalen = datalen;
970 bcopy(p, (char *)(bh + 1), datalen);
971 v->uv_blasterend += bblen;
973 if (v->uv_blastertimer == 0) {
974 int *i = (int *)malloc(sizeof(int *));
977 log(LOG_ERR, 0, "out of memory");
981 v->uv_blastertimer = timer_setTimer(5,
982 process_blaster_report, i);
987 * Periodic process; process up to 5 of the routes in the route-blaster
988 * queue. If there are more routes remaining, reschedule myself to run
992 process_blaster_report(vifip)
995 vifi_t vifi = *(int *)vifip;
996 register struct uvif *v;
997 register struct blaster_hdr *bh;
1000 IF_DEBUG(DEBUG_ROUTE)
1001 log(LOG_DEBUG, 0, "processing vif %d blasted routes", vifi);
1003 for (i = 0; i < 5; i++) {
1004 if (v->uv_blastercur >= v->uv_blasterend)
1006 bh = (struct blaster_hdr *)v->uv_blastercur;
1007 v->uv_blastercur += sizeof(*bh) + ((bh->bh_datalen + 3) & ~3);
1008 accept_report(bh->bh_src, bh->bh_dst, (char *)(bh + 1),
1009 -bh->bh_datalen, bh->bh_level);
1012 if (v->uv_blastercur >= v->uv_blasterend) {
1013 v->uv_blastercur = v->uv_blasterbuf;
1014 v->uv_blasterend = v->uv_blasterbuf;
1015 v->uv_blastertimer = 0;
1017 IF_DEBUG(DEBUG_ROUTE)
1018 log(LOG_DEBUG, 0, "finish processing vif %d blaster", vifi);
1020 IF_DEBUG(DEBUG_ROUTE)
1021 log(LOG_DEBUG, 0, "more blasted routes to come on vif %d", vifi);
1022 v->uv_blastertimer = timer_setTimer(1,
1023 process_blaster_report, vifip);
1028 * Process an incoming route report message.
1029 * If the report arrived on a vif marked as a "blaster", then just
1030 * queue it and return; queue_blaster_report() will schedule it for
1031 * processing later. If datalen is negative, then this is actually
1032 * a queued report so actually process it instead of queueing it.
1035 accept_report(src, dst, p, datalen, level)
1036 u_int32 src, dst, level;
1038 register int datalen;
1041 register int width, i, nrt = 0;
1045 struct newrt rt[4096];
1046 struct listaddr *nbr;
1048 if ((vifi = find_vif(src, dst)) == NO_VIF) {
1050 "ignoring route report from non-neighbor %s", inet_fmt(src, s1));
1054 if (uvifs[vifi].uv_flags & VIFF_BLASTER)
1056 queue_blaster_report(vifi, src, dst, p, datalen, level);
1062 if (!(nbr = update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level)))
1065 if (datalen > 2*4096) {
1067 "ignoring oversize (%d bytes) route report from %s",
1068 datalen, inet_fmt(src, s1));
1072 while (datalen > 0) { /* Loop through per-mask lists. */
1076 "received truncated route report from %s",
1080 ((u_char *)&mask)[0] = 0xff; width = 1;
1081 if ((((u_char *)&mask)[1] = *p++) != 0) width = 2;
1082 if ((((u_char *)&mask)[2] = *p++) != 0) width = 3;
1083 if ((((u_char *)&mask)[3] = *p++) != 0) width = 4;
1084 if (!inet_valid_mask(ntohl(mask))) {
1086 "%s reports bogus netmask 0x%08x (%s)",
1087 inet_fmt(src, s1), ntohl(mask), inet_fmt(mask, s2));
1092 do { /* Loop through (origin, metric) pairs */
1093 if (datalen < width + 1) {
1095 "received truncated route report from %s",
1100 for (i = 0; i < width; ++i)
1101 ((char *)&origin)[i] = *p++;
1103 datalen -= width + 1;
1104 rt[nrt].mask = mask;
1105 rt[nrt].origin = origin;
1106 rt[nrt].metric = (metric & 0x7f);
1108 } while (!(metric & 0x80));
1111 qsort((char*)rt, nrt, sizeof(rt[0]), compare_rts);
1112 start_route_updates();
1114 * If the last entry is default, change mask from 0xff000000 to 0
1116 if (rt[nrt-1].origin == 0)
1119 IF_DEBUG(DEBUG_ROUTE)
1120 log(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt,
1121 inet_fmt(src, s1), inet_fmt(dst, s2));
1122 for (i = 0; i < nrt; ++i) {
1123 if (i != 0 && rt[i].origin == rt[i-1].origin &&
1124 rt[i].mask == rt[i-1].mask) {
1125 log(LOG_WARNING, 0, "%s reports duplicate route for %s",
1126 inet_fmt(src, s1), inet_fmts(rt[i].origin, rt[i].mask, s2));
1129 /* Only filter non-poisoned updates. */
1130 if (uvifs[vifi].uv_filter && rt[i].metric < UNREACHABLE) {
1131 struct vf_element *vfe;
1134 for (vfe = uvifs[vifi].uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
1135 if (vfe->vfe_flags & VFEF_EXACT) {
1136 if ((vfe->vfe_addr == rt[i].origin) &&
1137 (vfe->vfe_mask == rt[i].mask)) {
1142 if ((rt[i].origin & vfe->vfe_mask) == vfe->vfe_addr) {
1148 if ((uvifs[vifi].uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
1149 (uvifs[vifi].uv_filter->vf_type == VFT_DENY && match == 1)) {
1150 IF_DEBUG(DEBUG_ROUTE)
1151 log(LOG_DEBUG, 0, "%s skipped on vif %d because it %s %s",
1152 inet_fmts(rt[i].origin, rt[i].mask, s1),
1154 match ? "matches" : "doesn't match",
1155 match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2) :
1158 rt[i].metric += vfe->vfe_addmetric;
1159 if (rt[i].metric > UNREACHABLE)
1161 rt[i].metric = UNREACHABLE;
1164 update_route(rt[i].origin, rt[i].mask, rt[i].metric,
1168 if (routes_changed && !delay_change_reports)
1169 report_to_all_neighbors(CHANGED_ROUTES);
1174 * Send a route report message to destination 'dst', via virtual interface
1175 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
1178 report(which_routes, vifi, dst)
1183 register struct rtentry *r;
1187 while (r != RT_ADDR) {
1188 i = report_chunk(which_routes, r, vifi, dst);
1196 * Send a route report message to all neighboring routers.
1197 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
1200 report_to_all_neighbors(which_routes)
1203 register vifi_t vifi;
1204 register struct uvif *v;
1205 register struct rtentry *r;
1206 int routes_changed_before;
1209 * Remember the state of the global routes_changed flag before
1210 * generating the reports, and clear the flag.
1212 routes_changed_before = routes_changed;
1213 routes_changed = FALSE;
1216 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
1217 if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
1218 report(which_routes, vifi, v->uv_dst_addr);
1223 * If there were changed routes before we sent the reports AND
1224 * if no new changes occurred while sending the reports, clear
1225 * the change flags in the individual route entries. If changes
1226 * did occur while sending the reports, new reports will be
1227 * generated at the next timer interrupt.
1229 if (routes_changed_before && !routes_changed) {
1230 for (r = routing_table; r != NULL; r = r->rt_next) {
1231 r->rt_flags &= ~RTF_CHANGED;
1236 * Set a flag to inhibit further reports of changed routes until the
1237 * next timer interrupt. This is to alleviate update storms.
1239 delay_change_reports = TRUE;
1243 * Send a route report message to destination 'dst', via virtual interface
1244 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
1247 report_chunk(which_routes, start_rt, vifi, dst)
1249 register struct rtentry *start_rt;
1253 register struct rtentry *r;
1256 register int nrt = 0;
1257 struct uvif *v = &uvifs[vifi];
1262 int admetric = v->uv_admetric;
1265 src = v->uv_lcl_addr;
1266 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
1268 for (r = start_rt; r != RT_ADDR; r = r->rt_prev) {
1269 if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED)) {
1275 * Do not poison-reverse a route for a directly-connected
1276 * subnetwork on that subnetwork. This can cause loops when
1277 * some router on the subnetwork is misconfigured.
1279 if (r->rt_gateway == 0 && r->rt_parent == vifi) {
1284 if (v->uv_filter && v->uv_filter->vf_flags & VFF_BIDIR) {
1285 struct vf_element *vfe;
1288 for (vfe = v->uv_filter->vf_filter; vfe; vfe = vfe->vfe_next) {
1289 if (vfe->vfe_flags & VFEF_EXACT) {
1290 if ((vfe->vfe_addr == r->rt_origin) &&
1291 (vfe->vfe_mask == r->rt_originmask)) {
1296 if ((r->rt_origin & vfe->vfe_mask) == vfe->vfe_addr) {
1302 if ((v->uv_filter->vf_type == VFT_ACCEPT && match == 0) ||
1303 (v->uv_filter->vf_type == VFT_DENY && match == 1)) {
1304 IF_DEBUG(DEBUG_ROUTE)
1305 log(LOG_DEBUG, 0, "%s not reported on vif %d because it %s %s",
1306 RT_FMT(r, s1), vifi,
1307 match ? "matches" : "doesn't match",
1308 match ? inet_fmts(vfe->vfe_addr, vfe->vfe_mask, s2) :
1316 * If there is no room for this route in the current message,
1317 * send it & return how many routes we sent.
1319 if (datalen + ((r->rt_originmask == mask) ?
1321 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
1323 send_on_vif(v, 0, DVMRP_REPORT, datalen);
1327 if (r->rt_originmask != mask || datalen == 0) {
1328 mask = r->rt_originmask;
1329 width = r->rt_originwidth;
1330 if (datalen != 0) *(p-1) |= 0x80;
1331 *p++ = ((char *)&mask)[1];
1332 *p++ = ((char *)&mask)[2];
1333 *p++ = ((char *)&mask)[3];
1336 for (i = 0; i < width; ++i)
1337 *p++ = ((char *)&(r->rt_origin))[i];
1339 metric = r->rt_metric + admetric;
1340 if (metric > UNREACHABLE)
1341 metric = UNREACHABLE;
1342 if (r->rt_parent != vifi && AVOID_TRANSIT(vifi, r))
1343 metric = UNREACHABLE;
1344 *p++ = (r->rt_parent == vifi && metric != UNREACHABLE) ?
1345 (char)(metric + UNREACHABLE) : /* "poisoned reverse" */
1348 datalen += width + 1;
1352 send_on_vif(v, 0, DVMRP_REPORT, datalen);
1358 * send the next chunk of our routing table to all neighbors.
1359 * return the length of the smallest chunk we sent out.
1364 register vifi_t vifi;
1365 register struct uvif *v;
1366 register struct rtentry *sr;
1367 register int i, n = 0, min = 20000;
1368 static int start_rt;
1374 * find this round's starting route.
1376 for (sr = rt_end, i = start_rt; --i >= 0; ) {
1383 * send one chunk of routes starting at this round's start to
1384 * all our neighbors.
1386 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
1387 if (!NBRM_ISEMPTY(v->uv_nbrmap)) {
1388 n = report_chunk(ALL_ROUTES, sr, vifi, v->uv_dst_addr);
1394 min = 0; /* Neighborless router didn't send any routes */
1397 IF_DEBUG(DEBUG_ROUTE)
1398 log(LOG_INFO, 0, "update %d starting at %d of %d",
1399 n, (nroutes - start_rt), nroutes);
1401 start_rt = (start_rt + n) % nroutes;
1407 * Print the contents of the routing table on file 'fp'.
1413 register struct rtentry *r;
1418 "Multicast Routing Table (%u %s)\n%s\n",
1419 nroutes, (nroutes == 1) ? "entry" : "entries",
1420 " Origin-Subnet From-Gateway Metric Tmr Fl In-Vif Out-Vifs");
1422 for (r = routing_table; r != NULL; r = r->rt_next) {
1424 fprintf(fp, " %-18s %-15s ",
1425 inet_fmts(r->rt_origin, r->rt_originmask, s1),
1426 (r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway, s2));
1428 fprintf(fp, (r->rt_metric == UNREACHABLE) ? " NR " : "%4u ",
1431 fprintf(fp, " %3u %c%c %3u ", r->rt_timer,
1432 (r->rt_flags & RTF_CHANGED) ? 'C' : '.',
1433 (r->rt_flags & RTF_HOLDDOWN) ? 'H' : '.',
1436 for (i = 0; i < numvifs; ++i) {
1440 if (VIFM_ISSET(i, r->rt_children)) {
1441 if ((uvifs[i].uv_flags & VIFF_TUNNEL) &&
1442 !NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
1443 /* Don't print out parenthood of a leaf tunnel. */
1445 fprintf(fp, " %u", i);
1446 if (!NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
1448 for (n = uvifs[i].uv_neighbors; n; n = n->al_next) {
1449 if (NBRM_ISSET(n->al_index, r->rt_subordinates)) {
1450 fprintf(fp, "%c%d", l, n->al_index);
1464 determine_route(src)
1469 for (rt = routing_table; rt != NULL; rt = rt->rt_next) {
1470 if (rt->rt_origin == (src & rt->rt_originmask) &&
1471 rt->rt_metric != UNREACHABLE)