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