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