/* LWIP service - route.c - route management */
/*
 * This module provides a destination-based routing implementation, roughly
 * matching the routing as done traditionally by the BSDs and by current NetBSD
 * in particular.  As such, this implementation almost completely replaces
 * lwIP's own more limited (and less rigid) routing algorithms.  It does this
 * using a combination of overriding lwIP functions (ip4_route, ip6_route) with
 * weak-symbol patching, and lwIP-provided gateway hooks.  Especially the
 * former gives us a level of control that lwIP's routing hooks do not provide:
 * not only does such overriding give us the ability to flag that no route was
 * found at all, we also bypass a number of default decisions taken by lwIP
 * where the routing hooks are not called at all.
 *
 * As a result, the routing tables as visible to the user are an almost
 * completely accurate reflection of the routing decisions taken by this TCP/IP
 * stack in practice.  There is currently only one exception: for IPv4 gateway
 * selection, lwIP will bypass the gateway hook if the given address is on the
 * local subnet according to the locally assigned IP address and subnet mask.
 * This exception should practically affect noone, though.
 *
 * Our routing implementation differs from NetBSD's in various aspects, though.
 * Perhaps the most important one, also noted elsewhere, is that we do not
 * support the coexistence of an all-bits-set network route and a host route
 * for the same IP address.  If necessary, this issue can be resolved.
 *
 * We use a custom concept of "immutable" routes for local addresses, which are
 * a somewhat special case as explained in the ifaddr module.  Since those
 * RTF_LOCAL routes cannot be deleted, a small change is made to the route(8)
 * flush-all command to skip them.  Packets directed at local addresses on
 * non-loopback interfaces are handled in a way that differs from NetBSD's,
 * too.  This is explained in the ifdev module.
 *
 * The BSDs support special routes that reject or blackhole packets, based on
 * routing flags.  We support such routes as well, but implement them somewhat
 * differently from the BSDs: such packets always get routed over a loopback
 * interface (regardless of their associated interface), in order to save on
 * routing lookups for packets in the common case.
 *
 * As general rules of thumb: if there is no route to a destination, assignment
 * of a local address will already fail with a "no route to host" error.  If
 * there is an RTF_REJECT route, a local address will be assigned, but actual
 * packets will be routed to a loopback interface and result in a "no route to
 * host" error upon reception there - this is what NetBSD seems to do too, even
 * though the documentation says that RTF_REJECT routes generate ICMP messages
 * instead.  RTF_BLACKHOLE behaves similarly to RTF_REJECT, except that the
 * packet is simply discarded upon receipt by the loopback interface.
 *
 * In various places, both here and elsewhere, we check to make sure that on
 * routing and output, scoped IPv6 source and destination addresses never leave
 * their zone.  For example, a packet must not be sent to an outgoing interface
 * if its source address is a link-local address with a zone for another
 * interface.  lwIP does not check for such violations, and so we must make
 * sure that this does not happen ourselves.
 *
 * Normally, one would tell lwIP to use a particular default IPv4 gateway by
 * associating the gateway address to a particular interface, and then setting
 * that interface as default interface (netif_default).  We explicitly do
 * neither of these things.  Instead, the routing hooks should return the
 * default route whenever applicable, and the gateway hooks should return the
 * default route's gateway IP address whenever needed.
 *
 * Due to lwIP's limited set of error codes, we do not properly distinguish
 * between cases where EHOSTUNREACH or ENETUNREACH should be thrown, and throw
 * the former in most cases.
 */

#include "lwip.h"
#include "ifaddr.h"
#include "rttree.h"
#include "rtsock.h"
#include "route.h"
#include "lldata.h"

#include "lwip/nd6.h"

/*
 * The maximum number of uint8_t bytes needed to represent a routing address.
 * This value is the maximum of 4 (for IPv4) and 16 (for IPv6).
 */
#define ROUTE_ADDR_MAX	(MAX(IP4_BITS, IP6_BITS) / NBBY)

/*
 * We use a shared routing entry data structure for IPv4 and IPv6 routing
 * entries.  The result is cleaner code at the cost of (currently) about 2.3KB
 * of memory wasted (costing 12 bytes per address for three addresses for 64 of
 * the 128 routing entries that would be for IPv4), although with the benefit
 * that either address family may use more than half of the routing entries.
 * From that 2.3KB, 1KB can be reclaimed by moving the destination address and
 * mask into the rttree_entry data structure, at the cost of its generality.
 */
struct route_entry {
	struct rttree_entry re_entry;		/* routing tree entry */
	union pxfer_re_pu {
		struct ifdev *repu_ifdev;	/* associated interface */
		SIMPLEQ_ENTRY(route_entry) repu_next;	/* next free pointer */
	} re_pu;
	unsigned int re_flags;			/* routing flags (RTF_) */
	unsigned int re_use;			/* number of times used */
	uint8_t re_addr[ROUTE_ADDR_MAX];	/* destination address */
	uint8_t re_mask[ROUTE_ADDR_MAX];	/* destination mask */
	union ixfer_re_gu {
		ip4_addr_p_t regu_gw4;		/* gateway (IPv4) */
		ip6_addr_p_t regu_gw6;		/* gateway (IPv6) */
	} re_gu;
};
#define re_ifdev	re_pu.repu_ifdev
#define re_next		re_pu.repu_next
#define re_gw4		re_gu.regu_gw4
#define re_gw6		re_gu.regu_gw6

/* Routes for local addresses are immutable, for reasons explained in ifdev. */
#define route_is_immutable(route)	((route)->re_flags & RTF_LOCAL)

/*
 * We override a subset of the BSD routing flags in order to store our own
 * local settings.  In particular, we have to have a way to store whether a
 * route is for an IPv4 or IPv6 destination address.  We override BSD's
 * RTF_DONE flag for this: RTF_DONE is only used with routing sockets, and
 * never associated with actual routes.  In contrast, RTF_IPV6 is only used
 * with actual routes, and never sent across routing sockets.  In general,
 * overriding flags is preferable to adding new ones, as BSD might later add
 * more flags itself as well, while it can never remove existing flags.
 */
#define RTF_IPV6	RTF_DONE	/* route is for an IPv6 destination */

/* The total number of routing entries (IPv4 and IPv6 combined). */
#define NR_ROUTE_ENTRY	128

static struct route_entry route_array[NR_ROUTE_ENTRY];	/* routing entries */

static SIMPLEQ_HEAD(, route_entry) route_freelist;	/* free entry list */

/* The routing trees.  There are two: one for IPv4 and one for IPv6. */
#define ROUTE_TREE_V4	0
#define ROUTE_TREE_V6	1
#define NR_ROUTE_TREE	2

static struct rttree route_tree[NR_ROUTE_TREE];

/* We support a single cached routing entry per address family (IPv4, IPv6). */
static int rtcache_v4set;
static ip4_addr_t rtcache_v4addr;
static struct route_entry *rtcache_v4route;

static int rtcache_v6set;
static ip6_addr_t rtcache_v6addr;
static struct route_entry *rtcache_v6route;

/*
 * Initialize the routing cache.  There are a lot of trivial functions here,
 * but this is designed to be extended in the future.
 */
static void
rtcache_init(void)
{

	rtcache_v4set = FALSE;
	rtcache_v6set = FALSE;
}

