/*
 * dhcpcd - route management
 * SPDX-License-Identifier: BSD-2-Clause
 * Copyright (c) 2006-2025 Roy Marples <roy@marples.name>
 * All rights reserved

 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <syslog.h>
#include <unistd.h>

#include "config.h" // IWYU pragma: keep
#include "common.h"
#include "dhcpcd.h"
#include "if-options.h"
#include "if.h"
#include "ipv4.h"
#include "ipv4ll.h"
#include "ipv6.h"
#include "logerr.h"
#include "route.h"
#include "sa.h"

/* Needed for NetBSD-6, 7 and 8. */
#ifndef RB_TREE_FOREACH_SAFE
#ifndef RB_TREE_PREV
#define RB_TREE_NEXT(T, N) rb_tree_iterate((T), (N), RB_DIR_RIGHT)
#define RB_TREE_PREV(T, N) rb_tree_iterate((T), (N), RB_DIR_LEFT)
#endif
#define RB_TREE_FOREACH_SAFE(N, T, S)                                        \
	for ((N) = RB_TREE_MIN(T); (N) && ((S) = RB_TREE_NEXT((T), (N)), 1); \
	    (N) = (S))
#define RB_TREE_FOREACH_REVERSE_SAFE(N, T, S)                                \
	for ((N) = RB_TREE_MAX(T); (N) && ((S) = RB_TREE_PREV((T), (N)), 1); \
	    (N) = (S))
#endif

/*
 * For our purposes, RTF_CONNECTED is the same as RTF_CLONING.
 * If we change the route, we want to flush anything dynamically created.
 */
#if defined(BSD) && !defined(RTF_CLONING) && defined(RTF_CONNECTED)
#define RTF_CLONING RTF_CONNECTED
#endif

#ifdef RT_FREE_ROUTE_TABLE_STATS
static size_t croutes;
static size_t nroutes;
static size_t froutes;
static size_t mroutes;
#endif

static void
rt_maskedaddr(struct sockaddr *dst, const struct sockaddr *addr,
    const struct sockaddr *netmask)
{
	const char *addrp = addr->sa_data, *netmaskp = netmask->sa_data;
	char *dstp = dst->sa_data;
	const char *addre = (char *)dst + sa_len(addr);
	const char *netmaske = (char *)dst + MIN(sa_len(addr), sa_len(netmask));

	dst->sa_family = addr->sa_family;
#ifdef HAVE_SA_LEN
	dst->sa_len = addr->sa_len;
#endif

	if (sa_is_unspecified(netmask)) {
		if (addre > dstp)
			memcpy(dstp, addrp, (size_t)(addre - dstp));
		return;
	}

	while (dstp < netmaske)
		*dstp++ = *addrp++ & *netmaskp++;
	if (dstp < addre)
		memset(dstp, 0, (size_t)(addre - dstp));
}

/*
 * On some systems, host routes have no need for a netmask.
 * However DHCP specifies host routes using an all-ones netmask.
 * This handy function allows easy comparison when the two
 * differ.
 */
static int
rt_cmp_netmask(const struct rt *rt1, const struct rt *rt2)
{
	if (rt1->rt_flags & RTF_HOST && rt2->rt_flags & RTF_HOST)
		return 0;
	return sa_cmp(rt1->rt_netmask, rt2->rt_netmask);
}

int
rt_cmp_dest(const struct rt *rt1, const struct rt *rt2)
{
	struct sockaddr_storage ss1 = { .ss_family = AF_UNSPEC };
	struct sockaddr_storage ss2 = { .ss_family = AF_UNSPEC };
	struct sockaddr *ma1 = (struct sockaddr *)&ss1;
	struct sockaddr *ma2 = (struct sockaddr *)&ss2;
	int c;

	rt_maskedaddr(ma1, rt1->rt_dest, rt1->rt_netmask);
	rt_maskedaddr(ma2, rt2->rt_dest, rt2->rt_netmask);
	c = sa_cmp(ma1, ma2);
	if (c != 0)
		return c;

	return rt_cmp_netmask(rt1, rt2);
}

