2 * Copyright (c) 2000-2009 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 * Copyright (c) 1980, 1986, 1991, 1993
30 * The Regents of the University of California. All rights reserved.
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
35 * 1. Redistributions of source code must retain the above copyright
36 * notice, this list of conditions and the following disclaimer.
37 * 2. Redistributions in binary form must reproduce the above copyright
38 * notice, this list of conditions and the following disclaimer in the
39 * documentation and/or other materials provided with the distribution.
40 * 3. All advertising materials mentioning features or use of this software
41 * must display the following acknowledgement:
42 * This product includes software developed by the University of
43 * California, Berkeley and its contributors.
44 * 4. Neither the name of the University 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 REGENTS 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 REGENTS 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
60 * @(#)route.c 8.2 (Berkeley) 11/15/93
61 * $FreeBSD: src/sys/net/route.c,v 1.59.2.3 2001/07/29 19:18:02 ume Exp $
64 #include <sys/param.h>
65 #include <sys/sysctl.h>
66 #include <sys/systm.h>
67 #include <sys/malloc.h>
69 #include <sys/socket.h>
70 #include <sys/domain.h>
71 #include <sys/syslog.h>
72 #include <sys/queue.h>
73 #include <kern/lock.h>
74 #include <kern/zalloc.h>
77 #include <net/route.h>
79 #include <netinet/in.h>
80 #include <netinet/in_var.h>
81 #include <netinet/ip_mroute.h>
82 #include <netinet/ip_var.h>
84 #include <net/if_dl.h>
86 #include <libkern/OSAtomic.h>
87 #include <libkern/OSDebug.h>
89 #include <pexpert/pexpert.h>
92 * Synchronization notes:
94 * Routing entries fall under two locking domains: the global routing table
95 * lock (rnh_lock) and the per-entry lock (rt_lock); the latter is a mutex that
96 * resides (statically defined) in the rtentry structure.
98 * The locking domains for routing are defined as follows:
100 * The global routing lock is used to serialize all accesses to the radix
101 * trees defined by rt_tables[], as well as the tree of masks. This includes
102 * lookups, insertions and removals of nodes to/from the respective tree.
103 * It is also used to protect certain fields in the route entry that aren't
104 * often modified and/or require global serialization (more details below.)
106 * The per-route entry lock is used to serialize accesses to several routing
107 * entry fields (more details below.) Acquiring and releasing this lock is
108 * done via RT_LOCK() and RT_UNLOCK() routines.
110 * In cases where both rnh_lock and rt_lock must be held, the former must be
111 * acquired first in order to maintain lock ordering. It is not a requirement
112 * that rnh_lock be acquired first before rt_lock, but in case both must be
113 * acquired in succession, the correct lock ordering must be followed.
115 * The fields of the rtentry structure are protected in the following way:
119 * - Routing table lock (rnh_lock).
121 * rt_parent, rt_mask, rt_llinfo_free
123 * - Set once during creation and never changes; no locks to read.
125 * rt_flags, rt_genmask, rt_llinfo, rt_rmx, rt_refcnt, rt_gwroute
127 * - Routing entry lock (rt_lock) for read/write access.
129 * - Some values of rt_flags are either set once at creation time,
130 * or aren't currently used, and thus checking against them can
131 * be done without rt_lock: RTF_GATEWAY, RTF_HOST, RTF_DYNAMIC,
132 * RTF_DONE, RTF_XRESOLVE, RTF_STATIC, RTF_BLACKHOLE, RTF_ANNOUNCE,
133 * RTF_USETRAILERS, RTF_WASCLONED, RTF_PINNED, RTF_LOCAL,
134 * RTF_BROADCAST, RTF_MULTICAST, RTF_IFSCOPE, RTF_IFREF.
136 * rt_key, rt_gateway, rt_ifp, rt_ifa
138 * - Always written/modified with both rnh_lock and rt_lock held.
140 * - May be read freely with rnh_lock held, else must hold rt_lock
141 * for read access; holding both locks for read is also okay.
143 * - In the event rnh_lock is not acquired, or is not possible to be
144 * acquired across the operation, setting RTF_CONDEMNED on a route
145 * entry will prevent its rt_key, rt_gateway, rt_ifp and rt_ifa
146 * from being modified. This is typically done on a route that
147 * has been chosen for a removal (from the tree) prior to dropping
148 * the rt_lock, so that those values will remain the same until
149 * the route is freed.
151 * When rnh_lock is held rt_setgate(), rt_setif(), and rtsetifa() are
152 * single-threaded, thus exclusive. This flag will also prevent the
153 * route from being looked up via rt_lookup().
157 * - Assumes that 32-bit writes are atomic; no locks.
161 * - Currently unused; no locks.
163 * Operations on a route entry can be described as follows:
165 * CREATE an entry with reference count set to 0 as part of RTM_ADD/RESOLVE.
167 * INSERTION of an entry into the radix tree holds the rnh_lock, checks
168 * for duplicates and then adds the entry. rtrequest returns the entry
169 * after bumping up the reference count to 1 (for the caller).
171 * LOOKUP of an entry holds the rnh_lock and bumps up the reference count
172 * before returning; it is valid to also bump up the reference count using
173 * RT_ADDREF after the lookup has returned an entry.
175 * REMOVAL of an entry from the radix tree holds the rnh_lock, removes the
176 * entry but does not decrement the reference count. Removal happens when
177 * the route is explicitly deleted (RTM_DELETE) or when it is in the cached
178 * state and it expires. The route is said to be "down" when it is no
179 * longer present in the tree. Freeing the entry will happen on the last
180 * reference release of such a "down" route.
182 * RT_ADDREF/RT_REMREF operates on the routing entry which increments/
183 * decrements the reference count, rt_refcnt, atomically on the rtentry.
184 * rt_refcnt is modified only using this routine. The general rule is to
185 * do RT_ADDREF in the function that is passing the entry as an argument,
186 * in order to prevent the entry from being freed by the callee.
189 #define equal(a1, a2) (bcmp((caddr_t)(a1), (caddr_t)(a2), (a1)->sa_len) == 0)
190 #define SA(p) ((struct sockaddr *)(p))
192 extern void kdp_set_gateway_mac (void *gatewaymac
);
194 extern struct domain routedomain
;
195 struct route_cb route_cb
;
196 __private_extern__
struct rtstat rtstat
= { 0, 0, 0, 0, 0 };
197 struct radix_node_head
*rt_tables
[AF_MAX
+1];
199 lck_mtx_t
*rnh_lock
; /* global routing tables mutex */
200 static lck_attr_t
*rnh_lock_attr
;
201 static lck_grp_t
*rnh_lock_grp
;
202 static lck_grp_attr_t
*rnh_lock_grp_attr
;
204 /* Lock group and attribute for routing entry locks */
205 static lck_attr_t
*rte_mtx_attr
;
206 static lck_grp_t
*rte_mtx_grp
;
207 static lck_grp_attr_t
*rte_mtx_grp_attr
;
209 lck_mtx_t
*route_domain_mtx
; /*### global routing tables mutex for now */
210 int rttrash
= 0; /* routes not in table but not freed */
212 unsigned int rte_debug
;
214 /* Possible flags for rte_debug */
215 #define RTD_DEBUG 0x1 /* enable or disable rtentry debug facility */
216 #define RTD_TRACE 0x2 /* trace alloc, free, refcnt and lock */
217 #define RTD_NO_FREE 0x4 /* don't free (good to catch corruptions) */
219 #define RTE_NAME "rtentry" /* name for zone and rt_lock */
221 static struct zone
*rte_zone
; /* special zone for rtentry */
222 #define RTE_ZONE_MAX 65536 /* maximum elements in zone */
223 #define RTE_ZONE_NAME RTE_NAME /* name of rtentry zone */
225 #define RTD_INUSE 0xFEEDFACE /* entry is in use */
226 #define RTD_FREED 0xDEADBEEF /* entry is freed */
229 __private_extern__
unsigned int ctrace_stack_size
= CTRACE_STACK_SIZE
;
230 __private_extern__
unsigned int ctrace_hist_size
= CTRACE_HIST_SIZE
;
233 * Debug variant of rtentry structure.
236 struct rtentry rtd_entry
; /* rtentry */
237 struct rtentry rtd_entry_saved
; /* saved rtentry */
238 uint32_t rtd_inuse
; /* in use pattern */
239 uint16_t rtd_refhold_cnt
; /* # of rtref */
240 uint16_t rtd_refrele_cnt
; /* # of rtunref */
241 uint32_t rtd_lock_cnt
; /* # of locks */
242 uint32_t rtd_unlock_cnt
; /* # of unlocks */
244 * Alloc and free callers.
249 * Circular lists of rtref and rtunref callers.
251 ctrace_t rtd_refhold
[CTRACE_HIST_SIZE
];
252 ctrace_t rtd_refrele
[CTRACE_HIST_SIZE
];
254 * Circular lists of locks and unlocks.
256 ctrace_t rtd_lock
[CTRACE_HIST_SIZE
];
257 ctrace_t rtd_unlock
[CTRACE_HIST_SIZE
];
261 TAILQ_ENTRY(rtentry_dbg
) rtd_trash_link
;
264 #define atomic_add_16_ov(a, n) \
265 ((uint16_t) OSAddAtomic16(n, (volatile SInt16 *)a))
266 #define atomic_add_32_ov(a, n) \
267 ((uint32_t) OSAddAtomic(n, a))
269 /* List of trash route entries protected by rnh_lock */
270 static TAILQ_HEAD(, rtentry_dbg
) rttrash_head
;
272 static void rte_lock_init(struct rtentry
*);
273 static void rte_lock_destroy(struct rtentry
*);
274 static inline struct rtentry
*rte_alloc_debug(void);
275 static inline void rte_free_debug(struct rtentry
*);
276 static inline void rte_lock_debug(struct rtentry_dbg
*);
277 static inline void rte_unlock_debug(struct rtentry_dbg
*);
278 static void rt_maskedcopy(struct sockaddr
*,
279 struct sockaddr
*, struct sockaddr
*);
280 static void rtable_init(void **);
281 static inline void rtref_audit(struct rtentry_dbg
*);
282 static inline void rtunref_audit(struct rtentry_dbg
*);
283 static struct rtentry
*rtalloc1_common_locked(struct sockaddr
*, int, uint32_t,
285 static int rtrequest_common_locked(int, struct sockaddr
*,
286 struct sockaddr
*, struct sockaddr
*, int, struct rtentry
**,
288 static void rtalloc_ign_common_locked(struct route
*, uint32_t, unsigned int);
289 static inline void sa_set_ifscope(struct sockaddr
*, unsigned int);
290 static struct sockaddr
*sin_copy(struct sockaddr_in
*, struct sockaddr_in
*,
292 static struct sockaddr
*mask_copy(struct sockaddr
*, struct sockaddr_in
*,
294 static struct sockaddr
*sa_trim(struct sockaddr
*, int);
295 static struct radix_node
*node_lookup(struct sockaddr
*, struct sockaddr
*,
297 static struct radix_node
*node_lookup_default(void);
298 static int rn_match_ifscope(struct radix_node
*, void *);
299 static struct ifaddr
*ifa_ifwithroute_common_locked(int,
300 const struct sockaddr
*, const struct sockaddr
*, unsigned int);
301 static struct rtentry
*rte_alloc(void);
302 static void rte_free(struct rtentry
*);
303 static void rtfree_common(struct rtentry
*, boolean_t
);
304 #if IFNET_ROUTE_REFCNT
305 static void rte_if_ref(struct ifnet
*, int);
306 #endif /* IFNET_ROUTE_REFCNT */
308 uint32_t route_generation
= 0;
311 * sockaddr_in with embedded interface scope; this is used internally
312 * to keep track of scoped route entries in the routing table. The
313 * fact that such a scope is embedded in the structure is an artifact
314 * of the current implementation which could change in future.
316 struct sockaddr_inifscope
{
318 sa_family_t sin_family
;
320 struct in_addr sin_addr
;
322 * To avoid possible conflict with an overlaid sockaddr_inarp
323 * having sin_other set to SIN_PROXY, we use the first 4-bytes
324 * of sin_zero since sin_srcaddr is one of the unused fields
333 #define sin_ifscope un._in_index.ifscope
336 #define SIN(sa) ((struct sockaddr_in *)(size_t)(sa))
337 #define SINIFSCOPE(sa) ((struct sockaddr_inifscope *)(size_t)(sa))
339 #define ASSERT_SINIFSCOPE(sa) { \
340 if ((sa)->sa_family != AF_INET || \
341 (sa)->sa_len < sizeof (struct sockaddr_in)) \
342 panic("%s: bad sockaddr_in %p\n", __func__, sa); \
346 * Argument to leaf-matching routine; at present it is scoped routing
347 * specific but can be expanded in future to include other search filters.
349 struct matchleaf_arg
{
350 unsigned int ifscope
; /* interface scope */
354 * For looking up the non-scoped default route (sockaddr instead
355 * of sockaddr_in for convenience).
357 static struct sockaddr sin_def
= {
358 sizeof (struct sockaddr_in
), AF_INET
, { 0, }
362 * Interface index (scope) of the primary interface; determined at
363 * the time when the default, non-scoped route gets added, changed
364 * or deleted. Protected by rnh_lock.
366 static unsigned int primary_ifscope
= IFSCOPE_NONE
;
368 #define INET_DEFAULT(dst) \
369 ((dst)->sa_family == AF_INET && SIN(dst)->sin_addr.s_addr == 0)
371 #define RT(r) ((struct rtentry *)r)
372 #define RT_HOST(r) (RT(r)->rt_flags & RTF_HOST)
374 #if IFNET_ROUTE_REFCNT
375 SYSCTL_DECL(_net_idle_route
);
377 static int rt_if_idle_expire_timeout
= RT_IF_IDLE_EXPIRE_TIMEOUT
;
378 SYSCTL_INT(_net_idle_route
, OID_AUTO
, expire_timeout
, CTLFLAG_RW
,
379 &rt_if_idle_expire_timeout
, 0, "Default expiration time on routes for "
380 "interface idle reference counting");
381 #endif /* IFNET_ROUTE_REFCNT */
384 * Given a route, determine whether or not it is the non-scoped default
385 * route; dst typically comes from rt_key(rt) but may be coming from
386 * a separate place when rt is in the process of being created.
389 rt_inet_default(struct rtentry
*rt
, struct sockaddr
*dst
)
391 return (INET_DEFAULT(dst
) && !(rt
->rt_flags
& RTF_IFSCOPE
));
395 * Set the ifscope of the primary interface; caller holds rnh_lock.
398 set_primary_ifscope(unsigned int ifscope
)
400 primary_ifscope
= ifscope
;
404 * Return the ifscope of the primary interface; caller holds rnh_lock.
407 get_primary_ifscope(void)
409 return (primary_ifscope
);
413 * Embed ifscope into a given a sockaddr_in.
416 sa_set_ifscope(struct sockaddr
*sa
, unsigned int ifscope
)
418 /* Caller must pass in sockaddr_in */
419 ASSERT_SINIFSCOPE(sa
);
421 SINIFSCOPE(sa
)->sin_ifscope
= ifscope
;
425 * Given a sockaddr_in, return the embedded ifscope to the caller.
428 sa_get_ifscope(struct sockaddr
*sa
)
430 /* Caller must pass in sockaddr_in */
431 ASSERT_SINIFSCOPE(sa
);
433 return (SINIFSCOPE(sa
)->sin_ifscope
);
437 * Copy a sockaddr_in src to dst and embed ifscope into dst.
439 static struct sockaddr
*
440 sin_copy(struct sockaddr_in
*src
, struct sockaddr_in
*dst
, unsigned int ifscope
)
443 sa_set_ifscope(SA(dst
), ifscope
);
449 * Copy a mask from src to a sockaddr_in dst and embed ifscope into dst.
451 static struct sockaddr
*
452 mask_copy(struct sockaddr
*src
, struct sockaddr_in
*dst
, unsigned int ifscope
)
454 /* We know dst is at least the size of sockaddr{_in} */
455 bzero(dst
, sizeof (*dst
));
456 rt_maskedcopy(src
, SA(dst
), src
);
459 * The length of the mask sockaddr would need to be adjusted
460 * to cover the additional sin_ifscope field; when ifscope is
461 * IFSCOPE_NONE, we'd end up clearing the embedded ifscope on
462 * the destination mask in addition to extending the length
463 * of the sockaddr, as a side effect. This is okay, as any
464 * trailing zeroes would be skipped by rn_addmask prior to
465 * inserting or looking up the mask in the mask tree.
467 SINIFSCOPE(dst
)->sin_ifscope
= ifscope
;
468 SINIFSCOPE(dst
)->sin_len
=
469 offsetof(struct sockaddr_inifscope
, sin_ifscope
) +
470 sizeof (SINIFSCOPE(dst
)->sin_ifscope
);
476 * Trim trailing zeroes on a sockaddr and update its length.
478 static struct sockaddr
*
479 sa_trim(struct sockaddr
*sa
, int skip
)
481 caddr_t cp
, base
= (caddr_t
)sa
+ skip
;
483 if (sa
->sa_len
<= skip
)
486 for (cp
= base
+ (sa
->sa_len
- skip
); cp
> base
&& cp
[-1] == 0;)
489 sa
->sa_len
= (cp
- base
) + skip
;
490 if (sa
->sa_len
< skip
) {
491 /* Must not happen, and if so, panic */
492 panic("%s: broken logic (sa_len %d < skip %d )", __func__
,
495 } else if (sa
->sa_len
== skip
) {
496 /* If we end up with all zeroes, then there's no mask */
504 * Called by rtm_msg{1,2} routines to "scrub" the embedded interface scope
505 * away from the socket address structure, so that clients of the routing
506 * socket will not be confused by the presence of the embedded scope, or the
507 * side effect of the increased length due to that. The source sockaddr is
508 * not modified; instead, the scrubbing happens on the destination sockaddr
509 * storage that is passed in by the caller.
512 rtm_scrub_ifscope(int idx
, struct sockaddr
*hint
, struct sockaddr
*sa
,
513 struct sockaddr_storage
*ss
)
515 struct sockaddr
*ret
= sa
;
520 * If this is for an AF_INET destination address, call
521 * sin_copy() with IFSCOPE_NONE as it does what we need.
523 if (sa
->sa_family
== AF_INET
&&
524 SINIFSCOPE(sa
)->sin_ifscope
!= IFSCOPE_NONE
) {
525 bzero(ss
, sizeof (*ss
));
526 ret
= sin_copy(SIN(sa
), SIN(ss
), IFSCOPE_NONE
);
532 * If this is for a mask, we can't tell whether or not
533 * there is an embedded interface scope, as the span of
534 * bytes between sa_len and the beginning of the mask
535 * (offset of sin_addr in the case of AF_INET) may be
536 * filled with all-ones by rn_addmask(), and hence we
537 * cannot rely on sa_family. Because of this, we use
538 * the sa_family of the hint sockaddr (RTAX_{DST,IFA})
539 * as indicator as to whether or not the mask is to be
540 * treated as one for AF_INET. Clearing the embedded
541 * scope involves setting it to IFSCOPE_NONE followed
542 * by calling sa_trim() to trim trailing zeroes from
543 * the storage sockaddr, which reverses what was done
544 * earlier by mask_copy() on the source sockaddr.
546 int skip
= offsetof(struct sockaddr_in
, sin_addr
);
547 if (sa
->sa_len
> skip
&& sa
->sa_len
<= sizeof (*ss
) &&
548 hint
!= NULL
&& hint
->sa_family
== AF_INET
) {
549 bzero(ss
, sizeof (*ss
));
550 bcopy(sa
, ss
, sa
->sa_len
);
551 SINIFSCOPE(ss
)->sin_ifscope
= IFSCOPE_NONE
;
552 ret
= sa_trim(SA(ss
), skip
);
564 * Callback leaf-matching routine for rn_matchaddr_args used
565 * for looking up an exact match for a scoped route entry.
568 rn_match_ifscope(struct radix_node
*rn
, void *arg
)
570 struct rtentry
*rt
= (struct rtentry
*)rn
;
571 struct matchleaf_arg
*ma
= arg
;
573 if (!(rt
->rt_flags
& RTF_IFSCOPE
) || rt_key(rt
)->sa_family
!= AF_INET
)
576 return (SINIFSCOPE(rt_key(rt
))->sin_ifscope
== ma
->ifscope
);
580 rtable_init(void **table
)
583 for (dom
= domains
; dom
; dom
= dom
->dom_next
)
584 if (dom
->dom_rtattach
)
585 dom
->dom_rtattach(&table
[dom
->dom_family
],
594 PE_parse_boot_argn("rte_debug", &rte_debug
, sizeof (rte_debug
));
596 rte_debug
|= RTD_DEBUG
;
598 rnh_lock_grp_attr
= lck_grp_attr_alloc_init();
599 rnh_lock_grp
= lck_grp_alloc_init("route", rnh_lock_grp_attr
);
600 rnh_lock_attr
= lck_attr_alloc_init();
601 if ((rnh_lock
= lck_mtx_alloc_init(rnh_lock_grp
,
602 rnh_lock_attr
)) == NULL
) {
603 printf("route_init: can't alloc rnh_lock\n");
607 rte_mtx_grp_attr
= lck_grp_attr_alloc_init();
608 rte_mtx_grp
= lck_grp_alloc_init(RTE_NAME
, rte_mtx_grp_attr
);
609 rte_mtx_attr
= lck_attr_alloc_init();
611 lck_mtx_lock(rnh_lock
);
612 rn_init(); /* initialize all zeroes, all ones, mask table */
613 lck_mtx_unlock(rnh_lock
);
614 rtable_init((void **)rt_tables
);
615 route_domain_mtx
= routedomain
.dom_mtx
;
617 if (rte_debug
& RTD_DEBUG
)
618 size
= sizeof (struct rtentry_dbg
);
620 size
= sizeof (struct rtentry
);
622 rte_zone
= zinit(size
, RTE_ZONE_MAX
* size
, 0, RTE_ZONE_NAME
);
623 if (rte_zone
== NULL
)
624 panic("route_init: failed allocating rte_zone");
626 zone_change(rte_zone
, Z_EXPAND
, TRUE
);
627 zone_change(rte_zone
, Z_NOENCRYPT
, TRUE
);
629 TAILQ_INIT(&rttrash_head
);
633 * Atomically increment route generation counter
636 routegenid_update(void)
638 (void) atomic_add_32_ov(&route_generation
, 1);
642 * Packet routing routines.
645 rtalloc(struct route
*ro
)
651 rtalloc_ign_locked(struct route
*ro
, uint32_t ignore
)
653 return (rtalloc_ign_common_locked(ro
, ignore
, IFSCOPE_NONE
));
657 rtalloc_scoped_ign_locked(struct route
*ro
, uint32_t ignore
,
658 unsigned int ifscope
)
660 return (rtalloc_ign_common_locked(ro
, ignore
, ifscope
));
664 rtalloc_ign_common_locked(struct route
*ro
, uint32_t ignore
,
665 unsigned int ifscope
)
669 if ((rt
= ro
->ro_rt
) != NULL
) {
671 if (rt
->rt_ifp
!= NULL
&& (rt
->rt_flags
& RTF_UP
) &&
672 rt
->generation_id
== route_generation
) {
680 ro
->ro_rt
= rtalloc1_common_locked(&ro
->ro_dst
, 1, ignore
, ifscope
);
681 if (ro
->ro_rt
!= NULL
) {
682 ro
->ro_rt
->generation_id
= route_generation
;
683 RT_LOCK_ASSERT_NOTHELD(ro
->ro_rt
);
688 rtalloc_ign(struct route
*ro
, uint32_t ignore
)
690 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
691 lck_mtx_lock(rnh_lock
);
692 rtalloc_ign_locked(ro
, ignore
);
693 lck_mtx_unlock(rnh_lock
);
697 rtalloc_scoped_ign(struct route
*ro
, uint32_t ignore
, unsigned int ifscope
)
699 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
700 lck_mtx_lock(rnh_lock
);
701 rtalloc_scoped_ign_locked(ro
, ignore
, ifscope
);
702 lck_mtx_unlock(rnh_lock
);
706 rtalloc1_locked(struct sockaddr
*dst
, int report
, uint32_t ignflags
)
708 return (rtalloc1_common_locked(dst
, report
, ignflags
, IFSCOPE_NONE
));
712 rtalloc1_scoped_locked(struct sockaddr
*dst
, int report
, uint32_t ignflags
,
713 unsigned int ifscope
)
715 return (rtalloc1_common_locked(dst
, report
, ignflags
, ifscope
));
719 * Look up the route that matches the address given
720 * Or, at least try.. Create a cloned route if needed.
722 static struct rtentry
*
723 rtalloc1_common_locked(struct sockaddr
*dst
, int report
, uint32_t ignflags
,
724 unsigned int ifscope
)
726 struct radix_node_head
*rnh
= rt_tables
[dst
->sa_family
];
727 struct rtentry
*rt
, *newrt
= NULL
;
728 struct rt_addrinfo info
;
730 int err
= 0, msgtype
= RTM_MISS
;
736 * Find the longest prefix or exact (in the scoped case) address match;
737 * callee adds a reference to entry and checks for root node as well
739 rt
= rt_lookup(FALSE
, dst
, NULL
, rnh
, ifscope
);
745 nflags
= rt
->rt_flags
& ~ignflags
;
747 if (report
&& (nflags
& (RTF_CLONING
| RTF_PRCLONING
))) {
749 * We are apparently adding (report = 0 in delete).
750 * If it requires that it be cloned, do so.
751 * (This implies it wasn't a HOST route.)
753 err
= rtrequest_locked(RTM_RESOLVE
, dst
, NULL
, NULL
, 0, &newrt
);
756 * If the cloning didn't succeed, maybe what we
757 * have from lookup above will do. Return that;
758 * no need to hold another reference since it's
766 * We cloned it; drop the original route found during lookup.
767 * The resulted cloned route (newrt) would now have an extra
768 * reference held during rtrequest.
771 if ((rt
= newrt
) && (rt
->rt_flags
& RTF_XRESOLVE
)) {
773 * If the new route specifies it be
774 * externally resolved, then go do that.
776 msgtype
= RTM_RESOLVE
;
784 * Either we hit the root or couldn't find any match,
785 * Which basically means "cant get there from here"
787 rtstat
.rts_unreach
++;
791 * If required, report the failure to the supervising
793 * For a delete, this is not an error. (report == 0)
795 bzero((caddr_t
)&info
, sizeof(info
));
796 info
.rti_info
[RTAX_DST
] = dst
;
797 rt_missmsg(msgtype
, &info
, 0, err
);
804 rtalloc1(struct sockaddr
*dst
, int report
, uint32_t ignflags
)
806 struct rtentry
* entry
;
807 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
808 lck_mtx_lock(rnh_lock
);
809 entry
= rtalloc1_locked(dst
, report
, ignflags
);
810 lck_mtx_unlock(rnh_lock
);
815 rtalloc1_scoped(struct sockaddr
*dst
, int report
, uint32_t ignflags
,
816 unsigned int ifscope
)
818 struct rtentry
* entry
;
819 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
820 lck_mtx_lock(rnh_lock
);
821 entry
= rtalloc1_scoped_locked(dst
, report
, ignflags
, ifscope
);
822 lck_mtx_unlock(rnh_lock
);
827 * Remove a reference count from an rtentry.
828 * If the count gets low enough, take it out of the routing table
831 rtfree_locked(struct rtentry
*rt
)
833 rtfree_common(rt
, TRUE
);
837 rtfree_common(struct rtentry
*rt
, boolean_t locked
)
839 struct radix_node_head
*rnh
;
842 * Atomically decrement the reference count and if it reaches 0,
843 * and there is a close function defined, call the close function.
846 if (rtunref(rt
) > 0) {
852 * To avoid violating lock ordering, we must drop rt_lock before
853 * trying to acquire the global rnh_lock. If we are called with
854 * rnh_lock held, then we already have exclusive access; otherwise
855 * we do the lock dance.
859 * Note that we check it again below after grabbing rnh_lock,
860 * since it is possible that another thread doing a lookup wins
861 * the race, grabs the rnh_lock first, and bumps up the reference
862 * count in which case the route should be left alone as it is
863 * still in use. It's also possible that another thread frees
864 * the route after we drop rt_lock; to prevent the route from
865 * being freed, we hold an extra reference.
867 RT_ADDREF_LOCKED(rt
);
869 lck_mtx_lock(rnh_lock
);
871 RT_REMREF_LOCKED(rt
);
872 if (rt
->rt_refcnt
> 0) {
873 /* We've lost the race, so abort */
880 * We may be blocked on other lock(s) as part of freeing
881 * the entry below, so convert from spin to full mutex.
885 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
887 /* Negative refcnt must never happen */
888 if (rt
->rt_refcnt
!= 0)
889 panic("rt %p invalid refcnt %d", rt
, rt
->rt_refcnt
);
892 * find the tree for that address family
893 * Note: in the case of igmp packets, there might not be an rnh
895 rnh
= rt_tables
[rt_key(rt
)->sa_family
];
898 * On last reference give the "close method" a chance to cleanup
899 * private state. This also permits (for IPv4 and IPv6) a chance
900 * to decide if the routing table entry should be purged immediately
901 * or at a later time. When an immediate purge is to happen the
902 * close routine typically issues RTM_DELETE which clears the RTF_UP
903 * flag on the entry so that the code below reclaims the storage.
905 if (rnh
!= NULL
&& rnh
->rnh_close
!= NULL
)
906 rnh
->rnh_close((struct radix_node
*)rt
, rnh
);
909 * If we are no longer "up" (and ref == 0) then we can free the
910 * resources associated with the route.
912 if (!(rt
->rt_flags
& RTF_UP
)) {
913 if (rt
->rt_nodes
->rn_flags
& (RNF_ACTIVE
| RNF_ROOT
))
914 panic("rt %p freed while in radix tree\n", rt
);
916 * the rtentry must have been removed from the routing table
917 * so it is represented in rttrash; remove that now.
919 (void) OSDecrementAtomic(&rttrash
);
920 if (rte_debug
& RTD_DEBUG
) {
921 TAILQ_REMOVE(&rttrash_head
, (struct rtentry_dbg
*)rt
,
926 * Route is no longer in the tree and refcnt is 0;
927 * we have exclusive access, so destroy it.
932 * release references on items we hold them on..
933 * e.g other routes and ifaddrs.
935 if (rt
->rt_parent
!= NULL
) {
936 rtfree_locked(rt
->rt_parent
);
937 rt
->rt_parent
= NULL
;
940 if (rt
->rt_ifa
!= NULL
) {
946 * Now free any attached link-layer info.
948 if (rt
->rt_llinfo
!= NULL
) {
949 if (rt
->rt_llinfo_free
!= NULL
)
950 (*rt
->rt_llinfo_free
)(rt
->rt_llinfo
);
952 R_Free(rt
->rt_llinfo
);
953 rt
->rt_llinfo
= NULL
;
957 * The key is separately alloc'd so free it (see rt_setgate()).
958 * This also frees the gateway, as they are always malloc'd
964 * and the rtentry itself of course
966 rte_lock_destroy(rt
);
970 * The "close method" has been called, but the route is
971 * still in the radix tree with zero refcnt, i.e. "up"
972 * and in the cached state.
978 lck_mtx_unlock(rnh_lock
);
982 rtfree(struct rtentry
*rt
)
984 rtfree_common(rt
, FALSE
);
988 * Decrements the refcount but does not free the route when
989 * the refcount reaches zero. Unless you have really good reason,
990 * use rtfree not rtunref.
993 rtunref(struct rtentry
*p
)
995 RT_LOCK_ASSERT_HELD(p
);
997 if (p
->rt_refcnt
== 0)
998 panic("%s(%p) bad refcnt\n", __func__
, p
);
1002 if (rte_debug
& RTD_DEBUG
)
1003 rtunref_audit((struct rtentry_dbg
*)p
);
1005 /* Return new value */
1006 return (p
->rt_refcnt
);
1010 rtunref_audit(struct rtentry_dbg
*rte
)
1014 if (rte
->rtd_inuse
!= RTD_INUSE
)
1015 panic("rtunref: on freed rte=%p\n", rte
);
1017 idx
= atomic_add_16_ov(&rte
->rtd_refrele_cnt
, 1) % CTRACE_HIST_SIZE
;
1018 if (rte_debug
& RTD_TRACE
)
1019 ctrace_record(&rte
->rtd_refrele
[idx
]);
1023 * Add a reference count from an rtentry.
1026 rtref(struct rtentry
*p
)
1028 RT_LOCK_ASSERT_HELD(p
);
1030 if (++p
->rt_refcnt
== 0)
1031 panic("%s(%p) bad refcnt\n", __func__
, p
);
1033 if (rte_debug
& RTD_DEBUG
)
1034 rtref_audit((struct rtentry_dbg
*)p
);
1038 rtref_audit(struct rtentry_dbg
*rte
)
1042 if (rte
->rtd_inuse
!= RTD_INUSE
)
1043 panic("rtref_audit: on freed rte=%p\n", rte
);
1045 idx
= atomic_add_16_ov(&rte
->rtd_refhold_cnt
, 1) % CTRACE_HIST_SIZE
;
1046 if (rte_debug
& RTD_TRACE
)
1047 ctrace_record(&rte
->rtd_refhold
[idx
]);
1051 rtsetifa(struct rtentry
*rt
, struct ifaddr
* ifa
)
1053 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
1055 RT_LOCK_ASSERT_HELD(rt
);
1057 if (rt
->rt_ifa
== ifa
)
1060 /* Release the old ifa */
1062 ifafree(rt
->rt_ifa
);
1067 /* Take a reference to the ifa */
1073 * Force a routing table entry to the specified
1074 * destination to go through the given gateway.
1075 * Normally called as a result of a routing redirect
1076 * message from the network layer.
1079 rtredirect(struct ifnet
*ifp
, struct sockaddr
*dst
, struct sockaddr
*gateway
,
1080 struct sockaddr
*netmask
, int flags
, struct sockaddr
*src
,
1081 struct rtentry
**rtp
)
1083 struct rtentry
*rt
= NULL
;
1086 struct rt_addrinfo info
;
1087 struct ifaddr
*ifa
= NULL
;
1088 unsigned int ifscope
= (ifp
!= NULL
) ? ifp
->if_index
: IFSCOPE_NONE
;
1089 struct sockaddr_in sin
;
1091 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
1092 lck_mtx_lock(rnh_lock
);
1095 * Verify the gateway is directly reachable; if scoped routing
1096 * is enabled, verify that it is reachable from the interface
1097 * where the ICMP redirect arrived on.
1099 if ((ifa
= ifa_ifwithnet_scoped(gateway
, ifscope
)) == NULL
) {
1100 error
= ENETUNREACH
;
1104 /* Lookup route to the destination (from the original IP header) */
1105 rt
= rtalloc1_scoped_locked(dst
, 0, RTF_CLONING
|RTF_PRCLONING
, ifscope
);
1109 /* Embed scope in src for comparison against rt_gateway below */
1110 if (ip_doscopedroute
&& src
->sa_family
== AF_INET
)
1111 src
= sin_copy(SIN(src
), &sin
, ifscope
);
1114 * If the redirect isn't from our current router for this dst,
1115 * it's either old or wrong. If it redirects us to ourselves,
1116 * we have a routing loop, perhaps as a result of an interface
1117 * going down recently.
1119 if (!(flags
& RTF_DONE
) && rt
!= NULL
&&
1120 (!equal(src
, rt
->rt_gateway
) || !equal(rt
->rt_ifa
->ifa_addr
,
1125 if ((ifa
= ifa_ifwithaddr(gateway
))) {
1128 error
= EHOSTUNREACH
;
1144 * Create a new entry if we just got back a wildcard entry
1145 * or the the lookup failed. This is necessary for hosts
1146 * which use routing redirects generated by smart gateways
1147 * to dynamically build the routing tables.
1149 if ((rt
== NULL
) || (rt_mask(rt
) != NULL
&& rt_mask(rt
)->sa_len
< 2))
1152 * Don't listen to the redirect if it's
1153 * for a route to an interface.
1155 RT_LOCK_ASSERT_HELD(rt
);
1156 if (rt
->rt_flags
& RTF_GATEWAY
) {
1157 if (((rt
->rt_flags
& RTF_HOST
) == 0) && (flags
& RTF_HOST
)) {
1159 * Changing from route to net => route to host.
1160 * Create new route, rather than smashing route
1161 * to net; similar to cloned routes, the newly
1162 * created host route is scoped as well.
1167 flags
|= RTF_GATEWAY
| RTF_DYNAMIC
;
1168 error
= rtrequest_scoped_locked(RTM_ADD
, dst
,
1169 gateway
, netmask
, flags
, NULL
, ifscope
);
1170 stat
= &rtstat
.rts_dynamic
;
1173 * Smash the current notion of the gateway to
1174 * this destination. Should check about netmask!!!
1176 rt
->rt_flags
|= RTF_MODIFIED
;
1177 flags
|= RTF_MODIFIED
;
1178 stat
= &rtstat
.rts_newgateway
;
1180 * add the key and gateway (in one malloc'd chunk).
1182 error
= rt_setgate(rt
, rt_key(rt
), gateway
);
1187 error
= EHOSTUNREACH
;
1191 RT_LOCK_ASSERT_NOTHELD(rt
);
1199 rtstat
.rts_badredirect
++;
1204 routegenid_update();
1206 lck_mtx_unlock(rnh_lock
);
1207 bzero((caddr_t
)&info
, sizeof(info
));
1208 info
.rti_info
[RTAX_DST
] = dst
;
1209 info
.rti_info
[RTAX_GATEWAY
] = gateway
;
1210 info
.rti_info
[RTAX_NETMASK
] = netmask
;
1211 info
.rti_info
[RTAX_AUTHOR
] = src
;
1212 rt_missmsg(RTM_REDIRECT
, &info
, flags
, error
);
1216 * Routing table ioctl interface.
1219 rtioctl(unsigned long req
, caddr_t data
, struct proc
*p
)
1222 #if INET && MROUTING
1223 return mrt_ioctl(req
, data
);
1226 #pragma unused(data)
1234 const struct sockaddr
*dst
,
1235 const struct sockaddr
*gateway
)
1239 lck_mtx_lock(rnh_lock
);
1240 ifa
= ifa_ifwithroute_locked(flags
, dst
, gateway
);
1241 lck_mtx_unlock(rnh_lock
);
1247 ifa_ifwithroute_locked(int flags
, const struct sockaddr
*dst
,
1248 const struct sockaddr
*gateway
)
1250 return (ifa_ifwithroute_common_locked((flags
& ~RTF_IFSCOPE
), dst
,
1251 gateway
, IFSCOPE_NONE
));
1255 ifa_ifwithroute_scoped_locked(int flags
, const struct sockaddr
*dst
,
1256 const struct sockaddr
*gateway
, unsigned int ifscope
)
1258 if (ifscope
!= IFSCOPE_NONE
)
1259 flags
|= RTF_IFSCOPE
;
1261 flags
&= ~RTF_IFSCOPE
;
1263 return (ifa_ifwithroute_common_locked(flags
, dst
, gateway
, ifscope
));
1266 static struct ifaddr
*
1267 ifa_ifwithroute_common_locked(int flags
, const struct sockaddr
*dst
,
1268 const struct sockaddr
*gateway
, unsigned int ifscope
)
1270 struct ifaddr
*ifa
= NULL
;
1271 struct rtentry
*rt
= NULL
;
1272 struct sockaddr_in dst_in
, gw_in
;
1274 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
1276 if (ip_doscopedroute
) {
1278 * Just in case the sockaddr passed in by the caller
1279 * contains embedded scope, make sure to clear it since
1280 * IPv4 interface addresses aren't scoped.
1282 if (dst
!= NULL
&& dst
->sa_family
== AF_INET
)
1283 dst
= sin_copy(SIN(dst
), &dst_in
, IFSCOPE_NONE
);
1284 if (gateway
!= NULL
&& gateway
->sa_family
== AF_INET
)
1285 gateway
= sin_copy(SIN(gateway
), &gw_in
, IFSCOPE_NONE
);
1288 if (!(flags
& RTF_GATEWAY
)) {
1290 * If we are adding a route to an interface,
1291 * and the interface is a pt to pt link
1292 * we should search for the destination
1293 * as our clue to the interface. Otherwise
1294 * we can use the local address.
1296 if (flags
& RTF_HOST
) {
1297 ifa
= ifa_ifwithdstaddr(dst
);
1300 ifa
= ifa_ifwithaddr_scoped(gateway
, ifscope
);
1303 * If we are adding a route to a remote net
1304 * or host, the gateway may still be on the
1305 * other end of a pt to pt link.
1307 ifa
= ifa_ifwithdstaddr(gateway
);
1310 ifa
= ifa_ifwithnet_scoped(gateway
, ifscope
);
1312 /* Workaround to avoid gcc warning regarding const variable */
1313 rt
= rtalloc1_scoped_locked((struct sockaddr
*)(size_t)dst
,
1320 RT_REMREF_LOCKED(rt
);
1325 if (ifa
!= NULL
&& ifa
->ifa_addr
->sa_family
!= dst
->sa_family
) {
1326 struct ifaddr
*newifa
;
1327 /* Callee adds reference to newifa upon success */
1328 newifa
= ifaof_ifpforaddr(dst
, ifa
->ifa_ifp
);
1329 if (newifa
!= NULL
) {
1335 * If we are adding a gateway, it is quite possible that the
1336 * routing table has a static entry in place for the gateway,
1337 * that may not agree with info garnered from the interfaces.
1338 * The routing table should carry more precedence than the
1339 * interfaces in this matter. Must be careful not to stomp
1340 * on new entries from rtinit, hence (ifa->ifa_addr != gateway).
1343 !equal(ifa
->ifa_addr
, (struct sockaddr
*)(size_t)gateway
)) &&
1344 (rt
= rtalloc1_scoped_locked((struct sockaddr
*)(size_t)gateway
,
1345 0, 0, ifscope
)) != NULL
) {
1352 RT_REMREF_LOCKED(rt
);
1356 * If an interface scope was specified, the interface index of
1357 * the found ifaddr must be equivalent to that of the scope;
1358 * otherwise there is no match.
1360 if ((flags
& RTF_IFSCOPE
) &&
1361 ifa
!= NULL
&& ifa
->ifa_ifp
->if_index
!= ifscope
) {
1369 static int rt_fixdelete(struct radix_node
*, void *);
1370 static int rt_fixchange(struct radix_node
*, void *);
1373 struct rtentry
*rt0
;
1374 struct radix_node_head
*rnh
;
1378 rtrequest_locked(int req
, struct sockaddr
*dst
, struct sockaddr
*gateway
,
1379 struct sockaddr
*netmask
, int flags
, struct rtentry
**ret_nrt
)
1381 return (rtrequest_common_locked(req
, dst
, gateway
, netmask
,
1382 (flags
& ~RTF_IFSCOPE
), ret_nrt
, IFSCOPE_NONE
));
1386 rtrequest_scoped_locked(int req
, struct sockaddr
*dst
,
1387 struct sockaddr
*gateway
, struct sockaddr
*netmask
, int flags
,
1388 struct rtentry
**ret_nrt
, unsigned int ifscope
)
1390 if (ifscope
!= IFSCOPE_NONE
)
1391 flags
|= RTF_IFSCOPE
;
1393 flags
&= ~RTF_IFSCOPE
;
1395 return (rtrequest_common_locked(req
, dst
, gateway
, netmask
,
1396 flags
, ret_nrt
, ifscope
));
1400 * Do appropriate manipulations of a routing tree given all the bits of
1403 * Embedding the scope in the radix key is an internal job that should be
1404 * left to routines in this module. Callers should specify the scope value
1405 * to the "scoped" variants of route routines instead of manipulating the
1406 * key itself. This is typically done when creating a scoped route, e.g.
1407 * rtrequest(RTM_ADD). Once such a route is created and marked with the
1408 * RTF_IFSCOPE flag, callers can simply use its rt_key(rt) to clone it
1409 * (RTM_RESOLVE) or to remove it (RTM_DELETE). An exception to this is
1410 * during certain routing socket operations where the search key might be
1411 * derived from the routing message itself, in which case the caller must
1412 * specify the destination address and scope value for RTM_ADD/RTM_DELETE.
1415 rtrequest_common_locked(int req
, struct sockaddr
*dst0
,
1416 struct sockaddr
*gateway
, struct sockaddr
*netmask
, int flags
,
1417 struct rtentry
**ret_nrt
, unsigned int ifscope
)
1421 struct radix_node
*rn
;
1422 struct radix_node_head
*rnh
;
1423 struct ifaddr
*ifa
= NULL
;
1424 struct sockaddr
*ndst
, *dst
= dst0
;
1425 struct sockaddr_in sin
, mask
;
1426 #define senderr(x) { error = x ; goto bad; }
1428 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
1430 * Find the correct routing tree to use for this Address Family
1432 if ((rnh
= rt_tables
[dst
->sa_family
]) == 0)
1435 * If we are adding a host route then we don't want to put
1436 * a netmask in the tree
1438 if (flags
& RTF_HOST
)
1442 * If RTF_IFSCOPE is specified, use a local copy of the destination
1443 * address to embed the scope into. This logic is repeated below
1444 * in the RTM_RESOLVE handler since the caller does not normally
1445 * specify such a flag during a resolve; instead it passes in the
1446 * route used for cloning for which the scope info is derived from.
1447 * Note also that in the case of RTM_DELETE, the address passed in
1448 * by the caller might already contain the embedded scope info when
1449 * it is the key itself, thus making RTF_IFSCOPE unnecessary; one
1450 * instance where it is explicitly set is inside route_output()
1451 * as part of handling a routing socket request.
1453 if (req
!= RTM_RESOLVE
&& (flags
& RTF_IFSCOPE
)) {
1454 /* Scoped routing is for AF_INET only */
1455 if (dst
->sa_family
!= AF_INET
||
1456 (req
== RTM_ADD
&& !ip_doscopedroute
))
1459 if (ifscope
== IFSCOPE_NONE
) {
1460 flags
&= ~RTF_IFSCOPE
;
1462 /* Embed ifscope into the key (local copy) */
1463 dst
= sin_copy(SIN(dst
), &sin
, ifscope
);
1465 /* Embed ifscope into netmask (local copy) */
1466 if (netmask
!= NULL
)
1467 netmask
= mask_copy(netmask
, &mask
, ifscope
);
1474 * Remove the item from the tree and return it.
1475 * Complain if it is not there and do no more processing.
1477 if ((rn
= rnh
->rnh_deladdr(dst
, netmask
, rnh
)) == 0)
1479 if (rn
->rn_flags
& (RNF_ACTIVE
| RNF_ROOT
))
1480 panic ("rtrequest delete");
1481 rt
= (struct rtentry
*)rn
;
1484 * Take an extra reference to handle the deletion of a route
1485 * entry whose reference count is already 0; e.g. an expiring
1486 * cloned route entry or an entry that was added to the table
1487 * with 0 reference. If the caller is interested in this route,
1488 * we will return it with the reference intact. Otherwise we
1489 * will decrement the reference via rtfree_locked() and then
1490 * possibly deallocate it.
1493 RT_ADDREF_LOCKED(rt
);
1494 rt
->rt_flags
&= ~RTF_UP
;
1497 * For consistency, in case the caller didn't set the flag.
1499 rt
->rt_flags
|= RTF_CONDEMNED
;
1502 * Now search what's left of the subtree for any cloned
1503 * routes which might have been formed from this node.
1505 if ((rt
->rt_flags
& (RTF_CLONING
| RTF_PRCLONING
)) &&
1508 rnh
->rnh_walktree_from(rnh
, dst
, rt_mask(rt
),
1514 * Remove any external references we may have.
1515 * This might result in another rtentry being freed if
1516 * we held its last reference.
1518 if (rt
->rt_gwroute
!= NULL
) {
1519 rtfree_locked(rt
->rt_gwroute
);
1520 rt
->rt_gwroute
= NULL
;
1524 * give the protocol a chance to keep things in sync.
1526 if ((ifa
= rt
->rt_ifa
) && ifa
->ifa_rtrequest
)
1527 ifa
->ifa_rtrequest(RTM_DELETE
, rt
, SA(0));
1531 * one more rtentry floating around that is not
1532 * linked to the routing table.
1534 (void) OSIncrementAtomic(&rttrash
);
1535 if (rte_debug
& RTD_DEBUG
) {
1536 TAILQ_INSERT_TAIL(&rttrash_head
,
1537 (struct rtentry_dbg
*)rt
, rtd_trash_link
);
1541 * If this is the (non-scoped) default route, clear
1542 * the interface index used for the primary ifscope.
1544 if (rt_inet_default(rt
, rt_key(rt
)))
1545 set_primary_ifscope(IFSCOPE_NONE
);
1547 #if IFNET_ROUTE_REFCNT
1548 if (rt
->rt_if_ref_fn
!= NULL
) {
1549 rt
->rt_if_ref_fn(rt
->rt_ifp
, -1);
1550 rt
->rt_flags
&= ~RTF_IFREF
;
1552 #endif /* IFNET_ROUTE_REFCNT */
1557 * If the caller wants it, then it can have it,
1558 * but it's up to it to free the rtentry as we won't be
1561 if (ret_nrt
!= NULL
) {
1562 /* Return the route to caller with reference intact */
1565 /* Dereference or deallocate the route */
1571 if (ret_nrt
== 0 || (rt
= *ret_nrt
) == 0)
1574 * If cloning, we have the parent route given by the caller
1575 * and will use its rt_gateway, rt_rmx as part of the cloning
1576 * process below. Since rnh_lock is held at this point, the
1577 * parent's rt_ifa and rt_gateway will not change, and its
1578 * relevant rt_flags will not change as well. The only thing
1579 * that could change are the metrics, and thus we hold the
1580 * parent route's rt_lock later on during the actual copying
1585 flags
= rt
->rt_flags
&
1586 ~(RTF_CLONING
| RTF_PRCLONING
| RTF_STATIC
);
1587 flags
|= RTF_WASCLONED
;
1588 gateway
= rt
->rt_gateway
;
1589 if ((netmask
= rt
->rt_genmask
) == 0)
1592 if (!ip_doscopedroute
|| dst
->sa_family
!= AF_INET
)
1595 * When scoped routing is enabled, cloned entries are
1596 * always scoped according to the interface portion of
1597 * the parent route. The exception to this are IPv4
1598 * link local addresses.
1600 if (!IN_LINKLOCAL(ntohl(SIN(dst
)->sin_addr
.s_addr
))) {
1601 if (flags
& RTF_IFSCOPE
) {
1602 ifscope
= sa_get_ifscope(rt_key(rt
));
1604 ifscope
= rt
->rt_ifp
->if_index
;
1605 flags
|= RTF_IFSCOPE
;
1608 ifscope
= IFSCOPE_NONE
;
1609 flags
&= ~RTF_IFSCOPE
;
1612 /* Embed or clear ifscope into/from the key (local copy) */
1613 dst
= sin_copy(SIN(dst
), &sin
, ifscope
);
1615 /* Embed or clear ifscope into/from netmask (local copy) */
1616 if (netmask
!= NULL
)
1617 netmask
= mask_copy(netmask
, &mask
, ifscope
);
1622 if ((flags
& RTF_GATEWAY
) && !gateway
)
1623 panic("rtrequest: RTF_GATEWAY but no gateway");
1625 if (flags
& RTF_IFSCOPE
) {
1626 ifa
= ifa_ifwithroute_scoped_locked(flags
, dst0
,
1629 ifa
= ifa_ifwithroute_locked(flags
, dst0
, gateway
);
1632 senderr(ENETUNREACH
);
1634 if ((rt
= rte_alloc()) == NULL
)
1636 Bzero(rt
, sizeof(*rt
));
1639 rt
->rt_flags
= RTF_UP
| flags
;
1642 * Add the gateway. Possibly re-malloc-ing the storage for it
1643 * also add the rt_gwroute if possible.
1645 if ((error
= rt_setgate(rt
, dst
, gateway
)) != 0) {
1647 rte_lock_destroy(rt
);
1653 * point to the (possibly newly malloc'd) dest address.
1658 * make sure it contains the value we want (masked if needed).
1661 rt_maskedcopy(dst
, ndst
, netmask
);
1663 Bcopy(dst
, ndst
, dst
->sa_len
);
1666 * Note that we now have a reference to the ifa.
1667 * This moved from below so that rnh->rnh_addaddr() can
1668 * examine the ifa and ifa->ifa_ifp if it so desires.
1671 rt
->rt_ifp
= rt
->rt_ifa
->ifa_ifp
;
1673 /* XXX mtu manipulation will be done in rnh_addaddr -- itojun */
1675 rn
= rnh
->rnh_addaddr((caddr_t
)ndst
, (caddr_t
)netmask
,
1678 struct rtentry
*rt2
;
1680 * Uh-oh, we already have one of these in the tree.
1681 * We do a special hack: if the route that's already
1682 * there was generated by the protocol-cloning
1683 * mechanism, then we just blow it away and retry
1684 * the insertion of the new one.
1686 if (flags
& RTF_IFSCOPE
) {
1687 rt2
= rtalloc1_scoped_locked(dst0
, 0,
1688 RTF_CLONING
| RTF_PRCLONING
, ifscope
);
1690 rt2
= rtalloc1_locked(dst
, 0,
1691 RTF_CLONING
| RTF_PRCLONING
);
1693 if (rt2
&& rt2
->rt_parent
) {
1695 * rnh_lock is held here, so rt_key and
1696 * rt_gateway of rt2 will not change.
1698 (void) rtrequest_locked(RTM_DELETE
, rt_key(rt2
),
1699 rt2
->rt_gateway
, rt_mask(rt2
),
1702 rn
= rnh
->rnh_addaddr((caddr_t
)ndst
,
1706 /* undo the extra ref we got */
1712 * If it still failed to go into the tree,
1713 * then un-make it (this should be a function)
1716 if (rt
->rt_gwroute
) {
1717 rtfree_locked(rt
->rt_gwroute
);
1718 rt
->rt_gwroute
= NULL
;
1721 ifafree(rt
->rt_ifa
);
1726 rte_lock_destroy(rt
);
1734 * If we got here from RESOLVE, then we are cloning so clone
1735 * the rest, and note that we are a clone (and increment the
1736 * parent's references). rnh_lock is still held, which prevents
1737 * a lookup from returning the newly-created route. Hence
1738 * holding and releasing the parent's rt_lock while still
1739 * holding the route's rt_lock is safe since the new route
1740 * is not yet externally visible.
1742 if (req
== RTM_RESOLVE
) {
1743 RT_LOCK_SPIN(*ret_nrt
);
1744 rt
->rt_rmx
= (*ret_nrt
)->rt_rmx
; /* copy metrics */
1745 if ((*ret_nrt
)->rt_flags
& (RTF_CLONING
| RTF_PRCLONING
)) {
1746 rt
->rt_parent
= (*ret_nrt
);
1747 RT_ADDREF_LOCKED(*ret_nrt
);
1749 RT_UNLOCK(*ret_nrt
);
1751 #if IFNET_ROUTE_REFCNT
1753 * Enable interface reference counting for unicast
1754 * cloned routes and bump up the reference count.
1756 if (rt
->rt_parent
!= NULL
&&
1757 !(rt
->rt_flags
& (RTF_BROADCAST
| RTF_MULTICAST
))) {
1758 rt
->rt_if_ref_fn
= rte_if_ref
;
1759 rt
->rt_if_ref_fn(rt
->rt_ifp
, 1);
1760 rt
->rt_flags
|= RTF_IFREF
;
1762 #endif /* IFNET_ROUTE_REFCNT */
1766 * if this protocol has something to add to this then
1767 * allow it to do that as well.
1769 if (ifa
->ifa_rtrequest
)
1770 ifa
->ifa_rtrequest(req
, rt
, SA(ret_nrt
? *ret_nrt
: 0));
1775 * If this is the (non-scoped) default route, record
1776 * the interface index used for the primary ifscope.
1778 if (rt_inet_default(rt
, rt_key(rt
)))
1779 set_primary_ifscope(rt
->rt_ifp
->if_index
);
1782 * actually return a resultant rtentry and
1783 * give the caller a single reference.
1787 RT_ADDREF_LOCKED(rt
);
1791 * We repeat the same procedure from rt_setgate() here because
1792 * it doesn't fire when we call it there because the node
1793 * hasn't been added to the tree yet.
1795 if (req
== RTM_ADD
&&
1796 !(rt
->rt_flags
& RTF_HOST
) && rt_mask(rt
) != 0) {
1797 struct rtfc_arg arg
;
1801 rnh
->rnh_walktree_from(rnh
, rt_key(rt
), rt_mask(rt
),
1802 rt_fixchange
, &arg
);
1817 struct sockaddr
*dst
,
1818 struct sockaddr
*gateway
,
1819 struct sockaddr
*netmask
,
1821 struct rtentry
**ret_nrt
)
1824 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
1825 lck_mtx_lock(rnh_lock
);
1826 error
= rtrequest_locked(req
, dst
, gateway
, netmask
, flags
, ret_nrt
);
1827 lck_mtx_unlock(rnh_lock
);
1831 * Called from rtrequest(RTM_DELETE, ...) to fix up the route's ``family''
1832 * (i.e., the routes related to it by the operation of cloning). This
1833 * routine is iterated over all potential former-child-routes by way of
1834 * rnh->rnh_walktree_from() above, and those that actually are children of
1835 * the late parent (passed in as VP here) are themselves deleted.
1838 rt_fixdelete(struct radix_node
*rn
, void *vp
)
1840 struct rtentry
*rt
= (struct rtentry
*)rn
;
1841 struct rtentry
*rt0
= vp
;
1843 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
1846 if (rt
->rt_parent
== rt0
&&
1847 !(rt
->rt_flags
& (RTF_PINNED
| RTF_CLONING
| RTF_PRCLONING
))) {
1849 * Safe to drop rt_lock and use rt_key, since holding
1850 * rnh_lock here prevents another thread from calling
1851 * rt_setgate() on this route.
1854 return (rtrequest_locked(RTM_DELETE
, rt_key(rt
), NULL
,
1855 rt_mask(rt
), rt
->rt_flags
, NULL
));
1862 * This routine is called from rt_setgate() to do the analogous thing for
1863 * adds and changes. There is the added complication in this case of a
1864 * middle insert; i.e., insertion of a new network route between an older
1865 * network route and (cloned) host routes. For this reason, a simple check
1866 * of rt->rt_parent is insufficient; each candidate route must be tested
1867 * against the (mask, value) of the new route (passed as before in vp)
1868 * to see if the new route matches it.
1870 * XXX - it may be possible to do fixdelete() for changes and reserve this
1871 * routine just for adds. I'm not sure why I thought it was necessary to do
1875 rt_fixchange(struct radix_node
*rn
, void *vp
)
1877 struct rtentry
*rt
= (struct rtentry
*)rn
;
1878 struct rtfc_arg
*ap
= vp
;
1879 struct rtentry
*rt0
= ap
->rt0
;
1880 struct radix_node_head
*rnh
= ap
->rnh
;
1881 u_char
*xk1
, *xm1
, *xk2
, *xmp
;
1884 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
1888 if (!rt
->rt_parent
||
1889 (rt
->rt_flags
& (RTF_PINNED
| RTF_CLONING
| RTF_PRCLONING
))) {
1894 if (rt
->rt_parent
== rt0
)
1898 * There probably is a function somewhere which does this...
1899 * if not, there should be.
1901 len
= imin(rt_key(rt0
)->sa_len
, rt_key(rt
)->sa_len
);
1903 xk1
= (u_char
*)rt_key(rt0
);
1904 xm1
= (u_char
*)rt_mask(rt0
);
1905 xk2
= (u_char
*)rt_key(rt
);
1908 * Avoid applying a less specific route; do this only if the parent
1909 * route (rt->rt_parent) is a network route, since otherwise its mask
1910 * will be NULL if it is a cloning host route.
1912 if ((xmp
= (u_char
*)rt_mask(rt
->rt_parent
)) != NULL
) {
1913 int mlen
= rt_mask(rt
->rt_parent
)->sa_len
;
1914 if (mlen
> rt_mask(rt0
)->sa_len
) {
1919 for (i
= rnh
->rnh_treetop
->rn_offset
; i
< mlen
; i
++) {
1920 if ((xmp
[i
] & ~(xmp
[i
] ^ xm1
[i
])) != xmp
[i
]) {
1927 for (i
= rnh
->rnh_treetop
->rn_offset
; i
< len
; i
++) {
1928 if ((xk2
[i
] & xm1
[i
]) != xk1
[i
]) {
1935 * OK, this node is a clone, and matches the node currently being
1936 * changed/added under the node's mask. So, get rid of it.
1940 * Safe to drop rt_lock and use rt_key, since holding rnh_lock here
1941 * prevents another thread from calling rt_setgate() on this route.
1944 return (rtrequest_locked(RTM_DELETE
, rt_key(rt
), NULL
,
1945 rt_mask(rt
), rt
->rt_flags
, NULL
));
1949 * Round up sockaddr len to multiples of 32-bytes. This will reduce
1950 * or even eliminate the need to re-allocate the chunk of memory used
1951 * for rt_key and rt_gateway in the event the gateway portion changes.
1952 * Certain code paths (e.g. IPSec) are notorious for caching the address
1953 * of rt_gateway; this rounding-up would help ensure that the gateway
1954 * portion never gets deallocated (though it may change contents) and
1955 * thus greatly simplifies things.
1957 #define SA_SIZE(x) (-(-((uintptr_t)(x)) & -(32)))
1960 * Sets the gateway and/or gateway route portion of a route; may be
1961 * called on an existing route to modify the gateway portion. Both
1962 * rt_key and rt_gateway are allocated out of the same memory chunk.
1963 * Route entry lock must be held by caller; this routine will return
1964 * with the lock held.
1967 rt_setgate(struct rtentry
*rt
, struct sockaddr
*dst
, struct sockaddr
*gate
)
1969 int dlen
= SA_SIZE(dst
->sa_len
), glen
= SA_SIZE(gate
->sa_len
);
1970 struct radix_node_head
*rnh
= rt_tables
[dst
->sa_family
];
1972 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
1973 RT_LOCK_ASSERT_HELD(rt
);
1976 * If this is for a route that is on its way of being removed,
1977 * or is temporarily frozen, reject the modification request.
1979 if (rt
->rt_flags
& RTF_CONDEMNED
)
1982 /* Add an extra ref for ourselves */
1983 RT_ADDREF_LOCKED(rt
);
1986 * A host route with the destination equal to the gateway
1987 * will interfere with keeping LLINFO in the routing
1988 * table, so disallow it.
1990 if (((rt
->rt_flags
& (RTF_HOST
|RTF_GATEWAY
|RTF_LLINFO
)) ==
1991 (RTF_HOST
|RTF_GATEWAY
)) && (dst
->sa_len
== gate
->sa_len
) &&
1992 (bcmp(dst
, gate
, dst
->sa_len
) == 0)) {
1994 * The route might already exist if this is an RTM_CHANGE
1995 * or a routing redirect, so try to delete it.
1997 if (rt_key(rt
) != NULL
) {
1999 * Safe to drop rt_lock and use rt_key, rt_gateway,
2000 * since holding rnh_lock here prevents another thread
2001 * from calling rt_setgate() on this route.
2004 (void) rtrequest_locked(RTM_DELETE
, rt_key(rt
),
2005 rt
->rt_gateway
, rt_mask(rt
), rt
->rt_flags
, NULL
);
2008 /* Release extra ref */
2009 RT_REMREF_LOCKED(rt
);
2010 return (EADDRNOTAVAIL
);
2014 * The destination is not directly reachable. Get a route
2015 * to the next-hop gateway and store it in rt_gwroute.
2017 if (rt
->rt_flags
& RTF_GATEWAY
) {
2018 struct rtentry
*gwrt
;
2019 unsigned int ifscope
;
2021 ifscope
= (dst
->sa_family
== AF_INET
) ?
2022 sa_get_ifscope(dst
) : IFSCOPE_NONE
;
2025 gwrt
= rtalloc1_scoped_locked(gate
, 1, RTF_PRCLONING
, ifscope
);
2027 RT_LOCK_ASSERT_NOTHELD(gwrt
);
2031 * Cloning loop avoidance:
2033 * In the presence of protocol-cloning and bad configuration,
2034 * it is possible to get stuck in bottomless mutual recursion
2035 * (rtrequest rt_setgate rtalloc1). We avoid this by not
2036 * allowing protocol-cloning to operate for gateways (which
2037 * is probably the correct choice anyway), and avoid the
2038 * resulting reference loops by disallowing any route to run
2039 * through itself as a gateway. This is obviously mandatory
2040 * when we get rt->rt_output(). It implies that a route to
2041 * the gateway must already be present in the system in order
2042 * for the gateway to be referred to by another route.
2045 RT_REMREF_LOCKED(gwrt
);
2046 /* Release extra ref */
2047 RT_REMREF_LOCKED(rt
);
2048 return (EADDRINUSE
); /* failure */
2052 * If scoped, the gateway route must use the same interface;
2053 * we're holding rnh_lock now, so rt_gateway and rt_ifp of gwrt
2054 * should not change and are freely accessible.
2056 if (ifscope
!= IFSCOPE_NONE
&& (rt
->rt_flags
& RTF_IFSCOPE
) &&
2057 gwrt
!= NULL
&& gwrt
->rt_ifp
!= NULL
&&
2058 gwrt
->rt_ifp
->if_index
!= ifscope
) {
2059 rtfree_locked(gwrt
); /* rt != gwrt, no deadlock */
2060 /* Release extra ref */
2061 RT_REMREF_LOCKED(rt
);
2062 return ((rt
->rt_flags
& RTF_HOST
) ?
2063 EHOSTUNREACH
: ENETUNREACH
);
2066 /* Check again since we dropped the lock above */
2067 if (rt
->rt_flags
& RTF_CONDEMNED
) {
2069 rtfree_locked(gwrt
);
2070 /* Release extra ref */
2071 RT_REMREF_LOCKED(rt
);
2075 if (rt
->rt_gwroute
!= NULL
)
2076 rtfree_locked(rt
->rt_gwroute
);
2077 rt
->rt_gwroute
= gwrt
;
2080 * In case the (non-scoped) default route gets modified via
2081 * an ICMP redirect, record the interface index used for the
2082 * primary ifscope. Also done in rt_setif() to take care
2083 * of the non-redirect cases.
2085 if (rt_inet_default(rt
, dst
) && rt
->rt_ifp
!= NULL
)
2086 set_primary_ifscope(rt
->rt_ifp
->if_index
);
2089 * Tell the kernel debugger about the new default gateway
2090 * if the gateway route uses the primary interface, or
2091 * if we are in a transient state before the non-scoped
2092 * default gateway is installed (similar to how the system
2093 * was behaving in the past). In future, it would be good
2094 * to do all this only when KDP is enabled.
2096 if ((dst
->sa_family
== AF_INET
) &&
2097 gwrt
!= NULL
&& gwrt
->rt_gateway
->sa_family
== AF_LINK
&&
2098 (gwrt
->rt_ifp
->if_index
== get_primary_ifscope() ||
2099 get_primary_ifscope() == IFSCOPE_NONE
))
2100 kdp_set_gateway_mac(SDL(gwrt
->rt_gateway
)->sdl_data
);
2104 * Prepare to store the gateway in rt_gateway. Both dst and gateway
2105 * are stored one after the other in the same malloc'd chunk. If we
2106 * have room, reuse the old buffer since rt_gateway already points
2107 * to the right place. Otherwise, malloc a new block and update
2108 * the 'dst' address and point rt_gateway to the right place.
2110 if (rt
->rt_gateway
== NULL
|| glen
> SA_SIZE(rt
->rt_gateway
->sa_len
)) {
2113 /* The underlying allocation is done with M_WAITOK set */
2114 R_Malloc(new, caddr_t
, dlen
+ glen
);
2116 if (rt
->rt_gwroute
!= NULL
)
2117 rtfree_locked(rt
->rt_gwroute
);
2118 rt
->rt_gwroute
= NULL
;
2119 /* Release extra ref */
2120 RT_REMREF_LOCKED(rt
);
2125 * Copy from 'dst' and not rt_key(rt) because we can get
2126 * here to initialize a newly allocated route entry, in
2127 * which case rt_key(rt) is NULL (and so does rt_gateway).
2129 bzero(new, dlen
+ glen
);
2130 Bcopy(dst
, new, dst
->sa_len
);
2131 R_Free(rt_key(rt
)); /* free old block; NULL is okay */
2132 rt
->rt_nodes
->rn_key
= new;
2133 rt
->rt_gateway
= (struct sockaddr
*)(new + dlen
);
2137 * Copy the new gateway value into the memory chunk.
2139 Bcopy(gate
, rt
->rt_gateway
, gate
->sa_len
);
2142 * For consistency between rt_gateway and rt_key(gwrt).
2144 if ((rt
->rt_flags
& RTF_GATEWAY
) && rt
->rt_gwroute
!= NULL
&&
2145 (rt
->rt_gwroute
->rt_flags
& RTF_IFSCOPE
) &&
2146 rt
->rt_gateway
->sa_family
== AF_INET
&&
2147 rt_key(rt
->rt_gwroute
)->sa_family
== AF_INET
) {
2148 sa_set_ifscope(rt
->rt_gateway
,
2149 sa_get_ifscope(rt_key(rt
->rt_gwroute
)));
2153 * This isn't going to do anything useful for host routes, so
2154 * don't bother. Also make sure we have a reasonable mask
2155 * (we don't yet have one during adds).
2157 if (!(rt
->rt_flags
& RTF_HOST
) && rt_mask(rt
) != 0) {
2158 struct rtfc_arg arg
;
2162 rnh
->rnh_walktree_from(rnh
, rt_key(rt
), rt_mask(rt
),
2163 rt_fixchange
, &arg
);
2167 /* Release extra ref */
2168 RT_REMREF_LOCKED(rt
);
2175 rt_maskedcopy(struct sockaddr
*src
, struct sockaddr
*dst
,
2176 struct sockaddr
*netmask
)
2178 u_char
*cp1
= (u_char
*)src
;
2179 u_char
*cp2
= (u_char
*)dst
;
2180 u_char
*cp3
= (u_char
*)netmask
;
2181 u_char
*cplim
= cp2
+ *cp3
;
2182 u_char
*cplim2
= cp2
+ *cp1
;
2184 *cp2
++ = *cp1
++; *cp2
++ = *cp1
++; /* copies sa_len & sa_family */
2189 *cp2
++ = *cp1
++ & *cp3
++;
2191 bzero((caddr_t
)cp2
, (unsigned)(cplim2
- cp2
));
2195 * Lookup an AF_INET scoped or non-scoped route depending on the ifscope
2196 * value passed in by the caller (IFSCOPE_NONE implies non-scoped).
2198 static struct radix_node
*
2199 node_lookup(struct sockaddr
*dst
, struct sockaddr
*netmask
,
2200 unsigned int ifscope
)
2202 struct radix_node_head
*rnh
= rt_tables
[AF_INET
];
2203 struct radix_node
*rn
;
2204 struct sockaddr_in sin
, mask
;
2205 struct matchleaf_arg ma
= { ifscope
};
2206 rn_matchf_t
*f
= rn_match_ifscope
;
2209 if (dst
->sa_family
!= AF_INET
)
2213 * Embed ifscope into the search key; for a non-scoped
2214 * search this will clear out any embedded scope value.
2216 dst
= sin_copy(SIN(dst
), &sin
, ifscope
);
2218 /* Embed (or clear) ifscope into netmask */
2219 if (netmask
!= NULL
)
2220 netmask
= mask_copy(netmask
, &mask
, ifscope
);
2222 if (ifscope
== IFSCOPE_NONE
)
2225 rn
= rnh
->rnh_lookup_args(dst
, netmask
, rnh
, f
, w
);
2226 if (rn
!= NULL
&& (rn
->rn_flags
& RNF_ROOT
))
2233 * Lookup the AF_INET non-scoped default route.
2235 static struct radix_node
*
2236 node_lookup_default(void)
2238 struct radix_node_head
*rnh
= rt_tables
[AF_INET
];
2239 return (rnh
->rnh_lookup(&sin_def
, NULL
, rnh
));
2243 * Common routine to lookup/match a route. It invokes the lookup/matchaddr
2244 * callback which could be address family-specific. The main difference
2245 * between the two (at least for AF_INET/AF_INET6) is that a lookup does
2246 * not alter the expiring state of a route, whereas a match would unexpire
2247 * or revalidate the route.
2249 * The optional scope or interface index property of a route allows for a
2250 * per-interface route instance. This permits multiple route entries having
2251 * the same destination (but not necessarily the same gateway) to exist in
2252 * the routing table; each of these entries is specific to the corresponding
2253 * interface. This is made possible by embedding the scope value into the
2254 * radix key, thus making each route entry unique. These scoped entries
2255 * exist along with the regular, non-scoped entries in the same radix tree
2256 * for a given address family (currently AF_INET only); the scope logically
2257 * partitions it into multiple per-interface sub-trees.
2259 * When a scoped route lookup is performed, the routing table is searched for
2260 * the best match that would result in a route using the same interface as the
2261 * one associated with the scope (the exception to this are routes that point
2262 * to the loopback interface). The search rule follows the longest matching
2263 * prefix with the additional interface constraint.
2266 rt_lookup(boolean_t lookup_only
, struct sockaddr
*dst
, struct sockaddr
*netmask
,
2267 struct radix_node_head
*rnh
, unsigned int ifscope
)
2269 struct radix_node
*rn0
, *rn
;
2270 boolean_t dontcare
= (ifscope
== IFSCOPE_NONE
);
2272 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_OWNED
);
2278 * Non-scoped route lookup.
2280 if (!ip_doscopedroute
|| dst
->sa_family
!= AF_INET
) {
2282 rn
= rnh
->rnh_lookup(dst
, netmask
, rnh
);
2284 rn
= rnh
->rnh_matchaddr(dst
, rnh
);
2287 * Don't return a root node; also, rnh_matchaddr callback
2288 * would have done the necessary work to clear RTPRF_OURS
2289 * for certain protocol families.
2291 if (rn
!= NULL
&& (rn
->rn_flags
& RNF_ROOT
))
2294 RT_LOCK_SPIN(RT(rn
));
2295 if (!(RT(rn
)->rt_flags
& RTF_CONDEMNED
)) {
2296 RT_ADDREF_LOCKED(RT(rn
));
2307 * Scoped route lookup:
2309 * We first perform a non-scoped lookup for the original result.
2310 * Afterwards, depending on whether or not the caller has specified
2311 * a scope, we perform a more specific scoped search and fallback
2312 * to this original result upon failure.
2314 rn0
= rn
= node_lookup(dst
, netmask
, IFSCOPE_NONE
);
2317 * If the caller did not specify a scope, use the primary scope
2318 * derived from the system's non-scoped default route. If, for
2319 * any reason, there is no primary interface, return what we have.
2321 if (dontcare
&& (ifscope
= get_primary_ifscope()) == IFSCOPE_NONE
)
2325 * Keep the original result if either of the following is true:
2327 * 1) The interface portion of the route has the same interface
2328 * index as the scope value and it is marked with RTF_IFSCOPE.
2329 * 2) The route uses the loopback interface, in which case the
2330 * destination (host/net) is local/loopback.
2332 * Otherwise, do a more specified search using the scope;
2333 * we're holding rnh_lock now, so rt_ifp should not change.
2336 struct rtentry
*rt
= RT(rn
);
2337 if (rt
->rt_ifp
!= lo_ifp
) {
2338 if (rt
->rt_ifp
->if_index
!= ifscope
) {
2340 * Wrong interface; keep the original result
2341 * only if the caller did not specify a scope,
2342 * and do a more specific scoped search using
2343 * the scope of the found route. Otherwise,
2344 * start again from scratch.
2348 ifscope
= rt
->rt_ifp
->if_index
;
2351 } else if (!(rt
->rt_flags
& RTF_IFSCOPE
)) {
2353 * Right interface, except that this route
2354 * isn't marked with RTF_IFSCOPE. Do a more
2355 * specific scoped search. Keep the original
2356 * result and return it it in case the scoped
2365 * Scoped search. Find the most specific entry having the same
2366 * interface scope as the one requested. The following will result
2367 * in searching for the longest prefix scoped match.
2370 rn
= node_lookup(dst
, netmask
, ifscope
);
2373 * Use the original result if either of the following is true:
2375 * 1) The scoped search did not yield any result.
2376 * 2) The result from the scoped search is a scoped default route,
2377 * and the original (non-scoped) result is not a default route,
2378 * i.e. the original result is a more specific host/net route.
2379 * 3) The scoped search yielded a net route but the original
2380 * result is a host route, i.e. the original result is treated
2381 * as a more specific route.
2383 if (rn
== NULL
|| (rn0
!= NULL
&&
2384 ((INET_DEFAULT(rt_key(RT(rn
))) && !INET_DEFAULT(rt_key(RT(rn0
)))) ||
2385 (!RT_HOST(rn
) && RT_HOST(rn0
)))))
2389 * If we still don't have a route, use the non-scoped default
2390 * route as long as the interface portion satistifes the scope.
2392 if (rn
== NULL
&& (rn
= node_lookup_default()) != NULL
&&
2393 RT(rn
)->rt_ifp
->if_index
!= ifscope
)
2399 * Manually clear RTPRF_OURS using in_validate() and
2400 * bump up the reference count after, and not before;
2401 * we only get here for AF_INET. node_lookup() has
2402 * done the check against RNF_ROOT, so we can be sure
2403 * that we're not returning a root node here.
2405 RT_LOCK_SPIN(RT(rn
));
2406 if (!(RT(rn
)->rt_flags
& RTF_CONDEMNED
)) {
2408 (void) in_validate(rn
);
2409 RT_ADDREF_LOCKED(RT(rn
));
2421 * Set up a routing table entry, normally
2425 rtinit(struct ifaddr
*ifa
, int cmd
, int flags
)
2428 lck_mtx_assert(rnh_lock
, LCK_MTX_ASSERT_NOTOWNED
);
2429 lck_mtx_lock(rnh_lock
);
2430 error
= rtinit_locked(ifa
, cmd
, flags
);
2431 lck_mtx_unlock(rnh_lock
);
2436 rtinit_locked(struct ifaddr
*ifa
, int cmd
, int flags
)
2439 struct sockaddr
*dst
;
2440 struct sockaddr
*deldst
;
2442 struct rtentry
*nrt
= 0;
2445 dst
= flags
& RTF_HOST
? ifa
->ifa_dstaddr
: ifa
->ifa_addr
;
2447 * If it's a delete, check that if it exists, it's on the correct
2448 * interface or we might scrub a route to another ifa which would
2449 * be confusing at best and possibly worse.
2451 if (cmd
== RTM_DELETE
) {
2453 * It's a delete, so it should already exist..
2454 * If it's a net, mask off the host bits
2455 * (Assuming we have a mask)
2457 if ((flags
& RTF_HOST
) == 0 && ifa
->ifa_netmask
) {
2458 m
= m_get(M_DONTWAIT
, MT_SONAME
);
2462 deldst
= mtod(m
, struct sockaddr
*);
2463 rt_maskedcopy(dst
, deldst
, ifa
->ifa_netmask
);
2467 * Get an rtentry that is in the routing tree and
2468 * contains the correct info. (if this fails, can't get there).
2469 * We set "report" to FALSE so that if it doesn't exist,
2470 * it doesn't report an error or clone a route, etc. etc.
2472 rt
= rtalloc1_locked(dst
, 0, 0);
2475 * Ok so we found the rtentry. it has an extra reference
2476 * for us at this stage. we won't need that so
2480 if (rt
->rt_ifa
!= ifa
) {
2481 RT_REMREF_LOCKED(rt
);
2484 * If the interface in the rtentry doesn't match
2485 * the interface we are using, then we don't
2486 * want to delete it, so return an error.
2487 * This seems to be the only point of
2488 * this whole RTM_DELETE clause.
2492 return (flags
& RTF_HOST
? EHOSTUNREACH
2495 RT_REMREF_LOCKED(rt
);
2503 * One would think that as we are deleting, and we know
2504 * it doesn't exist, we could just return at this point
2505 * with an "ELSE" clause, but apparently not..
2507 lck_mtx_unlock(rnh_lock
);
2508 return (flags
& RTF_HOST
? EHOSTUNREACH
2514 * Do the actual request
2516 error
= rtrequest_locked(cmd
, dst
, ifa
->ifa_addr
, ifa
->ifa_netmask
,
2517 flags
| ifa
->ifa_flags
, &nrt
);
2521 * If we are deleting, and we found an entry, then
2522 * it's been removed from the tree.. now throw it away.
2524 if (cmd
== RTM_DELETE
&& error
== 0 && (rt
= nrt
)) {
2526 * notify any listening routing agents of the change
2529 rt_newaddrmsg(cmd
, ifa
, error
, nrt
);
2531 routegenid_update();
2537 * We are adding, and we have a returned routing entry.
2538 * We need to sanity check the result.
2540 if (cmd
== RTM_ADD
&& error
== 0 && (rt
= nrt
)) {
2543 * If it came back with an unexpected interface, then it must
2544 * have already existed or something. (XXX)
2546 if (rt
->rt_ifa
!= ifa
) {
2547 if (!(rt
->rt_ifa
->ifa_ifp
->if_flags
&
2548 (IFF_POINTOPOINT
|IFF_LOOPBACK
)))
2549 printf("rtinit: wrong ifa (%p) was (%p)\n",
2552 * Ask that the protocol in question
2553 * remove anything it has associated with
2554 * this route and ifaddr.
2556 if (rt
->rt_ifa
->ifa_rtrequest
)
2557 rt
->rt_ifa
->ifa_rtrequest(RTM_DELETE
, rt
, SA(0));
2559 * Set the route's ifa.
2562 #if IFNET_ROUTE_REFCNT
2564 * Adjust route ref count for the interfaces.
2566 if (rt
->rt_if_ref_fn
!= NULL
&&
2567 rt
->rt_ifp
!= ifa
->ifa_ifp
) {
2568 rt
->rt_if_ref_fn(ifa
->ifa_ifp
, 1);
2569 rt
->rt_if_ref_fn(rt
->rt_ifp
, -1);
2571 #endif /* IFNET_ROUTE_REFCNT */
2573 * And substitute in references to the ifaddr
2576 rt
->rt_ifp
= ifa
->ifa_ifp
;
2577 rt
->rt_rmx
.rmx_mtu
= ifa
->ifa_ifp
->if_mtu
; /*XXX*/
2579 * Now ask the protocol to check if it needs
2580 * any special processing in its new form.
2582 if (ifa
->ifa_rtrequest
)
2583 ifa
->ifa_rtrequest(RTM_ADD
, rt
, SA(0));
2586 * notify any listenning routing agents of the change
2588 rt_newaddrmsg(cmd
, ifa
, error
, nrt
);
2590 routegenid_update();
2592 * We just wanted to add it; we don't actually need a
2593 * reference. This will result in a route that's added
2594 * to the routing table without a reference count. The
2595 * RTM_DELETE code will do the necessary step to adjust
2596 * the reference count at deletion time.
2598 RT_REMREF_LOCKED(rt
);
2605 rt_expiry(struct rtentry
*rt
, u_int64_t base
, u_int32_t delta
)
2607 #if IFNET_ROUTE_REFCNT
2611 * If the interface of the route doesn't demand aggressive draining,
2612 * return the expiration time based on the caller-supplied delta.
2613 * Otherwise use the more aggressive route expiration delta (or
2614 * the caller-supplied delta, whichever is less.)
2616 if (rt
->rt_ifp
== NULL
|| rt
->rt_ifp
->if_want_aggressive_drain
== 0)
2617 retval
= base
+ delta
;
2619 retval
= base
+ MIN(rt_if_idle_expire_timeout
, delta
);
2624 return (base
+ delta
);
2625 #endif /* IFNET_ROUTE_REFCNT */
2629 rte_lock_init(struct rtentry
*rt
)
2631 lck_mtx_init(&rt
->rt_lock
, rte_mtx_grp
, rte_mtx_attr
);
2635 rte_lock_destroy(struct rtentry
*rt
)
2637 RT_LOCK_ASSERT_NOTHELD(rt
);
2638 lck_mtx_destroy(&rt
->rt_lock
, rte_mtx_grp
);
2642 rt_lock(struct rtentry
*rt
, boolean_t spin
)
2644 RT_LOCK_ASSERT_NOTHELD(rt
);
2646 lck_mtx_lock_spin(&rt
->rt_lock
);
2648 lck_mtx_lock(&rt
->rt_lock
);
2649 if (rte_debug
& RTD_DEBUG
)
2650 rte_lock_debug((struct rtentry_dbg
*)rt
);
2654 rt_unlock(struct rtentry
*rt
)
2656 RT_LOCK_ASSERT_HELD(rt
);
2657 if (rte_debug
& RTD_DEBUG
)
2658 rte_unlock_debug((struct rtentry_dbg
*)rt
);
2659 lck_mtx_unlock(&rt
->rt_lock
);
2664 rte_lock_debug(struct rtentry_dbg
*rte
)
2668 idx
= atomic_add_32_ov(&rte
->rtd_lock_cnt
, 1) % CTRACE_HIST_SIZE
;
2669 if (rte_debug
& RTD_TRACE
)
2670 ctrace_record(&rte
->rtd_lock
[idx
]);
2674 rte_unlock_debug(struct rtentry_dbg
*rte
)
2678 idx
= atomic_add_32_ov(&rte
->rtd_unlock_cnt
, 1) % CTRACE_HIST_SIZE
;
2679 if (rte_debug
& RTD_TRACE
)
2680 ctrace_record(&rte
->rtd_unlock
[idx
]);
2683 static struct rtentry
*
2686 if (rte_debug
& RTD_DEBUG
)
2687 return (rte_alloc_debug());
2689 return ((struct rtentry
*)zalloc(rte_zone
));
2693 rte_free(struct rtentry
*p
)
2695 if (rte_debug
& RTD_DEBUG
) {
2700 if (p
->rt_refcnt
!= 0)
2701 panic("rte_free: rte=%p refcnt=%d non-zero\n", p
, p
->rt_refcnt
);
2706 #if IFNET_ROUTE_REFCNT
2708 rte_if_ref(struct ifnet
*ifp
, int cnt
)
2710 struct kev_msg ev_msg
;
2711 struct net_event_data ev_data
;
2714 /* Force cnt to 1 increment/decrement */
2715 if (cnt
< -1 || cnt
> 1)
2716 panic("%s: invalid count argument (%d)", __func__
, cnt
);
2718 old
= atomic_add_32_ov(&ifp
->if_route_refcnt
, cnt
);
2719 if (cnt
< 0 && old
== 0)
2720 panic("%s: ifp=%p negative route refcnt!", __func__
, ifp
);
2723 * The following is done without first holding the ifnet lock,
2724 * for performance reasons. The relevant ifnet fields, with
2725 * the exception of the if_idle_flags, are never changed
2726 * during the lifetime of the ifnet. The if_idle_flags
2727 * may possibly be modified, so in the event that the value
2728 * is stale because IFRF_IDLE_NOTIFY was cleared, we'd end up
2729 * sending the event anyway. This is harmless as it is just
2730 * a notification to the monitoring agent in user space, and
2731 * it is expected to check via SIOCGIFGETRTREFCNT again anyway.
2733 if ((ifp
->if_idle_flags
& IFRF_IDLE_NOTIFY
) && cnt
< 0 && old
== 1) {
2734 bzero(&ev_msg
, sizeof (ev_msg
));
2735 bzero(&ev_data
, sizeof (ev_data
));
2737 ev_msg
.vendor_code
= KEV_VENDOR_APPLE
;
2738 ev_msg
.kev_class
= KEV_NETWORK_CLASS
;
2739 ev_msg
.kev_subclass
= KEV_DL_SUBCLASS
;
2740 ev_msg
.event_code
= KEV_DL_IF_IDLE_ROUTE_REFCNT
;
2742 strlcpy(&ev_data
.if_name
[0], ifp
->if_name
, IFNAMSIZ
);
2744 ev_data
.if_family
= ifp
->if_family
;
2745 ev_data
.if_unit
= ifp
->if_unit
;
2746 ev_msg
.dv
[0].data_length
= sizeof (struct net_event_data
);
2747 ev_msg
.dv
[0].data_ptr
= &ev_data
;
2749 kev_post_msg(&ev_msg
);
2752 #endif /* IFNET_ROUTE_REFCNT */
2754 static inline struct rtentry
*
2755 rte_alloc_debug(void)
2757 struct rtentry_dbg
*rte
;
2759 rte
= ((struct rtentry_dbg
*)zalloc(rte_zone
));
2761 bzero(rte
, sizeof (*rte
));
2762 if (rte_debug
& RTD_TRACE
)
2763 ctrace_record(&rte
->rtd_alloc
);
2764 rte
->rtd_inuse
= RTD_INUSE
;
2766 return ((struct rtentry
*)rte
);
2770 rte_free_debug(struct rtentry
*p
)
2772 struct rtentry_dbg
*rte
= (struct rtentry_dbg
*)p
;
2774 if (p
->rt_refcnt
!= 0)
2775 panic("rte_free: rte=%p refcnt=%d\n", p
, p
->rt_refcnt
);
2777 if (rte
->rtd_inuse
== RTD_FREED
)
2778 panic("rte_free: double free rte=%p\n", rte
);
2779 else if (rte
->rtd_inuse
!= RTD_INUSE
)
2780 panic("rte_free: corrupted rte=%p\n", rte
);
2782 bcopy((caddr_t
)p
, (caddr_t
)&rte
->rtd_entry_saved
, sizeof (*p
));
2783 /* Preserve rt_lock to help catch use-after-free cases */
2784 bzero((caddr_t
)p
, offsetof(struct rtentry
, rt_lock
));
2786 rte
->rtd_inuse
= RTD_FREED
;
2788 if (rte_debug
& RTD_TRACE
)
2789 ctrace_record(&rte
->rtd_free
);
2791 if (!(rte_debug
& RTD_NO_FREE
))
2796 ctrace_record(ctrace_t
*tr
)
2798 tr
->th
= current_thread();
2799 bzero(tr
->pc
, sizeof (tr
->pc
));
2800 (void) OSBacktrace(tr
->pc
, CTRACE_STACK_SIZE
);