/*
 * Look up the given IPv4 address in the routing cache.  If there is a match,
 * return TRUE with the associated route in 'route', possibly NULL if a
 * negative result was cached.  Return FALSE if the routing cache does not
 * cache the given IPv4 address.
 */
static inline int
rtcache_lookup_v4(const ip4_addr_t * ipaddr, struct route_entry ** route)
{

	if (rtcache_v4set && ip4_addr_cmp(&rtcache_v4addr, ipaddr)) {
		*route = rtcache_v4route;

		return TRUE;
	} else
		return FALSE;
}

/*
 * Add the given IPv4 address and the given routing entry (NULL for negative
 * caching) to the routing cache.
 */
static inline void
rtcache_add_v4(const ip4_addr_t * ipaddr, struct route_entry * route)
{

	rtcache_v4addr = *ipaddr;
	rtcache_v4route = route;
	rtcache_v4set = TRUE;
}

/*
 * Reset the IPv4 routing cache.
 */
static void
rtcache_reset_v4(void)
{

	rtcache_v4set = FALSE;
}

/*
 * Look up the given IPv6 address in the routing cache.  If there is a match,
 * return TRUE with the associated route in 'route', possibly NULL if a
 * negative result was cached.  Return FALSE if the routing cache does not
 * cache the given IPv6 address.
 */
static inline int
rtcache_lookup_v6(const ip6_addr_t * ipaddr, struct route_entry ** route)
{

	if (rtcache_v6set && ip6_addr_cmp(&rtcache_v6addr, ipaddr)) {
		*route = rtcache_v6route;

		return TRUE;
	} else
		return FALSE;
}

/*
 * Add the given IPv6 address and the given routing entry (NULL for negative
 * caching) to the routing cache.  Caching of scoped addresses without zones is
 * not supported.
 */
static inline void
rtcache_add_v6(const ip6_addr_t * ipaddr, struct route_entry * route)
{

	rtcache_v6addr = *ipaddr;
	rtcache_v6route = route;
	rtcache_v6set = TRUE;
}

/*
 * Reset the IPv6 routing cache.
 */
static void
rtcache_reset_v6(void)
{

	rtcache_v6set = FALSE;
}

/*
 * Initialize the routing module.
 */
void
route_init(void)
{
	unsigned int slot;

	/* Initialize the routing trees. */
	rttree_init(&route_tree[ROUTE_TREE_V4], IP4_BITS);
	rttree_init(&route_tree[ROUTE_TREE_V6], IP6_BITS);

	/* Initialize the list of free routing entries. */
	SIMPLEQ_INIT(&route_freelist);

	for (slot = 0; slot < __arraycount(route_array); slot++)
		SIMPLEQ_INSERT_TAIL(&route_freelist, &route_array[slot],
		    re_next);

	/* Reset the routing cache. */
	rtcache_init();
}

/*
 * Prepare for a routing tree operation by converting the given IPv4 address
 * into a raw address that can be used in that routing tree operation.
 */
static inline void
route_prepare_v4(const ip4_addr_t * ip4addr, uint8_t rtaddr[ROUTE_ADDR_MAX])
{
	uint32_t val;

	val = ip4_addr_get_u32(ip4addr);

	memcpy(rtaddr, &val, sizeof(val));
}

/*
 * Prepare for a routing tree operation by converting the given IPv6 address
 * into a raw address that can be used in that routing tree operation.  If the
 * given prefix length allows for it, also incorporate the address zone.
 */
static inline void
route_prepare_v6(const ip6_addr_t * ip6addr, unsigned int prefix,
	uint8_t rtaddr[ROUTE_ADDR_MAX])
{

	assert(sizeof(ip6addr->addr) == IP6_BITS / NBBY);

	/*
	 * TODO: in most cases, we could actually return a pointer to the
	 * address contained in the given lwIP IP address structure.  However,
	 * doing so would make a lot things quite a bit messier around here,
	 * but the small performance gain may still make it worth it.
	 */
	memcpy(rtaddr, ip6addr->addr, sizeof(ip6addr->addr));

	/*
	 * Embed the zone ID into the address, KAME style.  This is the
	 * easiest way to have link-local addresses for multiple interfaces
	 * coexist in a single routing tree.  Do this only if the full zone ID
	 * would be included in the prefix though, or we might de-normalize the
	 * address.
	 */
	if (ip6_addr_has_zone(ip6addr) && prefix >= 32)
		rtaddr[3] = ip6_addr_zone(ip6addr);
}

/*
 * Prepare for a routing tree operation by converting the given IP address into
 * a raw address that can be used in that routing tree operation.  The given
 * address's zone ID is embedded "KAME-style" into the raw (IPv6) address when
 * applicable and if the given prefix length allows for it.  Return the index
 * of the routing tree to use (ROUTE_TREE_V4 or ROUTE_TREE_V6).
 */
static unsigned int
route_prepare(const ip_addr_t * ipaddr, unsigned int prefix,
	uint8_t rtaddr[ROUTE_ADDR_MAX])
{

	switch (IP_GET_TYPE(ipaddr)) {
	case IPADDR_TYPE_V4:
		route_prepare_v4(ip_2_ip4(ipaddr), rtaddr);

		return ROUTE_TREE_V4;

	case IPADDR_TYPE_V6:
		route_prepare_v6(ip_2_ip6(ipaddr), prefix, rtaddr);

		return ROUTE_TREE_V6;

	default:
		panic("unknown IP address type: %u", IP_GET_TYPE(ipaddr));
	}
}

/*
 * The given routing tree (ROUTE_TREE_V4 or ROUTE_TREE_V6) has been updated.
 * Invalidate any cache entries that may now have become stale, both locally
 * and in lwIP.
 */
static void
route_updated(unsigned int tree)
{

	if (tree == ROUTE_TREE_V6) {
		rtcache_reset_v6();

		/*
		 * Also clear the lwIP ND6 destination cache, which may now
		 * contain entries for the wrong gateway.
		 */
		nd6_clear_destination_cache();
	} else
		rtcache_reset_v4();
}

/*
 * Add a route to the appropriate routing table.  The address, address zone,
 * prefix, and RTF_HOST flag in the flags field make up the identity of the
 * route.  If the flags field contains RTF_GATEWAY, a gateway must be given;
 * otherwise, it must be NULL.  The route is associated with the given
 * interface, which may not be NULL.  The caller must ensure that the flags
 * field does not contain unsupported flags.  On success, return OK, and also
 * also announce the addition.  On failure, return a negative error code.
 */