static int
rt_compare_os(__unused void *context, const void *node1, const void *node2)
{
	const struct rt *rt1 = node1, *rt2 = node2;
	int c;

	/* Sort by masked destination. */
	c = rt_cmp_dest(rt1, rt2);
	if (c != 0)
		return c;

#ifdef HAVE_ROUTE_METRIC
	c = (int)(rt1->rt_ifp->metric - rt2->rt_ifp->metric);
#endif
	return c;
}

static int
rt_compare_list(__unused void *context, const void *node1, const void *node2)
{
	const struct rt *rt1 = node1, *rt2 = node2;

	if (rt1->rt_order > rt2->rt_order)
		return 1;
	if (rt1->rt_order < rt2->rt_order)
		return -1;
	return 0;
}

static int
rt_compare_proto(void *context, const void *node1, const void *node2)
{
	const struct rt *rt1 = node1, *rt2 = node2;
	int c;
	struct interface *ifp1, *ifp2;

	assert(rt1->rt_ifp != NULL);
	assert(rt2->rt_ifp != NULL);
	ifp1 = rt1->rt_ifp;
	ifp2 = rt2->rt_ifp;

	/* Prefer interfaces with a carrier. */
	c = ifp1->carrier - ifp2->carrier;
	if (c != 0)
		return -c;

	/* Prefer roaming over non roaming if both carriers are down. */
	if (ifp1->carrier == LINK_DOWN && ifp2->carrier == LINK_DOWN) {
		bool roam1 = if_roaming(ifp1);
		bool roam2 = if_roaming(ifp2);

		if (roam1 != roam2)
			return roam1 ? 1 : -1;
	}

#ifdef INET
	/* IPv4LL routes always come last */
	if (rt1->rt_dflags & RTDF_IPV4LL && !(rt2->rt_dflags & RTDF_IPV4LL))
		return -1;
	else if (!(rt1->rt_dflags & RTDF_IPV4LL) &&
	    rt2->rt_dflags & RTDF_IPV4LL)
		return 1;
#endif

	/* Lower metric interfaces come first. */
	c = (int)(ifp1->metric - ifp2->metric);
	if (c != 0)
		return c;

	/* Finally the order in which the route was given to us. */
	return rt_compare_list(context, rt1, rt2);
}

static const rb_tree_ops_t rt_compare_os_ops = {
	.rbto_compare_nodes = rt_compare_os,
	.rbto_compare_key = rt_compare_os,
	.rbto_node_offset = offsetof(struct rt, rt_tree),
	.rbto_context = NULL
};

const rb_tree_ops_t rt_compare_list_ops = {
	.rbto_compare_nodes = rt_compare_list,
	.rbto_compare_key = rt_compare_list,
	.rbto_node_offset = offsetof(struct rt, rt_tree),
	.rbto_context = NULL
};

const rb_tree_ops_t rt_compare_proto_ops = {
	.rbto_compare_nodes = rt_compare_proto,
	.rbto_compare_key = rt_compare_proto,
	.rbto_node_offset = offsetof(struct rt, rt_tree),
	.rbto_context = NULL
};

#ifdef RT_FREE_ROUTE_TABLE
static int
rt_compare_free(__unused void *context, const void *node1, const void *node2)
{
	return node1 == node2 ? 0 : node1 < node2 ? -1 : 1;
}

static const rb_tree_ops_t rt_compare_free_ops = {
	.rbto_compare_nodes = rt_compare_free,
	.rbto_compare_key = rt_compare_free,
	.rbto_node_offset = offsetof(struct rt, rt_tree),
	.rbto_context = NULL
};
#endif

void
rt_init_routes(struct dhcpcd_ctx *ctx)
{
	rb_tree_init(&ctx->routes, &rt_compare_os_ops);
#ifdef RT_FREE_ROUTE_TABLE
	rb_tree_init(&ctx->froutes, &rt_compare_free_ops);
#endif
}

bool
rt_is_default(const struct rt *rt)
{
	return sa_is_unspecified(rt->rt_dest) &&
	    sa_is_unspecified(rt->rt_netmask);
}

