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