int
route_add(const ip_addr_t * addr, unsigned int prefix,
	const ip_addr_t * gateway, struct ifdev * ifdev, unsigned int flags,
	const struct rtsock_request * rtr)
{
	struct route_entry *route;
	unsigned int tree, byte;
	int r;

	assert(flags & RTF_UP);
	assert(!!(flags & RTF_GATEWAY) == (gateway != NULL));
	assert(ifdev != NULL);

	/* Get a routing entry, if any are available. */
	if (SIMPLEQ_EMPTY(&route_freelist))
		return ENOBUFS;

	route = SIMPLEQ_FIRST(&route_freelist);

	/*
	 * Perform sanity checks on the input, and fill in enough of the
	 * routing entry to be able to try and add it to the routing tree.
	 */
	memset(route->re_addr, 0, sizeof(route->re_addr));

	tree = route_prepare(addr, prefix, route->re_addr);

	switch (tree) {
	case ROUTE_TREE_V4:
		if (prefix > IP4_BITS ||
		    (prefix != IP4_BITS && (flags & RTF_HOST)))
			return EINVAL;

		flags &= ~RTF_IPV6;

		break;

	case ROUTE_TREE_V6:
		if (prefix > IP6_BITS ||
		    (prefix != IP6_BITS && (flags & RTF_HOST)))
			return EINVAL;

		flags |= RTF_IPV6;

		break;

	default:
		return EINVAL;
	}

	/* Generate the (raw) network mask.  This is protocol agnostic! */
	addr_make_netmask(route->re_mask, sizeof(route->re_mask), prefix);

	/* The given address must be normalized to its mask. */
	for (byte = 0; byte < __arraycount(route->re_addr); byte++)
		if ((route->re_addr[byte] & ~route->re_mask[byte]) != 0)
			return EINVAL;

	/*
	 * Attempt to add the routing entry.  Host-type entries do not have an
	 * associated mask, enabling ever-so-slightly faster matching.
	 */
	if ((r = rttree_add(&route_tree[tree], &route->re_entry,
	    route->re_addr, (flags & RTF_HOST) ? NULL : route->re_mask,
	    prefix)) != OK)
		return r;

	/*
	 * Success.  Finish the routing entry.  Remove the entry from the free
	 * list before assigning re_ifdev, as these two use the same memory.
	 */
	SIMPLEQ_REMOVE_HEAD(&route_freelist, re_next);

	route->re_ifdev = ifdev;
	route->re_flags = flags;

	/*
	 * Store the gateway if one is given.  Store the address in lwIP format
	 * because that is the easiest way use it later again.  Store it as a
	 * union to keep the route entry structure as small as possible.  Store
	 * the address without its zone, because the gateway's address zone is
	 * implied by its associated ifdev.
	 *
	 * If no gateway is given, this is a link-type route, i.e., a route for
	 * a local network, with all nodes directly connected and reachable.
	 */
	if (flags & RTF_GATEWAY) {
		if (flags & RTF_IPV6)
			ip6_addr_copy_to_packed(route->re_gw6,
			    *ip_2_ip6(gateway));
		else
			ip4_addr_copy(route->re_gw4, *ip_2_ip4(gateway));
	}

	/* We have made routing changes. */
	route_updated(tree);

	/* Announce the route addition. */
	rtsock_msg_route(route, RTM_ADD, rtr);

	return OK;
}

/*
 * Check whether it is possible to add a route for the given destination to the
 * corresponding routing table, that is, a subsequent route_add() call for this
 * destination address is guaranteed to succeed (if all its parameters are
 * valid).  Return TRUE if adding the route is guaranteed to succeed, or FALSE
 * if creating a route for the given destination would fail.
 */
int
route_can_add(const ip_addr_t * addr, unsigned int prefix,
	int is_host __unused)
{
	uint8_t rtaddr[ROUTE_ADDR_MAX];
	unsigned int tree;

	tree = route_prepare(addr, prefix, rtaddr);

	/*
	 * The corresponding routing tree must not already contain an exact
	 * match for the destination.  If the routing tree implementation is
	 * ever extended with support for coexisting host and net entries with
	 * the same prefix, we should also pass in 'is_host' here.
	 */
	if (rttree_lookup_exact(&route_tree[tree], rtaddr, prefix) != NULL)
		return FALSE;

	/* There must be a routing entry on the free list as well. */
	return !SIMPLEQ_EMPTY(&route_freelist);
}

/*
 * Find a route with the exact given route identity.  Return the route if
 * found, or NULL if no route exists with this identity.
 */
struct route_entry *
route_find(const ip_addr_t * addr, unsigned int prefix, int is_host)
{
	struct rttree_entry *entry;
	struct route_entry *route;
	uint8_t rtaddr[ROUTE_ADDR_MAX];
	unsigned int tree;

	tree = route_prepare(addr, prefix, rtaddr);

	entry = rttree_lookup_exact(&route_tree[tree], rtaddr, prefix);
	if (entry == NULL)
		return NULL;

	route = (struct route_entry *)entry;

	/*
	 * As long as the routing tree code does not support coexisting host
	 * and net entries with the same prefix, we have to check the type.
	 */
	if (!!(route->re_flags & RTF_HOST) != is_host)
		return NULL;

	return route;
}

/*
 * A route lookup failed for the given IP address.  Generate an RTM_MISS
 * message on routing sockets.
 */
static void
route_miss(const ip_addr_t * ipaddr)
{
	union sockaddr_any addr;
	socklen_t addr_len;

	addr_len = sizeof(addr);

	addr_put_inet(&addr.sa, &addr_len, ipaddr, TRUE /*kame*/, 0 /*port*/);

	rtsock_msg_miss(&addr.sa);
}

/*
 * A route lookup failed for the given IPv4 address.  Generate an RTM_MISS
 * message on routing sockets.
 */
static void
route_miss_v4(const ip4_addr_t * ip4addr)
{
	ip_addr_t ipaddr;

	ip_addr_copy_from_ip4(ipaddr, *ip4addr);

	route_miss(&ipaddr);
}

/*
 * A route lookup failed for the given IPv6 address.  Generate an RTM_MISS
 * message on routing sockets.
 */
static void
route_miss_v6(const ip6_addr_t * ip6addr)
{
	ip_addr_t ipaddr;

	ip_addr_copy_from_ip6(ipaddr, *ip6addr);

	route_miss(&ipaddr);
}

/*
 * Look up the most narrow matching routing entry for the given IPv4 address.
 * Return the routing entry if one exists at all, or NULL otherwise.  This
 * function performs caching.
 */
static inline struct route_entry *
route_lookup_v4(const ip4_addr_t * ip4addr)
{
	uint8_t rtaddr[ROUTE_ADDR_MAX];
	struct route_entry *route;

	/*
	 * Look up the route for the destination IP address, unless we have a
	 * cached route entry.  We cache negatives in order to avoid generating
	 * lots of RTM_MISS messages for the same destination in a row.
	 */
	if (rtcache_lookup_v4(ip4addr, &route))
		return route;

	route_prepare_v4(ip4addr, rtaddr);

	route = (struct route_entry *)
	    rttree_lookup_match(&route_tree[ROUTE_TREE_V4], rtaddr);

	/* Cache the result, even if we found no route. */
	rtcache_add_v4(ip4addr, route);

	return route;
}

/*
 * Look up the most narrow matching routing entry for the given IPv6 address,
 * taking into account its zone ID if applicable.  Return the routing entry if
 * one exists at all, or NULL otherwise.  This function performs caching.
 */
static inline struct route_entry *
route_lookup_v6(const ip6_addr_t * ip6addr)
{
	uint8_t rtaddr[ROUTE_ADDR_MAX];
	struct route_entry *route;
	int use_cache;

	/*
	 * We do not support caching of addresses that should have a zone but
	 * do not: in different contexts, such addresses could yield different
	 * routes.
	 */
	use_cache = !ip6_addr_lacks_zone(ip6addr, IP6_UNKNOWN);

	if (use_cache && rtcache_lookup_v6(ip6addr, &route))
		return route;

	route_prepare_v6(ip6addr, IP6_BITS, rtaddr);

	route = (struct route_entry *)
	    rttree_lookup_match(&route_tree[ROUTE_TREE_V6], rtaddr);

	/* Cache the result, even if no route was found. */
	if (use_cache)
		rtcache_add_v6(ip6addr, route);

	return route;
}