static void
rt_desc(int loglevel, const char *cmd, const struct rt *rt)
{
	char dest[INET_MAX_ADDRSTRLEN], gateway[INET_MAX_ADDRSTRLEN];
	int prefix;
	const char *ifname;
	bool gateway_unspec;

	assert(cmd != NULL);
	assert(rt != NULL);

	sa_addrtop(rt->rt_dest, dest, sizeof(dest));
	prefix = sa_toprefix(rt->rt_netmask);
	sa_addrtop(rt->rt_gateway, gateway, sizeof(gateway));
	gateway_unspec = sa_is_unspecified(rt->rt_gateway);
	ifname = rt->rt_ifp == NULL ? "(null)" : rt->rt_ifp->name;

	if (rt->rt_flags & RTF_HOST) {
		if (gateway_unspec)
			logmessage(loglevel, "%s: %s host route to %s", ifname,
			    cmd, dest);
		else
			logmessage(loglevel, "%s: %s host route to %s via %s",
			    ifname, cmd, dest, gateway);
	} else if (rt_is_default(rt)) {
		if (gateway_unspec)
			logmessage(loglevel, "%s: %s default route", ifname,
			    cmd);
		else
			logmessage(loglevel, "%s: %s default route via %s",
			    ifname, cmd, gateway);
	} else if (gateway_unspec)
		logmessage(loglevel, "%s: %s%s route to %s/%d", ifname, cmd,
		    rt->rt_flags & RTF_REJECT ? " reject" : "", dest, prefix);
	else
		logmessage(loglevel, "%s: %s%s route to %s/%d via %s", ifname,
		    cmd, rt->rt_flags & RTF_REJECT ? " reject" : "", dest,
		    prefix, gateway);
}

void
rt_headclear0(struct dhcpcd_ctx *ctx, rb_tree_t *rts, int af)
{
	struct rt *rt, *rtn;

	if (rts == NULL)
		return;
#ifdef RT_FREE_ROUTE_TABLE
	if (ctx != NULL)
		assert(&ctx->froutes != rts);
#endif

	RB_TREE_FOREACH_SAFE(rt, rts, rtn)
	{
		if (af != AF_UNSPEC && rt->rt_dest->sa_family != af &&
		    rt->rt_gateway->sa_family != af)
			continue;
		rb_tree_remove_node(rts, rt);
		rt_free(rt);
	}
}

void
rt_headclear(rb_tree_t *rts, int af)
{
	struct rt *rt;

	if (rts == NULL || (rt = RB_TREE_MIN(rts)) == NULL)
		return;
	rt_headclear0(rt->rt_ifp ? rt->rt_ifp->ctx : NULL, rts, af);
}

static void
rt_headfree(rb_tree_t *rts)
{
	struct rt *rt;

	while ((rt = RB_TREE_MIN(rts)) != NULL) {
		rb_tree_remove_node(rts, rt);
		free(rt);
	}
}

void
rt_dispose(struct dhcpcd_ctx *ctx)
{
	assert(ctx != NULL);
	rt_headfree(&ctx->routes);
#ifdef RT_FREE_ROUTE_TABLE
	rt_headfree(&ctx->froutes);
#ifdef RT_FREE_ROUTE_TABLE_STATS
	logdebugx("free route list used %zu times", froutes);
	logdebugx("new routes from route free list %zu", nroutes);
	logdebugx("maximum route free list size %zu", mroutes);
#endif
#endif
}

static void
rt_setup_sa(struct rt *rt)
{
	rt->rt_dest = (struct sockaddr *)&rt->rt_ss_dest;
	rt->rt_netmask = (struct sockaddr *)&rt->rt_ss_netmask;
	rt->rt_gateway = (struct sockaddr *)&rt->rt_ss_gateway;
	rt->rt_ifa = (struct sockaddr *)&rt->rt_ss_ifa;
}

void
rt_init(struct rt *rt)
{
	memset(rt, 0, sizeof(*rt));
	rt_setup_sa(rt);
}

void
rt_copy(struct rt *dst, const struct rt *src)
{
	memcpy(dst, src, sizeof(*dst));
	rt_setup_sa(dst);
}

