]>
git.saurik.com Git - apple/xnu.git/blob - bsd/netinet6/in6_rmx.c
34f2fd32029c3675282feb319ab8c6658dd9fcae
2 * Copyright (c) 2003-2008 Apple Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
29 /* $FreeBSD: src/sys/netinet6/in6_rmx.c,v 1.1.2.2 2001/07/03 11:01:52 ume Exp $ */
30 /* $KAME: in6_rmx.c,v 1.10 2001/05/24 05:44:58 itojun Exp $ */
33 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
34 * All rights reserved.
36 * Redistribution and use in source and binary forms, with or without
37 * modification, are permitted provided that the following conditions
39 * 1. Redistributions of source code must retain the above copyright
40 * notice, this list of conditions and the following disclaimer.
41 * 2. Redistributions in binary form must reproduce the above copyright
42 * notice, this list of conditions and the following disclaimer in the
43 * documentation and/or other materials provided with the distribution.
44 * 3. Neither the name of the project nor the names of its contributors
45 * may be used to endorse or promote products derived from this software
46 * without specific prior written permission.
48 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
49 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
50 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
51 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
52 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
56 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
57 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 * Copyright 1994, 1995 Massachusetts Institute of Technology
64 * Permission to use, copy, modify, and distribute this software and
65 * its documentation for any purpose and without fee is hereby
66 * granted, provided that both the above copyright notice and this
67 * permission notice appear in all copies, that both the above
68 * copyright notice and this permission notice appear in all
69 * supporting documentation, and that the name of M.I.T. not be used
70 * in advertising or publicity pertaining to distribution of the
71 * software without specific, written prior permission. M.I.T. makes
72 * no representations about the suitability of this software for any
73 * purpose. It is provided "as is" without express or implied
76 * THIS SOFTWARE IS PROVIDED BY M.I.T. ``AS IS''. M.I.T. DISCLAIMS
77 * ALL EXPRESS OR IMPLIED WARRANTIES WITH REGARD TO THIS SOFTWARE,
78 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
79 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT
80 * SHALL M.I.T. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
81 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
82 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
83 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
84 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
85 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
86 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
92 * This code does two things necessary for the enhanced TCP metrics to
93 * function in a useful manner:
94 * 1) It marks all non-host routes as `cloning', thus ensuring that
95 * every actual reference to such a route actually gets turned
96 * into a reference to a host route to the specific destination
98 * 2) When such routes lose all their references, it arranges for them
99 * to be deleted in some random collection of circumstances, so that
100 * a large quantity of stale routing data is not kept in kernel memory
101 * indefinitely. See in6_rtqtimo() below for the exact mechanism.
104 #include <sys/param.h>
105 #include <sys/systm.h>
106 #include <sys/kernel.h>
107 #include <sys/sysctl.h>
108 #include <kern/queue.h>
109 #include <sys/socket.h>
110 #include <sys/socketvar.h>
111 #include <sys/mbuf.h>
112 #include <sys/syslog.h>
113 #include <kern/lock.h>
116 #include <net/route.h>
117 #include <netinet/in.h>
118 #include <netinet/ip_var.h>
119 #include <netinet/in_var.h>
121 #include <netinet/ip6.h>
122 #include <netinet6/ip6_var.h>
124 #include <netinet/icmp6.h>
126 #include <netinet/tcp.h>
127 #include <netinet/tcp_seq.h>
128 #include <netinet/tcp_timer.h>
129 #include <netinet/tcp_var.h>
131 extern int in6_inithead(void **head
, int off
);
132 static void in6_rtqtimo(void *rock
);
133 static void in6_mtutimo(void *rock
);
134 extern int tvtohz(struct timeval
*);
136 static struct radix_node
*in6_matroute_args(void *, struct radix_node_head
*,
137 rn_matchf_t
*, void *);
139 #define RTPRF_OURS RTF_PROTO3 /* set on routes we manage */
142 * Accessed by in6_addroute(), in6_deleteroute() and in6_rtqkill(), during
143 * which the routing lock (rnh_lock) is held and thus protects the variable.
145 static int in6dynroutes
;
148 * Do what we need to do when inserting a route.
150 static struct radix_node
*
151 in6_addroute(void *v_arg
, void *n_arg
, struct radix_node_head
*head
,
152 struct radix_node
*treenodes
)
154 struct rtentry
*rt
= (struct rtentry
*)treenodes
;
155 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)rt_key(rt
);
156 struct radix_node
*ret
;
158 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
159 RT_LOCK_ASSERT_HELD(rt
);
162 * If this is a dynamic route (which is created via Redirect) and
163 * we already have the maximum acceptable number of such route entries,
164 * reject creating a new one. We could initiate garbage collection to
165 * make available space right now, but the benefit would probably not
166 * be worth the cleaning overhead; we only have to endure a slightly
167 * suboptimal path even without the redirecbted route.
169 if ((rt
->rt_flags
& RTF_DYNAMIC
) != 0 &&
170 ip6_maxdynroutes
>= 0 && in6dynroutes
>= ip6_maxdynroutes
)
174 * For IPv6, all unicast non-host routes are automatically cloning.
176 if (IN6_IS_ADDR_MULTICAST(&sin6
->sin6_addr
))
177 rt
->rt_flags
|= RTF_MULTICAST
;
179 if (!(rt
->rt_flags
& (RTF_HOST
| RTF_CLONING
| RTF_MULTICAST
))) {
180 rt
->rt_flags
|= RTF_PRCLONING
;
184 * A little bit of help for both IPv6 output and input:
185 * For local addresses, we make sure that RTF_LOCAL is set,
186 * with the thought that this might one day be used to speed up
189 * We also mark routes to multicast addresses as such, because
190 * it's easy to do and might be useful (but this is much more
191 * dubious since it's so easy to inspect the address). (This
195 * should elaborate the code.
197 if (rt
->rt_flags
& RTF_HOST
) {
198 if (IN6_ARE_ADDR_EQUAL(&satosin6(rt
->rt_ifa
->ifa_addr
)
201 rt
->rt_flags
|= RTF_LOCAL
;
205 if (!rt
->rt_rmx
.rmx_mtu
&& !(rt
->rt_rmx
.rmx_locks
& RTV_MTU
)
207 rt
->rt_rmx
.rmx_mtu
= rt
->rt_ifp
->if_mtu
;
209 ret
= rn_addroute(v_arg
, n_arg
, head
, treenodes
);
210 if (ret
== NULL
&& (rt
->rt_flags
& RTF_HOST
)) {
213 * We are trying to add a host route, but can't.
214 * Find out if it is because of an
215 * ARP entry and delete it if so.
217 rt2
= rtalloc1_locked((struct sockaddr
*)sin6
, 0,
218 RTF_CLONING
| RTF_PRCLONING
);
221 if ((rt2
->rt_flags
& RTF_LLINFO
) &&
222 (rt2
->rt_flags
& RTF_HOST
) &&
223 rt2
->rt_gateway
!= NULL
&&
224 rt2
->rt_gateway
->sa_family
== AF_LINK
) {
226 * Safe to drop rt_lock and use rt_key,
227 * rt_gateway, since holding rnh_lock here
228 * prevents another thread from calling
229 * rt_setgate() on this route.
232 (void) rtrequest_locked(RTM_DELETE
, rt_key(rt2
),
233 rt2
->rt_gateway
, rt_mask(rt2
),
235 ret
= rn_addroute(v_arg
, n_arg
, head
,
242 } else if (ret
== NULL
&& (rt
->rt_flags
& RTF_CLONING
)) {
245 * We are trying to add a net route, but can't.
246 * The following case should be allowed, so we'll make a
247 * special check for this:
248 * Two IPv6 addresses with the same prefix is assigned
249 * to a single interrface.
250 * # ifconfig if0 inet6 3ffe:0501::1 prefix 64 alias (*1)
251 * # ifconfig if0 inet6 3ffe:0501::2 prefix 64 alias (*2)
252 * In this case, (*1) and (*2) want to add the same
253 * net route entry, 3ffe:0501:: -> if0.
254 * This case should not raise an error.
256 rt2
= rtalloc1_locked((struct sockaddr
*)sin6
, 0,
257 RTF_CLONING
| RTF_PRCLONING
);
260 if ((rt2
->rt_flags
& (RTF_CLONING
|RTF_HOST
|RTF_GATEWAY
))
263 && rt2
->rt_gateway
->sa_family
== AF_LINK
264 && rt2
->rt_ifp
== rt
->rt_ifp
) {
272 if (ret
!= NULL
&& (rt
->rt_flags
& RTF_DYNAMIC
) != 0)
278 static struct radix_node
*
279 in6_deleteroute(void * v_arg
, void *netmask_arg
, struct radix_node_head
*head
)
281 struct radix_node
*rn
;
283 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
285 rn
= rn_delete(v_arg
, netmask_arg
, head
);
287 struct rtentry
*rt
= (struct rtentry
*)rn
;
289 if ((rt
->rt_flags
& RTF_DYNAMIC
) != 0)
298 * Similar to in6_matroute_args except without the leaf-matching parameters.
300 static struct radix_node
*
301 in6_matroute(void *v_arg
, struct radix_node_head
*head
)
303 return (in6_matroute_args(v_arg
, head
, NULL
, NULL
));
307 * This code is the inverse of in6_clsroute: on first reference, if we
308 * were managing the route, stop doing so and set the expiration timer
311 static struct radix_node
*
312 in6_matroute_args(void *v_arg
, struct radix_node_head
*head
,
313 rn_matchf_t
*f
, void *w
)
315 struct radix_node
*rn
= rn_match_args(v_arg
, head
, f
, w
);
316 struct rtentry
*rt
= (struct rtentry
*)rn
;
318 /* This is first reference? */
321 if (rt
->rt_refcnt
== 0 && (rt
->rt_flags
& RTPRF_OURS
)) {
322 rt
->rt_flags
&= ~RTPRF_OURS
;
323 rt
->rt_rmx
.rmx_expire
= 0;
330 SYSCTL_DECL(_net_inet6_ip6
);
332 static int rtq_reallyold
= 60*60;
333 /* one hour is ``really old'' */
334 SYSCTL_INT(_net_inet6_ip6
, IPV6CTL_RTEXPIRE
, rtexpire
,
335 CTLFLAG_RW
, &rtq_reallyold
, 0, "");
337 static int rtq_minreallyold
= 10;
338 /* never automatically crank down to less */
339 SYSCTL_INT(_net_inet6_ip6
, IPV6CTL_RTMINEXPIRE
, rtminexpire
,
340 CTLFLAG_RW
, &rtq_minreallyold
, 0, "");
342 static int rtq_toomany
= 128;
343 /* 128 cached routes is ``too many'' */
344 SYSCTL_INT(_net_inet6_ip6
, IPV6CTL_RTMAXCACHE
, rtmaxcache
,
345 CTLFLAG_RW
, &rtq_toomany
, 0, "");
349 * On last reference drop, mark the route as belong to us so that it can be
353 in6_clsroute(struct radix_node
*rn
, __unused
struct radix_node_head
*head
)
355 struct rtentry
*rt
= (struct rtentry
*)rn
;
357 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
358 RT_LOCK_ASSERT_HELD(rt
);
360 if (!(rt
->rt_flags
& RTF_UP
))
361 return; /* prophylactic measures */
363 if ((rt
->rt_flags
& (RTF_LLINFO
| RTF_HOST
)) != RTF_HOST
)
366 if (rt
->rt_flags
& RTPRF_OURS
)
369 if (!(rt
->rt_flags
& (RTF_WASCLONED
| RTF_DYNAMIC
)))
373 * Delete the route immediately if RTF_DELCLONE is set or
374 * if route caching is disabled (rtq_reallyold set to 0).
375 * Otherwise, let it expire and be deleted by in6_rtqkill().
377 if ((rt
->rt_flags
& RTF_DELCLONE
) || rtq_reallyold
== 0) {
379 * Delete the route from the radix tree but since we are
380 * called when the route's reference count is 0, don't
381 * deallocate it until we return from this routine by
382 * telling rtrequest that we're interested in it.
383 * Safe to drop rt_lock and use rt_key, rt_gateway,
384 * since holding rnh_lock here prevents another thread
385 * from calling rt_setgate() on this route.
388 if (rtrequest_locked(RTM_DELETE
, rt_key(rt
),
389 rt
->rt_gateway
, rt_mask(rt
), rt
->rt_flags
, &rt
) == 0) {
390 /* Now let the caller free it */
392 RT_REMREF_LOCKED(rt
);
397 struct timeval timenow
;
399 getmicrotime(&timenow
);
400 rt
->rt_flags
|= RTPRF_OURS
;
401 rt
->rt_rmx
.rmx_expire
= timenow
.tv_sec
+ rtq_reallyold
;
406 struct radix_node_head
*rnh
;
416 * Get rid of old routes. When draining, this deletes everything, even when
417 * the timeout is not expired yet. This also applies if the route is dynamic
418 * and there are sufficiently large number of such routes (more than a half of
419 * maximum). When updating, this makes sure that nothing has a timeout longer
420 * than the current value of rtq_reallyold.
423 in6_rtqkill(struct radix_node
*rn
, void *rock
)
425 struct rtqk_arg
*ap
= rock
;
426 struct rtentry
*rt
= (struct rtentry
*)rn
;
428 struct timeval timenow
;
430 getmicrotime(&timenow
);
431 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
434 if (rt
->rt_flags
& RTPRF_OURS
) {
437 if (ap
->draining
|| rt
->rt_rmx
.rmx_expire
<= timenow
.tv_sec
||
438 ((rt
->rt_flags
& RTF_DYNAMIC
) != 0 &&
439 ip6_maxdynroutes
>= 0 &&
440 in6dynroutes
> ip6_maxdynroutes
/ 2)) {
441 if (rt
->rt_refcnt
> 0)
442 panic("rtqkill route really not free");
445 * Delete this route since we're done with it;
446 * the route may be freed afterwards, so we
447 * can no longer refer to 'rt' upon returning
448 * from rtrequest(). Safe to drop rt_lock and
449 * use rt_key, rt_gateway, since holding rnh_lock
450 * here prevents another thread from calling
451 * rt_setgate() on this route.
454 err
= rtrequest_locked(RTM_DELETE
, rt_key(rt
),
455 rt
->rt_gateway
, rt_mask(rt
), rt
->rt_flags
, 0);
457 log(LOG_WARNING
, "in6_rtqkill: error %d", err
);
463 && (rt
->rt_rmx
.rmx_expire
- timenow
.tv_sec
465 rt
->rt_rmx
.rmx_expire
= timenow
.tv_sec
468 ap
->nextstop
= lmin(ap
->nextstop
,
469 rt
->rt_rmx
.rmx_expire
);
479 #define RTQ_TIMEOUT 60*10 /* run no less than once every ten minutes */
480 static int rtq_timeout
= RTQ_TIMEOUT
;
483 in6_rtqtimo(void *rock
)
485 struct radix_node_head
*rnh
= rock
;
488 static time_t last_adjusted_timeout
= 0;
489 struct timeval timenow
;
491 lck_mtx_lock(rnh_lock
);
492 /* Get the timestamp after we acquire the lock for better accuracy */
493 getmicrotime(&timenow
);
495 arg
.found
= arg
.killed
= 0;
497 arg
.nextstop
= timenow
.tv_sec
+ rtq_timeout
;
498 arg
.draining
= arg
.updating
= 0;
499 rnh
->rnh_walktree(rnh
, in6_rtqkill
, &arg
);
502 * Attempt to be somewhat dynamic about this:
503 * If there are ``too many'' routes sitting around taking up space,
504 * then crank down the timeout, and see if we can't make some more
505 * go away. However, we make sure that we will never adjust more
506 * than once in rtq_timeout seconds, to keep from cranking down too
509 if ((arg
.found
- arg
.killed
> rtq_toomany
)
510 && (timenow
.tv_sec
- last_adjusted_timeout
>= rtq_timeout
)
511 && rtq_reallyold
> rtq_minreallyold
) {
512 rtq_reallyold
= 2*rtq_reallyold
/ 3;
513 if (rtq_reallyold
< rtq_minreallyold
) {
514 rtq_reallyold
= rtq_minreallyold
;
517 last_adjusted_timeout
= timenow
.tv_sec
;
519 log(LOG_DEBUG
, "in6_rtqtimo: adjusted rtq_reallyold to %d",
522 arg
.found
= arg
.killed
= 0;
524 rnh
->rnh_walktree(rnh
, in6_rtqkill
, &arg
);
528 atv
.tv_sec
= arg
.nextstop
- timenow
.tv_sec
;
529 lck_mtx_unlock(rnh_lock
);
530 timeout(in6_rtqtimo
, rock
, tvtohz(&atv
));
537 struct radix_node_head
*rnh
;
542 in6_mtuexpire(struct radix_node
*rn
, void *rock
)
544 struct rtentry
*rt
= (struct rtentry
*)rn
;
545 struct mtuex_arg
*ap
= rock
;
546 struct timeval timenow
;
548 getmicrotime(&timenow
);
552 panic("rt == NULL in in6_mtuexpire");
555 if (rt
->rt_rmx
.rmx_expire
&& !(rt
->rt_flags
& RTF_PROBEMTU
)) {
556 if (rt
->rt_rmx
.rmx_expire
<= timenow
.tv_sec
) {
557 rt
->rt_flags
|= RTF_PROBEMTU
;
559 ap
->nextstop
= lmin(ap
->nextstop
,
560 rt
->rt_rmx
.rmx_expire
);
568 #define MTUTIMO_DEFAULT (60*1)
571 in6_mtutimo(void *rock
)
573 struct radix_node_head
*rnh
= rock
;
574 struct mtuex_arg arg
;
576 struct timeval timenow
;
578 getmicrotime(&timenow
);
581 arg
.nextstop
= timenow
.tv_sec
+ MTUTIMO_DEFAULT
;
582 lck_mtx_lock(rnh_lock
);
583 rnh
->rnh_walktree(rnh
, in6_mtuexpire
, &arg
);
586 atv
.tv_sec
= arg
.nextstop
;
587 if (atv
.tv_sec
< timenow
.tv_sec
) {
589 log(LOG_DEBUG
, "IPv6: invalid mtu expiration time on routing table\n");
591 arg
.nextstop
= timenow
.tv_sec
+ 30; /*last resort*/
593 atv
.tv_sec
-= timenow
.tv_sec
;
594 lck_mtx_unlock(rnh_lock
);
595 timeout(in6_mtutimo
, rock
, tvtohz(&atv
));
602 struct radix_node_head
*rnh
= rt_tables
[AF_INET6
];
605 arg
.found
= arg
.killed
= 0;
611 rnh
->rnh_walktree(rnh
, in6_rtqkill
, &arg
);
617 * Initialize our routing tree.
620 in6_inithead(void **head
, int off
)
622 struct radix_node_head
*rnh
;
624 if (!rn_inithead(head
, off
))
627 if (head
!= (void **)&rt_tables
[AF_INET6
]) /* BOGUS! */
628 return 1; /* only do this for the real routing table */
631 rnh
->rnh_addaddr
= in6_addroute
;
632 rnh
->rnh_deladdr
= in6_deleteroute
;
633 rnh
->rnh_matchaddr
= in6_matroute
;
634 rnh
->rnh_matchaddr_args
= in6_matroute_args
;
635 rnh
->rnh_close
= in6_clsroute
;
636 in6_rtqtimo(rnh
); /* kick off timeout first time */
637 in6_mtutimo(rnh
); /* kick off timeout first time */