/*
 * Look up the most narrow matching routing entry for the given IP address,
 * taking into account its zone ID if applicable.  Return the routing entry if
 * one exists at all, or NULL otherwise.  This function performs caching.
 */
struct route_entry *
route_lookup(const ip_addr_t * addr)
{

	if (IP_IS_V4(addr))
		return route_lookup_v4(ip_2_ip4(addr));
	else
		return route_lookup_v6(ip_2_ip6(addr));
}

/*
 * Change an existing routing entry.  Its flags are always updated to the new
 * set of given flags, although certain flags are always preserved.  If the
 * new flags set has RTF_GATEWAY set and 'gateway' is not NULL, update the
 * gateway associated with the route.  If 'ifdev' is not NULL, reassociate the
 * route with the given interface; this will not affect the zone of the
 * route's destination address.  On success, return OK, and also announce the
 * change.  On failure, return a negative error code.
 */
static int
route_change(struct route_entry * route, const ip_addr_t * gateway,
	struct ifdev * ifdev, unsigned int flags,
	const struct rtsock_request * rtr)
{
	unsigned int tree, preserve;

	tree = (route->re_flags & RTF_IPV6) ? ROUTE_TREE_V6 : ROUTE_TREE_V4;

	/* Update the associated interface (only) if a new one is given. */
	if (ifdev != NULL)
		route->re_ifdev = ifdev;

	/*
	 * These flags may not be changed.  RTF_UP should always be set anyway.
	 * RTF_HOST and RTF_IPV6 are part of the route's identity.  RTF_LOCAL
	 * should be preserved as well, although we will not get here if either
	 * the old or the new flags have it set anyway.
	 */
	preserve = RTF_UP | RTF_HOST | RTF_IPV6 | RTF_LOCAL;

	/* Always update the flags.  There is no way not to. */
	route->re_flags = (route->re_flags & preserve) | (flags & ~preserve);

	/*
	 * If a new gateway is given *and* RTF_GATEWAY is set, update the
	 * gateway.  If RTF_GATEWAY is not set, this is a link-type route with
	 * no gateway.  If no new gateway is given, we keep the gateway as is.
	 */
	if (gateway != NULL && (flags & RTF_GATEWAY)) {
		if (flags & RTF_IPV6)
			ip6_addr_copy_to_packed(route->re_gw6,
			    *ip_2_ip6(gateway));
		else
			ip4_addr_copy(route->re_gw4, *ip_2_ip4(gateway));
	}

	/* We have made routing changes. */
	route_updated(tree);

	/* Announce the route change. */
	rtsock_msg_route(route, RTM_CHANGE, rtr);

	return OK;
}

/*
 * Delete the given route, and announce its deletion.
 */
void
route_delete(struct route_entry * route, const struct rtsock_request * rtr)
{
	unsigned int tree;

	/* First announce the deletion, while the route is still around. */
	tree = (route->re_flags & RTF_IPV6) ? ROUTE_TREE_V6 : ROUTE_TREE_V4;

	rtsock_msg_route(route, RTM_DELETE, rtr);

	/* Then actually delete the route. */
	rttree_delete(&route_tree[tree], &route->re_entry);

	SIMPLEQ_INSERT_HEAD(&route_freelist, route, re_next);

	/* We have made routing changes. */
	route_updated(tree);
}

/*
 * Delete all routes associated with the given interface, typically as part of
 * destroying the interface.
 */
void
route_clear(struct ifdev * ifdev)
{
	struct rttree_entry *entry, *parent;
	struct route_entry *route;
	unsigned int tree;

	/*
	 * Delete all routes associated with the given interface.  Fortunately,
	 * we need not also delete addresses zoned to the given interface,
	 * because no route can be created with a zone ID that does not match
	 * the associated interface.  That is the main reason why we ignore
	 * zone IDs for gateways when adding or changing routes..
	 */
	for (tree = 0; tree < NR_ROUTE_TREE; tree++) {
		parent = NULL;

		while ((entry = rttree_enum(&route_tree[tree],
		    parent)) != NULL) {
			route = (struct route_entry *)entry;

			if (route->re_ifdev == ifdev)
				route_delete(route, NULL /*request*/);
			else
				parent = entry;
		}
	}
}

/*
 * Process a routing command specifically for an IPv4 or IPv6 route, as one of
 * the specific continuations of processing started by route_process().  The
 * RTM_ routing command is given as 'type'.  The route destination is given as
 * 'dst_addr'; its address type determines whether the operation is for IPv4 or
 * IPv6.  The sockaddr structures for 'mask' and 'gateway' are passed on as is
 * and may have to be parsed here if not NULL.  'ifdev' is the interface to be
 * associated with a route; it is non-NULL only if an interface name (IFP) or
 * address (IFA) was given.  The RTF_ flags field 'flags' has been checked
 * against the globally supported flags, but may have to be checked for flags
 * that do not apply to IPv4/IPv6 routes.  Return OK or a negative error code,
 * following the same semantics as route_process().
 */