struct rt *
rt_new0(struct dhcpcd_ctx *ctx)
{
	struct rt *rt;

	assert(ctx != NULL);
#ifdef RT_FREE_ROUTE_TABLE
	if ((rt = RB_TREE_MIN(&ctx->froutes)) != NULL) {
		rb_tree_remove_node(&ctx->froutes, rt);
#ifdef RT_FREE_ROUTE_TABLE_STATS
		croutes--;
		nroutes++;
#endif
	} else
#endif
	    if ((rt = malloc(sizeof(*rt))) == NULL) {
		logerr(__func__);
		return NULL;
	}
	rt_init(rt);
	return rt;
}

void
rt_setif(struct rt *rt, struct interface *ifp)
{
	assert(rt != NULL);
	assert(ifp != NULL);
	rt->rt_ifp = ifp;
#ifdef HAVE_ROUTE_METRIC
	rt->rt_metric = ifp->metric;
	if (if_roaming(ifp))
		rt->rt_metric += RTMETRIC_ROAM;
#endif
}

struct rt *
rt_new(struct interface *ifp)
{
	struct rt *rt;

	assert(ifp != NULL);
	if ((rt = rt_new0(ifp->ctx)) == NULL)
		return NULL;
	rt_setif(rt, ifp);
	return rt;
}

struct rt *
rt_proto_add_ctx(rb_tree_t *tree, struct rt *rt, struct dhcpcd_ctx *ctx)
{
	rt->rt_order = ctx->rt_order++;
	if (rb_tree_insert_node(tree, rt) == rt)
		return rt;

	rt_free(rt);
	errno = EEXIST;
	return NULL;
}

struct rt *
rt_proto_add(rb_tree_t *tree, struct rt *rt)
{
	assert(rt->rt_ifp != NULL);
	return rt_proto_add_ctx(tree, rt, rt->rt_ifp->ctx);
}

void
rt_free(struct rt *rt)
{
#ifdef RT_FREE_ROUTE_TABLE
	struct dhcpcd_ctx *ctx;

	assert(rt != NULL);
	if (rt->rt_ifp == NULL) {
		free(rt);
		return;
	}

	ctx = rt->rt_ifp->ctx;
	rb_tree_insert_node(&ctx->froutes, rt);
#ifdef RT_FREE_ROUTE_TABLE_STATS
	croutes++;
	froutes++;
	if (croutes > mroutes)
		mroutes = croutes;
#endif
#else
	free(rt);
#endif
}

void
rt_freeif(struct interface *ifp)
{
	struct dhcpcd_ctx *ctx;
	struct rt *rt, *rtn;

	if (ifp == NULL)
		return;
	ctx = ifp->ctx;
	RB_TREE_FOREACH_SAFE(rt, &ctx->routes, rtn)
	{
		if (rt->rt_ifp == ifp) {
			rb_tree_remove_node(&ctx->routes, rt);
			rt_free(rt);
		}
	}
}

/* If something other than dhcpcd removes a route,
 * we need to remove it from our internal table. */
void
rt_recvrt(int cmd, const struct rt *rt, pid_t pid)
{
	struct dhcpcd_ctx *ctx;
	struct rt *f;

	assert(rt != NULL);
	assert(rt->rt_ifp != NULL);
	assert(rt->rt_ifp->ctx != NULL);

	ctx = rt->rt_ifp->ctx;

	switch (cmd) {
	case RTM_DELETE:
		f = rb_tree_find_node(&ctx->routes, rt);
		if (f != NULL) {
			char buf[32];

			rb_tree_remove_node(&ctx->routes, f);
			snprintf(buf, sizeof(buf), "pid %d deleted", (int)pid);
			rt_desc(LOG_WARNING, buf, f);
			rt_free(f);
		}
		break;
	}

#if defined(IPV4LL) && defined(HAVE_ROUTE_METRIC)
	if (rt->rt_dest->sa_family == AF_INET)
		ipv4ll_recvrt(cmd, rt);
#endif
}

/* Compare miscellaneous route details */
static int
rt_cmp_mtu(struct rt *nrt, struct rt *ort)
{
#if defined(__FreeBSD__) || defined(__DragonFly__)
	/* FreeBSD puts the interface MTU into the route MTU
	 * if the route does not define it's own. */
	unsigned int nmtu, omtu;

	nmtu = nrt->rt_mtu ? nrt->rt_mtu : (unsigned int)nrt->rt_ifp->mtu;
	omtu = ort->rt_mtu ? ort->rt_mtu : (unsigned int)ort->rt_ifp->mtu;
	if (omtu != nmtu)
		return 1;
#else
	if (ort->rt_mtu != nrt->rt_mtu)
		return 1;
#endif

	return 0;
}

