Home | History | Annotate | Line # | Download | only in net
route.c revision 1.131
      1 /*	$NetBSD: route.c,v 1.131 2014/06/06 01:02:47 rmind 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 #include "opt_route.h"
     94 
     95 #include <sys/cdefs.h>
     96 __KERNEL_RCSID(0, "$NetBSD: route.c,v 1.131 2014/06/06 01:02:47 rmind Exp $");
     97 
     98 #include <sys/param.h>
     99 #include <sys/kmem.h>
    100 #include <sys/sysctl.h>
    101 #include <sys/systm.h>
    102 #include <sys/callout.h>
    103 #include <sys/proc.h>
    104 #include <sys/mbuf.h>
    105 #include <sys/socket.h>
    106 #include <sys/socketvar.h>
    107 #include <sys/domain.h>
    108 #include <sys/protosw.h>
    109 #include <sys/kernel.h>
    110 #include <sys/ioctl.h>
    111 #include <sys/pool.h>
    112 #include <sys/kauth.h>
    113 
    114 #include <net/if.h>
    115 #include <net/if_dl.h>
    116 #include <net/route.h>
    117 #include <net/raw_cb.h>
    118 
    119 #include <netinet/in.h>
    120 #include <netinet/in_var.h>
    121 
    122 #ifdef RTFLUSH_DEBUG
    123 #define	rtcache_debug() __predict_false(_rtcache_debug)
    124 #else /* RTFLUSH_DEBUG */
    125 #define	rtcache_debug() 0
    126 #endif /* RTFLUSH_DEBUG */
    127 
    128 struct	rtstat	rtstat;
    129 
    130 int	rttrash;		/* routes not in table but not freed */
    131 
    132 struct pool rtentry_pool;
    133 struct pool rttimer_pool;
    134 
    135 struct callout rt_timer_ch; /* callout for rt_timer_timer() */
    136 
    137 #ifdef RTFLUSH_DEBUG
    138 static int _rtcache_debug = 0;
    139 #endif /* RTFLUSH_DEBUG */
    140 
    141 static kauth_listener_t route_listener;
    142 
    143 static int rtdeletemsg(struct rtentry *);
    144 static int rtflushclone1(struct rtentry *, void *);
    145 static void rtflushclone(sa_family_t family, struct rtentry *);
    146 
    147 #ifdef RTFLUSH_DEBUG
    148 static void sysctl_net_rtcache_setup(struct sysctllog **);
    149 static void
    150 sysctl_net_rtcache_setup(struct sysctllog **clog)
    151 {
    152 	const struct sysctlnode *rnode;
    153 
    154 	if (sysctl_createv(clog, 0, NULL, &rnode, CTLFLAG_PERMANENT,
    155 	    CTLTYPE_NODE,
    156 	    "rtcache", SYSCTL_DESCR("Route cache related settings"),
    157 	    NULL, 0, NULL, 0, CTL_NET, CTL_CREATE, CTL_EOL) != 0)
    158 		return;
    159 	if (sysctl_createv(clog, 0, &rnode, &rnode,
    160 	    CTLFLAG_PERMANENT|CTLFLAG_READWRITE, CTLTYPE_INT,
    161 	    "debug", SYSCTL_DESCR("Debug route caches"),
    162 	    NULL, 0, &_rtcache_debug, 0, CTL_CREATE, CTL_EOL) != 0)
    163 		return;
    164 }
    165 #endif /* RTFLUSH_DEBUG */
    166 
    167 struct ifaddr *
    168 rt_get_ifa(struct rtentry *rt)
    169 {
    170 	struct ifaddr *ifa;
    171 
    172 	if ((ifa = rt->rt_ifa) == NULL)
    173 		return ifa;
    174 	else if (ifa->ifa_getifa == NULL)
    175 		return ifa;
    176 #if 0
    177 	else if (ifa->ifa_seqno != NULL && *ifa->ifa_seqno == rt->rt_ifa_seqno)
    178 		return ifa;
    179 #endif
    180 	else {
    181 		ifa = (*ifa->ifa_getifa)(ifa, rt_getkey(rt));
    182 		rt_replace_ifa(rt, ifa);
    183 		return ifa;
    184 	}
    185 }
    186 
    187 static void
    188 rt_set_ifa1(struct rtentry *rt, struct ifaddr *ifa)
    189 {
    190 	rt->rt_ifa = ifa;
    191 	if (ifa->ifa_seqno != NULL)
    192 		rt->rt_ifa_seqno = *ifa->ifa_seqno;
    193 }
    194 
    195 /*
    196  * Is this route the connected route for the ifa?
    197  */
    198 static int
    199 rt_ifa_connected(const struct rtentry *rt, const struct ifaddr *ifa)
    200 {
    201 	const struct sockaddr *key, *dst, *odst;
    202 	struct sockaddr_storage maskeddst;
    203 
    204 	key = rt_getkey(rt);
    205 	dst = rt->rt_flags & RTF_HOST ? ifa->ifa_dstaddr : ifa->ifa_addr;
    206 	if (dst == NULL ||
    207 	    dst->sa_family != key->sa_family ||
    208 	    dst->sa_len != key->sa_len)
    209 		return 0;
    210 	if ((rt->rt_flags & RTF_HOST) == 0 && ifa->ifa_netmask) {
    211 		odst = dst;
    212 		dst = (struct sockaddr *)&maskeddst;
    213 		rt_maskedcopy(odst, (struct sockaddr *)&maskeddst,
    214 		    ifa->ifa_netmask);
    215 	}
    216 	return (memcmp(dst, key, dst->sa_len) == 0);
    217 }
    218 
    219 void
    220 rt_replace_ifa(struct rtentry *rt, struct ifaddr *ifa)
    221 {
    222 	if (rt->rt_ifa &&
    223 	    rt->rt_ifa != ifa &&
    224 	    rt->rt_ifa->ifa_flags & IFA_ROUTE &&
    225 	    rt_ifa_connected(rt, rt->rt_ifa))
    226 	{
    227 		RT_DPRINTF("rt->_rt_key = %p, ifa = %p, "
    228 		    "replace deleted IFA_ROUTE\n",
    229 		    (void *)rt->_rt_key, (void *)rt->rt_ifa);
    230 		rt->rt_ifa->ifa_flags &= ~IFA_ROUTE;
    231 		if (rt_ifa_connected(rt, ifa)) {
    232 			RT_DPRINTF("rt->_rt_key = %p, ifa = %p, "
    233 			    "replace added IFA_ROUTE\n",
    234 			    (void *)rt->_rt_key, (void *)ifa);
    235 			ifa->ifa_flags |= IFA_ROUTE;
    236 		}
    237 	}
    238 
    239 	IFAREF(ifa);
    240 	IFAFREE(rt->rt_ifa);
    241 	rt_set_ifa1(rt, ifa);
    242 }
    243 
    244 static void
    245 rt_set_ifa(struct rtentry *rt, struct ifaddr *ifa)
    246 {
    247 	IFAREF(ifa);
    248 	rt_set_ifa1(rt, ifa);
    249 }
    250 
    251 static int
    252 route_listener_cb(kauth_cred_t cred, kauth_action_t action, void *cookie,
    253     void *arg0, void *arg1, void *arg2, void *arg3)
    254 {
    255 	struct rt_msghdr *rtm;
    256 	int result;
    257 
    258 	result = KAUTH_RESULT_DEFER;
    259 	rtm = arg1;
    260 
    261 	if (action != KAUTH_NETWORK_ROUTE)
    262 		return result;
    263 
    264 	if (rtm->rtm_type == RTM_GET)
    265 		result = KAUTH_RESULT_ALLOW;
    266 
    267 	return result;
    268 }
    269 
    270 void
    271 rt_init(void)
    272 {
    273 
    274 #ifdef RTFLUSH_DEBUG
    275 	sysctl_net_rtcache_setup(NULL);
    276 #endif
    277 
    278 	pool_init(&rtentry_pool, sizeof(struct rtentry), 0, 0, 0, "rtentpl",
    279 	    NULL, IPL_SOFTNET);
    280 	pool_init(&rttimer_pool, sizeof(struct rttimer), 0, 0, 0, "rttmrpl",
    281 	    NULL, IPL_SOFTNET);
    282 
    283 	rn_init();	/* initialize all zeroes, all ones, mask table */
    284 	rtbl_init();
    285 
    286 	route_listener = kauth_listen_scope(KAUTH_SCOPE_NETWORK,
    287 	    route_listener_cb, NULL);
    288 }
    289 
    290 void
    291 rtflushall(int family)
    292 {
    293 	struct domain *dom;
    294 
    295 	if (rtcache_debug())
    296 		printf("%s: enter\n", __func__);
    297 
    298 	if ((dom = pffinddomain(family)) == NULL)
    299 		return;
    300 
    301 	rtcache_invalidate(&dom->dom_rtcache);
    302 }
    303 
    304 static void
    305 rtcache(struct route *ro)
    306 {
    307 	struct domain *dom;
    308 
    309 	rtcache_invariants(ro);
    310 	KASSERT(ro->_ro_rt != NULL);
    311 	KASSERT(ro->ro_invalid == false);
    312 	KASSERT(rtcache_getdst(ro) != NULL);
    313 
    314 	if ((dom = pffinddomain(rtcache_getdst(ro)->sa_family)) == NULL)
    315 		return;
    316 
    317 	LIST_INSERT_HEAD(&dom->dom_rtcache, ro, ro_rtcache_next);
    318 	rtcache_invariants(ro);
    319 }
    320 
    321 /*
    322  * Packet routing routines.
    323  */
    324 struct rtentry *
    325 rtalloc1(const struct sockaddr *dst, int report)
    326 {
    327 	rtbl_t *rtbl = rt_gettable(dst->sa_family);
    328 	struct rtentry *rt;
    329 	struct rtentry *newrt = NULL;
    330 	struct rt_addrinfo info;
    331 	int  s = splsoftnet(), err = 0, msgtype = RTM_MISS;
    332 
    333 	if (rtbl != NULL && (rt = rt_matchaddr(rtbl, dst)) != NULL) {
    334 		newrt = rt;
    335 		if (report && (rt->rt_flags & RTF_CLONING)) {
    336 			err = rtrequest(RTM_RESOLVE, dst, NULL, NULL, 0,
    337 			    &newrt);
    338 			if (err) {
    339 				newrt = rt;
    340 				rt->rt_refcnt++;
    341 				goto miss;
    342 			}
    343 			KASSERT(newrt != NULL);
    344 			rt = newrt;
    345 			if (rt->rt_flags & RTF_XRESOLVE) {
    346 				msgtype = RTM_RESOLVE;
    347 				goto miss;
    348 			}
    349 			/* Inform listeners of the new route */
    350 			memset(&info, 0, sizeof(info));
    351 			info.rti_info[RTAX_DST] = rt_getkey(rt);
    352 			info.rti_info[RTAX_NETMASK] = rt_mask(rt);
    353 			info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
    354 			if (rt->rt_ifp != NULL) {
    355 				info.rti_info[RTAX_IFP] =
    356 				    rt->rt_ifp->if_dl->ifa_addr;
    357 				info.rti_info[RTAX_IFA] = rt->rt_ifa->ifa_addr;
    358 			}
    359 			rt_missmsg(RTM_ADD, &info, rt->rt_flags, 0);
    360 		} else
    361 			rt->rt_refcnt++;
    362 	} else {
    363 		rtstat.rts_unreach++;
    364 	miss:	if (report) {
    365 			memset((void *)&info, 0, sizeof(info));
    366 			info.rti_info[RTAX_DST] = dst;
    367 			rt_missmsg(msgtype, &info, 0, err);
    368 		}
    369 	}
    370 	splx(s);
    371 	return newrt;
    372 }
    373 
    374 void
    375 rtfree(struct rtentry *rt)
    376 {
    377 	struct ifaddr *ifa;
    378 
    379 	if (rt == NULL)
    380 		panic("rtfree");
    381 	rt->rt_refcnt--;
    382 	if (rt->rt_refcnt <= 0 && (rt->rt_flags & RTF_UP) == 0) {
    383 		rt_assert_inactive(rt);
    384 		rttrash--;
    385 		if (rt->rt_refcnt < 0) {
    386 			printf("rtfree: %p not freed (neg refs)\n", rt);
    387 			return;
    388 		}
    389 		rt_timer_remove_all(rt, 0);
    390 		ifa = rt->rt_ifa;
    391 		rt->rt_ifa = NULL;
    392 		IFAFREE(ifa);
    393 		rt->rt_ifp = NULL;
    394 		rt_destroy(rt);
    395 		pool_put(&rtentry_pool, rt);
    396 	}
    397 }
    398 
    399 void
    400 ifafree(struct ifaddr *ifa)
    401 {
    402 
    403 #ifdef DIAGNOSTIC
    404 	if (ifa == NULL)
    405 		panic("ifafree: null ifa");
    406 	if (ifa->ifa_refcnt != 0)
    407 		panic("ifafree: ifa_refcnt != 0 (%d)", ifa->ifa_refcnt);
    408 #endif
    409 #ifdef IFAREF_DEBUG
    410 	printf("ifafree: freeing ifaddr %p\n", ifa);
    411 #endif
    412 	free(ifa, M_IFADDR);
    413 }
    414 
    415 /*
    416  * Force a routing table entry to the specified
    417  * destination to go through the given gateway.
    418  * Normally called as a result of a routing redirect
    419  * message from the network layer.
    420  *
    421  * N.B.: must be called at splsoftnet
    422  */
    423 void
    424 rtredirect(const struct sockaddr *dst, const struct sockaddr *gateway,
    425 	const struct sockaddr *netmask, int flags, const struct sockaddr *src,
    426 	struct rtentry **rtp)
    427 {
    428 	struct rtentry *rt;
    429 	int error = 0;
    430 	uint64_t *stat = NULL;
    431 	struct rt_addrinfo info;
    432 	struct ifaddr *ifa;
    433 
    434 	/* verify the gateway is directly reachable */
    435 	if ((ifa = ifa_ifwithnet(gateway)) == NULL) {
    436 		error = ENETUNREACH;
    437 		goto out;
    438 	}
    439 	rt = rtalloc1(dst, 0);
    440 	/*
    441 	 * If the redirect isn't from our current router for this dst,
    442 	 * it's either old or wrong.  If it redirects us to ourselves,
    443 	 * we have a routing loop, perhaps as a result of an interface
    444 	 * going down recently.
    445 	 */
    446 	if (!(flags & RTF_DONE) && rt &&
    447 	     (sockaddr_cmp(src, rt->rt_gateway) != 0 || rt->rt_ifa != ifa))
    448 		error = EINVAL;
    449 	else if (ifa_ifwithaddr(gateway))
    450 		error = EHOSTUNREACH;
    451 	if (error)
    452 		goto done;
    453 	/*
    454 	 * Create a new entry if we just got back a wildcard entry
    455 	 * or the lookup failed.  This is necessary for hosts
    456 	 * which use routing redirects generated by smart gateways
    457 	 * to dynamically build the routing tables.
    458 	 */
    459 	if (rt == NULL || (rt_mask(rt) && rt_mask(rt)->sa_len < 2))
    460 		goto create;
    461 	/*
    462 	 * Don't listen to the redirect if it's
    463 	 * for a route to an interface.
    464 	 */
    465 	if (rt->rt_flags & RTF_GATEWAY) {
    466 		if (((rt->rt_flags & RTF_HOST) == 0) && (flags & RTF_HOST)) {
    467 			/*
    468 			 * Changing from route to net => route to host.
    469 			 * Create new route, rather than smashing route to net.
    470 			 */
    471 		create:
    472 			if (rt != NULL)
    473 				rtfree(rt);
    474 			flags |=  RTF_GATEWAY | RTF_DYNAMIC;
    475 			memset(&info, 0, sizeof(info));
    476 			info.rti_info[RTAX_DST] = dst;
    477 			info.rti_info[RTAX_GATEWAY] = gateway;
    478 			info.rti_info[RTAX_NETMASK] = netmask;
    479 			info.rti_ifa = ifa;
    480 			info.rti_flags = flags;
    481 			rt = NULL;
    482 			error = rtrequest1(RTM_ADD, &info, &rt);
    483 			if (rt != NULL)
    484 				flags = rt->rt_flags;
    485 			stat = &rtstat.rts_dynamic;
    486 		} else {
    487 			/*
    488 			 * Smash the current notion of the gateway to
    489 			 * this destination.  Should check about netmask!!!
    490 			 */
    491 			rt->rt_flags |= RTF_MODIFIED;
    492 			flags |= RTF_MODIFIED;
    493 			stat = &rtstat.rts_newgateway;
    494 			rt_setgate(rt, gateway);
    495 		}
    496 	} else
    497 		error = EHOSTUNREACH;
    498 done:
    499 	if (rt) {
    500 		if (rtp != NULL && !error)
    501 			*rtp = rt;
    502 		else
    503 			rtfree(rt);
    504 	}
    505 out:
    506 	if (error)
    507 		rtstat.rts_badredirect++;
    508 	else if (stat != NULL)
    509 		(*stat)++;
    510 	memset(&info, 0, sizeof(info));
    511 	info.rti_info[RTAX_DST] = dst;
    512 	info.rti_info[RTAX_GATEWAY] = gateway;
    513 	info.rti_info[RTAX_NETMASK] = netmask;
    514 	info.rti_info[RTAX_AUTHOR] = src;
    515 	rt_missmsg(RTM_REDIRECT, &info, flags, error);
    516 }
    517 
    518 /*
    519  * Delete a route and generate a message
    520  */
    521 static int
    522 rtdeletemsg(struct rtentry *rt)
    523 {
    524 	int error;
    525 	struct rt_addrinfo info;
    526 
    527 	/*
    528 	 * Request the new route so that the entry is not actually
    529 	 * deleted.  That will allow the information being reported to
    530 	 * be accurate (and consistent with route_output()).
    531 	 */
    532 	memset(&info, 0, sizeof(info));
    533 	info.rti_info[RTAX_DST] = rt_getkey(rt);
    534 	info.rti_info[RTAX_NETMASK] = rt_mask(rt);
    535 	info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
    536 	info.rti_flags = rt->rt_flags;
    537 	error = rtrequest1(RTM_DELETE, &info, &rt);
    538 
    539 	rt_missmsg(RTM_DELETE, &info, info.rti_flags, error);
    540 
    541 	/* Adjust the refcount */
    542 	if (error == 0 && rt->rt_refcnt <= 0) {
    543 		rt->rt_refcnt++;
    544 		rtfree(rt);
    545 	}
    546 	return error;
    547 }
    548 
    549 static int
    550 rtflushclone1(struct rtentry *rt, void *arg)
    551 {
    552 	struct rtentry *parent;
    553 
    554 	parent = (struct rtentry *)arg;
    555 	if ((rt->rt_flags & RTF_CLONED) != 0 && rt->rt_parent == parent)
    556 		rtdeletemsg(rt);
    557 	return 0;
    558 }
    559 
    560 static void
    561 rtflushclone(sa_family_t family, struct rtentry *parent)
    562 {
    563 
    564 #ifdef DIAGNOSTIC
    565 	if (!parent || (parent->rt_flags & RTF_CLONING) == 0)
    566 		panic("rtflushclone: called with a non-cloning route");
    567 #endif
    568 	rt_walktree(family, rtflushclone1, (void *)parent);
    569 }
    570 
    571 struct ifaddr *
    572 ifa_ifwithroute(int flags, const struct sockaddr *dst,
    573 	const struct sockaddr *gateway)
    574 {
    575 	struct ifaddr *ifa;
    576 	if ((flags & RTF_GATEWAY) == 0) {
    577 		/*
    578 		 * If we are adding a route to an interface,
    579 		 * and the interface is a pt to pt link
    580 		 * we should search for the destination
    581 		 * as our clue to the interface.  Otherwise
    582 		 * we can use the local address.
    583 		 */
    584 		ifa = NULL;
    585 		if ((flags & RTF_HOST) && gateway->sa_family != AF_LINK)
    586 			ifa = ifa_ifwithdstaddr(dst);
    587 		if (ifa == NULL)
    588 			ifa = ifa_ifwithaddr(gateway);
    589 	} else {
    590 		/*
    591 		 * If we are adding a route to a remote net
    592 		 * or host, the gateway may still be on the
    593 		 * other end of a pt to pt link.
    594 		 */
    595 		ifa = ifa_ifwithdstaddr(gateway);
    596 	}
    597 	if (ifa == NULL)
    598 		ifa = ifa_ifwithnet(gateway);
    599 	if (ifa == NULL) {
    600 		struct rtentry *rt = rtalloc1(dst, 0);
    601 		if (rt == NULL)
    602 			return NULL;
    603 		rt->rt_refcnt--;
    604 		if ((ifa = rt->rt_ifa) == NULL)
    605 			return NULL;
    606 	}
    607 	if (ifa->ifa_addr->sa_family != dst->sa_family) {
    608 		struct ifaddr *oifa = ifa;
    609 		ifa = ifaof_ifpforaddr(dst, ifa->ifa_ifp);
    610 		if (ifa == NULL)
    611 			ifa = oifa;
    612 	}
    613 	return ifa;
    614 }
    615 
    616 int
    617 rtrequest(int req, const struct sockaddr *dst, const struct sockaddr *gateway,
    618 	const struct sockaddr *netmask, int flags, struct rtentry **ret_nrt)
    619 {
    620 	struct rt_addrinfo info;
    621 
    622 	memset(&info, 0, sizeof(info));
    623 	info.rti_flags = flags;
    624 	info.rti_info[RTAX_DST] = dst;
    625 	info.rti_info[RTAX_GATEWAY] = gateway;
    626 	info.rti_info[RTAX_NETMASK] = netmask;
    627 	return rtrequest1(req, &info, ret_nrt);
    628 }
    629 
    630 int
    631 rt_getifa(struct rt_addrinfo *info)
    632 {
    633 	struct ifaddr *ifa;
    634 	const struct sockaddr *dst = info->rti_info[RTAX_DST];
    635 	const struct sockaddr *gateway = info->rti_info[RTAX_GATEWAY];
    636 	const struct sockaddr *ifaaddr = info->rti_info[RTAX_IFA];
    637 	const struct sockaddr *ifpaddr = info->rti_info[RTAX_IFP];
    638 	int flags = info->rti_flags;
    639 
    640 	/*
    641 	 * ifp may be specified by sockaddr_dl when protocol address
    642 	 * is ambiguous
    643 	 */
    644 	if (info->rti_ifp == NULL && ifpaddr != NULL
    645 	    && ifpaddr->sa_family == AF_LINK &&
    646 	    (ifa = ifa_ifwithnet(ifpaddr)) != NULL)
    647 		info->rti_ifp = ifa->ifa_ifp;
    648 	if (info->rti_ifa == NULL && ifaaddr != NULL)
    649 		info->rti_ifa = ifa_ifwithaddr(ifaaddr);
    650 	if (info->rti_ifa == NULL) {
    651 		const struct sockaddr *sa;
    652 
    653 		sa = ifaaddr != NULL ? ifaaddr :
    654 		    (gateway != NULL ? gateway : dst);
    655 		if (sa != NULL && info->rti_ifp != NULL)
    656 			info->rti_ifa = ifaof_ifpforaddr(sa, info->rti_ifp);
    657 		else if (dst != NULL && gateway != NULL)
    658 			info->rti_ifa = ifa_ifwithroute(flags, dst, gateway);
    659 		else if (sa != NULL)
    660 			info->rti_ifa = ifa_ifwithroute(flags, sa, sa);
    661 	}
    662 	if ((ifa = info->rti_ifa) == NULL)
    663 		return ENETUNREACH;
    664 	if (ifa->ifa_getifa != NULL)
    665 		info->rti_ifa = ifa = (*ifa->ifa_getifa)(ifa, dst);
    666 	if (info->rti_ifp == NULL)
    667 		info->rti_ifp = ifa->ifa_ifp;
    668 	return 0;
    669 }
    670 
    671 int
    672 rtrequest1(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt)
    673 {
    674 	int s = splsoftnet();
    675 	int error = 0, rc;
    676 	struct rtentry *rt, *crt;
    677 	rtbl_t *rtbl;
    678 	struct ifaddr *ifa, *ifa2;
    679 	struct sockaddr_storage maskeddst;
    680 	const struct sockaddr *dst = info->rti_info[RTAX_DST];
    681 	const struct sockaddr *gateway = info->rti_info[RTAX_GATEWAY];
    682 	const struct sockaddr *netmask = info->rti_info[RTAX_NETMASK];
    683 	int flags = info->rti_flags;
    684 #define senderr(x) { error = x ; goto bad; }
    685 
    686 	if ((rtbl = rt_gettable(dst->sa_family)) == NULL)
    687 		senderr(ESRCH);
    688 	if (flags & RTF_HOST)
    689 		netmask = NULL;
    690 	switch (req) {
    691 	case RTM_DELETE:
    692 		if (netmask) {
    693 			rt_maskedcopy(dst, (struct sockaddr *)&maskeddst,
    694 			    netmask);
    695 			dst = (struct sockaddr *)&maskeddst;
    696 		}
    697 		if ((rt = rt_lookup(rtbl, dst, netmask)) == NULL)
    698 			senderr(ESRCH);
    699 		if ((rt->rt_flags & RTF_CLONING) != 0) {
    700 			/* clean up any cloned children */
    701 			rtflushclone(dst->sa_family, rt);
    702 		}
    703 		if ((rt = rt_deladdr(rtbl, dst, netmask)) == NULL)
    704 			senderr(ESRCH);
    705 		if (rt->rt_gwroute) {
    706 			rtfree(rt->rt_gwroute);
    707 			rt->rt_gwroute = NULL;
    708 		}
    709 		if (rt->rt_parent) {
    710 			rt->rt_parent->rt_refcnt--;
    711 			rt->rt_parent = NULL;
    712 		}
    713 		rt->rt_flags &= ~RTF_UP;
    714 		if ((ifa = rt->rt_ifa)) {
    715 			if (ifa->ifa_flags & IFA_ROUTE &&
    716 			    rt_ifa_connected(rt, ifa)) {
    717 				RT_DPRINTF("rt->_rt_key = %p, ifa = %p, "
    718 				    "deleted IFA_ROUTE\n",
    719 				    (void *)rt->_rt_key, (void *)ifa);
    720 				ifa->ifa_flags &= ~IFA_ROUTE;
    721 			}
    722 			if (ifa->ifa_rtrequest)
    723 				ifa->ifa_rtrequest(RTM_DELETE, rt, info);
    724 		}
    725 		rttrash++;
    726 		if (ret_nrt)
    727 			*ret_nrt = rt;
    728 		else if (rt->rt_refcnt <= 0) {
    729 			rt->rt_refcnt++;
    730 			rtfree(rt);
    731 		}
    732 		break;
    733 
    734 	case RTM_RESOLVE:
    735 		if (ret_nrt == NULL || (rt = *ret_nrt) == NULL)
    736 			senderr(EINVAL);
    737 		if ((rt->rt_flags & RTF_CLONING) == 0)
    738 			senderr(EINVAL);
    739 		ifa = rt->rt_ifa;
    740 		flags = rt->rt_flags & ~(RTF_CLONING | RTF_STATIC);
    741 		flags |= RTF_CLONED;
    742 		gateway = rt->rt_gateway;
    743 		flags |= RTF_HOST;
    744 		goto makeroute;
    745 
    746 	case RTM_ADD:
    747 		if (info->rti_ifa == NULL && (error = rt_getifa(info)))
    748 			senderr(error);
    749 		ifa = info->rti_ifa;
    750 	makeroute:
    751 		/* Already at splsoftnet() so pool_get/pool_put are safe */
    752 		rt = pool_get(&rtentry_pool, PR_NOWAIT);
    753 		if (rt == NULL)
    754 			senderr(ENOBUFS);
    755 		memset(rt, 0, sizeof(*rt));
    756 		rt->rt_flags = RTF_UP | flags;
    757 		LIST_INIT(&rt->rt_timer);
    758 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    759 		if (rt_setkey(rt, dst, M_NOWAIT) == NULL ||
    760 		    rt_setgate(rt, gateway) != 0) {
    761 			pool_put(&rtentry_pool, rt);
    762 			senderr(ENOBUFS);
    763 		}
    764 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    765 		if (netmask) {
    766 			rt_maskedcopy(dst, (struct sockaddr *)&maskeddst,
    767 			    netmask);
    768 			rt_setkey(rt, (struct sockaddr *)&maskeddst, M_NOWAIT);
    769 			RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    770 		} else {
    771 			rt_setkey(rt, dst, M_NOWAIT);
    772 			RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    773 		}
    774 		rt_set_ifa(rt, ifa);
    775 		if (info->rti_info[RTAX_TAG] != NULL)
    776 			rt_settag(rt, info->rti_info[RTAX_TAG]);
    777 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    778 		if (info->rti_info[RTAX_IFP] != NULL &&
    779 		    (ifa2 = ifa_ifwithnet(info->rti_info[RTAX_IFP])) != NULL &&
    780 		    ifa2->ifa_ifp != NULL)
    781 			rt->rt_ifp = ifa2->ifa_ifp;
    782 		else
    783 			rt->rt_ifp = ifa->ifa_ifp;
    784 		if (req == RTM_RESOLVE) {
    785 			rt->rt_rmx = (*ret_nrt)->rt_rmx; /* copy metrics */
    786 			rt->rt_parent = *ret_nrt;
    787 			rt->rt_parent->rt_refcnt++;
    788 		}
    789 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    790 		rc = rt_addaddr(rtbl, rt, netmask);
    791 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    792 		if (rc != 0 && (crt = rtalloc1(rt_getkey(rt), 0)) != NULL) {
    793 			/* overwrite cloned route */
    794 			if ((crt->rt_flags & RTF_CLONED) != 0) {
    795 				rtdeletemsg(crt);
    796 				rc = rt_addaddr(rtbl, rt, netmask);
    797 			}
    798 			rtfree(crt);
    799 			RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    800 		}
    801 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    802 		if (rc != 0) {
    803 			IFAFREE(ifa);
    804 			if ((rt->rt_flags & RTF_CLONED) != 0 && rt->rt_parent)
    805 				rtfree(rt->rt_parent);
    806 			if (rt->rt_gwroute)
    807 				rtfree(rt->rt_gwroute);
    808 			rt_destroy(rt);
    809 			pool_put(&rtentry_pool, rt);
    810 			senderr(rc);
    811 		}
    812 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    813 		if (ifa->ifa_rtrequest)
    814 			ifa->ifa_rtrequest(req, rt, info);
    815 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    816 		if (ret_nrt) {
    817 			*ret_nrt = rt;
    818 			rt->rt_refcnt++;
    819 		}
    820 		if ((rt->rt_flags & RTF_CLONING) != 0) {
    821 			/* clean up any cloned children */
    822 			rtflushclone(dst->sa_family, rt);
    823 		}
    824 		rtflushall(dst->sa_family);
    825 		break;
    826 	case RTM_GET:
    827 		if (netmask != NULL) {
    828 			rt_maskedcopy(dst, (struct sockaddr *)&maskeddst,
    829 			    netmask);
    830 			dst = (struct sockaddr *)&maskeddst;
    831 		}
    832 		if ((rt = rt_lookup(rtbl, dst, netmask)) == NULL)
    833 			senderr(ESRCH);
    834 		if (ret_nrt != NULL) {
    835 			*ret_nrt = rt;
    836 			rt->rt_refcnt++;
    837 		}
    838 		break;
    839 	}
    840 bad:
    841 	splx(s);
    842 	return error;
    843 }
    844 
    845 int
    846 rt_setgate(struct rtentry *rt, const struct sockaddr *gate)
    847 {
    848 	KASSERT(rt != rt->rt_gwroute);
    849 
    850 	KASSERT(rt->_rt_key != NULL);
    851 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    852 
    853 	if (rt->rt_gwroute) {
    854 		rtfree(rt->rt_gwroute);
    855 		rt->rt_gwroute = NULL;
    856 	}
    857 	KASSERT(rt->_rt_key != NULL);
    858 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    859 	if (rt->rt_gateway != NULL)
    860 		sockaddr_free(rt->rt_gateway);
    861 	KASSERT(rt->_rt_key != NULL);
    862 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    863 	if ((rt->rt_gateway = sockaddr_dup(gate, M_NOWAIT)) == NULL)
    864 		return ENOMEM;
    865 	KASSERT(rt->_rt_key != NULL);
    866 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    867 
    868 	if (rt->rt_flags & RTF_GATEWAY) {
    869 		KASSERT(rt->_rt_key != NULL);
    870 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    871 		rt->rt_gwroute = rtalloc1(gate, 1);
    872 		/*
    873 		 * If we switched gateways, grab the MTU from the new
    874 		 * gateway route if the current MTU, if the current MTU is
    875 		 * greater than the MTU of gateway.
    876 		 * Note that, if the MTU of gateway is 0, we will reset the
    877 		 * MTU of the route to run PMTUD again from scratch. XXX
    878 		 */
    879 		KASSERT(rt->_rt_key != NULL);
    880 		RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    881 		if (rt->rt_gwroute
    882 		    && !(rt->rt_rmx.rmx_locks & RTV_MTU)
    883 		    && rt->rt_rmx.rmx_mtu
    884 		    && rt->rt_rmx.rmx_mtu > rt->rt_gwroute->rt_rmx.rmx_mtu) {
    885 			rt->rt_rmx.rmx_mtu = rt->rt_gwroute->rt_rmx.rmx_mtu;
    886 		}
    887 	}
    888 	KASSERT(rt->_rt_key != NULL);
    889 	RT_DPRINTF("rt->_rt_key = %p\n", (void *)rt->_rt_key);
    890 	return 0;
    891 }
    892 
    893 void
    894 rt_maskedcopy(const struct sockaddr *src, struct sockaddr *dst,
    895 	const struct sockaddr *netmask)
    896 {
    897 	const char *netmaskp = &netmask->sa_data[0],
    898 	           *srcp = &src->sa_data[0];
    899 	char *dstp = &dst->sa_data[0];
    900 	const char *maskend = (char *)dst + MIN(netmask->sa_len, src->sa_len);
    901 	const char *srcend = (char *)dst + src->sa_len;
    902 
    903 	dst->sa_len = src->sa_len;
    904 	dst->sa_family = src->sa_family;
    905 
    906 	while (dstp < maskend)
    907 		*dstp++ = *srcp++ & *netmaskp++;
    908 	if (dstp < srcend)
    909 		memset(dstp, 0, (size_t)(srcend - dstp));
    910 }
    911 
    912 /*
    913  * Set up or tear down a routing table entry, normally
    914  * for an interface.
    915  */
    916 int
    917 rtinit(struct ifaddr *ifa, int cmd, int flags)
    918 {
    919 	struct rtentry *rt;
    920 	struct sockaddr *dst, *odst;
    921 	struct sockaddr_storage maskeddst;
    922 	struct rtentry *nrt = NULL;
    923 	int error;
    924 	struct rt_addrinfo info;
    925 	struct sockaddr_dl *sdl;
    926 	const struct sockaddr_dl *ifsdl;
    927 
    928 	dst = flags & RTF_HOST ? ifa->ifa_dstaddr : ifa->ifa_addr;
    929 	if (cmd == RTM_DELETE) {
    930 		if ((flags & RTF_HOST) == 0 && ifa->ifa_netmask) {
    931 			/* Delete subnet route for this interface */
    932 			odst = dst;
    933 			dst = (struct sockaddr *)&maskeddst;
    934 			rt_maskedcopy(odst, dst, ifa->ifa_netmask);
    935 		}
    936 		if ((rt = rtalloc1(dst, 0)) != NULL) {
    937 			rt->rt_refcnt--;
    938 			if (rt->rt_ifa != ifa)
    939 				return (flags & RTF_HOST) ? EHOSTUNREACH
    940 							: ENETUNREACH;
    941 		}
    942 	}
    943 	memset(&info, 0, sizeof(info));
    944 	info.rti_ifa = ifa;
    945 	info.rti_flags = flags | ifa->ifa_flags;
    946 	info.rti_info[RTAX_DST] = dst;
    947 	info.rti_info[RTAX_GATEWAY] = ifa->ifa_addr;
    948 	/*
    949 	 * XXX here, it seems that we are assuming that ifa_netmask is NULL
    950 	 * for RTF_HOST.  bsdi4 passes NULL explicitly (via intermediate
    951 	 * variable) when RTF_HOST is 1.  still not sure if i can safely
    952 	 * change it to meet bsdi4 behavior.
    953 	 */
    954 	if (cmd != RTM_LLINFO_UPD)
    955 		info.rti_info[RTAX_NETMASK] = ifa->ifa_netmask;
    956 	error = rtrequest1((cmd == RTM_LLINFO_UPD) ? RTM_GET : cmd, &info,
    957 	    &nrt);
    958 	if (error != 0 || (rt = nrt) == NULL)
    959 		;
    960 	else switch (cmd) {
    961 	case RTM_DELETE:
    962 		rt_newaddrmsg(cmd, ifa, error, nrt);
    963 		if (rt->rt_refcnt <= 0) {
    964 			rt->rt_refcnt++;
    965 			rtfree(rt);
    966 		}
    967 		break;
    968 	case RTM_LLINFO_UPD:
    969 		rt->rt_refcnt--;
    970 		RT_DPRINTF("%s: updating%s\n", __func__,
    971 		    ((rt->rt_flags & RTF_LLINFO) == 0) ? " (no llinfo)" : "");
    972 
    973 		ifsdl = ifa->ifa_ifp->if_sadl;
    974 
    975 		if ((rt->rt_flags & RTF_LLINFO) != 0 &&
    976 		    (sdl = satosdl(rt->rt_gateway)) != NULL &&
    977 		    sdl->sdl_family == AF_LINK &&
    978 		    sockaddr_dl_setaddr(sdl, sdl->sdl_len, CLLADDR(ifsdl),
    979 		                        ifa->ifa_ifp->if_addrlen) == NULL) {
    980 			error = EINVAL;
    981 			break;
    982 		}
    983 
    984 		if (cmd == RTM_LLINFO_UPD && ifa->ifa_rtrequest != NULL)
    985 			ifa->ifa_rtrequest(RTM_LLINFO_UPD, rt, &info);
    986 		rt_newaddrmsg(RTM_CHANGE, ifa, error, nrt);
    987 		break;
    988 	case RTM_ADD:
    989 		rt->rt_refcnt--;
    990 		if (rt->rt_ifa != ifa) {
    991 			printf("rtinit: wrong ifa (%p) was (%p)\n", ifa,
    992 				rt->rt_ifa);
    993 			if (rt->rt_ifa->ifa_rtrequest != NULL) {
    994 				rt->rt_ifa->ifa_rtrequest(RTM_DELETE, rt,
    995 				    &info);
    996 			}
    997 			rt_replace_ifa(rt, ifa);
    998 			rt->rt_ifp = ifa->ifa_ifp;
    999 			if (ifa->ifa_rtrequest != NULL)
   1000 				ifa->ifa_rtrequest(RTM_ADD, rt, &info);
   1001 		}
   1002 		rt_newaddrmsg(cmd, ifa, error, nrt);
   1003 		break;
   1004 	}
   1005 	return error;
   1006 }
   1007 
   1008 /*
   1009  * Route timer routines.  These routes allow functions to be called
   1010  * for various routes at any time.  This is useful in supporting
   1011  * path MTU discovery and redirect route deletion.
   1012  *
   1013  * This is similar to some BSDI internal functions, but it provides
   1014  * for multiple queues for efficiency's sake...
   1015  */
   1016 
   1017 LIST_HEAD(, rttimer_queue) rttimer_queue_head;
   1018 static int rt_init_done = 0;
   1019 
   1020 #define RTTIMER_CALLOUT(r)	do {					\
   1021 		if (r->rtt_func != NULL) {				\
   1022 			(*r->rtt_func)(r->rtt_rt, r);			\
   1023 		} else {						\
   1024 			rtrequest((int) RTM_DELETE,			\
   1025 				  rt_getkey(r->rtt_rt),			\
   1026 				  0, 0, 0, 0);				\
   1027 		}							\
   1028 	} while (/*CONSTCOND*/0)
   1029 
   1030 /*
   1031  * Some subtle order problems with domain initialization mean that
   1032  * we cannot count on this being run from rt_init before various
   1033  * protocol initializations are done.  Therefore, we make sure
   1034  * that this is run when the first queue is added...
   1035  */
   1036 
   1037 void
   1038 rt_timer_init(void)
   1039 {
   1040 	assert(rt_init_done == 0);
   1041 
   1042 	LIST_INIT(&rttimer_queue_head);
   1043 	callout_init(&rt_timer_ch, 0);
   1044 	callout_reset(&rt_timer_ch, hz, rt_timer_timer, NULL);
   1045 	rt_init_done = 1;
   1046 }
   1047 
   1048 struct rttimer_queue *
   1049 rt_timer_queue_create(u_int timeout)
   1050 {
   1051 	struct rttimer_queue *rtq;
   1052 
   1053 	if (rt_init_done == 0)
   1054 		rt_timer_init();
   1055 
   1056 	R_Malloc(rtq, struct rttimer_queue *, sizeof *rtq);
   1057 	if (rtq == NULL)
   1058 		return NULL;
   1059 	memset(rtq, 0, sizeof(*rtq));
   1060 
   1061 	rtq->rtq_timeout = timeout;
   1062 	TAILQ_INIT(&rtq->rtq_head);
   1063 	LIST_INSERT_HEAD(&rttimer_queue_head, rtq, rtq_link);
   1064 
   1065 	return rtq;
   1066 }
   1067 
   1068 void
   1069 rt_timer_queue_change(struct rttimer_queue *rtq, long timeout)
   1070 {
   1071 
   1072 	rtq->rtq_timeout = timeout;
   1073 }
   1074 
   1075 void
   1076 rt_timer_queue_remove_all(struct rttimer_queue *rtq, int destroy)
   1077 {
   1078 	struct rttimer *r;
   1079 
   1080 	while ((r = TAILQ_FIRST(&rtq->rtq_head)) != NULL) {
   1081 		LIST_REMOVE(r, rtt_link);
   1082 		TAILQ_REMOVE(&rtq->rtq_head, r, rtt_next);
   1083 		if (destroy)
   1084 			RTTIMER_CALLOUT(r);
   1085 		/* we are already at splsoftnet */
   1086 		pool_put(&rttimer_pool, r);
   1087 		if (rtq->rtq_count > 0)
   1088 			rtq->rtq_count--;
   1089 		else
   1090 			printf("rt_timer_queue_remove_all: "
   1091 			    "rtq_count reached 0\n");
   1092 	}
   1093 }
   1094 
   1095 void
   1096 rt_timer_queue_destroy(struct rttimer_queue *rtq, int destroy)
   1097 {
   1098 
   1099 	rt_timer_queue_remove_all(rtq, destroy);
   1100 
   1101 	LIST_REMOVE(rtq, rtq_link);
   1102 
   1103 	/*
   1104 	 * Caller is responsible for freeing the rttimer_queue structure.
   1105 	 */
   1106 }
   1107 
   1108 unsigned long
   1109 rt_timer_count(struct rttimer_queue *rtq)
   1110 {
   1111 	return rtq->rtq_count;
   1112 }
   1113 
   1114 void
   1115 rt_timer_remove_all(struct rtentry *rt, int destroy)
   1116 {
   1117 	struct rttimer *r;
   1118 
   1119 	while ((r = LIST_FIRST(&rt->rt_timer)) != NULL) {
   1120 		LIST_REMOVE(r, rtt_link);
   1121 		TAILQ_REMOVE(&r->rtt_queue->rtq_head, r, rtt_next);
   1122 		if (destroy)
   1123 			RTTIMER_CALLOUT(r);
   1124 		if (r->rtt_queue->rtq_count > 0)
   1125 			r->rtt_queue->rtq_count--;
   1126 		else
   1127 			printf("rt_timer_remove_all: rtq_count reached 0\n");
   1128 		/* we are already at splsoftnet */
   1129 		pool_put(&rttimer_pool, r);
   1130 	}
   1131 }
   1132 
   1133 int
   1134 rt_timer_add(struct rtentry *rt,
   1135 	void (*func)(struct rtentry *, struct rttimer *),
   1136 	struct rttimer_queue *queue)
   1137 {
   1138 	struct rttimer *r;
   1139 	int s;
   1140 
   1141 	/*
   1142 	 * If there's already a timer with this action, destroy it before
   1143 	 * we add a new one.
   1144 	 */
   1145 	LIST_FOREACH(r, &rt->rt_timer, rtt_link) {
   1146 		if (r->rtt_func == func)
   1147 			break;
   1148 	}
   1149 	if (r != NULL) {
   1150 		LIST_REMOVE(r, rtt_link);
   1151 		TAILQ_REMOVE(&r->rtt_queue->rtq_head, r, rtt_next);
   1152 		if (r->rtt_queue->rtq_count > 0)
   1153 			r->rtt_queue->rtq_count--;
   1154 		else
   1155 			printf("rt_timer_add: rtq_count reached 0\n");
   1156 	} else {
   1157 		s = splsoftnet();
   1158 		r = pool_get(&rttimer_pool, PR_NOWAIT);
   1159 		splx(s);
   1160 		if (r == NULL)
   1161 			return ENOBUFS;
   1162 	}
   1163 
   1164 	memset(r, 0, sizeof(*r));
   1165 
   1166 	r->rtt_rt = rt;
   1167 	r->rtt_time = time_uptime;
   1168 	r->rtt_func = func;
   1169 	r->rtt_queue = queue;
   1170 	LIST_INSERT_HEAD(&rt->rt_timer, r, rtt_link);
   1171 	TAILQ_INSERT_TAIL(&queue->rtq_head, r, rtt_next);
   1172 	r->rtt_queue->rtq_count++;
   1173 
   1174 	return 0;
   1175 }
   1176 
   1177 /* ARGSUSED */
   1178 void
   1179 rt_timer_timer(void *arg)
   1180 {
   1181 	struct rttimer_queue *rtq;
   1182 	struct rttimer *r;
   1183 	int s;
   1184 
   1185 	s = splsoftnet();
   1186 	LIST_FOREACH(rtq, &rttimer_queue_head, rtq_link) {
   1187 		while ((r = TAILQ_FIRST(&rtq->rtq_head)) != NULL &&
   1188 		    (r->rtt_time + rtq->rtq_timeout) < time_uptime) {
   1189 			LIST_REMOVE(r, rtt_link);
   1190 			TAILQ_REMOVE(&rtq->rtq_head, r, rtt_next);
   1191 			RTTIMER_CALLOUT(r);
   1192 			pool_put(&rttimer_pool, r);
   1193 			if (rtq->rtq_count > 0)
   1194 				rtq->rtq_count--;
   1195 			else
   1196 				printf("rt_timer_timer: rtq_count reached 0\n");
   1197 		}
   1198 	}
   1199 	splx(s);
   1200 
   1201 	callout_reset(&rt_timer_ch, hz, rt_timer_timer, NULL);
   1202 }
   1203 
   1204 static struct rtentry *
   1205 _rtcache_init(struct route *ro, int flag)
   1206 {
   1207 	rtcache_invariants(ro);
   1208 	KASSERT(ro->_ro_rt == NULL);
   1209 
   1210 	if (rtcache_getdst(ro) == NULL)
   1211 		return NULL;
   1212 	ro->ro_invalid = false;
   1213 	if ((ro->_ro_rt = rtalloc1(rtcache_getdst(ro), flag)) != NULL)
   1214 		rtcache(ro);
   1215 
   1216 	rtcache_invariants(ro);
   1217 	return ro->_ro_rt;
   1218 }
   1219 
   1220 struct rtentry *
   1221 rtcache_init(struct route *ro)
   1222 {
   1223 	return _rtcache_init(ro, 1);
   1224 }
   1225 
   1226 struct rtentry *
   1227 rtcache_init_noclone(struct route *ro)
   1228 {
   1229 	return _rtcache_init(ro, 0);
   1230 }
   1231 
   1232 struct rtentry *
   1233 rtcache_update(struct route *ro, int clone)
   1234 {
   1235 	rtcache_clear(ro);
   1236 	return _rtcache_init(ro, clone);
   1237 }
   1238 
   1239 void
   1240 rtcache_copy(struct route *new_ro, const struct route *old_ro)
   1241 {
   1242 	struct rtentry *rt;
   1243 
   1244 	KASSERT(new_ro != old_ro);
   1245 	rtcache_invariants(new_ro);
   1246 	rtcache_invariants(old_ro);
   1247 
   1248 	if ((rt = rtcache_validate(old_ro)) != NULL)
   1249 		rt->rt_refcnt++;
   1250 
   1251 	if (rtcache_getdst(old_ro) == NULL ||
   1252 	    rtcache_setdst(new_ro, rtcache_getdst(old_ro)) != 0)
   1253 		return;
   1254 
   1255 	new_ro->ro_invalid = false;
   1256 	if ((new_ro->_ro_rt = rt) != NULL)
   1257 		rtcache(new_ro);
   1258 	rtcache_invariants(new_ro);
   1259 }
   1260 
   1261 static struct dom_rtlist invalid_routes = LIST_HEAD_INITIALIZER(dom_rtlist);
   1262 
   1263 void
   1264 rtcache_invalidate(struct dom_rtlist *rtlist)
   1265 {
   1266 	struct route *ro;
   1267 
   1268 	while ((ro = LIST_FIRST(rtlist)) != NULL) {
   1269 		rtcache_invariants(ro);
   1270 		KASSERT(ro->_ro_rt != NULL);
   1271 		ro->ro_invalid = true;
   1272 		LIST_REMOVE(ro, ro_rtcache_next);
   1273 		LIST_INSERT_HEAD(&invalid_routes, ro, ro_rtcache_next);
   1274 		rtcache_invariants(ro);
   1275 	}
   1276 }
   1277 
   1278 void
   1279 rtcache_clear(struct route *ro)
   1280 {
   1281 	rtcache_invariants(ro);
   1282 	if (ro->_ro_rt == NULL)
   1283 		return;
   1284 
   1285 	LIST_REMOVE(ro, ro_rtcache_next);
   1286 
   1287 	rtfree(ro->_ro_rt);
   1288 	ro->_ro_rt = NULL;
   1289 	ro->ro_invalid = false;
   1290 	rtcache_invariants(ro);
   1291 }
   1292 
   1293 struct rtentry *
   1294 rtcache_lookup2(struct route *ro, const struct sockaddr *dst, int clone,
   1295     int *hitp)
   1296 {
   1297 	const struct sockaddr *odst;
   1298 	struct rtentry *rt = NULL;
   1299 
   1300 	rtcache_invariants(ro);
   1301 
   1302 	odst = rtcache_getdst(ro);
   1303 
   1304 	if (odst == NULL)
   1305 		;
   1306 	else if (sockaddr_cmp(odst, dst) != 0)
   1307 		rtcache_free(ro);
   1308 	else if ((rt = rtcache_validate(ro)) == NULL)
   1309 		rtcache_clear(ro);
   1310 
   1311 	if (rt == NULL) {
   1312 		*hitp = 0;
   1313 		if (rtcache_setdst(ro, dst) == 0)
   1314 			rt = _rtcache_init(ro, clone);
   1315 	} else
   1316 		*hitp = 1;
   1317 
   1318 	rtcache_invariants(ro);
   1319 
   1320 	return rt;
   1321 }
   1322 
   1323 void
   1324 rtcache_free(struct route *ro)
   1325 {
   1326 	rtcache_clear(ro);
   1327 	if (ro->ro_sa != NULL) {
   1328 		sockaddr_free(ro->ro_sa);
   1329 		ro->ro_sa = NULL;
   1330 	}
   1331 	rtcache_invariants(ro);
   1332 }
   1333 
   1334 int
   1335 rtcache_setdst(struct route *ro, const struct sockaddr *sa)
   1336 {
   1337 	KASSERT(sa != NULL);
   1338 
   1339 	rtcache_invariants(ro);
   1340 	if (ro->ro_sa != NULL && ro->ro_sa->sa_family == sa->sa_family) {
   1341 		rtcache_clear(ro);
   1342 		if (sockaddr_copy(ro->ro_sa, ro->ro_sa->sa_len, sa) != NULL) {
   1343 			rtcache_invariants(ro);
   1344 			return 0;
   1345 		}
   1346 		sockaddr_free(ro->ro_sa);
   1347 	} else if (ro->ro_sa != NULL)
   1348 		rtcache_free(ro);	/* free ro_sa, wrong family */
   1349 
   1350 	KASSERT(ro->_ro_rt == NULL);
   1351 
   1352 	if ((ro->ro_sa = sockaddr_dup(sa, M_NOWAIT)) == NULL) {
   1353 		rtcache_invariants(ro);
   1354 		return ENOMEM;
   1355 	}
   1356 	rtcache_invariants(ro);
   1357 	return 0;
   1358 }
   1359 
   1360 const struct sockaddr *
   1361 rt_settag(struct rtentry *rt, const struct sockaddr *tag)
   1362 {
   1363 	if (rt->rt_tag != tag) {
   1364 		if (rt->rt_tag != NULL)
   1365 			sockaddr_free(rt->rt_tag);
   1366 		rt->rt_tag = sockaddr_dup(tag, M_NOWAIT);
   1367 	}
   1368 	return rt->rt_tag;
   1369 }
   1370 
   1371 struct sockaddr *
   1372 rt_gettag(struct rtentry *rt)
   1373 {
   1374 	return rt->rt_tag;
   1375 }
   1376