static int
route_process_inet(unsigned int type, const ip_addr_t * dst_addr,
	const struct sockaddr * mask, const struct sockaddr * gateway,
	struct ifdev * ifdev, unsigned int flags,
	const struct rtsock_request * rtr)
{
	struct route_entry *route;
	ip_addr_t gw_storage, *gw_addr;
	struct ifdev *ifdev2;
	uint32_t zone;
	unsigned int prefix;
	int r;

	assert(!(flags & RTF_LLDATA));

	if ((flags & (RTF_DYNAMIC | RTF_MODIFIED | RTF_DONE | RTF_XRESOLVE |
	    RTF_LLINFO | RTF_CLONED | RTF_SRC | RTF_ANNOUNCE |
	    RTF_BROADCAST)) != 0)
		return EINVAL;

	/*
	 * For network entries, a network mask must be provided in all cases.
	 * For host entries, the network mask is ignored, and we use a prefix
	 * with all bits set.
	 */
	if (!(flags & RTF_HOST)) {
		if (mask == NULL)
			return EINVAL;

		if ((r = addr_get_netmask(mask, mask->sa_len,
		    IP_GET_TYPE(dst_addr), &prefix, NULL /*ipaddr*/)) != OK)
			return r;
	} else {
		if (IP_IS_V4(dst_addr))
			prefix = IP4_BITS;
		else
			prefix = IP6_BITS;
	}

	gw_addr = NULL;

	/*
	 * Determine the gateway and interface for the routing entry, if
	 * applicable.
	 */
	if (type == RTM_ADD || type == RTM_CHANGE) {
		/*
		 * The RTF_UP flag must always be set, but only if the flags
		 * field is used at all.
		 */
		if (!(flags & RTF_UP))
			return EINVAL;

		if ((flags & RTF_GATEWAY) && gateway != NULL) {
			if ((r = addr_get_inet(gateway, gateway->sa_len,
			    IP_GET_TYPE(dst_addr), &gw_storage, TRUE /*kame*/,
			    NULL /*port*/)) != OK)
				return r;

			gw_addr = &gw_storage;

			/*
			 * We use the zone of the gateway to help determine the
			 * interface, but we do not reject a mismatching zone
			 * here.  The reason for this is that we do not want
			 * routes that have zones for an interface other than
			 * the one associated with the route, as that could
			 * create a world of trouble: packets leaving their
			 * zone, complications with cleaning up interfaces..
			 */
			if (IP_IS_V6(gw_addr) &&
			    ip6_addr_has_zone(ip_2_ip6(gw_addr))) {
				zone = ip6_addr_zone(ip_2_ip6(gw_addr));

				ifdev2 = ifdev_get_by_index(zone);

				if (ifdev != NULL && ifdev != ifdev2)
					return EINVAL;
				else
					ifdev = ifdev2;
			}

			/*
			 * If we still have no interface at this point, see if
			 * we can find one based on just the gateway address.
			 * See if a locally attached network owns the address.
			 * That may not succeed, leaving ifdev set to NULL.
			 */
			if (ifdev == NULL)
				ifdev = ifaddr_map_by_subnet(gw_addr);
		}

		/*
		 * When adding routes, all necessary information must be given.
		 * When changing routes, we can leave some settings as is.
		 */
		if (type == RTM_ADD) {
			if ((flags & RTF_GATEWAY) && gw_addr == NULL)
				return EINVAL;

			/* TODO: try harder to find a matching interface.. */
			if (ifdev == NULL)
				return ENETUNREACH;
		}
	}

	/*
	 * All route commands except RTM_ADD require that a route exists for
	 * the given identity, although RTM_GET, when requesting a host entry,
	 * may return a wider (network) route based on just the destination
	 * address.
	 */
	if (type != RTM_ADD) {
		/* For RTM_GET (only), a host query may return a net route. */
		if (type == RTM_GET && (flags & RTF_HOST))
			route = route_lookup(dst_addr);
		else
			route = route_find(dst_addr, prefix,
			    !!(flags & RTF_HOST));

		if (route == NULL)
			return ESRCH;
	} else
		route = NULL;

	/* Process the actual routing command. */
	switch (type) {
	case RTM_ADD:
		return route_add(dst_addr, prefix, gw_addr, ifdev, flags, rtr);

	case RTM_CHANGE:
		/* Routes for local addresses are immutable. */
		if (route_is_immutable(route))
			return EPERM;

		return route_change(route, gw_addr, ifdev, flags, rtr);

	case RTM_DELETE:
		/* Routes for local addresses are immutable. */
		if (route_is_immutable(route))
			return EPERM;

		route_delete(route, rtr);

		return OK;

	case RTM_LOCK:
		/*
		 * TODO: implement even the suggestion that we support this.
		 * For now, we do not keep per-route metrics, let alone change
		 * them dynamically ourselves, so "locking" metrics is really
		 * not a concept that applies to us.  We may however have to
		 * save the lock mask and return it in queries..
		 */
		/* FALLTHROUGH */
	case RTM_GET:
		/* Simply generate a message for the route we just found. */
		rtsock_msg_route(route, type, rtr);

		return OK;

	default:
		return EINVAL;
	}
}

/*
 * Process a routing command from a routing socket.  The RTM_ type of command
 * is given as 'type', and is one of RTM_ADD, RTM_CHANGE, RTM_DELETE, RTM_GET,
 * RTM_LOCK.  In addition, the function takes a set of sockaddr pointers as
 * provided by the routing command.  Each of these sockaddr pointers may be
 * NULL; if not NULL, the structure is at least large enough to contain the
 * address length (sa_len) and family (sa_family), and the length never exceeds
 * the amount of memory used to store the sockaddr structure.  However, the
 * length itself has not yet been checked against the expected protocol
 * structure and could even be zero.  The command's RTF_ routing flags and
 * metrics are provided as well.  On success, return OK, in which case the
 * caller assumes that a routing socket announcement for the processed command
 * has been sent already (passing on 'rtr' to the announcement function as is).
 * On failure, return a negative error code; in that case, the caller will send
 * a failure response on the original routing socket itself.
 */
int
route_process(unsigned int type, const struct sockaddr * dst,
	const struct sockaddr * mask, const struct sockaddr * gateway,
	const struct sockaddr * ifp, const struct sockaddr * ifa,
	unsigned int flags, unsigned long inits,
	const struct rt_metrics * rmx, const struct rtsock_request * rtr)
{
	struct ifdev *ifdev, *ifdev2;
	char name[IFNAMSIZ];
	ip_addr_t dst_addr, if_addr;
	uint32_t zone;
	uint8_t addr_type;
	int r;

	/*
	 * The identity of a route is determined by its destination address,
	 * destination zone, prefix length, and whether it is a host entry
	 * or not.  If it is a host entry (RTF_HOST is set), the prefix length
	 * is implied by the protocol; otherwise it should be obtained from the
	 * given netmask if necessary.  For link-local addresses, the zone ID
	 * must be embedded KAME-style in the destination address.  A
	 * destination address must always be given.  The destination address
	 * also determines the overall address family.
	 */
	if (dst == NULL)
		return EINVAL;

	switch (dst->sa_family) {
	case AF_INET:
		addr_type = IPADDR_TYPE_V4;
		break;
#ifdef INET6
	case AF_INET6:
		addr_type = IPADDR_TYPE_V6;
		break;
#endif /* INET6 */
	default:
		return EAFNOSUPPORT;
	}

	if ((r = addr_get_inet(dst, dst->sa_len, addr_type, &dst_addr,
	    TRUE /*kame*/, NULL /*port*/)) != OK)
		return r;

	/*
	 * Perform a generic test on the given flags.  This covers everything
	 * we support at all, plus a few flags we ignore.  Specific route types
	 * may have further restrictions; those tests are performed later.
	 */
	if ((flags & ~(RTF_UP | RTF_GATEWAY | RTF_HOST | RTF_REJECT |
	    RTF_CLONING | RTF_LLINFO | RTF_LLDATA | RTF_STATIC |
	    RTF_BLACKHOLE | RTF_CLONED | RTF_PROTO2 | RTF_PROTO1)) != 0)
		return EINVAL;

	ifdev = NULL;

	if (type == RTM_ADD || type == RTM_CHANGE) {
		/*
		 * If an interface address or name is given, use that to
		 * identify the target interface.  If both are given, make sure
		 * that both identify the same interface--a hopefully helpful
		 * feature to detect wrong route(8) usage (NetBSD simply takes
		 * IFP over IFA).  An empty interface name is ignored on the
		 * basis that libc link_addr(3) is broken.
		 */
		if (ifp != NULL) {
			if ((r = addr_get_link(ifp, ifp->sa_len, name,
			    sizeof(name), NULL /*hwaddr*/,
			    0 /*hwaddr_len*/)) != OK)
				return r;

			if (name[0] != '\0' &&
			    (ifdev = ifdev_find_by_name(name)) == NULL)
				return ENXIO;
		}

		if (ifa != NULL) {
			/*
			 * This is similar to retrieval of source addresses in
			 * ipsock, with the difference that we do not impose
			 * that a zone ID be given for link-local addresses.
			 */
			if ((r = addr_get_inet(ifa, ifa->sa_len, addr_type,
			    &if_addr, TRUE /*kame*/, NULL /*port*/)) != OK)
				return r;

			if ((ifdev2 = ifaddr_map_by_addr(&if_addr)) == NULL)
				return EADDRNOTAVAIL;

			if (ifdev != NULL && ifdev != ifdev2)
				return EINVAL;
			else
				ifdev = ifdev2;
		}

		/*
		 * If the destination address has a zone, then it must not
		 * conflict with the interface, if one was given.  If not, we
		 * may use it to decide the interface to use for the route.
		 */
		if (IP_IS_V6(&dst_addr) &&
		    ip6_addr_has_zone(ip_2_ip6(&dst_addr))) {
			if (ifdev == NULL) {
				zone = ip6_addr_zone(ip_2_ip6(&dst_addr));

				ifdev = ifdev_get_by_index(zone);
			} else {
				if (!ip6_addr_test_zone(ip_2_ip6(&dst_addr),
				    ifdev_get_netif(ifdev)))
					return EADDRNOTAVAIL;
			}
		}
	}

	/*
	 * For now, no initializers are supported by any of the sub-processing
	 * routines, so outright reject requests that set any initializers.
	 * Most importantly, we do not support per-route MTU settings (RTV_MTU)
	 * because lwIP would not use them, and we do not support non-zero
	 * expiry (RTV_EXPIRE) because for IPv4/IPv6 routes it is not a widely
	 * used feature and for ARP/NDP we would have to change lwIP.
	 * dhcpcd(8) does supply RTV_MTU, we have to ignore that option rather
	 * than reject it, unfortunately.  arp(8) always sets RTV_EXPIRE, so we
	 * reject only non-zero expiry there.
	 */
	if ((inits & ~(RTV_EXPIRE | RTV_MTU)) != 0 ||
	    ((inits & RTV_EXPIRE) != 0 && rmx->rmx_expire != 0))
		return ENOSYS;

	/*
	 * From here on, the processing differs for ARP, NDP, and IP routes.
	 * As of writing, our userland is from NetBSD 7, which puts link-local
	 * route entries in its main route tables.  This means we would have to
	 * search for existing routes before we can determine whether, say, a
	 * RTM_GET request is for an IP or an ARP route entry.  As of NetBSD 8,
	 * the link-local administration is separated, and all requests use the
	 * RTF_LLDATA flag to indicate that they are for ARP/NDP routes rather
	 * than IP routes.  Since that change makes things much cleaner for us,
	 * we borrow from the future, patching arp(8) and ndp(8) to add the
	 * RTF_LLDATA flag now, so that we can implement a clean split here.
	 */
	if (!(flags & RTF_LLDATA))
		return route_process_inet(type, &dst_addr, mask, gateway,
		    ifdev, flags, rtr);
	else
		return lldata_process(type, &dst_addr, gateway, ifdev, flags,
		    rtr);
}

