1 /* SPDX-License-Identifier: BSD-2-Clause */
3 * dhcpcd - route management
4 * Copyright (c) 2006-2020 Roy Marples <roy@marples.name>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
42 #include "if-options.h"
50 /* Needed for NetBSD-6, 7 and 8. */
51 #ifndef RB_TREE_FOREACH_SAFE
53 #define RB_TREE_NEXT(T, N) rb_tree_iterate((T), (N), RB_DIR_RIGHT)
54 #define RB_TREE_PREV(T, N) rb_tree_iterate((T), (N), RB_DIR_LEFT)
56 #define RB_TREE_FOREACH_SAFE(N, T, S) \
57 for ((N) = RB_TREE_MIN(T); \
58 (N) && ((S) = RB_TREE_NEXT((T), (N)), 1); \
60 #define RB_TREE_FOREACH_REVERSE_SAFE(N, T, S) \
61 for ((N) = RB_TREE_MAX(T); \
62 (N) && ((S) = RB_TREE_PREV((T), (N)), 1); \
66 #ifdef RT_FREE_ROUTE_TABLE_STATS
67 static size_t croutes
;
68 static size_t nroutes
;
69 static size_t froutes
;
70 static size_t mroutes
;
74 rt_maskedaddr(struct sockaddr
*dst
,
75 const struct sockaddr
*addr
, const struct sockaddr
*netmask
)
77 const char *addrp
= addr
->sa_data
, *netmaskp
= netmask
->sa_data
;
78 char *dstp
= dst
->sa_data
;
79 const char *addre
= (char *)dst
+ sa_len(addr
);
80 const char *netmaske
= (char *)dst
+ MIN(sa_len(addr
), sa_len(netmask
));
82 dst
->sa_family
= addr
->sa_family
;
84 dst
->sa_len
= addr
->sa_len
;
87 if (sa_is_unspecified(netmask
)) {
89 memcpy(dstp
, addrp
, (size_t)(addre
- dstp
));
93 while (dstp
< netmaske
)
94 *dstp
++ = *addrp
++ & *netmaskp
++;
96 memset(dstp
, 0, (size_t)(addre
- dstp
));
100 rt_cmp_dest(const struct rt
*rt1
, const struct rt
*rt2
)
102 union sa_ss ma1
= { .sa
.sa_family
= AF_UNSPEC
};
103 union sa_ss ma2
= { .sa
.sa_family
= AF_UNSPEC
};
105 rt_maskedaddr(&ma1
.sa
, &rt1
->rt_dest
, &rt1
->rt_netmask
);
106 rt_maskedaddr(&ma2
.sa
, &rt2
->rt_dest
, &rt2
->rt_netmask
);
107 return sa_cmp(&ma1
.sa
, &ma2
.sa
);
111 * On some systems, host routes have no need for a netmask.
112 * However DHCP specifies host routes using an all-ones netmask.
113 * This handy function allows easy comparison when the two
117 rt_cmp_netmask(const struct rt
*rt1
, const struct rt
*rt2
)
120 if (rt1
->rt_flags
& RTF_HOST
&& rt2
->rt_flags
& RTF_HOST
)
122 return sa_cmp(&rt1
->rt_netmask
, &rt2
->rt_netmask
);
126 rt_compare_os(__unused
void *context
, const void *node1
, const void *node2
)
128 const struct rt
*rt1
= node1
, *rt2
= node2
;
131 /* Sort by masked destination. */
132 c
= rt_cmp_dest(rt1
, rt2
);
136 #ifdef HAVE_ROUTE_METRIC
137 c
= (int)(rt1
->rt_ifp
->metric
- rt2
->rt_ifp
->metric
);
143 rt_compare_list(__unused
void *context
, const void *node1
, const void *node2
)
145 const struct rt
*rt1
= node1
, *rt2
= node2
;
147 if (rt1
->rt_order
> rt2
->rt_order
)
149 if (rt1
->rt_order
< rt2
->rt_order
)
155 rt_compare_proto(void *context
, const void *node1
, const void *node2
)
157 const struct rt
*rt1
= node1
, *rt2
= node2
;
159 struct interface
*ifp1
, *ifp2
;
161 assert(rt1
->rt_ifp
!= NULL
);
162 assert(rt2
->rt_ifp
!= NULL
);
166 /* Prefer interfaces with a carrier. */
167 c
= ifp1
->carrier
- ifp2
->carrier
;
172 /* IPv4LL routes always come last */
173 if (rt1
->rt_dflags
& RTDF_IPV4LL
&& !(rt2
->rt_dflags
& RTDF_IPV4LL
))
175 else if (!(rt1
->rt_dflags
& RTDF_IPV4LL
) && rt2
->rt_dflags
& RTDF_IPV4LL
)
179 /* Lower metric interfaces come first. */
180 c
= (int)(ifp1
->metric
- ifp2
->metric
);
184 /* Finally the order in which the route was given to us. */
185 return rt_compare_list(context
, rt1
, rt2
);
188 static const rb_tree_ops_t rt_compare_os_ops
= {
189 .rbto_compare_nodes
= rt_compare_os
,
190 .rbto_compare_key
= rt_compare_os
,
191 .rbto_node_offset
= offsetof(struct rt
, rt_tree
),
195 const rb_tree_ops_t rt_compare_list_ops
= {
196 .rbto_compare_nodes
= rt_compare_list
,
197 .rbto_compare_key
= rt_compare_list
,
198 .rbto_node_offset
= offsetof(struct rt
, rt_tree
),
202 const rb_tree_ops_t rt_compare_proto_ops
= {
203 .rbto_compare_nodes
= rt_compare_proto
,
204 .rbto_compare_key
= rt_compare_proto
,
205 .rbto_node_offset
= offsetof(struct rt
, rt_tree
),
209 #ifdef RT_FREE_ROUTE_TABLE
211 rt_compare_free(__unused
void *context
, const void *node1
, const void *node2
)
214 return node1
== node2
? 0 : node1
< node2
? -1 : 1;
217 static const rb_tree_ops_t rt_compare_free_ops
= {
218 .rbto_compare_nodes
= rt_compare_free
,
219 .rbto_compare_key
= rt_compare_free
,
220 .rbto_node_offset
= offsetof(struct rt
, rt_tree
),
226 rt_init(struct dhcpcd_ctx
*ctx
)
229 rb_tree_init(&ctx
->routes
, &rt_compare_os_ops
);
230 #ifdef RT_FREE_ROUTE_TABLE
231 rb_tree_init(&ctx
->froutes
, &rt_compare_free_ops
);
236 rt_is_default(const struct rt
*rt
)
239 return sa_is_unspecified(&rt
->rt_dest
) &&
240 sa_is_unspecified(&rt
->rt_netmask
);
244 rt_desc(const char *cmd
, const struct rt
*rt
)
246 char dest
[INET_MAX_ADDRSTRLEN
], gateway
[INET_MAX_ADDRSTRLEN
];
254 sa_addrtop(&rt
->rt_dest
, dest
, sizeof(dest
));
255 prefix
= sa_toprefix(&rt
->rt_netmask
);
256 sa_addrtop(&rt
->rt_gateway
, gateway
, sizeof(gateway
));
257 gateway_unspec
= sa_is_unspecified(&rt
->rt_gateway
);
258 ifname
= rt
->rt_ifp
== NULL
? "(null)" : rt
->rt_ifp
->name
;
260 if (rt
->rt_flags
& RTF_HOST
) {
262 loginfox("%s: %s host route to %s",
265 loginfox("%s: %s host route to %s via %s",
266 ifname
, cmd
, dest
, gateway
);
267 } else if (rt_is_default(rt
)) {
269 loginfox("%s: %s default route",
272 loginfox("%s: %s default route via %s",
273 ifname
, cmd
, gateway
);
274 } else if (gateway_unspec
)
275 loginfox("%s: %s%s route to %s/%d",
277 rt
->rt_flags
& RTF_REJECT
? " reject" : "",
280 loginfox("%s: %s%s route to %s/%d via %s",
282 rt
->rt_flags
& RTF_REJECT
? " reject" : "",
283 dest
, prefix
, gateway
);
287 rt_headclear0(struct dhcpcd_ctx
*ctx
, rb_tree_t
*rts
, int af
)
294 #ifdef RT_FREE_ROUTE_TABLE
295 assert(&ctx
->froutes
!= rts
);
298 RB_TREE_FOREACH_SAFE(rt
, rts
, rtn
) {
299 if (af
!= AF_UNSPEC
&&
300 rt
->rt_dest
.sa_family
!= af
&&
301 rt
->rt_gateway
.sa_family
!= af
)
303 rb_tree_remove_node(rts
, rt
);
309 rt_headclear(rb_tree_t
*rts
, int af
)
313 if (rts
== NULL
|| (rt
= RB_TREE_MIN(rts
)) == NULL
)
315 rt_headclear0(rt
->rt_ifp
->ctx
, rts
, af
);
319 rt_headfree(rb_tree_t
*rts
)
323 while ((rt
= RB_TREE_MIN(rts
)) != NULL
) {
324 rb_tree_remove_node(rts
, rt
);
330 rt_dispose(struct dhcpcd_ctx
*ctx
)
334 rt_headfree(&ctx
->routes
);
335 #ifdef RT_FREE_ROUTE_TABLE
336 rt_headfree(&ctx
->froutes
);
337 #ifdef RT_FREE_ROUTE_TABLE_STATS
338 logdebugx("free route list used %zu times", froutes
);
339 logdebugx("new routes from route free list %zu", nroutes
);
340 logdebugx("maximum route free list size %zu", mroutes
);
346 rt_new0(struct dhcpcd_ctx
*ctx
)
351 #ifdef RT_FREE_ROUTE_TABLE
352 if ((rt
= RB_TREE_MIN(&ctx
->froutes
)) != NULL
) {
353 rb_tree_remove_node(&ctx
->froutes
, rt
);
354 #ifdef RT_FREE_ROUTE_TABLE_STATS
360 if ((rt
= malloc(sizeof(*rt
))) == NULL
) {
364 memset(rt
, 0, sizeof(*rt
));
369 rt_setif(struct rt
*rt
, struct interface
*ifp
)
375 #ifdef HAVE_ROUTE_METRIC
376 rt
->rt_metric
= ifp
->metric
;
381 rt_new(struct interface
*ifp
)
386 if ((rt
= rt_new0(ifp
->ctx
)) == NULL
)
393 rt_proto_add_ctx(rb_tree_t
*tree
, struct rt
*rt
, struct dhcpcd_ctx
*ctx
)
396 rt
->rt_order
= ctx
->rt_order
++;
397 if (rb_tree_insert_node(tree
, rt
) == rt
)
405 rt_proto_add(rb_tree_t
*tree
, struct rt
*rt
)
408 assert (rt
->rt_ifp
!= NULL
);
409 return rt_proto_add_ctx(tree
, rt
, rt
->rt_ifp
->ctx
);
413 rt_free(struct rt
*rt
)
415 #ifdef RT_FREE_ROUTE_TABLE
416 struct dhcpcd_ctx
*ctx
;
419 if (rt
->rt_ifp
== NULL
) {
424 ctx
= rt
->rt_ifp
->ctx
;
425 rb_tree_insert_node(&ctx
->froutes
, rt
);
426 #ifdef RT_FREE_ROUTE_TABLE_STATS
429 if (croutes
> mroutes
)
438 rt_freeif(struct interface
*ifp
)
440 struct dhcpcd_ctx
*ctx
;
446 RB_TREE_FOREACH_SAFE(rt
, &ctx
->routes
, rtn
) {
447 if (rt
->rt_ifp
== ifp
) {
448 rb_tree_remove_node(&ctx
->routes
, rt
);
454 /* If something other than dhcpcd removes a route,
455 * we need to remove it from our internal table. */
457 rt_recvrt(int cmd
, const struct rt
*rt
, pid_t pid
)
459 struct dhcpcd_ctx
*ctx
;
463 assert(rt
->rt_ifp
!= NULL
);
464 assert(rt
->rt_ifp
->ctx
!= NULL
);
466 ctx
= rt
->rt_ifp
->ctx
;
470 f
= rb_tree_find_node(&ctx
->routes
, rt
);
474 rb_tree_remove_node(&ctx
->routes
, f
);
475 snprintf(buf
, sizeof(buf
), "pid %d deleted", pid
);
482 #if defined(IPV4LL) && defined(HAVE_ROUTE_METRIC)
483 if (rt
->rt_dest
.sa_family
== AF_INET
)
484 ipv4ll_recvrt(cmd
, rt
);
489 rt_add(rb_tree_t
*kroutes
, struct rt
*nrt
, struct rt
*ort
)
491 struct dhcpcd_ctx
*ctx
;
492 bool change
, kroute
, result
;
495 ctx
= nrt
->rt_ifp
->ctx
;
498 * Don't install a gateway if not asked to.
499 * This option is mainly for VPN users who want their VPN to be the
501 * Because VPN's generally don't care about route management
502 * beyond their own, a longer term solution would be to remove this
503 * and get the VPN to inject the default route into dhcpcd somehow.
505 if (((nrt
->rt_ifp
->active
&&
506 !(nrt
->rt_ifp
->options
->options
& DHCPCD_GATEWAY
)) ||
507 (!nrt
->rt_ifp
->active
&& !(ctx
->options
& DHCPCD_GATEWAY
))) &&
508 sa_is_unspecified(&nrt
->rt_dest
) &&
509 sa_is_unspecified(&nrt
->rt_netmask
))
512 rt_desc(ort
== NULL
? "adding" : "changing", nrt
);
514 change
= kroute
= result
= false;
516 ort
= rb_tree_find_node(kroutes
, nrt
);
518 ((ort
->rt_flags
& RTF_REJECT
&&
519 nrt
->rt_flags
& RTF_REJECT
) ||
520 (ort
->rt_ifp
== nrt
->rt_ifp
&&
521 #ifdef HAVE_ROUTE_METRIC
522 ort
->rt_metric
== nrt
->rt_metric
&&
524 sa_cmp(&ort
->rt_gateway
, &nrt
->rt_gateway
) == 0)))
526 if (ort
->rt_mtu
== nrt
->rt_mtu
)
531 } else if (ort
->rt_dflags
& RTDF_FAKE
&&
532 !(nrt
->rt_dflags
& RTDF_FAKE
) &&
533 ort
->rt_ifp
== nrt
->rt_ifp
&&
534 #ifdef HAVE_ROUTE_METRIC
535 ort
->rt_metric
== nrt
->rt_metric
&&
537 sa_cmp(&ort
->rt_dest
, &nrt
->rt_dest
) == 0 &&
538 rt_cmp_netmask(ort
, nrt
) == 0 &&
539 sa_cmp(&ort
->rt_gateway
, &nrt
->rt_gateway
) == 0)
541 if (ort
->rt_mtu
== nrt
->rt_mtu
)
547 /* BSD can set routes to be cloning routes.
548 * Cloned routes inherit the parent flags.
549 * As such, we need to delete and re-add the route to flush children
550 * to correct the flags. */
551 if (change
&& ort
!= NULL
&& ort
->rt_flags
& RTF_CLONING
)
556 if (if_route(RTM_CHANGE
, nrt
) != -1) {
561 logerr("if_route (CHG)");
564 #ifdef HAVE_ROUTE_METRIC
565 /* With route metrics, we can safely add the new route before
566 * deleting the old route. */
567 if (if_route(RTM_ADD
, nrt
) != -1) {
569 if (if_route(RTM_DELETE
, ort
) == -1 && errno
!= ESRCH
)
570 logerr("if_route (DEL)");
576 /* If the kernel claims the route exists we need to rip out the
578 if (errno
!= EEXIST
|| ort
== NULL
)
582 /* No route metrics, we need to delete the old route before
583 * adding the new one. */
584 #ifdef ROUTE_PER_GATEWAY
588 if (if_route(RTM_DELETE
, ort
) == -1 && errno
!= ESRCH
)
589 logerr("if_route (DEL)");
593 #ifdef ROUTE_PER_GATEWAY
594 /* The OS allows many routes to the same dest with different gateways.
595 * dhcpcd does not support this yet, so for the time being just keep on
596 * deleting the route until there is an error. */
597 if (ort
!= NULL
&& errno
== 0) {
599 if (if_route(RTM_DELETE
, ort
) == -1)
605 /* Shouldn't need to check for EEXIST, but some kernels don't
606 * dump the subnet route just after we added the address. */
607 if (if_route(RTM_ADD
, nrt
) != -1 || errno
== EEXIST
) {
612 #ifdef HAVE_ROUTE_METRIC
615 logerr("if_route (ADD)");
619 rb_tree_remove_node(kroutes
, ort
);
626 rt_delete(struct rt
*rt
)
630 rt_desc("deleting", rt
);
631 retval
= if_route(RTM_DELETE
, rt
) == -1 ? false : true;
632 if (!retval
&& errno
!= ENOENT
&& errno
!= ESRCH
)
638 rt_cmp(const struct rt
*r1
, const struct rt
*r2
)
641 return (r1
->rt_ifp
== r2
->rt_ifp
&&
642 #ifdef HAVE_ROUTE_METRIC
643 r1
->rt_metric
== r2
->rt_metric
&&
645 sa_cmp(&r1
->rt_gateway
, &r2
->rt_gateway
) == 0);
649 rt_doroute(rb_tree_t
*kroutes
, struct rt
*rt
)
651 struct dhcpcd_ctx
*ctx
;
654 ctx
= rt
->rt_ifp
->ctx
;
655 /* Do we already manage it? */
656 or = rb_tree_find_node(&ctx
->routes
, rt
);
658 if (rt
->rt_dflags
& RTDF_FAKE
)
660 if (or->rt_dflags
& RTDF_FAKE
||
662 (rt
->rt_ifa
.sa_family
!= AF_UNSPEC
&&
663 sa_cmp(&or->rt_ifa
, &rt
->rt_ifa
) != 0) ||
664 or->rt_mtu
!= rt
->rt_mtu
)
666 if (!rt_add(kroutes
, rt
, or))
669 rb_tree_remove_node(&ctx
->routes
, or);
672 if (rt
->rt_dflags
& RTDF_FAKE
) {
673 or = rb_tree_find_node(kroutes
, rt
);
679 if (!rt_add(kroutes
, rt
, NULL
))
688 rt_build(struct dhcpcd_ctx
*ctx
, int af
)
690 rb_tree_t routes
, added
, kroutes
;
692 unsigned long long o
;
694 rb_tree_init(&routes
, &rt_compare_proto_ops
);
695 rb_tree_init(&added
, &rt_compare_os_ops
);
696 rb_tree_init(&kroutes
, &rt_compare_os_ops
);
697 if_initrt(ctx
, &kroutes
, af
);
699 ctx
->options
|= DHCPCD_RTBUILD
;
702 if (!inet_getroutes(ctx
, &routes
))
706 if (!inet6_getroutes(ctx
, &routes
))
711 /* Rewind the miss filter */
712 ctx
->rt_missfilterlen
= 0;
715 RB_TREE_FOREACH_SAFE(rt
, &routes
, rtn
) {
717 if (rt_is_default(rt
) &&
718 if_missfilter(rt
->rt_ifp
, &rt
->rt_gateway
) == -1)
719 logerr("if_missfilter");
721 if ((rt
->rt_dest
.sa_family
!= af
&&
722 rt
->rt_dest
.sa_family
!= AF_UNSPEC
) ||
723 (rt
->rt_gateway
.sa_family
!= af
&&
724 rt
->rt_gateway
.sa_family
!= AF_UNSPEC
))
726 /* Is this route already in our table? */
727 if (rb_tree_find_node(&added
, rt
) != NULL
)
729 if (rt_doroute(&kroutes
, rt
)) {
730 rb_tree_remove_node(&routes
, rt
);
731 if (rb_tree_insert_node(&added
, rt
) != rt
) {
740 if (if_missfilter_apply(ctx
) == -1 && errno
!= ENOTSUP
)
741 logerr("if_missfilter_apply");
744 /* Remove old routes we used to manage. */
745 RB_TREE_FOREACH_REVERSE_SAFE(rt
, &ctx
->routes
, rtn
) {
746 if ((rt
->rt_dest
.sa_family
!= af
&&
747 rt
->rt_dest
.sa_family
!= AF_UNSPEC
) ||
748 (rt
->rt_gateway
.sa_family
!= af
&&
749 rt
->rt_gateway
.sa_family
!= AF_UNSPEC
))
751 rb_tree_remove_node(&ctx
->routes
, rt
);
752 if (rb_tree_find_node(&added
, rt
) == NULL
) {
753 o
= rt
->rt_ifp
->options
?
754 rt
->rt_ifp
->options
->options
:
757 (DHCPCD_EXITING
| DHCPCD_PERSISTENT
)) !=
758 (DHCPCD_EXITING
| DHCPCD_PERSISTENT
))
764 /* XXX This needs to be optimised. */
765 while ((rt
= RB_TREE_MIN(&added
)) != NULL
) {
766 rb_tree_remove_node(&added
, rt
);
767 if (rb_tree_insert_node(&ctx
->routes
, rt
) != rt
) {
776 rt_headclear(&routes
, AF_UNSPEC
);
777 rt_headclear(&kroutes
, AF_UNSPEC
);