1 /* $NetBSD: table.c,v 1.28 2018/02/06 09:33:07 mrg Exp $ */
2
3 /*
4 * Copyright (c) 1983, 1988, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgment:
17 * This product includes software developed by the University of
18 * California, Berkeley and its contributors.
19 * 4. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 #include "defs.h"
37
38 #ifdef __NetBSD__
39 __RCSID("$NetBSD: table.c,v 1.28 2018/02/06 09:33:07 mrg Exp $");
40 #elif defined(__FreeBSD__)
41 __RCSID("$FreeBSD$");
42 #else
43 __RCSID("Revision: 2.27 ");
44 #ident "Revision: 2.27 "
45 #endif
46
47 static struct rt_spare *rts_better(struct rt_entry *);
48 static struct rt_spare rts_empty = {0,0,0,HOPCNT_INFINITY,0,0,0};
49 static void set_need_flash(void);
50 #ifdef _HAVE_SIN_LEN
51 static void masktrim(struct sockaddr_in *ap);
52 #else
53 static void masktrim(struct sockaddr_in_new *ap);
54 #endif
55
56
57 struct radix_node_head *rhead; /* root of the radix tree */
58
59 int need_flash = 1; /* flash update needed
60 * start =1 to suppress the 1st
61 */
62
63 struct timeval age_timer; /* next check of old routes */
64 struct timeval need_kern = { /* need to update kernel table */
65 EPOCH+MIN_WAITTIME-1, 0
66 };
67
68 int stopint;
69
70 int total_routes;
71
72 /* zap any old routes through this gateway */
73 naddr age_bad_gate;
74
75
76 /* It is desirable to "aggregate" routes, to combine differing routes of
77 * the same metric and next hop into a common route with a smaller netmask
78 * or to suppress redundant routes, routes that add no information to
79 * routes with smaller netmasks.
80 *
81 * A route is redundant if and only if any and all routes with smaller
82 * but matching netmasks and nets are the same. Since routes are
83 * kept sorted in the radix tree, redundant routes always come second.
84 *
85 * There are two kinds of aggregations. First, two routes of the same bit
86 * mask and differing only in the least significant bit of the network
87 * number can be combined into a single route with a coarser mask.
88 *
89 * Second, a route can be suppressed in favor of another route with a more
90 * coarse mask provided no incompatible routes with intermediate masks
91 * are present. The second kind of aggregation involves suppressing routes.
92 * A route must not be suppressed if an incompatible route exists with
93 * an intermediate mask, since the suppressed route would be covered
94 * by the intermediate.
95 *
96 * This code relies on the radix tree walk encountering routes
97 * sorted first by address, with the smallest address first.
98 */
99
100 struct ag_info ag_slots[NUM_AG_SLOTS], *ag_avail, *ag_corsest, *ag_finest;
101
102 /* #define DEBUG_AG */
103 #ifdef DEBUG_AG
104 #define CHECK_AG() {int acnt = 0; struct ag_info *cag; \
105 for (cag = ag_avail; cag != 0; cag = cag->ag_fine) \
106 acnt++; \
107 for (cag = ag_corsest; cag != 0; cag = cag->ag_fine) \
108 acnt++; \
109 if (acnt != NUM_AG_SLOTS) { \
110 (void)fflush(stderr); \
111 abort(); \
112 } \
113 }
114 #else
115 #define CHECK_AG()
116 #endif
117
118
119 /* Output the contents of an aggregation table slot.
120 * This function must always be immediately followed with the deletion
121 * of the target slot.
122 */
123 static void
ag_out(struct ag_info * ag,void (* out)(struct ag_info *))124 ag_out(struct ag_info *ag,
125 void (*out)(struct ag_info *))
126 {
127 struct ag_info *ag_cors;
128 naddr bit;
129
130
131 /* Forget it if this route should not be output for split-horizon. */
132 if (ag->ag_state & AGS_SPLIT_HZ)
133 return;
134
135 /* If we output both the even and odd twins, then the immediate parent,
136 * if it is present, is redundant, unless the parent manages to
137 * aggregate into something coarser.
138 * On successive calls, this code detects the even and odd twins,
139 * and marks the parent.
140 *
141 * Note that the order in which the radix tree code emits routes
142 * ensures that the twins are seen before the parent is emitted.
143 */
144 ag_cors = ag->ag_cors;
145 if (ag_cors != 0
146 && ag_cors->ag_mask == ag->ag_mask<<1
147 && ag_cors->ag_dst_h == (ag->ag_dst_h & ag_cors->ag_mask)) {
148 ag_cors->ag_state |= ((ag_cors->ag_dst_h == ag->ag_dst_h)
149 ? AGS_REDUN0
150 : AGS_REDUN1);
151 }
152
153 /* Skip it if this route is itself redundant.
154 *
155 * It is ok to change the contents of the slot here, since it is
156 * always deleted next.
157 */
158 if (ag->ag_state & AGS_REDUN0) {
159 if (ag->ag_state & AGS_REDUN1)
160 return; /* quit if fully redundant */
161 /* make it finer if it is half-redundant */
162 bit = (-ag->ag_mask) >> 1;
163 ag->ag_dst_h |= bit;
164 ag->ag_mask |= bit;
165
166 } else if (ag->ag_state & AGS_REDUN1) {
167 /* make it finer if it is half-redundant */
168 bit = (-ag->ag_mask) >> 1;
169 ag->ag_mask |= bit;
170 }
171 out(ag);
172 }
173
174
175 static void
ag_del(struct ag_info * ag)176 ag_del(struct ag_info *ag)
177 {
178 CHECK_AG();
179
180 if (ag->ag_cors == 0)
181 ag_corsest = ag->ag_fine;
182 else
183 ag->ag_cors->ag_fine = ag->ag_fine;
184
185 if (ag->ag_fine == 0)
186 ag_finest = ag->ag_cors;
187 else
188 ag->ag_fine->ag_cors = ag->ag_cors;
189
190 ag->ag_fine = ag_avail;
191 ag_avail = ag;
192
193 CHECK_AG();
194 }
195
196
197 /* Flush routes waiting for aggregation.
198 * This must not suppress a route unless it is known that among all
199 * routes with coarser masks that match it, the one with the longest
200 * mask is appropriate. This is ensured by scanning the routes
201 * in lexical order, and with the most restrictive mask first
202 * among routes to the same destination.
203 */
204 void
ag_flush(naddr lim_dst_h,naddr lim_mask,void (* out)(struct ag_info *))205 ag_flush(naddr lim_dst_h, /* flush routes to here */
206 naddr lim_mask, /* matching this mask */
207 void (*out)(struct ag_info *))
208 {
209 struct ag_info *ag, *ag_cors;
210 naddr dst_h;
211
212
213 for (ag = ag_finest;
214 ag != 0 && ag->ag_mask >= lim_mask;
215 ag = ag_cors) {
216 ag_cors = ag->ag_cors;
217
218 /* work on only the specified routes */
219 dst_h = ag->ag_dst_h;
220 if ((dst_h & lim_mask) != lim_dst_h)
221 continue;
222
223 if (!(ag->ag_state & AGS_SUPPRESS))
224 ag_out(ag, out);
225
226 else for ( ; ; ag_cors = ag_cors->ag_cors) {
227 /* Look for a route that can suppress the
228 * current route */
229 if (ag_cors == 0) {
230 /* failed, so output it and look for
231 * another route to work on
232 */
233 ag_out(ag, out);
234 break;
235 }
236
237 if ((dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h) {
238 /* We found a route with a coarser mask that
239 * aggregates the current target.
240 *
241 * If it has a different next hop, it
242 * cannot replace the target, so output
243 * the target.
244 */
245 if (ag->ag_gate != ag_cors->ag_gate
246 && !(ag->ag_state & AGS_FINE_GATE)
247 && !(ag_cors->ag_state & AGS_CORS_GATE)) {
248 ag_out(ag, out);
249 break;
250 }
251
252 /* If the coarse route has a good enough
253 * metric, it suppresses the target.
254 * If the suppressed target was redundant,
255 * then mark the suppressor redundant.
256 */
257 if (ag_cors->ag_pref <= ag->ag_pref) {
258 if (AG_IS_REDUN(ag->ag_state)
259 && ag_cors->ag_mask==ag->ag_mask<<1) {
260 if (ag_cors->ag_dst_h == dst_h)
261 ag_cors->ag_state |= AGS_REDUN0;
262 else
263 ag_cors->ag_state |= AGS_REDUN1;
264 }
265 if (ag->ag_tag != ag_cors->ag_tag)
266 ag_cors->ag_tag = 0;
267 if (ag->ag_nhop != ag_cors->ag_nhop)
268 ag_cors->ag_nhop = 0;
269 break;
270 }
271 }
272 }
273
274 /* That route has either been output or suppressed */
275 ag_cors = ag->ag_cors;
276 ag_del(ag);
277 }
278
279 CHECK_AG();
280 }
281
282
283 /* Try to aggregate a route with previous routes.
284 */
285 void
ag_check(naddr dst,naddr mask,naddr gate,naddr nhop,char metric,char pref,u_int new_seqno,u_short tag,u_short state,void (* out)(struct ag_info *))286 ag_check(naddr dst,
287 naddr mask,
288 naddr gate,
289 naddr nhop,
290 char metric,
291 char pref,
292 u_int new_seqno,
293 u_short tag,
294 u_short state,
295 void (*out)(struct ag_info *)) /* output using this */
296 {
297 struct ag_info *ag, *nag, *ag_cors;
298 naddr xaddr;
299 int x;
300
301 dst = ntohl(dst);
302
303 /* Punt non-contiguous subnet masks.
304 *
305 * (X & -X) contains a single bit if and only if X is a power of 2.
306 * (X + (X & -X)) == 0 if and only if X is a power of 2.
307 */
308 if ((mask & -mask) + mask != 0) {
309 struct ag_info nc_ag;
310
311 nc_ag.ag_dst_h = dst;
312 nc_ag.ag_mask = mask;
313 nc_ag.ag_gate = gate;
314 nc_ag.ag_nhop = nhop;
315 nc_ag.ag_metric = metric;
316 nc_ag.ag_pref = pref;
317 nc_ag.ag_tag = tag;
318 nc_ag.ag_state = state;
319 nc_ag.ag_seqno = new_seqno;
320 out(&nc_ag);
321 return;
322 }
323
324 /* Search for the right slot in the aggregation table.
325 */
326 ag_cors = 0;
327 ag = ag_corsest;
328 while (ag != 0) {
329 if (ag->ag_mask >= mask)
330 break;
331
332 /* Suppress old routes (i.e. combine with compatible routes
333 * with coarser masks) as we look for the right slot in the
334 * aggregation table for the new route.
335 * A route to an address less than the current destination
336 * will not be affected by the current route or any route
337 * seen hereafter. That means it is safe to suppress it.
338 * This check keeps poor routes (e.g. with large hop counts)
339 * from preventing suppression of finer routes.
340 */
341 if (ag_cors != 0
342 && ag->ag_dst_h < dst
343 && (ag->ag_state & AGS_SUPPRESS)
344 && ag_cors->ag_pref <= ag->ag_pref
345 && (ag->ag_dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h
346 && (ag_cors->ag_gate == ag->ag_gate
347 || (ag->ag_state & AGS_FINE_GATE)
348 || (ag_cors->ag_state & AGS_CORS_GATE))) {
349 /* If the suppressed target was redundant,
350 * then mark the suppressor redundant.
351 */
352 if (AG_IS_REDUN(ag->ag_state)
353 && ag_cors->ag_mask == ag->ag_mask<<1) {
354 if (ag_cors->ag_dst_h == dst)
355 ag_cors->ag_state |= AGS_REDUN0;
356 else
357 ag_cors->ag_state |= AGS_REDUN1;
358 }
359 if (ag->ag_tag != ag_cors->ag_tag)
360 ag_cors->ag_tag = 0;
361 if (ag->ag_nhop != ag_cors->ag_nhop)
362 ag_cors->ag_nhop = 0;
363 ag_del(ag);
364 CHECK_AG();
365 } else {
366 ag_cors = ag;
367 }
368 ag = ag_cors->ag_fine;
369 }
370
371 /* If we find the even/odd twin of the new route, and if the
372 * masks and so forth are equal, we can aggregate them.
373 * We can probably promote one of the pair.
374 *
375 * Since the routes are encountered in lexical order,
376 * the new route must be odd. However, the second or later
377 * times around this loop, it could be the even twin promoted
378 * from the even/odd pair of twins of the finer route.
379 */
380 while (ag != 0
381 && ag->ag_mask == mask
382 && ((ag->ag_dst_h ^ dst) & (mask<<1)) == 0) {
383
384 /* Here we know the target route and the route in the current
385 * slot have the same netmasks and differ by at most the
386 * last bit. They are either for the same destination, or
387 * for an even/odd pair of destinations.
388 */
389 if (ag->ag_dst_h == dst) {
390 /* We have two routes to the same destination.
391 * Routes are encountered in lexical order, so a
392 * route is never promoted until the parent route is
393 * already present. So we know that the new route is
394 * a promoted (or aggregated) pair and the route
395 * already in the slot is the explicit route.
396 *
397 * Prefer the best route if their metrics differ,
398 * or the aggregated one if not, following a sort
399 * of longest-match rule.
400 */
401 if (pref <= ag->ag_pref) {
402 ag->ag_gate = gate;
403 ag->ag_nhop = nhop;
404 ag->ag_tag = tag;
405 ag->ag_metric = metric;
406 ag->ag_pref = pref;
407 if (ag->ag_seqno < new_seqno)
408 ag->ag_seqno = new_seqno;
409 x = ag->ag_state;
410 ag->ag_state = state;
411 state = x;
412 }
413
414 /* Some bits are set if they are set on either route,
415 * except when the route is for an interface.
416 */
417 if (!(ag->ag_state & AGS_IF))
418 ag->ag_state |= (state & (AGS_AGGREGATE_EITHER
419 | AGS_REDUN0
420 | AGS_REDUN1));
421 return;
422 }
423
424 /* If one of the routes can be promoted and the other can
425 * be suppressed, it may be possible to combine them or
426 * worthwhile to promote one.
427 *
428 * Any route that can be promoted is always
429 * marked to be eligible to be suppressed.
430 */
431 if (!((state & AGS_AGGREGATE)
432 && (ag->ag_state & AGS_SUPPRESS))
433 && !((ag->ag_state & AGS_AGGREGATE)
434 && (state & AGS_SUPPRESS)))
435 break;
436
437 /* A pair of even/odd twin routes can be combined
438 * if either is redundant, or if they are via the
439 * same gateway and have the same metric.
440 */
441 if (AG_IS_REDUN(ag->ag_state)
442 || AG_IS_REDUN(state)
443 || (ag->ag_gate == gate
444 && ag->ag_pref == pref
445 && (state & ag->ag_state & AGS_AGGREGATE) != 0)) {
446
447 /* We have both the even and odd pairs.
448 * Since the routes are encountered in order,
449 * the route in the slot must be the even twin.
450 *
451 * Combine and promote (aggregate) the pair of routes.
452 */
453 if (new_seqno < ag->ag_seqno)
454 new_seqno = ag->ag_seqno;
455 if (!AG_IS_REDUN(state))
456 state &= ~AGS_REDUN1;
457 if (AG_IS_REDUN(ag->ag_state))
458 state |= AGS_REDUN0;
459 else
460 state &= ~AGS_REDUN0;
461 state |= (ag->ag_state & AGS_AGGREGATE_EITHER);
462 if (ag->ag_tag != tag)
463 tag = 0;
464 if (ag->ag_nhop != nhop)
465 nhop = 0;
466
467 /* Get rid of the even twin that was already
468 * in the slot.
469 */
470 ag_del(ag);
471
472 } else if (ag->ag_pref >= pref
473 && (ag->ag_state & AGS_AGGREGATE)) {
474 /* If we cannot combine the pair, maybe the route
475 * with the worse metric can be promoted.
476 *
477 * Promote the old, even twin, by giving its slot
478 * in the table to the new, odd twin.
479 */
480 ag->ag_dst_h = dst;
481
482 xaddr = ag->ag_gate;
483 ag->ag_gate = gate;
484 gate = xaddr;
485
486 xaddr = ag->ag_nhop;
487 ag->ag_nhop = nhop;
488 nhop = xaddr;
489
490 x = ag->ag_tag;
491 ag->ag_tag = tag;
492 tag = x;
493
494 /* The promoted route is even-redundant only if the
495 * even twin was fully redundant. It is not
496 * odd-redundant because the odd-twin will still be
497 * in the table.
498 */
499 x = ag->ag_state;
500 if (!AG_IS_REDUN(x))
501 x &= ~AGS_REDUN0;
502 x &= ~AGS_REDUN1;
503 ag->ag_state = state;
504 state = x;
505
506 x = ag->ag_metric;
507 ag->ag_metric = metric;
508 metric = x;
509
510 x = ag->ag_pref;
511 ag->ag_pref = pref;
512 pref = x;
513
514 /* take the newest sequence number */
515 if (new_seqno <= ag->ag_seqno)
516 new_seqno = ag->ag_seqno;
517 else
518 ag->ag_seqno = new_seqno;
519
520 } else {
521 if (!(state & AGS_AGGREGATE))
522 break; /* cannot promote either twin */
523
524 /* Promote the new, odd twin by shaving its
525 * mask and address.
526 * The promoted route is odd-redundant only if the
527 * odd twin was fully redundant. It is not
528 * even-redundant because the even twin is still in
529 * the table.
530 */
531 if (!AG_IS_REDUN(state))
532 state &= ~AGS_REDUN1;
533 state &= ~AGS_REDUN0;
534 if (new_seqno < ag->ag_seqno)
535 new_seqno = ag->ag_seqno;
536 else
537 ag->ag_seqno = new_seqno;
538 }
539
540 mask <<= 1;
541 dst &= mask;
542
543 if (ag_cors == 0) {
544 ag = ag_corsest;
545 break;
546 }
547 ag = ag_cors;
548 ag_cors = ag->ag_cors;
549 }
550
551 /* When we can no longer promote and combine routes,
552 * flush the old route in the target slot. Also flush
553 * any finer routes that we know will never be aggregated by
554 * the new route.
555 *
556 * In case we moved toward coarser masks,
557 * get back where we belong
558 */
559 if (ag != 0
560 && ag->ag_mask < mask) {
561 ag_cors = ag;
562 ag = ag->ag_fine;
563 }
564
565 /* Empty the target slot
566 */
567 if (ag != 0 && ag->ag_mask == mask) {
568 ag_flush(ag->ag_dst_h, ag->ag_mask, out);
569 ag = (ag_cors == 0) ? ag_corsest : ag_cors->ag_fine;
570 }
571
572 #ifdef DEBUG_AG
573 (void)fflush(stderr);
574 if (ag == 0 && ag_cors != ag_finest)
575 abort();
576 if (ag_cors == 0 && ag != ag_corsest)
577 abort();
578 if (ag != 0 && ag->ag_cors != ag_cors)
579 abort();
580 if (ag_cors != 0 && ag_cors->ag_fine != ag)
581 abort();
582 CHECK_AG();
583 #endif
584
585 /* Save the new route on the end of the table.
586 */
587 nag = ag_avail;
588 ag_avail = nag->ag_fine;
589
590 nag->ag_dst_h = dst;
591 nag->ag_mask = mask;
592 nag->ag_gate = gate;
593 nag->ag_nhop = nhop;
594 nag->ag_metric = metric;
595 nag->ag_pref = pref;
596 nag->ag_tag = tag;
597 nag->ag_state = state;
598 nag->ag_seqno = new_seqno;
599
600 nag->ag_fine = ag;
601 if (ag != 0)
602 ag->ag_cors = nag;
603 else
604 ag_finest = nag;
605 nag->ag_cors = ag_cors;
606 if (ag_cors == 0)
607 ag_corsest = nag;
608 else
609 ag_cors->ag_fine = nag;
610 CHECK_AG();
611 }
612
613
614 static const char *
rtm_type_name(u_char type)615 rtm_type_name(u_char type)
616 {
617 static const char *rtm_types[] = {
618 "RTM_ADD",
619 "RTM_DELETE",
620 "RTM_CHANGE",
621 "RTM_GET",
622 "RTM_LOSING",
623 "RTM_REDIRECT",
624 "RTM_MISS",
625 "RTM_LOCK",
626 "RTM_OLDADD",
627 "RTM_OLDDEL",
628 "RTM_RESOLVE",
629 "RTM_NEWADDR",
630 "RTM_DELADDR",
631 #ifdef RTM_OIFINFO
632 "RTM_OIFINFO",
633 #endif
634 "RTM_IFINFO",
635 "RTM_NEWMADDR",
636 "RTM_DELMADDR"
637 };
638 #define NEW_RTM_PAT "RTM type %#x"
639 static char name0[sizeof(NEW_RTM_PAT)+2];
640
641
642 if (type > sizeof(rtm_types)/sizeof(rtm_types[0])
643 || type == 0) {
644 snprintf(name0, sizeof(name0), NEW_RTM_PAT, type);
645 return name0;
646 } else {
647 return rtm_types[type-1];
648 }
649 #undef NEW_RTM_PAT
650 }
651
652
653 /* Trim a mask in a sockaddr
654 * Produce a length of 0 for an address of 0.
655 * Otherwise produce the index of the first zero byte.
656 */
657 void
658 #ifdef _HAVE_SIN_LEN
masktrim(struct sockaddr_in * ap)659 masktrim(struct sockaddr_in *ap)
660 #else
661 masktrim(struct sockaddr_in_new *ap)
662 #endif
663 {
664 char *cp;
665
666 if (ap->sin_addr.s_addr == 0) {
667 ap->sin_len = 0;
668 return;
669 }
670 cp = (char *)&ap->sin_addr.s_addr + sizeof(ap->sin_addr.s_addr);
671 while (*--cp == 0)
672 continue;
673 ap->sin_len = cp - (char*)ap + 1;
674 }
675
676
677 /* Tell the kernel to add, delete or change a route
678 */
679 static void
rtioctl(int action,naddr dst,naddr gate,naddr mask,int metric,int flags)680 rtioctl(int action, /* RTM_DELETE, etc */
681 naddr dst,
682 naddr gate,
683 naddr mask,
684 int metric,
685 int flags)
686 {
687 struct {
688 struct rt_msghdr w_rtm;
689 struct sockaddr_in w_dst;
690 struct sockaddr_in w_gate;
691 #ifdef _HAVE_SA_LEN
692 struct sockaddr_in w_mask;
693 #else
694 struct sockaddr_in_new w_mask;
695 #endif
696 } w;
697 long cc;
698 # define PAT " %-10s %s metric=%d flags=%#x"
699 # define ARGS rtm_type_name(action), rtname(dst,mask,gate), metric, flags
700
701 again:
702 memset(&w, 0, sizeof(w));
703 w.w_rtm.rtm_msglen = sizeof(w);
704 w.w_rtm.rtm_version = RTM_VERSION;
705 w.w_rtm.rtm_type = action;
706 w.w_rtm.rtm_flags = flags;
707 w.w_rtm.rtm_seq = ++rt_sock_seqno;
708 w.w_rtm.rtm_addrs = RTA_DST|RTA_GATEWAY;
709 if (metric != 0 || action == RTM_CHANGE) {
710 w.w_rtm.rtm_rmx.rmx_hopcount = metric;
711 w.w_rtm.rtm_inits |= RTV_HOPCOUNT;
712 }
713 w.w_dst.sin_family = AF_INET;
714 w.w_dst.sin_addr.s_addr = dst;
715 w.w_gate.sin_family = AF_INET;
716 w.w_gate.sin_addr.s_addr = gate;
717 #ifdef _HAVE_SA_LEN
718 w.w_dst.sin_len = sizeof(w.w_dst);
719 w.w_gate.sin_len = sizeof(w.w_gate);
720 #endif
721 if (mask == HOST_MASK) {
722 w.w_rtm.rtm_flags |= RTF_HOST;
723 w.w_rtm.rtm_msglen -= sizeof(w.w_mask);
724 } else {
725 w.w_rtm.rtm_addrs |= RTA_NETMASK;
726 w.w_mask.sin_addr.s_addr = htonl(mask);
727 #ifdef _HAVE_SA_LEN
728 masktrim(&w.w_mask);
729 if (w.w_mask.sin_len == 0)
730 w.w_mask.sin_len = sizeof(long);
731 w.w_rtm.rtm_msglen -= (sizeof(w.w_mask) - w.w_mask.sin_len);
732 #endif
733 }
734
735 #ifndef NO_INSTALL
736 cc = write(rt_sock, &w, w.w_rtm.rtm_msglen);
737 if (cc < 0) {
738 if (errno == ESRCH
739 && (action == RTM_CHANGE || action == RTM_DELETE)) {
740 trace_act("route disappeared before" PAT, ARGS);
741 if (action == RTM_CHANGE) {
742 action = RTM_ADD;
743 goto again;
744 }
745 return;
746 }
747 msglog("write(rt_sock)" PAT ": %s", ARGS, strerror(errno));
748 return;
749 } else if (cc != w.w_rtm.rtm_msglen) {
750 msglog("write(rt_sock) wrote %ld instead of %d for" PAT,
751 cc, w.w_rtm.rtm_msglen, ARGS);
752 return;
753 }
754 #endif
755 if (TRACEKERNEL)
756 trace_misc("write kernel" PAT, ARGS);
757 #undef PAT
758 #undef ARGS
759 }
760
761
762 #define KHASH_SIZE 71 /* should be prime */
763 #define KHASH(a,m) khash_bins[((a) ^ (m)) % KHASH_SIZE]
764 static struct khash {
765 struct khash *k_next;
766 naddr k_dst;
767 naddr k_mask;
768 naddr k_gate;
769 short k_metric;
770 u_short k_state;
771 #define KS_NEW 0x001
772 #define KS_DELETE 0x002 /* need to delete the route */
773 #define KS_ADD 0x004 /* add to the kernel */
774 #define KS_CHANGE 0x008 /* tell kernel to change the route */
775 #define KS_DEL_ADD 0x010 /* delete & add to change the kernel */
776 #define KS_STATIC 0x020 /* Static flag in kernel */
777 #define KS_GATEWAY 0x040 /* G flag in kernel */
778 #define KS_DYNAMIC 0x080 /* result of redirect */
779 #define KS_DELETED 0x100 /* already deleted from kernel */
780 #define KS_CHECK 0x200
781 #define KS_LOCAL 0x400
782 time_t k_keep;
783 #define K_KEEP_LIM 30
784 time_t k_redirect_time; /* when redirected route 1st seen */
785 } *khash_bins[KHASH_SIZE];
786
787
788 static struct khash*
kern_find(naddr dst,naddr mask,struct khash *** ppk)789 kern_find(naddr dst, naddr mask, struct khash ***ppk)
790 {
791 struct khash *k, **pk;
792
793 for (pk = &KHASH(dst,mask); (k = *pk) != 0; pk = &k->k_next) {
794 if (k->k_dst == dst && k->k_mask == mask)
795 break;
796 }
797 if (ppk != 0)
798 *ppk = pk;
799 return k;
800 }
801
802
803 static struct khash*
kern_add(naddr dst,naddr mask)804 kern_add(naddr dst, naddr mask)
805 {
806 struct khash *k, **pk;
807
808 k = kern_find(dst, mask, &pk);
809 if (k != 0)
810 return k;
811
812 k = (struct khash *)rtmalloc(sizeof(*k), "kern_add");
813
814 memset(k, 0, sizeof(*k));
815 k->k_dst = dst;
816 k->k_mask = mask;
817 k->k_state = KS_NEW;
818 k->k_keep = now.tv_sec;
819 *pk = k;
820
821 return k;
822 }
823
824
825 /* If a kernel route has a non-zero metric, check that it is still in the
826 * daemon table, and not deleted by interfaces coming and going.
827 */
828 static void
kern_check_static(struct khash * k,struct interface * ifp)829 kern_check_static(struct khash *k,
830 struct interface *ifp)
831 {
832 struct rt_entry *rt;
833 struct rt_spare new;
834
835 if (k->k_metric == 0)
836 return;
837
838 memset(&new, 0, sizeof(new));
839 new.rts_ifp = ifp;
840 new.rts_gate = k->k_gate;
841 new.rts_router = (ifp != 0) ? ifp->int_addr : loopaddr;
842 new.rts_metric = k->k_metric;
843 new.rts_time = now.tv_sec;
844
845 rt = rtget(k->k_dst, k->k_mask);
846 if (rt != 0) {
847 if (!(rt->rt_state & RS_STATIC))
848 rtchange(rt, rt->rt_state | RS_STATIC, &new, 0);
849 } else {
850 rtadd(k->k_dst, k->k_mask, RS_STATIC, &new);
851 }
852 }
853
854
855 /* operate on a kernel entry
856 */
857 static void
kern_ioctl(struct khash * k,int action,int flags)858 kern_ioctl(struct khash *k,
859 int action, /* RTM_DELETE, etc */
860 int flags)
861
862 {
863 switch (action) {
864 case RTM_DELETE:
865 k->k_state &= ~KS_DYNAMIC;
866 if (k->k_state & KS_DELETED)
867 return;
868 k->k_state |= KS_DELETED;
869 break;
870 case RTM_ADD:
871 k->k_state &= ~KS_DELETED;
872 break;
873 case RTM_CHANGE:
874 if (k->k_state & KS_DELETED) {
875 action = RTM_ADD;
876 k->k_state &= ~KS_DELETED;
877 }
878 break;
879 }
880
881 rtioctl(action, k->k_dst, k->k_gate, k->k_mask, k->k_metric, flags);
882 }
883
884
885 /* add a route the kernel told us
886 */
887 static void
rtm_add(struct rt_msghdr * rtm,struct rt_addrinfo * info,time_t keep)888 rtm_add(struct rt_msghdr *rtm,
889 struct rt_addrinfo *info,
890 time_t keep)
891 {
892 struct khash *k;
893 struct interface *ifp;
894 naddr mask;
895
896
897 if (rtm->rtm_flags & RTF_HOST) {
898 mask = HOST_MASK;
899 } else if (INFO_MASK(info) != 0) {
900 mask = ntohl(S_ADDR(INFO_MASK(info)));
901 } else {
902 msglog("ignore %s without mask", rtm_type_name(rtm->rtm_type));
903 return;
904 }
905
906 k = kern_add(S_ADDR(INFO_DST(info)), mask);
907 if (k->k_state & KS_NEW)
908 k->k_keep = now.tv_sec+keep;
909 if (INFO_GATE(info) == 0) {
910 trace_act("note %s without gateway",
911 rtm_type_name(rtm->rtm_type));
912 k->k_metric = HOPCNT_INFINITY;
913 } else if (INFO_GATE(info)->sa_family != AF_INET) {
914 trace_act("note %s with gateway AF=%d",
915 rtm_type_name(rtm->rtm_type),
916 INFO_GATE(info)->sa_family);
917 k->k_metric = HOPCNT_INFINITY;
918 } else {
919 k->k_gate = S_ADDR(INFO_GATE(info));
920 k->k_metric = rtm->rtm_rmx.rmx_hopcount;
921 if (k->k_metric < 0)
922 k->k_metric = 0;
923 else if (k->k_metric > HOPCNT_INFINITY-1)
924 k->k_metric = HOPCNT_INFINITY-1;
925 }
926 k->k_state &= ~(KS_DELETE | KS_ADD | KS_CHANGE | KS_DEL_ADD
927 | KS_DELETED | KS_GATEWAY | KS_STATIC
928 | KS_NEW | KS_CHECK | KS_LOCAL);
929 if (rtm->rtm_flags & RTF_GATEWAY)
930 k->k_state |= KS_GATEWAY;
931 if (rtm->rtm_flags & RTF_STATIC)
932 k->k_state |= KS_STATIC;
933 if (rtm->rtm_flags & RTF_LOCAL)
934 k->k_state |= KS_LOCAL;
935
936 if (0 != (rtm->rtm_flags & (RTF_DYNAMIC | RTF_MODIFIED))) {
937 if (INFO_AUTHOR(info) != 0
938 && INFO_AUTHOR(info)->sa_family == AF_INET)
939 ifp = iflookup(S_ADDR(INFO_AUTHOR(info)));
940 else
941 ifp = 0;
942 if (supplier
943 && (ifp == 0 || !(ifp->int_state & IS_REDIRECT_OK))) {
944 /* Routers are not supposed to listen to redirects,
945 * so delete it if it came via an unknown interface
946 * or the interface does not have special permission.
947 */
948 k->k_state &= ~KS_DYNAMIC;
949 k->k_state |= KS_DELETE;
950 LIM_SEC(need_kern, 0);
951 trace_act("mark for deletion redirected %s --> %s"
952 " via %s",
953 addrname(k->k_dst, k->k_mask, 0),
954 naddr_ntoa(k->k_gate),
955 ifp ? ifp->int_name : "unknown interface");
956 } else {
957 k->k_state |= KS_DYNAMIC;
958 k->k_redirect_time = now.tv_sec;
959 trace_act("accept redirected %s --> %s via %s",
960 addrname(k->k_dst, k->k_mask, 0),
961 naddr_ntoa(k->k_gate),
962 ifp ? ifp->int_name : "unknown interface");
963 }
964 return;
965 }
966
967 /* If it is not a static route, quit until the next comparison
968 * between the kernel and daemon tables, when it will be deleted.
969 */
970 if (!(k->k_state & KS_STATIC) && !(k->k_state & KS_LOCAL)) {
971 k->k_state |= KS_DELETE;
972 LIM_SEC(need_kern, k->k_keep);
973 return;
974 }
975
976 /* Put static routes with real metrics into the daemon table so
977 * they can be advertised.
978 *
979 * Find the interface toward the gateway.
980 */
981 ifp = iflookup(k->k_gate);
982 if (ifp == 0)
983 msglog("static route %s --> %s impossibly lacks ifp",
984 addrname(S_ADDR(INFO_DST(info)), mask, 0),
985 naddr_ntoa(k->k_gate));
986
987 kern_check_static(k, ifp);
988 }
989
990
991 /* deal with packet loss
992 */
993 static void
rtm_lose(struct rt_msghdr * rtm,struct rt_addrinfo * info)994 rtm_lose(struct rt_msghdr *rtm,
995 struct rt_addrinfo *info)
996 {
997 if (INFO_GATE(info) == 0
998 || INFO_GATE(info)->sa_family != AF_INET) {
999 trace_act("ignore %s without gateway",
1000 rtm_type_name(rtm->rtm_type));
1001 return;
1002 }
1003
1004 if (rdisc_ok)
1005 rdisc_age(S_ADDR(INFO_GATE(info)));
1006 age(S_ADDR(INFO_GATE(info)));
1007 }
1008
1009
1010 /* Make the gateway slot of an info structure point to something
1011 * useful. If it is not already useful, but it specifies an interface,
1012 * then fill in the sockaddr_in provided and point it there.
1013 */
1014 static int
get_info_gate(const struct sockaddr ** sap,struct sockaddr_in * rsin)1015 get_info_gate(const struct sockaddr **sap,
1016 struct sockaddr_in *rsin)
1017 {
1018 const struct sockaddr_dl *sdl = (const struct sockaddr_dl *)*sap;
1019 struct interface *ifp;
1020
1021 if (sdl == 0)
1022 return 0;
1023 if ((sdl)->sdl_family == AF_INET)
1024 return 1;
1025 if ((sdl)->sdl_family != AF_LINK)
1026 return 0;
1027
1028 ifp = ifwithindex(sdl->sdl_index, 1);
1029 if (ifp == 0)
1030 return 0;
1031
1032 rsin->sin_addr.s_addr = ifp->int_addr;
1033 #ifdef _HAVE_SA_LEN
1034 rsin->sin_len = sizeof(*rsin);
1035 #endif
1036 rsin->sin_family = AF_INET;
1037 *sap = (const struct sockaddr*)rsin;
1038
1039 return 1;
1040 }
1041
1042
1043 /* Clean the kernel table by copying it to the daemon image.
1044 * Eventually the daemon will delete any extra routes.
1045 */
1046 void
flush_kern(void)1047 flush_kern(void)
1048 {
1049 static char *sysctl_buf;
1050 static size_t sysctl_buf_size = 0;
1051 size_t needed;
1052 int mib[6];
1053 char *next, *lim;
1054 struct rt_msghdr *rtm;
1055 struct sockaddr_in gate_sin;
1056 struct rt_addrinfo info;
1057 int i;
1058 struct khash *k;
1059
1060
1061 for (i = 0; i < KHASH_SIZE; i++) {
1062 for (k = khash_bins[i]; k != 0; k = k->k_next) {
1063 k->k_state |= KS_CHECK;
1064 }
1065 }
1066
1067 mib[0] = CTL_NET;
1068 mib[1] = PF_ROUTE;
1069 mib[2] = 0; /* protocol */
1070 mib[3] = 0; /* wildcard address family */
1071 mib[4] = NET_RT_DUMP;
1072 mib[5] = 0; /* no flags */
1073 for (;;) {
1074 if ((needed = sysctl_buf_size) != 0) {
1075 if (sysctl(mib, 6, sysctl_buf,&needed, 0, 0) >= 0)
1076 break;
1077 if (errno != ENOMEM && errno != EFAULT)
1078 BADERR(1,"flush_kern: sysctl(RT_DUMP)");
1079 free(sysctl_buf);
1080 needed = 0;
1081 }
1082 if (sysctl(mib, 6, 0, &needed, 0, 0) < 0)
1083 BADERR(1,"flush_kern: sysctl(RT_DUMP) estimate");
1084 /* Kludge around the habit of some systems, such as
1085 * BSD/OS 3.1, to not admit how many routes are in the
1086 * kernel, or at least to be quite wrong.
1087 */
1088 needed += 50*(sizeof(*rtm)+5*sizeof(struct sockaddr));
1089 sysctl_buf = rtmalloc(sysctl_buf_size = needed,
1090 "flush_kern sysctl(RT_DUMP)");
1091 }
1092
1093 lim = sysctl_buf + needed;
1094 for (next = sysctl_buf; next < lim; next += rtm->rtm_msglen) {
1095 rtm = (struct rt_msghdr *)next;
1096 if (rtm->rtm_msglen == 0) {
1097 msglog("zero length kernel route at "
1098 " %#lx in buffer %#lx before %#lx",
1099 (u_long)rtm, (u_long)sysctl_buf, (u_long)lim);
1100 break;
1101 }
1102
1103 rt_xaddrs(&info,
1104 (struct sockaddr *)(rtm+1),
1105 (struct sockaddr *)(next + rtm->rtm_msglen),
1106 rtm->rtm_addrs);
1107
1108 if (INFO_DST(&info) == 0
1109 || INFO_DST(&info)->sa_family != AF_INET)
1110 continue;
1111
1112 /* ignore cloned routes
1113 */
1114 #if defined(RTF_CLONED) && defined(__bsdi__)
1115 if (rtm->rtm_flags & RTF_CLONED)
1116 continue;
1117 #endif
1118 #if defined(RTF_WASCLONED) && defined(__FreeBSD__)
1119 if (rtm->rtm_flags & RTF_WASCLONED)
1120 continue;
1121 #endif
1122
1123
1124 /* ignore multicast addresses
1125 */
1126 if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info)))))
1127 continue;
1128
1129 if (!get_info_gate(&INFO_GATE(&info), &gate_sin))
1130 continue;
1131
1132 /* Note static routes and interface routes, and also
1133 * preload the image of the kernel table so that
1134 * we can later clean it, as well as avoid making
1135 * unneeded changes. Keep the old kernel routes for a
1136 * few seconds to allow a RIP or router-discovery
1137 * response to be heard.
1138 */
1139 rtm_add(rtm,&info,MIN_WAITTIME);
1140 }
1141
1142 for (i = 0; i < KHASH_SIZE; i++) {
1143 for (k = khash_bins[i]; k != 0; k = k->k_next) {
1144 if (k->k_state & KS_CHECK) {
1145 msglog("%s --> %s disappeared from kernel",
1146 addrname(k->k_dst, k->k_mask, 0),
1147 naddr_ntoa(k->k_gate));
1148 del_static(k->k_dst, k->k_mask, k->k_gate, 1);
1149 }
1150 }
1151 }
1152 }
1153
1154
1155 /* Listen to announcements from the kernel
1156 */
1157 void
read_rt(void)1158 read_rt(void)
1159 {
1160 long cc;
1161 struct interface *ifp;
1162 struct sockaddr_in gate_sin;
1163 naddr mask, gate;
1164 union {
1165 struct {
1166 struct rt_msghdr rtm;
1167 struct sockaddr addrs[RTAX_MAX];
1168 } r;
1169 struct if_msghdr ifm;
1170 } m;
1171 char str[100], *strp;
1172 struct rt_addrinfo info;
1173
1174
1175 for (;;) {
1176 cc = read(rt_sock, &m, sizeof(m));
1177 if (cc <= 0) {
1178 if (cc < 0 && errno != EWOULDBLOCK)
1179 LOGERR("read(rt_sock)");
1180 return;
1181 }
1182
1183 if (m.r.rtm.rtm_version != RTM_VERSION) {
1184 msglog("bogus routing message version %d",
1185 m.r.rtm.rtm_version);
1186 continue;
1187 }
1188
1189 /* Ignore our own results.
1190 */
1191 if (m.r.rtm.rtm_type <= RTM_CHANGE
1192 && m.r.rtm.rtm_pid == mypid) {
1193 static int complained = 0;
1194 if (!complained) {
1195 msglog("receiving our own change messages");
1196 complained = 1;
1197 }
1198 continue;
1199 }
1200
1201 if (m.r.rtm.rtm_type == RTM_IFINFO
1202 || m.r.rtm.rtm_type == RTM_NEWADDR
1203 || m.r.rtm.rtm_type == RTM_DELADDR) {
1204 ifp = ifwithindex(m.ifm.ifm_index,
1205 m.r.rtm.rtm_type != RTM_DELADDR);
1206 if (ifp == 0)
1207 trace_act("note %s with flags %#x"
1208 " for unknown interface index #%d",
1209 rtm_type_name(m.r.rtm.rtm_type),
1210 m.ifm.ifm_flags,
1211 m.ifm.ifm_index);
1212 else
1213 trace_act("note %s with flags %#x for %s",
1214 rtm_type_name(m.r.rtm.rtm_type),
1215 m.ifm.ifm_flags,
1216 ifp->int_name);
1217
1218 /* After being informed of a change to an interface,
1219 * check them all now if the check would otherwise
1220 * be a long time from now, if the interface is
1221 * not known, or if the interface has been turned
1222 * off or on.
1223 */
1224 if (ifinit_timer.tv_sec-now.tv_sec>=CHECK_BAD_INTERVAL
1225 || ifp == 0
1226 || ((ifp->int_if_flags ^ m.ifm.ifm_flags)
1227 & IFF_UP) != 0)
1228 ifinit_timer.tv_sec = now.tv_sec;
1229 continue;
1230 }
1231 #ifdef RTM_OIFINFO
1232 if (m.r.rtm.rtm_type == RTM_OIFINFO)
1233 continue; /* ignore compat message */
1234 #endif
1235
1236 strlcpy(str, rtm_type_name(m.r.rtm.rtm_type), sizeof(str));
1237 strp = &str[strlen(str)];
1238 if (m.r.rtm.rtm_type <= RTM_CHANGE) {
1239 snprintf(strp, str + sizeof(str) - strp,
1240 " from pid %d",m.r.rtm.rtm_pid);
1241 strp += strlen(strp);
1242 }
1243
1244 rt_xaddrs(&info, m.r.addrs, &m.r.addrs[RTAX_MAX],
1245 m.r.rtm.rtm_addrs);
1246
1247 if (INFO_DST(&info) == 0) {
1248 trace_act("ignore %s without dst", str);
1249 continue;
1250 }
1251
1252 if (INFO_DST(&info)->sa_family != AF_INET) {
1253 trace_act("ignore %s for AF %d", str,
1254 INFO_DST(&info)->sa_family);
1255 continue;
1256 }
1257
1258 mask = ((INFO_MASK(&info) != 0)
1259 ? ntohl(S_ADDR(INFO_MASK(&info)))
1260 : (m.r.rtm.rtm_flags & RTF_HOST)
1261 ? HOST_MASK
1262 : std_mask(S_ADDR(INFO_DST(&info))));
1263
1264 snprintf(strp, str + sizeof(str) - strp, ": %s",
1265 addrname(S_ADDR(INFO_DST(&info)), mask, 0));
1266 strp += strlen(strp);
1267
1268 if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info))))) {
1269 trace_act("ignore multicast %s", str);
1270 continue;
1271 }
1272
1273 #if defined(RTF_CLONED) && defined(__bsdi__)
1274 if (m.r.rtm.rtm_flags & RTF_CLONED) {
1275 trace_act("ignore cloned %s", str);
1276 continue;
1277 }
1278 #endif
1279 #if defined(RTF_WASCLONED) && defined(__FreeBSD__)
1280 if (m.r.rtm.rtm_flags & RTF_WASCLONED) {
1281 trace_act("ignore cloned %s", str);
1282 continue;
1283 }
1284 #endif
1285
1286 if (get_info_gate(&INFO_GATE(&info), &gate_sin)) {
1287 gate = S_ADDR(INFO_GATE(&info));
1288 snprintf(strp, str + sizeof(str) - strp,
1289 " --> %s", naddr_ntoa(gate));
1290 strp += strlen(strp);
1291 } else {
1292 gate = 0;
1293 }
1294
1295 if (INFO_AUTHOR(&info) != 0) {
1296 snprintf(strp, str + sizeof(str) - strp,
1297 " by authority of %s",
1298 saddr_ntoa(INFO_AUTHOR(&info)));
1299 strp += strlen(strp);
1300 }
1301
1302 switch (m.r.rtm.rtm_type) {
1303 case RTM_ADD:
1304 case RTM_CHANGE:
1305 case RTM_REDIRECT:
1306 if (m.r.rtm.rtm_errno != 0) {
1307 trace_act("ignore %s with \"%s\" error",
1308 str, strerror(m.r.rtm.rtm_errno));
1309 } else {
1310 trace_act("%s", str);
1311 rtm_add(&m.r.rtm,&info,0);
1312 }
1313 break;
1314
1315 case RTM_DELETE:
1316 if (m.r.rtm.rtm_errno != 0
1317 && m.r.rtm.rtm_errno != ESRCH) {
1318 trace_act("ignore %s with \"%s\" error",
1319 str, strerror(m.r.rtm.rtm_errno));
1320 } else {
1321 trace_act("%s", str);
1322 del_static(S_ADDR(INFO_DST(&info)), mask,
1323 gate, 1);
1324 }
1325 break;
1326
1327 case RTM_LOSING:
1328 trace_act("%s", str);
1329 rtm_lose(&m.r.rtm,&info);
1330 break;
1331
1332 default:
1333 trace_act("ignore %s", str);
1334 break;
1335 }
1336 }
1337 }
1338
1339
1340 /* after aggregating, note routes that belong in the kernel
1341 */
1342 static void
kern_out(struct ag_info * ag)1343 kern_out(struct ag_info *ag)
1344 {
1345 struct khash *k;
1346
1347
1348 /* Do not install bad routes if they are not already present.
1349 * This includes routes that had RS_NET_SYN for interfaces that
1350 * recently died.
1351 */
1352 if (ag->ag_metric == HOPCNT_INFINITY) {
1353 k = kern_find(htonl(ag->ag_dst_h), ag->ag_mask, 0);
1354 if (k == 0)
1355 return;
1356 } else {
1357 k = kern_add(htonl(ag->ag_dst_h), ag->ag_mask);
1358 }
1359
1360 if (k->k_state & KS_NEW) {
1361 /* will need to add new entry to the kernel table */
1362 k->k_state = KS_ADD;
1363 if (ag->ag_state & AGS_GATEWAY)
1364 k->k_state |= KS_GATEWAY;
1365 k->k_gate = ag->ag_gate;
1366 k->k_metric = ag->ag_metric;
1367 return;
1368 }
1369
1370 if ((k->k_state & KS_STATIC) || (k->k_state & KS_LOCAL))
1371 return;
1372
1373 /* modify existing kernel entry if necessary */
1374 if (k->k_gate != ag->ag_gate
1375 || k->k_metric != ag->ag_metric) {
1376 /* Must delete bad interface routes etc. to change them. */
1377 if (k->k_metric == HOPCNT_INFINITY)
1378 k->k_state |= KS_DEL_ADD;
1379 k->k_gate = ag->ag_gate;
1380 k->k_metric = ag->ag_metric;
1381 k->k_state |= KS_CHANGE;
1382 }
1383
1384 /* If the daemon thinks the route should exist, forget
1385 * about any redirections.
1386 * If the daemon thinks the route should exist, eventually
1387 * override manual intervention by the operator.
1388 */
1389 if ((k->k_state & (KS_DYNAMIC | KS_DELETED)) != 0) {
1390 k->k_state &= ~KS_DYNAMIC;
1391 k->k_state |= (KS_ADD | KS_DEL_ADD);
1392 }
1393
1394 if ((k->k_state & KS_GATEWAY)
1395 && !(ag->ag_state & AGS_GATEWAY)) {
1396 k->k_state &= ~KS_GATEWAY;
1397 k->k_state |= (KS_ADD | KS_DEL_ADD);
1398 } else if (!(k->k_state & KS_GATEWAY)
1399 && (ag->ag_state & AGS_GATEWAY)) {
1400 k->k_state |= KS_GATEWAY;
1401 k->k_state |= (KS_ADD | KS_DEL_ADD);
1402 }
1403
1404 /* Deleting-and-adding is necessary to change aspects of a route.
1405 * Just delete instead of deleting and then adding a bad route.
1406 * Otherwise, we want to keep the route in the kernel.
1407 */
1408 if (k->k_metric == HOPCNT_INFINITY
1409 && (k->k_state & KS_DEL_ADD))
1410 k->k_state |= KS_DELETE;
1411 else
1412 k->k_state &= ~KS_DELETE;
1413 #undef RT
1414 }
1415
1416
1417 /* ARGSUSED */
1418 static int
walk_kern(struct radix_node * rn,struct walkarg * argp UNUSED)1419 walk_kern(struct radix_node *rn,
1420 struct walkarg *argp UNUSED)
1421 {
1422 #define RT ((struct rt_entry *)rn)
1423 char metric, pref;
1424 u_int ags = 0;
1425
1426
1427 /* Do not install synthetic routes */
1428 if (RT->rt_state & RS_NET_SYN)
1429 return 0;
1430
1431 if (!(RT->rt_state & RS_IF)) {
1432 /* This is an ordinary route, not for an interface.
1433 */
1434
1435 /* aggregate, ordinary good routes without regard to
1436 * their metric
1437 */
1438 pref = 1;
1439 ags |= (AGS_GATEWAY | AGS_SUPPRESS | AGS_AGGREGATE);
1440
1441 /* Do not install host routes directly to hosts, to avoid
1442 * interfering with ARP entries in the kernel table.
1443 */
1444 if (RT_ISHOST(RT)
1445 && ntohl(RT->rt_dst) == RT->rt_gate)
1446 return 0;
1447
1448 } else {
1449 /* This is an interface route.
1450 * Do not install routes for "external" remote interfaces.
1451 */
1452 if (RT->rt_ifp != 0 && (RT->rt_ifp->int_state & IS_EXTERNAL))
1453 return 0;
1454
1455 /* Interfaces should override received routes.
1456 */
1457 pref = 0;
1458 ags |= (AGS_IF | AGS_CORS_GATE);
1459
1460 /* If it is not an interface, or an alias for an interface,
1461 * it must be a "gateway."
1462 *
1463 * If it is a "remote" interface, it is also a "gateway" to
1464 * the kernel if is not a alias.
1465 */
1466 if (RT->rt_ifp == 0
1467 || (RT->rt_ifp->int_state & IS_REMOTE))
1468 ags |= (AGS_GATEWAY | AGS_SUPPRESS | AGS_AGGREGATE);
1469 }
1470
1471 /* If RIP is off and IRDP is on, let the route to the discovered
1472 * route suppress any RIP routes. Eventually the RIP routes
1473 * will time-out and be deleted. This reaches the steady-state
1474 * quicker.
1475 */
1476 if ((RT->rt_state & RS_RDISC) && rip_sock < 0)
1477 ags |= AGS_CORS_GATE;
1478
1479 metric = RT->rt_metric;
1480 if (metric == HOPCNT_INFINITY) {
1481 /* if the route is dead, so try hard to aggregate. */
1482 pref = HOPCNT_INFINITY;
1483 ags |= (AGS_FINE_GATE | AGS_SUPPRESS);
1484 ags &= ~(AGS_IF | AGS_CORS_GATE);
1485 }
1486
1487 ag_check(RT->rt_dst, RT->rt_mask, RT->rt_gate, 0,
1488 metric,pref, 0, 0, ags, kern_out);
1489 return 0;
1490 #undef RT
1491 }
1492
1493
1494 /* Update the kernel table to match the daemon table.
1495 */
1496 static void
fix_kern(void)1497 fix_kern(void)
1498 {
1499 int i;
1500 struct khash *k, **pk;
1501
1502
1503 need_kern = age_timer;
1504
1505 /* Walk daemon table, updating the copy of the kernel table.
1506 */
1507 (void)rn_walktree(rhead, walk_kern, 0);
1508 ag_flush(0,0,kern_out);
1509
1510 for (i = 0; i < KHASH_SIZE; i++) {
1511 for (pk = &khash_bins[i]; (k = *pk) != 0; ) {
1512 /* Do not touch static routes */
1513 if (k->k_state & KS_STATIC) {
1514 kern_check_static(k,0);
1515 pk = &k->k_next;
1516 continue;
1517 }
1518
1519 /* Do not touch local routes */
1520 if (k->k_state & KS_LOCAL) {
1521 pk = &k->k_next;
1522 continue;
1523 }
1524
1525 /* check hold on routes deleted by the operator */
1526 if (k->k_keep > now.tv_sec) {
1527 /* ensure we check when the hold is over */
1528 LIM_SEC(need_kern, k->k_keep);
1529 /* mark for the next cycle */
1530 k->k_state |= KS_DELETE;
1531 pk = &k->k_next;
1532 continue;
1533 }
1534
1535 if ((k->k_state & KS_DELETE)
1536 && !(k->k_state & KS_DYNAMIC)) {
1537 kern_ioctl(k, RTM_DELETE, 0);
1538 *pk = k->k_next;
1539 free(k);
1540 continue;
1541 }
1542
1543 if (k->k_state & KS_DEL_ADD)
1544 kern_ioctl(k, RTM_DELETE, 0);
1545
1546 if (k->k_state & KS_ADD) {
1547 kern_ioctl(k, RTM_ADD,
1548 ((0 != (k->k_state & (KS_GATEWAY
1549 | KS_DYNAMIC)))
1550 ? RTF_GATEWAY : 0));
1551 } else if (k->k_state & KS_CHANGE) {
1552 kern_ioctl(k, RTM_CHANGE,
1553 ((0 != (k->k_state & (KS_GATEWAY
1554 | KS_DYNAMIC)))
1555 ? RTF_GATEWAY : 0));
1556 }
1557 k->k_state &= ~(KS_ADD|KS_CHANGE|KS_DEL_ADD);
1558
1559 /* Mark this route to be deleted in the next cycle.
1560 * This deletes routes that disappear from the
1561 * daemon table, since the normal aging code
1562 * will clear the bit for routes that have not
1563 * disappeared from the daemon table.
1564 */
1565 k->k_state |= KS_DELETE;
1566 pk = &k->k_next;
1567 }
1568 }
1569 }
1570
1571
1572 /* Delete a static route in the image of the kernel table.
1573 */
1574 void
del_static(naddr dst,naddr mask,naddr gate,int gone)1575 del_static(naddr dst,
1576 naddr mask,
1577 naddr gate,
1578 int gone)
1579 {
1580 struct khash *k;
1581 struct rt_entry *rt;
1582
1583 /* Just mark it in the table to be deleted next time the kernel
1584 * table is updated.
1585 * If it has already been deleted, mark it as such, and set its
1586 * keep-timer so that it will not be deleted again for a while.
1587 * This lets the operator delete a route added by the daemon
1588 * and add a replacement.
1589 */
1590 k = kern_find(dst, mask, 0);
1591 if (k != 0 && (gate == 0 || k->k_gate == gate)) {
1592 k->k_state &= ~(KS_STATIC | KS_DYNAMIC | KS_CHECK);
1593 k->k_state |= KS_DELETE;
1594 if (gone) {
1595 k->k_state |= KS_DELETED;
1596 k->k_keep = now.tv_sec + K_KEEP_LIM;
1597 }
1598 }
1599
1600 rt = rtget(dst, mask);
1601 if (rt != 0 && (rt->rt_state & RS_STATIC))
1602 rtbad(rt);
1603 }
1604
1605
1606 /* Delete all routes generated from ICMP Redirects that use a given gateway,
1607 * as well as old redirected routes.
1608 */
1609 void
del_redirects(naddr bad_gate,time_t old)1610 del_redirects(naddr bad_gate,
1611 time_t old)
1612 {
1613 int i;
1614 struct khash *k;
1615
1616
1617 for (i = 0; i < KHASH_SIZE; i++) {
1618 for (k = khash_bins[i]; k != 0; k = k->k_next) {
1619 if (!(k->k_state & KS_DYNAMIC)
1620 || (k->k_state & KS_STATIC))
1621 continue;
1622
1623 if (k->k_gate != bad_gate
1624 && k->k_redirect_time > old
1625 && !supplier)
1626 continue;
1627
1628 k->k_state |= KS_DELETE;
1629 k->k_state &= ~KS_DYNAMIC;
1630 need_kern.tv_sec = now.tv_sec;
1631 trace_act("mark redirected %s --> %s for deletion",
1632 addrname(k->k_dst, k->k_mask, 0),
1633 naddr_ntoa(k->k_gate));
1634 }
1635 }
1636 }
1637
1638
1639 /* Start the daemon tables.
1640 */
1641 extern int max_keylen;
1642
1643 void
rtinit(void)1644 rtinit(void)
1645 {
1646 int i;
1647 struct ag_info *ag;
1648
1649 /* Initialize the radix trees */
1650 max_keylen = sizeof(struct sockaddr_in);
1651 rn_init();
1652 rn_inithead((void*)&rhead, 32);
1653
1654 /* mark all of the slots in the table free */
1655 ag_avail = ag_slots;
1656 for (ag = ag_slots, i = 1; i < NUM_AG_SLOTS; i++) {
1657 ag->ag_fine = ag+1;
1658 ag++;
1659 }
1660 }
1661
1662
1663 #ifdef _HAVE_SIN_LEN
1664 static struct sockaddr_in dst_sock = {sizeof(dst_sock), AF_INET, 0, {0}, {0}};
1665 static struct sockaddr_in mask_sock = {sizeof(mask_sock), AF_INET, 0, {0}, {0}};
1666 #else
1667 static struct sockaddr_in_new dst_sock = {_SIN_ADDR_SIZE, AF_INET};
1668 static struct sockaddr_in_new mask_sock = {_SIN_ADDR_SIZE, AF_INET};
1669 #endif
1670
1671
1672 static void
set_need_flash(void)1673 set_need_flash(void)
1674 {
1675 if (!need_flash) {
1676 need_flash = 1;
1677 /* Do not send the flash update immediately. Wait a little
1678 * while to hear from other routers.
1679 */
1680 no_flash.tv_sec = now.tv_sec + MIN_WAITTIME;
1681 }
1682 }
1683
1684
1685 /* Get a particular routing table entry
1686 */
1687 struct rt_entry *
rtget(naddr dst,naddr mask)1688 rtget(naddr dst, naddr mask)
1689 {
1690 struct rt_entry *rt;
1691
1692 dst_sock.sin_addr.s_addr = dst;
1693 mask_sock.sin_addr.s_addr = htonl(mask);
1694 masktrim(&mask_sock);
1695 rt = (struct rt_entry *)rhead->rnh_lookup(&dst_sock,&mask_sock,rhead);
1696 if (!rt
1697 || rt->rt_dst != dst
1698 || rt->rt_mask != mask)
1699 return 0;
1700
1701 return rt;
1702 }
1703
1704
1705 /* Find a route to dst as the kernel would.
1706 */
1707 struct rt_entry *
rtfind(naddr dst)1708 rtfind(naddr dst)
1709 {
1710 dst_sock.sin_addr.s_addr = dst;
1711 return (struct rt_entry *)rhead->rnh_matchaddr(&dst_sock, rhead);
1712 }
1713
1714
1715 /* add a route to the table
1716 */
1717 void
rtadd(naddr dst,naddr mask,u_int state,struct rt_spare * new)1718 rtadd(naddr dst,
1719 naddr mask,
1720 u_int state, /* rt_state for the entry */
1721 struct rt_spare *new)
1722 {
1723 struct rt_entry *rt;
1724 naddr smask;
1725 int i;
1726 struct rt_spare *rts;
1727
1728 rt = (struct rt_entry *)rtmalloc(sizeof (*rt), "rtadd");
1729 memset(rt, 0, sizeof(*rt));
1730 for (rts = rt->rt_spares, i = NUM_SPARES; i != 0; i--, rts++)
1731 rts->rts_metric = HOPCNT_INFINITY;
1732
1733 rt->rt_nodes->rn_key = (caddr_t)&rt->rt_dst_sock;
1734 rt->rt_dst = dst;
1735 rt->rt_dst_sock.sin_family = AF_INET;
1736 #ifdef _HAVE_SIN_LEN
1737 rt->rt_dst_sock.sin_len = dst_sock.sin_len;
1738 #endif
1739 if (mask != HOST_MASK) {
1740 smask = std_mask(dst);
1741 if ((smask & ~mask) == 0 && mask > smask)
1742 state |= RS_SUBNET;
1743 }
1744 mask_sock.sin_addr.s_addr = htonl(mask);
1745 masktrim(&mask_sock);
1746 rt->rt_mask = mask;
1747 rt->rt_state = state;
1748 rt->rt_spares[0] = *new;
1749 rt->rt_time = now.tv_sec;
1750 rt->rt_poison_metric = HOPCNT_INFINITY;
1751 rt->rt_seqno = update_seqno;
1752
1753 if (++total_routes == MAX_ROUTES)
1754 msglog("have maximum (%d) routes", total_routes);
1755 if (TRACEACTIONS)
1756 trace_add_del("Add", rt);
1757
1758 need_kern.tv_sec = now.tv_sec;
1759 set_need_flash();
1760
1761 if (0 == rhead->rnh_addaddr(&rt->rt_dst_sock, &mask_sock,
1762 rhead, rt->rt_nodes)) {
1763 msglog("rnh_addaddr() failed for %s mask=%#lx",
1764 naddr_ntoa(dst), (u_long)mask);
1765 free(rt);
1766 }
1767 }
1768
1769
1770 /* notice a changed route
1771 */
1772 void
rtchange(struct rt_entry * rt,u_int state,struct rt_spare * new,char * label)1773 rtchange(struct rt_entry *rt,
1774 u_int state, /* new state bits */
1775 struct rt_spare *new,
1776 char *label)
1777 {
1778 if (rt->rt_metric != new->rts_metric) {
1779 /* Fix the kernel immediately if it seems the route
1780 * has gone bad, since there may be a working route that
1781 * aggregates this route.
1782 */
1783 if (new->rts_metric == HOPCNT_INFINITY) {
1784 need_kern.tv_sec = now.tv_sec;
1785 if (new->rts_time >= now.tv_sec - EXPIRE_TIME)
1786 new->rts_time = now.tv_sec - EXPIRE_TIME;
1787 }
1788 rt->rt_seqno = update_seqno;
1789 set_need_flash();
1790 }
1791
1792 if (rt->rt_gate != new->rts_gate) {
1793 need_kern.tv_sec = now.tv_sec;
1794 rt->rt_seqno = update_seqno;
1795 set_need_flash();
1796 }
1797
1798 state |= (rt->rt_state & RS_SUBNET);
1799
1800 /* Keep various things from deciding ageless routes are stale.
1801 */
1802 if (!AGE_RT(state, new->rts_ifp))
1803 new->rts_time = now.tv_sec;
1804
1805 if (TRACEACTIONS)
1806 trace_change(rt, state, new,
1807 label ? label : "Chg ");
1808
1809 rt->rt_state = state;
1810 rt->rt_spares[0] = *new;
1811 }
1812
1813
1814 /* check for a better route among the spares
1815 */
1816 static struct rt_spare *
rts_better(struct rt_entry * rt)1817 rts_better(struct rt_entry *rt)
1818 {
1819 struct rt_spare *rts, *rts1;
1820 int i;
1821
1822 /* find the best alternative among the spares */
1823 rts = rt->rt_spares+1;
1824 for (i = NUM_SPARES, rts1 = rts+1; i > 2; i--, rts1++) {
1825 if (BETTER_LINK(rt,rts1,rts))
1826 rts = rts1;
1827 }
1828
1829 return rts;
1830 }
1831
1832
1833 /* switch to a backup route
1834 */
1835 void
rtswitch(struct rt_entry * rt,struct rt_spare * rts)1836 rtswitch(struct rt_entry *rt,
1837 struct rt_spare *rts)
1838 {
1839 struct rt_spare swap;
1840 char label[20];
1841
1842 /* Do not change permanent routes */
1843 if (0 != (rt->rt_state & (RS_MHOME | RS_STATIC | RS_RDISC
1844 | RS_NET_SYN | RS_IF)))
1845 return;
1846
1847 /* find the best alternative among the spares */
1848 if (rts == 0)
1849 rts = rts_better(rt);
1850
1851 /* Do not bother if it is not worthwhile.
1852 */
1853 if (!BETTER_LINK(rt, rts, rt->rt_spares))
1854 return;
1855
1856 swap = rt->rt_spares[0];
1857 (void)snprintf(label, sizeof(label), "Use #%d",
1858 (int)(rts - rt->rt_spares));
1859 rtchange(rt, rt->rt_state & ~(RS_NET_SYN | RS_RDISC), rts, label);
1860 if (swap.rts_metric == HOPCNT_INFINITY) {
1861 *rts = rts_empty;
1862 } else {
1863 *rts = swap;
1864 }
1865 }
1866
1867
1868 void
rtdelete(struct rt_entry * rt)1869 rtdelete(struct rt_entry *rt)
1870 {
1871 struct khash *k;
1872
1873
1874 if (TRACEACTIONS)
1875 trace_add_del("Del", rt);
1876
1877 k = kern_find(rt->rt_dst, rt->rt_mask, 0);
1878 if (k != 0) {
1879 k->k_state |= KS_DELETE;
1880 need_kern.tv_sec = now.tv_sec;
1881 }
1882
1883 dst_sock.sin_addr.s_addr = rt->rt_dst;
1884 mask_sock.sin_addr.s_addr = htonl(rt->rt_mask);
1885 masktrim(&mask_sock);
1886 if (rt != (struct rt_entry *)rhead->rnh_deladdr(&dst_sock, &mask_sock,
1887 rhead)) {
1888 msglog("rnh_deladdr() failed");
1889 } else {
1890 free(rt);
1891 total_routes--;
1892 }
1893 }
1894
1895
1896 void
rts_delete(struct rt_entry * rt,struct rt_spare * rts)1897 rts_delete(struct rt_entry *rt,
1898 struct rt_spare *rts)
1899 {
1900 trace_upslot(rt, rts, &rts_empty);
1901 *rts = rts_empty;
1902 }
1903
1904
1905 /* Get rid of a bad route, and try to switch to a replacement.
1906 */
1907 void
rtbad(struct rt_entry * rt)1908 rtbad(struct rt_entry *rt)
1909 {
1910 struct rt_spare new;
1911
1912 /* Poison the route */
1913 new = rt->rt_spares[0];
1914 new.rts_metric = HOPCNT_INFINITY;
1915 rtchange(rt, rt->rt_state & ~(RS_IF | RS_LOCAL | RS_STATIC), &new, 0);
1916 rtswitch(rt, 0);
1917 }
1918
1919
1920 /* Junk a RS_NET_SYN or RS_LOCAL route,
1921 * unless it is needed by another interface.
1922 */
1923 void
rtbad_sub(struct rt_entry * rt)1924 rtbad_sub(struct rt_entry *rt)
1925 {
1926 struct interface *ifp, *ifp1;
1927 struct intnet *intnetp;
1928 u_int state;
1929
1930
1931 ifp1 = 0;
1932 state = 0;
1933
1934 if (rt->rt_state & RS_LOCAL) {
1935 /* Is this the route through loopback for the interface?
1936 * If so, see if it is used by any other interfaces, such
1937 * as a point-to-point interface with the same local address.
1938 */
1939 for (ifp = ifnet; ifp != 0; ifp = ifp->int_next) {
1940 /* Retain it if another interface needs it.
1941 */
1942 if (ifp->int_addr == rt->rt_ifp->int_addr) {
1943 state |= RS_LOCAL;
1944 ifp1 = ifp;
1945 break;
1946 }
1947 }
1948
1949 }
1950
1951 if (!(state & RS_LOCAL)) {
1952 /* Retain RIPv1 logical network route if there is another
1953 * interface that justifies it.
1954 */
1955 if (rt->rt_state & RS_NET_SYN) {
1956 for (ifp = ifnet; ifp != 0; ifp = ifp->int_next) {
1957 if ((ifp->int_state & IS_NEED_NET_SYN)
1958 && rt->rt_mask == ifp->int_std_mask
1959 && rt->rt_dst == ifp->int_std_addr) {
1960 state |= RS_NET_SYN;
1961 ifp1 = ifp;
1962 break;
1963 }
1964 }
1965 }
1966
1967 /* or if there is an authority route that needs it. */
1968 for (intnetp = intnets;
1969 intnetp != 0;
1970 intnetp = intnetp->intnet_next) {
1971 if (intnetp->intnet_addr == rt->rt_dst
1972 && intnetp->intnet_mask == rt->rt_mask) {
1973 state |= (RS_NET_SYN | RS_NET_INT);
1974 break;
1975 }
1976 }
1977 }
1978
1979 if (ifp1 != 0 || (state & RS_NET_SYN)) {
1980 struct rt_spare new = rt->rt_spares[0];
1981 new.rts_ifp = ifp1;
1982 rtchange(rt, ((rt->rt_state & ~(RS_NET_SYN|RS_LOCAL)) | state),
1983 &new, 0);
1984 } else {
1985 rtbad(rt);
1986 }
1987 }
1988
1989
1990 /* Called while walking the table looking for sick interfaces
1991 * or after a time change.
1992 */
1993 /* ARGSUSED */
1994 int
walk_bad(struct radix_node * rn,struct walkarg * argp UNUSED)1995 walk_bad(struct radix_node *rn,
1996 struct walkarg *argp UNUSED)
1997 {
1998 #define RT ((struct rt_entry *)rn)
1999 struct rt_spare *rts;
2000 int i;
2001
2002
2003 /* fix any spare routes through the interface
2004 */
2005 rts = RT->rt_spares;
2006 for (i = NUM_SPARES; i != 1; i--) {
2007 rts++;
2008 if (rts->rts_metric < HOPCNT_INFINITY
2009 && (rts->rts_ifp == 0
2010 || (rts->rts_ifp->int_state & IS_BROKE)))
2011 rts_delete(RT, rts);
2012 }
2013
2014 /* Deal with the main route
2015 */
2016 /* finished if it has been handled before or if its interface is ok
2017 */
2018 if (RT->rt_ifp == 0 || !(RT->rt_ifp->int_state & IS_BROKE))
2019 return 0;
2020
2021 /* Bad routes for other than interfaces are easy.
2022 */
2023 if (0 == (RT->rt_state & (RS_IF | RS_NET_SYN | RS_LOCAL))) {
2024 rtbad(RT);
2025 return 0;
2026 }
2027
2028 rtbad_sub(RT);
2029 return 0;
2030 #undef RT
2031 }
2032
2033
2034 /* Check the age of an individual route.
2035 */
2036 /* ARGSUSED */
2037 static int
walk_age(struct radix_node * rn,struct walkarg * argp UNUSED)2038 walk_age(struct radix_node *rn,
2039 struct walkarg *argp UNUSED)
2040 {
2041 #define RT ((struct rt_entry *)rn)
2042 struct interface *ifp;
2043 struct rt_spare *rts;
2044 int i;
2045
2046
2047 /* age all of the spare routes, including the primary route
2048 * currently in use
2049 */
2050 rts = RT->rt_spares;
2051 for (i = NUM_SPARES; i != 0; i--, rts++) {
2052
2053 ifp = rts->rts_ifp;
2054 if (i == NUM_SPARES) {
2055 if (!AGE_RT(RT->rt_state, ifp)) {
2056 /* Keep various things from deciding ageless
2057 * routes are stale
2058 */
2059 rts->rts_time = now.tv_sec;
2060 continue;
2061 }
2062
2063 /* forget RIP routes after RIP has been turned off.
2064 */
2065 if (rip_sock < 0) {
2066 rtdelete(RT);
2067 return 0;
2068 }
2069 }
2070
2071 /* age failing routes
2072 */
2073 if (age_bad_gate == rts->rts_gate
2074 && rts->rts_time >= now_stale) {
2075 rts->rts_time -= SUPPLY_INTERVAL;
2076 }
2077
2078 /* trash the spare routes when they go bad */
2079 if (rts->rts_metric < HOPCNT_INFINITY
2080 && now_garbage > rts->rts_time
2081 && i != NUM_SPARES)
2082 rts_delete(RT, rts);
2083 }
2084
2085
2086 /* finished if the active route is still fresh */
2087 if (now_stale <= RT->rt_time)
2088 return 0;
2089
2090 /* try to switch to an alternative */
2091 rtswitch(RT, 0);
2092
2093 /* Delete a dead route after it has been publically mourned. */
2094 if (now_garbage > RT->rt_time) {
2095 rtdelete(RT);
2096 return 0;
2097 }
2098
2099 /* Start poisoning a bad route before deleting it. */
2100 if (now.tv_sec - RT->rt_time > EXPIRE_TIME) {
2101 struct rt_spare new = RT->rt_spares[0];
2102 new.rts_metric = HOPCNT_INFINITY;
2103 rtchange(RT, RT->rt_state, &new, 0);
2104 }
2105 return 0;
2106 }
2107
2108
2109 /* Watch for dead routes and interfaces.
2110 */
2111 void
age(naddr bad_gate)2112 age(naddr bad_gate)
2113 {
2114 struct interface *ifp;
2115 int need_query = 0;
2116
2117 /* If not listening to RIP, there is no need to age the routes in
2118 * the table.
2119 */
2120 age_timer.tv_sec = (now.tv_sec
2121 + ((rip_sock < 0) ? NEVER : SUPPLY_INTERVAL));
2122
2123 /* Check for dead IS_REMOTE interfaces by timing their
2124 * transmissions.
2125 */
2126 for (ifp = ifnet; ifp; ifp = ifp->int_next) {
2127 if (!(ifp->int_state & IS_REMOTE))
2128 continue;
2129
2130 /* ignore unreachable remote interfaces */
2131 if (!check_remote(ifp))
2132 continue;
2133
2134 /* Restore remote interface that has become reachable
2135 */
2136 if (ifp->int_state & IS_BROKE)
2137 if_ok(ifp, "remote ");
2138
2139 if (ifp->int_act_time != NEVER
2140 && now.tv_sec - ifp->int_act_time > EXPIRE_TIME) {
2141 msglog("remote interface %s to %s timed out after"
2142 " %lld:%lld",
2143 ifp->int_name,
2144 naddr_ntoa(ifp->int_dstaddr),
2145 (long long)(now.tv_sec - ifp->int_act_time)/60,
2146 (long long)(now.tv_sec - ifp->int_act_time)%60);
2147 if_sick(ifp);
2148 }
2149
2150 /* If we have not heard from the other router
2151 * recently, ask it.
2152 */
2153 if (now.tv_sec >= ifp->int_query_time) {
2154 ifp->int_query_time = NEVER;
2155 need_query = 1;
2156 }
2157 }
2158
2159 /* Age routes. */
2160 age_bad_gate = bad_gate;
2161 (void)rn_walktree(rhead, walk_age, 0);
2162
2163 /* delete old redirected routes to keep the kernel table small
2164 * and prevent blackholes
2165 */
2166 del_redirects(bad_gate, now.tv_sec-STALE_TIME);
2167
2168 /* Update the kernel routing table. */
2169 fix_kern();
2170
2171 /* poke reticent remote gateways */
2172 if (need_query)
2173 rip_query();
2174 }
2175