/*
 * Return the routing flags (RTF_) for the given routing entry.  Strip out any
 * internal flags.
 */
unsigned int
route_get_flags(const struct route_entry * route)
{

	return route->re_flags & ~RTF_IPV6;
}

/*
 * Return TRUE if the given routing entry is for the IPv6 address family, or
 * FALSE if it is for IPv4.
 */
int
route_is_ipv6(const struct route_entry * route)
{

	return !!(route->re_flags & RTF_IPV6);
}

/*
 * Return the interface associated with the given routing entry.  The resulting
 * interface is never NULL.
 */
struct ifdev *
route_get_ifdev(const struct route_entry * route)
{

	return route->re_ifdev;
}

/*
 * Convert the given raw routing address pointed to by 'rtaddr' into a
 * lwIP-style IP address 'ipaddr' of type 'type', which must by IPADDR_TYPE_V4
 * or IPADDR_TYPE_V6.
 */
static void
route_get_addr(ip_addr_t * ipaddr, const uint8_t * rtaddr, uint8_t type)
{
	ip6_addr_t *ip6addr;
	uint32_t val, zone;

	/*
	 * Convert the routing address to a lwIP-type IP address.  Take out the
	 * KAME-style embedded zone, if needed.
	 */
	memset(ipaddr, 0, sizeof(*ipaddr));
	IP_SET_TYPE(ipaddr, type);

	switch (type) {
	case IPADDR_TYPE_V4:
		memcpy(&val, rtaddr, sizeof(val));

		ip_addr_set_ip4_u32(ipaddr, val);

		break;

	case IPADDR_TYPE_V6:
		ip6addr = ip_2_ip6(ipaddr);

		memcpy(ip6addr->addr, rtaddr, sizeof(ip6addr->addr));

		if (ip6_addr_has_scope(ip6addr, IP6_UNKNOWN)) {
			zone = ntohl(ip6addr->addr[0]) & 0x0000ffffU;

			ip6addr->addr[0] &= PP_HTONL(0xffff0000U);

			ip6_addr_set_zone(ip6addr, zone);
		}

		break;

	default:
		panic("unknown IP address type: %u", type);
	}
}

/*
 * Obtain information about an IPv4 or IPv6 routing entry, by filling 'addr',
 * 'mask', 'gateway', and optionally (if not NULL) 'ifp' and 'ifa' with
 * sockaddr-type data for each of those fields.  Also store the associated
 * interface in 'ifdevp', the routing entry's flags in 'flags', and the route's
 * usage count in 'use'.
 */
void
route_get(const struct route_entry * route, union sockaddr_any * addr,
	union sockaddr_any * mask, union sockaddr_any * gateway,
	union sockaddr_any * ifp, union sockaddr_any * ifa,
	struct ifdev ** ifdevp, unsigned int * flags, unsigned int * use)
{
	const ip_addr_t *src_addr;
	ip_addr_t dst_addr, gw_addr;
	struct ifdev *ifdev;
	socklen_t addr_len;
	uint8_t type;

	type = (route->re_flags & RTF_IPV6) ? IPADDR_TYPE_V6 : IPADDR_TYPE_V4;

	/* Get the destination address. */
	route_get_addr(&dst_addr, route->re_addr, type);

	addr_len = sizeof(*addr);

	addr_put_inet(&addr->sa, &addr_len, &dst_addr, TRUE /*kame*/,
	    0 /*port*/);

	/* Get the network mask, if applicable. */
	if (!(route->re_flags & RTF_HOST)) {
		addr_len = sizeof(*mask);

		addr_put_netmask(&mask->sa, &addr_len, type,
		    rttree_get_prefix(&route->re_entry));
	} else
		mask->sa.sa_len = 0;

	/* Get the gateway, which may be an IP address or a local link. */
	addr_len = sizeof(*gateway);

	ifdev = route->re_ifdev;

	if (route->re_flags & RTF_GATEWAY) {
		if (type == IPADDR_TYPE_V4)
			ip_addr_copy_from_ip4(gw_addr, route->re_gw4);
		else
			ip_addr_copy_from_ip6_packed(gw_addr, route->re_gw6);

		addr_put_inet(&gateway->sa, &addr_len, &gw_addr, TRUE /*kame*/,
		    0 /*port*/);
	} else {
		addr_put_link(&gateway->sa, &addr_len, ifdev_get_index(ifdev),
		    ifdev_get_iftype(ifdev), NULL /*name*/, NULL /*hwaddr*/,
		    0 /*hwaddr_len*/);
	}

