Home | History | Annotate | Line # | Download | only in net
route.c revision 1.157
      1 /*	$NetBSD: route.c,v 1.157 2016/04/01 09:52:39 ozaki-r Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 1998, 2008 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by Kevin M. Lahey of the Numerical Aerospace Simulation Facility,
      9  * NASA Ames Research Center.
     10  *
     11  * Redistribution and use in source and binary forms, with or without
     12  * modification, are permitted provided that the following conditions
     13  * are met:
     14  * 1. Redistributions of source code must retain the above copyright
     15  *    notice, this list of conditions and the following disclaimer.
     16  * 2. Redistributions in binary form must reproduce the above copyright
     17  *    notice, this list of conditions and the following disclaimer in the
     18  *    documentation and/or other materials provided with the distribution.
     19  *
     20  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     23  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     24  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     30  * POSSIBILITY OF SUCH DAMAGE.
     31  */
     32 
     33 /*
     34  * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
     35  * All rights reserved.
     36  *
     37  * Redistribution and use in source and binary forms, with or without
     38  * modification, are permitted provided that the following conditions
     39  * are met:
     40  * 1. Redistributions of source code must retain the above copyright
     41  *    notice, this list of conditions and the following disclaimer.
     42  * 2. Redistributions in binary form must reproduce the above copyright
     43  *    notice, this list of conditions and the following disclaimer in the
     44  *    documentation and/or other materials provided with the distribution.
     45  * 3. Neither the name of the project nor the names of its contributors
     46  *    may be used to endorse or promote products derived from this software
     47  *    without specific prior written permission.
     48  *
     49  * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
     50  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     51  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     52  * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
     53  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     54  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     55  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     56  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     57  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     58  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     59  * SUCH DAMAGE.
     60  */
     61 
     62 /*
     63  * Copyright (c) 1980, 1986, 1991, 1993
     64  *	The Regents of the University of California.  All rights reserved.
     65  *
     66  * Redistribution and use in source and binary forms, with or without
     67  * modification, are permitted provided that the following conditions
     68  * are met:
     69  * 1. Redistributions of source code must retain the above copyright
     70  *    notice, this list of conditions and the following disclaimer.
     71  * 2. Redistributions in binary form must reproduce the above copyright
     72  *    notice, this list of conditions and the following disclaimer in the
     73  *    documentation and/or other materials provided with the distribution.
     74  * 3. Neither the name of the University nor the names of its contributors
     75  *    may be used to endorse or promote products derived from this software
     76  *    without specific prior written permission.
     77  *
     78  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     79  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     80  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     81  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     82  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     83  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     84  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     85  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     86  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     87  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     88  * SUCH DAMAGE.
     89  *
     90  *	@(#)route.c	8.3 (Berkeley) 1/9/95
     91  */
     92 
     93 #ifdef _KERNEL_OPT
     94 #include "opt_inet.h"
     95 #include "opt_route.h"
     96 #endif
     97 
     98 #include <sys/cdefs.h>
     99 __KERNEL_RCSID(0, "$NetBSD: route.c,v 1.157 2016/04/01 09:52:39 ozaki-r Exp $");
    100 
    101 #include <sys/param.h>
    102 #ifdef RTFLUSH_DEBUG
    103 #include <sys/sysctl.h>
    104 #endif
    105 #include <sys/systm.h>
    106 #include <sys/callout.h>
    107 #include <sys/proc.h>
    108 #include <sys/mbuf.h>
    109 #include <sys/socket.h>
    110 #include <sys/socketvar.h>
    111 #include <sys/domain.h>
    112 #include <sys/protosw.h>
    113 #include <sys/kernel.h>
    114 #include <sys/ioctl.h>
    115 #include <sys/pool.h>
    116 #include <sys/kauth.h>
    117 
    118 #include <net/if.h>
    119 #include <net/if_dl.h>
    120 #include <net/route.h>
    121 
    122 #include <netinet/in.h>
    123 #include <netinet/in_var.h>
    124 
    125 #ifdef RTFLUSH_DEBUG
    126 #define	rtcache_debug() __predict_false(_rtcache_debug)
    127 #else /* RTFLUSH_DEBUG */
    128 #define	rtcache_debug() 0
    129 #endif /* RTFLUSH_DEBUG */
    130 
    131 struct rtstat		rtstat;
    132 
    133 static int		rttrash;	/* routes not in table but not freed */
    134 
    135 static struct pool	rtentry_pool;
    136 static struct pool	rttimer_pool;
    137 
    138 static struct callout	rt_timer_ch; /* callout for rt_timer_timer() */
    139 
    140 #ifdef RTFLUSH_DEBUG
    141 static int _rtcache_debug = 0;
    142 #endif /* RTFLUSH_DEBUG */
    143 
    144 static kauth_listener_t route_listener;
    145 
    146 static int rtdeletemsg(struct rtentry *);
    147 static int rtflushclone1(struct rtentry *, void *);
    148 static void rtflushclone(sa_family_t family, struct rtentry *);
    149 static void rtflushall(int);
    150 
    151 static void rt_maskedcopy(const struct sockaddr *,
    152     struct sockaddr *, const struct sockaddr *);
    153 
    154 static void rtcache_clear(struct route *);
    155 static void rtcache_invalidate(struct dom_rtlist *);
    156 
    157 #ifdef RTFLUSH_DEBUG
    158 static void sysctl_net_rtcache_setup(struct sysctllog **);
    159 static void
    160 sysctl_net_rtcache_setup(struct sysctllog **clog)
    161 {
    162 	const struct sysctlnode *rnode;
    163 
    164 	if (sysctl_createv(clog, 0, NULL, &rnode, CTLFLAG_PERMANENT,
    165 	    CTLTYPE_NODE,
    166 	    "rtcache", SYSCTL_DESCR("Route cache related settings"),
    167 	    NULL, 0, NULL, 0, CTL_NET, CTL_CREATE, CTL_EOL) != 0)
    168 		return;
    169 	if (sysctl_createv(clog, 0, &rnode, &rnode,
    170 	    CTLFLAG_PERMANENT|CTLFLAG_READWRITE, CTLTYPE_INT,
    171 	    "debug", SYSCTL_DESCR("Debug route caches"),
    172 	    NULL, 0, &_rtcache_debug, 0, CTL_CREATE, CTL_EOL) != 0)
    173 		return;
    174 }
    175 #endif /* RTFLUSH_DEBUG */
    176 
    177 static inline void
    178 rt_destroy(struct rtentry *rt)
    179 {
    180 	if (rt->_rt_key != NULL)
    181 		sockaddr_free(rt->_rt_key);
    182 	if (rt->rt_gateway != NULL)
    183 		sockaddr_free(rt->rt_gateway);
    184 	if (rt_gettag(rt) != NULL)
    185 		sockaddr_free(rt_gettag(rt));
    186 	rt->_rt_key = rt->rt_gateway = rt->rt_tag = NULL;
    187 }
    188 
    189 static inline const struct sockaddr *
    190 rt_setkey(struct rtentry *rt, const struct sockaddr *key, int flags)
    191 {
    192 	if (rt->_rt_key == key)
    193 		goto out;
    194 
    195 	if (rt->_rt_key != NULL)
    196 		sockaddr_free(rt->_rt_key);
    197 	rt->_rt_key = sockaddr_dup(key, flags);
    198 out:
    199 	rt->rt_nodes->rn_key = (const char *)rt->_rt_key;
    200 	return rt->_rt_key;
    201 }
    202 
    203 struct ifaddr *
    204 rt_get_ifa(struct rtentry *rt)
    205 {
    206 	struct ifaddr *ifa;
    207 
    208 	if ((ifa = rt->rt_ifa) == NULL)
    209 		return ifa;
    210 	else if (ifa->ifa_getifa == NULL)
    211 		return ifa;
    212 #if 0
    213 	else if (ifa->ifa_seqno != NULL && *ifa->ifa_seqno == rt->rt_ifa_seqno)
    214 		return ifa;
    215 #endif
    216 	else {
    217 		ifa = (*ifa->ifa_getifa)(ifa, rt_getkey(rt));
    218 		if (ifa == NULL)
    219 			return NULL;
    220 		rt_replace_ifa(rt, ifa);
    221 		return ifa;
    222 	}
    223 }
    224 
    225 static void
    226 rt_set_ifa1(struct rtentry *rt, struct ifaddr *ifa)
    227 {
    228 	rt->rt_ifa = ifa;
    229 	if (ifa->ifa_seqno != NULL)
    230 		rt->rt_ifa_seqno = *ifa->ifa_seqno;
    231 }
    232 
    233 /*
    234  * Is this route the connected route for the ifa?
    235  */
    236 static int
    237 rt_ifa_connected(const struct rtentry *rt, const struct ifaddr *ifa)
    238 {
    239 	const struct sockaddr *key, *dst, *odst;
    240 	struct sockaddr_storage maskeddst;
    241 
    242 	key = rt_getkey(rt);
    243 	dst = rt->rt_flags & RTF_HOST ? ifa->ifa_dstaddr : ifa->ifa_addr;
    244 	if (dst == NULL ||
    245 	    dst->sa_family != key->sa_family ||
    246 	    dst->sa_len != key->sa_len)
    247 		return 0;
    248 	if ((rt->rt_flags & RTF_HOST) == 0 && ifa->ifa_netmask) {
    249 		odst = dst;
    250 		dst = (struct sockaddr *)&maskeddst;
    251 		rt_maskedcopy(odst, (struct sockaddr *)&maskeddst,
    252 		    ifa->ifa_netmask);
    253 	}
    254 	return (memcmp(dst, key, dst->sa_len) == 0);
    255 }
    256 
    257 void
    258 rt_replace_ifa(struct rtentry *rt, struct ifaddr *ifa)
    259 {
    260 	if (rt->rt_ifa &&
    261 	    rt->rt_ifa != ifa &&
    262 	    rt->rt_ifa->ifa_flags & IFA_ROUTE &&
    263 	    rt_ifa_connected(rt, rt->rt_ifa))
    264 	{
    265 		RT_DPRINTF("rt->_rt_key = %p, ifa = %p, "
    266 		    "replace deleted IFA_ROUTE\n",
    267 		    (void *)rt->_rt_key, (void *)rt->rt_ifa);
    268 		rt->rt_ifa->ifa_flags &= ~IFA_ROUTE;
    269 		if (rt_ifa_connected(rt, ifa)) {
    270 			RT_DPRINTF("rt->_rt_key = %p, ifa = %p, "
    271 			    "replace added IFA_ROUTE\n",
    272 			    (void *)rt->_rt_key, (void *)ifa);
    273 			ifa->ifa_flags |= IFA_ROUTE;
    274 		}
    275 	}
    276 
    277 	ifaref(ifa);
    278 	ifafree(rt->rt_ifa);
    279 	rt_set_ifa1(rt, ifa);
    280 }
    281 
    282 static void
    283 rt_set_ifa(struct rtentry *rt, struct ifaddr *ifa)
    284 {
    285 	ifaref(ifa);
    286 	rt_set_ifa1(rt, ifa);
    287 }
    288 
    289 static int
    290 route_listener_cb(kauth_cred_t cred, kauth_action_t action, void *cookie,
    291     void *arg0, void *arg1, void *arg2, void *arg3)
    292 {
    293 	struct rt_msghdr *rtm;
    294 	int result;
    295 
    296 	result = KAUTH_RESULT_DEFER;
    297 	rtm = arg1;
    298 
    299 	if (action != KAUTH_NETWORK_ROUTE)
    300 		return result;
    301 
    302 	if (rtm->rtm_type == RTM_GET)
    303 		result = KAUTH_RESULT_ALLOW;
    304 
    305 	return result;
    306 }
    307 
    308 void
    309 rt_init(void)
    310 {
    311 
    312 #ifdef RTFLUSH_DEBUG
    313 	sysctl_net_rtcache_setup(NULL);
    314 #endif
    315 
    316 	pool_init(&rtentry_pool, sizeof(struct rtentry), 0, 0, 0, "rtentpl",
    317 	    NULL, IPL_SOFTNET);
    318 	pool_init(&rttimer_pool, sizeof(struct rttimer), 0, 0, 0, "rttmrpl",
    319 	    NULL, IPL_SOFTNET);
    320 
    321 	rn_init();	/* initialize all zeroes, all ones, mask table */
    322 	rtbl_init();
    323 
    324 	route_listener = kauth_listen_scope(KAUTH_SCOPE_NETWORK,
    325 	    route_listener_cb, NULL);
    326 }
    327 
    328 static void
    329 rtflushall(int family)
    330 {
    331 	struct domain *dom;
    332 
    333 	if (rtcache_debug())
    334 		printf("%s: enter\n", __func__);
    335 
    336 	if ((dom = pffinddomain(family)) == NULL)
    337 		return;
    338 
    339 	rtcache_invalidate(&dom->dom_rtcache);
    340 }
    341 
    342 static void
    343 rtcache(struct route *ro)
    344 {
    345 	struct domain *dom;
    346 
    347 	rtcache_invariants(ro);
    348 	KASSERT(ro->_ro_rt != NULL);
    349 	KASSERT(ro->ro_invalid == false);
    350 	KASSERT(rtcache_getdst(ro) != NULL);
    351 
    352 	if ((dom = pffinddomain(rtcache_getdst(ro)->sa_family)) == NULL)
    353 		return;
    354 
    355 	LIST_INSERT_HEAD(&dom->dom_rtcache, ro, ro_rtcache_next);
    356 	rtcache_invariants(ro);
    357 }
    358 
    359 /*
    360  * Packet routing routines. If success, refcnt of a returned rtentry
    361  * will be incremented. The caller has to rtfree it by itself.
    362  */
    363 struct rtentry *
    364 rtalloc1(const struct sockaddr *dst, int report)
    365 {
    366 	rtbl_t *rtbl = rt_gettable(dst->sa_family);
    367 	struct rtentry *rt;
    368 	struct rtentry *newrt = NULL;
    369 	struct rt_addrinfo info;
    370 	int  s = splsoftnet(), err = 0, msgtype = RTM_MISS;
    371 
    372 	if (rtbl != NULL && (rt = rt_matchaddr(rtbl, dst)) != NULL) {
    373 		newrt = rt;
    374 		if (report && (rt->rt_flags & RTF_CLONING)) {
    375 			err = rtrequest(RTM_RESOLVE, dst, NULL, NULL, 0,
    376 			    &newrt);
    377 			if (err) {
    378 				newrt = rt;
    379 				rt->rt_refcnt++;
    380 				goto miss;
    381 			}
    382 			KASSERT(newrt != NULL);
    383 			rt = newrt;
    384 			if (rt->rt_flags & RTF_XRESOLVE) {
    385 				msgtype = RTM_RESOLVE;
    386 				goto miss;
    387 			}
    388 			/* Inform listeners of the new route */
    389 			memset(&info, 0, sizeof(info));
    390 			info.rti_info[RTAX_DST] = rt_getkey(rt);
    391 			info.rti_info[RTAX_NETMASK] = rt_mask(rt);
    392 			info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
    393 			if (rt->rt_ifp != NULL) {
    394 				info.rti_info[RTAX_IFP] =
    395 				    rt->rt_ifp->if_dl->ifa_addr;
    396 				info.rti_info[RTAX_IFA] = rt->rt_ifa->ifa_addr;
    397 			}
    398 			rt_missmsg(RTM_ADD, &info, rt->rt_flags, 0);
    399 		} else
    400 			rt->rt_refcnt++;
    401 	} else {
    402 		rtstat.rts_unreach++;
    403 	miss:	if (report) {
    404 			memset((void *)&info, 0, sizeof(info));
    405 			info.rti_info[RTAX_DST] = dst;
    406 			rt_missmsg(msgtype, &info, 0, err);
    407 		}
    408 	}
    409 	splx(s);
    410 	return newrt;
    411 }
    412 
    413 #ifdef DEBUG
    414 /*
    415  * Check the following constraint for each rtcache:
    416  *   if a rtcache holds a rtentry, the rtentry's refcnt is more than zero,
    417  *   i.e., the rtentry should be referenced at least by the rtcache.
    418  */
    419 static void
    420 rtcache_check_rtrefcnt(int family)
    421 {
    422 	struct domain *dom = pffinddomain(family);
    423 	struct route *ro;
    424 
    425 	if (dom == NULL)
    426 		return;
    427 
    428 	LIST_FOREACH(ro, &dom->dom_rtcache, ro_rtcache_next)
    429 		KDASSERT(ro->_ro_rt == NULL || ro->_ro_rt->rt_refcnt > 0);
    430 }
    431 #endif
    432 
    433 void
    434 rtfree(struct rtentry *rt)
    435 {
    436 	struct ifaddr *ifa;
    437 
    438 	KASSERT(rt != NULL);
    439 	KASSERT(rt->rt_refcnt > 0);
    440 
    441 	rt->rt_refcnt--;
    442 #ifdef DEBUG
    443 	if (rt_getkey(rt) != NULL)
    444 		rtcache_check_rtrefcnt(rt_getkey(rt)->sa_family);
    445 #endif
    446 	if (rt->rt_refcnt == 0 && (rt->rt_flags & RTF_UP) == 0) {
    447 		rt_assert_inactive(rt);
    448 		rttrash--;
    449 		rt_timer_remove_all(rt, 0);
    450 		ifa = rt->rt_ifa;
    451 		rt->rt_ifa = NULL;
    452 		ifafree(ifa);
    453 		rt->rt_ifp = NULL;
    454 		rt_destroy(rt);
    455 		pool_put(&rtentry_pool, rt);
    456 	}
    457 }
    458 
    459 /*
    460  * Force a routing table entry to the specified
    461  * destination to go through the given gateway.
    462  * Normally called as a result of a routing redirect
    463  * message from the network layer.
    464  *
    465  * N.B.: must be called at splsoftnet
    466  */
    467 void
    468 rtredirect(const struct sockaddr *dst, const struct sockaddr *gateway,
    469 	const struct sockaddr *netmask, int flags, const struct sockaddr *src,
    470 	struct rtentry **rtp)
    471 {
    472 	struct rtentry *rt;
    473 	int error = 0;
    474 	uint64_t *stat = NULL;
    475 	struct rt_addrinfo info;
    476 	struct ifaddr *ifa;
    477 
    478 	/* verify the gateway is directly reachable */
    479 	if ((ifa = ifa_ifwithnet(gateway)) == NULL) {
    480 		error = ENETUNREACH;
    481 		goto out;
    482 	}
    483 	rt = rtalloc1(dst, 0);
    484 	/*
    485 	 * If the redirect isn't from our current router for this dst,
    486 	 * it's either old or wrong.  If it redirects us to ourselves,
    487 	 * we have a routing loop, perhaps as a result of an interface
    488 	 * going down recently.
    489 	 */
    490 	if (!(flags & RTF_DONE) && rt &&
    491 	     (sockaddr_cmp(src, rt->rt_gateway) != 0 || rt->rt_ifa != ifa))
    492 		error = EINVAL;
    493 	else if (ifa_ifwithaddr(gateway))
    494 		error = EHOSTUNREACH;
    495 	if (error)
    496 		goto done;
    497 	/*
    498 	 * Create a new entry if we just got back a wildcard entry
    499 	 * or the lookup failed.  This is necessary for hosts
    500 	 * which use routing redirects generated by smart gateways
    501 	 * to dynamically build the routing tables.
    502 	 */
    503 	if (rt == NULL || (rt_mask(rt) && rt_mask(rt)->sa_len < 2))
    504 		goto create;
    505 	/*
    506 	 * Don't listen to the redirect if it's
    507 	 * for a route to an interface.
    508 	 */
    509 	if (rt->rt_flags & RTF_GATEWAY) {
    510 		if (((rt->rt_flags & RTF_HOST) == 0) && (flags & RTF_HOST)) {
    511 			/*
    512 			 * Changing from route to net => route to host.
    513 			 * Create new route, rather than smashing route to net.
    514 			 */
    515 		create:
    516 			if (rt != NULL)
    517 				rtfree(rt);
    518 			flags |=  RTF_GATEWAY | RTF_DYNAMIC;
    519 			memset(&info, 0, sizeof(info));
    520 			info.rti_info[RTAX_DST] = dst;
    521 			info.rti_info[RTAX_GATEWAY] = gateway;
    522 			info.rti_info[RTAX_NETMASK] = netmask;
    523 			info.rti_ifa = ifa;
    524 			info.rti_flags = flags;
    525 			rt = NULL;
    526 			error = rtrequest1(RTM_ADD, &info, &rt);
    527 			if (rt != NULL)
    528 				flags = rt->rt_flags;
    529 			stat = &rtstat.rts_dynamic;
    530 		} else {
    531 			/*
    532 			 * Smash the current notion of the gateway to
    533 			 * this destination.  Should check about netmask!!!
    534 			 */
    535 			rt->rt_flags |= RTF_MODIFIED;
    536 			flags |= RTF_MODIFIED;
    537 			stat = &rtstat.rts_newgateway;
    538 			rt_setgate(rt, gateway);
    539 		}
    540 	} else
    541 		error = EHOSTUNREACH;
    542 done:
    543 	if (rt) {
    544 		if (rtp != NULL && !error)
    545 			*rtp = rt;
    546 		else
    547 			rtfree(rt);
    548 	}
    549 out:
    550 	if (error)
    551 		rtstat.rts_badredirect++;
    552 	else if (stat != NULL)
    553 		(*stat)++;
    554 	memset(&info, 0, sizeof(info));
    555 	info.rti_info[RTAX_DST] = dst;
    556 	info.rti_info[RTAX_GATEWAY] = gateway;
    557 	info.rti_info[RTAX_NETMASK] = netmask;
    558 	info.rti_info[RTAX_AUTHOR] = src;
    559 	rt_missmsg(RTM_REDIRECT, &info, flags, error);
    560 }
    561 
    562 /*
    563  * Delete a route and generate a message.
    564  * It doesn't free a passed rt.
    565  */
    566 static int
    567 rtdeletemsg(struct rtentry *rt)
    568 {
    569 	int error;
    570 	struct rt_addrinfo info;
    571 
    572 	/*
    573 	 * Request the new route so that the entry is not actually
    574 	 * deleted.  That will allow the information being reported to
    575 	 * be accurate (and consistent with route_output()).
    576 	 */
    577 	memset(&info, 0, sizeof(info));
    578 	info.rti_info[RTAX_DST] = rt_getkey(rt);
    579 	info.rti_info[RTAX_NETMASK] = rt_mask(rt);
    580 	info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
    581 	info.rti_flags = rt->rt_flags;
    582 	error = rtrequest1(RTM_DELETE, &info, NULL);
    583 
    584 	rt_missmsg(RTM_DELETE, &info, info.rti_flags, error);
    585 
    586 	return error;
    587 }
    588 
    589 static int
    590 rtflushclone1(struct rtentry *rt, void *arg)
    591 {
    592 	struct rtentry *parent;
    593 
    594 	parent = (struct rtentry *)arg;
    595 	if ((rt->rt_flags & RTF_CLONED) != 0 && rt->rt_parent == parent)
    596 		rtdeletemsg(rt);
    597 	return 0;
    598 }
    599 
    600 static void
    601 rtflushclone(sa_family_t family, struct rtentry *parent)
    602 {
    603 
    604 #ifdef DIAGNOSTIC
    605 	if (!parent || (parent->rt_flags & RTF_CLONING) == 0)
    606 		panic("rtflushclone: called with a non-cloning route");
    607 #endif
    608 	rt_walktree(family, rtflushclone1, (void *)parent);
    609 }
    610 
    611 struct ifaddr *
    612 ifa_ifwithroute(int flags, const struct sockaddr *dst,
    613 	const struct sockaddr *gateway)
    614 {
    615 	struct ifaddr *ifa;
    616 	if ((flags & RTF_GATEWAY) == 0) {
    617 		/*
    618 		 * If we are adding a route to an interface,
    619 		 * and the interface is a pt to pt link
    620 		 * we should search for the destination
    621 		 * as our clue to the interface.  Otherwise
    622 		 * we can use the local address.
    623 		 */
    624 		ifa = NULL;
    625 		if ((flags & RTF_HOST) && gateway->sa_family != AF_LINK)
    626 			ifa = ifa_ifwithdstaddr(dst);
    627 		if (ifa == NULL)
    628 			ifa = ifa_ifwithaddr(gateway);
    629 	} else {
    630 		/*
    631 		 * If we are adding a route to a remote net
    632 		 * or host, the gateway may still be on the
    633 		 * other end of a pt to pt link.
    634 		 */
    635 		ifa = ifa_ifwithdstaddr(gateway);
    636 	}
    637 	if (ifa == NULL)
    638 		ifa = ifa_ifwithnet(gateway);
    639 	if (ifa == NULL) {
    640 		struct rtentry *rt = rtalloc1(dst, 0);
    641 		if (rt == NULL)
    642 			return NULL;
    643 		ifa = rt->rt_ifa;
    644 		rtfree(rt);
    645 		if (ifa == NULL)
    646 			return NULL;
    647 	}
    648 	if (ifa->ifa_addr->sa_family != dst->sa_family) {
    649 		struct ifaddr *oifa = ifa;
    650 		ifa = ifaof_ifpforaddr(dst, ifa->ifa_ifp);
    651 		if (ifa == NULL)
    652 			ifa = oifa;
    653 	}
    654 	return ifa;
    655 }
    656 
    657 /*
    658  * If it suceeds and ret_nrt isn't NULL, refcnt of ret_nrt is incremented.
    659  * The caller has to rtfree it by itself.
    660  */
    661 int
    662 rtrequest(int req, const struct sockaddr *dst, const struct sockaddr *gateway,
    663 	const struct sockaddr *netmask, int flags, struct rtentry **ret_nrt)
    664 {
    665 	struct rt_addrinfo info;
    666 
    667 	memset(&info, 0, sizeof(info));
    668 	info.rti_flags = flags;
    669 	info.rti_info[RTAX_DST] = dst;
    670 	info.rti_info[RTAX_GATEWAY] = gateway;
    671 	info.rti_info[RTAX_NETMASK] = netmask;
    672 	return rtrequest1(req, &info, ret_nrt);
    673 }
    674 
    675 /*
    676  * It's a utility function to add/remove a route to/from the routing table
    677  * and tell user processes the addition/removal on success.
    678  */
    679 int
    680 rtrequest_newmsg(const int req, const struct sockaddr *dst,
    681 	const struct sockaddr *gateway, const struct sockaddr *netmask,
    682 	const int flags)
    683 {
    684 	int error;
    685 	struct rtentry *ret_nrt = NULL;
    686 
    687 	KASSERT(req == RTM_ADD || req == RTM_DELETE);
    688 
    689 	error = rtrequest(req, dst, gateway, netmask, flags, &ret_nrt);
    690 	if (error != 0)
    691 		return error;
    692 
    693 	KASSERT(ret_nrt != NULL);
    694 
    695 	rt_newmsg(req, ret_nrt); /* tell user process */
    696 	rtfree(ret_nrt);
    697 
    698 	return 0;
    699 }
    700 
    701 int
    702 rt_getifa(struct rt_addrinfo *info)
    703 {
    704 	struct ifaddr *ifa;
    705 	const struct sockaddr *dst = info->rti_info[RTAX_DST];
    706 	const struct sockaddr *gateway = info->rti_info[RTAX_GATEWAY];
    707 	const struct sockaddr *ifaaddr = info->rti_info[RTAX_IFA];
    708 	const struct sockaddr *ifpaddr = info->rti_info[RTAX_IFP];
    709 	int flags = info->rti_flags;
    710 
    711 	/*
    712 	 * ifp may be specified by sockaddr_dl when protocol address
    713 	 * is ambiguous
    714 	 */
    715 	if (info->rti_ifp == NULL && ifpaddr != NULL
    716 	    && ifpaddr->sa_family == AF_LINK &&
    717 	    (ifa = ifa_ifwithnet(ifpaddr)) != NULL)
    718 		info->rti_ifp = ifa->ifa_ifp;
    719 	if (info->rti_ifa == NULL && ifaaddr != NULL)
    720 		info->rti_ifa = ifa_ifwithaddr(ifaaddr);
    721 	if (info->rti_ifa == NULL) {
    722 		const struct sockaddr *sa;
    723 
    724 		sa = ifaaddr != NULL ? ifaaddr :
    725 		    (gateway != NULL ? gateway : dst);
    726 		if (sa != NULL && info->rti_ifp != NULL)
    727 			info->rti_ifa = ifaof_ifpforaddr(sa, info->rti_ifp);
    728 		else if (dst != NULL && gateway != NULL)
    729 			info->rti_ifa = ifa_ifwithroute(flags, dst, gateway);
    730 		else if (sa != NULL)
    731 			info->rti_ifa = ifa_ifwithroute(flags, sa, sa);
    732 	}
    733 	if ((ifa = info->rti_ifa) == NULL)
    734 		return ENETUNREACH;
    735 	if (ifa->ifa_getifa != NULL) {
    736 		info->rti_ifa = ifa = (*ifa->ifa_getifa)(ifa, dst);
    737 		if (ifa == NULL)
    738 			return ENETUNREACH;
    739 	}
    740 	if (info->rti_ifp == NULL)
    741 		info->rti_ifp = ifa->ifa_ifp;
    742 	return 0;
    743 }
    744 
    745 /*
    746  * If it suceeds and ret_nrt isn't NULL, refcnt of ret_nrt is incremented.
    747  * The caller has to rtfree it by itself.
    748  */
    749 int
    750 rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt)
    751 {
    752 	int s = splsoftnet();
    753 	int error = 0, rc;
    754 	struct rtentry *rt, *crt;
    755 	rtbl_t *rtbl;
    756 	struct ifaddr *ifa, *ifa2;
    757 	struct sockaddr_storage maskeddst;
    758 	const struct sockaddr *dst = info->rti_info[RTAX_DST];
    759 	const struct sockaddr *gateway = info->rti_info[RTAX_GATEWAY];
    760 	const struct sockaddr *netmask = info->rti_info[RTAX_NETMASK];
    761 	int flags = info->rti_flags;
    762 #define senderr(x) { error = x ; goto bad; }
    763 
    764 	if ((rtbl = rt_gettable(dst->sa_family)) == NULL)
    765 		senderr(ESRCH);
    766 	if (flags & RTF_HOST)
    767 		netmask = NULL;
    768 	switch (req) {
    769 	case RTM_DELETE:
    770 		if (netmask) {
    771 			rt_maskedcopy(dst, (struct sockaddr *)&maskeddst,
    772 			    netmask);
    773 			dst = (struct sockaddr *)&maskeddst;
    774 		}
    775 		if ((rt = rt_lookup(rtbl, dst, netmask)) == NULL)
    776 			senderr(ESRCH);
    777 		if ((rt->rt_flags & RTF_CLONING) != 0) {
    778 			/* clean up any cloned children */
    779 			rtflushclone(dst->sa_family, rt);
    780 		}
    781 		if ((rt = rt_deladdr(rtbl, dst, netmask)) == NULL)
    782 			senderr(ESRCH);
    783 		if (rt->rt_gwroute) {
    784 			rtfree(rt->rt_gwroute);
    785 			rt->rt_gwroute = NULL;
    786 		}
    787 		if (rt->rt_parent) {
    788 			rt->rt_parent->rt_refcnt--;
    789 			rt->rt_parent = NULL;
    790 		}
    791 		rt->rt_flags &= ~RTF_UP;
    792 		if ((ifa = rt->rt_ifa)) {
    793 			if (ifa->ifa_flags & IFA_ROUTE &&
    794 			    rt_ifa_connected(rt, ifa)) {
    795 				RT_DPRINTF("rt->_rt_key = %p, ifa = %p, "
    796 				    "deleted IFA_ROUTE\n",
    797 				    (void *)rt->_rt_key, (void *)ifa);
    798 				ifa->ifa_flags &= ~IFA_ROUTE;
    799 			}
    800 			if (ifa->ifa_rtrequest)
    801 				ifa->ifa_rtrequest(RTM_DELETE, rt, info);
    802 		}
    803 		rttrash++;
    804 		if (ret_nrt) {
    805 			*ret_nrt = rt;
    806 			rt->rt_refcnt++;
    807 		} else if (rt->rt_refcnt <= 0) {
    808 			/* Adjust the refcount */
    809 			rt->rt_refcnt++;
    810 			rtfree(rt);
    811 		}
    812 		break;
    813 
    814 	case RTM_RESOLVE:
    815 		if (ret_nrt == NULL || (rt = *ret_nrt) == NULL)
    816 			senderr(EINVAL);
    817 		if ((rt->rt_flags & RTF_CLONING) == 0)
    818 			senderr(EINVAL);
    819 		ifa = rt->rt_ifa;
    820 		flags = rt->rt_flags & ~(RTF_CLONING | RTF_STATIC);
    821 		flags |= RTF_CLONED;
    822 		gateway = rt->rt_gateway;
    823 		flags |= RTF_HOST;
    824 		goto makeroute;
    825 
    826 	case RTM_ADD:
    827 		if (info->rti_ifa == NULL && (error = rt_getifa(info)))
    828 			senderr(error);
    829 		ifa = info->rti_ifa;
    830 	makeroute:
    831 		/* Already at splsoftnet() so pool_get/pool_put are safe */
    832 		rt = pool_get(&rtentry_pool, PR_NOWAIT);
    833 		if (rt == NULL)
    834 			senderr(ENOBUFS);
    835 		memset(rt, 0, sizeof(*rt));
    836 		rt->rt_flags = RTF_UP | flags;
    837 		LIST_INIT(&rt->rt_timer);
    838 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    839 		if (rt_setkey(rt, dst, M_NOWAIT) == NULL ||
    840 		    rt_setgate(rt, gateway) != 0) {
    841 			pool_put(&rtentry_pool, rt);
    842 			senderr(ENOBUFS);
    843 		}
    844 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    845 		if (netmask) {
    846 			rt_maskedcopy(dst, (struct sockaddr *)&maskeddst,
    847 			    netmask);
    848 			rt_setkey(rt, (struct sockaddr *)&maskeddst, M_NOWAIT);
    849 			RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    850 		} else {
    851 			rt_setkey(rt, dst, M_NOWAIT);
    852 			RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    853 		}
    854 		rt_set_ifa(rt, ifa);
    855 		if (info->rti_info[RTAX_TAG] != NULL)
    856 			rt_settag(rt, info->rti_info[RTAX_TAG]);
    857 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    858 		if (info->rti_info[RTAX_IFP] != NULL &&
    859 		    (ifa2 = ifa_ifwithnet(info->rti_info[RTAX_IFP])) != NULL &&
    860 		    ifa2->ifa_ifp != NULL)
    861 			rt->rt_ifp = ifa2->ifa_ifp;
    862 		else
    863 			rt->rt_ifp = ifa->ifa_ifp;
    864 		if (req == RTM_RESOLVE) {
    865 			rt->rt_rmx = (*ret_nrt)->rt_rmx; /* copy metrics */
    866 			rt->rt_parent = *ret_nrt;
    867 			rt->rt_parent->rt_refcnt++;
    868 		}
    869 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    870 		rc = rt_addaddr(rtbl, rt, netmask);
    871 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    872 		if (rc != 0 && (crt = rtalloc1(rt_getkey(rt), 0)) != NULL) {
    873 			/* overwrite cloned route */
    874 			if ((crt->rt_flags & RTF_CLONED) != 0) {
    875 				rtdeletemsg(crt);
    876 				rc = rt_addaddr(rtbl, rt, netmask);
    877 			}
    878 			rtfree(crt);
    879 			RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    880 		}
    881 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    882 		if (rc != 0) {
    883 			ifafree(ifa);
    884 			if ((rt->rt_flags & RTF_CLONED) != 0 && rt->rt_parent)
    885 				rtfree(rt->rt_parent);
    886 			if (rt->rt_gwroute)
    887 				rtfree(rt->rt_gwroute);
    888 			rt_destroy(rt);
    889 			pool_put(&rtentry_pool, rt);
    890 			senderr(rc);
    891 		}
    892 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    893 		if (ifa->ifa_rtrequest)
    894 			ifa->ifa_rtrequest(req, rt, info);
    895 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    896 		if (ret_nrt) {
    897 			*ret_nrt = rt;
    898 			rt->rt_refcnt++;
    899 		}
    900 		if ((rt->rt_flags & RTF_CLONING) != 0) {
    901 			/* clean up any cloned children */
    902 			rtflushclone(dst->sa_family, rt);
    903 		}
    904 		rtflushall(dst->sa_family);
    905 		break;
    906 	case RTM_GET:
    907 		if (netmask != NULL) {
    908 			rt_maskedcopy(dst, (struct sockaddr *)&maskeddst,
    909 			    netmask);
    910 			dst = (struct sockaddr *)&maskeddst;
    911 		}
    912 		if ((rt = rt_lookup(rtbl, dst, netmask)) == NULL)
    913 			senderr(ESRCH);
    914 		if (ret_nrt != NULL) {
    915 			*ret_nrt = rt;
    916 			rt->rt_refcnt++;
    917 		}
    918 		break;
    919 	}
    920 bad:
    921 	splx(s);
    922 	return error;
    923 }
    924 
    925 int
    926 rt_setgate(struct rtentry *rt, const struct sockaddr *gate)
    927 {
    928 	KASSERT(rt != rt->rt_gwroute);
    929 
    930 	KASSERT(rt->_rt_key != NULL);
    931 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    932 
    933 	if (rt->rt_gwroute) {
    934 		rtfree(rt->rt_gwroute);
    935 		rt->rt_gwroute = NULL;
    936 	}
    937 	KASSERT(rt->_rt_key != NULL);
    938 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    939 	if (rt->rt_gateway != NULL)
    940 		sockaddr_free(rt->rt_gateway);
    941 	KASSERT(rt->_rt_key != NULL);
    942 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    943 	if ((rt->rt_gateway = sockaddr_dup(gate, M_ZERO | M_NOWAIT)) == NULL)
    944 		return ENOMEM;
    945 	KASSERT(rt->_rt_key != NULL);
    946 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    947 
    948 	if (rt->rt_flags & RTF_GATEWAY) {
    949 		KASSERT(rt->_rt_key != NULL);
    950 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    951 		rt->rt_gwroute = rtalloc1(gate, 1);
    952 		/*
    953 		 * If we switched gateways, grab the MTU from the new
    954 		 * gateway route if the current MTU, if the current MTU is
    955 		 * greater than the MTU of gateway.
    956 		 * Note that, if the MTU of gateway is 0, we will reset the
    957 		 * MTU of the route to run PMTUD again from scratch. XXX
    958 		 */
    959 		KASSERT(rt->_rt_key != NULL);
    960 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    961 		if (rt->rt_gwroute
    962 		    && !(rt->rt_rmx.rmx_locks & RTV_MTU)
    963 		    && rt->rt_rmx.rmx_mtu
    964 		    && rt->rt_rmx.rmx_mtu > rt->rt_gwroute->rt_rmx.rmx_mtu) {
    965 			rt->rt_rmx.rmx_mtu = rt->rt_gwroute->rt_rmx.rmx_mtu;
    966 		}
    967 	}
    968 	KASSERT(rt->_rt_key != NULL);
    969 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    970 	return 0;
    971 }
    972 
    973 static void
    974 rt_maskedcopy(const struct sockaddr *src, struct sockaddr *dst,
    975 	const struct sockaddr *netmask)
    976 {
    977 	const char *netmaskp = &netmask->sa_data[0],
    978 	           *srcp = &src->sa_data[0];
    979 	char *dstp = &dst->sa_data[0];
    980 	const char *maskend = (char *)dst + MIN(netmask->sa_len, src->sa_len);
    981 	const char *srcend = (char *)dst + src->sa_len;
    982 
    983 	dst->sa_len = src->sa_len;
    984 	dst->sa_family = src->sa_family;
    985 
    986 	while (dstp < maskend)
    987 		*dstp++ = *srcp++ & *netmaskp++;
    988 	if (dstp < srcend)
    989 		memset(dstp, 0, (size_t)(srcend - dstp));
    990 }
    991 
    992 /*
    993  * Inform the routing socket of a route change.
    994  */
    995 void
    996 rt_newmsg(const int cmd, const struct rtentry *rt)
    997 {
    998 	struct rt_addrinfo info;
    999 
   1000 	memset((void *)&info, 0, sizeof(info));
   1001 	info.rti_info[RTAX_DST] = rt_getkey(rt);
   1002 	info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
   1003 	info.rti_info[RTAX_NETMASK] = rt_mask(rt);
   1004 	if (rt->rt_ifp) {
   1005 		info.rti_info[RTAX_IFP] = rt->rt_ifp->if_dl->ifa_addr;
   1006 		info.rti_info[RTAX_IFA] = rt->rt_ifa->ifa_addr;
   1007 	}
   1008 
   1009 	rt_missmsg(cmd, &info, rt->rt_flags, 0);
   1010 }
   1011 
   1012 /*
   1013  * Set up or tear down a routing table entry, normally
   1014  * for an interface.
   1015  */
   1016 int
   1017 rtinit(struct ifaddr *ifa, int cmd, int flags)
   1018 {
   1019 	struct rtentry *rt;
   1020 	struct sockaddr *dst, *odst;
   1021 	struct sockaddr_storage maskeddst;
   1022 	struct rtentry *nrt = NULL;
   1023 	int error;
   1024 	struct rt_addrinfo info;
   1025 	struct sockaddr_dl *sdl;
   1026 	const struct sockaddr_dl *ifsdl;
   1027 
   1028 	dst = flags & RTF_HOST ? ifa->ifa_dstaddr : ifa->ifa_addr;
   1029 	if (cmd == RTM_DELETE) {
   1030 		if ((flags & RTF_HOST) == 0 && ifa->ifa_netmask) {
   1031 			/* Delete subnet route for this interface */
   1032 			odst = dst;
   1033 			dst = (struct sockaddr *)&maskeddst;
   1034 			rt_maskedcopy(odst, dst, ifa->ifa_netmask);
   1035 		}
   1036 		if ((rt = rtalloc1(dst, 0)) != NULL) {
   1037 			if (rt->rt_ifa != ifa) {
   1038 				rtfree(rt);
   1039 				return (flags & RTF_HOST) ? EHOSTUNREACH
   1040 							: ENETUNREACH;
   1041 			}
   1042 			rtfree(rt);
   1043 		}
   1044 	}
   1045 	memset(&info, 0, sizeof(info));
   1046 	info.rti_ifa = ifa;
   1047 	info.rti_flags = flags | ifa->ifa_flags;
   1048 	info.rti_info[RTAX_DST] = dst;
   1049 	info.rti_info[RTAX_GATEWAY] = ifa->ifa_addr;
   1050 	/*
   1051 	 * XXX here, it seems that we are assuming that ifa_netmask is NULL
   1052 	 * for RTF_HOST.  bsdi4 passes NULL explicitly (via intermediate
   1053 	 * variable) when RTF_HOST is 1.  still not sure if i can safely
   1054 	 * change it to meet bsdi4 behavior.
   1055 	 */
   1056 	if (cmd != RTM_LLINFO_UPD)
   1057 		info.rti_info[RTAX_NETMASK] = ifa->ifa_netmask;
   1058 	error = rtrequest1((cmd == RTM_LLINFO_UPD) ? RTM_GET : cmd, &info,
   1059 	    &nrt);
   1060 	if (error != 0)
   1061 		return error;
   1062 
   1063 	rt = nrt;
   1064 	switch (cmd) {
   1065 	case RTM_DELETE:
   1066 		rt_newmsg(cmd, rt);
   1067 		break;
   1068 	case RTM_LLINFO_UPD:
   1069 		RT_DPRINTF("%s: updating%s\n", __func__,
   1070 		    ((rt->rt_flags & RTF_LLINFO) == 0) ? " (no llinfo)" : "");
   1071 
   1072 		ifsdl = ifa->ifa_ifp->if_sadl;
   1073 
   1074 		if ((rt->rt_flags & RTF_LLINFO) != 0 &&
   1075 		    (sdl = satosdl(rt->rt_gateway)) != NULL &&
   1076 		    sdl->sdl_family == AF_LINK &&
   1077 		    sockaddr_dl_setaddr(sdl, sdl->sdl_len, CLLADDR(ifsdl),
   1078 		                        ifa->ifa_ifp->if_addrlen) == NULL) {
   1079 			error = EINVAL;
   1080 			break;
   1081 		}
   1082 
   1083 		if (cmd == RTM_LLINFO_UPD && ifa->ifa_rtrequest != NULL)
   1084 			ifa->ifa_rtrequest(RTM_LLINFO_UPD, rt, &info);
   1085 		rt_newmsg(RTM_CHANGE, rt);
   1086 		break;
   1087 	case RTM_ADD:
   1088 		if (rt->rt_ifa != ifa) {
   1089 			printf("rtinit: wrong ifa (%p) was (%p)\n", ifa,
   1090 				rt->rt_ifa);
   1091 			if (rt->rt_ifa->ifa_rtrequest != NULL) {
   1092 				rt->rt_ifa->ifa_rtrequest(RTM_DELETE, rt,
   1093 				    &info);
   1094 			}
   1095 			rt_replace_ifa(rt, ifa);
   1096 			rt->rt_ifp = ifa->ifa_ifp;
   1097 			if (ifa->ifa_rtrequest != NULL)
   1098 				ifa->ifa_rtrequest(RTM_ADD, rt, &info);
   1099 		}
   1100 		rt_newmsg(cmd, rt);
   1101 		break;
   1102 	}
   1103 	rtfree(rt);
   1104 	return error;
   1105 }
   1106 
   1107 /*
   1108  * Create a local route entry for the address.
   1109  * Announce the addition of the address and the route to the routing socket.
   1110  */
   1111 int
   1112 rt_ifa_addlocal(struct ifaddr *ifa)
   1113 {
   1114 	struct rtentry *rt;
   1115 	int e;
   1116 
   1117 	/* If there is no loopback entry, allocate one. */
   1118 	rt = rtalloc1(ifa->ifa_addr, 0);
   1119 	if (rt == NULL || (rt->rt_flags & RTF_HOST) == 0 ||
   1120 	    (rt->rt_ifp->if_flags & IFF_LOOPBACK) == 0)
   1121 	{
   1122 		struct rt_addrinfo info;
   1123 		struct rtentry *nrt;
   1124 
   1125 		memset(&info, 0, sizeof(info));
   1126 		info.rti_flags = RTF_HOST | RTF_LOCAL;
   1127 		if (!(ifa->ifa_ifp->if_flags & (IFF_LOOPBACK|IFF_POINTOPOINT)))
   1128 			info.rti_flags |= RTF_LLINFO;
   1129 		info.rti_info[RTAX_DST] = ifa->ifa_addr;
   1130 		info.rti_info[RTAX_GATEWAY] =
   1131 		    (const struct sockaddr *)ifa->ifa_ifp->if_sadl;
   1132 		info.rti_ifa = ifa;
   1133 		nrt = NULL;
   1134 		e = rtrequest1(RTM_ADD, &info, &nrt);
   1135 		if (nrt && ifa != nrt->rt_ifa)
   1136 			rt_replace_ifa(nrt, ifa);
   1137 		rt_newaddrmsg(RTM_ADD, ifa, e, nrt);
   1138 		if (nrt != NULL)
   1139 			rtfree(nrt);
   1140 	} else {
   1141 		e = 0;
   1142 		rt_newaddrmsg(RTM_NEWADDR, ifa, 0, NULL);
   1143 	}
   1144 	if (rt != NULL)
   1145 		rtfree(rt);
   1146 	return e;
   1147 }
   1148 
   1149 /*
   1150  * Remove the local route entry for the address.
   1151  * Announce the removal of the address and the route to the routing socket.
   1152  */
   1153 int
   1154 rt_ifa_remlocal(struct ifaddr *ifa, struct ifaddr *alt_ifa)
   1155 {
   1156 	struct rtentry *rt;
   1157 	int e = 0;
   1158 
   1159 	rt = rtalloc1(ifa->ifa_addr, 0);
   1160 
   1161 	/*
   1162 	 * Before deleting, check if a corresponding loopbacked
   1163 	 * host route surely exists.  With this check, we can avoid
   1164 	 * deleting an interface direct route whose destination is
   1165 	 * the same as the address being removed.  This can happen
   1166 	 * when removing a subnet-router anycast address on an
   1167 	 * interface attached to a shared medium.
   1168 	 */
   1169 	if (rt != NULL &&
   1170 	    (rt->rt_flags & RTF_HOST) &&
   1171 	    (rt->rt_ifp->if_flags & IFF_LOOPBACK))
   1172 	{
   1173 		/* If we cannot replace the route's ifaddr with the equivalent
   1174 		 * ifaddr of another interface, I believe it is safest to
   1175 		 * delete the route.
   1176 		 */
   1177 		if (alt_ifa == NULL) {
   1178 			e = rtdeletemsg(rt);
   1179 			rt_newaddrmsg(RTM_DELADDR, ifa, 0, NULL);
   1180 		} else {
   1181 			rt_replace_ifa(rt, alt_ifa);
   1182 			rt_newmsg(RTM_CHANGE, rt);
   1183 		}
   1184 	} else
   1185 		rt_newaddrmsg(RTM_DELADDR, ifa, 0, NULL);
   1186 	if (rt != NULL)
   1187 		rtfree(rt);
   1188 	return e;
   1189 }
   1190 
   1191 /*
   1192  * Route timer routines.  These routes allow functions to be called
   1193  * for various routes at any time.  This is useful in supporting
   1194  * path MTU discovery and redirect route deletion.
   1195  *
   1196  * This is similar to some BSDI internal functions, but it provides
   1197  * for multiple queues for efficiency's sake...
   1198  */
   1199 
   1200 LIST_HEAD(, rttimer_queue) rttimer_queue_head;
   1201 static int rt_init_done = 0;
   1202 
   1203 /*
   1204  * Some subtle order problems with domain initialization mean that
   1205  * we cannot count on this being run from rt_init before various
   1206  * protocol initializations are done.  Therefore, we make sure
   1207  * that this is run when the first queue is added...
   1208  */
   1209 
   1210 void
   1211 rt_timer_init(void)
   1212 {
   1213 	assert(rt_init_done == 0);
   1214 
   1215 	LIST_INIT(&rttimer_queue_head);
   1216 	callout_init(&rt_timer_ch, 0);
   1217 	callout_reset(&rt_timer_ch, hz, rt_timer_timer, NULL);
   1218 	rt_init_done = 1;
   1219 }
   1220 
   1221 struct rttimer_queue *
   1222 rt_timer_queue_create(u_int timeout)
   1223 {
   1224 	struct rttimer_queue *rtq;
   1225 
   1226 	if (rt_init_done == 0)
   1227 		rt_timer_init();
   1228 
   1229 	R_Malloc(rtq, struct rttimer_queue *, sizeof *rtq);
   1230 	if (rtq == NULL)
   1231 		return NULL;
   1232 	memset(rtq, 0, sizeof(*rtq));
   1233 
   1234 	rtq->rtq_timeout = timeout;
   1235 	TAILQ_INIT(&rtq->rtq_head);
   1236 	LIST_INSERT_HEAD(&rttimer_queue_head, rtq, rtq_link);
   1237 
   1238 	return rtq;
   1239 }
   1240 
   1241 void
   1242 rt_timer_queue_change(struct rttimer_queue *rtq, long timeout)
   1243 {
   1244 
   1245 	rtq->rtq_timeout = timeout;
   1246 }
   1247 
   1248 void
   1249 rt_timer_queue_remove_all(struct rttimer_queue *rtq, int destroy)
   1250 {
   1251 	struct rttimer *r;
   1252 
   1253 	while ((r = TAILQ_FIRST(&rtq->rtq_head)) != NULL) {
   1254 		LIST_REMOVE(r, rtt_link);
   1255 		TAILQ_REMOVE(&rtq->rtq_head, r, rtt_next);
   1256 		if (destroy)
   1257 			(*r->rtt_func)(r->rtt_rt, r);
   1258 		rtfree(r->rtt_rt);
   1259 		/* we are already at splsoftnet */
   1260 		pool_put(&rttimer_pool, r);
   1261 		if (rtq->rtq_count > 0)
   1262 			rtq->rtq_count--;
   1263 		else
   1264 			printf("rt_timer_queue_remove_all: "
   1265 			    "rtq_count reached 0\n");
   1266 	}
   1267 }
   1268 
   1269 void
   1270 rt_timer_queue_destroy(struct rttimer_queue *rtq, int destroy)
   1271 {
   1272 
   1273 	rt_timer_queue_remove_all(rtq, destroy);
   1274 
   1275 	LIST_REMOVE(rtq, rtq_link);
   1276 
   1277 	/*
   1278 	 * Caller is responsible for freeing the rttimer_queue structure.
   1279 	 */
   1280 }
   1281 
   1282 unsigned long
   1283 rt_timer_count(struct rttimer_queue *rtq)
   1284 {
   1285 	return rtq->rtq_count;
   1286 }
   1287 
   1288 void
   1289 rt_timer_remove_all(struct rtentry *rt, int destroy)
   1290 {
   1291 	struct rttimer *r;
   1292 
   1293 	while ((r = LIST_FIRST(&rt->rt_timer)) != NULL) {
   1294 		LIST_REMOVE(r, rtt_link);
   1295 		TAILQ_REMOVE(&r->rtt_queue->rtq_head, r, rtt_next);
   1296 		if (destroy)
   1297 			(*r->rtt_func)(r->rtt_rt, r);
   1298 		if (r->rtt_queue->rtq_count > 0)
   1299 			r->rtt_queue->rtq_count--;
   1300 		else
   1301 			printf("rt_timer_remove_all: rtq_count reached 0\n");
   1302 		rtfree(r->rtt_rt);
   1303 		/* we are already at splsoftnet */
   1304 		pool_put(&rttimer_pool, r);
   1305 	}
   1306 }
   1307 
   1308 int
   1309 rt_timer_add(struct rtentry *rt,
   1310 	void (*func)(struct rtentry *, struct rttimer *),
   1311 	struct rttimer_queue *queue)
   1312 {
   1313 	struct rttimer *r;
   1314 	int s;
   1315 
   1316 	KASSERT(func != NULL);
   1317 	/*
   1318 	 * If there's already a timer with this action, destroy it before
   1319 	 * we add a new one.
   1320 	 */
   1321 	LIST_FOREACH(r, &rt->rt_timer, rtt_link) {
   1322 		if (r->rtt_func == func)
   1323 			break;
   1324 	}
   1325 	if (r != NULL) {
   1326 		LIST_REMOVE(r, rtt_link);
   1327 		TAILQ_REMOVE(&r->rtt_queue->rtq_head, r, rtt_next);
   1328 		if (r->rtt_queue->rtq_count > 0)
   1329 			r->rtt_queue->rtq_count--;
   1330 		else
   1331 			printf("rt_timer_add: rtq_count reached 0\n");
   1332 		rtfree(r->rtt_rt);
   1333 	} else {
   1334 		s = splsoftnet();
   1335 		r = pool_get(&rttimer_pool, PR_NOWAIT);
   1336 		splx(s);
   1337 		if (r == NULL)
   1338 			return ENOBUFS;
   1339 	}
   1340 
   1341 	memset(r, 0, sizeof(*r));
   1342 
   1343 	rt->rt_refcnt++;
   1344 	r->rtt_rt = rt;
   1345 	r->rtt_time = time_uptime;
   1346 	r->rtt_func = func;
   1347 	r->rtt_queue = queue;
   1348 	LIST_INSERT_HEAD(&rt->rt_timer, r, rtt_link);
   1349 	TAILQ_INSERT_TAIL(&queue->rtq_head, r, rtt_next);
   1350 	r->rtt_queue->rtq_count++;
   1351 
   1352 	return 0;
   1353 }
   1354 
   1355 /* ARGSUSED */
   1356 void
   1357 rt_timer_timer(void *arg)
   1358 {
   1359 	struct rttimer_queue *rtq;
   1360 	struct rttimer *r;
   1361 	int s;
   1362 
   1363 	s = splsoftnet();
   1364 	LIST_FOREACH(rtq, &rttimer_queue_head, rtq_link) {
   1365 		while ((r = TAILQ_FIRST(&rtq->rtq_head)) != NULL &&
   1366 		    (r->rtt_time + rtq->rtq_timeout) < time_uptime) {
   1367 			LIST_REMOVE(r, rtt_link);
   1368 			TAILQ_REMOVE(&rtq->rtq_head, r, rtt_next);
   1369 			(*r->rtt_func)(r->rtt_rt, r);
   1370 			rtfree(r->rtt_rt);
   1371 			pool_put(&rttimer_pool, r);
   1372 			if (rtq->rtq_count > 0)
   1373 				rtq->rtq_count--;
   1374 			else
   1375 				printf("rt_timer_timer: rtq_count reached 0\n");
   1376 		}
   1377 	}
   1378 	splx(s);
   1379 
   1380 	callout_reset(&rt_timer_ch, hz, rt_timer_timer, NULL);
   1381 }
   1382 
   1383 static struct rtentry *
   1384 _rtcache_init(struct route *ro, int flag)
   1385 {
   1386 	rtcache_invariants(ro);
   1387 	KASSERT(ro->_ro_rt == NULL);
   1388 
   1389 	if (rtcache_getdst(ro) == NULL)
   1390 		return NULL;
   1391 	ro->ro_invalid = false;
   1392 	if ((ro->_ro_rt = rtalloc1(rtcache_getdst(ro), flag)) != NULL)
   1393 		rtcache(ro);
   1394 
   1395 	rtcache_invariants(ro);
   1396 	return ro->_ro_rt;
   1397 }
   1398 
   1399 struct rtentry *
   1400 rtcache_init(struct route *ro)
   1401 {
   1402 	return _rtcache_init(ro, 1);
   1403 }
   1404 
   1405 struct rtentry *
   1406 rtcache_init_noclone(struct route *ro)
   1407 {
   1408 	return _rtcache_init(ro, 0);
   1409 }
   1410 
   1411 struct rtentry *
   1412 rtcache_update(struct route *ro, int clone)
   1413 {
   1414 	rtcache_clear(ro);
   1415 	return _rtcache_init(ro, clone);
   1416 }
   1417 
   1418 void
   1419 rtcache_copy(struct route *new_ro, const struct route *old_ro)
   1420 {
   1421 	struct rtentry *rt;
   1422 
   1423 	KASSERT(new_ro != old_ro);
   1424 	rtcache_invariants(new_ro);
   1425 	rtcache_invariants(old_ro);
   1426 
   1427 	if ((rt = rtcache_validate(old_ro)) != NULL)
   1428 		rt->rt_refcnt++;
   1429 
   1430 	if (rtcache_getdst(old_ro) == NULL ||
   1431 	    rtcache_setdst(new_ro, rtcache_getdst(old_ro)) != 0)
   1432 		return;
   1433 
   1434 	new_ro->ro_invalid = false;
   1435 	if ((new_ro->_ro_rt = rt) != NULL)
   1436 		rtcache(new_ro);
   1437 	rtcache_invariants(new_ro);
   1438 }
   1439 
   1440 static struct dom_rtlist invalid_routes = LIST_HEAD_INITIALIZER(dom_rtlist);
   1441 
   1442 static void
   1443 rtcache_invalidate(struct dom_rtlist *rtlist)
   1444 {
   1445 	struct route *ro;
   1446 
   1447 	while ((ro = LIST_FIRST(rtlist)) != NULL) {
   1448 		rtcache_invariants(ro);
   1449 		KASSERT(ro->_ro_rt != NULL);
   1450 		ro->ro_invalid = true;
   1451 		LIST_REMOVE(ro, ro_rtcache_next);
   1452 		LIST_INSERT_HEAD(&invalid_routes, ro, ro_rtcache_next);
   1453 		rtcache_invariants(ro);
   1454 	}
   1455 }
   1456 
   1457 static void
   1458 rtcache_clear(struct route *ro)
   1459 {
   1460 	rtcache_invariants(ro);
   1461 	if (ro->_ro_rt == NULL)
   1462 		return;
   1463 
   1464 	LIST_REMOVE(ro, ro_rtcache_next);
   1465 
   1466 	rtfree(ro->_ro_rt);
   1467 	ro->_ro_rt = NULL;
   1468 	ro->ro_invalid = false;
   1469 	rtcache_invariants(ro);
   1470 }
   1471 
   1472 struct rtentry *
   1473 rtcache_lookup2(struct route *ro, const struct sockaddr *dst, int clone,
   1474     int *hitp)
   1475 {
   1476 	const struct sockaddr *odst;
   1477 	struct rtentry *rt = NULL;
   1478 
   1479 	odst = rtcache_getdst(ro);
   1480 	if (odst == NULL)
   1481 		goto miss;
   1482 
   1483 	if (sockaddr_cmp(odst, dst) != 0) {
   1484 		rtcache_free(ro);
   1485 		goto miss;
   1486 	}
   1487 
   1488 	rt = rtcache_validate(ro);
   1489 	if (rt == NULL) {
   1490 		rtcache_clear(ro);
   1491 		goto miss;
   1492 	}
   1493 
   1494 	*hitp = 1;
   1495 	rtcache_invariants(ro);
   1496 
   1497 	return rt;
   1498 miss:
   1499 	*hitp = 0;
   1500 	if (rtcache_setdst(ro, dst) == 0)
   1501 		rt = _rtcache_init(ro, clone);
   1502 
   1503 	rtcache_invariants(ro);
   1504 
   1505 	return rt;
   1506 }
   1507 
   1508 void
   1509 rtcache_free(struct route *ro)
   1510 {
   1511 	rtcache_clear(ro);
   1512 	if (ro->ro_sa != NULL) {
   1513 		sockaddr_free(ro->ro_sa);
   1514 		ro->ro_sa = NULL;
   1515 	}
   1516 	rtcache_invariants(ro);
   1517 }
   1518 
   1519 int
   1520 rtcache_setdst(struct route *ro, const struct sockaddr *sa)
   1521 {
   1522 	KASSERT(sa != NULL);
   1523 
   1524 	rtcache_invariants(ro);
   1525 	if (ro->ro_sa != NULL) {
   1526 		if (ro->ro_sa->sa_family == sa->sa_family) {
   1527 			rtcache_clear(ro);
   1528 			sockaddr_copy(ro->ro_sa, ro->ro_sa->sa_len, sa);
   1529 			rtcache_invariants(ro);
   1530 			return 0;
   1531 		}
   1532 		/* free ro_sa, wrong family */
   1533 		rtcache_free(ro);
   1534 	}
   1535 
   1536 	KASSERT(ro->_ro_rt == NULL);
   1537 
   1538 	if ((ro->ro_sa = sockaddr_dup(sa, M_ZERO | M_NOWAIT)) == NULL) {
   1539 		rtcache_invariants(ro);
   1540 		return ENOMEM;
   1541 	}
   1542 	rtcache_invariants(ro);
   1543 	return 0;
   1544 }
   1545 
   1546 const struct sockaddr *
   1547 rt_settag(struct rtentry *rt, const struct sockaddr *tag)
   1548 {
   1549 	if (rt->rt_tag != tag) {
   1550 		if (rt->rt_tag != NULL)
   1551 			sockaddr_free(rt->rt_tag);
   1552 		rt->rt_tag = sockaddr_dup(tag, M_ZERO | M_NOWAIT);
   1553 	}
   1554 	return rt->rt_tag;
   1555 }
   1556 
   1557 struct sockaddr *
   1558 rt_gettag(struct rtentry *rt)
   1559 {
   1560 	return rt->rt_tag;
   1561 }
   1562