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