17c478bd9Sstevel@tonic-gate /*
2d52135a8SSowmini Varadhan  * Copyright 2010 Sun Microsystems, Inc.  All rights reserved.
37c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
47c478bd9Sstevel@tonic-gate  *
57c478bd9Sstevel@tonic-gate  * Copyright (c) 1983, 1988, 1993
67c478bd9Sstevel@tonic-gate  *	The Regents of the University of California.  All rights reserved.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * Redistribution and use in source and binary forms, with or without
97c478bd9Sstevel@tonic-gate  * modification, are permitted provided that the following conditions
107c478bd9Sstevel@tonic-gate  * are met:
117c478bd9Sstevel@tonic-gate  * 1. Redistributions of source code must retain the above copyright
127c478bd9Sstevel@tonic-gate  *    notice, this list of conditions and the following disclaimer.
137c478bd9Sstevel@tonic-gate  * 2. Redistributions in binary form must reproduce the above copyright
147c478bd9Sstevel@tonic-gate  *    notice, this list of conditions and the following disclaimer in the
157c478bd9Sstevel@tonic-gate  *    documentation and/or other materials provided with the distribution.
167c478bd9Sstevel@tonic-gate  * 3. All advertising materials mentioning features or use of this software
177c478bd9Sstevel@tonic-gate  *    must display the following acknowledgment:
187c478bd9Sstevel@tonic-gate  *	This product includes software developed by the University of
197c478bd9Sstevel@tonic-gate  *	California, Berkeley and its contributors.
207c478bd9Sstevel@tonic-gate  * 4. Neither the name of the University nor the names of its contributors
217c478bd9Sstevel@tonic-gate  *    may be used to endorse or promote products derived from this software
227c478bd9Sstevel@tonic-gate  *    without specific prior written permission.
237c478bd9Sstevel@tonic-gate  *
247c478bd9Sstevel@tonic-gate  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
257c478bd9Sstevel@tonic-gate  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
267c478bd9Sstevel@tonic-gate  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
277c478bd9Sstevel@tonic-gate  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
287c478bd9Sstevel@tonic-gate  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
297c478bd9Sstevel@tonic-gate  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
307c478bd9Sstevel@tonic-gate  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
317c478bd9Sstevel@tonic-gate  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
327c478bd9Sstevel@tonic-gate  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
337c478bd9Sstevel@tonic-gate  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
347c478bd9Sstevel@tonic-gate  * SUCH DAMAGE.
357c478bd9Sstevel@tonic-gate  *
367c478bd9Sstevel@tonic-gate  * $FreeBSD: src/sbin/routed/table.c,v 1.15 2000/08/11 08:24:38 sheldonh Exp $
377c478bd9Sstevel@tonic-gate  */
387c478bd9Sstevel@tonic-gate 
397c478bd9Sstevel@tonic-gate #include "defs.h"
407c478bd9Sstevel@tonic-gate #include <fcntl.h>
417c478bd9Sstevel@tonic-gate #include <stropts.h>
427c478bd9Sstevel@tonic-gate #include <sys/tihdr.h>
437c478bd9Sstevel@tonic-gate #include <inet/mib2.h>
447c478bd9Sstevel@tonic-gate #include <inet/ip.h>
457c478bd9Sstevel@tonic-gate 
467c478bd9Sstevel@tonic-gate /* This structure is used to store a disassembled routing socket message. */
477c478bd9Sstevel@tonic-gate struct rt_addrinfo {
487c478bd9Sstevel@tonic-gate 	int	rti_addrs;
497c478bd9Sstevel@tonic-gate 	struct sockaddr_storage *rti_info[RTAX_MAX];
507c478bd9Sstevel@tonic-gate };
517c478bd9Sstevel@tonic-gate 
527c478bd9Sstevel@tonic-gate static struct rt_spare *rts_better(struct rt_entry *);
537c478bd9Sstevel@tonic-gate static struct rt_spare rts_empty = EMPTY_RT_SPARE;
547c478bd9Sstevel@tonic-gate static void set_need_flash(void);
557c478bd9Sstevel@tonic-gate static void rtbad(struct rt_entry *, struct interface *);
567c478bd9Sstevel@tonic-gate static int rt_xaddrs(struct rt_addrinfo *, struct sockaddr_storage *,
577c478bd9Sstevel@tonic-gate     char *, int);
587c478bd9Sstevel@tonic-gate static struct interface *gwkludge_iflookup(in_addr_t, in_addr_t, in_addr_t);
59982ec2c2SRishi Srivatsavai static struct interface *lifp_iflookup(in_addr_t, const char *);
607c478bd9Sstevel@tonic-gate 
617c478bd9Sstevel@tonic-gate struct radix_node_head *rhead;		/* root of the radix tree */
627c478bd9Sstevel@tonic-gate 
637c478bd9Sstevel@tonic-gate /* Flash update needed.  _B_TRUE to suppress the 1st. */
647c478bd9Sstevel@tonic-gate boolean_t need_flash = _B_TRUE;
657c478bd9Sstevel@tonic-gate 
667c478bd9Sstevel@tonic-gate struct timeval age_timer;		/* next check of old routes */
677c478bd9Sstevel@tonic-gate struct timeval need_kern = {		/* need to update kernel table */
687c478bd9Sstevel@tonic-gate 	EPOCH+MIN_WAITTIME-1, 0
697c478bd9Sstevel@tonic-gate };
707c478bd9Sstevel@tonic-gate 
717c478bd9Sstevel@tonic-gate static uint32_t	total_routes;
727c478bd9Sstevel@tonic-gate 
737c478bd9Sstevel@tonic-gate #define	ROUNDUP_LONG(a) \
747c478bd9Sstevel@tonic-gate 	((a) > 0 ? (1 + (((a) - 1) | (sizeof (long) - 1))) : sizeof (long))
757c478bd9Sstevel@tonic-gate 
767c478bd9Sstevel@tonic-gate /*
777c478bd9Sstevel@tonic-gate  * It is desirable to "aggregate" routes, to combine differing routes of
787c478bd9Sstevel@tonic-gate  * the same metric and next hop into a common route with a smaller netmask
797c478bd9Sstevel@tonic-gate  * or to suppress redundant routes, routes that add no information to
807c478bd9Sstevel@tonic-gate  * routes with smaller netmasks.
817c478bd9Sstevel@tonic-gate  *
827c478bd9Sstevel@tonic-gate  * A route is redundant if and only if any and all routes with smaller
837c478bd9Sstevel@tonic-gate  * but matching netmasks and nets are the same.  Since routes are
847c478bd9Sstevel@tonic-gate  * kept sorted in the radix tree, redundant routes always come second.
857c478bd9Sstevel@tonic-gate  *
867c478bd9Sstevel@tonic-gate  * There are two kinds of aggregations.  First, two routes of the same bit
877c478bd9Sstevel@tonic-gate  * mask and differing only in the least significant bit of the network
887c478bd9Sstevel@tonic-gate  * number can be combined into a single route with a coarser mask.
897c478bd9Sstevel@tonic-gate  *
907c478bd9Sstevel@tonic-gate  * Second, a route can be suppressed in favor of another route with a more
917c478bd9Sstevel@tonic-gate  * coarse mask provided no incompatible routes with intermediate masks
927c478bd9Sstevel@tonic-gate  * are present.  The second kind of aggregation involves suppressing routes.
937c478bd9Sstevel@tonic-gate  * A route must not be suppressed if an incompatible route exists with
947c478bd9Sstevel@tonic-gate  * an intermediate mask, since the suppressed route would be covered
957c478bd9Sstevel@tonic-gate  * by the intermediate.
967c478bd9Sstevel@tonic-gate  *
977c478bd9Sstevel@tonic-gate  * This code relies on the radix tree walk encountering routes
987c478bd9Sstevel@tonic-gate  * sorted first by address, with the smallest address first.
997c478bd9Sstevel@tonic-gate  */
1007c478bd9Sstevel@tonic-gate 
1017c478bd9Sstevel@tonic-gate static struct ag_info ag_slots[NUM_AG_SLOTS], *ag_avail, *ag_corsest,
1027c478bd9Sstevel@tonic-gate 	*ag_finest;
1037c478bd9Sstevel@tonic-gate 
1047c478bd9Sstevel@tonic-gate #ifdef DEBUG_AG
1057c478bd9Sstevel@tonic-gate #define	CHECK_AG() do { int acnt = 0; struct ag_info *cag;	\
1067c478bd9Sstevel@tonic-gate 	for (cag = ag_avail; cag != NULL; cag = cag->ag_fine)	\
1077c478bd9Sstevel@tonic-gate 		acnt++;						\
1087c478bd9Sstevel@tonic-gate 	for (cag = ag_corsest; cag != NULL; cag = cag->ag_fine)	\
1097c478bd9Sstevel@tonic-gate 		acnt++;						\
1107c478bd9Sstevel@tonic-gate 	if (acnt != NUM_AG_SLOTS)				\
1117c478bd9Sstevel@tonic-gate 		abort();					\
1127c478bd9Sstevel@tonic-gate } while (_B_FALSE)
1137c478bd9Sstevel@tonic-gate #else
1147c478bd9Sstevel@tonic-gate #define	CHECK_AG()	(void)0
1157c478bd9Sstevel@tonic-gate #endif
1167c478bd9Sstevel@tonic-gate 
1177c478bd9Sstevel@tonic-gate 
1187c478bd9Sstevel@tonic-gate /*
1197c478bd9Sstevel@tonic-gate  * Output the contents of an aggregation table slot.
1207c478bd9Sstevel@tonic-gate  *	This function must always be immediately followed with the deletion
1217c478bd9Sstevel@tonic-gate  *	of the target slot.
1227c478bd9Sstevel@tonic-gate  */
1237c478bd9Sstevel@tonic-gate static void
ag_out(struct ag_info * ag,void (* out)(struct ag_info *))1247c478bd9Sstevel@tonic-gate ag_out(struct ag_info *ag, void (*out)(struct ag_info *))
1257c478bd9Sstevel@tonic-gate {
1267c478bd9Sstevel@tonic-gate 	struct ag_info *ag_cors;
1277c478bd9Sstevel@tonic-gate 	uint32_t bit;
1287c478bd9Sstevel@tonic-gate 
1297c478bd9Sstevel@tonic-gate 
1307c478bd9Sstevel@tonic-gate 	/* Forget it if this route should not be output for split-horizon. */
1317c478bd9Sstevel@tonic-gate 	if (ag->ag_state & AGS_SPLIT_HZ)
1327c478bd9Sstevel@tonic-gate 		return;
1337c478bd9Sstevel@tonic-gate 
1347c478bd9Sstevel@tonic-gate 	/*
1357c478bd9Sstevel@tonic-gate 	 * If we output both the even and odd twins, then the immediate parent,
1367c478bd9Sstevel@tonic-gate 	 * if it is present, is redundant, unless the parent manages to
1377c478bd9Sstevel@tonic-gate 	 * aggregate into something coarser.
1387c478bd9Sstevel@tonic-gate 	 * On successive calls, this code detects the even and odd twins,
1397c478bd9Sstevel@tonic-gate 	 * and marks the parent.
1407c478bd9Sstevel@tonic-gate 	 *
1417c478bd9Sstevel@tonic-gate 	 * Note that the order in which the radix tree code emits routes
1427c478bd9Sstevel@tonic-gate 	 * ensures that the twins are seen before the parent is emitted.
1437c478bd9Sstevel@tonic-gate 	 */
1447c478bd9Sstevel@tonic-gate 	ag_cors = ag->ag_cors;
1457c478bd9Sstevel@tonic-gate 	if (ag_cors != NULL &&
1467c478bd9Sstevel@tonic-gate 	    ag_cors->ag_mask == (ag->ag_mask << 1) &&
1477c478bd9Sstevel@tonic-gate 	    ag_cors->ag_dst_h == (ag->ag_dst_h & ag_cors->ag_mask)) {
1487c478bd9Sstevel@tonic-gate 		ag_cors->ag_state |= ((ag_cors->ag_dst_h == ag->ag_dst_h) ?
1497c478bd9Sstevel@tonic-gate 		    AGS_REDUN0 : AGS_REDUN1);
1507c478bd9Sstevel@tonic-gate 	}
1517c478bd9Sstevel@tonic-gate 
1527c478bd9Sstevel@tonic-gate 	/*
1537c478bd9Sstevel@tonic-gate 	 * Skip it if this route is itself redundant.
1547c478bd9Sstevel@tonic-gate 	 *
1557c478bd9Sstevel@tonic-gate 	 * It is ok to change the contents of the slot here, since it is
1567c478bd9Sstevel@tonic-gate 	 * always deleted next.
1577c478bd9Sstevel@tonic-gate 	 */
1587c478bd9Sstevel@tonic-gate 	if (ag->ag_state & AGS_REDUN0) {
1597c478bd9Sstevel@tonic-gate 		if (ag->ag_state & AGS_REDUN1)
1607c478bd9Sstevel@tonic-gate 			return;		/* quit if fully redundant */
1617c478bd9Sstevel@tonic-gate 		/* make it finer if it is half-redundant */
1627c478bd9Sstevel@tonic-gate 		bit = (-ag->ag_mask) >> 1;
1637c478bd9Sstevel@tonic-gate 		ag->ag_dst_h |= bit;
1647c478bd9Sstevel@tonic-gate 		ag->ag_mask |= bit;
1657c478bd9Sstevel@tonic-gate 
1667c478bd9Sstevel@tonic-gate 	} else if (ag->ag_state & AGS_REDUN1) {
1677c478bd9Sstevel@tonic-gate 		/* make it finer if it is half-redundant */
1687c478bd9Sstevel@tonic-gate 		bit = (-ag->ag_mask) >> 1;
1697c478bd9Sstevel@tonic-gate 		ag->ag_mask |= bit;
1707c478bd9Sstevel@tonic-gate 	}
1717c478bd9Sstevel@tonic-gate 	out(ag);
1727c478bd9Sstevel@tonic-gate }
1737c478bd9Sstevel@tonic-gate 
1747c478bd9Sstevel@tonic-gate 
1757c478bd9Sstevel@tonic-gate static void
ag_del(struct ag_info * ag)1767c478bd9Sstevel@tonic-gate ag_del(struct ag_info *ag)
1777c478bd9Sstevel@tonic-gate {
1787c478bd9Sstevel@tonic-gate 	CHECK_AG();
1797c478bd9Sstevel@tonic-gate 
1807c478bd9Sstevel@tonic-gate 	if (ag->ag_cors == NULL)
1817c478bd9Sstevel@tonic-gate 		ag_corsest = ag->ag_fine;
1827c478bd9Sstevel@tonic-gate 	else
1837c478bd9Sstevel@tonic-gate 		ag->ag_cors->ag_fine = ag->ag_fine;
1847c478bd9Sstevel@tonic-gate 
1857c478bd9Sstevel@tonic-gate 	if (ag->ag_fine == NULL)
1867c478bd9Sstevel@tonic-gate 		ag_finest = ag->ag_cors;
1877c478bd9Sstevel@tonic-gate 	else
1887c478bd9Sstevel@tonic-gate 		ag->ag_fine->ag_cors = ag->ag_cors;
1897c478bd9Sstevel@tonic-gate 
1907c478bd9Sstevel@tonic-gate 	ag->ag_fine = ag_avail;
1917c478bd9Sstevel@tonic-gate 	ag_avail = ag;
1927c478bd9Sstevel@tonic-gate 
1937c478bd9Sstevel@tonic-gate 	CHECK_AG();
1947c478bd9Sstevel@tonic-gate }
1957c478bd9Sstevel@tonic-gate 
1967c478bd9Sstevel@tonic-gate 
1977c478bd9Sstevel@tonic-gate /* Look for a route that can suppress the given route. */
1987c478bd9Sstevel@tonic-gate static struct ag_info *
ag_find_suppressor(struct ag_info * ag)1997c478bd9Sstevel@tonic-gate ag_find_suppressor(struct ag_info *ag)
2007c478bd9Sstevel@tonic-gate {
2017c478bd9Sstevel@tonic-gate 	struct ag_info *ag_cors;
2027c478bd9Sstevel@tonic-gate 	in_addr_t dst_h = ag->ag_dst_h;
2037c478bd9Sstevel@tonic-gate 
2047c478bd9Sstevel@tonic-gate 	for (ag_cors = ag->ag_cors; ag_cors != NULL;
2057c478bd9Sstevel@tonic-gate 	    ag_cors = ag_cors->ag_cors) {
2067c478bd9Sstevel@tonic-gate 
2077c478bd9Sstevel@tonic-gate 		if ((dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h) {
2087c478bd9Sstevel@tonic-gate 			/*
2097c478bd9Sstevel@tonic-gate 			 * We found a route with a coarser mask that covers
2107c478bd9Sstevel@tonic-gate 			 * the given target.  It can suppress the target
2117c478bd9Sstevel@tonic-gate 			 * only if it has a good enough metric and it
2127c478bd9Sstevel@tonic-gate 			 * either has the same (gateway, ifp), or if its state
2137c478bd9Sstevel@tonic-gate 			 * includes AGS_CORS_GATE or the target's state
2147c478bd9Sstevel@tonic-gate 			 * includes AGS_FINE_GATE.
2157c478bd9Sstevel@tonic-gate 			 */
2167c478bd9Sstevel@tonic-gate 			if (ag_cors->ag_pref <= ag->ag_pref &&
2177c478bd9Sstevel@tonic-gate 			    (((ag->ag_nhop == ag_cors->ag_nhop) &&
2187c478bd9Sstevel@tonic-gate 			    (ag->ag_ifp == ag_cors->ag_ifp)) ||
2197c478bd9Sstevel@tonic-gate 			    ag_cors->ag_state & AGS_CORS_GATE ||
2207c478bd9Sstevel@tonic-gate 			    ag->ag_state & AGS_FINE_GATE)) {
2217c478bd9Sstevel@tonic-gate 				return (ag_cors);
2227c478bd9Sstevel@tonic-gate 			}
2237c478bd9Sstevel@tonic-gate 		}
2247c478bd9Sstevel@tonic-gate 	}
2257c478bd9Sstevel@tonic-gate 
2267c478bd9Sstevel@tonic-gate 	return (NULL);
2277c478bd9Sstevel@tonic-gate }
2287c478bd9Sstevel@tonic-gate 
2297c478bd9Sstevel@tonic-gate 
2307c478bd9Sstevel@tonic-gate /*
2317c478bd9Sstevel@tonic-gate  * Flush routes waiting for aggregation.
2327c478bd9Sstevel@tonic-gate  * This must not suppress a route unless it is known that among all routes
2337c478bd9Sstevel@tonic-gate  * with coarser masks that match it, the one with the longest mask is
2347c478bd9Sstevel@tonic-gate  * appropriate.  This is ensured by scanning the routes in lexical order,
2357c478bd9Sstevel@tonic-gate  * and with the most restrictive mask first among routes to the same
2367c478bd9Sstevel@tonic-gate  * destination.
2377c478bd9Sstevel@tonic-gate  */
2387c478bd9Sstevel@tonic-gate void
ag_flush(in_addr_t lim_dst_h,in_addr_t lim_mask,void (* out)(struct ag_info *))2397c478bd9Sstevel@tonic-gate ag_flush(in_addr_t lim_dst_h,	/* flush routes to here */
2407c478bd9Sstevel@tonic-gate     in_addr_t lim_mask,		/* matching this mask */
2417c478bd9Sstevel@tonic-gate     void (*out)(struct ag_info *))
2427c478bd9Sstevel@tonic-gate {
2437c478bd9Sstevel@tonic-gate 	struct ag_info *ag, *ag_cors, *ag_supr;
2447c478bd9Sstevel@tonic-gate 	in_addr_t dst_h;
2457c478bd9Sstevel@tonic-gate 
2467c478bd9Sstevel@tonic-gate 
2477c478bd9Sstevel@tonic-gate 	for (ag = ag_finest; ag != NULL && ag->ag_mask >= lim_mask;
2487c478bd9Sstevel@tonic-gate 	    ag = ag_cors) {
2497c478bd9Sstevel@tonic-gate 		/* Get the next route now, before we delete ag. */
2507c478bd9Sstevel@tonic-gate 		ag_cors = ag->ag_cors;
2517c478bd9Sstevel@tonic-gate 
2527c478bd9Sstevel@tonic-gate 		/* Work on only the specified routes. */
2537c478bd9Sstevel@tonic-gate 		dst_h = ag->ag_dst_h;
2547c478bd9Sstevel@tonic-gate 		if ((dst_h & lim_mask) != lim_dst_h)
2557c478bd9Sstevel@tonic-gate 			continue;
2567c478bd9Sstevel@tonic-gate 
2577c478bd9Sstevel@tonic-gate 		/*
2587c478bd9Sstevel@tonic-gate 		 * Don't try to suppress the route if its state doesn't
2597c478bd9Sstevel@tonic-gate 		 * include AGS_SUPPRESS.
2607c478bd9Sstevel@tonic-gate 		 */
2617c478bd9Sstevel@tonic-gate 		if (!(ag->ag_state & AGS_SUPPRESS)) {
2627c478bd9Sstevel@tonic-gate 			ag_out(ag, out);
2637c478bd9Sstevel@tonic-gate 			ag_del(ag);
2647c478bd9Sstevel@tonic-gate 			continue;
2657c478bd9Sstevel@tonic-gate 		}
2667c478bd9Sstevel@tonic-gate 
2677c478bd9Sstevel@tonic-gate 		ag_supr = ag_find_suppressor(ag);
2687c478bd9Sstevel@tonic-gate 		if (ag_supr == NULL) {
2697c478bd9Sstevel@tonic-gate 			/*
2707c478bd9Sstevel@tonic-gate 			 * We didn't find a route which suppresses the
2717c478bd9Sstevel@tonic-gate 			 * target, so the target can go out.
2727c478bd9Sstevel@tonic-gate 			 */
2737c478bd9Sstevel@tonic-gate 			ag_out(ag, out);
2747c478bd9Sstevel@tonic-gate 		} else {
2757c478bd9Sstevel@tonic-gate 			/*
2767c478bd9Sstevel@tonic-gate 			 * We found a route which suppresses the target, so
2777c478bd9Sstevel@tonic-gate 			 * don't output the target.
2787c478bd9Sstevel@tonic-gate 			 */
2797c478bd9Sstevel@tonic-gate 			if (TRACEACTIONS) {
2807c478bd9Sstevel@tonic-gate 				trace_misc("aggregated away %s",
2817c478bd9Sstevel@tonic-gate 				    rtname(htonl(ag->ag_dst_h), ag->ag_mask,
2827c478bd9Sstevel@tonic-gate 				    ag->ag_nhop));
2837c478bd9Sstevel@tonic-gate 				trace_misc("on coarser route %s",
2847c478bd9Sstevel@tonic-gate 				    rtname(htonl(ag_supr->ag_dst_h),
2857c478bd9Sstevel@tonic-gate 				    ag_supr->ag_mask, ag_supr->ag_nhop));
2867c478bd9Sstevel@tonic-gate 			}
2877c478bd9Sstevel@tonic-gate 			/*
2887c478bd9Sstevel@tonic-gate 			 * If the suppressed target was redundant, then
2897c478bd9Sstevel@tonic-gate 			 * mark the suppressor as redundant.
2907c478bd9Sstevel@tonic-gate 			 */
2917c478bd9Sstevel@tonic-gate 			if (AG_IS_REDUN(ag->ag_state) &&
2927c478bd9Sstevel@tonic-gate 			    ag_supr->ag_mask == (ag->ag_mask<<1)) {
2937c478bd9Sstevel@tonic-gate 				if (ag_supr->ag_dst_h == dst_h)
2947c478bd9Sstevel@tonic-gate 					ag_supr->ag_state |= AGS_REDUN0;
2957c478bd9Sstevel@tonic-gate 				else
2967c478bd9Sstevel@tonic-gate 					ag_supr->ag_state |= AGS_REDUN1;
2977c478bd9Sstevel@tonic-gate 			}
2987c478bd9Sstevel@tonic-gate 			if (ag->ag_tag != ag_supr->ag_tag)
2997c478bd9Sstevel@tonic-gate 				ag_supr->ag_tag = 0;
3007c478bd9Sstevel@tonic-gate 			if (ag->ag_nhop != ag_supr->ag_nhop)
3017c478bd9Sstevel@tonic-gate 				ag_supr->ag_nhop = 0;
3027c478bd9Sstevel@tonic-gate 		}
3037c478bd9Sstevel@tonic-gate 
3047c478bd9Sstevel@tonic-gate 		/* The route has either been output or suppressed */
3057c478bd9Sstevel@tonic-gate 		ag_del(ag);
3067c478bd9Sstevel@tonic-gate 	}
3077c478bd9Sstevel@tonic-gate 
3087c478bd9Sstevel@tonic-gate 	CHECK_AG();
3097c478bd9Sstevel@tonic-gate }
3107c478bd9Sstevel@tonic-gate 
3117c478bd9Sstevel@tonic-gate 
3127c478bd9Sstevel@tonic-gate /* Try to aggregate a route with previous routes. */
3137c478bd9Sstevel@tonic-gate void
ag_check(in_addr_t dst,in_addr_t mask,in_addr_t gate,struct interface * ifp,in_addr_t nhop,uint8_t metric,uint8_t pref,uint32_t seqno,uint16_t tag,uint16_t state,void (* out)(struct ag_info *))3147c478bd9Sstevel@tonic-gate ag_check(in_addr_t dst,
3157c478bd9Sstevel@tonic-gate     in_addr_t	mask,
3167c478bd9Sstevel@tonic-gate     in_addr_t	gate,
3177c478bd9Sstevel@tonic-gate     struct interface *ifp,
3187c478bd9Sstevel@tonic-gate     in_addr_t	nhop,
3197c478bd9Sstevel@tonic-gate     uint8_t	metric,
3207c478bd9Sstevel@tonic-gate     uint8_t	pref,
3217c478bd9Sstevel@tonic-gate     uint32_t	seqno,
3227c478bd9Sstevel@tonic-gate     uint16_t	tag,
3237c478bd9Sstevel@tonic-gate     uint16_t	state,
3247c478bd9Sstevel@tonic-gate     void (*out)(struct ag_info *))	/* output using this */
3257c478bd9Sstevel@tonic-gate {
3267c478bd9Sstevel@tonic-gate 	struct ag_info *ag, *nag, *ag_cors;
3277c478bd9Sstevel@tonic-gate 	in_addr_t xaddr;
3287c478bd9Sstevel@tonic-gate 	int tmp;
3297c478bd9Sstevel@tonic-gate 	struct interface *xifp;
3307c478bd9Sstevel@tonic-gate 
3317c478bd9Sstevel@tonic-gate 	dst = ntohl(dst);
3327c478bd9Sstevel@tonic-gate 
3337c478bd9Sstevel@tonic-gate 	/*
3347c478bd9Sstevel@tonic-gate 	 * Don't bother trying to aggregate routes with non-contiguous
3357c478bd9Sstevel@tonic-gate 	 * subnet masks.
3367c478bd9Sstevel@tonic-gate 	 *
3377c478bd9Sstevel@tonic-gate 	 * (X & -X) contains a single bit if and only if X is a power of 2.
3387c478bd9Sstevel@tonic-gate 	 * (X + (X & -X)) == 0 if and only if X is a power of 2.
3397c478bd9Sstevel@tonic-gate 	 */
3407c478bd9Sstevel@tonic-gate 	if ((mask & -mask) + mask != 0) {
3417c478bd9Sstevel@tonic-gate 		struct ag_info nc_ag;
3427c478bd9Sstevel@tonic-gate 
3437c478bd9Sstevel@tonic-gate 		nc_ag.ag_dst_h = dst;
3447c478bd9Sstevel@tonic-gate 		nc_ag.ag_mask = mask;
3457c478bd9Sstevel@tonic-gate 		nc_ag.ag_gate = gate;
3467c478bd9Sstevel@tonic-gate 		nc_ag.ag_ifp = ifp;
3477c478bd9Sstevel@tonic-gate 		nc_ag.ag_nhop = nhop;
3487c478bd9Sstevel@tonic-gate 		nc_ag.ag_metric = metric;
3497c478bd9Sstevel@tonic-gate 		nc_ag.ag_pref = pref;
3507c478bd9Sstevel@tonic-gate 		nc_ag.ag_tag = tag;
3517c478bd9Sstevel@tonic-gate 		nc_ag.ag_state = state;
3527c478bd9Sstevel@tonic-gate 		nc_ag.ag_seqno = seqno;
3537c478bd9Sstevel@tonic-gate 		out(&nc_ag);
3547c478bd9Sstevel@tonic-gate 		return;
3557c478bd9Sstevel@tonic-gate 	}
3567c478bd9Sstevel@tonic-gate 
3577c478bd9Sstevel@tonic-gate 	/* Search for the right slot in the aggregation table. */
3587c478bd9Sstevel@tonic-gate 	ag_cors = NULL;
3597c478bd9Sstevel@tonic-gate 	ag = ag_corsest;
3607c478bd9Sstevel@tonic-gate 	while (ag != NULL) {
3617c478bd9Sstevel@tonic-gate 		if (ag->ag_mask >= mask)
3627c478bd9Sstevel@tonic-gate 			break;
3637c478bd9Sstevel@tonic-gate 
3647c478bd9Sstevel@tonic-gate 		/*
3657c478bd9Sstevel@tonic-gate 		 * Suppress old routes (i.e. combine with compatible routes
3667c478bd9Sstevel@tonic-gate 		 * with coarser masks) as we look for the right slot in the
3677c478bd9Sstevel@tonic-gate 		 * aggregation table for the new route.
3687c478bd9Sstevel@tonic-gate 		 * A route to an address less than the current destination
3697c478bd9Sstevel@tonic-gate 		 * will not be affected by the current route or any route
3707c478bd9Sstevel@tonic-gate 		 * seen hereafter.  That means it is safe to suppress it.
3717c478bd9Sstevel@tonic-gate 		 * This check keeps poor routes (e.g. with large hop counts)
3727c478bd9Sstevel@tonic-gate 		 * from preventing suppression of finer routes.
3737c478bd9Sstevel@tonic-gate 		 */
3747c478bd9Sstevel@tonic-gate 		if (ag_cors != NULL && ag->ag_dst_h < dst &&
3757c478bd9Sstevel@tonic-gate 		    (ag->ag_state & AGS_SUPPRESS) &&
3767c478bd9Sstevel@tonic-gate 		    ag_cors->ag_pref <= ag->ag_pref &&
3777c478bd9Sstevel@tonic-gate 		    (ag->ag_dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h &&
3787c478bd9Sstevel@tonic-gate 		    ((ag_cors->ag_nhop == ag->ag_nhop &&
3797c478bd9Sstevel@tonic-gate 		    (ag_cors->ag_ifp == ag->ag_ifp))||
380f9aa3e1eSkcpoon 		    (ag->ag_state & AGS_FINE_GATE) ||
381f9aa3e1eSkcpoon 		    (ag_cors->ag_state & AGS_CORS_GATE))) {
3827c478bd9Sstevel@tonic-gate 			/*
3837c478bd9Sstevel@tonic-gate 			 * If the suppressed target was redundant,
3847c478bd9Sstevel@tonic-gate 			 * then mark the suppressor redundant.
3857c478bd9Sstevel@tonic-gate 			 */
3867c478bd9Sstevel@tonic-gate 			if (AG_IS_REDUN(ag->ag_state) &&
3877c478bd9Sstevel@tonic-gate 			    ag_cors->ag_mask == (ag->ag_mask << 1)) {
3887c478bd9Sstevel@tonic-gate 				if (ag_cors->ag_dst_h == dst)
3897c478bd9Sstevel@tonic-gate 					ag_cors->ag_state |= AGS_REDUN0;
3907c478bd9Sstevel@tonic-gate 				else
3917c478bd9Sstevel@tonic-gate 					ag_cors->ag_state |= AGS_REDUN1;
3927c478bd9Sstevel@tonic-gate 			}
3937c478bd9Sstevel@tonic-gate 			if (ag->ag_tag != ag_cors->ag_tag)
3947c478bd9Sstevel@tonic-gate 				ag_cors->ag_tag = 0;
3957c478bd9Sstevel@tonic-gate 			if (ag->ag_nhop != ag_cors->ag_nhop)
3967c478bd9Sstevel@tonic-gate 				ag_cors->ag_nhop = 0;
3977c478bd9Sstevel@tonic-gate 			ag_del(ag);
3987c478bd9Sstevel@tonic-gate 			CHECK_AG();
3997c478bd9Sstevel@tonic-gate 		} else {
4007c478bd9Sstevel@tonic-gate 			ag_cors = ag;
4017c478bd9Sstevel@tonic-gate 		}
4027c478bd9Sstevel@tonic-gate 		ag = ag_cors->ag_fine;
4037c478bd9Sstevel@tonic-gate 	}
4047c478bd9Sstevel@tonic-gate 
4057c478bd9Sstevel@tonic-gate 	/*
4067c478bd9Sstevel@tonic-gate 	 * If we find the even/odd twin of the new route, and if the
4077c478bd9Sstevel@tonic-gate 	 * masks and so forth are equal, we can aggregate them.
4087c478bd9Sstevel@tonic-gate 	 * We can probably promote one of the pair.
4097c478bd9Sstevel@tonic-gate 	 *
4107c478bd9Sstevel@tonic-gate 	 * Since the routes are encountered in lexical order,
4117c478bd9Sstevel@tonic-gate 	 * the new route must be odd.  However, the second or later
4127c478bd9Sstevel@tonic-gate 	 * times around this loop, it could be the even twin promoted
4137c478bd9Sstevel@tonic-gate 	 * from the even/odd pair of twins of the finer route.
4147c478bd9Sstevel@tonic-gate 	 */
4157c478bd9Sstevel@tonic-gate 	while (ag != NULL && ag->ag_mask == mask &&
4167c478bd9Sstevel@tonic-gate 	    ((ag->ag_dst_h ^ dst) & (mask<<1)) == 0) {
4177c478bd9Sstevel@tonic-gate 
4187c478bd9Sstevel@tonic-gate 		/*
4197c478bd9Sstevel@tonic-gate 		 * Here we know the target route and the route in the current
4207c478bd9Sstevel@tonic-gate 		 * slot have the same netmasks and differ by at most the
4217c478bd9Sstevel@tonic-gate 		 * last bit.  They are either for the same destination, or
4227c478bd9Sstevel@tonic-gate 		 * for an even/odd pair of destinations.
4237c478bd9Sstevel@tonic-gate 		 */
4247c478bd9Sstevel@tonic-gate 		if (ag->ag_dst_h == dst) {
4257c478bd9Sstevel@tonic-gate 			if (ag->ag_nhop == nhop && ag->ag_ifp == ifp) {
4267c478bd9Sstevel@tonic-gate 				/*
4277c478bd9Sstevel@tonic-gate 				 * We have two routes to the same destination,
4287c478bd9Sstevel@tonic-gate 				 * with the same nexthop and interface.
4297c478bd9Sstevel@tonic-gate 				 * Routes are encountered in lexical order,
4307c478bd9Sstevel@tonic-gate 				 * so a route is never promoted until the
4317c478bd9Sstevel@tonic-gate 				 * parent route is already present.  So we
4327c478bd9Sstevel@tonic-gate 				 * know that the new route is a promoted (or
4337c478bd9Sstevel@tonic-gate 				 * aggregated) pair and the route already in
4347c478bd9Sstevel@tonic-gate 				 * the slot is the explicit route.
4357c478bd9Sstevel@tonic-gate 				 *
4367c478bd9Sstevel@tonic-gate 				 * Prefer the best route if their metrics
4377c478bd9Sstevel@tonic-gate 				 * differ, or the aggregated one if not,
4387c478bd9Sstevel@tonic-gate 				 * following a sort of longest-match rule.
4397c478bd9Sstevel@tonic-gate 				 */
4407c478bd9Sstevel@tonic-gate 				if (pref <= ag->ag_pref) {
4417c478bd9Sstevel@tonic-gate 					ag->ag_gate = gate;
4427c478bd9Sstevel@tonic-gate 					ag->ag_ifp = ifp;
4437c478bd9Sstevel@tonic-gate 					ag->ag_nhop = nhop;
4447c478bd9Sstevel@tonic-gate 					ag->ag_tag = tag;
4457c478bd9Sstevel@tonic-gate 					ag->ag_metric = metric;
4467c478bd9Sstevel@tonic-gate 					ag->ag_pref = pref;
4477c478bd9Sstevel@tonic-gate 					if (seqno > ag->ag_seqno)
4487c478bd9Sstevel@tonic-gate 						ag->ag_seqno = seqno;
4497c478bd9Sstevel@tonic-gate 					tmp = ag->ag_state;
4507c478bd9Sstevel@tonic-gate 					ag->ag_state = state;
4517c478bd9Sstevel@tonic-gate 					state = tmp;
4527c478bd9Sstevel@tonic-gate 				}
4537c478bd9Sstevel@tonic-gate 
4547c478bd9Sstevel@tonic-gate 				/*
4557c478bd9Sstevel@tonic-gate 				 * Some bits are set if they are set on
4567c478bd9Sstevel@tonic-gate 				 * either route, except when the route is
4577c478bd9Sstevel@tonic-gate 				 * for an interface.
4587c478bd9Sstevel@tonic-gate 				 */
4597c478bd9Sstevel@tonic-gate 				if (!(ag->ag_state & AGS_IF))
4607c478bd9Sstevel@tonic-gate 					ag->ag_state |=
4617c478bd9Sstevel@tonic-gate 					    (state & (AGS_AGGREGATE_EITHER |
4627c478bd9Sstevel@tonic-gate 					    AGS_REDUN0 | AGS_REDUN1));
4637c478bd9Sstevel@tonic-gate 
4647c478bd9Sstevel@tonic-gate 				return;
4657c478bd9Sstevel@tonic-gate 			} else {
4667c478bd9Sstevel@tonic-gate 				/*
4677c478bd9Sstevel@tonic-gate 				 * multiple routes to same dest/mask with
4687c478bd9Sstevel@tonic-gate 				 * differing gate nexthop/or ifp. Flush
4697c478bd9Sstevel@tonic-gate 				 * both out.
4707c478bd9Sstevel@tonic-gate 				 */
4717c478bd9Sstevel@tonic-gate 				break;
4727c478bd9Sstevel@tonic-gate 			}
4737c478bd9Sstevel@tonic-gate 		}
4747c478bd9Sstevel@tonic-gate 
4757c478bd9Sstevel@tonic-gate 		/*
4767c478bd9Sstevel@tonic-gate 		 * If one of the routes can be promoted and the other can
4777c478bd9Sstevel@tonic-gate 		 * be suppressed, it may be possible to combine them or
4787c478bd9Sstevel@tonic-gate 		 * worthwhile to promote one.
4797c478bd9Sstevel@tonic-gate 		 *
4807c478bd9Sstevel@tonic-gate 		 * Any route that can be promoted is always
4817c478bd9Sstevel@tonic-gate 		 * marked to be eligible to be suppressed.
4827c478bd9Sstevel@tonic-gate 		 */
4837c478bd9Sstevel@tonic-gate 		if (!((state & AGS_AGGREGATE) &&
4847c478bd9Sstevel@tonic-gate 		    (ag->ag_state & AGS_SUPPRESS)) &&
4857c478bd9Sstevel@tonic-gate 		    !((ag->ag_state & AGS_AGGREGATE) && (state & AGS_SUPPRESS)))
4867c478bd9Sstevel@tonic-gate 			break;
4877c478bd9Sstevel@tonic-gate 
4887c478bd9Sstevel@tonic-gate 		/*
4897c478bd9Sstevel@tonic-gate 		 * A pair of even/odd twin routes can be combined
4907c478bd9Sstevel@tonic-gate 		 * if either is redundant, or if they are via the
4917c478bd9Sstevel@tonic-gate 		 * same gateway and have the same metric.
4927c478bd9Sstevel@tonic-gate 		 */
4937c478bd9Sstevel@tonic-gate 		if (AG_IS_REDUN(ag->ag_state) || AG_IS_REDUN(state) ||
4947c478bd9Sstevel@tonic-gate 		    (ag->ag_nhop == nhop && ag->ag_ifp == ifp &&
4957c478bd9Sstevel@tonic-gate 		    ag->ag_pref == pref &&
4967c478bd9Sstevel@tonic-gate 		    (state & ag->ag_state & AGS_AGGREGATE) != 0)) {
4977c478bd9Sstevel@tonic-gate 
4987c478bd9Sstevel@tonic-gate 			/*
4997c478bd9Sstevel@tonic-gate 			 * We have both the even and odd pairs.
5007c478bd9Sstevel@tonic-gate 			 * Since the routes are encountered in order,
5017c478bd9Sstevel@tonic-gate 			 * the route in the slot must be the even twin.
5027c478bd9Sstevel@tonic-gate 			 *
5037c478bd9Sstevel@tonic-gate 			 * Combine and promote (aggregate) the pair of routes.
5047c478bd9Sstevel@tonic-gate 			 */
5057c478bd9Sstevel@tonic-gate 			if (seqno < ag->ag_seqno)
5067c478bd9Sstevel@tonic-gate 				seqno = ag->ag_seqno;
5077c478bd9Sstevel@tonic-gate 			if (!AG_IS_REDUN(state))
5087c478bd9Sstevel@tonic-gate 				state &= ~AGS_REDUN1;
5097c478bd9Sstevel@tonic-gate 			if (AG_IS_REDUN(ag->ag_state))
5107c478bd9Sstevel@tonic-gate 				state |= AGS_REDUN0;
5117c478bd9Sstevel@tonic-gate 			else
5127c478bd9Sstevel@tonic-gate 				state &= ~AGS_REDUN0;
5137c478bd9Sstevel@tonic-gate 			state |= (ag->ag_state & AGS_AGGREGATE_EITHER);
5147c478bd9Sstevel@tonic-gate 			if (ag->ag_tag != tag)
5157c478bd9Sstevel@tonic-gate 				tag = 0;
5167c478bd9Sstevel@tonic-gate 			if (ag->ag_nhop != nhop)
5177c478bd9Sstevel@tonic-gate 				nhop = 0;
5187c478bd9Sstevel@tonic-gate 
5197c478bd9Sstevel@tonic-gate 			/*
5207c478bd9Sstevel@tonic-gate 			 * Get rid of the even twin that was already
5217c478bd9Sstevel@tonic-gate 			 * in the slot.
5227c478bd9Sstevel@tonic-gate 			 */
5237c478bd9Sstevel@tonic-gate 			ag_del(ag);
5247c478bd9Sstevel@tonic-gate 
5257c478bd9Sstevel@tonic-gate 		} else if (ag->ag_pref >= pref &&
5267c478bd9Sstevel@tonic-gate 		    (ag->ag_state & AGS_AGGREGATE)) {
5277c478bd9Sstevel@tonic-gate 			/*
5287c478bd9Sstevel@tonic-gate 			 * If we cannot combine the pair, maybe the route
5297c478bd9Sstevel@tonic-gate 			 * with the worse metric can be promoted.
5307c478bd9Sstevel@tonic-gate 			 *
5317c478bd9Sstevel@tonic-gate 			 * Promote the old, even twin, by giving its slot
5327c478bd9Sstevel@tonic-gate 			 * in the table to the new, odd twin.
5337c478bd9Sstevel@tonic-gate 			 */
5347c478bd9Sstevel@tonic-gate 			ag->ag_dst_h = dst;
5357c478bd9Sstevel@tonic-gate 
5367c478bd9Sstevel@tonic-gate 			xaddr = ag->ag_gate;
5377c478bd9Sstevel@tonic-gate 			ag->ag_gate = gate;
5387c478bd9Sstevel@tonic-gate 			gate = xaddr;
5397c478bd9Sstevel@tonic-gate 
5407c478bd9Sstevel@tonic-gate 			xifp = ag->ag_ifp;
5417c478bd9Sstevel@tonic-gate 			ag->ag_ifp = ifp;
5427c478bd9Sstevel@tonic-gate 			ifp = xifp;
5437c478bd9Sstevel@tonic-gate 
5447c478bd9Sstevel@tonic-gate 			xaddr = ag->ag_nhop;
5457c478bd9Sstevel@tonic-gate 			ag->ag_nhop = nhop;
5467c478bd9Sstevel@tonic-gate 			nhop = xaddr;
5477c478bd9Sstevel@tonic-gate 
5487c478bd9Sstevel@tonic-gate 			tmp = ag->ag_tag;
5497c478bd9Sstevel@tonic-gate 			ag->ag_tag = tag;
5507c478bd9Sstevel@tonic-gate 			tag = tmp;
5517c478bd9Sstevel@tonic-gate 
5527c478bd9Sstevel@tonic-gate 			/*
5537c478bd9Sstevel@tonic-gate 			 * The promoted route is even-redundant only if the
5547c478bd9Sstevel@tonic-gate 			 * even twin was fully redundant.  It is not
5557c478bd9Sstevel@tonic-gate 			 * odd-redundant because the odd-twin will still be
5567c478bd9Sstevel@tonic-gate 			 * in the table.
5577c478bd9Sstevel@tonic-gate 			 */
5587c478bd9Sstevel@tonic-gate 			tmp = ag->ag_state;
5597c478bd9Sstevel@tonic-gate 			if (!AG_IS_REDUN(tmp))
5607c478bd9Sstevel@tonic-gate 				tmp &= ~AGS_REDUN0;
5617c478bd9Sstevel@tonic-gate 			tmp &= ~AGS_REDUN1;
5627c478bd9Sstevel@tonic-gate 			ag->ag_state = state;
5637c478bd9Sstevel@tonic-gate 			state = tmp;
5647c478bd9Sstevel@tonic-gate 
5657c478bd9Sstevel@tonic-gate 			tmp = ag->ag_metric;
5667c478bd9Sstevel@tonic-gate 			ag->ag_metric = metric;
5677c478bd9Sstevel@tonic-gate 			metric = tmp;
5687c478bd9Sstevel@tonic-gate 
5697c478bd9Sstevel@tonic-gate 			tmp = ag->ag_pref;
5707c478bd9Sstevel@tonic-gate 			ag->ag_pref = pref;
5717c478bd9Sstevel@tonic-gate 			pref = tmp;
5727c478bd9Sstevel@tonic-gate 
5737c478bd9Sstevel@tonic-gate 			/* take the newest sequence number */
5747c478bd9Sstevel@tonic-gate 			if (seqno <= ag->ag_seqno)
5757c478bd9Sstevel@tonic-gate 				seqno = ag->ag_seqno;
5767c478bd9Sstevel@tonic-gate 			else
5777c478bd9Sstevel@tonic-gate 				ag->ag_seqno = seqno;
5787c478bd9Sstevel@tonic-gate 
5797c478bd9Sstevel@tonic-gate 		} else {
5807c478bd9Sstevel@tonic-gate 			if (!(state & AGS_AGGREGATE))
5817c478bd9Sstevel@tonic-gate 				break;	/* cannot promote either twin */
5827c478bd9Sstevel@tonic-gate 
5837c478bd9Sstevel@tonic-gate 			/*
5847c478bd9Sstevel@tonic-gate 			 * Promote the new, odd twin by shaving its
5857c478bd9Sstevel@tonic-gate 			 * mask and address.
5867c478bd9Sstevel@tonic-gate 			 * The promoted route is odd-redundant only if the
5877c478bd9Sstevel@tonic-gate 			 * odd twin was fully redundant.  It is not
5887c478bd9Sstevel@tonic-gate 			 * even-redundant because the even twin is still in
5897c478bd9Sstevel@tonic-gate 			 * the table.
5907c478bd9Sstevel@tonic-gate 			 */
5917c478bd9Sstevel@tonic-gate 			if (!AG_IS_REDUN(state))
5927c478bd9Sstevel@tonic-gate 				state &= ~AGS_REDUN1;
5937c478bd9Sstevel@tonic-gate 			state &= ~AGS_REDUN0;
5947c478bd9Sstevel@tonic-gate 			if (seqno < ag->ag_seqno)
5957c478bd9Sstevel@tonic-gate 				seqno = ag->ag_seqno;
5967c478bd9Sstevel@tonic-gate 			else
5977c478bd9Sstevel@tonic-gate 				ag->ag_seqno = seqno;
5987c478bd9Sstevel@tonic-gate 		}
5997c478bd9Sstevel@tonic-gate 
6007c478bd9Sstevel@tonic-gate 		mask <<= 1;
6017c478bd9Sstevel@tonic-gate 		dst &= mask;
6027c478bd9Sstevel@tonic-gate 
6037c478bd9Sstevel@tonic-gate 		if (ag_cors == NULL) {
6047c478bd9Sstevel@tonic-gate 			ag = ag_corsest;
6057c478bd9Sstevel@tonic-gate 			break;
6067c478bd9Sstevel@tonic-gate 		}
6077c478bd9Sstevel@tonic-gate 		ag = ag_cors;
6087c478bd9Sstevel@tonic-gate 		ag_cors = ag->ag_cors;
6097c478bd9Sstevel@tonic-gate 	}
6107c478bd9Sstevel@tonic-gate 
6117c478bd9Sstevel@tonic-gate 	/*
6127c478bd9Sstevel@tonic-gate 	 * When we can no longer promote and combine routes,
6137c478bd9Sstevel@tonic-gate 	 * flush the old route in the target slot.  Also flush
6147c478bd9Sstevel@tonic-gate 	 * any finer routes that we know will never be aggregated by
6157c478bd9Sstevel@tonic-gate 	 * the new route.
6167c478bd9Sstevel@tonic-gate 	 *
6177c478bd9Sstevel@tonic-gate 	 * In case we moved toward coarser masks,
6187c478bd9Sstevel@tonic-gate 	 * get back where we belong
6197c478bd9Sstevel@tonic-gate 	 */
6207c478bd9Sstevel@tonic-gate 	if (ag != NULL && ag->ag_mask < mask) {
6217c478bd9Sstevel@tonic-gate 		ag_cors = ag;
6227c478bd9Sstevel@tonic-gate 		ag = ag->ag_fine;
6237c478bd9Sstevel@tonic-gate 	}
6247c478bd9Sstevel@tonic-gate 
6257c478bd9Sstevel@tonic-gate 	/* Empty the target slot */
6267c478bd9Sstevel@tonic-gate 	if (ag != NULL && ag->ag_mask == mask) {
6277c478bd9Sstevel@tonic-gate 		ag_flush(ag->ag_dst_h, ag->ag_mask, out);
6287c478bd9Sstevel@tonic-gate 		ag = (ag_cors == NULL) ? ag_corsest : ag_cors->ag_fine;
6297c478bd9Sstevel@tonic-gate 	}
6307c478bd9Sstevel@tonic-gate 
6317c478bd9Sstevel@tonic-gate #ifdef DEBUG_AG
6327c478bd9Sstevel@tonic-gate 	if (ag == NULL && ag_cors != ag_finest)
6337c478bd9Sstevel@tonic-gate 		abort();
6347c478bd9Sstevel@tonic-gate 	if (ag_cors == NULL && ag != ag_corsest)
6357c478bd9Sstevel@tonic-gate 		abort();
6367c478bd9Sstevel@tonic-gate 	if (ag != NULL && ag->ag_cors != ag_cors)
6377c478bd9Sstevel@tonic-gate 		abort();
6387c478bd9Sstevel@tonic-gate 	if (ag_cors != NULL && ag_cors->ag_fine != ag)
6397c478bd9Sstevel@tonic-gate 		abort();
6407c478bd9Sstevel@tonic-gate 	CHECK_AG();
6417c478bd9Sstevel@tonic-gate #endif
6427c478bd9Sstevel@tonic-gate 
6437c478bd9Sstevel@tonic-gate 	/* Save the new route on the end of the table. */
6447c478bd9Sstevel@tonic-gate 	nag = ag_avail;
6457c478bd9Sstevel@tonic-gate 	ag_avail = nag->ag_fine;
6467c478bd9Sstevel@tonic-gate 
6477c478bd9Sstevel@tonic-gate 	nag->ag_dst_h = dst;
6487c478bd9Sstevel@tonic-gate 	nag->ag_mask = mask;
6497c478bd9Sstevel@tonic-gate 	nag->ag_ifp = ifp;
6507c478bd9Sstevel@tonic-gate 	nag->ag_gate = gate;
6517c478bd9Sstevel@tonic-gate 	nag->ag_nhop = nhop;
6527c478bd9Sstevel@tonic-gate 	nag->ag_metric = metric;
6537c478bd9Sstevel@tonic-gate 	nag->ag_pref = pref;
6547c478bd9Sstevel@tonic-gate 	nag->ag_tag = tag;
6557c478bd9Sstevel@tonic-gate 	nag->ag_state = state;
6567c478bd9Sstevel@tonic-gate 	nag->ag_seqno = seqno;
6577c478bd9Sstevel@tonic-gate 
6587c478bd9Sstevel@tonic-gate 	nag->ag_fine = ag;
6597c478bd9Sstevel@tonic-gate 	if (ag != NULL)
6607c478bd9Sstevel@tonic-gate 		ag->ag_cors = nag;
6617c478bd9Sstevel@tonic-gate 	else
6627c478bd9Sstevel@tonic-gate 		ag_finest = nag;
6637c478bd9Sstevel@tonic-gate 	nag->ag_cors = ag_cors;
6647c478bd9Sstevel@tonic-gate 	if (ag_cors == NULL)
6657c478bd9Sstevel@tonic-gate 		ag_corsest = nag;
6667c478bd9Sstevel@tonic-gate 	else
6677c478bd9Sstevel@tonic-gate 		ag_cors->ag_fine = nag;
6687c478bd9Sstevel@tonic-gate 	CHECK_AG();
6697c478bd9Sstevel@tonic-gate }
6707c478bd9Sstevel@tonic-gate 
6717c478bd9Sstevel@tonic-gate 
6727c478bd9Sstevel@tonic-gate static const char *
rtm_type_name(uchar_t type)6737c478bd9Sstevel@tonic-gate rtm_type_name(uchar_t type)
6747c478bd9Sstevel@tonic-gate {
6757c478bd9Sstevel@tonic-gate 	static const char *rtm_types[] = {
6767c478bd9Sstevel@tonic-gate 		"RTM_ADD",
6777c478bd9Sstevel@tonic-gate 		"RTM_DELETE",
6787c478bd9Sstevel@tonic-gate 		"RTM_CHANGE",
6797c478bd9Sstevel@tonic-gate 		"RTM_GET",
6807c478bd9Sstevel@tonic-gate 		"RTM_LOSING",
6817c478bd9Sstevel@tonic-gate 		"RTM_REDIRECT",
6827c478bd9Sstevel@tonic-gate 		"RTM_MISS",
6837c478bd9Sstevel@tonic-gate 		"RTM_LOCK",
6847c478bd9Sstevel@tonic-gate 		"RTM_OLDADD",
6857c478bd9Sstevel@tonic-gate 		"RTM_OLDDEL",
6867c478bd9Sstevel@tonic-gate 		"RTM_RESOLVE",
6877c478bd9Sstevel@tonic-gate 		"RTM_NEWADDR",
6887c478bd9Sstevel@tonic-gate 		"RTM_DELADDR",
6897c478bd9Sstevel@tonic-gate 		"RTM_IFINFO",
6901cb875aeSCathy Zhou 		"RTM_CHGMADDR",
6911cb875aeSCathy Zhou 		"RTM_FREEMADDR"
6927c478bd9Sstevel@tonic-gate 	};
6937c478bd9Sstevel@tonic-gate #define	NEW_RTM_PAT	"RTM type %#x"
6947c478bd9Sstevel@tonic-gate 	static char name0[sizeof (NEW_RTM_PAT) + 2];
6957c478bd9Sstevel@tonic-gate 
6967c478bd9Sstevel@tonic-gate 	if (type > sizeof (rtm_types) / sizeof (rtm_types[0]) || type == 0) {
6977c478bd9Sstevel@tonic-gate 		(void) snprintf(name0, sizeof (name0), NEW_RTM_PAT, type);
6987c478bd9Sstevel@tonic-gate 		return (name0);
6997c478bd9Sstevel@tonic-gate 	} else {
7007c478bd9Sstevel@tonic-gate 		return (rtm_types[type-1]);
7017c478bd9Sstevel@tonic-gate 	}
7027c478bd9Sstevel@tonic-gate #undef	NEW_RTM_PAT
7037c478bd9Sstevel@tonic-gate }
7047c478bd9Sstevel@tonic-gate 
7057c478bd9Sstevel@tonic-gate 
7067c478bd9Sstevel@tonic-gate static void
dump_rt_msg(const char * act,struct rt_msghdr * rtm,int mlen)7077c478bd9Sstevel@tonic-gate dump_rt_msg(const char *act, struct rt_msghdr *rtm, int mlen)
7087c478bd9Sstevel@tonic-gate {
7097c478bd9Sstevel@tonic-gate 	const char *mtype;
7107c478bd9Sstevel@tonic-gate 	uchar_t *cp;
7117c478bd9Sstevel@tonic-gate 	int i, j;
7127c478bd9Sstevel@tonic-gate 	char buffer[16*3 + 1], *ibs;
7137c478bd9Sstevel@tonic-gate 	struct ifa_msghdr *ifam;
7147c478bd9Sstevel@tonic-gate 	struct if_msghdr *ifm;
7157c478bd9Sstevel@tonic-gate 
7167c478bd9Sstevel@tonic-gate 	switch (rtm->rtm_type) {
7177c478bd9Sstevel@tonic-gate 	case RTM_NEWADDR:
7187c478bd9Sstevel@tonic-gate 	case RTM_DELADDR:
7191cb875aeSCathy Zhou 	case RTM_FREEADDR:
7201cb875aeSCathy Zhou 	case RTM_CHGADDR:
7217c478bd9Sstevel@tonic-gate 		mtype = "ifam";
7227c478bd9Sstevel@tonic-gate 		break;
7237c478bd9Sstevel@tonic-gate 	case RTM_IFINFO:
7247c478bd9Sstevel@tonic-gate 		mtype = "ifm";
7257c478bd9Sstevel@tonic-gate 		break;
7267c478bd9Sstevel@tonic-gate 	default:
7277c478bd9Sstevel@tonic-gate 		mtype = "rtm";
7287c478bd9Sstevel@tonic-gate 		break;
7297c478bd9Sstevel@tonic-gate 	}
7307c478bd9Sstevel@tonic-gate 	trace_misc("%s %s %d bytes", act, mtype, mlen);
7317c478bd9Sstevel@tonic-gate 	if (mlen > rtm->rtm_msglen) {
7327c478bd9Sstevel@tonic-gate 		trace_misc("%s: extra %d bytes ignored", mtype,
7337c478bd9Sstevel@tonic-gate 		    mlen - rtm->rtm_msglen);
7347c478bd9Sstevel@tonic-gate 		mlen = rtm->rtm_msglen;
7357c478bd9Sstevel@tonic-gate 	} else if (mlen < rtm->rtm_msglen) {
7367c478bd9Sstevel@tonic-gate 		trace_misc("%s: truncated by %d bytes", mtype,
7377c478bd9Sstevel@tonic-gate 		    rtm->rtm_msglen - mlen);
7387c478bd9Sstevel@tonic-gate 	}
7397c478bd9Sstevel@tonic-gate 	switch (rtm->rtm_type) {
7407c478bd9Sstevel@tonic-gate 	case RTM_NEWADDR:
7417c478bd9Sstevel@tonic-gate 	case RTM_DELADDR:
7421cb875aeSCathy Zhou 	case RTM_CHGADDR:
7431cb875aeSCathy Zhou 	case RTM_FREEADDR:
7447c478bd9Sstevel@tonic-gate 		ifam = (struct ifa_msghdr *)rtm;
7457c478bd9Sstevel@tonic-gate 		trace_misc("ifam: msglen %d version %d type %d addrs %X",
7467c478bd9Sstevel@tonic-gate 		    ifam->ifam_msglen, ifam->ifam_version, ifam->ifam_type,
7477c478bd9Sstevel@tonic-gate 		    ifam->ifam_addrs);
7487c478bd9Sstevel@tonic-gate 		trace_misc("ifam: flags %X index %d metric %d",
7497c478bd9Sstevel@tonic-gate 		    ifam->ifam_flags, ifam->ifam_index, ifam->ifam_metric);
7507c478bd9Sstevel@tonic-gate 		cp = (uchar_t *)(ifam + 1);
7517c478bd9Sstevel@tonic-gate 		break;
7527c478bd9Sstevel@tonic-gate 	case RTM_IFINFO:
7537c478bd9Sstevel@tonic-gate 		ifm = (struct if_msghdr *)rtm;
7547c478bd9Sstevel@tonic-gate 		trace_misc("ifm: msglen %d version %d type %d addrs %X",
7557c478bd9Sstevel@tonic-gate 		    ifm->ifm_msglen, ifm->ifm_version, ifm->ifm_type,
7567c478bd9Sstevel@tonic-gate 		    ifm->ifm_addrs);
7577c478bd9Sstevel@tonic-gate 		ibs = if_bit_string(ifm->ifm_flags, _B_TRUE);
7587c478bd9Sstevel@tonic-gate 		if (ibs == NULL) {
7597c478bd9Sstevel@tonic-gate 			trace_misc("ifm: flags %#x index %d", ifm->ifm_flags,
7607c478bd9Sstevel@tonic-gate 			    ifm->ifm_index);
7617c478bd9Sstevel@tonic-gate 		} else {
7627c478bd9Sstevel@tonic-gate 			trace_misc("ifm: flags %s index %d", ibs,
7637c478bd9Sstevel@tonic-gate 			    ifm->ifm_index);
7647c478bd9Sstevel@tonic-gate 			free(ibs);
7657c478bd9Sstevel@tonic-gate 		}
7667c478bd9Sstevel@tonic-gate 		cp = (uchar_t *)(ifm + 1);
7677c478bd9Sstevel@tonic-gate 		break;
7687c478bd9Sstevel@tonic-gate 	default:
7697c478bd9Sstevel@tonic-gate 		trace_misc("rtm: msglen %d version %d type %d index %d",
7707c478bd9Sstevel@tonic-gate 		    rtm->rtm_msglen, rtm->rtm_version, rtm->rtm_type,
7717c478bd9Sstevel@tonic-gate 		    rtm->rtm_index);
7727c478bd9Sstevel@tonic-gate 		trace_misc("rtm: flags %X addrs %X pid %d seq %d",
7737c478bd9Sstevel@tonic-gate 		    rtm->rtm_flags, rtm->rtm_addrs, rtm->rtm_pid, rtm->rtm_seq);
7747c478bd9Sstevel@tonic-gate 		trace_misc("rtm: errno %d use %d inits %X", rtm->rtm_errno,
7757c478bd9Sstevel@tonic-gate 		    rtm->rtm_use, rtm->rtm_inits);
7767c478bd9Sstevel@tonic-gate 		cp = (uchar_t *)(rtm + 1);
7777c478bd9Sstevel@tonic-gate 		break;
7787c478bd9Sstevel@tonic-gate 	}
7797c478bd9Sstevel@tonic-gate 	i = mlen - (cp - (uint8_t *)rtm);
7807c478bd9Sstevel@tonic-gate 	while (i > 0) {
7817c478bd9Sstevel@tonic-gate 		buffer[0] = '\0';
7827c478bd9Sstevel@tonic-gate 		ibs = buffer;
7837c478bd9Sstevel@tonic-gate 		for (j = 0; j < 16 && i > 0; j++, i--)
7847c478bd9Sstevel@tonic-gate 			ibs += sprintf(ibs, " %02X", *cp++);
7857c478bd9Sstevel@tonic-gate 		trace_misc("addr%s", buffer);
7867c478bd9Sstevel@tonic-gate 	}
7877c478bd9Sstevel@tonic-gate }
7887c478bd9Sstevel@tonic-gate 
7897c478bd9Sstevel@tonic-gate /*
7907c478bd9Sstevel@tonic-gate  * Tell the kernel to add, delete or change a route
7917c478bd9Sstevel@tonic-gate  * Pass k_state from khash in for diagnostic info.
7927c478bd9Sstevel@tonic-gate  */
7937c478bd9Sstevel@tonic-gate static void
rtioctl(int action,in_addr_t dst,in_addr_t gate,in_addr_t mask,struct interface * ifp,uint8_t metric,int flags)7947c478bd9Sstevel@tonic-gate rtioctl(int action,			/* RTM_DELETE, etc */
7957c478bd9Sstevel@tonic-gate     in_addr_t dst,
7967c478bd9Sstevel@tonic-gate     in_addr_t gate,
7977c478bd9Sstevel@tonic-gate     in_addr_t mask,
7987c478bd9Sstevel@tonic-gate     struct interface *ifp,
7997c478bd9Sstevel@tonic-gate     uint8_t metric,
8007c478bd9Sstevel@tonic-gate     int flags)
8017c478bd9Sstevel@tonic-gate {
8027c478bd9Sstevel@tonic-gate 	static int rt_sock_seqno = 0;
8037c478bd9Sstevel@tonic-gate 	struct {
8047c478bd9Sstevel@tonic-gate 		struct rt_msghdr w_rtm;
8057c478bd9Sstevel@tonic-gate 		struct sockaddr_in w_dst;
8067c478bd9Sstevel@tonic-gate 		struct sockaddr_in w_gate;
8077c478bd9Sstevel@tonic-gate 		uint8_t w_space[512];
8087c478bd9Sstevel@tonic-gate 	} w;
8097c478bd9Sstevel@tonic-gate 	struct sockaddr_in w_mask;
8107c478bd9Sstevel@tonic-gate 	struct sockaddr_dl w_ifp;
8117c478bd9Sstevel@tonic-gate 	uint8_t *cp;
8127c478bd9Sstevel@tonic-gate 	long cc;
8137c478bd9Sstevel@tonic-gate #define	PAT " %-10s %s metric=%d flags=%#x"
8147c478bd9Sstevel@tonic-gate #define	ARGS rtm_type_name(action), rtname(dst, mask, gate), metric, flags
8157c478bd9Sstevel@tonic-gate 
8167c478bd9Sstevel@tonic-gate again:
8177c478bd9Sstevel@tonic-gate 	(void) memset(&w, 0, sizeof (w));
8187c478bd9Sstevel@tonic-gate 	(void) memset(&w_mask, 0, sizeof (w_mask));
8197c478bd9Sstevel@tonic-gate 	(void) memset(&w_ifp, 0, sizeof (w_ifp));
8207c478bd9Sstevel@tonic-gate 	cp = w.w_space;
8217c478bd9Sstevel@tonic-gate 	w.w_rtm.rtm_msglen = sizeof (struct rt_msghdr) +
8227c478bd9Sstevel@tonic-gate 	    2 * ROUNDUP_LONG(sizeof (struct sockaddr_in));
8237c478bd9Sstevel@tonic-gate 	w.w_rtm.rtm_version = RTM_VERSION;
8247c478bd9Sstevel@tonic-gate 	w.w_rtm.rtm_type = action;
8257c478bd9Sstevel@tonic-gate 	w.w_rtm.rtm_flags = flags;
8267c478bd9Sstevel@tonic-gate 	w.w_rtm.rtm_seq = ++rt_sock_seqno;
8277c478bd9Sstevel@tonic-gate 	w.w_rtm.rtm_addrs = RTA_DST|RTA_GATEWAY;
8287c478bd9Sstevel@tonic-gate 	if (metric != 0 || action == RTM_CHANGE) {
8297c478bd9Sstevel@tonic-gate 		w.w_rtm.rtm_rmx.rmx_hopcount = metric;
8307c478bd9Sstevel@tonic-gate 		w.w_rtm.rtm_inits |= RTV_HOPCOUNT;
8317c478bd9Sstevel@tonic-gate 	}
8327c478bd9Sstevel@tonic-gate 	w.w_dst.sin_family = AF_INET;
8337c478bd9Sstevel@tonic-gate 	w.w_dst.sin_addr.s_addr = dst;
8347c478bd9Sstevel@tonic-gate 	w.w_gate.sin_family = AF_INET;
8357c478bd9Sstevel@tonic-gate 	w.w_gate.sin_addr.s_addr = gate;
8367c478bd9Sstevel@tonic-gate 	if (mask == HOST_MASK) {
8377c478bd9Sstevel@tonic-gate 		w.w_rtm.rtm_flags |= RTF_HOST;
8387c478bd9Sstevel@tonic-gate 	} else {
8397c478bd9Sstevel@tonic-gate 		w.w_rtm.rtm_addrs |= RTA_NETMASK;
8407c478bd9Sstevel@tonic-gate 		w_mask.sin_family = AF_INET;
8417c478bd9Sstevel@tonic-gate 		w_mask.sin_addr.s_addr = htonl(mask);
8427c478bd9Sstevel@tonic-gate 		(void) memmove(cp, &w_mask, sizeof (w_mask));
8437c478bd9Sstevel@tonic-gate 		cp += ROUNDUP_LONG(sizeof (struct sockaddr_in));
8447c478bd9Sstevel@tonic-gate 		w.w_rtm.rtm_msglen += ROUNDUP_LONG(sizeof (struct sockaddr_in));
8457c478bd9Sstevel@tonic-gate 	}
8467c478bd9Sstevel@tonic-gate 	if (ifp == NULL)
8477c478bd9Sstevel@tonic-gate 		ifp = iflookup(gate);
8487c478bd9Sstevel@tonic-gate 
849982ec2c2SRishi Srivatsavai 	if (ifp == NULL || (ifp->int_phys == NULL)) {
8507c478bd9Sstevel@tonic-gate 		trace_misc("no ifp for" PAT, ARGS);
8517c478bd9Sstevel@tonic-gate 	} else {
8527c478bd9Sstevel@tonic-gate 		if (ifp->int_phys->phyi_index > UINT16_MAX) {
8537c478bd9Sstevel@tonic-gate 			trace_misc("ifindex %d is too big for sdl_index",
8547c478bd9Sstevel@tonic-gate 			    ifp->int_phys->phyi_index);
8557c478bd9Sstevel@tonic-gate 		} else {
8567c478bd9Sstevel@tonic-gate 			w_ifp.sdl_family = AF_LINK;
8577c478bd9Sstevel@tonic-gate 			w.w_rtm.rtm_addrs |= RTA_IFP;
8587c478bd9Sstevel@tonic-gate 			w_ifp.sdl_index = ifp->int_phys->phyi_index;
8597c478bd9Sstevel@tonic-gate 			(void) memmove(cp, &w_ifp, sizeof (w_ifp));
8607c478bd9Sstevel@tonic-gate 			w.w_rtm.rtm_msglen +=
8617c478bd9Sstevel@tonic-gate 			    ROUNDUP_LONG(sizeof (struct sockaddr_dl));
8627c478bd9Sstevel@tonic-gate 		}
8637c478bd9Sstevel@tonic-gate 	}
8647c478bd9Sstevel@tonic-gate 
8657c478bd9Sstevel@tonic-gate 
8667c478bd9Sstevel@tonic-gate 	if (!no_install) {
8677c478bd9Sstevel@tonic-gate 		if (TRACERTS)
8687c478bd9Sstevel@tonic-gate 			dump_rt_msg("write", &w.w_rtm, w.w_rtm.rtm_msglen);
8697c478bd9Sstevel@tonic-gate 		cc = write(rt_sock, &w, w.w_rtm.rtm_msglen);
8707c478bd9Sstevel@tonic-gate 		if (cc < 0) {
8717c478bd9Sstevel@tonic-gate 			if (errno == ESRCH && (action == RTM_CHANGE ||
8727c478bd9Sstevel@tonic-gate 			    action == RTM_DELETE)) {
8737c478bd9Sstevel@tonic-gate 				trace_act("route disappeared before" PAT, ARGS);
8747c478bd9Sstevel@tonic-gate 				if (action == RTM_CHANGE) {
8757c478bd9Sstevel@tonic-gate 					action = RTM_ADD;
8767c478bd9Sstevel@tonic-gate 					goto again;
8777c478bd9Sstevel@tonic-gate 				}
8787c478bd9Sstevel@tonic-gate 				return;
8797c478bd9Sstevel@tonic-gate 			}
8807c478bd9Sstevel@tonic-gate 			writelog(LOG_WARNING, "write(rt_sock)" PAT ": %s ",
8817c478bd9Sstevel@tonic-gate 			    ARGS, rip_strerror(errno));
8827c478bd9Sstevel@tonic-gate 			return;
8837c478bd9Sstevel@tonic-gate 		} else if (cc != w.w_rtm.rtm_msglen) {
8847c478bd9Sstevel@tonic-gate 			msglog("write(rt_sock) wrote %ld instead of %d for" PAT,
8857c478bd9Sstevel@tonic-gate 			    cc, w.w_rtm.rtm_msglen, ARGS);
8867c478bd9Sstevel@tonic-gate 			return;
8877c478bd9Sstevel@tonic-gate 		}
8887c478bd9Sstevel@tonic-gate 	}
8897c478bd9Sstevel@tonic-gate 	if (TRACEKERNEL)
8907c478bd9Sstevel@tonic-gate 		trace_misc("write kernel" PAT, ARGS);
8917c478bd9Sstevel@tonic-gate #undef PAT
8927c478bd9Sstevel@tonic-gate #undef ARGS
8937c478bd9Sstevel@tonic-gate }
8947c478bd9Sstevel@tonic-gate 
8957c478bd9Sstevel@tonic-gate 
8967c478bd9Sstevel@tonic-gate /* Hash table containing our image of the kernel forwarding table. */
8977c478bd9Sstevel@tonic-gate #define	KHASH_SIZE 71			/* should be prime */
8987c478bd9Sstevel@tonic-gate #define	KHASH(a, m) khash_bins[((a) ^ (m)) % KHASH_SIZE]
8997c478bd9Sstevel@tonic-gate static struct khash *khash_bins[KHASH_SIZE];
9007c478bd9Sstevel@tonic-gate 
9017c478bd9Sstevel@tonic-gate #define	K_KEEP_LIM	30	/* k_keep */
9027c478bd9Sstevel@tonic-gate 
9037c478bd9Sstevel@tonic-gate static struct khash *
kern_find(in_addr_t dst,in_addr_t mask,in_addr_t gate,struct interface * ifp,struct khash *** ppk)9047c478bd9Sstevel@tonic-gate kern_find(in_addr_t dst, in_addr_t mask, in_addr_t gate,
9057c478bd9Sstevel@tonic-gate     struct interface *ifp, struct khash ***ppk)
9067c478bd9Sstevel@tonic-gate {
9077c478bd9Sstevel@tonic-gate 	struct khash *k, **pk;
9087c478bd9Sstevel@tonic-gate 
9097c478bd9Sstevel@tonic-gate 	for (pk = &KHASH(dst, mask); (k = *pk) != NULL; pk = &k->k_next) {
9107c478bd9Sstevel@tonic-gate 		if (k->k_dst == dst && k->k_mask == mask &&
9117c478bd9Sstevel@tonic-gate 		    (gate == 0 || k->k_gate == gate) &&
9127c478bd9Sstevel@tonic-gate 		    (ifp == NULL || k->k_ifp == ifp)) {
9137c478bd9Sstevel@tonic-gate 			break;
9147c478bd9Sstevel@tonic-gate 		}
9157c478bd9Sstevel@tonic-gate 	}
9167c478bd9Sstevel@tonic-gate 	if (ppk != NULL)
9177c478bd9Sstevel@tonic-gate 		*ppk = pk;
9187c478bd9Sstevel@tonic-gate 	return (k);
9197c478bd9Sstevel@tonic-gate }
9207c478bd9Sstevel@tonic-gate 
9217c478bd9Sstevel@tonic-gate 
9227c478bd9Sstevel@tonic-gate /*
9237c478bd9Sstevel@tonic-gate  * Find out if there is an alternate route to a given destination
9247c478bd9Sstevel@tonic-gate  * off of a given interface.
9257c478bd9Sstevel@tonic-gate  */
9267c478bd9Sstevel@tonic-gate static struct khash *
kern_alternate(in_addr_t dst,in_addr_t mask,in_addr_t gate,struct interface * ifp,struct khash *** ppk)9277c478bd9Sstevel@tonic-gate kern_alternate(in_addr_t dst, in_addr_t mask, in_addr_t gate,
9287c478bd9Sstevel@tonic-gate     struct interface *ifp, struct khash ***ppk)
9297c478bd9Sstevel@tonic-gate {
9307c478bd9Sstevel@tonic-gate 	struct khash *k, **pk;
9317c478bd9Sstevel@tonic-gate 
9327c478bd9Sstevel@tonic-gate 	for (pk = &KHASH(dst, mask); (k = *pk) != NULL; pk = &k->k_next) {
9337c478bd9Sstevel@tonic-gate 		if (k->k_dst == dst && k->k_mask == mask &&
9347c478bd9Sstevel@tonic-gate 		    (k->k_gate != gate) &&
9357c478bd9Sstevel@tonic-gate 		    (k->k_ifp == ifp)) {
9367c478bd9Sstevel@tonic-gate 			break;
9377c478bd9Sstevel@tonic-gate 		}
9387c478bd9Sstevel@tonic-gate 	}
9397c478bd9Sstevel@tonic-gate 	if (ppk != NULL)
9407c478bd9Sstevel@tonic-gate 		*ppk = pk;
9417c478bd9Sstevel@tonic-gate 	return (k);
9427c478bd9Sstevel@tonic-gate }
9437c478bd9Sstevel@tonic-gate 
9447c478bd9Sstevel@tonic-gate static struct khash *
kern_add(in_addr_t dst,uint32_t mask,in_addr_t gate,struct interface * ifp)9457c478bd9Sstevel@tonic-gate kern_add(in_addr_t dst, uint32_t mask, in_addr_t gate, struct interface *ifp)
9467c478bd9Sstevel@tonic-gate {
9477c478bd9Sstevel@tonic-gate 	struct khash *k, **pk;
9487c478bd9Sstevel@tonic-gate 
9497c478bd9Sstevel@tonic-gate 	k = kern_find(dst, mask, gate, ifp, &pk);
9507c478bd9Sstevel@tonic-gate 	if (k != NULL)
9517c478bd9Sstevel@tonic-gate 		return (k);
9527c478bd9Sstevel@tonic-gate 
9537c478bd9Sstevel@tonic-gate 	k = rtmalloc(sizeof (*k), "kern_add");
9547c478bd9Sstevel@tonic-gate 
9557c478bd9Sstevel@tonic-gate 	(void) memset(k, 0, sizeof (*k));
9567c478bd9Sstevel@tonic-gate 	k->k_dst = dst;
9577c478bd9Sstevel@tonic-gate 	k->k_mask = mask;
9587c478bd9Sstevel@tonic-gate 	k->k_state = KS_NEW;
9597c478bd9Sstevel@tonic-gate 	k->k_keep = now.tv_sec;
9607c478bd9Sstevel@tonic-gate 	k->k_gate = gate;
9617c478bd9Sstevel@tonic-gate 	k->k_ifp = ifp;
9627c478bd9Sstevel@tonic-gate 	*pk = k;
9637c478bd9Sstevel@tonic-gate 
9647c478bd9Sstevel@tonic-gate 	return (k);
9657c478bd9Sstevel@tonic-gate }
9667c478bd9Sstevel@tonic-gate 
9677c478bd9Sstevel@tonic-gate /* delete all khash entries that are wired through the interface ifp */
9687c478bd9Sstevel@tonic-gate void
kern_flush_ifp(struct interface * ifp)9697c478bd9Sstevel@tonic-gate kern_flush_ifp(struct interface *ifp)
9707c478bd9Sstevel@tonic-gate {
9717c478bd9Sstevel@tonic-gate 	struct khash *k, *kprev, *knext;
9727c478bd9Sstevel@tonic-gate 	int i;
9737c478bd9Sstevel@tonic-gate 
9747c478bd9Sstevel@tonic-gate 	for (i = 0; i < KHASH_SIZE; i++) {
9757c478bd9Sstevel@tonic-gate 		kprev = NULL;
9767c478bd9Sstevel@tonic-gate 		for (k = khash_bins[i]; k != NULL; k = knext) {
9777c478bd9Sstevel@tonic-gate 			knext = k->k_next;
9787c478bd9Sstevel@tonic-gate 			if (k->k_ifp == ifp) {
9797c478bd9Sstevel@tonic-gate 				if (kprev != NULL)
9807c478bd9Sstevel@tonic-gate 					kprev->k_next = k->k_next;
9817c478bd9Sstevel@tonic-gate 				else
9827c478bd9Sstevel@tonic-gate 					khash_bins[i] = k->k_next;
9837c478bd9Sstevel@tonic-gate 				free(k);
9847c478bd9Sstevel@tonic-gate 				continue;
9857c478bd9Sstevel@tonic-gate 			}
9867c478bd9Sstevel@tonic-gate 			kprev = k;
9877c478bd9Sstevel@tonic-gate 		}
9887c478bd9Sstevel@tonic-gate 	}
9897c478bd9Sstevel@tonic-gate }
9907c478bd9Sstevel@tonic-gate 
9917c478bd9Sstevel@tonic-gate /*
9927c478bd9Sstevel@tonic-gate  * rewire khash entries that currently go through oldifp to
9937c478bd9Sstevel@tonic-gate  * go through newifp.
9947c478bd9Sstevel@tonic-gate  */
9957c478bd9Sstevel@tonic-gate void
kern_rewire_ifp(struct interface * oldifp,struct interface * newifp)9967c478bd9Sstevel@tonic-gate kern_rewire_ifp(struct interface *oldifp, struct interface *newifp)
9977c478bd9Sstevel@tonic-gate {
9987c478bd9Sstevel@tonic-gate 	struct khash *k;
9997c478bd9Sstevel@tonic-gate 	int i;
10007c478bd9Sstevel@tonic-gate 
10017c478bd9Sstevel@tonic-gate 	for (i = 0; i < KHASH_SIZE; i++) {
10027c478bd9Sstevel@tonic-gate 		for (k = khash_bins[i]; k; k = k->k_next) {
10037c478bd9Sstevel@tonic-gate 			if (k->k_ifp == oldifp) {
10047c478bd9Sstevel@tonic-gate 				k->k_ifp = newifp;
10057c478bd9Sstevel@tonic-gate 				trace_misc("kern_rewire_ifp k 0x%lx "
10067c478bd9Sstevel@tonic-gate 				    "from %s to %s", k, oldifp->int_name,
10077c478bd9Sstevel@tonic-gate 				    newifp->int_name);
10087c478bd9Sstevel@tonic-gate 			}
10097c478bd9Sstevel@tonic-gate 		}
10107c478bd9Sstevel@tonic-gate 	}
10117c478bd9Sstevel@tonic-gate }
10127c478bd9Sstevel@tonic-gate 
10137c478bd9Sstevel@tonic-gate /*
10147c478bd9Sstevel@tonic-gate  * Check that a static route it is still in the daemon table, and not
10157c478bd9Sstevel@tonic-gate  * deleted by interfaces coming and going.  This is also the routine
10167c478bd9Sstevel@tonic-gate  * responsible for adding new static routes to the daemon table.
10177c478bd9Sstevel@tonic-gate  */
10187c478bd9Sstevel@tonic-gate static void
kern_check_static(struct khash * k,struct interface * ifp)10197c478bd9Sstevel@tonic-gate kern_check_static(struct khash *k, struct interface *ifp)
10207c478bd9Sstevel@tonic-gate {
10217c478bd9Sstevel@tonic-gate 	struct rt_entry *rt;
10227c478bd9Sstevel@tonic-gate 	struct rt_spare new;
10237c478bd9Sstevel@tonic-gate 	uint16_t rt_state = RS_STATIC;
10247c478bd9Sstevel@tonic-gate 
10257c478bd9Sstevel@tonic-gate 	(void) memset(&new, 0, sizeof (new));
10267c478bd9Sstevel@tonic-gate 	new.rts_ifp = ifp;
10277c478bd9Sstevel@tonic-gate 	new.rts_gate = k->k_gate;
10287c478bd9Sstevel@tonic-gate 	new.rts_router = (ifp != NULL) ? ifp->int_addr : loopaddr;
10297c478bd9Sstevel@tonic-gate 	new.rts_metric = k->k_metric;
10307c478bd9Sstevel@tonic-gate 	new.rts_time = now.tv_sec;
10317c478bd9Sstevel@tonic-gate 	new.rts_origin = RO_STATIC;
10327c478bd9Sstevel@tonic-gate 
10337c478bd9Sstevel@tonic-gate 	rt = rtget(k->k_dst, k->k_mask);
10347c478bd9Sstevel@tonic-gate 	if ((ifp != NULL && !IS_IFF_ROUTING(ifp->int_if_flags)) ||
10357c478bd9Sstevel@tonic-gate 	    (k->k_state & KS_PRIVATE))
10367c478bd9Sstevel@tonic-gate 		rt_state |= RS_NOPROPAGATE;
10377c478bd9Sstevel@tonic-gate 
10387c478bd9Sstevel@tonic-gate 	if (rt != NULL) {
10397c478bd9Sstevel@tonic-gate 		if ((rt->rt_state & RS_STATIC) == 0) {
10407c478bd9Sstevel@tonic-gate 			/*
10417c478bd9Sstevel@tonic-gate 			 * We are already tracking this dest/mask
10427c478bd9Sstevel@tonic-gate 			 * via RIP/RDISC. Ignore the static route,
10437c478bd9Sstevel@tonic-gate 			 * because we don't currently have a good
10447c478bd9Sstevel@tonic-gate 			 * way to compare metrics on static routes
10457c478bd9Sstevel@tonic-gate 			 * with rip metrics, and therefore cannot
10467c478bd9Sstevel@tonic-gate 			 * mix and match the two.
10477c478bd9Sstevel@tonic-gate 			 */
10487c478bd9Sstevel@tonic-gate 			return;
10497c478bd9Sstevel@tonic-gate 		}
10507c478bd9Sstevel@tonic-gate 		rt_state |= rt->rt_state;
10517c478bd9Sstevel@tonic-gate 		if (rt->rt_state != rt_state)
10527c478bd9Sstevel@tonic-gate 			rtchange(rt, rt_state, &new, 0);
10537c478bd9Sstevel@tonic-gate 	} else {
10547c478bd9Sstevel@tonic-gate 		rtadd(k->k_dst, k->k_mask, rt_state, &new);
10557c478bd9Sstevel@tonic-gate 	}
10567c478bd9Sstevel@tonic-gate }
10577c478bd9Sstevel@tonic-gate 
10587c478bd9Sstevel@tonic-gate 
10597c478bd9Sstevel@tonic-gate /* operate on a kernel entry */
10607c478bd9Sstevel@tonic-gate static void
kern_ioctl(struct khash * k,int action,int flags)10617c478bd9Sstevel@tonic-gate kern_ioctl(struct khash *k,
10627c478bd9Sstevel@tonic-gate     int action,			/* RTM_DELETE, etc */
10637c478bd9Sstevel@tonic-gate     int flags)
10647c478bd9Sstevel@tonic-gate {
10657c478bd9Sstevel@tonic-gate 	if (((k->k_state & (KS_IF|KS_PASSIVE)) == KS_IF) ||
10667c478bd9Sstevel@tonic-gate 	    (k->k_state & KS_DEPRE_IF)) {
10677c478bd9Sstevel@tonic-gate 		/*
10687c478bd9Sstevel@tonic-gate 		 * Prevent execution of RTM_DELETE, RTM_ADD or
10697c478bd9Sstevel@tonic-gate 		 * RTM_CHANGE of interface routes
10707c478bd9Sstevel@tonic-gate 		 */
10717c478bd9Sstevel@tonic-gate 		trace_act("Blocking execution of %s  %s --> %s ",
10727c478bd9Sstevel@tonic-gate 		    rtm_type_name(action),
10737c478bd9Sstevel@tonic-gate 		    addrname(k->k_dst, k->k_mask, 0), naddr_ntoa(k->k_gate));
10747c478bd9Sstevel@tonic-gate 		return;
10757c478bd9Sstevel@tonic-gate 	}
10767c478bd9Sstevel@tonic-gate 
10777c478bd9Sstevel@tonic-gate 	switch (action) {
10787c478bd9Sstevel@tonic-gate 	case RTM_DELETE:
10797c478bd9Sstevel@tonic-gate 		k->k_state &= ~KS_DYNAMIC;
10807c478bd9Sstevel@tonic-gate 		if (k->k_state & KS_DELETED)
10817c478bd9Sstevel@tonic-gate 			return;
10827c478bd9Sstevel@tonic-gate 		k->k_state |= KS_DELETED;
10837c478bd9Sstevel@tonic-gate 		break;
10847c478bd9Sstevel@tonic-gate 	case RTM_ADD:
10857c478bd9Sstevel@tonic-gate 		k->k_state &= ~KS_DELETED;
10867c478bd9Sstevel@tonic-gate 		break;
10877c478bd9Sstevel@tonic-gate 	case RTM_CHANGE:
10887c478bd9Sstevel@tonic-gate 		if (k->k_state & KS_DELETED) {
10897c478bd9Sstevel@tonic-gate 			action = RTM_ADD;
10907c478bd9Sstevel@tonic-gate 			k->k_state &= ~KS_DELETED;
10917c478bd9Sstevel@tonic-gate 		}
10927c478bd9Sstevel@tonic-gate 		break;
10937c478bd9Sstevel@tonic-gate 	}
10947c478bd9Sstevel@tonic-gate 
1095d52135a8SSowmini Varadhan 	/*
1096d52135a8SSowmini Varadhan 	 * We should be doing an RTM_CHANGE for a KS_CHANGE, but
1097d52135a8SSowmini Varadhan 	 * RTM_CHANGE in the kernel is not currently multipath-aware and
1098d52135a8SSowmini Varadhan 	 * assumes that RTF_GATEWAY implies that the gateway of the route for
1099d52135a8SSowmini Varadhan 	 * dst has to be changed. Moreover, the only change that in.routed
1100d52135a8SSowmini Varadhan 	 * wants to implement is a change in the ks_metric (rmx_hopcount)
1101d52135a8SSowmini Varadhan 	 * which the kernel ignores anway, so we skip the RTM_CHANGE operation
1102d52135a8SSowmini Varadhan 	 * on the kernel
1103d52135a8SSowmini Varadhan 	 */
1104d52135a8SSowmini Varadhan 	if (action != RTM_CHANGE) {
1105d52135a8SSowmini Varadhan 		rtioctl(action, k->k_dst, k->k_gate, k->k_mask, k->k_ifp,
1106d52135a8SSowmini Varadhan 		    k->k_metric, flags);
1107d52135a8SSowmini Varadhan 	}
11087c478bd9Sstevel@tonic-gate }
11097c478bd9Sstevel@tonic-gate 
11107c478bd9Sstevel@tonic-gate 
11117c478bd9Sstevel@tonic-gate /* add a route the kernel told us */
11127c478bd9Sstevel@tonic-gate static void
rtm_add(struct rt_msghdr * rtm,struct rt_addrinfo * info,time_t keep,boolean_t interf_route,struct interface * ifptr)11137c478bd9Sstevel@tonic-gate rtm_add(struct rt_msghdr *rtm,
11147c478bd9Sstevel@tonic-gate     struct rt_addrinfo *info,
11157c478bd9Sstevel@tonic-gate     time_t keep,
11167c478bd9Sstevel@tonic-gate     boolean_t interf_route,
11177c478bd9Sstevel@tonic-gate     struct interface *ifptr)
11187c478bd9Sstevel@tonic-gate {
11197c478bd9Sstevel@tonic-gate 	struct khash *k;
11207c478bd9Sstevel@tonic-gate 	struct interface *ifp = ifptr;
11217c478bd9Sstevel@tonic-gate 	in_addr_t mask, gate = 0;
11227c478bd9Sstevel@tonic-gate 	static struct msg_limit msg_no_ifp;
11237c478bd9Sstevel@tonic-gate 
11247c478bd9Sstevel@tonic-gate 	if (rtm->rtm_flags & RTF_HOST) {
11257c478bd9Sstevel@tonic-gate 		mask = HOST_MASK;
11267c478bd9Sstevel@tonic-gate 	} else if (INFO_MASK(info) != 0) {
11277c478bd9Sstevel@tonic-gate 		mask = ntohl(S_ADDR(INFO_MASK(info)));
11287c478bd9Sstevel@tonic-gate 	} else {
11297c478bd9Sstevel@tonic-gate 		writelog(LOG_WARNING,
11307c478bd9Sstevel@tonic-gate 		    "ignore %s without mask", rtm_type_name(rtm->rtm_type));
11317c478bd9Sstevel@tonic-gate 		return;
11327c478bd9Sstevel@tonic-gate 	}
11337c478bd9Sstevel@tonic-gate 
11347c478bd9Sstevel@tonic-gate 	/*
11357c478bd9Sstevel@tonic-gate 	 * Find the interface toward the gateway.
11367c478bd9Sstevel@tonic-gate 	 */
11377c478bd9Sstevel@tonic-gate 	if (INFO_GATE(info) != NULL)
11387c478bd9Sstevel@tonic-gate 		gate = S_ADDR(INFO_GATE(info));
11397c478bd9Sstevel@tonic-gate 
11407c478bd9Sstevel@tonic-gate 	if (ifp == NULL) {
11417c478bd9Sstevel@tonic-gate 		if (INFO_GATE(info) != NULL)
11427c478bd9Sstevel@tonic-gate 			ifp = iflookup(gate);
1143e1fa7f4dSsowmini 		if (ifp == NULL) {
11447c478bd9Sstevel@tonic-gate 			msglim(&msg_no_ifp, gate,
11457c478bd9Sstevel@tonic-gate 			    "route %s --> %s nexthop is not directly connected",
11467c478bd9Sstevel@tonic-gate 			    addrname(S_ADDR(INFO_DST(info)), mask, 0),
11477c478bd9Sstevel@tonic-gate 			    naddr_ntoa(gate));
1148e1fa7f4dSsowmini 		}
11497c478bd9Sstevel@tonic-gate 	}
11507c478bd9Sstevel@tonic-gate 
11517c478bd9Sstevel@tonic-gate 	k = kern_add(S_ADDR(INFO_DST(info)), mask, gate, ifp);
11527c478bd9Sstevel@tonic-gate 
11537c478bd9Sstevel@tonic-gate 	if (k->k_state & KS_NEW)
11547c478bd9Sstevel@tonic-gate 		k->k_keep = now.tv_sec+keep;
11557c478bd9Sstevel@tonic-gate 	if (INFO_GATE(info) == 0) {
11567c478bd9Sstevel@tonic-gate 		trace_act("note %s without gateway",
11577c478bd9Sstevel@tonic-gate 		    rtm_type_name(rtm->rtm_type));
11587c478bd9Sstevel@tonic-gate 		k->k_metric = HOPCNT_INFINITY;
11597c478bd9Sstevel@tonic-gate 	} else if (INFO_GATE(info)->ss_family != AF_INET) {
11607c478bd9Sstevel@tonic-gate 		trace_act("note %s with gateway AF=%d",
1161