xref: /freebsd/sbin/routed/table.c (revision 90100551e629f1b41040f747305094d8e4565a90)
17b6ab19dSGarrett Wollman /*
27b6ab19dSGarrett Wollman  * Copyright (c) 1983, 1988, 1993
37b6ab19dSGarrett Wollman  *	The Regents of the University of California.  All rights reserved.
47b6ab19dSGarrett Wollman  *
57b6ab19dSGarrett Wollman  * Redistribution and use in source and binary forms, with or without
67b6ab19dSGarrett Wollman  * modification, are permitted provided that the following conditions
77b6ab19dSGarrett Wollman  * are met:
87b6ab19dSGarrett Wollman  * 1. Redistributions of source code must retain the above copyright
97b6ab19dSGarrett Wollman  *    notice, this list of conditions and the following disclaimer.
107b6ab19dSGarrett Wollman  * 2. Redistributions in binary form must reproduce the above copyright
117b6ab19dSGarrett Wollman  *    notice, this list of conditions and the following disclaimer in the
127b6ab19dSGarrett Wollman  *    documentation and/or other materials provided with the distribution.
137b6ab19dSGarrett Wollman  * 3. All advertising materials mentioning features or use of this software
147b6ab19dSGarrett Wollman  *    must display the following acknowledgement:
157b6ab19dSGarrett Wollman  *	This product includes software developed by the University of
167b6ab19dSGarrett Wollman  *	California, Berkeley and its contributors.
177b6ab19dSGarrett Wollman  * 4. Neither the name of the University nor the names of its contributors
187b6ab19dSGarrett Wollman  *    may be used to endorse or promote products derived from this software
197b6ab19dSGarrett Wollman  *    without specific prior written permission.
207b6ab19dSGarrett Wollman  *
217b6ab19dSGarrett Wollman  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
227b6ab19dSGarrett Wollman  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
237b6ab19dSGarrett Wollman  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
247b6ab19dSGarrett Wollman  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
257b6ab19dSGarrett Wollman  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
267b6ab19dSGarrett Wollman  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
277b6ab19dSGarrett Wollman  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
287b6ab19dSGarrett Wollman  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
297b6ab19dSGarrett Wollman  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
307b6ab19dSGarrett Wollman  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
317b6ab19dSGarrett Wollman  * SUCH DAMAGE.
327b6ab19dSGarrett Wollman  */
337b6ab19dSGarrett Wollman 
3490100551SPhilippe Charnier #ifndef lint
3590100551SPhilippe Charnier #if 0
367b6ab19dSGarrett Wollman static char sccsid[] = "@(#)tables.c	8.1 (Berkeley) 6/5/93";
377b6ab19dSGarrett Wollman #endif
3890100551SPhilippe Charnier static const char rcsid[] =
3990100551SPhilippe Charnier 	"$Id$";
4090100551SPhilippe Charnier #endif /* not lint */
417b6ab19dSGarrett Wollman 
427b6ab19dSGarrett Wollman #include "defs.h"
437b6ab19dSGarrett Wollman 
447b6ab19dSGarrett Wollman static struct rt_spare *rts_better(struct rt_entry *);
457b6ab19dSGarrett Wollman 
467b6ab19dSGarrett Wollman struct radix_node_head *rhead;		/* root of the radix tree */
477b6ab19dSGarrett Wollman 
487b6ab19dSGarrett Wollman int	need_flash = 1;			/* flash update needed
497b6ab19dSGarrett Wollman 					 * start =1 to suppress the 1st
507b6ab19dSGarrett Wollman 					 */
517b6ab19dSGarrett Wollman 
527b6ab19dSGarrett Wollman struct timeval age_timer;		/* next check of old routes */
537b6ab19dSGarrett Wollman struct timeval need_kern = {		/* need to update kernel table */
547b6ab19dSGarrett Wollman 	EPOCH+MIN_WAITTIME-1
557b6ab19dSGarrett Wollman };
567b6ab19dSGarrett Wollman 
577b6ab19dSGarrett Wollman int	stopint;
587b6ab19dSGarrett Wollman 
597b6ab19dSGarrett Wollman int	total_routes;
607b6ab19dSGarrett Wollman 
6152ad6021SGarrett Wollman /* zap any old routes through this gateway */
627b6ab19dSGarrett Wollman naddr	age_bad_gate;
637b6ab19dSGarrett Wollman 
647b6ab19dSGarrett Wollman 
657b6ab19dSGarrett Wollman /* It is desirable to "aggregate" routes, to combine differing routes of
667b6ab19dSGarrett Wollman  * the same metric and next hop into a common route with a smaller netmask
677b6ab19dSGarrett Wollman  * or to suppress redundant routes, routes that add no information to
687b6ab19dSGarrett Wollman  * routes with smaller netmasks.
697b6ab19dSGarrett Wollman  *
707b6ab19dSGarrett Wollman  * A route is redundant if and only if any and all routes with smaller
717b6ab19dSGarrett Wollman  * but matching netmasks and nets are the same.  Since routes are
727b6ab19dSGarrett Wollman  * kept sorted in the radix tree, redundant routes always come second.
737b6ab19dSGarrett Wollman  *
747b6ab19dSGarrett Wollman  * There are two kinds of aggregations.  First, two routes of the same bit
757b6ab19dSGarrett Wollman  * mask and differing only in the least significant bit of the network
767b6ab19dSGarrett Wollman  * number can be combined into a single route with a coarser mask.
777b6ab19dSGarrett Wollman  *
787b6ab19dSGarrett Wollman  * Second, a route can be suppressed in favor of another route with a more
797b6ab19dSGarrett Wollman  * coarse mask provided no incompatible routes with intermediate masks
807b6ab19dSGarrett Wollman  * are present.  The second kind of aggregation involves suppressing routes.
817b6ab19dSGarrett Wollman  * A route must not be suppressed if an incompatible route exists with
827b6ab19dSGarrett Wollman  * an intermediate mask, since the suppressed route would be covered
837b6ab19dSGarrett Wollman  * by the intermediate.
847b6ab19dSGarrett Wollman  *
857b6ab19dSGarrett Wollman  * This code relies on the radix tree walk encountering routes
867b6ab19dSGarrett Wollman  * sorted first by address, with the smallest address first.
877b6ab19dSGarrett Wollman  */
887b6ab19dSGarrett Wollman 
897b6ab19dSGarrett Wollman struct ag_info ag_slots[NUM_AG_SLOTS], *ag_avail, *ag_corsest, *ag_finest;
907b6ab19dSGarrett Wollman 
917b6ab19dSGarrett Wollman /* #define DEBUG_AG */
927b6ab19dSGarrett Wollman #ifdef DEBUG_AG
937b6ab19dSGarrett Wollman #define CHECK_AG() {int acnt = 0; struct ag_info *cag;		\
947b6ab19dSGarrett Wollman 	for (cag = ag_avail; cag != 0; cag = cag->ag_fine)	\
957b6ab19dSGarrett Wollman 		acnt++;						\
967b6ab19dSGarrett Wollman 	for (cag = ag_corsest; cag != 0; cag = cag->ag_fine)	\
977b6ab19dSGarrett Wollman 		acnt++;						\
987b6ab19dSGarrett Wollman 	if (acnt != NUM_AG_SLOTS) {				\
997b6ab19dSGarrett Wollman 		(void)fflush(stderr);				\
1007b6ab19dSGarrett Wollman 		abort();					\
1017b6ab19dSGarrett Wollman 	}							\
1027b6ab19dSGarrett Wollman }
1037b6ab19dSGarrett Wollman #else
1047b6ab19dSGarrett Wollman #define CHECK_AG()
1057b6ab19dSGarrett Wollman #endif
1067b6ab19dSGarrett Wollman 
1077b6ab19dSGarrett Wollman 
1087b6ab19dSGarrett Wollman /* Output the contents of an aggregation table slot.
1097b6ab19dSGarrett Wollman  *	This function must always be immediately followed with the deletion
1107b6ab19dSGarrett Wollman  *	of the target slot.
1117b6ab19dSGarrett Wollman  */
1127b6ab19dSGarrett Wollman static void
1137b6ab19dSGarrett Wollman ag_out(struct ag_info *ag,
1147b6ab19dSGarrett Wollman 	 void (*out)(struct ag_info *))
1157b6ab19dSGarrett Wollman {
1167b6ab19dSGarrett Wollman 	struct ag_info *ag_cors;
1177b6ab19dSGarrett Wollman 	naddr bit;
1187b6ab19dSGarrett Wollman 
1197b6ab19dSGarrett Wollman 
1207b6ab19dSGarrett Wollman 	/* If we output both the even and odd twins, then the immediate parent,
1217b6ab19dSGarrett Wollman 	 * if it is present, is redundant, unless the parent manages to
1227b6ab19dSGarrett Wollman 	 * aggregate into something coarser.
1237b6ab19dSGarrett Wollman 	 * On successive calls, this code detects the even and odd twins,
1247b6ab19dSGarrett Wollman 	 * and marks the parent.
1257b6ab19dSGarrett Wollman 	 *
1267b6ab19dSGarrett Wollman 	 * Note that the order in which the radix tree code emits routes
1277b6ab19dSGarrett Wollman 	 * ensures that the twins are seen before the parent is emitted.
1287b6ab19dSGarrett Wollman 	 */
1297b6ab19dSGarrett Wollman 	ag_cors = ag->ag_cors;
1307b6ab19dSGarrett Wollman 	if (ag_cors != 0
1317b6ab19dSGarrett Wollman 	    && ag_cors->ag_mask == ag->ag_mask<<1
1327b6ab19dSGarrett Wollman 	    && ag_cors->ag_dst_h == (ag->ag_dst_h & ag_cors->ag_mask)) {
1337b6ab19dSGarrett Wollman 		ag_cors->ag_state |= ((ag_cors->ag_dst_h == ag->ag_dst_h)
1347b6ab19dSGarrett Wollman 				      ? AGS_REDUN0
1357b6ab19dSGarrett Wollman 				      : AGS_REDUN1);
1367b6ab19dSGarrett Wollman 	}
1377b6ab19dSGarrett Wollman 
1387b6ab19dSGarrett Wollman 	/* Skip it if this route is itself redundant.
1397b6ab19dSGarrett Wollman 	 *
1407b6ab19dSGarrett Wollman 	 * It is ok to change the contents of the slot here, since it is
1417b6ab19dSGarrett Wollman 	 * always deleted next.
1427b6ab19dSGarrett Wollman 	 */
1437b6ab19dSGarrett Wollman 	if (ag->ag_state & AGS_REDUN0) {
1447b6ab19dSGarrett Wollman 		if (ag->ag_state & AGS_REDUN1)
1457b6ab19dSGarrett Wollman 			return;
1467b6ab19dSGarrett Wollman 		bit = (-ag->ag_mask) >> 1;
1477b6ab19dSGarrett Wollman 		ag->ag_dst_h |= bit;
1487b6ab19dSGarrett Wollman 		ag->ag_mask |= bit;
1497b6ab19dSGarrett Wollman 
1507b6ab19dSGarrett Wollman 	} else if (ag->ag_state & AGS_REDUN1) {
1517b6ab19dSGarrett Wollman 		bit = (-ag->ag_mask) >> 1;
1527b6ab19dSGarrett Wollman 		ag->ag_mask |= bit;
1537b6ab19dSGarrett Wollman 	}
1547b6ab19dSGarrett Wollman 	out(ag);
1557b6ab19dSGarrett Wollman }
1567b6ab19dSGarrett Wollman 
1577b6ab19dSGarrett Wollman 
1587b6ab19dSGarrett Wollman static void
1597b6ab19dSGarrett Wollman ag_del(struct ag_info *ag)
1607b6ab19dSGarrett Wollman {
1617b6ab19dSGarrett Wollman 	CHECK_AG();
1627b6ab19dSGarrett Wollman 
1637b6ab19dSGarrett Wollman 	if (ag->ag_cors == 0)
1647b6ab19dSGarrett Wollman 		ag_corsest = ag->ag_fine;
1657b6ab19dSGarrett Wollman 	else
1667b6ab19dSGarrett Wollman 		ag->ag_cors->ag_fine = ag->ag_fine;
1677b6ab19dSGarrett Wollman 
1687b6ab19dSGarrett Wollman 	if (ag->ag_fine == 0)
1697b6ab19dSGarrett Wollman 		ag_finest = ag->ag_cors;
1707b6ab19dSGarrett Wollman 	else
1717b6ab19dSGarrett Wollman 		ag->ag_fine->ag_cors = ag->ag_cors;
1727b6ab19dSGarrett Wollman 
1737b6ab19dSGarrett Wollman 	ag->ag_fine = ag_avail;
1747b6ab19dSGarrett Wollman 	ag_avail = ag;
1757b6ab19dSGarrett Wollman 
1767b6ab19dSGarrett Wollman 	CHECK_AG();
1777b6ab19dSGarrett Wollman }
1787b6ab19dSGarrett Wollman 
1797b6ab19dSGarrett Wollman 
18090100551SPhilippe Charnier /* Flush routes waiting for aggregation.
1817b6ab19dSGarrett Wollman  *	This must not suppress a route unless it is known that among all
1827b6ab19dSGarrett Wollman  *	routes with coarser masks that match it, the one with the longest
1837b6ab19dSGarrett Wollman  *	mask is appropriate.  This is ensured by scanning the routes
18490100551SPhilippe Charnier  *	in lexical order, and with the most restrictive mask first
1857b6ab19dSGarrett Wollman  *	among routes to the same destination.
1867b6ab19dSGarrett Wollman  */
1877b6ab19dSGarrett Wollman void
1887b6ab19dSGarrett Wollman ag_flush(naddr lim_dst_h,		/* flush routes to here */
1897b6ab19dSGarrett Wollman 	 naddr lim_mask,		/* matching this mask */
1907b6ab19dSGarrett Wollman 	 void (*out)(struct ag_info *))
1917b6ab19dSGarrett Wollman {
1927b6ab19dSGarrett Wollman 	struct ag_info *ag, *ag_cors;
1937b6ab19dSGarrett Wollman 	naddr dst_h;
1947b6ab19dSGarrett Wollman 
1957b6ab19dSGarrett Wollman 
1967b6ab19dSGarrett Wollman 	for (ag = ag_finest;
1977b6ab19dSGarrett Wollman 	     ag != 0 && ag->ag_mask >= lim_mask;
1987b6ab19dSGarrett Wollman 	     ag = ag_cors) {
1997b6ab19dSGarrett Wollman 		ag_cors = ag->ag_cors;
2007b6ab19dSGarrett Wollman 
2017b6ab19dSGarrett Wollman 		/* work on only the specified routes */
2027b6ab19dSGarrett Wollman 		dst_h = ag->ag_dst_h;
2037b6ab19dSGarrett Wollman 		if ((dst_h & lim_mask) != lim_dst_h)
2047b6ab19dSGarrett Wollman 			continue;
2057b6ab19dSGarrett Wollman 
2067b6ab19dSGarrett Wollman 		if (!(ag->ag_state & AGS_SUPPRESS))
2077b6ab19dSGarrett Wollman 			ag_out(ag, out);
2087b6ab19dSGarrett Wollman 
2097b6ab19dSGarrett Wollman 		else for ( ; ; ag_cors = ag_cors->ag_cors) {
2107b6ab19dSGarrett Wollman 			/* Look for a route that can suppress the
2117b6ab19dSGarrett Wollman 			 * current route */
2127b6ab19dSGarrett Wollman 			if (ag_cors == 0) {
2137b6ab19dSGarrett Wollman 				/* failed, so output it and look for
2147b6ab19dSGarrett Wollman 				 * another route to work on
2157b6ab19dSGarrett Wollman 				 */
2167b6ab19dSGarrett Wollman 				ag_out(ag, out);
2177b6ab19dSGarrett Wollman 				break;
2187b6ab19dSGarrett Wollman 			}
2197b6ab19dSGarrett Wollman 
2207b6ab19dSGarrett Wollman 			if ((dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h) {
2217b6ab19dSGarrett Wollman 				/* We found a route with a coarser mask that
2227b6ab19dSGarrett Wollman 				 * aggregates the current target.
2237b6ab19dSGarrett Wollman 				 *
2247b6ab19dSGarrett Wollman 				 * If it has a different next hop, it
2257b6ab19dSGarrett Wollman 				 * cannot replace the target, so output
2267b6ab19dSGarrett Wollman 				 * the target.
2277b6ab19dSGarrett Wollman 				 */
2287b6ab19dSGarrett Wollman 				if (ag->ag_gate != ag_cors->ag_gate
2297b6ab19dSGarrett Wollman 				    && !(ag->ag_state & AGS_FINE_GATE)
2307b6ab19dSGarrett Wollman 				    && !(ag_cors->ag_state & AGS_CORS_GATE)) {
2317b6ab19dSGarrett Wollman 					ag_out(ag, out);
2327b6ab19dSGarrett Wollman 					break;
2337b6ab19dSGarrett Wollman 				}
2347b6ab19dSGarrett Wollman 
2357b6ab19dSGarrett Wollman 				/* If the coarse route has a good enough
2367b6ab19dSGarrett Wollman 				 * metric, it suppresses the target.
2377b6ab19dSGarrett Wollman 				 */
2387b6ab19dSGarrett Wollman 				if (ag_cors->ag_pref <= ag->ag_pref) {
2397b6ab19dSGarrett Wollman 				    if (ag_cors->ag_seqno > ag->ag_seqno)
2407b6ab19dSGarrett Wollman 					ag_cors->ag_seqno = ag->ag_seqno;
2417b6ab19dSGarrett Wollman 				    if (AG_IS_REDUN(ag->ag_state)
2427b6ab19dSGarrett Wollman 					&& ag_cors->ag_mask==ag->ag_mask<<1) {
2437b6ab19dSGarrett Wollman 					if (ag_cors->ag_dst_h == dst_h)
2447b6ab19dSGarrett Wollman 					    ag_cors->ag_state |= AGS_REDUN0;
2457b6ab19dSGarrett Wollman 					else
2467b6ab19dSGarrett Wollman 					    ag_cors->ag_state |= AGS_REDUN1;
2477b6ab19dSGarrett Wollman 				    }
2487b6ab19dSGarrett Wollman 				    if (ag->ag_tag != ag_cors->ag_tag)
2497b6ab19dSGarrett Wollman 					    ag_cors->ag_tag = 0;
2507b6ab19dSGarrett Wollman 				    if (ag->ag_nhop != ag_cors->ag_nhop)
2517b6ab19dSGarrett Wollman 					    ag_cors->ag_nhop = 0;
2527b6ab19dSGarrett Wollman 				    break;
2537b6ab19dSGarrett Wollman 				}
2547b6ab19dSGarrett Wollman 			}
2557b6ab19dSGarrett Wollman 		}
2567b6ab19dSGarrett Wollman 
2577b6ab19dSGarrett Wollman 		/* That route has either been output or suppressed */
2587b6ab19dSGarrett Wollman 		ag_cors = ag->ag_cors;
2597b6ab19dSGarrett Wollman 		ag_del(ag);
2607b6ab19dSGarrett Wollman 	}
2617b6ab19dSGarrett Wollman 
2627b6ab19dSGarrett Wollman 	CHECK_AG();
2637b6ab19dSGarrett Wollman }
2647b6ab19dSGarrett Wollman 
2657b6ab19dSGarrett Wollman 
2667b6ab19dSGarrett Wollman /* Try to aggregate a route with previous routes.
2677b6ab19dSGarrett Wollman  */
2687b6ab19dSGarrett Wollman void
2697b6ab19dSGarrett Wollman ag_check(naddr	dst,
2707b6ab19dSGarrett Wollman 	 naddr	mask,
2717b6ab19dSGarrett Wollman 	 naddr	gate,
2727b6ab19dSGarrett Wollman 	 naddr	nhop,
2737b6ab19dSGarrett Wollman 	 char	metric,
2747b6ab19dSGarrett Wollman 	 char	pref,
2757b6ab19dSGarrett Wollman 	 u_int	seqno,
2767b6ab19dSGarrett Wollman 	 u_short tag,
2777b6ab19dSGarrett Wollman 	 u_short state,
2787b6ab19dSGarrett Wollman 	 void (*out)(struct ag_info *))	/* output using this */
2797b6ab19dSGarrett Wollman {
2807b6ab19dSGarrett Wollman 	struct ag_info *ag, *nag, *ag_cors;
2817b6ab19dSGarrett Wollman 	naddr xaddr;
2827b6ab19dSGarrett Wollman 	int x;
2837b6ab19dSGarrett Wollman 
2847b6ab19dSGarrett Wollman 	NTOHL(dst);
2857b6ab19dSGarrett Wollman 
2867b6ab19dSGarrett Wollman 	/* Punt non-contiguous subnet masks.
2877b6ab19dSGarrett Wollman 	 *
2887b6ab19dSGarrett Wollman 	 * (X & -X) contains a single bit if and only if X is a power of 2.
2897b6ab19dSGarrett Wollman 	 * (X + (X & -X)) == 0 if and only if X is a power of 2.
2907b6ab19dSGarrett Wollman 	 */
2917b6ab19dSGarrett Wollman 	if ((mask & -mask) + mask != 0) {
2927b6ab19dSGarrett Wollman 		struct ag_info nc_ag;
2937b6ab19dSGarrett Wollman 
2947b6ab19dSGarrett Wollman 		nc_ag.ag_dst_h = dst;
2957b6ab19dSGarrett Wollman 		nc_ag.ag_mask = mask;
2967b6ab19dSGarrett Wollman 		nc_ag.ag_gate = gate;
2977b6ab19dSGarrett Wollman 		nc_ag.ag_nhop = nhop;
2987b6ab19dSGarrett Wollman 		nc_ag.ag_metric = metric;
2997b6ab19dSGarrett Wollman 		nc_ag.ag_pref = pref;
3007b6ab19dSGarrett Wollman 		nc_ag.ag_tag = tag;
3017b6ab19dSGarrett Wollman 		nc_ag.ag_state = state;
3027b6ab19dSGarrett Wollman 		nc_ag.ag_seqno = seqno;
3037b6ab19dSGarrett Wollman 		out(&nc_ag);
3047b6ab19dSGarrett Wollman 		return;
3057b6ab19dSGarrett Wollman 	}
3067b6ab19dSGarrett Wollman 
3077b6ab19dSGarrett Wollman 	/* Search for the right slot in the aggregation table.
3087b6ab19dSGarrett Wollman 	 */
3097b6ab19dSGarrett Wollman 	ag_cors = 0;
3107b6ab19dSGarrett Wollman 	ag = ag_corsest;
3117b6ab19dSGarrett Wollman 	while (ag != 0) {
3127b6ab19dSGarrett Wollman 		if (ag->ag_mask >= mask)
3137b6ab19dSGarrett Wollman 			break;
3147b6ab19dSGarrett Wollman 
3157b6ab19dSGarrett Wollman 		/* Suppress old routes (i.e. combine with compatible routes
3167b6ab19dSGarrett Wollman 		 * with coarser masks) as we look for the right slot in the
3177b6ab19dSGarrett Wollman 		 * aggregation table for the new route.
3187b6ab19dSGarrett Wollman 		 * A route to an address less than the current destination
3197b6ab19dSGarrett Wollman 		 * will not be affected by the current route or any route
3207b6ab19dSGarrett Wollman 		 * seen hereafter.  That means it is safe to suppress it.
32190100551SPhilippe Charnier 		 * This check keeps poor routes (e.g. with large hop counts)
32290100551SPhilippe Charnier 		 * from preventing suppression of finer routes.
3237b6ab19dSGarrett Wollman 		 */
3247b6ab19dSGarrett Wollman 		if (ag_cors != 0
3257b6ab19dSGarrett Wollman 		    && ag->ag_dst_h < dst
3267b6ab19dSGarrett Wollman 		    && (ag->ag_state & AGS_SUPPRESS)
3277b6ab19dSGarrett Wollman 		    && ag_cors->ag_pref <= ag->ag_pref
3287b6ab19dSGarrett Wollman 		    && (ag->ag_dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h
3297b6ab19dSGarrett Wollman 		    && (ag_cors->ag_gate == ag->ag_gate
3307b6ab19dSGarrett Wollman 			|| (ag->ag_state & AGS_FINE_GATE)
3317b6ab19dSGarrett Wollman 			|| (ag_cors->ag_state & AGS_CORS_GATE))) {
3327b6ab19dSGarrett Wollman 			if (ag_cors->ag_seqno > ag->ag_seqno)
3337b6ab19dSGarrett Wollman 				ag_cors->ag_seqno = ag->ag_seqno;
3347b6ab19dSGarrett Wollman 			if (AG_IS_REDUN(ag->ag_state)
3357b6ab19dSGarrett Wollman 			    && ag_cors->ag_mask==ag->ag_mask<<1) {
3367b6ab19dSGarrett Wollman 				if (ag_cors->ag_dst_h == dst)
3377b6ab19dSGarrett Wollman 					ag_cors->ag_state |= AGS_REDUN0;
3387b6ab19dSGarrett Wollman 				else
3397b6ab19dSGarrett Wollman 					ag_cors->ag_state |= AGS_REDUN1;
3407b6ab19dSGarrett Wollman 			}
3417b6ab19dSGarrett Wollman 			if (ag->ag_tag != ag_cors->ag_tag)
3427b6ab19dSGarrett Wollman 				ag_cors->ag_tag = 0;
3437b6ab19dSGarrett Wollman 			if (ag->ag_nhop != ag_cors->ag_nhop)
3447b6ab19dSGarrett Wollman 				ag_cors->ag_nhop = 0;
3457b6ab19dSGarrett Wollman 			ag_del(ag);
3467b6ab19dSGarrett Wollman 			CHECK_AG();
3477b6ab19dSGarrett Wollman 		} else {
3487b6ab19dSGarrett Wollman 			ag_cors = ag;
3497b6ab19dSGarrett Wollman 		}
3507b6ab19dSGarrett Wollman 		ag = ag_cors->ag_fine;
3517b6ab19dSGarrett Wollman 	}
3527b6ab19dSGarrett Wollman 
3537b6ab19dSGarrett Wollman 	/* If we find the even/odd twin of the new route, and if the
3547b6ab19dSGarrett Wollman 	 * masks and so forth are equal, we can aggregate them.
3557b6ab19dSGarrett Wollman 	 * We can probably promote one of the pair.
3567b6ab19dSGarrett Wollman 	 *
3577b6ab19dSGarrett Wollman 	 * Since the routes are encountered in lexical order,
3587b6ab19dSGarrett Wollman 	 * the new route must be odd.  However, the second or later
3597b6ab19dSGarrett Wollman 	 * times around this loop, it could be the even twin promoted
3607b6ab19dSGarrett Wollman 	 * from the even/odd pair of twins of the finer route.
3617b6ab19dSGarrett Wollman 	 */
3627b6ab19dSGarrett Wollman 	while (ag != 0
3637b6ab19dSGarrett Wollman 	       && ag->ag_mask == mask
3647b6ab19dSGarrett Wollman 	       && ((ag->ag_dst_h ^ dst) & (mask<<1)) == 0) {
3657b6ab19dSGarrett Wollman 
3667b6ab19dSGarrett Wollman 		/* Here we know the target route and the route in the current
3677b6ab19dSGarrett Wollman 		 * slot have the same netmasks and differ by at most the
3687b6ab19dSGarrett Wollman 		 * last bit.  They are either for the same destination, or
3697b6ab19dSGarrett Wollman 		 * for an even/odd pair of destinations.
3707b6ab19dSGarrett Wollman 		 */
3717b6ab19dSGarrett Wollman 		if (ag->ag_dst_h == dst) {
3727b6ab19dSGarrett Wollman 			/* We have two routes to the same destination.
3737b6ab19dSGarrett Wollman 			 * Routes are encountered in lexical order, so a
3747b6ab19dSGarrett Wollman 			 * route is never promoted until the parent route is
3757b6ab19dSGarrett Wollman 			 * already present.  So we know that the new route is
3767b6ab19dSGarrett Wollman 			 * a promoted pair and the route already in the slot
3777b6ab19dSGarrett Wollman 			 * is the explicit route.
3787b6ab19dSGarrett Wollman 			 *
3797b6ab19dSGarrett Wollman 			 * Prefer the best route if their metrics differ,
3807b6ab19dSGarrett Wollman 			 * or the promoted one if not, following a sort
3817b6ab19dSGarrett Wollman 			 * of longest-match rule.
3827b6ab19dSGarrett Wollman 			 */
3837b6ab19dSGarrett Wollman 			if (pref <= ag->ag_pref) {
3847b6ab19dSGarrett Wollman 				ag->ag_gate = gate;
3857b6ab19dSGarrett Wollman 				ag->ag_nhop = nhop;
3867b6ab19dSGarrett Wollman 				ag->ag_tag = tag;
3877b6ab19dSGarrett Wollman 				ag->ag_metric = metric;
3887b6ab19dSGarrett Wollman 				ag->ag_pref = pref;
3897b6ab19dSGarrett Wollman 				x = ag->ag_state;
3907b6ab19dSGarrett Wollman 				ag->ag_state = state;
3917b6ab19dSGarrett Wollman 				state = x;
3927b6ab19dSGarrett Wollman 			}
3937b6ab19dSGarrett Wollman 
3947b6ab19dSGarrett Wollman 			/* The sequence number controls flash updating,
3957b6ab19dSGarrett Wollman 			 * and should be the smaller of the two.
3967b6ab19dSGarrett Wollman 			 */
3977b6ab19dSGarrett Wollman 			if (ag->ag_seqno > seqno)
3987b6ab19dSGarrett Wollman 				ag->ag_seqno = seqno;
3997b6ab19dSGarrett Wollman 
4007b6ab19dSGarrett Wollman 			/* some bits are set if they are set on either route */
4017b6ab19dSGarrett Wollman 			ag->ag_state |= (state & (AGS_PROMOTE_EITHER
4027b6ab19dSGarrett Wollman 						  | AGS_REDUN0 | AGS_REDUN1));
4037b6ab19dSGarrett Wollman 			return;
4047b6ab19dSGarrett Wollman 		}
4057b6ab19dSGarrett Wollman 
4067b6ab19dSGarrett Wollman 		/* If one of the routes can be promoted and the other can
4077b6ab19dSGarrett Wollman 		 * be suppressed, it may be possible to combine them or
4087b6ab19dSGarrett Wollman 		 * worthwhile to promote one.
4097b6ab19dSGarrett Wollman 		 *
4107b6ab19dSGarrett Wollman 		 * Note that any route that can be promoted is always
4117b6ab19dSGarrett Wollman 		 * marked to be eligible to be suppressed.
4127b6ab19dSGarrett Wollman 		 */
4137b6ab19dSGarrett Wollman 		if (!((state & AGS_PROMOTE)
4147b6ab19dSGarrett Wollman 		      && (ag->ag_state & AGS_SUPPRESS))
4157b6ab19dSGarrett Wollman 		    && !((ag->ag_state & AGS_PROMOTE)
4167b6ab19dSGarrett Wollman 			 && (state & AGS_SUPPRESS)))
4177b6ab19dSGarrett Wollman 			break;
4187b6ab19dSGarrett Wollman 
4197b6ab19dSGarrett Wollman 		/* A pair of even/odd twin routes can be combined
4207b6ab19dSGarrett Wollman 		 * if either is redundant, or if they are via the
4217b6ab19dSGarrett Wollman 		 * same gateway and have the same metric.
4227b6ab19dSGarrett Wollman 		 */
4237b6ab19dSGarrett Wollman 		if (AG_IS_REDUN(ag->ag_state)
4247b6ab19dSGarrett Wollman 		    || AG_IS_REDUN(state)
4257b6ab19dSGarrett Wollman 		    || (ag->ag_gate == gate
4267b6ab19dSGarrett Wollman 			&& ag->ag_pref == pref
4277b6ab19dSGarrett Wollman 			&& (state & ag->ag_state & AGS_PROMOTE) != 0)) {
4287b6ab19dSGarrett Wollman 
4297b6ab19dSGarrett Wollman 			/* We have both the even and odd pairs.
4307b6ab19dSGarrett Wollman 			 * Since the routes are encountered in order,
4317b6ab19dSGarrett Wollman 			 * the route in the slot must be the even twin.
4327b6ab19dSGarrett Wollman 			 *
4337b6ab19dSGarrett Wollman 			 * Combine and promote the pair of routes.
4347b6ab19dSGarrett Wollman 			 */
4357b6ab19dSGarrett Wollman 			if (seqno > ag->ag_seqno)
4367b6ab19dSGarrett Wollman 				seqno = ag->ag_seqno;
4377b6ab19dSGarrett Wollman 			if (!AG_IS_REDUN(state))
4387b6ab19dSGarrett Wollman 				state &= ~AGS_REDUN1;
4397b6ab19dSGarrett Wollman 			if (AG_IS_REDUN(ag->ag_state))
4407b6ab19dSGarrett Wollman 				state |= AGS_REDUN0;
4417b6ab19dSGarrett Wollman 			else
4427b6ab19dSGarrett Wollman 				state &= ~AGS_REDUN0;
4437b6ab19dSGarrett Wollman 			state |= (ag->ag_state & AGS_PROMOTE_EITHER);
4447b6ab19dSGarrett Wollman 			if (ag->ag_tag != tag)
4457b6ab19dSGarrett Wollman 				tag = 0;
4467b6ab19dSGarrett Wollman 			if (ag->ag_nhop != nhop)
4477b6ab19dSGarrett Wollman 				nhop = 0;
4487b6ab19dSGarrett Wollman 
4497b6ab19dSGarrett Wollman 			/* Get rid of the even twin that was already
4507b6ab19dSGarrett Wollman 			 * in the slot.
4517b6ab19dSGarrett Wollman 			 */
4527b6ab19dSGarrett Wollman 			ag_del(ag);
4537b6ab19dSGarrett Wollman 
4547b6ab19dSGarrett Wollman 		} else if (ag->ag_pref >= pref
4557b6ab19dSGarrett Wollman 			   && (ag->ag_state & AGS_PROMOTE)) {
4567b6ab19dSGarrett Wollman 			/* If we cannot combine the pair, maybe the route
4577b6ab19dSGarrett Wollman 			 * with the worse metric can be promoted.
4587b6ab19dSGarrett Wollman 			 *
4597b6ab19dSGarrett Wollman 			 * Promote the old, even twin, by giving its slot
4607b6ab19dSGarrett Wollman 			 * in the table to the new, odd twin.
4617b6ab19dSGarrett Wollman 			 */
4627b6ab19dSGarrett Wollman 			ag->ag_dst_h = dst;
4637b6ab19dSGarrett Wollman 
4647b6ab19dSGarrett Wollman 			xaddr = ag->ag_gate;
4657b6ab19dSGarrett Wollman 			ag->ag_gate = gate;
4667b6ab19dSGarrett Wollman 			gate = xaddr;
4677b6ab19dSGarrett Wollman 
4687b6ab19dSGarrett Wollman 			xaddr = ag->ag_nhop;
4697b6ab19dSGarrett Wollman 			ag->ag_nhop = nhop;
4707b6ab19dSGarrett Wollman 			nhop = xaddr;
4717b6ab19dSGarrett Wollman 
4727b6ab19dSGarrett Wollman 			x = ag->ag_tag;
4737b6ab19dSGarrett Wollman 			ag->ag_tag = tag;
4747b6ab19dSGarrett Wollman 			tag = x;
4757b6ab19dSGarrett Wollman 
4767b6ab19dSGarrett Wollman 			x = ag->ag_state;
4777b6ab19dSGarrett Wollman 			ag->ag_state = state;
4787b6ab19dSGarrett Wollman 			state = x;
4797b6ab19dSGarrett Wollman 			if (!AG_IS_REDUN(state))
4807b6ab19dSGarrett Wollman 				state &= ~AGS_REDUN0;
4817b6ab19dSGarrett Wollman 
4827b6ab19dSGarrett Wollman 			x = ag->ag_metric;
4837b6ab19dSGarrett Wollman 			ag->ag_metric = metric;
4847b6ab19dSGarrett Wollman 			metric = x;
4857b6ab19dSGarrett Wollman 
4867b6ab19dSGarrett Wollman 			x = ag->ag_pref;
4877b6ab19dSGarrett Wollman 			ag->ag_pref = pref;
4887b6ab19dSGarrett Wollman 			pref = x;
4897b6ab19dSGarrett Wollman 
4907b6ab19dSGarrett Wollman 			if (seqno >= ag->ag_seqno)
4917b6ab19dSGarrett Wollman 				seqno = ag->ag_seqno;
4927b6ab19dSGarrett Wollman 			else
4937b6ab19dSGarrett Wollman 				ag->ag_seqno = seqno;
4947b6ab19dSGarrett Wollman 
4957b6ab19dSGarrett Wollman 		} else {
4967b6ab19dSGarrett Wollman 			if (!(state & AGS_PROMOTE))
4977b6ab19dSGarrett Wollman 				break;	/* cannot promote either twin */
4987b6ab19dSGarrett Wollman 
4997b6ab19dSGarrett Wollman 			/* promote the new, odd twin by shaving its
5007b6ab19dSGarrett Wollman 			 * mask and address.
5017b6ab19dSGarrett Wollman 			 */
5027b6ab19dSGarrett Wollman 			if (seqno > ag->ag_seqno)
5037b6ab19dSGarrett Wollman 				seqno = ag->ag_seqno;
5047b6ab19dSGarrett Wollman 			else
5057b6ab19dSGarrett Wollman 				ag->ag_seqno = seqno;
5067b6ab19dSGarrett Wollman 			if (!AG_IS_REDUN(state))
5077b6ab19dSGarrett Wollman 				state &= ~AGS_REDUN1;
5087b6ab19dSGarrett Wollman 		}
5097b6ab19dSGarrett Wollman 
5107b6ab19dSGarrett Wollman 		mask <<= 1;
5117b6ab19dSGarrett Wollman 		dst &= mask;
5127b6ab19dSGarrett Wollman 
5137b6ab19dSGarrett Wollman 		if (ag_cors == 0) {
5147b6ab19dSGarrett Wollman 			ag = ag_corsest;
5157b6ab19dSGarrett Wollman 			break;
5167b6ab19dSGarrett Wollman 		}
5177b6ab19dSGarrett Wollman 		ag = ag_cors;
5187b6ab19dSGarrett Wollman 		ag_cors = ag->ag_cors;
5197b6ab19dSGarrett Wollman 	}
5207b6ab19dSGarrett Wollman 
5217b6ab19dSGarrett Wollman 	/* When we can no longer promote and combine routes,
5227b6ab19dSGarrett Wollman 	 * flush the old route in the target slot.  Also flush
5237b6ab19dSGarrett Wollman 	 * any finer routes that we know will never be aggregated by
5247b6ab19dSGarrett Wollman 	 * the new route.
5257b6ab19dSGarrett Wollman 	 *
5267b6ab19dSGarrett Wollman 	 * In case we moved toward coarser masks,
5277b6ab19dSGarrett Wollman 	 * get back where we belong
5287b6ab19dSGarrett Wollman 	 */
5297b6ab19dSGarrett Wollman 	if (ag != 0
5307b6ab19dSGarrett Wollman 	    && ag->ag_mask < mask) {
5317b6ab19dSGarrett Wollman 		ag_cors = ag;
5327b6ab19dSGarrett Wollman 		ag = ag->ag_fine;
5337b6ab19dSGarrett Wollman 	}
5347b6ab19dSGarrett Wollman 
5357b6ab19dSGarrett Wollman 	/* Empty the target slot
5367b6ab19dSGarrett Wollman 	 */
5377b6ab19dSGarrett Wollman 	if (ag != 0 && ag->ag_mask == mask) {
5387b6ab19dSGarrett Wollman 		ag_flush(ag->ag_dst_h, ag->ag_mask, out);
5397b6ab19dSGarrett Wollman 		ag = (ag_cors == 0) ? ag_corsest : ag_cors->ag_fine;
5407b6ab19dSGarrett Wollman 	}
5417b6ab19dSGarrett Wollman 
5427b6ab19dSGarrett Wollman #ifdef DEBUG_AG
5437b6ab19dSGarrett Wollman 	(void)fflush(stderr);
5447b6ab19dSGarrett Wollman 	if (ag == 0 && ag_cors != ag_finest)
5457b6ab19dSGarrett Wollman 		abort();
5467b6ab19dSGarrett Wollman 	if (ag_cors == 0 && ag != ag_corsest)
5477b6ab19dSGarrett Wollman 		abort();
5487b6ab19dSGarrett Wollman 	if (ag != 0 && ag->ag_cors != ag_cors)
5497b6ab19dSGarrett Wollman 		abort();
5507b6ab19dSGarrett Wollman 	if (ag_cors != 0 && ag_cors->ag_fine != ag)
5517b6ab19dSGarrett Wollman 		abort();
5527b6ab19dSGarrett Wollman 	CHECK_AG();
5537b6ab19dSGarrett Wollman #endif
5547b6ab19dSGarrett Wollman 
5557b6ab19dSGarrett Wollman 	/* Save the new route on the end of the table.
5567b6ab19dSGarrett Wollman 	 */
5577b6ab19dSGarrett Wollman 	nag = ag_avail;
5587b6ab19dSGarrett Wollman 	ag_avail = nag->ag_fine;
5597b6ab19dSGarrett Wollman 
5607b6ab19dSGarrett Wollman 	nag->ag_dst_h = dst;
5617b6ab19dSGarrett Wollman 	nag->ag_mask = mask;
5627b6ab19dSGarrett Wollman 	nag->ag_gate = gate;
5637b6ab19dSGarrett Wollman 	nag->ag_nhop = nhop;
5647b6ab19dSGarrett Wollman 	nag->ag_metric = metric;
5657b6ab19dSGarrett Wollman 	nag->ag_pref = pref;
5667b6ab19dSGarrett Wollman 	nag->ag_tag = tag;
5677b6ab19dSGarrett Wollman 	nag->ag_state = state;
5687b6ab19dSGarrett Wollman 	nag->ag_seqno = seqno;
5697b6ab19dSGarrett Wollman 
5707b6ab19dSGarrett Wollman 	nag->ag_fine = ag;
5717b6ab19dSGarrett Wollman 	if (ag != 0)
5727b6ab19dSGarrett Wollman 		ag->ag_cors = nag;
5737b6ab19dSGarrett Wollman 	else
5747b6ab19dSGarrett Wollman 		ag_finest = nag;
5757b6ab19dSGarrett Wollman 	nag->ag_cors = ag_cors;
5767b6ab19dSGarrett Wollman 	if (ag_cors == 0)
5777b6ab19dSGarrett Wollman 		ag_corsest = nag;
5787b6ab19dSGarrett Wollman 	else
5797b6ab19dSGarrett Wollman 		ag_cors->ag_fine = nag;
5807b6ab19dSGarrett Wollman 	CHECK_AG();
5817b6ab19dSGarrett Wollman }
5827b6ab19dSGarrett Wollman 
5837b6ab19dSGarrett Wollman 
5847b6ab19dSGarrett Wollman static char *
5857b6ab19dSGarrett Wollman rtm_type_name(u_char type)
5867b6ab19dSGarrett Wollman {
5877b6ab19dSGarrett Wollman 	static char *rtm_types[] = {
5887b6ab19dSGarrett Wollman 		"RTM_ADD",
5897b6ab19dSGarrett Wollman 		"RTM_DELETE",
5907b6ab19dSGarrett Wollman 		"RTM_CHANGE",
5917b6ab19dSGarrett Wollman 		"RTM_GET",
5927b6ab19dSGarrett Wollman 		"RTM_LOSING",
5937b6ab19dSGarrett Wollman 		"RTM_REDIRECT",
5947b6ab19dSGarrett Wollman 		"RTM_MISS",
5957b6ab19dSGarrett Wollman 		"RTM_LOCK",
5967b6ab19dSGarrett Wollman 		"RTM_OLDADD",
5977b6ab19dSGarrett Wollman 		"RTM_OLDDEL",
5987b6ab19dSGarrett Wollman 		"RTM_RESOLVE",
5997b6ab19dSGarrett Wollman 		"RTM_NEWADDR",
6007b6ab19dSGarrett Wollman 		"RTM_DELADDR",
6017b6ab19dSGarrett Wollman 		"RTM_IFINFO"
6027b6ab19dSGarrett Wollman 	};
6037b6ab19dSGarrett Wollman 	static char name0[10];
6047b6ab19dSGarrett Wollman 
6057b6ab19dSGarrett Wollman 
6067b6ab19dSGarrett Wollman 	if (type > sizeof(rtm_types)/sizeof(rtm_types[0])
6077b6ab19dSGarrett Wollman 	    || type == 0) {
6087b6ab19dSGarrett Wollman 		sprintf(name0, "RTM type %#x", type);
6097b6ab19dSGarrett Wollman 		return name0;
6107b6ab19dSGarrett Wollman 	} else {
6117b6ab19dSGarrett Wollman 		return rtm_types[type-1];
6127b6ab19dSGarrett Wollman 	}
6137b6ab19dSGarrett Wollman }
6147b6ab19dSGarrett Wollman 
6157b6ab19dSGarrett Wollman 
6167b6ab19dSGarrett Wollman /* Trim a mask in a sockaddr
617a455644fSJulian Elischer  *	Produce the index of the first zero byte.
618a455644fSJulian Elischer  *	i.e. Produce a index of 4 for an mask of 0. (default route)
6197b6ab19dSGarrett Wollman  */
6207b6ab19dSGarrett Wollman void
6217b6ab19dSGarrett Wollman #ifdef _HAVE_SIN_LEN
6227b6ab19dSGarrett Wollman masktrim(struct sockaddr_in *ap)
6237b6ab19dSGarrett Wollman #else
6247b6ab19dSGarrett Wollman masktrim(struct sockaddr_in_new *ap)
6257b6ab19dSGarrett Wollman #endif
6267b6ab19dSGarrett Wollman {
6277b6ab19dSGarrett Wollman 	register char *cp;
6287b6ab19dSGarrett Wollman 
629a455644fSJulian Elischer 	ap->sin_port = 0xffff; /* buffer zone for default route */
6307b6ab19dSGarrett Wollman 	cp = (char *)(&ap->sin_addr.s_addr+1);
6317b6ab19dSGarrett Wollman 	while (*--cp == 0)
6327b6ab19dSGarrett Wollman 		continue;
633a455644fSJulian Elischer 	/*ap->sin_port = 0x0;*/ /* may not be needed (who cares?)*/
6347b6ab19dSGarrett Wollman 	ap->sin_len = cp - (char*)ap + 1;
6357b6ab19dSGarrett Wollman }
6367b6ab19dSGarrett Wollman 
6377b6ab19dSGarrett Wollman 
6387b6ab19dSGarrett Wollman /* Tell the kernel to add, delete or change a route
6397b6ab19dSGarrett Wollman  */
6407b6ab19dSGarrett Wollman static void
6417b6ab19dSGarrett Wollman rtioctl(int action,			/* RTM_DELETE, etc */
6427b6ab19dSGarrett Wollman 	naddr dst,
6437b6ab19dSGarrett Wollman 	naddr gate,
6447b6ab19dSGarrett Wollman 	naddr mask,
6457b6ab19dSGarrett Wollman 	int metric,
6467b6ab19dSGarrett Wollman 	int flags)
6477b6ab19dSGarrett Wollman {
6487b6ab19dSGarrett Wollman 	struct {
6497b6ab19dSGarrett Wollman 		struct rt_msghdr w_rtm;
6507b6ab19dSGarrett Wollman 		struct sockaddr_in w_dst;
6517b6ab19dSGarrett Wollman 		struct sockaddr_in w_gate;
6527b6ab19dSGarrett Wollman #ifdef _HAVE_SA_LEN
6537b6ab19dSGarrett Wollman 		struct sockaddr_in w_mask;
6547b6ab19dSGarrett Wollman #else
6557b6ab19dSGarrett Wollman 		struct sockaddr_in_new w_mask;
6567b6ab19dSGarrett Wollman #endif
6577b6ab19dSGarrett Wollman 	} w;
6587b6ab19dSGarrett Wollman 	long cc;
6597b6ab19dSGarrett Wollman 
6607b6ab19dSGarrett Wollman again:
6617b6ab19dSGarrett Wollman 	bzero(&w, sizeof(w));
6627b6ab19dSGarrett Wollman 	w.w_rtm.rtm_msglen = sizeof(w);
6637b6ab19dSGarrett Wollman 	w.w_rtm.rtm_version = RTM_VERSION;
6647b6ab19dSGarrett Wollman 	w.w_rtm.rtm_type = action;
6657b6ab19dSGarrett Wollman 	w.w_rtm.rtm_flags = flags;
6667b6ab19dSGarrett Wollman 	w.w_rtm.rtm_seq = ++rt_sock_seqno;
6677b6ab19dSGarrett Wollman 	w.w_rtm.rtm_addrs = RTA_DST|RTA_GATEWAY;
6687b6ab19dSGarrett Wollman 	if (metric != 0) {
6697b6ab19dSGarrett Wollman 		w.w_rtm.rtm_rmx.rmx_hopcount = metric;
6707b6ab19dSGarrett Wollman 		w.w_rtm.rtm_inits |= RTV_HOPCOUNT;
6717b6ab19dSGarrett Wollman 	}
6727b6ab19dSGarrett Wollman 	w.w_dst.sin_family = AF_INET;
6737b6ab19dSGarrett Wollman 	w.w_dst.sin_addr.s_addr = dst;
6747b6ab19dSGarrett Wollman 	w.w_gate.sin_family = AF_INET;
6757b6ab19dSGarrett Wollman 	w.w_gate.sin_addr.s_addr = gate;
6767b6ab19dSGarrett Wollman #ifdef _HAVE_SA_LEN
6777b6ab19dSGarrett Wollman 	w.w_dst.sin_len = sizeof(w.w_dst);
6787b6ab19dSGarrett Wollman 	w.w_gate.sin_len = sizeof(w.w_gate);
6797b6ab19dSGarrett Wollman #endif
6807b6ab19dSGarrett Wollman 	if (mask == HOST_MASK) {
6817b6ab19dSGarrett Wollman 		w.w_rtm.rtm_flags |= RTF_HOST;
6827b6ab19dSGarrett Wollman 		w.w_rtm.rtm_msglen -= sizeof(w.w_mask);
6837b6ab19dSGarrett Wollman 	} else {
6847b6ab19dSGarrett Wollman 		w.w_rtm.rtm_addrs |= RTA_NETMASK;
6857b6ab19dSGarrett Wollman 		w.w_mask.sin_addr.s_addr = htonl(mask);
6867b6ab19dSGarrett Wollman #ifdef _HAVE_SA_LEN
6877b6ab19dSGarrett Wollman 		masktrim(&w.w_mask);
6887b6ab19dSGarrett Wollman 		w.w_rtm.rtm_msglen -= (sizeof(w.w_mask) - w.w_mask.sin_len);
6897b6ab19dSGarrett Wollman #endif
6907b6ab19dSGarrett Wollman 	}
6917b6ab19dSGarrett Wollman 
6927b6ab19dSGarrett Wollman 	if (TRACEKERNEL)
6937b6ab19dSGarrett Wollman 		trace_kernel("write kernel %s %s->%s metric=%d flags=%#x\n",
6947b6ab19dSGarrett Wollman 			     rtm_type_name(action),
6957b6ab19dSGarrett Wollman 			     addrname(dst, mask, 0), naddr_ntoa(gate),
6967b6ab19dSGarrett Wollman 			     metric, flags);
6977b6ab19dSGarrett Wollman 
6987b6ab19dSGarrett Wollman #ifndef NO_INSTALL
6997b6ab19dSGarrett Wollman 	cc = write(rt_sock, &w, w.w_rtm.rtm_msglen);
7007b6ab19dSGarrett Wollman 	if (cc == w.w_rtm.rtm_msglen)
7017b6ab19dSGarrett Wollman 		return;
7027b6ab19dSGarrett Wollman 	if (cc < 0) {
7037b6ab19dSGarrett Wollman 		if (errno == ESRCH
7047b6ab19dSGarrett Wollman 		    && (action == RTM_CHANGE || action == RTM_DELETE)) {
70552ad6021SGarrett Wollman 			trace_act("route to %s disappeared before %s",
7067b6ab19dSGarrett Wollman 				  addrname(dst, mask, 0),
7077b6ab19dSGarrett Wollman 				  rtm_type_name(action));
7087b6ab19dSGarrett Wollman 			if (action == RTM_CHANGE) {
7097b6ab19dSGarrett Wollman 				action = RTM_ADD;
7107b6ab19dSGarrett Wollman 				goto again;
7117b6ab19dSGarrett Wollman 			}
7127b6ab19dSGarrett Wollman 			return;
7137b6ab19dSGarrett Wollman 		}
7147b6ab19dSGarrett Wollman 		msglog("write(rt_sock) %s %s --> %s: %s",
7157b6ab19dSGarrett Wollman 		       rtm_type_name(action),
7167b6ab19dSGarrett Wollman 		       addrname(dst, mask, 0), naddr_ntoa(gate),
7177b6ab19dSGarrett Wollman 		       strerror(errno));
7187b6ab19dSGarrett Wollman 	} else {
7197b6ab19dSGarrett Wollman 		msglog("write(rt_sock) wrote %d instead of %d",
7207b6ab19dSGarrett Wollman 		       cc, w.w_rtm.rtm_msglen);
7217b6ab19dSGarrett Wollman 	}
7227b6ab19dSGarrett Wollman #endif
7237b6ab19dSGarrett Wollman }
7247b6ab19dSGarrett Wollman 
7257b6ab19dSGarrett Wollman 
7267b6ab19dSGarrett Wollman #define KHASH_SIZE 71			/* should be prime */
7277b6ab19dSGarrett Wollman #define KHASH(a,m) khash_bins[((a) ^ (m)) % KHASH_SIZE]
7287b6ab19dSGarrett Wollman static struct khash {
7297b6ab19dSGarrett Wollman 	struct khash *k_next;
7307b6ab19dSGarrett Wollman 	naddr	k_dst;
7317b6ab19dSGarrett Wollman 	naddr	k_mask;
7327b6ab19dSGarrett Wollman 	naddr	k_gate;
7337b6ab19dSGarrett Wollman 	short	k_metric;
7347b6ab19dSGarrett Wollman 	u_short	k_state;
7357b6ab19dSGarrett Wollman #define	    KS_NEW	0x001
7367b6ab19dSGarrett Wollman #define	    KS_DELETE	0x002
7377b6ab19dSGarrett Wollman #define	    KS_ADD	0x004		/* add to the kernel */
7387b6ab19dSGarrett Wollman #define	    KS_CHANGE	0x008		/* tell kernel to change the route */
7397b6ab19dSGarrett Wollman #define	    KS_DEL_ADD	0x010		/* delete & add to change the kernel */
7407b6ab19dSGarrett Wollman #define	    KS_STATIC	0x020		/* Static flag in kernel */
7417b6ab19dSGarrett Wollman #define	    KS_GATEWAY	0x040		/* G flag in kernel */
7427b6ab19dSGarrett Wollman #define	    KS_DYNAMIC	0x080		/* result of redirect */
7437b6ab19dSGarrett Wollman #define	    KS_DELETED	0x100		/* already deleted */
7447b6ab19dSGarrett Wollman 	time_t	k_keep;
7457b6ab19dSGarrett Wollman #define	    K_KEEP_LIM	30
746a30febecSGarrett Wollman 	time_t	k_redirect_time;	/* when redirected route 1st seen */
7477b6ab19dSGarrett Wollman } *khash_bins[KHASH_SIZE];
7487b6ab19dSGarrett Wollman 
7497b6ab19dSGarrett Wollman 
7507b6ab19dSGarrett Wollman static struct khash*
7517b6ab19dSGarrett Wollman kern_find(naddr dst, naddr mask, struct khash ***ppk)
7527b6ab19dSGarrett Wollman {
7537b6ab19dSGarrett Wollman 	struct khash *k, **pk;
7547b6ab19dSGarrett Wollman 
7557b6ab19dSGarrett Wollman 	for (pk = &KHASH(dst,mask); (k = *pk) != 0; pk = &k->k_next) {
7567b6ab19dSGarrett Wollman 		if (k->k_dst == dst && k->k_mask == mask)
7577b6ab19dSGarrett Wollman 			break;
7587b6ab19dSGarrett Wollman 	}
7597b6ab19dSGarrett Wollman 	if (ppk != 0)
7607b6ab19dSGarrett Wollman 		*ppk = pk;
7617b6ab19dSGarrett Wollman 	return k;
7627b6ab19dSGarrett Wollman }
7637b6ab19dSGarrett Wollman 
7647b6ab19dSGarrett Wollman 
7657b6ab19dSGarrett Wollman static struct khash*
7667b6ab19dSGarrett Wollman kern_add(naddr dst, naddr mask)
7677b6ab19dSGarrett Wollman {
7687b6ab19dSGarrett Wollman 	struct khash *k, **pk;
7697b6ab19dSGarrett Wollman 
7707b6ab19dSGarrett Wollman 	k = kern_find(dst, mask, &pk);
7717b6ab19dSGarrett Wollman 	if (k != 0)
7727b6ab19dSGarrett Wollman 		return k;
7737b6ab19dSGarrett Wollman 
77490100551SPhilippe Charnier 	k = (struct khash *)rtmalloc(sizeof(*k), "kern_add");
7757b6ab19dSGarrett Wollman 
7767b6ab19dSGarrett Wollman 	bzero(k, sizeof(*k));
7777b6ab19dSGarrett Wollman 	k->k_dst = dst;
7787b6ab19dSGarrett Wollman 	k->k_mask = mask;
7797b6ab19dSGarrett Wollman 	k->k_state = KS_NEW;
7807b6ab19dSGarrett Wollman 	k->k_keep = now.tv_sec;
7817b6ab19dSGarrett Wollman 	*pk = k;
7827b6ab19dSGarrett Wollman 
7837b6ab19dSGarrett Wollman 	return k;
7847b6ab19dSGarrett Wollman }
7857b6ab19dSGarrett Wollman 
7867b6ab19dSGarrett Wollman 
7877b6ab19dSGarrett Wollman /* If a kernel route has a non-zero metric, check that it is still in the
7887b6ab19dSGarrett Wollman  *	daemon table, and not deleted by interfaces coming and going.
7897b6ab19dSGarrett Wollman  */
7907b6ab19dSGarrett Wollman static void
7917b6ab19dSGarrett Wollman kern_check_static(struct khash *k,
7927b6ab19dSGarrett Wollman 		  struct interface *ifp)
7937b6ab19dSGarrett Wollman {
7947b6ab19dSGarrett Wollman 	struct rt_entry *rt;
7957b6ab19dSGarrett Wollman 	naddr int_addr;
7967b6ab19dSGarrett Wollman 
7977b6ab19dSGarrett Wollman 	if (k->k_metric == 0)
7987b6ab19dSGarrett Wollman 		return;
7997b6ab19dSGarrett Wollman 
8007b6ab19dSGarrett Wollman 	int_addr = (ifp != 0) ? ifp->int_addr : loopaddr;
8017b6ab19dSGarrett Wollman 
8027b6ab19dSGarrett Wollman 	rt = rtget(k->k_dst, k->k_mask);
8037b6ab19dSGarrett Wollman 	if (rt != 0) {
8047b6ab19dSGarrett Wollman 		if (!(rt->rt_state & RS_STATIC))
8057b6ab19dSGarrett Wollman 			rtchange(rt, rt->rt_state | RS_STATIC,
8067b6ab19dSGarrett Wollman 				 k->k_gate, int_addr,
8077b6ab19dSGarrett Wollman 				 k->k_metric, 0, ifp, now.tv_sec, 0);
8087b6ab19dSGarrett Wollman 	} else {
8097b6ab19dSGarrett Wollman 		rtadd(k->k_dst, k->k_mask, k->k_gate, int_addr,
8107b6ab19dSGarrett Wollman 		      k->k_metric, 0, RS_STATIC, ifp);
8117b6ab19dSGarrett Wollman 	}
8127b6ab19dSGarrett Wollman }
8137b6ab19dSGarrett Wollman 
8147b6ab19dSGarrett Wollman 
8157b6ab19dSGarrett Wollman /* add a route the kernel told us
8167b6ab19dSGarrett Wollman  */
8177b6ab19dSGarrett Wollman static void
8187b6ab19dSGarrett Wollman rtm_add(struct rt_msghdr *rtm,
8197b6ab19dSGarrett Wollman 	struct rt_addrinfo *info,
8207b6ab19dSGarrett Wollman 	time_t keep)
8217b6ab19dSGarrett Wollman {
8227b6ab19dSGarrett Wollman 	struct khash *k;
8237b6ab19dSGarrett Wollman 	struct interface *ifp;
8247b6ab19dSGarrett Wollman 	naddr mask;
8257b6ab19dSGarrett Wollman 
8267b6ab19dSGarrett Wollman 
8277b6ab19dSGarrett Wollman 	if (rtm->rtm_flags & RTF_HOST) {
8287b6ab19dSGarrett Wollman 		mask = HOST_MASK;
8297b6ab19dSGarrett Wollman 	} else if (INFO_MASK(info) != 0) {
8307b6ab19dSGarrett Wollman 		mask = ntohl(S_ADDR(INFO_MASK(info)));
8317b6ab19dSGarrett Wollman 	} else {
832a30febecSGarrett Wollman 		msglog("ignore %s without mask", rtm_type_name(rtm->rtm_type));
8337b6ab19dSGarrett Wollman 		return;
8347b6ab19dSGarrett Wollman 	}
8357b6ab19dSGarrett Wollman 
8367b6ab19dSGarrett Wollman 	if (INFO_GATE(info) == 0
8377b6ab19dSGarrett Wollman 	    || INFO_GATE(info)->sa_family != AF_INET) {
83852ad6021SGarrett Wollman 		msglog("ignore %s without gateway",
8397b6ab19dSGarrett Wollman 		       rtm_type_name(rtm->rtm_type));
8407b6ab19dSGarrett Wollman 		return;
8417b6ab19dSGarrett Wollman 	}
8427b6ab19dSGarrett Wollman 
8437b6ab19dSGarrett Wollman 	k = kern_add(S_ADDR(INFO_DST(info)), mask);
8447b6ab19dSGarrett Wollman 	if (k->k_state & KS_NEW)
8457b6ab19dSGarrett Wollman 		k->k_keep = now.tv_sec+keep;
8467b6ab19dSGarrett Wollman 	k->k_gate = S_ADDR(INFO_GATE(info));
8477b6ab19dSGarrett Wollman 	k->k_metric = rtm->rtm_rmx.rmx_hopcount;
8487b6ab19dSGarrett Wollman 	if (k->k_metric < 0)
8497b6ab19dSGarrett Wollman 		k->k_metric = 0;
8507b6ab19dSGarrett Wollman 	else if (k->k_metric > HOPCNT_INFINITY)
8517b6ab19dSGarrett Wollman 		 k->k_metric = HOPCNT_INFINITY;
8527b6ab19dSGarrett Wollman 	k->k_state &= ~(KS_DELETED | KS_GATEWAY | KS_STATIC | KS_NEW);
8537b6ab19dSGarrett Wollman 	if (rtm->rtm_flags & RTF_GATEWAY)
8547b6ab19dSGarrett Wollman 		k->k_state |= KS_GATEWAY;
8557b6ab19dSGarrett Wollman 	if (rtm->rtm_flags & RTF_STATIC)
8567b6ab19dSGarrett Wollman 		k->k_state |= KS_STATIC;
8577b6ab19dSGarrett Wollman 
8587b6ab19dSGarrett Wollman 	if (0 != (rtm->rtm_flags & (RTF_DYNAMIC | RTF_MODIFIED))) {
859a30febecSGarrett Wollman 		if (INFO_AUTHOR(info) != 0
860a30febecSGarrett Wollman 		    && INFO_AUTHOR(info)->sa_family == AF_INET)
861a30febecSGarrett Wollman 			ifp = iflookup(S_ADDR(INFO_AUTHOR(info)));
862a30febecSGarrett Wollman 		else
863a30febecSGarrett Wollman 			ifp = 0;
864a30febecSGarrett Wollman 		if (supplier
865a30febecSGarrett Wollman 		    && (ifp == 0 || !(ifp->int_state & IS_REDIRECT_OK))) {
8667b6ab19dSGarrett Wollman 			/* Routers are not supposed to listen to redirects,
867a30febecSGarrett Wollman 			 * so delete it if it came via an unknown interface
868a30febecSGarrett Wollman 			 * or the interface does not have special permission.
8697b6ab19dSGarrett Wollman 			 */
8707b6ab19dSGarrett Wollman 			k->k_state &= ~KS_DYNAMIC;
8717b6ab19dSGarrett Wollman 			k->k_state |= KS_DELETE;
8727b6ab19dSGarrett Wollman 			LIM_SEC(need_kern, 0);
873a30febecSGarrett Wollman 			trace_act("mark for deletion redirected %s --> %s"
874a30febecSGarrett Wollman 				  " via %s",
8757b6ab19dSGarrett Wollman 				  addrname(k->k_dst, k->k_mask, 0),
876a30febecSGarrett Wollman 				  naddr_ntoa(k->k_gate),
877a30febecSGarrett Wollman 				  ifp ? ifp->int_name : "unknown interface");
8787b6ab19dSGarrett Wollman 		} else {
8797b6ab19dSGarrett Wollman 			k->k_state |= KS_DYNAMIC;
8807b6ab19dSGarrett Wollman 			k->k_redirect_time = now.tv_sec;
881a30febecSGarrett Wollman 			trace_act("accept redirected %s --> %s via %s",
882a30febecSGarrett Wollman 				  addrname(k->k_dst, k->k_mask, 0),
883a30febecSGarrett Wollman 				  naddr_ntoa(k->k_gate),
884a30febecSGarrett Wollman 				  ifp ? ifp->int_name : "unknown interface");
8857b6ab19dSGarrett Wollman 		}
8867b6ab19dSGarrett Wollman 		return;
8877b6ab19dSGarrett Wollman 	}
8887b6ab19dSGarrett Wollman 
8897b6ab19dSGarrett Wollman 	/* If it is not a static route, quit until the next comparison
8907b6ab19dSGarrett Wollman 	 * between the kernel and daemon tables, when it will be deleted.
8917b6ab19dSGarrett Wollman 	 */
8927b6ab19dSGarrett Wollman 	if (!(k->k_state & KS_STATIC)) {
8937b6ab19dSGarrett Wollman 		k->k_state |= KS_DELETE;
8947b6ab19dSGarrett Wollman 		LIM_SEC(need_kern, k->k_keep);
8957b6ab19dSGarrett Wollman 		return;
8967b6ab19dSGarrett Wollman 	}
8977b6ab19dSGarrett Wollman 
8987b6ab19dSGarrett Wollman 	/* Put static routes with real metrics into the daemon table so
8997b6ab19dSGarrett Wollman 	 * they can be advertised.
9007b6ab19dSGarrett Wollman 	 *
90152ad6021SGarrett Wollman 	 * Find the interface toward the gateway.
9027b6ab19dSGarrett Wollman 	 */
9037b6ab19dSGarrett Wollman 	ifp = iflookup(k->k_gate);
9047b6ab19dSGarrett Wollman 	if (ifp == 0)
9057b6ab19dSGarrett Wollman 		msglog("static route %s --> %s impossibly lacks ifp",
9067b6ab19dSGarrett Wollman 		       addrname(S_ADDR(INFO_DST(info)), mask, 0),
9077b6ab19dSGarrett Wollman 		       naddr_ntoa(k->k_gate));
9087b6ab19dSGarrett Wollman 
9097b6ab19dSGarrett Wollman 	kern_check_static(k, ifp);
9107b6ab19dSGarrett Wollman }
9117b6ab19dSGarrett Wollman 
9127b6ab19dSGarrett Wollman 
9137b6ab19dSGarrett Wollman /* deal with packet loss
9147b6ab19dSGarrett Wollman  */
9157b6ab19dSGarrett Wollman static void
9167b6ab19dSGarrett Wollman rtm_lose(struct rt_msghdr *rtm,
9177b6ab19dSGarrett Wollman 	 struct rt_addrinfo *info)
9187b6ab19dSGarrett Wollman {
9197b6ab19dSGarrett Wollman 	if (INFO_GATE(info) == 0
9207b6ab19dSGarrett Wollman 	    || INFO_GATE(info)->sa_family != AF_INET) {
921a30febecSGarrett Wollman 		trace_act("ignore %s without gateway",
9227b6ab19dSGarrett Wollman 			  rtm_type_name(rtm->rtm_type));
9237b6ab19dSGarrett Wollman 		return;
9247b6ab19dSGarrett Wollman 	}
9257b6ab19dSGarrett Wollman 
9267b6ab19dSGarrett Wollman 	if (!supplier)
9277b6ab19dSGarrett Wollman 		rdisc_age(S_ADDR(INFO_GATE(info)));
9287b6ab19dSGarrett Wollman 
9297b6ab19dSGarrett Wollman 	age(S_ADDR(INFO_GATE(info)));
9307b6ab19dSGarrett Wollman }
9317b6ab19dSGarrett Wollman 
9327b6ab19dSGarrett Wollman 
9337b6ab19dSGarrett Wollman /* Clean the kernel table by copying it to the daemon image.
9347b6ab19dSGarrett Wollman  * Eventually the daemon will delete any extra routes.
9357b6ab19dSGarrett Wollman  */
9367b6ab19dSGarrett Wollman void
9377b6ab19dSGarrett Wollman flush_kern(void)
9387b6ab19dSGarrett Wollman {
9397b6ab19dSGarrett Wollman 	size_t needed;
9407b6ab19dSGarrett Wollman 	int mib[6];
9417b6ab19dSGarrett Wollman 	char *buf, *next, *lim;
9427b6ab19dSGarrett Wollman 	struct rt_msghdr *rtm;
9437b6ab19dSGarrett Wollman 	struct interface *ifp;
9447b6ab19dSGarrett Wollman 	static struct sockaddr_in gate_sa;
9457b6ab19dSGarrett Wollman 	struct rt_addrinfo info;
9467b6ab19dSGarrett Wollman 
9477b6ab19dSGarrett Wollman 
9487b6ab19dSGarrett Wollman 	mib[0] = CTL_NET;
9497b6ab19dSGarrett Wollman 	mib[1] = PF_ROUTE;
9507b6ab19dSGarrett Wollman 	mib[2] = 0;		/* protocol */
9517b6ab19dSGarrett Wollman 	mib[3] = 0;		/* wildcard address family */
9527b6ab19dSGarrett Wollman 	mib[4] = NET_RT_DUMP;
9537b6ab19dSGarrett Wollman 	mib[5] = 0;		/* no flags */
9547b6ab19dSGarrett Wollman 	if (sysctl(mib, 6, 0, &needed, 0, 0) < 0) {
9557b6ab19dSGarrett Wollman 		DBGERR(1,"RT_DUMP-sysctl-estimate");
9567b6ab19dSGarrett Wollman 		return;
9577b6ab19dSGarrett Wollman 	}
95890100551SPhilippe Charnier 	buf = (char *)rtmalloc(needed, "flush_kern");
9597b6ab19dSGarrett Wollman 	if (sysctl(mib, 6, buf, &needed, 0, 0) < 0)
9607b6ab19dSGarrett Wollman 		BADERR(1,"RT_DUMP");
9617b6ab19dSGarrett Wollman 	lim = buf + needed;
9627b6ab19dSGarrett Wollman 	for (next = buf; next < lim; next += rtm->rtm_msglen) {
9637b6ab19dSGarrett Wollman 		rtm = (struct rt_msghdr *)next;
9647b6ab19dSGarrett Wollman 
9657b6ab19dSGarrett Wollman 		rt_xaddrs(&info,
9667b6ab19dSGarrett Wollman 			  (struct sockaddr *)(rtm+1),
9677b6ab19dSGarrett Wollman 			  (struct sockaddr *)(next + rtm->rtm_msglen),
9687b6ab19dSGarrett Wollman 			  rtm->rtm_addrs);
9697b6ab19dSGarrett Wollman 
9707b6ab19dSGarrett Wollman 		if (INFO_DST(&info) == 0
9717b6ab19dSGarrett Wollman 		    || INFO_DST(&info)->sa_family != AF_INET)
9727b6ab19dSGarrett Wollman 			continue;
9737b6ab19dSGarrett Wollman 
9747b6ab19dSGarrett Wollman 		/* ignore ARP table entries on systems with a merged route
9757b6ab19dSGarrett Wollman 		 * and ARP table.
9767b6ab19dSGarrett Wollman 		 */
9777b6ab19dSGarrett Wollman 		if (rtm->rtm_flags & RTF_LLINFO)
9787b6ab19dSGarrett Wollman 			continue;
9797b6ab19dSGarrett Wollman 
9807b6ab19dSGarrett Wollman 		if (INFO_GATE(&info) == 0)
9817b6ab19dSGarrett Wollman 			continue;
9827b6ab19dSGarrett Wollman 		if (INFO_GATE(&info)->sa_family != AF_INET) {
9837b6ab19dSGarrett Wollman 			if (INFO_GATE(&info)->sa_family != AF_LINK)
9847b6ab19dSGarrett Wollman 				continue;
9857b6ab19dSGarrett Wollman 			ifp = ifwithindex(((struct sockaddr_dl *)
9867b6ab19dSGarrett Wollman 					   INFO_GATE(&info))->sdl_index);
9877b6ab19dSGarrett Wollman 			if (ifp == 0)
9887b6ab19dSGarrett Wollman 				continue;
9897b6ab19dSGarrett Wollman 			if ((ifp->int_if_flags & IFF_POINTOPOINT)
9907b6ab19dSGarrett Wollman 			    || S_ADDR(INFO_DST(&info)) == ifp->int_addr)
9917b6ab19dSGarrett Wollman 				gate_sa.sin_addr.s_addr = ifp->int_addr;
9927b6ab19dSGarrett Wollman 			else
9937b6ab19dSGarrett Wollman 				gate_sa.sin_addr.s_addr = htonl(ifp->int_net);
9947b6ab19dSGarrett Wollman #ifdef _HAVE_SA_LEN
9957b6ab19dSGarrett Wollman 			gate_sa.sin_len = sizeof(gate_sa);
9967b6ab19dSGarrett Wollman #endif
9977b6ab19dSGarrett Wollman 			gate_sa.sin_family = AF_INET;
9987b6ab19dSGarrett Wollman 			INFO_GATE(&info) = (struct sockaddr *)&gate_sa;
9997b6ab19dSGarrett Wollman 		}
10007b6ab19dSGarrett Wollman 
10017b6ab19dSGarrett Wollman 		/* ignore multicast addresses
10027b6ab19dSGarrett Wollman 		 */
10037b6ab19dSGarrett Wollman 		if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info)))))
10047b6ab19dSGarrett Wollman 			continue;
10057b6ab19dSGarrett Wollman 
10067b6ab19dSGarrett Wollman 		/* Note static routes and interface routes, and also
10077b6ab19dSGarrett Wollman 		 * preload the image of the kernel table so that
10087b6ab19dSGarrett Wollman 		 * we can later clean it, as well as avoid making
10097b6ab19dSGarrett Wollman 		 * unneeded changes.  Keep the old kernel routes for a
10107b6ab19dSGarrett Wollman 		 * few seconds to allow a RIP or router-discovery
10117b6ab19dSGarrett Wollman 		 * response to be heard.
10127b6ab19dSGarrett Wollman 		 */
10137b6ab19dSGarrett Wollman 		rtm_add(rtm,&info,MIN_WAITTIME);
10147b6ab19dSGarrett Wollman 	}
10157b6ab19dSGarrett Wollman 	free(buf);
10167b6ab19dSGarrett Wollman }
10177b6ab19dSGarrett Wollman 
10187b6ab19dSGarrett Wollman 
10197b6ab19dSGarrett Wollman /* Listen to announcements from the kernel
10207b6ab19dSGarrett Wollman  */
10217b6ab19dSGarrett Wollman void
10227b6ab19dSGarrett Wollman read_rt(void)
10237b6ab19dSGarrett Wollman {
10247b6ab19dSGarrett Wollman 	long cc;
10257b6ab19dSGarrett Wollman 	struct interface *ifp;
10267b6ab19dSGarrett Wollman 	naddr mask;
10277b6ab19dSGarrett Wollman 	union {
10287b6ab19dSGarrett Wollman 		struct {
10297b6ab19dSGarrett Wollman 			struct rt_msghdr rtm;
10307b6ab19dSGarrett Wollman 			struct sockaddr addrs[RTAX_MAX];
10317b6ab19dSGarrett Wollman 		} r;
10327b6ab19dSGarrett Wollman 		struct if_msghdr ifm;
10337b6ab19dSGarrett Wollman 	} m;
10347b6ab19dSGarrett Wollman 	char str[100], *strp;
10357b6ab19dSGarrett Wollman 	struct rt_addrinfo info;
10367b6ab19dSGarrett Wollman 
10377b6ab19dSGarrett Wollman 
10387b6ab19dSGarrett Wollman 	for (;;) {
10397b6ab19dSGarrett Wollman 		cc = read(rt_sock, &m, sizeof(m));
10407b6ab19dSGarrett Wollman 		if (cc <= 0) {
10417b6ab19dSGarrett Wollman 			if (cc < 0 && errno != EWOULDBLOCK)
10427b6ab19dSGarrett Wollman 				LOGERR("read(rt_sock)");
10437b6ab19dSGarrett Wollman 			return;
10447b6ab19dSGarrett Wollman 		}
10457b6ab19dSGarrett Wollman 
10467b6ab19dSGarrett Wollman 		if (m.r.rtm.rtm_version != RTM_VERSION) {
10477b6ab19dSGarrett Wollman 			msglog("bogus routing message version %d",
10487b6ab19dSGarrett Wollman 			       m.r.rtm.rtm_version);
10497b6ab19dSGarrett Wollman 			continue;
10507b6ab19dSGarrett Wollman 		}
10517b6ab19dSGarrett Wollman 
10527b6ab19dSGarrett Wollman 		/* Ignore our own results.
10537b6ab19dSGarrett Wollman 		 */
10547b6ab19dSGarrett Wollman 		if (m.r.rtm.rtm_type <= RTM_CHANGE
10557b6ab19dSGarrett Wollman 		    && m.r.rtm.rtm_pid == mypid) {
10567b6ab19dSGarrett Wollman 			static int complained = 0;
10577b6ab19dSGarrett Wollman 			if (!complained) {
10587b6ab19dSGarrett Wollman 				msglog("receiving our own change messages");
10597b6ab19dSGarrett Wollman 				complained = 1;
10607b6ab19dSGarrett Wollman 			}
10617b6ab19dSGarrett Wollman 			continue;
10627b6ab19dSGarrett Wollman 		}
10637b6ab19dSGarrett Wollman 
10647b6ab19dSGarrett Wollman 		if (m.r.rtm.rtm_type == RTM_IFINFO
10657b6ab19dSGarrett Wollman 		    || m.r.rtm.rtm_type == RTM_NEWADDR
10667b6ab19dSGarrett Wollman 		    || m.r.rtm.rtm_type == RTM_DELADDR) {
10677b6ab19dSGarrett Wollman 			ifp = ifwithindex(m.ifm.ifm_index);
10687b6ab19dSGarrett Wollman 			if (ifp == 0)
10697b6ab19dSGarrett Wollman 				trace_act("note %s with flags %#x"
107052ad6021SGarrett Wollman 					  " for index #%d",
10717b6ab19dSGarrett Wollman 					  rtm_type_name(m.r.rtm.rtm_type),
10727b6ab19dSGarrett Wollman 					  m.ifm.ifm_flags,
10737b6ab19dSGarrett Wollman 					  m.ifm.ifm_index);
10747b6ab19dSGarrett Wollman 			else
107552ad6021SGarrett Wollman 				trace_act("note %s with flags %#x for %s",
10767b6ab19dSGarrett Wollman 					  rtm_type_name(m.r.rtm.rtm_type),
10777b6ab19dSGarrett Wollman 					  m.ifm.ifm_flags,
10787b6ab19dSGarrett Wollman 					  ifp->int_name);
10797b6ab19dSGarrett Wollman 
10807b6ab19dSGarrett Wollman 			/* After being informed of a change to an interface,
10817b6ab19dSGarrett Wollman 			 * check them all now if the check would otherwise
10827b6ab19dSGarrett Wollman 			 * be a long time from now, if the interface is
10837b6ab19dSGarrett Wollman 			 * not known, or if the interface has been turned
10847b6ab19dSGarrett Wollman 			 * off or on.
10857b6ab19dSGarrett Wollman 			 */
10867b6ab19dSGarrett Wollman 			if (ifinit_timer.tv_sec-now.tv_sec>=CHECK_BAD_INTERVAL
10877b6ab19dSGarrett Wollman 			    || ifp == 0
10887b6ab19dSGarrett Wollman 			    || ((ifp->int_if_flags ^ m.ifm.ifm_flags)
10897b6ab19dSGarrett Wollman 				& IFF_UP_RUNNING) != 0)
10907b6ab19dSGarrett Wollman 				ifinit_timer.tv_sec = now.tv_sec;
10917b6ab19dSGarrett Wollman 			continue;
10927b6ab19dSGarrett Wollman 		}
10937b6ab19dSGarrett Wollman 
10947b6ab19dSGarrett Wollman 		strcpy(str, rtm_type_name(m.r.rtm.rtm_type));
10957b6ab19dSGarrett Wollman 		strp = &str[strlen(str)];
10967b6ab19dSGarrett Wollman 		if (m.r.rtm.rtm_type <= RTM_CHANGE)
10977b6ab19dSGarrett Wollman 			strp += sprintf(strp," from pid %d",m.r.rtm.rtm_pid);
10987b6ab19dSGarrett Wollman 
10997b6ab19dSGarrett Wollman 		rt_xaddrs(&info, m.r.addrs, &m.r.addrs[RTAX_MAX],
11007b6ab19dSGarrett Wollman 			  m.r.rtm.rtm_addrs);
11017b6ab19dSGarrett Wollman 
11027b6ab19dSGarrett Wollman 		if (INFO_DST(&info) == 0) {
110352ad6021SGarrett Wollman 			trace_act("ignore %s without dst", str);
11047b6ab19dSGarrett Wollman 			continue;
11057b6ab19dSGarrett Wollman 		}
11067b6ab19dSGarrett Wollman 
11077b6ab19dSGarrett Wollman 		if (INFO_DST(&info)->sa_family != AF_INET) {
110852ad6021SGarrett Wollman 			trace_act("ignore %s for AF %d", str,
11097b6ab19dSGarrett Wollman 				  INFO_DST(&info)->sa_family);
11107b6ab19dSGarrett Wollman 			continue;
11117b6ab19dSGarrett Wollman 		}
11127b6ab19dSGarrett Wollman 
11137b6ab19dSGarrett Wollman 		mask = ((INFO_MASK(&info) != 0)
11147b6ab19dSGarrett Wollman 			? ntohl(S_ADDR(INFO_MASK(&info)))
11157b6ab19dSGarrett Wollman 			: (m.r.rtm.rtm_flags & RTF_HOST)
11167b6ab19dSGarrett Wollman 			? HOST_MASK
11177b6ab19dSGarrett Wollman 			: std_mask(S_ADDR(INFO_DST(&info))));
11187b6ab19dSGarrett Wollman 
11197b6ab19dSGarrett Wollman 		strp += sprintf(strp, ": %s",
11207b6ab19dSGarrett Wollman 				addrname(S_ADDR(INFO_DST(&info)), mask, 0));
11217b6ab19dSGarrett Wollman 
11227b6ab19dSGarrett Wollman 		if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info))))) {
112352ad6021SGarrett Wollman 			trace_act("ignore multicast %s", str);
11247b6ab19dSGarrett Wollman 			continue;
11257b6ab19dSGarrett Wollman 		}
11267b6ab19dSGarrett Wollman 
11277b6ab19dSGarrett Wollman 		if (INFO_GATE(&info) != 0
11287b6ab19dSGarrett Wollman 		    && INFO_GATE(&info)->sa_family == AF_INET)
11297b6ab19dSGarrett Wollman 			strp += sprintf(strp, " --> %s",
11307b6ab19dSGarrett Wollman 					saddr_ntoa(INFO_GATE(&info)));
11317b6ab19dSGarrett Wollman 
11327b6ab19dSGarrett Wollman 		if (INFO_AUTHOR(&info) != 0)
11337b6ab19dSGarrett Wollman 			strp += sprintf(strp, " by authority of %s",
11347b6ab19dSGarrett Wollman 					saddr_ntoa(INFO_AUTHOR(&info)));
11357b6ab19dSGarrett Wollman 
11367b6ab19dSGarrett Wollman 		switch (m.r.rtm.rtm_type) {
11377b6ab19dSGarrett Wollman 		case RTM_ADD:
11387b6ab19dSGarrett Wollman 		case RTM_CHANGE:
11397b6ab19dSGarrett Wollman 		case RTM_REDIRECT:
11407b6ab19dSGarrett Wollman 			if (m.r.rtm.rtm_errno != 0) {
114152ad6021SGarrett Wollman 				trace_act("ignore %s with \"%s\" error",
11427b6ab19dSGarrett Wollman 					  str, strerror(m.r.rtm.rtm_errno));
11437b6ab19dSGarrett Wollman 			} else {
114452ad6021SGarrett Wollman 				trace_act("%s", str);
11457b6ab19dSGarrett Wollman 				rtm_add(&m.r.rtm,&info,0);
11467b6ab19dSGarrett Wollman 			}
11477b6ab19dSGarrett Wollman 			break;
11487b6ab19dSGarrett Wollman 
11497b6ab19dSGarrett Wollman 		case RTM_DELETE:
11507b6ab19dSGarrett Wollman 			if (m.r.rtm.rtm_errno != 0) {
115152ad6021SGarrett Wollman 				trace_act("ignore %s with \"%s\" error",
11527b6ab19dSGarrett Wollman 					  str, strerror(m.r.rtm.rtm_errno));
11537b6ab19dSGarrett Wollman 			} else {
115452ad6021SGarrett Wollman 				trace_act("%s", str);
11557b6ab19dSGarrett Wollman 				del_static(S_ADDR(INFO_DST(&info)), mask, 1);
11567b6ab19dSGarrett Wollman 			}
11577b6ab19dSGarrett Wollman 			break;
11587b6ab19dSGarrett Wollman 
11597b6ab19dSGarrett Wollman 		case RTM_LOSING:
116052ad6021SGarrett Wollman 			trace_act("%s", str);
11617b6ab19dSGarrett Wollman 			rtm_lose(&m.r.rtm,&info);
11627b6ab19dSGarrett Wollman 			break;
11637b6ab19dSGarrett Wollman 
11647b6ab19dSGarrett Wollman 		default:
116552ad6021SGarrett Wollman 			trace_act("ignore %s", str);
11667b6ab19dSGarrett Wollman 			break;
11677b6ab19dSGarrett Wollman 		}
11687b6ab19dSGarrett Wollman 	}
11697b6ab19dSGarrett Wollman }
11707b6ab19dSGarrett Wollman 
11717b6ab19dSGarrett Wollman 
11727b6ab19dSGarrett Wollman /* after aggregating, note routes that belong in the kernel
11737b6ab19dSGarrett Wollman  */
11747b6ab19dSGarrett Wollman static void
11757b6ab19dSGarrett Wollman kern_out(struct ag_info *ag)
11767b6ab19dSGarrett Wollman {
11777b6ab19dSGarrett Wollman 	struct khash *k;
11787b6ab19dSGarrett Wollman 
11797b6ab19dSGarrett Wollman 
11807b6ab19dSGarrett Wollman 	/* Do not install bad routes if they are not already present.
11817b6ab19dSGarrett Wollman 	 * This includes routes that had RS_NET_SYN for interfaces that
11827b6ab19dSGarrett Wollman 	 * recently died.
11837b6ab19dSGarrett Wollman 	 */
11847b6ab19dSGarrett Wollman 	if (ag->ag_metric == HOPCNT_INFINITY) {
11857b6ab19dSGarrett Wollman 		k = kern_find(htonl(ag->ag_dst_h), ag->ag_mask, 0);
11867b6ab19dSGarrett Wollman 		if (k == 0)
11877b6ab19dSGarrett Wollman 			return;
11887b6ab19dSGarrett Wollman 	} else {
11897b6ab19dSGarrett Wollman 		k = kern_add(htonl(ag->ag_dst_h), ag->ag_mask);
11907b6ab19dSGarrett Wollman 	}
11917b6ab19dSGarrett Wollman 
11927b6ab19dSGarrett Wollman 	if (k->k_state & KS_NEW) {
11937b6ab19dSGarrett Wollman 		/* will need to add new entry to the kernel table */
11947b6ab19dSGarrett Wollman 		k->k_state = KS_ADD;
11957b6ab19dSGarrett Wollman 		if (ag->ag_state & AGS_GATEWAY)
11967b6ab19dSGarrett Wollman 			k->k_state |= KS_GATEWAY;
11977b6ab19dSGarrett Wollman 		k->k_gate = ag->ag_gate;
11987b6ab19dSGarrett Wollman 		k->k_metric = ag->ag_metric;
11997b6ab19dSGarrett Wollman 		return;
12007b6ab19dSGarrett Wollman 	}
12017b6ab19dSGarrett Wollman 
12027b6ab19dSGarrett Wollman 	if (k->k_state & KS_STATIC)
12037b6ab19dSGarrett Wollman 		return;
12047b6ab19dSGarrett Wollman 
12057b6ab19dSGarrett Wollman 	/* modify existing kernel entry if necessary */
12067b6ab19dSGarrett Wollman 	if (k->k_gate != ag->ag_gate
12077b6ab19dSGarrett Wollman 	    || k->k_metric != ag->ag_metric) {
12087b6ab19dSGarrett Wollman 		k->k_gate = ag->ag_gate;
12097b6ab19dSGarrett Wollman 		k->k_metric = ag->ag_metric;
12107b6ab19dSGarrett Wollman 		k->k_state |= KS_CHANGE;
12117b6ab19dSGarrett Wollman 	}
12127b6ab19dSGarrett Wollman 
12137b6ab19dSGarrett Wollman 	if (k->k_state & KS_DYNAMIC) {
12147b6ab19dSGarrett Wollman 		k->k_state &= ~KS_DYNAMIC;
12157b6ab19dSGarrett Wollman 		k->k_state |= (KS_ADD | KS_DEL_ADD);
12167b6ab19dSGarrett Wollman 	}
12177b6ab19dSGarrett Wollman 
12187b6ab19dSGarrett Wollman 	if ((k->k_state & KS_GATEWAY)
12197b6ab19dSGarrett Wollman 	    && !(ag->ag_state & AGS_GATEWAY)) {
12207b6ab19dSGarrett Wollman 		k->k_state &= ~KS_GATEWAY;
12217b6ab19dSGarrett Wollman 		k->k_state |= (KS_ADD | KS_DEL_ADD);
12227b6ab19dSGarrett Wollman 	} else if (!(k->k_state & KS_GATEWAY)
12237b6ab19dSGarrett Wollman 		   && (ag->ag_state & AGS_GATEWAY)) {
12247b6ab19dSGarrett Wollman 		k->k_state |= KS_GATEWAY;
12257b6ab19dSGarrett Wollman 		k->k_state |= (KS_ADD | KS_DEL_ADD);
12267b6ab19dSGarrett Wollman 	}
12277b6ab19dSGarrett Wollman 
12287b6ab19dSGarrett Wollman 	/* Deleting-and-adding is necessary to change aspects of a route.
12297b6ab19dSGarrett Wollman 	 * Just delete instead of deleting and then adding a bad route.
12307b6ab19dSGarrett Wollman 	 * Otherwise, we want to keep the route in the kernel.
12317b6ab19dSGarrett Wollman 	 */
12327b6ab19dSGarrett Wollman 	if (k->k_metric == HOPCNT_INFINITY
12337b6ab19dSGarrett Wollman 	    && (k->k_state & KS_DEL_ADD))
12347b6ab19dSGarrett Wollman 		k->k_state |= KS_DELETE;
12357b6ab19dSGarrett Wollman 	else
12367b6ab19dSGarrett Wollman 		k->k_state &= ~KS_DELETE;
12377b6ab19dSGarrett Wollman #undef RT
12387b6ab19dSGarrett Wollman }
12397b6ab19dSGarrett Wollman 
12407b6ab19dSGarrett Wollman 
12417b6ab19dSGarrett Wollman /* ARGSUSED */
12427b6ab19dSGarrett Wollman static int
12437b6ab19dSGarrett Wollman walk_kern(struct radix_node *rn,
12447b6ab19dSGarrett Wollman 	  struct walkarg *w)
12457b6ab19dSGarrett Wollman {
12467b6ab19dSGarrett Wollman #define RT ((struct rt_entry *)rn)
12477b6ab19dSGarrett Wollman 	char metric, pref;
12487b6ab19dSGarrett Wollman 	u_int ags = 0;
12497b6ab19dSGarrett Wollman 
12507b6ab19dSGarrett Wollman 
12517b6ab19dSGarrett Wollman 	/* Do not install synthetic routes */
12527b6ab19dSGarrett Wollman 	if (RT->rt_state & RS_NET_SYN)
12537b6ab19dSGarrett Wollman 		return 0;
12547b6ab19dSGarrett Wollman 
12557b6ab19dSGarrett Wollman 	if (!(RT->rt_state & RS_IF)) {
12567b6ab19dSGarrett Wollman 		ags |= (AGS_GATEWAY | AGS_SUPPRESS | AGS_PROMOTE);
12577b6ab19dSGarrett Wollman 
12587b6ab19dSGarrett Wollman 	} else {
12597b6ab19dSGarrett Wollman 		/* Do not install routes for "external" remote interfaces.
12607b6ab19dSGarrett Wollman 		 */
12617b6ab19dSGarrett Wollman 		if (RT->rt_ifp != 0 && (RT->rt_ifp->int_state & IS_EXTERNAL))
12627b6ab19dSGarrett Wollman 			return 0;
12637b6ab19dSGarrett Wollman 
12647b6ab19dSGarrett Wollman 		ags |= AGS_IF;
12657b6ab19dSGarrett Wollman 
12667b6ab19dSGarrett Wollman 		/* If it is not an interface, or an alias for an interface,
12677b6ab19dSGarrett Wollman 		 * it must be a "gateway."
12687b6ab19dSGarrett Wollman 		 *
12697b6ab19dSGarrett Wollman 		 * If it is a "remote" interface, it is also a "gateway" to
12707b6ab19dSGarrett Wollman 		 * the kernel if is not a alias.
12717b6ab19dSGarrett Wollman 		 */
12727b6ab19dSGarrett Wollman 		if (RT->rt_ifp == 0
127352ad6021SGarrett Wollman 		    || (RT->rt_ifp->int_state & IS_REMOTE))
12747b6ab19dSGarrett Wollman 			ags |= (AGS_GATEWAY | AGS_SUPPRESS | AGS_PROMOTE);
12757b6ab19dSGarrett Wollman 	}
12767b6ab19dSGarrett Wollman 
12777b6ab19dSGarrett Wollman 	if (RT->rt_state & RS_RDISC)
12787b6ab19dSGarrett Wollman 		ags |= AGS_CORS_GATE;
12797b6ab19dSGarrett Wollman 
12807b6ab19dSGarrett Wollman 	/* aggregate good routes without regard to their metric */
12817b6ab19dSGarrett Wollman 	pref = 1;
12827b6ab19dSGarrett Wollman 	metric = RT->rt_metric;
12837b6ab19dSGarrett Wollman 	if (metric == HOPCNT_INFINITY) {
12847b6ab19dSGarrett Wollman 		/* if the route is dead, so try hard to aggregate. */
12857b6ab19dSGarrett Wollman 		pref = HOPCNT_INFINITY;
12867b6ab19dSGarrett Wollman 		ags |= (AGS_FINE_GATE | AGS_SUPPRESS);
12877b6ab19dSGarrett Wollman 	}
12887b6ab19dSGarrett Wollman 
12897b6ab19dSGarrett Wollman 	ag_check(RT->rt_dst, RT->rt_mask, RT->rt_gate, 0,
12907b6ab19dSGarrett Wollman 		 metric,pref, 0, 0, ags, kern_out);
12917b6ab19dSGarrett Wollman 	return 0;
12927b6ab19dSGarrett Wollman #undef RT
12937b6ab19dSGarrett Wollman }
12947b6ab19dSGarrett Wollman 
12957b6ab19dSGarrett Wollman 
12967b6ab19dSGarrett Wollman /* Update the kernel table to match the daemon table.
12977b6ab19dSGarrett Wollman  */
12987b6ab19dSGarrett Wollman static void
12997b6ab19dSGarrett Wollman fix_kern(void)
13007b6ab19dSGarrett Wollman {
13017b6ab19dSGarrett Wollman 	int i, flags;
13027b6ab19dSGarrett Wollman 	struct khash *k, **pk;
13037b6ab19dSGarrett Wollman 
13047b6ab19dSGarrett Wollman 
13057b6ab19dSGarrett Wollman 	need_kern = age_timer;
13067b6ab19dSGarrett Wollman 
13077b6ab19dSGarrett Wollman 	/* Walk daemon table, updating the copy of the kernel table.
13087b6ab19dSGarrett Wollman 	 */
13097b6ab19dSGarrett Wollman 	(void)rn_walktree(rhead, walk_kern, 0);
13107b6ab19dSGarrett Wollman 	ag_flush(0,0,kern_out);
13117b6ab19dSGarrett Wollman 
13127b6ab19dSGarrett Wollman 	for (i = 0; i < KHASH_SIZE; i++) {
13137b6ab19dSGarrett Wollman 		for (pk = &khash_bins[i]; (k = *pk) != 0; ) {
13147b6ab19dSGarrett Wollman 			/* Do not touch static routes */
13157b6ab19dSGarrett Wollman 			if (k->k_state & KS_STATIC) {
13167b6ab19dSGarrett Wollman 				kern_check_static(k,0);
13177b6ab19dSGarrett Wollman 				pk = &k->k_next;
13187b6ab19dSGarrett Wollman 				continue;
13197b6ab19dSGarrett Wollman 			}
13207b6ab19dSGarrett Wollman 
13217b6ab19dSGarrett Wollman 			/* check hold on routes deleted by the operator */
13227b6ab19dSGarrett Wollman 			if (k->k_keep > now.tv_sec) {
13237b6ab19dSGarrett Wollman 				LIM_SEC(need_kern, k->k_keep);
13247b6ab19dSGarrett Wollman 				k->k_state |= KS_DELETE;
13257b6ab19dSGarrett Wollman 				pk = &k->k_next;
13267b6ab19dSGarrett Wollman 				continue;
13277b6ab19dSGarrett Wollman 			}
13287b6ab19dSGarrett Wollman 
13297b6ab19dSGarrett Wollman 			if ((k->k_state & (KS_DELETE | KS_DYNAMIC))
13307b6ab19dSGarrett Wollman 			    == KS_DELETE) {
13317b6ab19dSGarrett Wollman 				if (!(k->k_state & KS_DELETED))
13327b6ab19dSGarrett Wollman 					rtioctl(RTM_DELETE,
13337b6ab19dSGarrett Wollman 						k->k_dst, k->k_gate, k->k_mask,
13347b6ab19dSGarrett Wollman 						0, 0);
13357b6ab19dSGarrett Wollman 				*pk = k->k_next;
13367b6ab19dSGarrett Wollman 				free(k);
13377b6ab19dSGarrett Wollman 				continue;
13387b6ab19dSGarrett Wollman 			}
13397b6ab19dSGarrett Wollman 
13407b6ab19dSGarrett Wollman 			if (0 != (k->k_state&(KS_ADD|KS_CHANGE|KS_DEL_ADD))) {
13417b6ab19dSGarrett Wollman 				if (k->k_state & KS_DEL_ADD) {
13427b6ab19dSGarrett Wollman 					rtioctl(RTM_DELETE,
13437b6ab19dSGarrett Wollman 						k->k_dst,k->k_gate,k->k_mask,
13447b6ab19dSGarrett Wollman 						0, 0);
13457b6ab19dSGarrett Wollman 					k->k_state &= ~KS_DYNAMIC;
13467b6ab19dSGarrett Wollman 				}
13477b6ab19dSGarrett Wollman 
13487b6ab19dSGarrett Wollman 				flags = 0;
13497b6ab19dSGarrett Wollman 				if (0 != (k->k_state&(KS_GATEWAY|KS_DYNAMIC)))
13507b6ab19dSGarrett Wollman 					flags |= RTF_GATEWAY;
13517b6ab19dSGarrett Wollman 
13527b6ab19dSGarrett Wollman 				if (k->k_state & KS_ADD) {
13537b6ab19dSGarrett Wollman 					rtioctl(RTM_ADD,
13547b6ab19dSGarrett Wollman 						k->k_dst, k->k_gate, k->k_mask,
13557b6ab19dSGarrett Wollman 						k->k_metric, flags);
13567b6ab19dSGarrett Wollman 				} else if (k->k_state & KS_CHANGE) {
13577b6ab19dSGarrett Wollman 					rtioctl(RTM_CHANGE,
13587b6ab19dSGarrett Wollman 						k->k_dst,k->k_gate,k->k_mask,
13597b6ab19dSGarrett Wollman 						k->k_metric, flags);
13607b6ab19dSGarrett Wollman 				}
13617b6ab19dSGarrett Wollman 				k->k_state &= ~(KS_ADD|KS_CHANGE|KS_DEL_ADD);
13627b6ab19dSGarrett Wollman 			}
13637b6ab19dSGarrett Wollman 
13647b6ab19dSGarrett Wollman 			/* Mark this route to be deleted in the next cycle.
13657b6ab19dSGarrett Wollman 			 * This deletes routes that disappear from the
13667b6ab19dSGarrett Wollman 			 * daemon table, since the normal aging code
13677b6ab19dSGarrett Wollman 			 * will clear the bit for routes that have not
13687b6ab19dSGarrett Wollman 			 * disappeared from the daemon table.
13697b6ab19dSGarrett Wollman 			 */
13707b6ab19dSGarrett Wollman 			k->k_state |= KS_DELETE;
13717b6ab19dSGarrett Wollman 			pk = &k->k_next;
13727b6ab19dSGarrett Wollman 		}
13737b6ab19dSGarrett Wollman 	}
13747b6ab19dSGarrett Wollman }
13757b6ab19dSGarrett Wollman 
13767b6ab19dSGarrett Wollman 
13777b6ab19dSGarrett Wollman /* Delete a static route in the image of the kernel table.
13787b6ab19dSGarrett Wollman  */
13797b6ab19dSGarrett Wollman void
13807b6ab19dSGarrett Wollman del_static(naddr dst,
13817b6ab19dSGarrett Wollman 	   naddr mask,
13827b6ab19dSGarrett Wollman 	   int gone)
13837b6ab19dSGarrett Wollman {
13847b6ab19dSGarrett Wollman 	struct khash *k;
13857b6ab19dSGarrett Wollman 	struct rt_entry *rt;
13867b6ab19dSGarrett Wollman 
13877b6ab19dSGarrett Wollman 	/* Just mark it in the table to be deleted next time the kernel
13887b6ab19dSGarrett Wollman 	 * table is updated.
13897b6ab19dSGarrett Wollman 	 * If it has already been deleted, mark it as such, and set its
13907b6ab19dSGarrett Wollman 	 * keep-timer so that it will not be deleted again for a while.
13917b6ab19dSGarrett Wollman 	 * This lets the operator delete a route added by the daemon
13927b6ab19dSGarrett Wollman 	 * and add a replacement.
13937b6ab19dSGarrett Wollman 	 */
13947b6ab19dSGarrett Wollman 	k = kern_find(dst, mask, 0);
13957b6ab19dSGarrett Wollman 	if (k != 0) {
13967b6ab19dSGarrett Wollman 		k->k_state &= ~(KS_STATIC | KS_DYNAMIC);
13977b6ab19dSGarrett Wollman 		k->k_state |= KS_DELETE;
13987b6ab19dSGarrett Wollman 		if (gone) {
13997b6ab19dSGarrett Wollman 			k->k_state |= KS_DELETED;
14007b6ab19dSGarrett Wollman 			k->k_keep = now.tv_sec + K_KEEP_LIM;
14017b6ab19dSGarrett Wollman 		}
14027b6ab19dSGarrett Wollman 	}
14037b6ab19dSGarrett Wollman 
14047b6ab19dSGarrett Wollman 	rt = rtget(dst, mask);
14057b6ab19dSGarrett Wollman 	if (rt != 0 && (rt->rt_state & RS_STATIC))
14067b6ab19dSGarrett Wollman 		rtbad(rt);
14077b6ab19dSGarrett Wollman }
14087b6ab19dSGarrett Wollman 
14097b6ab19dSGarrett Wollman 
14107b6ab19dSGarrett Wollman /* Delete all routes generated from ICMP Redirects that use a given gateway,
14117b6ab19dSGarrett Wollman  * as well as old redirected routes.
14127b6ab19dSGarrett Wollman  */
14137b6ab19dSGarrett Wollman void
14147b6ab19dSGarrett Wollman del_redirects(naddr bad_gate,
14157b6ab19dSGarrett Wollman 	      time_t old)
14167b6ab19dSGarrett Wollman {
14177b6ab19dSGarrett Wollman 	int i;
14187b6ab19dSGarrett Wollman 	struct khash *k;
14197b6ab19dSGarrett Wollman 
14207b6ab19dSGarrett Wollman 
14217b6ab19dSGarrett Wollman 	for (i = 0; i < KHASH_SIZE; i++) {
14227b6ab19dSGarrett Wollman 		for (k = khash_bins[i]; k != 0; k = k->k_next) {
14237b6ab19dSGarrett Wollman 			if (!(k->k_state & KS_DYNAMIC)
14247b6ab19dSGarrett Wollman 			    || (k->k_state & KS_STATIC))
14257b6ab19dSGarrett Wollman 				continue;
14267b6ab19dSGarrett Wollman 
14277b6ab19dSGarrett Wollman 			if (k->k_gate != bad_gate
14287b6ab19dSGarrett Wollman 			    && k->k_redirect_time > old
14297b6ab19dSGarrett Wollman 			    && !supplier)
14307b6ab19dSGarrett Wollman 				continue;
14317b6ab19dSGarrett Wollman 
14327b6ab19dSGarrett Wollman 			k->k_state |= KS_DELETE;
14337b6ab19dSGarrett Wollman 			k->k_state &= ~KS_DYNAMIC;
14347b6ab19dSGarrett Wollman 			need_kern.tv_sec = now.tv_sec;
143552ad6021SGarrett Wollman 			trace_act("mark redirected %s --> %s for deletion",
14367b6ab19dSGarrett Wollman 				  addrname(k->k_dst, k->k_mask, 0),
14377b6ab19dSGarrett Wollman 				  naddr_ntoa(k->k_gate));
14387b6ab19dSGarrett Wollman 		}
14397b6ab19dSGarrett Wollman 	}
14407b6ab19dSGarrett Wollman }
14417b6ab19dSGarrett Wollman 
14427b6ab19dSGarrett Wollman 
14437b6ab19dSGarrett Wollman /* Start the daemon tables.
14447b6ab19dSGarrett Wollman  */
14457b6ab19dSGarrett Wollman void
14467b6ab19dSGarrett Wollman rtinit(void)
14477b6ab19dSGarrett Wollman {
14487b6ab19dSGarrett Wollman 	extern int max_keylen;
14497b6ab19dSGarrett Wollman 	int i;
14507b6ab19dSGarrett Wollman 	struct ag_info *ag;
14517b6ab19dSGarrett Wollman 
14527b6ab19dSGarrett Wollman 	/* Initialize the radix trees */
14537b6ab19dSGarrett Wollman 	max_keylen = sizeof(struct sockaddr_in);
14547b6ab19dSGarrett Wollman 	rn_init();
14557b6ab19dSGarrett Wollman 	rn_inithead((void**)&rhead, 32);
14567b6ab19dSGarrett Wollman 
14577b6ab19dSGarrett Wollman 	/* mark all of the slots in the table free */
14587b6ab19dSGarrett Wollman 	ag_avail = ag_slots;
14597b6ab19dSGarrett Wollman 	for (ag = ag_slots, i = 1; i < NUM_AG_SLOTS; i++) {
14607b6ab19dSGarrett Wollman 		ag->ag_fine = ag+1;
14617b6ab19dSGarrett Wollman 		ag++;
14627b6ab19dSGarrett Wollman 	}
14637b6ab19dSGarrett Wollman }
14647b6ab19dSGarrett Wollman 
14657b6ab19dSGarrett Wollman 
14667b6ab19dSGarrett Wollman #ifdef _HAVE_SIN_LEN
14677b6ab19dSGarrett Wollman static struct sockaddr_in dst_sock = {sizeof(dst_sock), AF_INET};
14687b6ab19dSGarrett Wollman static struct sockaddr_in mask_sock = {sizeof(mask_sock), AF_INET};
14697b6ab19dSGarrett Wollman #else
14707b6ab19dSGarrett Wollman static struct sockaddr_in_new dst_sock = {_SIN_ADDR_SIZE, AF_INET};
14717b6ab19dSGarrett Wollman static struct sockaddr_in_new mask_sock = {_SIN_ADDR_SIZE, AF_INET};
14727b6ab19dSGarrett Wollman #endif
14737b6ab19dSGarrett Wollman 
14747b6ab19dSGarrett Wollman 
14757b6ab19dSGarrett Wollman void
14767b6ab19dSGarrett Wollman set_need_flash(void)
14777b6ab19dSGarrett Wollman {
14787b6ab19dSGarrett Wollman 	if (!need_flash) {
14797b6ab19dSGarrett Wollman 		need_flash = 1;
14807b6ab19dSGarrett Wollman 		/* Do not send the flash update immediately.  Wait a little
14817b6ab19dSGarrett Wollman 		 * while to hear from other routers.
14827b6ab19dSGarrett Wollman 		 */
14837b6ab19dSGarrett Wollman 		no_flash.tv_sec = now.tv_sec + MIN_WAITTIME;
14847b6ab19dSGarrett Wollman 	}
14857b6ab19dSGarrett Wollman }
14867b6ab19dSGarrett Wollman 
14877b6ab19dSGarrett Wollman 
14887b6ab19dSGarrett Wollman /* Get a particular routing table entry
14897b6ab19dSGarrett Wollman  */
14907b6ab19dSGarrett Wollman struct rt_entry *
14917b6ab19dSGarrett Wollman rtget(naddr dst, naddr mask)
14927b6ab19dSGarrett Wollman {
14937b6ab19dSGarrett Wollman 	struct rt_entry *rt;
14947b6ab19dSGarrett Wollman 
14957b6ab19dSGarrett Wollman 	dst_sock.sin_addr.s_addr = dst;
14967b6ab19dSGarrett Wollman 	mask_sock.sin_addr.s_addr = mask;
14977b6ab19dSGarrett Wollman 	masktrim(&mask_sock);
14987b6ab19dSGarrett Wollman 	rt = (struct rt_entry *)rhead->rnh_lookup(&dst_sock,&mask_sock,rhead);
14997b6ab19dSGarrett Wollman 	if (!rt
15007b6ab19dSGarrett Wollman 	    || rt->rt_dst != dst
15017b6ab19dSGarrett Wollman 	    || rt->rt_mask != mask)
15027b6ab19dSGarrett Wollman 		return 0;
15037b6ab19dSGarrett Wollman 
15047b6ab19dSGarrett Wollman 	return rt;
15057b6ab19dSGarrett Wollman }
15067b6ab19dSGarrett Wollman 
15077b6ab19dSGarrett Wollman 
15087b6ab19dSGarrett Wollman /* Find a route to dst as the kernel would.
15097b6ab19dSGarrett Wollman  */
15107b6ab19dSGarrett Wollman struct rt_entry *
15117b6ab19dSGarrett Wollman rtfind(naddr dst)
15127b6ab19dSGarrett Wollman {
15137b6ab19dSGarrett Wollman 	dst_sock.sin_addr.s_addr = dst;
15147b6ab19dSGarrett Wollman 	return (struct rt_entry *)rhead->rnh_matchaddr(&dst_sock, rhead);
15157b6ab19dSGarrett Wollman }
15167b6ab19dSGarrett Wollman 
15177b6ab19dSGarrett Wollman 
15187b6ab19dSGarrett Wollman /* add a route to the table
15197b6ab19dSGarrett Wollman  */
15207b6ab19dSGarrett Wollman void
15217b6ab19dSGarrett Wollman rtadd(naddr	dst,
15227b6ab19dSGarrett Wollman       naddr	mask,
15237b6ab19dSGarrett Wollman       naddr	gate,			/* forward packets here */
15247b6ab19dSGarrett Wollman       naddr	router,			/* on the authority of this router */
15257b6ab19dSGarrett Wollman       int	metric,
15267b6ab19dSGarrett Wollman       u_short	tag,
15277b6ab19dSGarrett Wollman       u_int	state,			/* rs_state for the entry */
15287b6ab19dSGarrett Wollman       struct interface *ifp)
15297b6ab19dSGarrett Wollman {
15307b6ab19dSGarrett Wollman 	struct rt_entry *rt;
15317b6ab19dSGarrett Wollman 	naddr smask;
15327b6ab19dSGarrett Wollman 	int i;
15337b6ab19dSGarrett Wollman 	struct rt_spare *rts;
15347b6ab19dSGarrett Wollman 
15357b6ab19dSGarrett Wollman 	rt = (struct rt_entry *)rtmalloc(sizeof (*rt), "rtadd");
15367b6ab19dSGarrett Wollman 	bzero(rt, sizeof(*rt));
15377b6ab19dSGarrett Wollman 	for (rts = rt->rt_spares, i = NUM_SPARES; i != 0; i--, rts++)
15387b6ab19dSGarrett Wollman 		rts->rts_metric = HOPCNT_INFINITY;
15397b6ab19dSGarrett Wollman 
15407b6ab19dSGarrett Wollman 	rt->rt_nodes->rn_key = (caddr_t)&rt->rt_dst_sock;
15417b6ab19dSGarrett Wollman 	rt->rt_dst = dst;
15427b6ab19dSGarrett Wollman 	rt->rt_dst_sock.sin_family = AF_INET;
15437b6ab19dSGarrett Wollman #ifdef _HAVE_SIN_LEN
15447b6ab19dSGarrett Wollman 	rt->rt_dst_sock.sin_len = dst_sock.sin_len;
15457b6ab19dSGarrett Wollman #endif
15467b6ab19dSGarrett Wollman 	if (mask != HOST_MASK) {
15477b6ab19dSGarrett Wollman 		smask = std_mask(dst);
15487b6ab19dSGarrett Wollman 		if ((smask & ~mask) == 0 && mask > smask)
15497b6ab19dSGarrett Wollman 			state |= RS_SUBNET;
15507b6ab19dSGarrett Wollman 	}
15517b6ab19dSGarrett Wollman 	mask_sock.sin_addr.s_addr = mask;
15527b6ab19dSGarrett Wollman 	masktrim(&mask_sock);
15537b6ab19dSGarrett Wollman 	rt->rt_mask = mask;
15547b6ab19dSGarrett Wollman 	rt->rt_state = state;
15557b6ab19dSGarrett Wollman 	rt->rt_gate = gate;
15567b6ab19dSGarrett Wollman 	rt->rt_router = router;
15577b6ab19dSGarrett Wollman 	rt->rt_time = now.tv_sec;
15587b6ab19dSGarrett Wollman 	rt->rt_metric = metric;
15597b6ab19dSGarrett Wollman 	rt->rt_poison_metric = HOPCNT_INFINITY;
15607b6ab19dSGarrett Wollman 	rt->rt_tag = tag;
15617b6ab19dSGarrett Wollman 	rt->rt_ifp = ifp;
15627b6ab19dSGarrett Wollman 	rt->rt_seqno = update_seqno;
15637b6ab19dSGarrett Wollman 
15647b6ab19dSGarrett Wollman 	if (++total_routes == MAX_ROUTES)
15657b6ab19dSGarrett Wollman 		msglog("have maximum (%d) routes", total_routes);
15667b6ab19dSGarrett Wollman 	if (TRACEACTIONS)
15677b6ab19dSGarrett Wollman 		trace_add_del("Add", rt);
15687b6ab19dSGarrett Wollman 
15697b6ab19dSGarrett Wollman 	need_kern.tv_sec = now.tv_sec;
15707b6ab19dSGarrett Wollman 	set_need_flash();
15717b6ab19dSGarrett Wollman 
15727b6ab19dSGarrett Wollman 	if (0 == rhead->rnh_addaddr(&rt->rt_dst_sock, &mask_sock,
15737b6ab19dSGarrett Wollman 				    rhead, rt->rt_nodes)) {
157450d2cb3eSGarrett Wollman /*
157550d2cb3eSGarrett Wollman  * This will happen if RIP1 and RIP2 routeds talk to one another and
157650d2cb3eSGarrett Wollman  * there are variable subnets.  This is only good for filling up your
157750d2cb3eSGarrett Wollman  * syslog. -jkh
157850d2cb3eSGarrett Wollman  */
157950d2cb3eSGarrett Wollman #if 0
15807b6ab19dSGarrett Wollman 		msglog("rnh_addaddr() failed for %s mask=%#x",
15817b6ab19dSGarrett Wollman 		       naddr_ntoa(dst), mask);
158250d2cb3eSGarrett Wollman #endif
15837b6ab19dSGarrett Wollman 	}
15847b6ab19dSGarrett Wollman }
15857b6ab19dSGarrett Wollman 
15867b6ab19dSGarrett Wollman 
15877b6ab19dSGarrett Wollman /* notice a changed route
15887b6ab19dSGarrett Wollman  */
15897b6ab19dSGarrett Wollman void
15907b6ab19dSGarrett Wollman rtchange(struct rt_entry *rt,
15917b6ab19dSGarrett Wollman 	 u_int	state,			/* new state bits */
15927b6ab19dSGarrett Wollman 	 naddr	gate,			/* now forward packets here */
15937b6ab19dSGarrett Wollman 	 naddr	router,			/* on the authority of this router */
15947b6ab19dSGarrett Wollman 	 int	metric,			/* new metric */
15957b6ab19dSGarrett Wollman 	 u_short tag,
15967b6ab19dSGarrett Wollman 	 struct interface *ifp,
15977b6ab19dSGarrett Wollman 	 time_t	new_time,
15987b6ab19dSGarrett Wollman 	 char	*label)
15997b6ab19dSGarrett Wollman {
16007b6ab19dSGarrett Wollman 	if (rt->rt_metric != metric) {
16017b6ab19dSGarrett Wollman 		/* Fix the kernel immediately if it seems the route
16027b6ab19dSGarrett Wollman 		 * has gone bad, since there may be a working route that
16037b6ab19dSGarrett Wollman 		 * aggregates this route.
16047b6ab19dSGarrett Wollman 		 */
16057b6ab19dSGarrett Wollman 		if (metric == HOPCNT_INFINITY) {
16067b6ab19dSGarrett Wollman 			need_kern.tv_sec = now.tv_sec;
16077b6ab19dSGarrett Wollman 			if (new_time >= now.tv_sec - EXPIRE_TIME)
16087b6ab19dSGarrett Wollman 				new_time = now.tv_sec - EXPIRE_TIME;
16097b6ab19dSGarrett Wollman 		}
16107b6ab19dSGarrett Wollman 		rt->rt_seqno = update_seqno;
16117b6ab19dSGarrett Wollman 		set_need_flash();
16127b6ab19dSGarrett Wollman 	}
16137b6ab19dSGarrett Wollman 
16147b6ab19dSGarrett Wollman 	if (rt->rt_gate != gate) {
16157b6ab19dSGarrett Wollman 		need_kern.tv_sec = now.tv_sec;
16167b6ab19dSGarrett Wollman 		rt->rt_seqno = update_seqno;
16177b6ab19dSGarrett Wollman 		set_need_flash();
16187b6ab19dSGarrett Wollman 	}
16197b6ab19dSGarrett Wollman 
16207b6ab19dSGarrett Wollman 	state |= (rt->rt_state & RS_SUBNET);
16217b6ab19dSGarrett Wollman 
16227b6ab19dSGarrett Wollman 	/* Keep various things from deciding ageless routes are stale.
16237b6ab19dSGarrett Wollman 	 */
16247b6ab19dSGarrett Wollman 	if (!AGE_RT(state, ifp))
16257b6ab19dSGarrett Wollman 		new_time = now.tv_sec;
16267b6ab19dSGarrett Wollman 
16277b6ab19dSGarrett Wollman 	if (TRACEACTIONS)
16287b6ab19dSGarrett Wollman 		trace_change(rt, state, gate, router, metric, tag, ifp,
16297b6ab19dSGarrett Wollman 			     new_time,
16307b6ab19dSGarrett Wollman 			     label ? label : "Chg   ");
16317b6ab19dSGarrett Wollman 
16327b6ab19dSGarrett Wollman 	rt->rt_state = state;
16337b6ab19dSGarrett Wollman 	rt->rt_gate = gate;
16347b6ab19dSGarrett Wollman 	rt->rt_router = router;
16357b6ab19dSGarrett Wollman 	rt->rt_metric = metric;
16367b6ab19dSGarrett Wollman 	rt->rt_tag = tag;
16377b6ab19dSGarrett Wollman 	rt->rt_ifp = ifp;
16387b6ab19dSGarrett Wollman 	rt->rt_time = new_time;
16397b6ab19dSGarrett Wollman }
16407b6ab19dSGarrett Wollman 
16417b6ab19dSGarrett Wollman 
16427b6ab19dSGarrett Wollman /* check for a better route among the spares
16437b6ab19dSGarrett Wollman  */
16447b6ab19dSGarrett Wollman static struct rt_spare *
16457b6ab19dSGarrett Wollman rts_better(struct rt_entry *rt)
16467b6ab19dSGarrett Wollman {
16477b6ab19dSGarrett Wollman 	struct rt_spare *rts, *rts1;
16487b6ab19dSGarrett Wollman 	int i;
16497b6ab19dSGarrett Wollman 
16507b6ab19dSGarrett Wollman 	/* find the best alternative among the spares */
16517b6ab19dSGarrett Wollman 	rts = rt->rt_spares+1;
16527b6ab19dSGarrett Wollman 	for (i = NUM_SPARES, rts1 = rts+1; i > 2; i--, rts1++) {
16537b6ab19dSGarrett Wollman 		if (BETTER_LINK(rt,rts1,rts))
16547b6ab19dSGarrett Wollman 			rts = rts1;
16557b6ab19dSGarrett Wollman 	}
16567b6ab19dSGarrett Wollman 
16577b6ab19dSGarrett Wollman 	return rts;
16587b6ab19dSGarrett Wollman }
16597b6ab19dSGarrett Wollman 
16607b6ab19dSGarrett Wollman 
16617b6ab19dSGarrett Wollman /* switch to a backup route
16627b6ab19dSGarrett Wollman  */
16637b6ab19dSGarrett Wollman void
16647b6ab19dSGarrett Wollman rtswitch(struct rt_entry *rt,
16657b6ab19dSGarrett Wollman 	 struct rt_spare *rts)
16667b6ab19dSGarrett Wollman {
16677b6ab19dSGarrett Wollman 	struct rt_spare swap;
16687b6ab19dSGarrett Wollman 	char label[10];
16697b6ab19dSGarrett Wollman 
16707b6ab19dSGarrett Wollman 
16717b6ab19dSGarrett Wollman 	/* Do not change permanent routes */
16727b6ab19dSGarrett Wollman 	if (0 != (rt->rt_state & (RS_MHOME | RS_STATIC | RS_RDISC
16737b6ab19dSGarrett Wollman 				  | RS_NET_SYN | RS_IF)))
16747b6ab19dSGarrett Wollman 		return;
16757b6ab19dSGarrett Wollman 
16767b6ab19dSGarrett Wollman 	/* find the best alternative among the spares */
16777b6ab19dSGarrett Wollman 	if (rts == 0)
16787b6ab19dSGarrett Wollman 		rts = rts_better(rt);
16797b6ab19dSGarrett Wollman 
16807b6ab19dSGarrett Wollman 	/* Do not bother if it is not worthwhile.
16817b6ab19dSGarrett Wollman 	 */
16827b6ab19dSGarrett Wollman 	if (!BETTER_LINK(rt, rts, rt->rt_spares))
16837b6ab19dSGarrett Wollman 		return;
16847b6ab19dSGarrett Wollman 
16857b6ab19dSGarrett Wollman 	swap = rt->rt_spares[0];
16867b6ab19dSGarrett Wollman 	(void)sprintf(label, "Use #%d", rts - rt->rt_spares);
16877b6ab19dSGarrett Wollman 	rtchange(rt, rt->rt_state & ~(RS_NET_SYN | RS_RDISC),
16887b6ab19dSGarrett Wollman 		 rts->rts_gate, rts->rts_router, rts->rts_metric,
16897b6ab19dSGarrett Wollman 		 rts->rts_tag, rts->rts_ifp, rts->rts_time, label);
16907b6ab19dSGarrett Wollman 	*rts = swap;
16917b6ab19dSGarrett Wollman }
16927b6ab19dSGarrett Wollman 
16937b6ab19dSGarrett Wollman 
16947b6ab19dSGarrett Wollman void
16957b6ab19dSGarrett Wollman rtdelete(struct rt_entry *rt)
16967b6ab19dSGarrett Wollman {
16977b6ab19dSGarrett Wollman 	struct khash *k;
16987b6ab19dSGarrett Wollman 
16997b6ab19dSGarrett Wollman 
17007b6ab19dSGarrett Wollman 	if (TRACEACTIONS)
17017b6ab19dSGarrett Wollman 		trace_add_del("Del", rt);
17027b6ab19dSGarrett Wollman 
17037b6ab19dSGarrett Wollman 	k = kern_find(rt->rt_dst, rt->rt_mask, 0);
17047b6ab19dSGarrett Wollman 	if (k != 0) {
17057b6ab19dSGarrett Wollman 		k->k_state |= KS_DELETE;
17067b6ab19dSGarrett Wollman 		need_kern.tv_sec = now.tv_sec;
17077b6ab19dSGarrett Wollman 	}
17087b6ab19dSGarrett Wollman 
17097b6ab19dSGarrett Wollman 	dst_sock.sin_addr.s_addr = rt->rt_dst;
17107b6ab19dSGarrett Wollman 	mask_sock.sin_addr.s_addr = rt->rt_mask;
17117b6ab19dSGarrett Wollman 	masktrim(&mask_sock);
17127b6ab19dSGarrett Wollman 	if (rt != (struct rt_entry *)rhead->rnh_deladdr(&dst_sock, &mask_sock,
17137b6ab19dSGarrett Wollman 							rhead)) {
17147b6ab19dSGarrett Wollman 		msglog("rnh_deladdr() failed");
17157b6ab19dSGarrett Wollman 	} else {
17167b6ab19dSGarrett Wollman 		free(rt);
17177b6ab19dSGarrett Wollman 		total_routes--;
17187b6ab19dSGarrett Wollman 	}
17197b6ab19dSGarrett Wollman }
17207b6ab19dSGarrett Wollman 
17217b6ab19dSGarrett Wollman 
17227b6ab19dSGarrett Wollman /* Get rid of a bad route, and try to switch to a replacement.
17237b6ab19dSGarrett Wollman  */
17247b6ab19dSGarrett Wollman void
17257b6ab19dSGarrett Wollman rtbad(struct rt_entry *rt)
17267b6ab19dSGarrett Wollman {
17277b6ab19dSGarrett Wollman 	/* Poison the route */
17287b6ab19dSGarrett Wollman 	rtchange(rt, rt->rt_state & ~(RS_IF | RS_LOCAL | RS_STATIC),
17297b6ab19dSGarrett Wollman 		 rt->rt_gate, rt->rt_router, HOPCNT_INFINITY, rt->rt_tag,
17307b6ab19dSGarrett Wollman 		 0, rt->rt_time, 0);
17317b6ab19dSGarrett Wollman 
17327b6ab19dSGarrett Wollman 	rtswitch(rt, 0);
17337b6ab19dSGarrett Wollman }
17347b6ab19dSGarrett Wollman 
17357b6ab19dSGarrett Wollman 
17367b6ab19dSGarrett Wollman /* Junk a RS_NET_SYN or RS_LOCAL route,
17377b6ab19dSGarrett Wollman  *	unless it is needed by another interface.
17387b6ab19dSGarrett Wollman  */
17397b6ab19dSGarrett Wollman void
17407b6ab19dSGarrett Wollman rtbad_sub(struct rt_entry *rt)
17417b6ab19dSGarrett Wollman {
17427b6ab19dSGarrett Wollman 	struct interface *ifp, *ifp1;
17437b6ab19dSGarrett Wollman 	struct intnet *intnetp;
17447b6ab19dSGarrett Wollman 	u_int state;
17457b6ab19dSGarrett Wollman 
17467b6ab19dSGarrett Wollman 
17477b6ab19dSGarrett Wollman 	ifp1 = 0;
17487b6ab19dSGarrett Wollman 	state = 0;
17497b6ab19dSGarrett Wollman 
17507b6ab19dSGarrett Wollman 	if (rt->rt_state & RS_LOCAL) {
17517b6ab19dSGarrett Wollman 		/* Is this the route through loopback for the interface?
17527b6ab19dSGarrett Wollman 		 * If so, see if it is used by any other interfaces, such
17537b6ab19dSGarrett Wollman 		 * as a point-to-point interface with the same local address.
17547b6ab19dSGarrett Wollman 		 */
17557b6ab19dSGarrett Wollman 		for (ifp = ifnet; ifp != 0; ifp = ifp->int_next) {
17567b6ab19dSGarrett Wollman 			/* Retain it if another interface needs it.
17577b6ab19dSGarrett Wollman 			 */
17587b6ab19dSGarrett Wollman 			if (ifp->int_addr == rt->rt_ifp->int_addr) {
17597b6ab19dSGarrett Wollman 				state |= RS_LOCAL;
17607b6ab19dSGarrett Wollman 				ifp1 = ifp;
17617b6ab19dSGarrett Wollman 				break;
17627b6ab19dSGarrett Wollman 			}
17637b6ab19dSGarrett Wollman 		}
17647b6ab19dSGarrett Wollman 
17657b6ab19dSGarrett Wollman 	}
17667b6ab19dSGarrett Wollman 
17677b6ab19dSGarrett Wollman 	if (!(state & RS_LOCAL)) {
17687b6ab19dSGarrett Wollman 		/* Retain RIPv1 logical network route if there is another
17697b6ab19dSGarrett Wollman 		 * interface that justifies it.
17707b6ab19dSGarrett Wollman 		 */
17717b6ab19dSGarrett Wollman 		if (rt->rt_state & RS_NET_SYN) {
17727b6ab19dSGarrett Wollman 			for (ifp = ifnet; ifp != 0; ifp = ifp->int_next) {
17737b6ab19dSGarrett Wollman 				if ((ifp->int_state & IS_NEED_NET_SYN)
17747b6ab19dSGarrett Wollman 				    && rt->rt_mask == ifp->int_std_mask
17757b6ab19dSGarrett Wollman 				    && rt->rt_dst == ifp->int_std_addr) {
17767b6ab19dSGarrett Wollman 					state |= RS_NET_SYN;
17777b6ab19dSGarrett Wollman 					ifp1 = ifp;
17787b6ab19dSGarrett Wollman 					break;
17797b6ab19dSGarrett Wollman 				}
17807b6ab19dSGarrett Wollman 			}
17817b6ab19dSGarrett Wollman 		}
17827b6ab19dSGarrett Wollman 
17837b6ab19dSGarrett Wollman 		/* or if there is an authority route that needs it. */
17847b6ab19dSGarrett Wollman 		for (intnetp = intnets;
17857b6ab19dSGarrett Wollman 		     intnetp != 0;
17867b6ab19dSGarrett Wollman 		     intnetp = intnetp->intnet_next) {
17877b6ab19dSGarrett Wollman 			if (intnetp->intnet_addr == rt->rt_dst
17887b6ab19dSGarrett Wollman 			    && intnetp->intnet_mask == rt->rt_mask) {
17897b6ab19dSGarrett Wollman 				state |= (RS_NET_SYN | RS_NET_INT);
17907b6ab19dSGarrett Wollman 				break;
17917b6ab19dSGarrett Wollman 			}
17927b6ab19dSGarrett Wollman 		}
17937b6ab19dSGarrett Wollman 	}
17947b6ab19dSGarrett Wollman 
17957b6ab19dSGarrett Wollman 	if (ifp1 != 0 || (state & RS_NET_SYN)) {
17967b6ab19dSGarrett Wollman 		rtchange(rt, ((rt->rt_state & ~(RS_NET_SYN | RS_LOCAL))
17977b6ab19dSGarrett Wollman 			      | state),
17987b6ab19dSGarrett Wollman 			 rt->rt_gate, rt->rt_router, rt->rt_metric,
17997b6ab19dSGarrett Wollman 			 rt->rt_tag, ifp1, rt->rt_time, 0);
18007b6ab19dSGarrett Wollman 	} else {
18017b6ab19dSGarrett Wollman 		rtbad(rt);
18027b6ab19dSGarrett Wollman 	}
18037b6ab19dSGarrett Wollman }
18047b6ab19dSGarrett Wollman 
18057b6ab19dSGarrett Wollman 
18067b6ab19dSGarrett Wollman /* Called while walking the table looking for sick interfaces
18077b6ab19dSGarrett Wollman  * or after a time change.
18087b6ab19dSGarrett Wollman  */
18097b6ab19dSGarrett Wollman /* ARGSUSED */
18107b6ab19dSGarrett Wollman int
18117b6ab19dSGarrett Wollman walk_bad(struct radix_node *rn,
18127b6ab19dSGarrett Wollman 	 struct walkarg *w)
18137b6ab19dSGarrett Wollman {
18147b6ab19dSGarrett Wollman #define RT ((struct rt_entry *)rn)
18157b6ab19dSGarrett Wollman 	struct rt_spare *rts;
18167b6ab19dSGarrett Wollman 	int i;
18177b6ab19dSGarrett Wollman 	time_t new_time;
18187b6ab19dSGarrett Wollman 
18197b6ab19dSGarrett Wollman 
18207b6ab19dSGarrett Wollman 	/* fix any spare routes through the interface
18217b6ab19dSGarrett Wollman 	 */
18227b6ab19dSGarrett Wollman 	rts = RT->rt_spares;
18237b6ab19dSGarrett Wollman 	for (i = NUM_SPARES; i != 1; i--) {
18247b6ab19dSGarrett Wollman 		rts++;
18257b6ab19dSGarrett Wollman 
18267b6ab19dSGarrett Wollman 		if (rts->rts_ifp != 0
18277b6ab19dSGarrett Wollman 		    && (rts->rts_ifp->int_state & IS_BROKE)) {
18287b6ab19dSGarrett Wollman 			/* mark the spare route to be deleted immediately */
18297b6ab19dSGarrett Wollman 			new_time = rts->rts_time;
18307b6ab19dSGarrett Wollman 			if (new_time >= now_garbage)
18317b6ab19dSGarrett Wollman 				new_time = now_garbage-1;
18327b6ab19dSGarrett Wollman 			trace_upslot(RT, rts, rts->rts_gate,
18337b6ab19dSGarrett Wollman 				     rts->rts_router, 0,
18347b6ab19dSGarrett Wollman 				     HOPCNT_INFINITY, rts->rts_tag,
18357b6ab19dSGarrett Wollman 				     new_time);
18367b6ab19dSGarrett Wollman 			rts->rts_ifp = 0;
18377b6ab19dSGarrett Wollman 			rts->rts_metric = HOPCNT_INFINITY;
18387b6ab19dSGarrett Wollman 			rts->rts_time = new_time;
18397b6ab19dSGarrett Wollman 		}
18407b6ab19dSGarrett Wollman 	}
18417b6ab19dSGarrett Wollman 
18427b6ab19dSGarrett Wollman 	/* Deal with the main route
18437b6ab19dSGarrett Wollman 	 */
18447b6ab19dSGarrett Wollman 	/* finished if it has been handled before or if its interface is ok
18457b6ab19dSGarrett Wollman 	 */
18467b6ab19dSGarrett Wollman 	if (RT->rt_ifp == 0 || !(RT->rt_ifp->int_state & IS_BROKE))
18477b6ab19dSGarrett Wollman 		return 0;
18487b6ab19dSGarrett Wollman 
18497b6ab19dSGarrett Wollman 	/* Bad routes for other than interfaces are easy.
18507b6ab19dSGarrett Wollman 	 */
18517b6ab19dSGarrett Wollman 	if (0 == (RT->rt_state & (RS_IF | RS_NET_SYN | RS_LOCAL))) {
18527b6ab19dSGarrett Wollman 		rtbad(RT);
18537b6ab19dSGarrett Wollman 		return 0;
18547b6ab19dSGarrett Wollman 	}
18557b6ab19dSGarrett Wollman 
18567b6ab19dSGarrett Wollman 	rtbad_sub(RT);
18577b6ab19dSGarrett Wollman 	return 0;
18587b6ab19dSGarrett Wollman #undef RT
18597b6ab19dSGarrett Wollman }
18607b6ab19dSGarrett Wollman 
18617b6ab19dSGarrett Wollman 
18627b6ab19dSGarrett Wollman /* Check the age of an individual route.
18637b6ab19dSGarrett Wollman  */
18647b6ab19dSGarrett Wollman /* ARGSUSED */
18657b6ab19dSGarrett Wollman static int
18667b6ab19dSGarrett Wollman walk_age(struct radix_node *rn,
18677b6ab19dSGarrett Wollman 	   struct walkarg *w)
18687b6ab19dSGarrett Wollman {
18697b6ab19dSGarrett Wollman #define RT ((struct rt_entry *)rn)
18707b6ab19dSGarrett Wollman 	struct interface *ifp;
18717b6ab19dSGarrett Wollman 	struct rt_spare *rts;
18727b6ab19dSGarrett Wollman 	int i;
18737b6ab19dSGarrett Wollman 
18747b6ab19dSGarrett Wollman 
18757b6ab19dSGarrett Wollman 	/* age all of the spare routes, including the primary route
18767b6ab19dSGarrett Wollman 	 * currently in use
18777b6ab19dSGarrett Wollman 	 */
18787b6ab19dSGarrett Wollman 	rts = RT->rt_spares;
18797b6ab19dSGarrett Wollman 	for (i = NUM_SPARES; i != 0; i--, rts++) {
18807b6ab19dSGarrett Wollman 
18817b6ab19dSGarrett Wollman 		ifp = rts->rts_ifp;
18827b6ab19dSGarrett Wollman 		if (i == NUM_SPARES) {
18837b6ab19dSGarrett Wollman 			if (!AGE_RT(RT->rt_state, ifp)) {
18847b6ab19dSGarrett Wollman 				/* Keep various things from deciding ageless
18857b6ab19dSGarrett Wollman 				 * routes are stale
18867b6ab19dSGarrett Wollman 				 */
18877b6ab19dSGarrett Wollman 				rts->rts_time = now.tv_sec;
18887b6ab19dSGarrett Wollman 				continue;
18897b6ab19dSGarrett Wollman 			}
18907b6ab19dSGarrett Wollman 
18917b6ab19dSGarrett Wollman 			/* forget RIP routes after RIP has been turned off.
18927b6ab19dSGarrett Wollman 			 */
18937b6ab19dSGarrett Wollman 			if (rip_sock < 0) {
18947b6ab19dSGarrett Wollman 				rtdelete(RT);
18957b6ab19dSGarrett Wollman 				return 0;
18967b6ab19dSGarrett Wollman 			}
18977b6ab19dSGarrett Wollman 		}
18987b6ab19dSGarrett Wollman 
18997b6ab19dSGarrett Wollman 		/* age failing routes
19007b6ab19dSGarrett Wollman 		 */
19017b6ab19dSGarrett Wollman 		if (age_bad_gate == rts->rts_gate
19027b6ab19dSGarrett Wollman 		    && rts->rts_time >= now_stale) {
19037b6ab19dSGarrett Wollman 			rts->rts_time -= SUPPLY_INTERVAL;
19047b6ab19dSGarrett Wollman 		}
19057b6ab19dSGarrett Wollman 
19067b6ab19dSGarrett Wollman 		/* trash the spare routes when they go bad */
19077b6ab19dSGarrett Wollman 		if (rts->rts_metric < HOPCNT_INFINITY
19087b6ab19dSGarrett Wollman 		    && now_garbage > rts->rts_time) {
19097b6ab19dSGarrett Wollman 			trace_upslot(RT, rts, rts->rts_gate,
19107b6ab19dSGarrett Wollman 				     rts->rts_router, rts->rts_ifp,
19117b6ab19dSGarrett Wollman 				     HOPCNT_INFINITY, rts->rts_tag,
19127b6ab19dSGarrett Wollman 				     rts->rts_time);
19137b6ab19dSGarrett Wollman 			rts->rts_metric = HOPCNT_INFINITY;
19147b6ab19dSGarrett Wollman 		}
19157b6ab19dSGarrett Wollman 	}
19167b6ab19dSGarrett Wollman 
19177b6ab19dSGarrett Wollman 
19187b6ab19dSGarrett Wollman 	/* finished if the active route is still fresh */
19197b6ab19dSGarrett Wollman 	if (now_stale <= RT->rt_time)
19207b6ab19dSGarrett Wollman 		return 0;
19217b6ab19dSGarrett Wollman 
19227b6ab19dSGarrett Wollman 	/* try to switch to an alternative */
19237b6ab19dSGarrett Wollman 	rtswitch(RT, 0);
19247b6ab19dSGarrett Wollman 
19257b6ab19dSGarrett Wollman 	/* Delete a dead route after it has been publically mourned. */
19267b6ab19dSGarrett Wollman 	if (now_garbage > RT->rt_time) {
19277b6ab19dSGarrett Wollman 		rtdelete(RT);
19287b6ab19dSGarrett Wollman 		return 0;
19297b6ab19dSGarrett Wollman 	}
19307b6ab19dSGarrett Wollman 
19317b6ab19dSGarrett Wollman 	/* Start poisoning a bad route before deleting it. */
19327b6ab19dSGarrett Wollman 	if (now.tv_sec - RT->rt_time > EXPIRE_TIME)
19337b6ab19dSGarrett Wollman 		rtchange(RT, RT->rt_state, RT->rt_gate, RT->rt_router,
19347b6ab19dSGarrett Wollman 			 HOPCNT_INFINITY, RT->rt_tag, RT->rt_ifp,
19357b6ab19dSGarrett Wollman 			 RT->rt_time, 0);
19367b6ab19dSGarrett Wollman 	return 0;
19377b6ab19dSGarrett Wollman }
19387b6ab19dSGarrett Wollman 
19397b6ab19dSGarrett Wollman 
19407b6ab19dSGarrett Wollman /* Watch for dead routes and interfaces.
19417b6ab19dSGarrett Wollman  */
19427b6ab19dSGarrett Wollman void
19437b6ab19dSGarrett Wollman age(naddr bad_gate)
19447b6ab19dSGarrett Wollman {
19457b6ab19dSGarrett Wollman 	struct interface *ifp;
194652ad6021SGarrett Wollman 	int need_query = 0;
19477b6ab19dSGarrett Wollman 
194852ad6021SGarrett Wollman 	/* If not listening to RIP, there is no need to age the routes in
194952ad6021SGarrett Wollman 	 * the table.
195052ad6021SGarrett Wollman 	 */
195152ad6021SGarrett Wollman 	age_timer.tv_sec = (now.tv_sec
195252ad6021SGarrett Wollman 			    + ((rip_sock < 0) ? NEVER : SUPPLY_INTERVAL));
19537b6ab19dSGarrett Wollman 
19547b6ab19dSGarrett Wollman 	/* Check for dead IS_REMOTE interfaces by timing their
19557b6ab19dSGarrett Wollman 	 * transmissions.
19567b6ab19dSGarrett Wollman 	 */
195752ad6021SGarrett Wollman 	for (ifp = ifnet; ifp; ifp = ifp->int_next) {
195852ad6021SGarrett Wollman 		if (!(ifp->int_state & IS_REMOTE))
195952ad6021SGarrett Wollman 			continue;
19607b6ab19dSGarrett Wollman 
196152ad6021SGarrett Wollman 		/* ignore unreachable remote interfaces */
196252ad6021SGarrett Wollman 		if (!check_remote(ifp))
196352ad6021SGarrett Wollman 			continue;
196452ad6021SGarrett Wollman 		/* Restore remote interface that has become reachable
196552ad6021SGarrett Wollman 		 */
196652ad6021SGarrett Wollman 		if (ifp->int_state & IS_BROKE)
196752ad6021SGarrett Wollman 			if_ok(ifp, "remote ");
196852ad6021SGarrett Wollman 
196952ad6021SGarrett Wollman 		if (ifp->int_act_time != NEVER
197052ad6021SGarrett Wollman 		    && now.tv_sec - ifp->int_act_time > EXPIRE_TIME) {
197152ad6021SGarrett Wollman 			msglog("remote interface %s to %s timed out after"
197252ad6021SGarrett Wollman 			       " %d:%d",
19737b6ab19dSGarrett Wollman 			       ifp->int_name,
197452ad6021SGarrett Wollman 			       naddr_ntoa(ifp->int_dstaddr),
197552ad6021SGarrett Wollman 			       (now.tv_sec - ifp->int_act_time)/60,
197652ad6021SGarrett Wollman 			       (now.tv_sec - ifp->int_act_time)%60);
197752ad6021SGarrett Wollman 			if_sick(ifp);
19787b6ab19dSGarrett Wollman 		}
197952ad6021SGarrett Wollman 
198052ad6021SGarrett Wollman 		/* If we have not heard from the other router
198152ad6021SGarrett Wollman 		 * recently, ask it.
198252ad6021SGarrett Wollman 		 */
198352ad6021SGarrett Wollman 		if (now.tv_sec >= ifp->int_query_time) {
198452ad6021SGarrett Wollman 			ifp->int_query_time = NEVER;
198552ad6021SGarrett Wollman 			need_query = 1;
19867b6ab19dSGarrett Wollman 		}
19877b6ab19dSGarrett Wollman 	}
19887b6ab19dSGarrett Wollman 
19897b6ab19dSGarrett Wollman 	/* Age routes. */
19907b6ab19dSGarrett Wollman 	age_bad_gate = bad_gate;
19917b6ab19dSGarrett Wollman 	(void)rn_walktree(rhead, walk_age, 0);
19927b6ab19dSGarrett Wollman 
19937b6ab19dSGarrett Wollman 	/* Update the kernel routing table. */
19947b6ab19dSGarrett Wollman 	fix_kern();
199552ad6021SGarrett Wollman 
199652ad6021SGarrett Wollman 	/* poke reticent remote gateways */
199752ad6021SGarrett Wollman 	if (need_query)
199852ad6021SGarrett Wollman 		rip_query();
19997b6ab19dSGarrett Wollman }
2000