#ifdef HAVE_ROUTE_LIFETIME
static int
rt_cmp_lifetime(struct rt *nrt, struct rt *ort)
{
	/* There might be a minor difference between kernel route
	 * lifetime and our lifetime due to processing times.
	 * We allow a small deviation to avoid needless route changes.
	 * dhcpcd will expire the route regardless of route lifetime support.
	 */
	struct timespec ts;
	uint32_t deviation;

	timespecsub(&nrt->rt_acquired, &ort->rt_acquired, &ts);
	if (ts.tv_sec < 0)
		ts.tv_sec = -ts.tv_sec;
	if (ts.tv_sec > RTLIFETIME_DEV_MAX)
		return 1;
	if (nrt->rt_lifetime > ort->rt_lifetime)
		deviation = nrt->rt_lifetime - ort->rt_lifetime;
	else
		deviation = ort->rt_lifetime - nrt->rt_lifetime;
	if (deviation > RTLIFETIME_DEV_MAX)
		return 1;

	return 0;
}
#endif

static bool
rt_add(rb_tree_t *kroutes, struct rt *nrt, struct rt *ort)
{
	struct dhcpcd_ctx *ctx;
	struct rt *krt;
	int loglevel = LOG_INFO;
	bool change, result = false;

	assert(nrt != NULL);
	ctx = nrt->rt_ifp->ctx;

	/*
	 * Don't install a gateway if not asked to.
	 * This option is mainly for VPN users who want their VPN to be the
	 * default route.
	 * Because VPN's generally don't care about route management
	 * beyond their own, a longer term solution would be to remove this
	 * and get the VPN to inject the default route into dhcpcd somehow.
	 */
	if (((nrt->rt_ifp->active &&
		 !(nrt->rt_ifp->options->options & DHCPCD_GATEWAY)) ||
		(!nrt->rt_ifp->active && !(ctx->options & DHCPCD_GATEWAY))) &&
	    sa_is_unspecified(nrt->rt_dest) &&
	    sa_is_unspecified(nrt->rt_netmask))
		return false;

	krt = rb_tree_find_node(kroutes, nrt);
	if (krt != NULL && krt->rt_ifp == nrt->rt_ifp &&
	    /* Only test flags dhcpcd controls */
	    (krt->rt_flags & (RTF_HOST | RTF_REJECT)) == nrt->rt_flags &&
#ifdef HAVE_ROUTE_METRIC
	    krt->rt_metric == nrt->rt_metric &&
#endif
	    sa_cmp(krt->rt_dest, nrt->rt_dest) == 0 &&
	    rt_cmp_netmask(krt, nrt) == 0 &&
	    sa_cmp(krt->rt_gateway, nrt->rt_gateway) == 0 &&
	    (nrt->rt_ifp->flags & IFF_LOOPBACK || rt_cmp_mtu(krt, nrt) == 0)) {
#ifdef HAVE_ROUTE_LIFETIME
		if (rt_cmp_lifetime(krt, nrt) == 0) {
			rt_desc(LOG_DEBUG, "keeping", krt);
			return true;
		} else
			loglevel = LOG_DEBUG;
#else
		rt_desc(LOG_DEBUG, "keeping", krt);
		return true;
#endif
	}

	rt_desc(loglevel, ort == NULL ? "adding" : "changing", nrt);

	change = krt != NULL;
#ifdef RTF_CLONING
	/* BSD can set routes to be cloning routes.
	 * Cloned routes inherit the parent flags.
	 * As such, we need to delete and re-add the route to flush children
	 * to correct the flags. */
	if (change && krt != NULL && krt->rt_flags & RTF_CLONING)
		change = false;
#endif
	/* Reject routes have a gateway, non reject routes don't.
	 * BSD kernels at least preserve RTF_GATEWAY so we need to punt it. */
	if (change && krt->rt_flags & RTF_REJECT &&
	    !(nrt->rt_flags & RTF_REJECT))
		change = false;

	if (change) {
		if (if_route(RTM_CHANGE, nrt) != -1) {
			result = true;
			goto out;
		}
		if (errno != ESRCH)
			logerr("if_route (CHG)");
	}

#ifdef HAVE_ROUTE_METRIC
	/* With route metrics, we can safely add the new route before
	 * deleting the old route. */
	if (if_route(RTM_ADD, nrt) != -1) {
		if (krt != NULL) {
			if (if_route(RTM_DELETE, krt) == -1 && errno != ESRCH)
				logerr("if_route (DEL)");
		}
		result = true;
		goto out;
	}

	/* If the kernel claims the route exists we need to rip out the
	 * old one first. */
	if (errno != EEXIST || ort == NULL)
		goto logerr;
#endif

	/* No route metrics, we need to delete the old route before
	 * adding the new one. */
#ifdef ROUTE_PER_GATEWAY
	errno = 0;
#endif
	if (krt != NULL) {
		if (if_route(RTM_DELETE, krt) == -1 && errno != ESRCH)
			logerr("if_route (DEL)");
	}
#ifdef ROUTE_PER_GATEWAY
	/* The OS allows many routes to the same dest with different gateways.
	 * dhcpcd does not support this yet, so for the time being just keep on
	 * deleting the route until there is an error. */
	if (krt != NULL && errno == 0) {
		for (;;) {
			if (if_route(RTM_DELETE, krt) == -1)
				break;
		}
	}
#endif

	/* Shouldn't need to check for EEXIST, but some kernels don't
	 * dump the subnet route just after we added the address. */
	if (if_route(RTM_ADD, nrt) != -1 || errno == EEXIST) {
		result = true;
		goto out;
	}

#ifdef HAVE_ROUTE_METRIC
logerr:
#endif
	logerr("if_route (ADD)");

out:
	if (krt != NULL) {
		rb_tree_remove_node(kroutes, krt);
		rt_free(krt);
	}
	return result;
}