	/* Get the associated interface name. */
	if (ifp != NULL) {
		addr_len = sizeof(*ifp);

		addr_put_link(&ifp->sa, &addr_len, ifdev_get_index(ifdev),
		    ifdev_get_iftype(ifdev), ifdev_get_name(ifdev),
		    NULL /*hwaddr*/, 0 /*hwaddr_len*/);
	}

	/* Get the associated source address, if we can determine one. */
	if (ifa != NULL) {
		src_addr = ifaddr_select(&dst_addr, ifdev, NULL /*ifdevp*/);

		if (src_addr != NULL) {
			addr_len = sizeof(*ifa);

			addr_put_inet(&ifa->sa, &addr_len, src_addr,
			    TRUE /*kame*/, 0 /*port*/);
		} else
			ifa->sa.sa_len = 0;
	}

	/* Get other fields. */
	*flags = route_get_flags(route);	/* strip any internal flags */
	*ifdevp = ifdev;
	*use = route->re_use;
}

/*
 * Enumerate IPv4 routing entries.  Return the first IPv4 routing entry if
 * 'last' is NULL, or the next routing entry after 'last' if it is not NULL.
 * In both cases, the return value may be NULL if there are no more routes.
 */
struct route_entry *
route_enum_v4(struct route_entry * last)
{

	assert(last == NULL || !(last->re_flags & RTF_IPV6));

	return (struct route_entry *)rttree_enum(&route_tree[ROUTE_TREE_V4],
	    (last != NULL) ? &last->re_entry : NULL);
}

/*
 * Enumerate IPv6 routing entries.  Return the first IPv6 routing entry if
 * 'last' is NULL, or the next routing entry after 'last' if it is not NULL.
 * In both cases, the return value may be NULL if there are no more routes.
 */
struct route_entry *
route_enum_v6(struct route_entry * last)
{

	assert(last == NULL || (last->re_flags & RTF_IPV6));

	return (struct route_entry *)rttree_enum(&route_tree[ROUTE_TREE_V6],
	    (last != NULL) ? &last->re_entry : NULL);
}

/*
 * lwIP IPv4 routing function.   Given an IPv4 destination address, look up and
 * return the target interface, or NULL if there is no route to the address.
 *
 * This is a full replacement of the corresponding lwIP function, which should
 * be overridden with weak symbols, using patches against the lwIP source code.
 * As such, the lwIP headers should already provide the correct prototype for
 * this function.  If not, something will have changed in the lwIP
 * implementation, and this code must be revised accordingly.
 */
struct netif *
ip4_route(const ip4_addr_t * dst)
{
	struct route_entry *route;
	struct ifdev *ifdev;

	/*
	 * Look up the route for the destination IPv4 address.  If no route is
	 * found at all, return NULL to the caller.
	 */
	if ((route = route_lookup_v4(dst)) == NULL) {
		route_miss_v4(dst);

		return NULL;
	}

	/*
	 * For now, we increase the use counter only for actual route lookups,
	 * and not for gateway lookups or user queries.  As of writing,
	 * route(8) does not print this number anyway..
	 */
	route->re_use++;

	/*
	 * For all packets that are supposed to be rejected or blackholed, use
	 * a loopback interface, regardless of the interface to which the route
	 * is associated (even though it will typically be lo0 anyway).  The
	 * reason for this is that on packet output, we perform another route
	 * route lookup just to check for rejection/blackholing, but for
	 * efficiency reasons, we limit such checks to loopback interfaces:
	 * loopback traffic will typically use only one IP address anyway, thus
	 * limiting route misses from such rejection/blackhole route lookups as
	 * much as we can.  The lookup is implemented in route_output_v4().  We
	 * divert only if the target interface is not a loopback interface
	 * already, mainly to allow userland tests to create blackhole routes
	 * to a specific loopback interface for testing purposes.
	 *
	 * It is not correct to return NULL for RTF_REJECT routes here, because
	 * this could cause e.g. connect() calls to fail immediately, which is
	 * not how rejection should work.  Related: a previous incarnation of
	 * support for these flags used a dedicated netif to eliminate the
	 * extra route lookup on regular output altogether, but in the current
	 * situation, that netif would have to be assigned (IPv4 and IPv6)
	 * addresses in order not to break e.g. connect() in the same way.
	 */
	if ((route->re_flags & (RTF_REJECT | RTF_BLACKHOLE)) &&
	    !ifdev_is_loopback(route->re_ifdev))
		ifdev = ifdev_get_loopback();
	else
		ifdev = route->re_ifdev;

	return ifdev_get_netif(ifdev);
}

/*
 * lwIP IPv4 routing hook.  Since this hook is called only from lwIP's own
 * ip4_route() implementation, this hook must never fire.  If it does, either
 * something is wrong with overriding ip4_route(), or lwIP added other places
 * from which this hook is called.  Both cases are highly problematic and must
 * be resolved somehow, which is why we simply call panic() here.
 */
struct netif *
lwip_hook_ip4_route(const ip4_addr_t * dst)
{

	panic("IPv4 routing hook called - this should not happen!");
}

/*
 * lwIP IPv4 ARP gateway hook.
 */
const ip4_addr_t *
lwip_hook_etharp_get_gw(struct netif * netif, const ip4_addr_t * ip4addr)
{
	static ip4_addr_t gw_addr; /* may be returned to the caller */
	struct route_entry *route;

	/* Look up the route for the destination IP address. */
	if ((route = route_lookup_v4(ip4addr)) == NULL)
		return NULL;

	/*
	 * This case could only ever trigger as a result of lwIP taking its own
	 * routing decisions instead of calling the IPv4 routing hook.  While
	 * not impossible, such cases should be extremely rare.  We cannot
	 * provide a meaningful gateway address in this case either, though.
	 */
	if (route->re_ifdev != netif_get_ifdev(netif)) {
		printf("LWIP: unexpected interface for gateway lookup\n");

		return NULL;
	}

	/*
	 * If this route has a gateway, return the IP address of the gateway.
	 * Otherwise, the route is for a local network, and we would typically
	 * not get here because lwIP performs the local-network check itself.
	 * It is possible that the local network consists of more than one IP
	 * range, and the user has configured a route for the other range.  In
	 * that case, return the IP address of the actual destination.
	 *
	 * We store a packed version of the IPv4 address, so reconstruct the
	 * unpacked version to a static variable first - for consistency with
	 * the IPv6 code.
	 */
	if (route->re_flags & RTF_GATEWAY) {
		ip4_addr_copy(gw_addr, route->re_gw4);

		return &gw_addr;
	} else
		return ip4addr;
}

/*
 * lwIP IPv6 routing function.   Given an IPv6 source and destination address,
 * look up and return the target interface, or NULL if there is no route to the
 * address.  Our routing algorithm is destination-based, meaning that the
 * source address must be considered only to resolve zone ambiguity.
 *
 * This is a full replacement of the corresponding lwIP function, which should
 * be overridden with weak symbols, using patches against the lwIP source code.
 * As such, the lwIP headers should already provide the correct prototype for
 * this function.  If not, something will have changed in the lwIP
 * implementation, and this code must be revised accordingly.
 */
