Abstract the routing table internals behind an rtable_* API.

Code abusing the radix internals for the routing table should now
includes <net/rtable.h> and only deal with "struct rtentry".

Code using a radix tree for another purpose can still include
<net/radix.h>.

Inputs from and ok claudio@, mikeb@

17 files changed, 480 insertions, 276 deletions

diff --git a/sys/conf/files b/sys/conf/files
index 0abdacef3f9..46676604e37 100644
--- a/sys/conf/files
+++ b/sys/conf/files
@@ -1,4 +1,4 @@
-#	$OpenBSD: files,v 1.595 2015/07/17 22:52:29 tedu Exp $
+#	$OpenBSD: files,v 1.596 2015/07/18 15:51:16 mpi Exp $
 #	$NetBSD: files,v 1.87 1996/05/19 17:17:50 jonathan Exp $
 
 #	@(#)files.newconf	7.5 (Berkeley) 5/10/93
@@ -776,6 +776,7 @@ file net/radix.c
 file net/radix_mpath.c			!small_kernel
 file net/raw_cb.c
 file net/raw_usrreq.c
+file net/rtable.c
 file net/route.c
 file net/rtsock.c
 file net/slcompress.c			ppp
diff --git a/sys/net/if.c b/sys/net/if.c
index d25a5400c40..d0e6c1373d1 100644
--- a/sys/net/if.c
+++ b/sys/net/if.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if.c,v 1.350 2015/07/16 15:31:35 mpi Exp $	*/
+/*	$OpenBSD: if.c,v 1.351 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$NetBSD: if.c,v 1.35 1996/05/07 05:26:04 thorpej Exp $	*/
 
 /*
@@ -2093,7 +2093,8 @@ if_group_egress_build(void)
 	bzero(&sa_in, sizeof(sa_in));
 	sa_in.sin_len = sizeof(sa_in);
 	sa_in.sin_family = AF_INET;
-	if ((rt = rt_lookup(sintosa(&sa_in), sintosa(&sa_in), 0)) != NULL) {
+	rt = rtable_lookup(0, sintosa(&sa_in), sintosa(&sa_in));
+	if (rt != NULL) {
 		do {
 			if (rt->rt_ifp)
 				if_addgroup(rt->rt_ifp, IFG_EGRESS);
@@ -2107,7 +2108,8 @@ if_group_egress_build(void)
 
 #ifdef INET6
 	bcopy(&sa6_any, &sa_in6, sizeof(sa_in6));
-	if ((rt = rt_lookup(sin6tosa(&sa_in6), sin6tosa(&sa_in6), 0)) != NULL) {
+	rt = rtable_lookup(0, sin6tosa(&sa_in6), sin6tosa(&sa_in6));
+	if (rt != NULL) {
 		do {
 			if (rt->rt_ifp)
 				if_addgroup(rt->rt_ifp, IFG_EGRESS);
@@ -2237,7 +2239,7 @@ ifa_print_all(void)
 		}
 	}
 }
-#endif /* SMALL_KERNEL */
+#endif /* DDB */
 
 void
 ifnewlladdr(struct ifnet *ifp)
diff --git a/sys/net/if_pppx.c b/sys/net/if_pppx.c
index 71692f03eac..525cd705485 100644
--- a/sys/net/if_pppx.c
+++ b/sys/net/if_pppx.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_pppx.c,v 1.41 2015/07/15 22:16:42 deraadt Exp $ */
+/*	$OpenBSD: if_pppx.c,v 1.42 2015/07/18 15:51:16 mpi Exp $ */
 
 /*
  * Copyright (c) 2010 Claudio Jeker <claudio@openbsd.org>
@@ -63,7 +63,6 @@
 
 #include <net/if.h>
 #include <net/if_types.h>
-#include <net/radix.h>
 #include <net/netisr.h>
 #include <netinet/in.h>
 #include <netinet/if_ether.h>
@@ -89,6 +88,7 @@
 #include <crypto/arc4.h>
 
 #ifdef PIPEX
+#include <net/radix.h>
 #include <net/pipex.h>
 #include <net/pipex_local.h>
 #else
diff --git a/sys/net/if_spppsubr.c b/sys/net/if_spppsubr.c
index b6f94f95bf9..22bf11be23b 100644
--- a/sys/net/if_spppsubr.c
+++ b/sys/net/if_spppsubr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_spppsubr.c,v 1.135 2015/06/30 13:54:42 mpi Exp $	*/
+/*	$OpenBSD: if_spppsubr.c,v 1.136 2015/07/18 15:51:16 mpi Exp $	*/
 /*
  * Synchronous PPP/Cisco link level subroutines.
  * Keepalive protocol implemented in both Cisco and PPP modes.
@@ -356,7 +356,7 @@ void sppp_phase_network(struct sppp *sp);
 void sppp_print_bytes(const u_char *p, u_short len);
 void sppp_print_string(const char *p, u_short len);
 void sppp_qflush(struct ifqueue *ifq);
-int sppp_update_gw_walker(struct radix_node *rn, void *arg, u_int);
+int sppp_update_gw_walker(struct rtentry *rt, void *arg, unsigned int id);
 void sppp_update_gw(struct ifnet *ifp);
 void sppp_set_ip_addrs(void *);
 void sppp_clear_ip_addrs(void *);
@@ -4502,10 +4502,9 @@ sppp_get_ip_addrs(struct sppp *sp, u_int32_t *src, u_int32_t *dst,
 }
 
 int
-sppp_update_gw_walker(struct radix_node *rn, void *arg, u_int id)
+sppp_update_gw_walker(struct rtentry *rt, void *arg, unsigned int id)
 {
 	struct ifnet *ifp = arg;
-	struct rtentry *rt = (struct rtentry *)rn;
 
 	if (rt->rt_ifp == ifp) {
 		if (rt->rt_ifa->ifa_dstaddr->sa_family !=
@@ -4521,16 +4520,13 @@ sppp_update_gw_walker(struct radix_node *rn, void *arg, u_int id)
 void
 sppp_update_gw(struct ifnet *ifp)
 {
-        struct radix_node_head *rnh;
 	u_int tid;
 
 	/* update routing table */
 	for (tid = 0; tid <= RT_TABLEID_MAX; tid++) {
-		if ((rnh = rtable_get(tid, AF_INET)) != NULL) {
-			while ((*rnh->rnh_walktree)(rnh,
-			    sppp_update_gw_walker, ifp) == EAGAIN)
-				;	/* nothing */
-		}
+		while (rtable_walk(tid, AF_INET, sppp_update_gw_walker,
+		    ifp) == EAGAIN)
+			;	/* nothing */
 	}
 }
 
diff --git a/sys/net/radix_mpath.c b/sys/net/radix_mpath.c
index e8921f5db17..c23d1ee70d9 100644
--- a/sys/net/radix_mpath.c
+++ b/sys/net/radix_mpath.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.c,v 1.30 2015/07/16 18:17:27 claudio Exp $	*/
+/*	$OpenBSD: radix_mpath.c,v 1.31 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$KAME: radix_mpath.c,v 1.13 2002/10/28 21:05:59 itojun Exp $	*/
 
 /*
@@ -381,35 +381,16 @@ rn_mpath_reprio(struct radix_node *rn, int newprio)
 	}
 }
 
-/*
- * allocate a route, potentially using multipath to select the peer.
- */
+/* Gateway selection by Hash-Threshold (RFC 2992) */
 struct rtentry *