static bool
rt_delete(struct rt *rt)
{
	int retval;

	rt_desc(LOG_INFO, "deleting", rt);
	retval = if_route(RTM_DELETE, rt) == -1 ? false : true;
	if (!retval && errno != ENOENT && errno != ESRCH)
		logerr(__func__);
	return retval;
}

static int
rt_cmp(const struct rt *r1, const struct rt *r2)
{
	if (r1->rt_ifp == r2->rt_ifp &&
#ifdef HAVE_ROUTE_METRIC
	    r1->rt_metric == r2->rt_metric &&
#endif
	    sa_cmp(r1->rt_gateway, r2->rt_gateway) == 0)
		return 0;
	return 1;
}

static bool
rt_doroute(rb_tree_t *kroutes, struct rt *rt)
{
	struct dhcpcd_ctx *ctx;
	struct rt * or ;

	ctx = rt->rt_ifp->ctx;
	/* Do we already manage it? */
	or = rb_tree_find_node(&ctx->routes, rt);
	if (or != NULL) {
		if (rt->rt_dflags & RTDF_FAKE)
			return true;
		if (or->rt_dflags & RTDF_FAKE || rt_cmp(rt, or) != 0 ||
		    (rt->rt_ifa->sa_family != AF_UNSPEC &&
			sa_cmp(or->rt_ifa, rt->rt_ifa) != 0) ||
#ifdef HAVE_ROUTE_LIFETIME
		    rt_cmp_lifetime(rt, or) != 0 ||
#endif
		    rt_cmp_mtu(rt, or) != 0) {
			if (!rt_add(kroutes, rt, or))
				return false;
		} else {
#ifdef HAVE_ROUTE_LIFETIME
			/* The existing kernel route matches what we want
			 * and the lifetime is inside the allowed deviation.
			 * Persist the original acquisition time so the
			 * deviaton can drop outside what is allowed and the
			 * kernel route is re-added with a new lifetime. */
			rt->rt_acquired = or->rt_acquired;
#endif
		}

		rb_tree_remove_node(&ctx->routes, or);
		rt_free(or);
	} else {
		if (rt->rt_dflags & RTDF_FAKE) {
			or = rb_tree_find_node(kroutes, rt);
			if (or == NULL)
				return false;
			if (rt_cmp(rt, or) == 0)
				return false;
		} else {
			if (!rt_add(kroutes, rt, NULL))
				return false;
		}
	}

	return true;
}

