1 /* $NetBSD: route.c,v 1.13 2009/04/17 16:05:43 lukem Exp $ */
2
3 /*
4 * The mrouted program is covered by the license in the accompanying file
5 * named "LICENSE". Use of the mrouted program represents acceptance of
6 * the terms and conditions listed in that file.
7 *
8 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
9 * Leland Stanford Junior University.
10 */
11
12
13 #include "defs.h"
14
15
16 /*
17 * This define statement saves a lot of space later
18 */
19 #define RT_ADDR (struct rtentry *)&routing_table
20
21 /*
22 * Exported variables.
23 */
24 int routes_changed; /* 1=>some routes have changed */
25 int delay_change_reports; /* 1=>postpone change reports */
26
27
28 /*
29 * The routing table is shared with prune.c , so must not be static.
30 */
31 struct rtentry *routing_table; /* pointer to list of route entries */
32
33 /*
34 * Private variables.
35 */
36 static struct rtentry *rtp; /* pointer to a route entry */
37 static struct rtentry *rt_end; /* pointer to last route entry */
38 unsigned int nroutes; /* current number of route entries */
39
40 /*
41 * Private functions.
42 */
43 static int init_children_and_leaves(struct rtentry *r, vifi_t parent);
44 static int find_route(u_int32_t origin, u_int32_t mask);
45 static void create_route(u_int32_t origin, u_int32_t mask);
46 static void discard_route(struct rtentry *prev_r);
47 static int compare_rts(const void *rt1, const void *rt2);
48 static int report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst);
49
50 /*
51 * Initialize the routing table and associated variables.
52 */
53 void
init_routes(void)54 init_routes(void)
55 {
56 routing_table = NULL;
57 rt_end = RT_ADDR;
58 nroutes = 0;
59 routes_changed = FALSE;
60 delay_change_reports = FALSE;
61 }
62
63
64 /*
65 * Initialize the children and leaf bits for route 'r', along with the
66 * associated dominant, subordinate, and leaf timing data structures.
67 * Return TRUE if this changes the value of either the children or
68 * leaf bitmaps for 'r'.
69 */
70 static int
init_children_and_leaves(struct rtentry * r,vifi_t parent)71 init_children_and_leaves(struct rtentry *r, vifi_t parent)
72 {
73 vifi_t vifi;
74 struct uvif *v;
75 vifbitmap_t old_children, old_leaves;
76
77 VIFM_COPY(r->rt_children, old_children);
78 VIFM_COPY(r->rt_leaves, old_leaves );
79
80 VIFM_CLRALL(r->rt_children);
81 VIFM_CLRALL(r->rt_leaves);
82 r->rt_flags &= ~RTF_LEAF_TIMING;
83
84 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
85 r->rt_dominants [vifi] = 0;
86 r->rt_subordinates[vifi] = 0;
87
88 if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED))) {
89 VIFM_SET(vifi, r->rt_children);
90 if (v->uv_neighbors == NULL) {
91 VIFM_SET(vifi, r->rt_leaves);
92 r->rt_leaf_timers[vifi] = 0;
93 }
94 else {
95 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
96 r->rt_flags |= RTF_LEAF_TIMING;
97 }
98 }
99 else {
100 r->rt_leaf_timers[vifi] = 0;
101 }
102 }
103
104 return (!VIFM_SAME(r->rt_children, old_children) ||
105 !VIFM_SAME(r->rt_leaves, old_leaves));
106 }
107
108
109 /*
110 * A new vif has come up -- update the children and leaf bitmaps in all route
111 * entries to take that into account.
112 */
113 void
add_vif_to_routes(vifi_t vifi)114 add_vif_to_routes(vifi_t vifi)
115 {
116 struct rtentry *r;
117 struct uvif *v;
118
119 v = &uvifs[vifi];
120 for (r = routing_table; r != NULL; r = r->rt_next) {
121 if (r->rt_metric != UNREACHABLE &&
122 !VIFM_ISSET(vifi, r->rt_children)) {
123 VIFM_SET(vifi, r->rt_children);
124 r->rt_dominants [vifi] = 0;
125 r->rt_subordinates[vifi] = 0;
126 if (v->uv_neighbors == NULL) {
127 VIFM_SET(vifi, r->rt_leaves);
128 r->rt_leaf_timers[vifi] = 0;
129 }
130 else {
131 VIFM_CLR(vifi, r->rt_leaves);
132 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
133 r->rt_flags |= RTF_LEAF_TIMING;
134 }
135 update_table_entry(r);
136 }
137 }
138 }
139
140
141 /*
142 * A vif has gone down -- expire all routes that have that vif as parent,
143 * and update the children bitmaps in all other route entries to take into
144 * account the failed vif.
145 */
146 void
delete_vif_from_routes(vifi_t vifi)147 delete_vif_from_routes(vifi_t vifi)
148 {
149 struct rtentry *r;
150
151 for (r = routing_table; r != NULL; r = r->rt_next) {
152 if (r->rt_metric != UNREACHABLE) {
153 if (vifi == r->rt_parent) {
154 del_table_entry(r, 0, DEL_ALL_ROUTES);
155 r->rt_timer = ROUTE_EXPIRE_TIME;
156 r->rt_metric = UNREACHABLE;
157 r->rt_flags |= RTF_CHANGED;
158 routes_changed = TRUE;
159 }
160 else if (VIFM_ISSET(vifi, r->rt_children)) {
161 VIFM_CLR(vifi, r->rt_children);
162 VIFM_CLR(vifi, r->rt_leaves);
163 r->rt_subordinates[vifi] = 0;
164 r->rt_leaf_timers [vifi] = 0;
165 update_table_entry(r);
166 }
167 else {
168 r->rt_dominants[vifi] = 0;
169 }
170 }
171 }
172 }
173
174
175 /*
176 * A neighbor has failed or become unreachable. If that neighbor was
177 * considered a dominant or subordinate router in any route entries,
178 * take appropriate action.
179 */
180 void
delete_neighbor_from_routes(u_int32_t addr,vifi_t vifi)181 delete_neighbor_from_routes(u_int32_t addr, vifi_t vifi)
182 {
183 struct rtentry *r;
184 struct uvif *v;
185
186 v = &uvifs[vifi];
187 for (r = routing_table; r != NULL; r = r->rt_next) {
188 if (r->rt_metric != UNREACHABLE) {
189 if (r->rt_dominants[vifi] == addr) {
190 VIFM_SET(vifi, r->rt_children);
191 r->rt_dominants [vifi] = 0;
192 r->rt_subordinates[vifi] = 0;
193 if (v->uv_neighbors == NULL) {
194 VIFM_SET(vifi, r->rt_leaves);
195 r->rt_leaf_timers[vifi] = 0;
196 }
197 else {
198 VIFM_CLR(vifi, r->rt_leaves);
199 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
200 r->rt_flags |= RTF_LEAF_TIMING;
201 }
202 update_table_entry(r);
203 }
204 else if (r->rt_subordinates[vifi] == addr) {
205 r->rt_subordinates[vifi] = 0;
206 if (v->uv_neighbors == NULL) {
207 VIFM_SET(vifi, r->rt_leaves);
208 update_table_entry(r);
209 }
210 else {
211 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
212 r->rt_flags |= RTF_LEAF_TIMING;
213 }
214 }
215 else if (v->uv_neighbors == NULL &&
216 r->rt_leaf_timers[vifi] != 0) {
217 VIFM_SET(vifi, r->rt_leaves);
218 r->rt_leaf_timers[vifi] = 0;
219 update_table_entry(r);
220 }
221 }
222 }
223 }
224
225
226 /*
227 * Prepare for a sequence of ordered route updates by initializing a pointer
228 * to the start of the routing table. The pointer is used to remember our
229 * position in the routing table in order to avoid searching from the
230 * beginning for each update; this relies on having the route reports in
231 * a single message be in the same order as the route entries in the routing
232 * table.
233 */
234 void
start_route_updates(void)235 start_route_updates(void)
236 {
237 rtp = RT_ADDR;
238 }
239
240
241 /*
242 * Starting at the route entry following the one to which 'rtp' points,
243 * look for a route entry matching the specified origin and mask. If a
244 * match is found, return TRUE and leave 'rtp' pointing at the found entry.
245 * If no match is found, return FALSE and leave 'rtp' pointing to the route
246 * entry preceding the point at which the new origin should be inserted.
247 * This code is optimized for the normal case in which the first entry to
248 * be examined is the matching entry.
249 */
250 static int
find_route(u_int32_t origin,u_int32_t mask)251 find_route(u_int32_t origin, u_int32_t mask)
252 {
253 struct rtentry *r;
254
255 r = rtp->rt_next;
256 while (r != NULL) {
257 if (origin == r->rt_origin && mask == r->rt_originmask) {
258 rtp = r;
259 return (TRUE);
260 }
261 if (ntohl(mask) < ntohl(r->rt_originmask) ||
262 (mask == r->rt_originmask &&
263 ntohl(origin) < ntohl(r->rt_origin))) {
264 rtp = r;
265 r = r->rt_next;
266 }
267 else break;
268 }
269 return (FALSE);
270 }
271
272 /*
273 * Create a new routing table entry for the specified origin and link it into
274 * the routing table. The shared variable 'rtp' is assumed to point to the
275 * routing entry after which the new one should be inserted. It is left
276 * pointing to the new entry.
277 *
278 * Only the origin, originmask, originwidth and flags fields are initialized
279 * in the new route entry; the caller is responsible for filling in the rest.
280 */
281 static void
create_route(u_int32_t origin,u_int32_t mask)282 create_route(u_int32_t origin, u_int32_t mask)
283 {
284 struct rtentry *r;
285
286 if ((r = (struct rtentry *) malloc(sizeof(struct rtentry) +
287 (2 * numvifs * sizeof(u_int32_t)) +
288 (numvifs * sizeof(u_int)))) == NULL) {
289 logit(LOG_ERR, 0, "ran out of memory"); /* fatal */
290 return;
291 }
292 r->rt_origin = origin;
293 r->rt_originmask = mask;
294 if (((char *)&mask)[3] != 0) r->rt_originwidth = 4;
295 else if (((char *)&mask)[2] != 0) r->rt_originwidth = 3;
296 else if (((char *)&mask)[1] != 0) r->rt_originwidth = 2;
297 else r->rt_originwidth = 1;
298 r->rt_flags = 0;
299 r->rt_dominants = (u_int32_t *)(r + 1);
300 r->rt_subordinates = (u_int32_t *)(r->rt_dominants + numvifs);
301 r->rt_leaf_timers = (u_int *)(r->rt_subordinates + numvifs);
302 r->rt_groups = NULL;
303
304 r->rt_next = rtp->rt_next;
305 rtp->rt_next = r;
306 r->rt_prev = rtp;
307 if (r->rt_next != NULL)
308 (r->rt_next)->rt_prev = r;
309 else
310 rt_end = r;
311 rtp = r;
312 ++nroutes;
313 }
314
315
316 /*
317 * Discard the routing table entry following the one to which 'prev_r' points.
318 */
319 static void
discard_route(struct rtentry * prev_r)320 discard_route(struct rtentry *prev_r)
321 {
322 struct rtentry *r;
323
324 r = prev_r->rt_next;
325 prev_r->rt_next = r->rt_next;
326 if (prev_r->rt_next != NULL)
327 (prev_r->rt_next)->rt_prev = prev_r;
328 else
329 rt_end = prev_r;
330 free((char *)r);
331 --nroutes;
332 }
333
334
335 /*
336 * Process a route report for a single origin, creating or updating the
337 * corresponding routing table entry if necessary. 'src' is either the
338 * address of a neighboring router from which the report arrived, or zero
339 * to indicate a change of status of one of our own interfaces.
340 */
341 void
update_route(u_int32_t origin,u_int32_t mask,u_int metric,u_int32_t src,vifi_t vifi)342 update_route(u_int32_t origin, u_int32_t mask, u_int metric, u_int32_t src,
343 vifi_t vifi)
344 {
345 struct rtentry *r;
346 u_int adj_metric;
347
348 /*
349 * Compute an adjusted metric, taking into account the cost of the
350 * subnet or tunnel over which the report arrived, and normalizing
351 * all unreachable/poisoned metrics into a single value.
352 */
353 if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) {
354 logit(LOG_WARNING, 0,
355 "%s reports out-of-range metric %u for origin %s",
356 inet_fmt(src), metric,
357 inet_fmts(origin, mask));
358 return;
359 }
360 adj_metric = metric + uvifs[vifi].uv_metric;
361 if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE;
362
363 /*
364 * Look up the reported origin in the routing table.
365 */
366 if (!find_route(origin, mask)) {
367 /*
368 * Not found.
369 * Don't create a new entry if the report says it's unreachable,
370 * or if the reported origin and mask are invalid.
371 */
372 if (adj_metric == UNREACHABLE) {
373 return;
374 }
375 if (src != 0 && !inet_valid_subnet(origin, mask)) {
376 logit(LOG_WARNING, 0,
377 "%s reports an invalid origin (%s) and/or mask (%08x)",
378 inet_fmt(src),
379 inet_fmt(origin), ntohl(mask));
380 return;
381 }
382
383 /*
384 * OK, create the new routing entry. 'rtp' will be left pointing
385 * to the new entry.
386 */
387 create_route(origin, mask);
388
389 /*
390 * Now "steal away" any sources that belong under this route
391 * by deleting any cache entries they might have created
392 * and allowing the kernel to re-request them.
393 */
394 steal_sources(rtp);
395
396 rtp->rt_metric = UNREACHABLE; /* temporary; updated below */
397 }
398
399 /*
400 * We now have a routing entry for the reported origin. Update it?
401 */
402 r = rtp;
403 if (r->rt_metric == UNREACHABLE) {
404 /*
405 * The routing entry is for a formerly-unreachable or new origin.
406 * If the report claims reachability, update the entry to use
407 * the reported route.
408 */
409 if (adj_metric == UNREACHABLE)
410 return;
411
412 r->rt_parent = vifi;
413 init_children_and_leaves(r, vifi);
414
415 r->rt_gateway = src;
416 r->rt_timer = 0;
417 r->rt_metric = adj_metric;
418 r->rt_flags |= RTF_CHANGED;
419 routes_changed = TRUE;
420 update_table_entry(r);
421 }
422 else if (src == r->rt_gateway) {
423 /*
424 * The report has come either from the interface directly-connected
425 * to the origin subnet (src and r->rt_gateway both equal zero) or
426 * from the gateway we have chosen as the best first-hop gateway back
427 * towards the origin (src and r->rt_gateway not equal zero). Reset
428 * the route timer and, if the reported metric has changed, update
429 * our entry accordingly.
430 */
431 r->rt_timer = 0;
432 if (adj_metric == r->rt_metric)
433 return;
434
435 if (adj_metric == UNREACHABLE) {
436 del_table_entry(r, 0, DEL_ALL_ROUTES);
437 r->rt_timer = ROUTE_EXPIRE_TIME;
438 }
439 else if (adj_metric < r->rt_metric) {
440 if (init_children_and_leaves(r, vifi)) {
441 update_table_entry(r);
442 }
443 }
444 r->rt_metric = adj_metric;
445 r->rt_flags |= RTF_CHANGED;
446 routes_changed = TRUE;
447 }
448 else if (src == 0 ||
449 (r->rt_gateway != 0 &&
450 (adj_metric < r->rt_metric ||
451 (adj_metric == r->rt_metric &&
452 (ntohl(src) < ntohl(r->rt_gateway) ||
453 r->rt_timer >= ROUTE_SWITCH_TIME))))) {
454 /*
455 * The report is for an origin we consider reachable; the report
456 * comes either from one of our own interfaces or from a gateway
457 * other than the one we have chosen as the best first-hop gateway
458 * back towards the origin. If the source of the update is one of
459 * our own interfaces, or if the origin is not a directly-connected
460 * subnet and the reported metric for that origin is better than
461 * what our routing entry says, update the entry to use the new
462 * gateway and metric. We also switch gateways if the reported
463 * metric is the same as the one in the route entry and the gateway
464 * associated with the route entry has not been heard from recently,
465 * or if the metric is the same but the reporting gateway has a lower
466 * IP address than the gateway associated with the route entry.
467 * Did you get all that?
468 */
469 if (r->rt_parent != vifi || adj_metric < r->rt_metric) {
470 /*
471 * XXX Why do we do this if we are just changing the metric?
472 */
473 r->rt_parent = vifi;
474 if (init_children_and_leaves(r, vifi)) {
475 update_table_entry(r);
476 }
477 }
478 r->rt_gateway = src;
479 r->rt_timer = 0;
480 r->rt_metric = adj_metric;
481 r->rt_flags |= RTF_CHANGED;
482 routes_changed = TRUE;
483 }
484 else if (vifi != r->rt_parent) {
485 /*
486 * The report came from a vif other than the route's parent vif.
487 * Update the children and leaf info, if necessary.
488 */
489 if (VIFM_ISSET(vifi, r->rt_children)) {
490 /*
491 * Vif is a child vif for this route.
492 */
493 if (metric < r->rt_metric ||
494 (metric == r->rt_metric &&
495 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) {
496 /*
497 * Neighbor has lower metric to origin (or has same metric
498 * and lower IP address) -- it becomes the dominant router,
499 * and vif is no longer a child for me.
500 */
501 VIFM_CLR(vifi, r->rt_children);
502 VIFM_CLR(vifi, r->rt_leaves);
503 r->rt_dominants [vifi] = src;
504 r->rt_subordinates[vifi] = 0;
505 r->rt_leaf_timers [vifi] = 0;
506 update_table_entry(r);
507 }
508 else if (metric > UNREACHABLE) { /* "poisoned reverse" */
509 /*
510 * Neighbor considers this vif to be on path to route's
511 * origin; if no subordinate recorded, record this neighbor
512 * as subordinate and clear the leaf flag.
513 */
514 if (r->rt_subordinates[vifi] == 0) {
515 VIFM_CLR(vifi, r->rt_leaves);
516 r->rt_subordinates[vifi] = src;
517 r->rt_leaf_timers [vifi] = 0;
518 update_table_entry(r);
519 }
520 }
521 else if (src == r->rt_subordinates[vifi]) {
522 /*
523 * Current subordinate no longer considers this vif to be on
524 * path to route's origin; it is no longer a subordinate
525 * router, and we set the leaf confirmation timer to give
526 * us time to hear from other subordinates.
527 */
528 r->rt_subordinates[vifi] = 0;
529 if (uvifs[vifi].uv_neighbors == NULL ||
530 uvifs[vifi].uv_neighbors->al_next == NULL) {
531 VIFM_SET(vifi, r->rt_leaves);
532 update_table_entry(r);
533 }
534 else {
535 r->rt_leaf_timers [vifi] = LEAF_CONFIRMATION_TIME;
536 r->rt_flags |= RTF_LEAF_TIMING;
537 }
538 }
539
540 }
541 else if (src == r->rt_dominants[vifi] &&
542 (metric > r->rt_metric ||
543 (metric == r->rt_metric &&
544 ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) {
545 /*
546 * Current dominant no longer has a lower metric to origin
547 * (or same metric and lower IP address); we adopt the vif
548 * as our own child.
549 */
550 VIFM_SET(vifi, r->rt_children);
551 r->rt_dominants [vifi] = 0;
552 if (metric > UNREACHABLE) {
553 r->rt_subordinates[vifi] = src;
554 }
555 else if (uvifs[vifi].uv_neighbors == NULL ||
556 uvifs[vifi].uv_neighbors->al_next == NULL) {
557 VIFM_SET(vifi, r->rt_leaves);
558 }
559 else {
560 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME;
561 r->rt_flags |= RTF_LEAF_TIMING;
562 }
563 update_table_entry(r);
564 }
565 }
566 }
567
568
569 /*
570 * On every timer interrupt, advance the timer in each routing entry.
571 */
572 void
age_routes(void)573 age_routes(void)
574 {
575 struct rtentry *r;
576 struct rtentry *prev_r;
577 vifi_t vifi;
578
579 for (prev_r = RT_ADDR, r = routing_table;
580 r != NULL;
581 prev_r = r, r = r->rt_next) {
582
583 if ((r->rt_timer += TIMER_INTERVAL) < ROUTE_EXPIRE_TIME) {
584 /*
585 * Route is still good; see if any leaf timers need to be
586 * advanced.
587 */
588 if (r->rt_flags & RTF_LEAF_TIMING) {
589 r->rt_flags &= ~RTF_LEAF_TIMING;
590 for (vifi = 0; vifi < numvifs; ++vifi) {
591 if (r->rt_leaf_timers[vifi] != 0) {
592 /*
593 * Unlike other timers, leaf timers decrement.
594 */
595 if ((r->rt_leaf_timers[vifi] -= TIMER_INTERVAL) == 0){
596 #ifdef NOTYET
597 /* If the vif is a physical leaf but has neighbors,
598 * it is not a tree leaf. If I am a leaf, then no
599 * interface with neighbors is a tree leaf. */
600 if (!(((uvifs[vifi].uv_flags & VIFF_LEAF) ||
601 (vifs_with_neighbors == 1)) &&
602 (uvifs[vifi].uv_neighbors != NULL))) {
603 #endif
604 VIFM_SET(vifi, r->rt_leaves);
605 update_table_entry(r);
606 #ifdef NOTYET
607 }
608 #endif
609 }
610 else {
611 r->rt_flags |= RTF_LEAF_TIMING;
612 }
613 }
614 }
615 }
616 }
617 else if (r->rt_timer >= ROUTE_DISCARD_TIME) {
618 /*
619 * Time to garbage-collect the route entry.
620 */
621 del_table_entry(r, 0, DEL_ALL_ROUTES);
622 discard_route(prev_r);
623 r = prev_r;
624 }
625 else if (r->rt_metric != UNREACHABLE) {
626 /*
627 * Time to expire the route entry. If the gateway is zero,
628 * i.e., it is a route to a directly-connected subnet, just
629 * set the timer back to zero; such routes expire only when
630 * the interface to the subnet goes down.
631 */
632 if (r->rt_gateway == 0) {
633 r->rt_timer = 0;
634 }
635 else {
636 del_table_entry(r, 0, DEL_ALL_ROUTES);
637 r->rt_metric = UNREACHABLE;
638 r->rt_flags |= RTF_CHANGED;
639 routes_changed = TRUE;
640 }
641 }
642 }
643 }
644
645
646 /*
647 * Mark all routes as unreachable. This function is called only from
648 * hup() in preparation for informing all neighbors that we are going
649 * off the air. For consistency, we ought also to delete all reachable
650 * route entries from the kernel, but since we are about to exit we rely
651 * on the kernel to do its own cleanup -- no point in making all those
652 * expensive kernel calls now.
653 */
654 void
expire_all_routes(void)655 expire_all_routes(void)
656 {
657 struct rtentry *r;
658
659 for (r = routing_table; r != NULL; r = r->rt_next) {
660 r->rt_metric = UNREACHABLE;
661 r->rt_flags |= RTF_CHANGED;
662 routes_changed = TRUE;
663 }
664 }
665
666
667 /*
668 * Delete all the routes in the routing table.
669 */
670 void
free_all_routes(void)671 free_all_routes(void)
672 {
673 struct rtentry *r;
674
675 r = RT_ADDR;
676
677 while (r->rt_next)
678 discard_route(r);
679 }
680
681
682 /*
683 * Process an incoming neighbor probe message.
684 */
685 void
accept_probe(u_int32_t src,u_int32_t dst,char * p,int datalen,u_int32_t level)686 accept_probe(u_int32_t src, u_int32_t dst, char *p, int datalen,
687 u_int32_t level)
688 {
689 vifi_t vifi;
690
691 if ((vifi = find_vif(src, dst)) == NO_VIF) {
692 logit(LOG_INFO, 0,
693 "ignoring probe from non-neighbor %s", inet_fmt(src));
694 return;
695 }
696
697 update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level);
698 }
699
700 struct newrt {
701 u_int32_t mask;
702 u_int32_t origin;
703 int metric;
704 int pad;
705 };
706
707 static int
compare_rts(const void * rt1,const void * rt2)708 compare_rts(const void *rt1, const void *rt2)
709 {
710 const struct newrt *r1 = (const struct newrt *)rt1;
711 const struct newrt *r2 = (const struct newrt *)rt2;
712 u_int32_t m1 = ntohl(r1->mask);
713 u_int32_t m2 = ntohl(r2->mask);
714 u_int32_t o1, o2;
715
716 if (m1 > m2)
717 return (-1);
718 if (m1 < m2)
719 return (1);
720
721 /* masks are equal */
722 o1 = ntohl(r1->origin);
723 o2 = ntohl(r2->origin);
724 if (o1 > o2)
725 return (-1);
726 if (o1 < o2)
727 return (1);
728 return (0);
729 }
730
731 /*
732 * Process an incoming route report message.
733 */
734 void
accept_report(u_int32_t src,u_int32_t dst,char * p,int datalen,u_int32_t level)735 accept_report(u_int32_t src, u_int32_t dst, char *p, int datalen,
736 u_int32_t level)
737 {
738 vifi_t vifi;
739 int width, i, nrt = 0;
740 int metric;
741 u_int32_t mask;
742 u_int32_t origin;
743 struct newrt rt[4096];
744
745 if ((vifi = find_vif(src, dst)) == NO_VIF) {
746 logit(LOG_INFO, 0,
747 "ignoring route report from non-neighbor %s", inet_fmt(src));
748 return;
749 }
750
751 if (!update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level))
752 return;
753
754 if (datalen > 2*4096) {
755 logit(LOG_INFO, 0,
756 "ignoring oversize (%d bytes) route report from %s",
757 datalen, inet_fmt(src));
758 return;
759 }
760
761 while (datalen > 0) { /* Loop through per-mask lists. */
762
763 if (datalen < 3) {
764 logit(LOG_WARNING, 0,
765 "received truncated route report from %s",
766 inet_fmt(src));
767 return;
768 }
769 ((u_char *)&mask)[0] = 0xff; width = 1;
770 if ((((u_char *)&mask)[1] = *p++) != 0) width = 2;
771 if ((((u_char *)&mask)[2] = *p++) != 0) width = 3;
772 if ((((u_char *)&mask)[3] = *p++) != 0) width = 4;
773 if (!inet_valid_mask(ntohl(mask))) {
774 logit(LOG_WARNING, 0,
775 "%s reports bogus netmask 0x%08x (%s)",
776 inet_fmt(src), ntohl(mask),
777 inet_fmt(mask));
778 return;
779 }
780 datalen -= 3;
781
782 do { /* Loop through (origin, metric) pairs */
783 if (datalen < width + 1) {
784 logit(LOG_WARNING, 0,
785 "received truncated route report from %s",
786 inet_fmt(src));
787 return;
788 }
789 origin = 0;
790 for (i = 0; i < width; ++i)
791 ((char *)&origin)[i] = *p++;
792 metric = *p++;
793 datalen -= width + 1;
794 rt[nrt].mask = mask;
795 rt[nrt].origin = origin;
796 rt[nrt].metric = (metric & 0x7f);
797 ++nrt;
798 } while (!(metric & 0x80));
799 }
800
801 qsort((char*)rt, nrt, sizeof(rt[0]), compare_rts);
802 start_route_updates();
803 /*
804 * If the last entry is default, change mask from 0xff000000 to 0
805 */
806 if (rt[nrt-1].origin == 0)
807 rt[nrt-1].mask = 0;
808
809 logit(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt,
810 inet_fmt(src), inet_fmt(dst));
811 for (i = 0; i < nrt; ++i) {
812 if (i != 0 && rt[i].origin == rt[i-1].origin &&
813 rt[i].mask == rt[i-1].mask) {
814 logit(LOG_WARNING, 0, "%s reports duplicate route for %s",
815 inet_fmt(src),
816 inet_fmts(rt[i].origin, rt[i].mask));
817 continue;
818 }
819 update_route(rt[i].origin, rt[i].mask, rt[i].metric,
820 src, vifi);
821 }
822
823 if (routes_changed && !delay_change_reports)
824 report_to_all_neighbors(CHANGED_ROUTES);
825 }
826
827
828 /*
829 * Send a route report message to destination 'dst', via virtual interface
830 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
831 */
832 void
report(int which_routes,vifi_t vifi,u_int32_t dst)833 report(int which_routes, vifi_t vifi, u_int32_t dst)
834 {
835 struct rtentry *r;
836 char *p;
837 int i;
838 int datalen = 0;
839 int width = 0;
840 u_int32_t mask = 0;
841 u_int32_t src;
842 u_int32_t nflags;
843
844 src = uvifs[vifi].uv_lcl_addr;
845
846 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
847
848 #ifdef NOTYET
849 /* If I'm not a leaf, but the neighbor is a leaf, only advertise default */
850 if ((vifs_with_neighbors != 1) && (uvifs[vifi].uv_flags & VIFF_LEAF)) {
851 *p++ = 0; /* 0xff000000 mask */
852 *p++ = 0;
853 *p++ = 0;
854 *p++ = 0; /* class A net 0.0.0.0 == default */
855 *p++ = 0x81; /*XXX metric 1, is this safe? */
856 datalen += 5;
857 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
858 htonl(MROUTED_LEVEL), datalen);
859 return;
860 }
861 #endif
862
863 nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS;
864
865 for (r = rt_end; r != RT_ADDR; r = r->rt_prev) {
866
867 if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED))
868 continue;
869
870 /*
871 * If there is no room for this route in the current message,
872 * send the message and start a new one.
873 */
874 if (datalen + ((r->rt_originmask == mask) ?
875 (width + 1) :
876 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
877 *(p-1) |= 0x80;
878 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
879 htonl(MROUTED_LEVEL | nflags), datalen);
880
881 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
882 datalen = 0;
883 mask = 0;
884 }
885
886 if (r->rt_originmask != mask || datalen == 0) {
887 mask = r->rt_originmask;
888 width = r->rt_originwidth;
889 if (datalen != 0) *(p-1) |= 0x80;
890 *p++ = ((char *)&mask)[1];
891 *p++ = ((char *)&mask)[2];
892 *p++ = ((char *)&mask)[3];
893 datalen += 3;
894 }
895
896 for (i = 0; i < width; ++i)
897 *p++ = ((char *)&(r->rt_origin))[i];
898
899 *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ?
900 (char)(r->rt_metric + UNREACHABLE) : /* "poisoned reverse" */
901 (char)(r->rt_metric);
902
903 datalen += width + 1;
904 }
905
906 if (datalen != 0) {
907 *(p-1) |= 0x80;
908 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
909 htonl(MROUTED_LEVEL | nflags), datalen);
910 }
911 }
912
913
914 /*
915 * Send a route report message to all neighboring routers.
916 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
917 */
918 void
report_to_all_neighbors(int which_routes)919 report_to_all_neighbors(int which_routes)
920 {
921 vifi_t vifi;
922 struct uvif *v;
923 struct rtentry *r;
924 int routes_changed_before;
925
926 /*
927 * Remember the state of the global routes_changed flag before
928 * generating the reports, and clear the flag.
929 */
930 routes_changed_before = routes_changed;
931 routes_changed = FALSE;
932
933
934 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
935 if (v->uv_neighbors != NULL) {
936 report(which_routes, vifi,
937 (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr
938 : dvmrp_group);
939 }
940 }
941
942 /*
943 * If there were changed routes before we sent the reports AND
944 * if no new changes occurred while sending the reports, clear
945 * the change flags in the individual route entries. If changes
946 * did occur while sending the reports, new reports will be
947 * generated at the next timer interrupt.
948 */
949 if (routes_changed_before && !routes_changed) {
950 for (r = routing_table; r != NULL; r = r->rt_next) {
951 r->rt_flags &= ~RTF_CHANGED;
952 }
953 }
954
955 /*
956 * Set a flag to inhibit further reports of changed routes until the
957 * next timer interrupt. This is to alleviate update storms.
958 */
959 delay_change_reports = TRUE;
960 }
961
962 /*
963 * Send a route report message to destination 'dst', via virtual interface
964 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES.
965 */
966 static int
report_chunk(struct rtentry * start_rt,vifi_t vifi,u_int32_t dst)967 report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst)
968 {
969 struct rtentry *r;
970 char *p;
971 int i;
972 int nrt = 0;
973 int datalen = 0;
974 int width = 0;
975 u_int32_t mask = 0;
976 u_int32_t src;
977 u_int32_t nflags;
978
979 src = uvifs[vifi].uv_lcl_addr;
980 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
981
982 nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS;
983
984 for (r = start_rt; r != RT_ADDR; r = r->rt_prev) {
985
986 #ifdef NOTYET
987 /* Don't send poisoned routes back to parents if I am a leaf */
988 if ((vifs_with_neighbors == 1) && (r->rt_parent == vifi)
989 && (r->rt_metric > 1)) {
990 ++nrt;
991 continue;
992 }
993 #endif
994
995 /*
996 * If there is no room for this route in the current message,
997 * send it & return how many routes we sent.
998 */
999 if (datalen + ((r->rt_originmask == mask) ?
1000 (width + 1) :
1001 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) {
1002 *(p-1) |= 0x80;
1003 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
1004 htonl(MROUTED_LEVEL | nflags), datalen);
1005 return (nrt);
1006 }
1007 if (r->rt_originmask != mask || datalen == 0) {
1008 mask = r->rt_originmask;
1009 width = r->rt_originwidth;
1010 if (datalen != 0) *(p-1) |= 0x80;
1011 *p++ = ((char *)&mask)[1];
1012 *p++ = ((char *)&mask)[2];
1013 *p++ = ((char *)&mask)[3];
1014 datalen += 3;
1015 }
1016 for (i = 0; i < width; ++i)
1017 *p++ = ((char *)&(r->rt_origin))[i];
1018
1019 *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ?
1020 (char)(r->rt_metric + UNREACHABLE) : /* "poisoned reverse" */
1021 (char)(r->rt_metric);
1022 ++nrt;
1023 datalen += width + 1;
1024 }
1025 if (datalen != 0) {
1026 *(p-1) |= 0x80;
1027 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT,
1028 htonl(MROUTED_LEVEL | nflags), datalen);
1029 }
1030 return (nrt);
1031 }
1032
1033 /*
1034 * send the next chunk of our routing table to all neighbors.
1035 * return the length of the smallest chunk we sent out.
1036 */
1037 int
report_next_chunk(void)1038 report_next_chunk(void)
1039 {
1040 vifi_t vifi;
1041 struct uvif *v;
1042 struct rtentry *sr;
1043 int i, n = 0, min = 20000;
1044 static int start_rt;
1045
1046 if (nroutes <= 0)
1047 return (0);
1048
1049 /*
1050 * find this round's starting route.
1051 */
1052 for (sr = rt_end, i = start_rt; --i >= 0; ) {
1053 sr = sr->rt_prev;
1054 if (sr == RT_ADDR)
1055 sr = rt_end;
1056 }
1057
1058 /*
1059 * send one chunk of routes starting at this round's start to
1060 * all our neighbors.
1061 */
1062 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
1063 if ((v->uv_neighbors != NULL)
1064 #ifdef NOTYET
1065 && !(v->uv_flags & VIFF_LEAF)
1066 #endif
1067 ) {
1068 n = report_chunk(sr, vifi,
1069 (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr
1070 : dvmrp_group);
1071 if (n < min)
1072 min = n;
1073 }
1074 }
1075 if (min == 20000)
1076 min = 0; /* Neighborless router didn't send any routes */
1077
1078 n = min;
1079 logit(LOG_INFO, 0, "update %d starting at %d of %d",
1080 n, (nroutes - start_rt), nroutes);
1081
1082 start_rt = (start_rt + n) % nroutes;
1083 return (n);
1084 }
1085
1086
1087 /*
1088 * Print the contents of the routing table on file 'fp'.
1089 */
1090 void
dump_routes(FILE * fp)1091 dump_routes(FILE *fp)
1092 {
1093 struct rtentry *r;
1094 vifi_t i;
1095
1096
1097 fprintf(fp,
1098 "Multicast Routing Table (%u %s)\n%s\n",
1099 nroutes, (nroutes == 1) ? "entry" : "entries",
1100 " Origin-Subnet From-Gateway Metric Tmr In-Vif Out-Vifs");
1101
1102 for (r = routing_table; r != NULL; r = r->rt_next) {
1103
1104 fprintf(fp, " %-18s %-15s ",
1105 inet_fmts(r->rt_origin, r->rt_originmask),
1106 (r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway));
1107
1108 fprintf(fp, (r->rt_metric == UNREACHABLE) ? " NR " : "%4u ",
1109 r->rt_metric);
1110
1111 fprintf(fp, " %3u %3u ", r->rt_timer, r->rt_parent);
1112
1113 for (i = 0; i < numvifs; ++i) {
1114 if (VIFM_ISSET(i, r->rt_children)) {
1115 fprintf(fp, " %u%c",
1116 i, VIFM_ISSET(i, r->rt_leaves) ? '*' : ' ');
1117 }
1118 }
1119 fprintf(fp, "\n");
1120 }
1121 fprintf(fp, "\n");
1122 }
1123
1124 struct rtentry *
determine_route(u_int32_t src)1125 determine_route(u_int32_t src)
1126 {
1127 struct rtentry *rt;
1128
1129 for (rt = routing_table; rt != NULL; rt = rt->rt_next) {
1130 if (rt->rt_origin == (src & rt->rt_originmask))
1131 break;
1132 }
1133 return rt;
1134 }
1135