-rtalloc_mpath(struct sockaddr *dst, u_int32_t *srcaddrp, u_int rtableid)
+rn_mpath_select(struct rtentry *rt, uint32_t *srcaddrp)
 {
-	struct rtentry *rt;
 	struct radix_node *rn;
 	int hash, npaths, threshold;
 
-	rt = rtalloc(dst, RT_REPORT|RT_RESOLVE, rtableid);
-
-	/* if the route does not exist or it is not multipath, don't care */
-	if (rt == NULL || !ISSET(rt->rt_flags, RTF_MPATH))
-		return (rt);
-
-	/* check if multipath routing is enabled for the specified protocol */
-	if (!(0
-	    || (ipmultipath && dst->sa_family == AF_INET)
-#ifdef INET6
-	    || (ip6_multipath && dst->sa_family == AF_INET6)
-#endif
-	    ))
-		return (rt);
-
-	/* gw selection by Hash-Threshold (RFC 2992) */
 	rn = (struct radix_node *)rt;
 	npaths = rn_mpath_active_count(rn);
-	hash = rn_mpath_hash(dst, srcaddrp) & 0xffff;
+	hash = rn_mpath_hash(rt_key(rt), srcaddrp) & 0xffff;
 	threshold = 1 + (0xffff / npaths);
 	while (hash > threshold && rn) {
 		/* stay within the multipath routes */
diff --git a/sys/net/radix_mpath.h b/sys/net/radix_mpath.h
index 5b3fe710973..a378a0d7020 100644
--- a/sys/net/radix_mpath.h
+++ b/sys/net/radix_mpath.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.h,v 1.15 2015/02/06 01:21:17 mpi Exp $	*/
+/*	$OpenBSD: radix_mpath.h,v 1.16 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$KAME: radix_mpath.h,v 1.9 2004/03/30 11:21:49 keiichi Exp $	*/
 
 /*
@@ -54,9 +54,9 @@ void	rn_mpath_adj_mpflag(struct radix_node *, u_int8_t);
 int	rn_mpath_active_count(struct radix_node *);
 struct rtentry *rt_mpath_matchgate(struct rtentry *, struct sockaddr *,
 	    u_int8_t);
+struct rtentry *rn_mpath_select(struct rtentry *, uint32_t *);
 int	rt_mpath_conflict(struct radix_node_head *, struct sockaddr *,
 	    struct sockaddr *, struct sockaddr *, u_int8_t, int);
-struct rtentry *rtalloc_mpath(struct sockaddr *, u_int32_t *, u_int);
 int	rn_mpath_inithead(void **, int);
 #endif /* _KERNEL */
 
diff --git a/sys/net/route.c b/sys/net/route.c
index 738b49cb8fb..f2b1be29513 100644
--- a/sys/net/route.c
+++ b/sys/net/route.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.c,v 1.216 2015/07/16 18:17:27 claudio Exp $	*/
+/*	$OpenBSD: route.c,v 1.217 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$NetBSD: route.c,v 1.14 1996/02/13 22:00:46 christos Exp $	*/
 
 /*
@@ -120,6 +120,12 @@
 #include <net/route.h>
 
 #include <netinet/in.h>
+#include <netinet/ip_var.h>
+
+#ifdef INET6
+#include <netinet/ip6.h>
+#include <netinet6/ip6_var.h>
+#endif
 
 #ifdef MPLS
 #include <netmpls/mpls.h>
@@ -131,7 +137,7 @@
 #endif
 
 struct	rtstat		   rtstat;
-struct	radix_node_head	***rt_tables;
+void			***rt_tables;
 u_int8_t		   af2rtafidx[AF_MAX+1];
 u_int8_t		   rtafidx_max;
 u_int			   rtbl_id_max = 0;
@@ -143,10 +149,10 @@ struct pool		rtentry_pool;	/* pool for rtentry structures */
 struct pool		rttimer_pool;	/* pool for rttimer structures */
 
 void	rt_timer_init(void);
-int	rtable_init(struct radix_node_head ***, u_int);
-int	rtflushclone1(struct radix_node *, void *, u_int);
-void	rtflushclone(struct radix_node_head *, struct rtentry *);
-int	rt_if_remove_rtdelete(struct radix_node *, void *, u_int);
+int	rtable_alloc(void ***, u_int);
+int	rtflushclone1(struct rtentry *, void *, u_int);
+void	rtflushclone(unsigned int, struct rtentry *);
+int	rt_if_remove_rtdelete(struct rtentry *, void *, u_int);
 
 struct	ifaddr *ifa_ifwithroute(int, struct sockaddr *, struct sockaddr *,
 		    u_int);
@@ -163,7 +169,7 @@ struct rt_label {
 TAILQ_HEAD(rt_labels, rt_label)	rt_labels = TAILQ_HEAD_INITIALIZER(rt_labels);
 
 int
-rtable_init(struct radix_node_head ***table, u_int id)
+rtable_alloc(void ***table, u_int id)
 {
 	void		**p;
 	struct domain	 *dom;
@@ -179,12 +185,10 @@ rtable_init(struct radix_node_head ***table, u_int id)
 			dom->dom_rtattach(&p[af2rtafidx[dom->dom_family]],
 			    dom->dom_rtoffset);
 
-	*table = (struct radix_node_head **)p;
+	for (i = 0; i < rtafidx_max; i++)
+		rtable_setid(p, id, i);
 
-	for (i = 0; i < rtafidx_max; i++) {
-		if ((*table)[i] != NULL)
-			(*table)[i]->rnh_rtableid = id;
-	}
+	*table = (void **)p;
 
 	return (0);
 }
@@ -196,7 +200,7 @@ route_init(void)
 
 	pool_init(&rtentry_pool, sizeof(struct rtentry), 0, 0, 0, "rtentry",
 	    NULL);
-	rn_init();	/* initialize all zeroes, all ones, mask table */
+	rtable_init();	/* initialize all zeroes, all ones, mask table */
 
 	bzero(af2rtafidx, sizeof(af2rtafidx));
 	rtafidx_max = 1;	/* must have NULL at index 0, so start at 1 */
@@ -249,10 +253,10 @@ rtable_add(u_int id)
 		return (EEXIST);
 
 	rt_tab2dom[id] = 0;	/* use main table/domain by default */
-	return (rtable_init(&rt_tables[id], id));
+	return (rtable_alloc(&rt_tables[id], id));
 }
 
-struct radix_node_head *
+void *
 rtable_get(u_int id, sa_family_t af)
 {
 	if (id > rtbl_id_max)
@@ -296,9 +300,7 @@ rtable_exists(u_int id)	/* verify table with that ID exists */
 struct rtentry *
 rtalloc(struct sockaddr *dst, int flags, unsigned int tableid)
 {
-	struct radix_node_head	*rnh;
 	struct rtentry		*rt;
-	struct radix_node	*rn;
 	struct rtentry		*newrt = 0;
 	struct rt_addrinfo	 info;
 	int			 s = splsoftnet(), err = 0, msgtype = RTM_MISS;
@@ -306,9 +308,9 @@ rtalloc(struct sockaddr *dst, int flags, unsigned int tableid)
 	bzero(&info, sizeof(info));
 	info.rti_info[RTAX_DST] = dst;
 
-	rnh = rtable_get(tableid, dst->sa_family);
-	if (rnh && (rn = rnh->rnh_matchaddr((caddr_t)dst, rnh))) {
-		newrt = rt = (struct rtentry *)rn;
+	rt = rtable_match(tableid, dst);
+	if (rt != NULL) {
+		newrt = rt;
 		if ((rt->rt_flags & RTF_CLONING) && ISSET(flags, RT_RESOLVE)) {
 			err = rtrequest1(RTM_RESOLVE, &info, RTP_DEFAULT,
 			    &newrt, tableid);
@@ -344,6 +346,34 @@ miss:
 	return (newrt);
 }
 
+#ifndef SMALL_KERNEL
+/*
+ * Allocate a route, potentially using multipath to select the peer.
+ */
+struct rtentry *
+rtalloc_mpath(struct sockaddr *dst, uint32_t *src, unsigned int rtableid)
+{
+	struct rtentry *rt;
+
+	rt = rtalloc(dst, RT_REPORT|RT_RESOLVE, rtableid);
+
+	/* if the route does not exist or it is not multipath, don't care */
+	if (rt == NULL || !ISSET(rt->rt_flags, RTF_MPATH))
+		return (rt);
+
+	/* check if multipath routing is enabled for the specified protocol */
+	if (!(0
+	    || (ipmultipath && dst->sa_family == AF_INET)
+#ifdef INET6
+	    || (ip6_multipath && dst->sa_family == AF_INET6)
+#endif
+	    ))
+		return (rt);
+
+	return (rtable_mpath_select(rt, src));
+}
+#endif /* SMALL_KERNEL */
+
 void
 rtfree(struct rtentry *rt)
 {
@@ -354,9 +384,9 @@ rtfree(struct rtentry *rt)
 	rt->rt_refcnt--;
 
 	if (rt->rt_refcnt <= 0 && (rt->rt_flags & RTF_UP) == 0) {
-		if (rt->rt_refcnt == 0 && (rt->rt_nodes->rn_flags & RNF_ACTIVE))
+		if (rt->rt_refcnt == 0 && RT_ACTIVE(rt))
 			return; /* route still active but currently down */
-		if (rt->rt_nodes->rn_flags & (RNF_ACTIVE | RNF_ROOT))
+		if (RT_ACTIVE(rt) || RT_ROOT(rt))
 			panic("rtfree 2");
 		rttrash--;
 		if (rt->rt_refcnt < 0) {
@@ -564,12 +594,10 @@ rtequal(struct rtentry *a, struct rtentry *b)
 }
 
 int
-rtflushclone1(struct radix_node *rn, void *arg, u_int id)
+rtflushclone1(struct rtentry *rt, void *arg, u_int id)
 {
-	struct rtentry	*rt, *parent;
+	struct rtentry *parent = arg;
 
-	rt = (struct rtentry *)rn;
-	parent = (struct rtentry *)arg;
 	if ((rt->rt_flags & RTF_CLONED) != 0 && (rt->rt_parent == parent ||
 	    rtequal(rt->rt_parent, parent)))
 		rtdeletemsg(rt, id);
@@ -577,16 +605,14 @@ rtflushclone1(struct radix_node *rn, void *arg, u_int id)
 }
 
 void
-rtflushclone(struct radix_node_head *rnh, struct rtentry *parent)
+rtflushclone(unsigned int rtableid, struct rtentry *parent)
 {
 
 #ifdef DIAGNOSTIC
 	if (!parent || (parent->rt_flags & RTF_CLONING) == 0)
 		panic("rtflushclone: called with a non-cloning route");
-	if (!rnh->rnh_walktree)
-		panic("rtflushclone: no rnh_walktree");
 #endif
-	rnh->rnh_walktree(rnh, rtflushclone1, (void *)parent);
+	rtable_walk(rtableid, rt_key(parent)->sa_family, rtflushclone1, parent);
 }
 
 int
@@ -723,8 +749,6 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
     struct rtentry **ret_nrt, u_int tableid)
 {
 	struct rtentry		*rt, *crt;
-	struct radix_node	*rn;
-	struct radix_node_head	*rnh;
 	struct ifaddr		*ifa;
 	struct sockaddr		*ndst;
 	struct sockaddr_rtlabel	*sa_rl, sa_rl2;
@@ -736,31 +760,29 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 
 	splsoftassert(IPL_SOFTNET);
 
-	if ((rnh = rtable_get(tableid, info->rti_info[RTAX_DST]->sa_family)) ==
-	    NULL)
+	if (!rtable_exists(tableid))
 		return (EAFNOSUPPORT);
 	if (info->rti_flags & RTF_HOST)
 		info->rti_info[RTAX_NETMASK] = NULL;
 	switch (req) {
 	case RTM_DELETE:
-		if ((rn = rnh->rnh_lookup(info->rti_info[RTAX_DST],
-		    info->rti_info[RTAX_NETMASK], rnh)) == NULL)
+		rt = rtable_lookup(tableid, info->rti_info[RTAX_DST],
+		    info->rti_info[RTAX_NETMASK]);
+		if (rt == NULL)
 			return (ESRCH);
-		rt = (struct rtentry *)rn;
 #ifndef SMALL_KERNEL
+		rt = rtable_mpath_match(tableid, rt,
+		    info->rti_info[RTAX_GATEWAY], prio);
+		if (rt == NULL)
+			return (ESRCH);
+
 		/*
-		 * if we got multipath routes, we require users to specify
-		 * a matching RTAX_GATEWAY.
+		 * If we got multipath routes, we require users to specify
+		 * a matching gateway.
 		 */
-		if (rn_mpath_capable(rnh)) {
-			rt = rt_mpath_matchgate(rt,
-			    info->rti_info[RTAX_GATEWAY], prio);
-			rn = (struct radix_node *)rt;
-			if (!rt ||
-			    (!info->rti_info[RTAX_GATEWAY] &&
-			    rt->rt_flags & RTF_MPATH))
-				return (ESRCH);
-		}
+		if ((rt->rt_flags & RTF_MPATH) &&
+		    info->rti_info[RTAX_GATEWAY] == NULL)
+			return (ESRCH);
 #endif
 
 		/*
@@ -772,17 +794,14 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 		    prio != RTP_LOCAL)
 			return (EINVAL);
 
-		if ((rn = rnh->rnh_deladdr(info->rti_info[RTAX_DST],
-		    info->rti_info[RTAX_NETMASK], rnh, rn)) == NULL)
+		error = rtable_delete(tableid, info->rti_info[RTAX_DST],
+		    info->rti_info[RTAX_NETMASK], prio, rt);
+		if (error != 0)
 			return (ESRCH);
-		rt = (struct rtentry *)rn;
 
 		/* clean up any cloned children */
 		if ((rt->rt_flags & RTF_CLONING) != 0)
-			rtflushclone(rnh, rt);
-
-		if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))
-			panic ("rtrequest delete");
+			rtflushclone(tableid, rt);
 
 		if (rt->rt_gwroute) {
 			rtfree(rt->rt_gwroute);
@@ -855,15 +874,12 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 			memcpy(ndst, info->rti_info[RTAX_DST], dlen);
 
 #ifndef SMALL_KERNEL
-		if (rn_mpath_capable(rnh)) {
-			/* do not permit exactly the same dst/mask/gw pair */
-			if (rt_mpath_conflict(rnh, ndst,
-			    info->rti_info[RTAX_NETMASK],
-			    info->rti_info[RTAX_GATEWAY], prio,
-			    info->rti_flags & RTF_MPATH)) {
-				free(ndst, M_RTABLE, dlen);
-				return (EEXIST);
-			}
+		/* Do not permit exactly the same dst/mask/gw pair. */
+		if (rtable_mpath_conflict(tableid, ndst,
+		    info->rti_info[RTAX_NETMASK], info->rti_info[RTAX_GATEWAY],
+		    prio, info->rti_flags & RTF_MPATH)) {
+			free(ndst, M_RTABLE, dlen);
+			return (EEXIST);
 		}
 #endif
 		rt = pool_get(&rtentry_pool, PR_NOWAIT | PR_ZERO);
@@ -878,7 +894,7 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 		LIST_INIT(&rt->rt_timer);
 
 #ifndef SMALL_KERNEL
-		if (rn_mpath_capable(rnh)) {
+		if (rtable_mpath_capable(tableid, ndst->sa_family)) {
 			/* check the link state since the table supports it */
 			if (LINK_STATE_IS_UP(ifa->ifa_ifp->if_link_state) &&
 			    ifa->ifa_ifp->if_flags & IFF_UP)
@@ -974,20 +990,19 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 			return (error);
 		}
 
-		rn = rnh->rnh_addaddr((caddr_t)ndst,
-		    (caddr_t)info->rti_info[RTAX_NETMASK], rnh, rt->rt_nodes,
-		    rt->rt_priority);
-		if (rn == NULL && (crt = rtalloc(ndst, 0, tableid)) != NULL) {
+		error = rtable_insert(tableid, ndst,
+		    info->rti_info[RTAX_NETMASK], rt->rt_priority, rt);
+		if (error != 0 && (crt = rtalloc(ndst, 0, tableid)) != NULL) {
 			/* overwrite cloned route */
 			if ((crt->rt_flags & RTF_CLONED) != 0) {
 				rtdeletemsg(crt, tableid);
-				rn = rnh->rnh_addaddr((caddr_t)ndst,
-				    (caddr_t)info->rti_info[RTAX_NETMASK],
-				    rnh, rt->rt_nodes, rt->rt_priority);
-			}
+				error = rtable_insert(tableid, ndst,
+				    info->rti_info[RTAX_NETMASK],
+				    rt->rt_priority, rt);
+				}
 			rtfree(crt);
 		}
-		if (rn == 0) {
+		if (error != 0) {
 			ifafree(ifa);
 			if ((rt->rt_flags & RTF_CLONED) != 0 && rt->rt_parent)
 				rtfree(rt->rt_parent);
@@ -1008,7 +1023,7 @@ rtrequest1(int req, struct rt_addrinfo *info, u_int8_t prio,
 		}
 		if ((rt->rt_flags & RTF_CLONING) != 0) {
 			/* clean up any cloned children */
-			rtflushclone(rnh, rt);
+			rtflushclone(tableid, rt);
 		}
 
 		if_group_routechange(info->rti_info[RTAX_DST],
@@ -1517,17 +1532,6 @@ rt_timer_add(struct rtentry *rt, void (*func)(struct rtentry *,
 	return (0);
 }
 
-struct rtentry *
-rt_lookup(struct sockaddr *dst, struct sockaddr *mask, u_int tableid)
-{
-	struct radix_node_head	*rnh;
-
-	if ((rnh = rtable_get(tableid, dst->sa_family)) == NULL)
-		return (NULL);
-
-	return ((struct rtentry *)rnh->rnh_lookup(dst, mask, rnh));
-}
-
 /* ARGSUSED */
 void
 rt_timer_timer(void *arg)
@@ -1657,16 +1661,14 @@ rt_if_remove(struct ifnet *ifp)
 {
 	int			 i;
 	u_int			 tid;
-	struct radix_node_head	*rnh;
 
 	for (tid = 0; tid <= rtbl_id_max; tid++) {
 		/* skip rtables that are not in the rdomain of the ifp */
 		if (rtable_l2(tid) != ifp->if_rdomain)
 			continue;
 		for (i = 1; i <= AF_MAX; i++) {
-			if ((rnh = rtable_get(tid, i)) != NULL)
-				while ((*rnh->rnh_walktree)(rnh,
-				    rt_if_remove_rtdelete, ifp) == EAGAIN)
+			while (rtable_walk(tid, i, rt_if_remove_rtdelete,
+				ifp) == EAGAIN)
 					;	/* nothing */
 		}
 	}
@@ -1679,10 +1681,9 @@ rt_if_remove(struct ifnet *ifp)
  * as long as EAGAIN is returned.
  */
 int
-rt_if_remove_rtdelete(struct radix_node *rn, void *vifp, u_int id)
+rt_if_remove_rtdelete(struct rtentry *rt, void *vifp, u_int id)
 {
 	struct ifnet	*ifp = vifp;
-	struct rtentry	*rt = (struct rtentry *)rn;
 
 	if (rt->rt_ifp == ifp) {
 		int	cloning = (rt->rt_flags & RTF_CLONING);
@@ -1703,7 +1704,6 @@ rt_if_remove_rtdelete(struct radix_node *rn, void *vifp, u_int id)
 void
 rt_if_track(struct ifnet *ifp)
 {
-	struct radix_node_head *rnh;
 	int i;
 	u_int tid;
 
@@ -1715,49 +1715,47 @@ rt_if_track(struct ifnet *ifp)
 		if (rtable_l2(tid) != ifp->if_rdomain)
 			continue;
 		for (i = 1; i <= AF_MAX; i++) {
-			if ((rnh = rtable_get(tid, i)) != NULL) {
-				if (!rn_mpath_capable(rnh))
-					continue;
-				while ((*rnh->rnh_walktree)(rnh,
-				    rt_if_linkstate_change, ifp) == EAGAIN)
-					;	/* nothing */
-			}
+			if (!rtable_mpath_capable(tid, i))
+				continue;
+
+			while (rtable_walk(tid, i,
+			    rt_if_linkstate_change, ifp) == EAGAIN)
+				;	/* nothing */
 		}
 	}
 }
 
 int
-rt_if_linkstate_change(struct radix_node *rn, void *arg, u_int id)
+rt_if_linkstate_change(struct rtentry *rt, void *arg, u_int id)
 {
 	struct ifnet *ifp = arg;
-	struct rtentry *rt = (struct rtentry *)rn;
 
-	if (rt->rt_ifp == ifp) {
-		if (LINK_STATE_IS_UP(ifp->if_link_state) &&
-		    ifp->if_flags & IFF_UP) {
-			if (!(rt->rt_flags & RTF_UP)) {
-				/* bring route up */
-				rt->rt_flags |= RTF_UP;
-				rn_mpath_reprio(rn, rt->rt_priority & RTP_MASK);
-			}
-		} else {
-			if (rt->rt_flags & RTF_UP) {
-				/*
-				 * Remove cloned routes (mainly arp) to
-				 * down interfaces so we have a chance to
-				 * clone a new route from a better source.
-				 */
-				if (rt->rt_flags & RTF_CLONED) {
-					rtdeletemsg(rt, id);
-					return (0);
-				}
-				/* take route down */
-				rt->rt_flags &= ~RTF_UP;
-				rn_mpath_reprio(rn, rt->rt_priority | RTP_DOWN);
+	if (rt->rt_ifp != ifp)
+		return (0);
+
+	if (LINK_STATE_IS_UP(ifp->if_link_state) && ifp->if_flags & IFF_UP) {
+		if (!(rt->rt_flags & RTF_UP)) {
+			/* bring route up */
+			rt->rt_flags |= RTF_UP;
+			rtable_mpath_reprio(rt, rt->rt_priority & RTP_MASK);
+		}
+	} else {
+		if (rt->rt_flags & RTF_UP) {
+			/*
+			 * Remove cloned routes (mainly arp) to
+			 * down interfaces so we have a chance to
+			 * clone a new route from a better source.
+			 */
+			if (rt->rt_flags & RTF_CLONED) {
+				rtdeletemsg(rt, id);
+				return (0);
 			}
+			/* take route down */
+			rt->rt_flags &= ~RTF_UP;
+			rtable_mpath_reprio(rt, rt->rt_priority | RTP_DOWN);
 		}
-		if_group_routechange(rt_key(rt), rt_mask(rt));
 	}
+	if_group_routechange(rt_key(rt), rt_mask(rt));
 
 	return (0);
 }
diff --git a/sys/net/route.h b/sys/net/route.h
index 3f6a938653f..40bf7b6a6ad 100644
--- a/sys/net/route.h
+++ b/sys/net/route.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.h,v 1.108 2015/07/08 07:56:51 mpi Exp $	*/
+/*	$OpenBSD: route.h,v 1.109 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$NetBSD: route.h,v 1.9 1996/02/13 22:00:49 christos Exp $	*/
 
 /*
@@ -80,9 +80,8 @@ struct rt_metrics {
 #define	RTM_RTTUNIT	1000000	/* units for rtt, rttvar, as units per sec */
 #define	RTTTOPRHZ(r)	((r) / (RTM_RTTUNIT / PR_SLOWHZ))
 
-#ifdef _KERNEL
-
 #include <sys/queue.h>
+#include <net/rtable.h>
 
 /*
  * We distinguish between routes to hosts and routes to networks,
@@ -92,13 +91,9 @@ struct rt_metrics {
  * gateways are marked so that the output routines know to address the
  * gateway rather than the ultimate destination.
  */
-#include <net/radix.h>
-#include <net/radix_mpath.h>
 
 struct rtentry {
 	struct	radix_node rt_nodes[2];	/* tree glue, and other values */
-#define	rt_key(r)	((struct sockaddr *)((r)->rt_nodes->rn_key))
-#define	rt_mask(r)	((struct sockaddr *)((r)->rt_nodes->rn_mask))
 	struct sockaddr	*rt_gateway;	/* value */
 	struct ifnet	*rt_ifp;	/* the answer: interface to use */
 	struct ifaddr	*rt_ifa;	/* the answer: interface addr to use */
@@ -117,8 +112,6 @@ struct rtentry {
 #define	rt_use		rt_rmx.rmx_pksent
 #define	rt_expire	rt_rmx.rmx_expire
 
-#endif /* _KERNEL */
-
 #define	RTF_UP		0x1		/* route usable */
 #define	RTF_GATEWAY	0x2		/* destination is a gateway */
 #define	RTF_HOST	0x4		/* host entry (net otherwise) */
@@ -342,10 +335,10 @@ void		 rtlabel_unref(u_int16_t);
 extern struct rtstat rtstat;
 extern const struct sockaddr_rtin rt_defmask4;
 
+struct	mbuf;
 struct	socket;
 void	 route_init(void);
 int	 rtable_add(u_int);
-struct radix_node_head *rtable_get(u_int, sa_family_t);
 u_int	 rtable_l2(u_int);
 void	 rtable_l2set(u_int, u_int);
 int	 rtable_exists(u_int);
@@ -379,6 +372,8 @@ void			 rt_timer_timer(void *);
 
 #ifdef SMALL_KERNEL
 #define	 rtalloc_mpath(dst, s, rid) rtalloc((dst), RT_REPORT|RT_RESOLVE, (rid))
+#else
+struct	 rtentry *rtalloc_mpath(struct sockaddr *, uint32_t *, u_int);
 #endif
 struct	 rtentry *rtalloc(struct sockaddr *, int, unsigned int);
 void	 rtfree(struct rtentry *);
@@ -397,12 +392,10 @@ int	 rtrequest1(int, struct rt_addrinfo *, u_int8_t, struct rtentry **,
 void	 rt_if_remove(struct ifnet *);
 #ifndef SMALL_KERNEL
 void	 rt_if_track(struct ifnet *);
-int	 rt_if_linkstate_change(struct radix_node *, void *, u_int);
+int	 rt_if_linkstate_change(struct rtentry *, void *, u_int);
 #endif
 int	 rtdeletemsg(struct rtentry *, u_int);
 
-struct rtentry		*rt_lookup(struct sockaddr *, struct sockaddr *, u_int);
-
 struct rtentry *rt_mpath_next(struct rtentry *);
 #endif /* _KERNEL */
 
diff --git a/sys/net/rtable.c b/sys/net/rtable.c
new file mode 100644
index 00000000000..48206248094
--- /dev/null
+++ b/sys/net/rtable.c
@@ -0,0 +1,204 @@
+/*	$OpenBSD: rtable.c,v 1.1 2015/07/18 15:51:16 mpi Exp $ */
+
+/*
+ * Copyright (c) 2014-2015 Martin Pieuchot
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/socket.h>
+
+#include <net/rtable.h>
+#include <net/route.h>
+
+void
+rtable_init(void)
+{
+	rn_init();
+}
+
+int
+rtable_attach(void **head, int off)
+{
+	int rv;
+
+#ifndef SMALL_KERNEL
+	rv = rn_mpath_inithead(head, off);
+#else
+	rv = rn_inithead(head, off);
+#endif
+
+	return (rv);
+}
+
+struct rtentry *
+rtable_lookup(unsigned int rtableid, struct sockaddr *dst,
+    struct sockaddr *mask)
+{
+	struct radix_node_head	*rnh;
+	struct radix_node	*rn;
+
+	rnh = rtable_get(rtableid, dst->sa_family);
+	if (rnh == NULL)
+		return (NULL);
+
+	rn = rnh->rnh_lookup(dst, mask, rnh);
+	if (rn == NULL || (rn->rn_flags & RNF_ROOT) != 0)
+		return (NULL);
+
+	return ((struct rtentry *)rn);
+}
+
+struct rtentry *
+rtable_match(unsigned int rtableid, struct sockaddr *dst)
+{
+	struct radix_node_head	*rnh;
+	struct radix_node	*rn;
+
+	rnh = rtable_get(rtableid, dst->sa_family);
+	if (rnh == NULL)
+		return (NULL);
+
+	rn = rnh->rnh_matchaddr(dst, rnh);
+	if (rn == NULL || (rn->rn_flags & RNF_ROOT) != 0)
+		return (NULL);
+
+	return ((struct rtentry *)rn);
+}
+
+int
+rtable_insert(unsigned int rtableid, struct sockaddr *dst,
+    struct sockaddr *mask, uint8_t prio, struct rtentry *rt)
+{
+	struct radix_node_head	*rnh;
+	struct radix_node	*rn = (struct radix_node *)rt;
+
+	rnh = rtable_get(rtableid, dst->sa_family);
+	if (rnh == NULL)
+		return (EAFNOSUPPORT);
+
+	rn = rnh->rnh_addaddr(dst, mask, rnh, rn, prio);
+	if (rn == NULL)
+		return (ESRCH);
+
+	return (0);
+}
+
+int
+rtable_delete(unsigned int rtableid, struct sockaddr *dst,
+    struct sockaddr *mask, uint8_t prio, struct rtentry *rt)
+{
+	struct radix_node_head	*rnh;
+	struct radix_node	*rn = (struct radix_node *)rt;
+
+	rnh = rtable_get(rtableid, dst->sa_family);
+	if (rnh == NULL)
+		return (EAFNOSUPPORT);
+
+	rn = rnh->rnh_deladdr(dst, mask, rnh, rn);
+	if (rn == NULL)
+		return (ESRCH);
+
+	if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))
+		panic("active node flags=%x", rn->rn_flags);
+
+	return (0);
+}
+
+int
+rtable_setid(void **p, unsigned int rtableid, sa_family_t af)
+{
+	struct radix_node_head **rnh = (struct radix_node_head **)p;
+
+	if (rnh == NULL || rnh[af] == NULL)
+		return (EINVAL);
+
+	rnh[af]->rnh_rtableid = rtableid;
+
+	return (0);
+}
+
+int
+rtable_walk(unsigned int rtableid, sa_family_t af,
+    int (*func)(struct rtentry *, void *, unsigned int), void *arg)
+{
+	struct radix_node_head	*rnh;
+	int (*f)(struct radix_node *, void *, u_int) = (void *)func;
+
+	rnh = rtable_get(rtableid, af);
+	if (rnh == NULL)
+		return (EAFNOSUPPORT);
+
+	return (*rnh->rnh_walktree)(rnh, f, arg);
+}
+
+#ifndef SMALL_KERNEL
+int
+rtable_mpath_capable(unsigned int rtableid, sa_family_t af)
+{
+	struct radix_node_head	*rnh;
+
+	rnh = rtable_get(rtableid, af);
+	if (rnh == NULL)
+		return (0);
+
+	return (rnh->rnh_multipath);
+}
+
+struct rtentry *
+rtable_mpath_match(unsigned int rtableid, struct rtentry *rt,
+    struct sockaddr *gateway, uint8_t prio)
+{
+	struct radix_node_head	*rnh;
+
+	rnh = rtable_get(rtableid, rt_key(rt)->sa_family);
+	if (rnh == NULL || rnh->rnh_multipath == 0)
+		return (rt);
+
+	rt = rt_mpath_matchgate(rt, gateway, prio);
+
+	return (rt);
+}
+
+int
+rtable_mpath_conflict(unsigned int rtableid, struct sockaddr *dst,
+    struct sockaddr *mask, struct sockaddr *gateway, uint8_t prio, int mpathok)
+{
+	struct radix_node_head	*rnh;
+
+	rnh = rtable_get(rtableid, dst->sa_family);
+	if (rnh == NULL)
+		return (EAFNOSUPPORT);
+
+	if (rnh->rnh_multipath == 0)
+		return (0);
+
+	return (rt_mpath_conflict(rnh, dst, mask, gateway, prio, mpathok));
+}
+
+struct rtentry *
+rtable_mpath_select(struct rtentry *rt, uint32_t *src)
+{
+	return (rn_mpath_select(rt, src));
+}
+
+void
+rtable_mpath_reprio(struct rtentry *rt, uint8_t newprio)
+{
+	struct radix_node	*rn = (struct radix_node *)rt;
+
+	rn_mpath_reprio(rn, newprio);
+}
+#endif
diff --git a/sys/net/rtable.h b/sys/net/rtable.h
new file mode 100644
index 00000000000..9a6a9c74b66
--- /dev/null
+++ b/sys/net/rtable.h
@@ -0,0 +1,57 @@
+/*	$OpenBSD: rtable.h,v 1.1 2015/07/18 15:51:16 mpi Exp $ */
+
+/*
+ * Copyright (c) 2014-2015 Martin Pieuchot
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef	_NET_RTABLE_H_
+#define	_NET_RTABLE_H_
+
+/*
+ * Traditional BSD routing table implementation based on a radix tree.
+ */
+#include <net/radix.h>
+#ifndef SMALL_KERNEL
+#include <net/radix_mpath.h>
+#endif
+
+#define	rt_key(rt)	(((struct sockaddr *)(rt)->rt_nodes[0].rn_key))
+#define	rt_mask(rt)	(((struct sockaddr *)(rt)->rt_nodes[0].rn_mask))
+#define	RT_ACTIVE(rt)	((rt)->rt_nodes[0].rn_flags & RNF_ACTIVE)
+#define	RT_ROOT(rt)	((rt)->rt_nodes[0].rn_flags & RNF_ROOT)
+
+void		 rtable_init(void);
+int		 rtable_attach(void **, int);
+struct rtentry	*rtable_lookup(unsigned int, struct sockaddr *,
+		     struct sockaddr *);
+struct rtentry	*rtable_match(unsigned int, struct sockaddr *);
+int		 rtable_insert(unsigned int, struct sockaddr *,
+		     struct sockaddr *, uint8_t, struct rtentry *);
+int		 rtable_delete(unsigned int, struct sockaddr *,
+		     struct sockaddr *, uint8_t, struct rtentry *);
+
+int		 rtable_setid(void **, unsigned int, sa_family_t);
+void		*rtable_get(unsigned int, sa_family_t);
+int		 rtable_walk(unsigned int, sa_family_t,
+		     int (*)(struct rtentry *, void *, unsigned int), void *);
+
+int		 rtable_mpath_capable(unsigned int, sa_family_t);
+struct rtentry	*rtable_mpath_match(unsigned int, struct rtentry *,
+		     struct sockaddr *, uint8_t);
+int		 rtable_mpath_conflict(unsigned int, struct sockaddr *,
+		     struct sockaddr *, struct sockaddr *, uint8_t, int);
+struct rtentry	*rtable_mpath_select(struct rtentry *, uint32_t *);
+void		 rtable_mpath_reprio(struct rtentry *, uint8_t);
+#endif /* _NET_RTABLE_H_ */
diff --git a/sys/net/rtsock.c b/sys/net/rtsock.c
index a8684186a94..88826887e4d 100644
--- a/sys/net/rtsock.c
+++ b/sys/net/rtsock.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rtsock.c,v 1.164 2015/07/18 00:02:30 phessler Exp $	*/
+/*	$OpenBSD: rtsock.c,v 1.165 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$NetBSD: rtsock.c,v 1.18 1996/03/29 00:32:10 cgd Exp $	*/
 
 /*
@@ -445,7 +445,6 @@ route_output(struct mbuf *m, ...)
 	struct rt_msghdr	*rtm = NULL;
 	struct rtentry		*rt = NULL;
 	struct rtentry		*saved_nrt = NULL;
-	struct radix_node_head	*rnh;
 	struct rt_addrinfo	 info;
 	int			 len, newgate, error = 0;
 	struct ifnet		*ifp = NULL;
@@ -617,52 +616,51 @@ route_output(struct mbuf *m, ...)
 	case RTM_GET:
 	case RTM_CHANGE:
 	case RTM_LOCK:
-		rnh = rtable_get(tableid, info.rti_info[RTAX_DST]->sa_family);
-		if (rnh == NULL) {
+		if (!rtable_exists(tableid)) {
 			error = EAFNOSUPPORT;
 			goto flush;
 		}
-		rt = rt_lookup(info.rti_info[RTAX_DST],
-		    info.rti_info[RTAX_NETMASK], tableid);
+		rt = rtable_lookup(tableid, info.rti_info[RTAX_DST],
+		    info.rti_info[RTAX_NETMASK]);
 		if (rt == NULL) {
 			error = ESRCH;
 			goto flush;
 		}
 #ifndef SMALL_KERNEL
-		if (rn_mpath_capable(rnh)) {
-			/* first find the right priority */
-			rt = rt_mpath_matchgate(rt, NULL, prio);
-			if (!rt) {
+		/* First find the right priority. */
+		rt = rtable_mpath_match(tableid, rt, NULL, prio);
+		if (rt == NULL) {
+			error = ESRCH;
+			goto flush;
+		}
+
+
+		/*
+		 * For RTM_CHANGE/LOCK, if we got multipath routes,
+		 * a matching RTAX_GATEWAY is required.
+		 * OR
+		 * If a gateway is specified then RTM_GET and
+		 * RTM_LOCK must match the gateway no matter
+		 * what even in the non multipath case.
+		 */
+		if ((rt->rt_flags & RTF_MPATH) ||
+		    (info.rti_info[RTAX_GATEWAY] && rtm->rtm_type !=
+		     RTM_CHANGE)) {
+			rt = rtable_mpath_match(tableid, rt,
+			    info.rti_info[RTAX_GATEWAY], prio);
+			if (rt == NULL) {
 				error = ESRCH;
 				goto flush;
 			}
 			/*
-			 * For RTM_CHANGE/LOCK, if we got multipath routes,
-			 * a matching RTAX_GATEWAY is required.
-			 * OR
-			 * If a gateway is specified then RTM_GET and
-			 * RTM_LOCK must match the gateway no matter
-			 * what even in the non multipath case.
+			 * Only RTM_GET may use an empty gateway
+			 * on multipath routes
 			 */
-			if ((rt->rt_flags & RTF_MPATH) ||
-			    (info.rti_info[RTAX_GATEWAY] && rtm->rtm_type !=
-			    RTM_CHANGE)) {
-				rt = rt_mpath_matchgate(rt,
-				    info.rti_info[RTAX_GATEWAY], prio);
-				if (!rt) {
-					error = ESRCH;
-					goto flush;
-				}
-				/*
-				 * only RTM_GET may use an empty gateway
-				 * on multipath routes
-				 */
-				if (!info.rti_info[RTAX_GATEWAY] &&
-				    rtm->rtm_type != RTM_GET) {
-					rt = NULL;
-					error = ESRCH;
-					goto flush;
-				}
+			if (info.rti_info[RTAX_GATEWAY] == NULL &&
+			    rtm->rtm_type != RTM_GET) {
+				rt = NULL;
+				error = ESRCH;
+				goto flush;
 			}
 		}
 #endif
@@ -776,8 +774,7 @@ report:
 					rt->rt_ifp = ifa->ifa_ifp;
 #ifndef SMALL_KERNEL
 					/* recheck link state after ifp change*/
-					rt_if_linkstate_change(
-					    (struct radix_node *)rt, rt->rt_ifp,
+					rt_if_linkstate_change(rt, rt->rt_ifp,
 					    tableid);
 #endif
 				}
@@ -1197,10 +1194,9 @@ rt_ifannouncemsg(struct ifnet *ifp, int what)
  * This is used in dumping the kernel table via sysctl().
  */
 int
-sysctl_dumpentry(struct radix_node *rn, void *v, u_int id)
+sysctl_dumpentry(struct rtentry *rt, void *v, unsigned int id)
 {
 	struct walkarg		*w = v;
-	struct rtentry		*rt = (struct rtentry *)rn;
 	int			 error = 0, size;
 	struct rt_addrinfo	 info;
 #ifdef MPLS
@@ -1332,7 +1328,6 @@ int
 sysctl_rtable(int *name, u_int namelen, void *where, size_t *given, void *new,
     size_t newlen)
 {
-	struct radix_node_head	*rnh;
 	int			 i, s, error = EINVAL;
 	u_char  		 af;
 	struct walkarg		 w;
@@ -1363,12 +1358,14 @@ sysctl_rtable(int *name, u_int namelen, void *where, size_t *given, void *new,
 
 	case NET_RT_DUMP:
 	case NET_RT_FLAGS:
-		for (i = 1; i <= AF_MAX; i++)
-			if ((rnh = rtable_get(tableid, i)) != NULL &&
-			    (af == 0 || af == i) &&
-			    (error = (*rnh->rnh_walktree)(rnh,
-			    sysctl_dumpentry, &w)))
+		for (i = 1; i <= AF_MAX; i++) {
+			if (af != 0 && af != i)
+				continue;
+
+			error = rtable_walk(tableid, i, sysctl_dumpentry, &w);
+			if (error)
 				break;
+		}
 		break;
 
 	case NET_RT_IFLIST:
diff --git a/sys/netinet/if_ether.c b/sys/netinet/if_ether.c
index 8fbf0bdc77a..4b9d5452357 100644
--- a/sys/netinet/if_ether.c
+++ b/sys/netinet/if_ether.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_ether.c,v 1.158 2015/07/17 18:35:25 mpi Exp $	*/
+/*	$OpenBSD: if_ether.c,v 1.159 2015/07/18 15:51:16 mpi Exp $	*/
 /*	$NetBSD: if_ether.c,v 1.31 1996/05/11 12:59:58 mycroft Exp $	*/
 
 /*
@@ -118,7 +118,7 @@ struct ifnet *revarp_ifp;
 void	db_print_sa(struct sockaddr *);
 void	db_print_ifa(struct ifaddr *);
 void	db_print_llinfo(caddr_t);
-int	db_show_radix_node(struct radix_node *, void *, u_int);
+int	db_show_rtentry(struct rtentry *, void *, unsigned int);
 #endif
 
 /*
@@ -1077,14 +1077,12 @@ db_print_llinfo(caddr_t li)
 }
 
 /*
- * Function to pass to rn_walktree().
+ * Function to pass to rtalble_walk().
  * Return non-zero error to abort walk.
  */
 int
-db_show_radix_node(struct radix_node *rn, void *w, u_int id)
+db_show_rtentry(struct rtentry *rt, void *w, unsigned int id)
 {
-	struct rtentry *rt = (struct rtentry *)rn;
-
 	db_printf("rtentry=%p", rt);
 
 	db_printf(" flags=0x%x refcnt=%d use=%llu expire=%lld rtableid=%u\n",
@@ -1115,14 +1113,8 @@ db_show_radix_node(struct radix_node *rn, void *w, u_int id)
 int
 db_show_arptab(void)
 {
-	struct radix_node_head *rnh;
-	rnh = rtable_get(0, AF_INET);
 	db_printf("Route tree for AF_INET\n");
-	if (rnh == NULL) {
-		db_printf(" (not initialized)\n");
-		return (0);
-	}
-	rn_walktree(rnh, db_show_radix_node, NULL);
+	rtable_walk(0, AF_INET, db_show_rtentry, NULL);
 	return (0);
 }
 #endif
diff --git a/sys/netinet/in_proto.c b/sys/netinet/in_proto.c
index d11a3f84a29..1e074a11ab6 100644
--- a/sys/netinet/in_proto.c
+++ b/sys/netinet/in_proto.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in_proto.c,v 1.63 2014/12/05 15:50:04 mpi Exp $	*/
+/*	$OpenBSD: in_proto.c,v 1.64 2015/07/18 15:51:17 mpi Exp $	*/
 /*	$NetBSD: in_proto.c,v 1.14 1996/02/18 18:58:32 christos Exp $	*/
 
 /*
@@ -106,10 +106,7 @@
 #include <net/if.h>
 #include <net/if_var.h>
 #include <net/route.h>
-#include <net/radix.h>
-#ifndef SMALL_KERNEL
-#include <net/radix_mpath.h>
-#endif
+#include <net/rtable.h>
 
 #include <netinet/in.h>
 #include <netinet/ip.h>
@@ -313,9 +310,5 @@ struct protosw inetsw[] = {
 struct domain inetdomain =
     { AF_INET, "internet", 0, 0, 0,
       inetsw, &inetsw[nitems(inetsw)], 0,
-#ifndef SMALL_KERNEL
-      rn_mpath_inithead,
-#else
-      rn_inithead,
-#endif
+      rtable_attach,
       32, sizeof(struct sockaddr_in) };
diff --git a/sys/netinet6/in6_proto.c b/sys/netinet6/in6_proto.c
index c16da207152..de32544d985 100644
--- a/sys/netinet6/in6_proto.c
+++ b/sys/netinet6/in6_proto.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in6_proto.c,v 1.77 2014/12/19 17:14:40 tedu Exp $	*/
+/*	$OpenBSD: in6_proto.c,v 1.78 2015/07/18 15:51:17 mpi Exp $	*/
 /*	$KAME: in6_proto.c,v 1.66 2000/10/10 15:35:47 itojun Exp $	*/
 
 /*
@@ -70,11 +70,8 @@
 
 #include <net/if.h>
 #include <net/if_var.h>
-#include <net/radix.h>
-#ifndef SMALL_KERNEL
-#include <net/radix_mpath.h>
-#endif
 #include <net/route.h>
+#include <net/rtable.h>
 
 #include <netinet/in.h>
 #include <netinet/ip.h>
@@ -249,11 +246,7 @@ struct domain inet6domain =
     { AF_INET6, "internet6", 0, 0, 0,
       (struct protosw *)inet6sw,
       (struct protosw *)&inet6sw[nitems(inet6sw)], 0,
-#ifndef SMALL_KERNEL
-      rn_mpath_inithead,
-#else
-      rn_inithead,
-#endif
+      rtable_attach,
       offsetof(struct sockaddr_in6, sin6_addr) << 3,
       sizeof(struct sockaddr_in6),
       in6_domifattach, in6_domifdetach, };
diff --git a/sys/netinet6/nd6_rtr.c b/sys/netinet6/nd6_rtr.c
index 6a1255538d8..fa2ab04e923 100644
--- a/sys/netinet6/nd6_rtr.c
+++ b/sys/netinet6/nd6_rtr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: nd6_rtr.c,v 1.112 2015/07/18 15:05:32 mpi Exp $	*/
+/*	$OpenBSD: nd6_rtr.c,v 1.113 2015/07/18 15:51:17 mpi Exp $	*/
 /*	$KAME: nd6_rtr.c,v 1.97 2001/02/07 11:09:13 itojun Exp $	*/
 
 /*
@@ -49,7 +49,7 @@
 #include <net/if_var.h>
 #include <net/if_types.h>
 #include <net/route.h>
-#include <net/radix.h>
+#include <net/rtable.h>
 
 #include <netinet/in.h>
 #include <netinet6/in6_var.h>
@@ -72,7 +72,7 @@ void purge_detached(struct ifnet *);
 
 void in6_init_address_ltimes(struct nd_prefix *, struct in6_addrlifetime *);
 
-int rt6_deleteroute(struct radix_node *, void *, u_int);
+int rt6_deleteroute(struct rtentry *, void *, unsigned int);
 
 void nd6_addr_add(void *);
 
@@ -2184,26 +2184,24 @@ in6_init_address_ltimes(struct nd_prefix *new, struct in6_addrlifetime *lt6)
 void
 rt6_flush(struct in6_addr *gateway, struct ifnet *ifp)
 {
-	struct radix_node_head *rnh = rtable_get(ifp->if_rdomain, AF_INET6);
-	int s = splsoftnet();
+	int s;
 
 	/* We'll care only link-local addresses */
-	if (!IN6_IS_ADDR_LINKLOCAL(gateway)) {
-		splx(s);
+	if (!IN6_IS_ADDR_LINKLOCAL(gateway))
 		return;
-	}
+
 	/* XXX: hack for KAME's link-local address kludge */
 	gateway->s6_addr16[1] = htons(ifp->if_index);
 
-	rnh->rnh_walktree(rnh, rt6_deleteroute, (void *)gateway);
+	s = splsoftnet();
+	rtable_walk(ifp->if_rdomain, AF_INET6, rt6_deleteroute, gateway);
 	splx(s);
 }
 
 int
-rt6_deleteroute(struct radix_node *rn, void *arg, u_int id)
+rt6_deleteroute(struct rtentry *rt, void *arg, unsigned int id)
 {
 	struct rt_addrinfo info;
-	struct rtentry *rt = (struct rtentry *)rn;
 	struct in6_addr *gate = (struct in6_addr *)arg;
 
 	if (rt->rt_gateway == NULL || rt->rt_gateway->sa_family != AF_INET6)
diff --git a/sys/netmpls/mpls_proto.c b/sys/netmpls/mpls_proto.c
index 0354abce9d6..d81f98a337c 100644
--- a/sys/netmpls/mpls_proto.c
+++ b/sys/netmpls/mpls_proto.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: mpls_proto.c,v 1.9 2014/12/05 15:50:04 mpi Exp $	*/
+/*	$OpenBSD: mpls_proto.c,v 1.10 2015/07/18 15:51:17 mpi Exp $	*/
 
 /*
  * Copyright (C) 1999, 2000 and 2001 AYAME Project, WIDE Project.
@@ -38,8 +38,7 @@
 
 #include <net/if.h>
 #include <net/if_var.h>
-#include <net/radix.h>
-#include <net/radix_mpath.h>
+#include <net/rtable.h>
 
 #include <netmpls/mpls.h>
 
@@ -69,7 +68,7 @@ struct domain mplsdomain = {
 	AF_MPLS, "mpls", mpls_init, 0, 0,
 	mplssw,
 	&mplssw[nitems(mplssw)], 0,
-	rn_mpath_inithead,
+	rtable_attach,
 	offsetof(struct sockaddr_mpls, smpls_label) << 3,
 	sizeof(struct sockaddr_mpls)
 };
diff --git a/sys/sys/sysctl.h b/sys/sys/sysctl.h
index 425dfc51b62..33e0222cbff 100644
--- a/sys/sys/sysctl.h
+++ b/sys/sys/sysctl.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: sysctl.h,v 1.155 2015/02/11 05:09:33 claudio Exp $	*/
+/*	$OpenBSD: sysctl.h,v 1.156 2015/07/18 15:51:17 mpi Exp $	*/
 /*	$NetBSD: sysctl.h,v 1.16 1996/04/09 20:55:36 cgd Exp $	*/
 
 /*
@@ -942,9 +942,9 @@ int sysctl_rdstruct(void *, size_t *, void *, const void *, int);
 int sysctl_struct(void *, size_t *, void *, size_t, void *, int);
 int sysctl_file(int *, u_int, char *, size_t *, struct proc *);
 int sysctl_doproc(int *, u_int, char *, size_t *);
-struct radix_node;
+struct rtentry;
 struct walkarg;
-int sysctl_dumpentry(struct radix_node *, void *, u_int);
+int sysctl_dumpentry(struct rtentry *, void *, unsigned int);
 int sysctl_iflist(int, struct walkarg *);
 int sysctl_rtable(int *, u_int, void *, size_t *, void *, size_t);
 int sysctl_clockrate(char *, size_t *, void *);