void
rt_build(struct dhcpcd_ctx *ctx, int af)
{
	rb_tree_t routes, added, kroutes;
	struct rt *rt, *rtn;
	unsigned long long o;

	/* When exiting with persistence, don't change any routing
	 * which maybe affected by interfaces stopping. */
	if ((ctx->options & (DHCPCD_EXITING | DHCPCD_PERSISTENT)) ==
	    (DHCPCD_EXITING | DHCPCD_PERSISTENT))
		return;

	rb_tree_init(&routes, &rt_compare_proto_ops);
	rb_tree_init(&added, &rt_compare_os_ops);
	rb_tree_init(&kroutes, &rt_compare_os_ops);
	if (if_initrt(ctx, &kroutes, af) != 0)
		logerr("%s: if_initrt", __func__);
	ctx->rt_order = 0;
	ctx->options |= DHCPCD_RTBUILD;

#ifdef INET
	if (!inet_getroutes(ctx, &routes))
		goto getfail;
#endif
#ifdef INET6
	if (!inet6_getroutes(ctx, &routes))
		goto getfail;
#endif

#ifdef HAVE_RT_MISSFILTER
	/* Rewind the miss filter */
	ctx->rt_missfilterlen = 0;
#endif

	RB_TREE_FOREACH_SAFE(rt, &routes, rtn)
	{
		if (rt->rt_ifp->active) {
			if (!(rt->rt_ifp->options->options & DHCPCD_CONFIGURE))
				continue;
		} else if (!(ctx->options & DHCPCD_CONFIGURE))
			continue;
#ifdef HAVE_RT_MISSFILTER
		if (rt_is_default(rt) &&
		    if_missfilter(rt->rt_ifp, rt->rt_gateway) == -1)
			logerr("if_missfilter");
#endif
		if ((rt->rt_dest->sa_family != af &&
			rt->rt_dest->sa_family != AF_UNSPEC) ||
		    (rt->rt_gateway->sa_family != af &&
			rt->rt_gateway->sa_family != AF_UNSPEC))
			continue;
		/* Is this route already in our table? */
		if (rb_tree_find_node(&added, rt) != NULL)
			continue;
		if (rt_doroute(&kroutes, rt)) {
			rb_tree_remove_node(&routes, rt);
			if (rb_tree_insert_node(&added, rt) != rt) {
				errno = EEXIST;
				logerr(__func__);
				rt_free(rt);
			}
		}
	}

#ifdef HAVE_RT_MISSFILTER
	if (!(ctx->options & DHCPCD_EXITING) &&
	    if_missfilter_apply(ctx) == -1 && errno != ENOTSUP)
		logerr("if_missfilter_apply");
#endif

	/* Remove old routes we used to manage. */
	RB_TREE_FOREACH_REVERSE_SAFE(rt, &ctx->routes, rtn)
	{
		if ((rt->rt_dest->sa_family != af &&
			rt->rt_dest->sa_family != AF_UNSPEC) ||
		    (rt->rt_gateway->sa_family != af &&
			rt->rt_gateway->sa_family != AF_UNSPEC))
			continue;
		rb_tree_remove_node(&ctx->routes, rt);
		if (rb_tree_find_node(&added, rt) == NULL) {
			o = rt->rt_ifp->options ? rt->rt_ifp->options->options :
						  ctx->options;
			if ((o & (DHCPCD_EXITING | DHCPCD_PERSISTENT)) !=
			    (DHCPCD_EXITING | DHCPCD_PERSISTENT))
				rt_delete(rt);
		}
		rt_free(rt);
	}

	/* XXX This needs to be optimised. */
	while ((rt = RB_TREE_MIN(&added)) != NULL) {
		rb_tree_remove_node(&added, rt);
		if (rb_tree_insert_node(&ctx->routes, rt) != rt) {
			errno = EEXIST;
			logerr(__func__);
			rt_free(rt);
		}
	}

getfail:
	rt_headclear(&routes, AF_UNSPEC);
	rt_headclear(&kroutes, AF_UNSPEC);
}