struct netif *
ip6_route(const ip6_addr_t * src, const ip6_addr_t * dst)
{
	struct route_entry *route;
	struct ifdev *ifdev;
	ip6_addr_t dst_addr;
	uint32_t zone;

	assert(src != NULL);
	assert(dst != NULL);

	/*
	 * If the destination address is scoped but has no zone, use the source
	 * address to determine a zone, which we then set on the destination
	 * address to find the route, if successful.  Obviously, the interface
	 * is not going to be different from the zone, but we do need to check
	 * other aspects of the route (e.g., one might want to null-route all
	 * multicast traffic).  In the case that no source address is given at
	 * all, first see if the destination address happens to be a locally
	 * assigned address.  In theory this could yield multiple matches, so
	 * pick the first one.  If not even that helps, we have absolutely
	 * nothing we can use to refine route selection.  We could pick an
	 * arbitrary interface in that case, but we currently don't.
	 */
	zone = IP6_NO_ZONE;

	if (ip6_addr_lacks_zone(dst, IP6_UNKNOWN)) {
		if (ip6_addr_has_zone(src))
			zone = ip6_addr_zone(src);
		else if (!ip6_addr_isany(src)) {
			if ((ifdev = ifaddr_v6_map_by_addr(src)) == NULL)
				return NULL; /* should never happen */
			zone = ifdev_get_index(ifdev);
		} else {
			if ((ifdev = ifaddr_v6_map_by_addr(dst)) != NULL)
				zone = ifdev_get_index(ifdev);
			else
				return NULL; /* TODO: try harder */
		}

		if (zone != IP6_NO_ZONE) {
			dst_addr = *dst;

			ip6_addr_set_zone(&dst_addr, zone);

			dst = &dst_addr;
		}
	}

	route = route_lookup_v6(dst);

	/*
	 * Look up the route for the destination IPv6 address.  If no route is
	 * found at all, return NULL to the caller.
	 */
	if (route == NULL) {
		/*
		 * Since we rely on userland to create routes for on-link
		 * prefixes and default routers, we do not have to call lwIP's
		 * nd6_find_route() here.
		 */

		/* Generate an RTM_MISS message. */
		route_miss_v6(dst);

		return NULL;
	}

	/*
	 * We have found a route based on the destination address.  If we did
	 * not pick the destination address zone based on the source address,
	 * we should now check for source address zone violations.  Note that
	 * if even the destination address zone violates its target interface,
	 * this case will be caught by route_lookup_v6().
	 */
	if (zone == IP6_NO_ZONE &&
	    ifaddr_is_zone_mismatch(src, route->re_ifdev))
		return NULL;

	route->re_use++;

	/*
	 * See ip4_route() for an explanation of the use of loopback here.  For
	 * the IPv6 case, the matching logic is in route_output_v6().
	 */
	if ((route->re_flags & (RTF_REJECT | RTF_BLACKHOLE)) &&
	    !ifdev_is_loopback(route->re_ifdev))
		ifdev = ifdev_get_loopback();
	else
		ifdev = route->re_ifdev;

	/*
	 * If the selected interface would cause the destination address to
	 * leave its zone, fail route selection altogether.  This case may
	 * trigger especially for reject routes, for which the interface change
	 * to loopback may introduce a zone violation.
	 */
	if (ip6_addr_has_zone(dst) &&
	    !ip6_addr_test_zone(dst, ifdev_get_netif(ifdev)))
		return NULL;

	return ifdev_get_netif(ifdev);
}

/*
 * lwIP IPv6 (source) routing hook.  Since this hook is called only from lwIP's
 * own ip6_route() implementation, this hook must never fire.  If it does,
 * either something is wrong with overriding ip6_route(), or lwIP added other
 * places from which this hook is called.  Both cases are highly problematic
 * and must be resolved somehow, which is why we simply call panic() here.
 */
struct netif *
lwip_hook_ip6_route(const ip6_addr_t * src, const ip6_addr_t * dst)
{

	panic("IPv6 routing hook called - this should not happen!");
}

/*
 * lwIP IPv6 ND6 gateway hook.
 */
const ip6_addr_t *
lwip_hook_nd6_get_gw(struct netif * netif, const ip6_addr_t * ip6addr)
{
	static ip6_addr_t gw_addr; /* may be returned to the caller */
	struct route_entry *route;
	struct ifdev *ifdev;

	ifdev = netif_get_ifdev(netif);
	assert(ifdev != NULL);

	/* Look up the route for the destination IP address. */
	if ((route = route_lookup_v6(ip6addr)) == NULL)
		return NULL;

	/* As for IPv4. */
	if (route->re_ifdev != ifdev) {
		printf("LWIP: unexpected interface for gateway lookup\n");

		return NULL;
	}

	/*
	 * We save memory by storing a packed (zoneless) version of the IPv6
	 * gateway address.  That means we cannot return a pointer to it here.
	 * Instead, we have to resort to expanding the address into a static
	 * variable.  The caller will immediately make a copy anyway, though.
	 */
	if (route->re_flags & RTF_GATEWAY) {
		ip6_addr_copy_from_packed(gw_addr, route->re_gw6);
		ip6_addr_assign_zone(&gw_addr, IP6_UNKNOWN, netif);

		return &gw_addr;
	} else
		return ip6addr;
}

/*
 * Check whether a packet is allowed to be sent to the given destination IPv4
 * address 'ipaddr' on the interface 'ifdev', according to route information.
 * Return TRUE if the packet should be sent.  Return FALSE if the packet should
 * be rejected or discarded, with 'err' set to the error to return to lwIP.
 */
int
route_output_v4(struct ifdev * ifdev, const ip4_addr_t * ipaddr, err_t * err)
{
	const struct route_entry *route;

	/* See if we should reject/blackhole packets to this destination. */
	if (ifdev_is_loopback(ifdev) &&
	    (route = route_lookup_v4(ipaddr)) != NULL &&
	    (route->re_flags & (RTF_REJECT | RTF_BLACKHOLE))) {
		if (route->re_flags & RTF_REJECT)
			*err = ERR_RTE;
		else
			*err = ERR_OK;

		return FALSE;
	}

	return TRUE;
}

/*
 * Check whether a packet is allowed to be sent to the given destination IPv6
 * address 'ipaddr' on the interface 'ifdev', according to route information.
 * Return TRUE if the packet should be sent.  Return FALSE if the packet should
 * be rejected or discarded, with 'err' set to the error to return to lwIP.
 */
int
route_output_v6(struct ifdev * ifdev, const ip6_addr_t * ipaddr, err_t * err)
{
	const struct route_entry *route;

	/* Do one more zone violation test, just in case.  It's cheap. */
	if (ip6_addr_has_zone(ipaddr) &&
	    !ip6_addr_test_zone(ipaddr, ifdev_get_netif(ifdev))) {
		*err = ERR_RTE;

		return FALSE;
	}

	/* See if we should reject/blackhole packets to this destination. */
	if (ifdev_is_loopback(ifdev) &&
	    (route = route_lookup_v6(ipaddr)) != NULL &&
	    (route->re_flags & (RTF_REJECT | RTF_BLACKHOLE))) {
		if (route->re_flags & RTF_REJECT)
			*err = ERR_RTE;
		else
			*err = ERR_OK;

		return FALSE;
	}

	return TRUE;
}