Index: sys/netinet/icmp6.h
===================================================================
--- sys/netinet/icmp6.h
+++ sys/netinet/icmp6.h
@@ -693,7 +693,7 @@
 
 #ifdef _KERNEL
 # ifdef __STDC__
-struct	rtentry;
+struct	nhop_object;
 struct	rttimer;
 struct	in6_multi;
 # endif
@@ -705,7 +705,7 @@
 void	icmp6_slowtimo(void);
 void	icmp6_prepare(struct mbuf *);
 void	icmp6_redirect_input(struct mbuf *, int);
-void	icmp6_redirect_output(struct mbuf *, struct rtentry *);
+void	icmp6_redirect_output(struct mbuf *, struct nhop_object *);
 
 struct	ip6ctlparam;
 void	icmp6_mtudisc_update(struct ip6ctlparam *, int);
Index: sys/netinet/in_pcb.c
===================================================================
--- sys/netinet/in_pcb.c
+++ sys/netinet/in_pcb.c
@@ -88,6 +88,7 @@
 #include <netinet/in_pcb.h>
 #ifdef INET
 #include <netinet/in_var.h>
+#include <netinet/in_fib.h>
 #endif
 #include <netinet/ip_var.h>
 #include <netinet/tcp_var.h>
@@ -102,6 +103,7 @@
 #include <netinet6/in6_var.h>
 #include <netinet6/ip6_var.h>
 #endif /* INET6 */
+#include <net/route/nhop.h>
 #endif
 
 #include <netipsec/ipsec_support.h>
@@ -1033,8 +1035,8 @@
 {
 	struct ifaddr *ifa;
 	struct sockaddr *sa;
-	struct sockaddr_in *sin;
-	struct route sro;
+	struct sockaddr_in *sin, dst;
+	struct nhop_object *nh;
 	int error;
 
 	NET_EPOCH_ASSERT();
@@ -1047,9 +1049,10 @@
 		return (0);
 
 	error = 0;
-	bzero(&sro, sizeof(sro));
 
-	sin = (struct sockaddr_in *)&sro.ro_dst;
+	nh = NULL;
+	bzero(&dst, sizeof(dst));
+	sin = &dst;
 	sin->sin_family = AF_INET;
 	sin->sin_len = sizeof(struct sockaddr_in);
 	sin->sin_addr.s_addr = faddr->s_addr;
@@ -1061,7 +1064,8 @@
 	 * Find out route to destination.
 	 */
 	if ((inp->inp_socket->so_options & SO_DONTROUTE) == 0)
-		in_rtalloc_ign(&sro, 0, inp->inp_inc.inc_fibnum);
+		nh = fib4_lookup_nh_ptr(inp->inp_inc.inc_fibnum, *faddr,
+		    0, NHR_NONE, 0);
 
 	/*
 	 * If we found a route, use the address corresponding to
@@ -1071,7 +1075,7 @@
 	 * network and try to find a corresponding interface to take
 	 * the source address from.
 	 */
-	if (sro.ro_rt == NULL || sro.ro_rt->rt_ifp == NULL) {
+	if (nh == NULL || nh->nh_ifp == NULL) {
 		struct in_ifaddr *ia;
 		struct ifnet *ifp;
 
@@ -1124,22 +1128,22 @@
 	 *    belonging to this jail. If so use it.
 	 * 3. as a last resort return the 'default' jail address.
 	 */
-	if ((sro.ro_rt->rt_ifp->if_flags & IFF_LOOPBACK) == 0) {
+	if ((nh->nh_ifp->if_flags & IFF_LOOPBACK) == 0) {
 		struct in_ifaddr *ia;
 		struct ifnet *ifp;
 
 		/* If not jailed, use the default returned. */
 		if (cred == NULL || !prison_flag(cred, PR_IP4)) {
-			ia = (struct in_ifaddr *)sro.ro_rt->rt_ifa;
+			ia = (struct in_ifaddr *)nh->nh_ifa;
 			laddr->s_addr = ia->ia_addr.sin_addr.s_addr;
 			goto done;
 		}
 
 		/* Jailed. */
 		/* 1. Check if the iface address belongs to the jail. */
-		sin = (struct sockaddr_in *)sro.ro_rt->rt_ifa->ifa_addr;
+		sin = (struct sockaddr_in *)nh->nh_ifa->ifa_addr;
 		if (prison_check_ip4(cred, &sin->sin_addr) == 0) {
-			ia = (struct in_ifaddr *)sro.ro_rt->rt_ifa;
+			ia = (struct in_ifaddr *)nh->nh_ifa;
 			laddr->s_addr = ia->ia_addr.sin_addr.s_addr;
 			goto done;
 		}
@@ -1149,7 +1153,7 @@
 		 *    belonging to this jail.
 		 */
 		ia = NULL;
-		ifp = sro.ro_rt->rt_ifp;
+		ifp = nh->nh_ifp;
 		CK_STAILQ_FOREACH(ifa, &ifp->if_addrhead, ifa_link) {
 			sa = ifa->ifa_addr;
 			if (sa->sa_family != AF_INET)
@@ -1179,7 +1183,7 @@
 	 * In case of jails, check that it is an address of the jail
 	 * and if we cannot find, fall back to the 'default' jail address.
 	 */
-	if ((sro.ro_rt->rt_ifp->if_flags & IFF_LOOPBACK) != 0) {
+	if ((nh->nh_ifp->if_flags & IFF_LOOPBACK) != 0) {
 		struct sockaddr_in sain;
 		struct in_ifaddr *ia;
 
@@ -1234,8 +1238,6 @@
 	}
 
 done:
-	if (sro.ro_rt != NULL)
-		RTFREE(sro.ro_rt);
 	return (error);
 }
 
Index: sys/netinet/ip_fastfwd.c
===================================================================
--- sys/netinet/ip_fastfwd.c
+++ sys/netinet/ip_fastfwd.c
@@ -96,6 +96,7 @@
 #include <net/if_dl.h>
 #include <net/pfil.h>
 #include <net/route.h>
+#include <net/route/nhop.h>
 #include <net/vnet.h>
 
 #include <netinet/in.h>
@@ -111,11 +112,13 @@
 #include <machine/in_cksum.h>
 
 static int
-ip_findroute(struct nhop4_basic *pnh, struct in_addr dest, struct mbuf *m)
+ip_findroute(struct nhop_object **pnh, struct in_addr dest, struct mbuf *m)
 {
+	struct nhop_object *nh;
 
-	bzero(pnh, sizeof(*pnh));
-	if (fib4_lookup_nh_basic(M_GETFIB(m), dest, 0, 0, pnh) != 0) {
+	nh = fib4_lookup_nh_ptr(M_GETFIB(m), dest, 0, NHR_NONE,
+	    m->m_pkthdr.flowid);
+	if (nh == NULL) {
 		IPSTAT_INC(ips_noroute);
 		IPSTAT_INC(ips_cantforward);
 		icmp_error(m, ICMP_UNREACH, ICMP_UNREACH_HOST, 0, 0);
@@ -124,18 +127,20 @@
 	/*
 	 * Drop blackholed traffic and directed broadcasts.
 	 */
-	if ((pnh->nh_flags & (NHF_BLACKHOLE | NHF_BROADCAST)) != 0) {
+	if ((nh->nh_flags & (NHF_BLACKHOLE | NHF_BROADCAST)) != 0) {
 		IPSTAT_INC(ips_cantforward);
 		m_freem(m);
 		return (EHOSTUNREACH);
 	}
 
-	if (pnh->nh_flags & NHF_REJECT) {
+	if (nh->nh_flags & NHF_REJECT) {
 		IPSTAT_INC(ips_cantforward);
 		icmp_error(m, ICMP_UNREACH, ICMP_UNREACH_HOST, 0, 0);
 		return (EHOSTUNREACH);
 	}
 
+	*pnh = nh;
+
 	return (0);
 }
 
@@ -151,7 +156,7 @@
 {
 	struct ip *ip;
 	struct mbuf *m0 = NULL;
-	struct nhop4_basic nh;
+	struct nhop_object *nh;
 	struct sockaddr_in dst;
 	struct in_addr dest, odest, rtdest;
 	uint16_t ip_len, ip_off;
@@ -323,7 +328,7 @@
 	if (!PFIL_HOOKED_OUT(V_inet_pfil_head))
 		goto passout;
 
-	if (pfil_run_hooks(V_inet_pfil_head, &m, nh.nh_ifp,
+	if (pfil_run_hooks(V_inet_pfil_head, &m, nh->nh_ifp,
 	    PFIL_OUT | PFIL_FWD, NULL) != PFIL_PASS)
 		goto drop;
 
@@ -376,12 +381,15 @@
 	bzero(&dst, sizeof(dst));
 	dst.sin_family = AF_INET;
 	dst.sin_len = sizeof(dst);
-	dst.sin_addr = nh.nh_addr;
+	if (nh->nh_flags & NHF_GATEWAY)
+		dst.sin_addr = nh->gw4_sa.sin_addr;
+	else
+		dst.sin_addr = dest;
 
 	/*
 	 * Check if packet fits MTU or if hardware will fragment for us
 	 */
-	if (ip_len <= nh.nh_mtu) {
+	if (ip_len <= nh->nh_mtu) {
 		/*
 		 * Avoid confusing lower layers.
 		 */
@@ -389,8 +397,8 @@
 		/*
 		 * Send off the packet via outgoing interface
 		 */
-		IP_PROBE(send, NULL, NULL, ip, nh.nh_ifp, ip, NULL);
-		error = (*nh.nh_ifp->if_output)(nh.nh_ifp, m,
+		IP_PROBE(send, NULL, NULL, ip, nh->nh_ifp, ip, NULL);
+		error = (*nh->nh_ifp->if_output)(nh->nh_ifp, m,
 		    (struct sockaddr *)&dst, NULL);
 	} else {
 		/*
@@ -399,15 +407,15 @@
 		if (ip_off & IP_DF) {
 			IPSTAT_INC(ips_cantfrag);
 			icmp_error(m, ICMP_UNREACH, ICMP_UNREACH_NEEDFRAG,
-				0, nh.nh_mtu);
+				0, nh->nh_mtu);
 			goto consumed;
 		} else {
 			/*
 			 * We have to fragment the packet
 			 */
 			m->m_pkthdr.csum_flags |= CSUM_IP;
-			if (ip_fragment(ip, &m, nh.nh_mtu,
-			    nh.nh_ifp->if_hwassist) != 0)
+			if (ip_fragment(ip, &m, nh->nh_mtu,
+			    nh->nh_ifp->if_hwassist) != 0)
 				goto drop;
 			KASSERT(m != NULL, ("null mbuf and no error"));
 			/*
@@ -423,10 +431,9 @@
 				m_clrprotoflags(m);
 
 				IP_PROBE(send, NULL, NULL,
-				    mtod(m, struct ip *), nh.nh_ifp,
+				    mtod(m, struct ip *), nh->nh_ifp,
 				    mtod(m, struct ip *), NULL);
-				/* XXX: we can use cached route here */
-				error = (*nh.nh_ifp->if_output)(nh.nh_ifp, m,
+				error = (*nh->nh_ifp->if_output)(nh->nh_ifp, m,
 				    (struct sockaddr *)&dst, NULL);
 				if (error)
 					break;
Index: sys/netinet/ip_icmp.c
===================================================================
--- sys/netinet/ip_icmp.c
+++ sys/netinet/ip_icmp.c
@@ -52,6 +52,7 @@
 #include <net/if_var.h>
 #include <net/if_types.h>
 #include <net/route.h>
+#include <net/route/nhop.h>
 #include <net/vnet.h>
 
 #include <netinet/in.h>
@@ -945,7 +946,7 @@
 icmp_verify_redirect_gateway(struct sockaddr_in *src, struct sockaddr_in *dst,
     struct sockaddr_in *gateway, u_int fibnum)
 {
-	struct rtentry *rt;
+	struct nhop_object *nh;
 	struct ifaddr *ifa;
 
 	NET_EPOCH_ASSERT();
@@ -958,8 +959,8 @@
 	if (ifa_ifwithaddr_check((struct sockaddr *)gateway))
 		return (EHOSTUNREACH);
 
-	rt = rtalloc1_fib((struct sockaddr *)dst, 0, 0UL, fibnum); /* NB: rt is locked */
-	if (rt == NULL)
+	nh = fib4_lookup_nh_ptr(fibnum, dst->sin_addr, 0, NHR_NONE, 0);
+	if (nh == NULL)
 		return (EINVAL);
 
 	/*
@@ -968,28 +969,19 @@
 	 * we have a routing loop, perhaps as a result of an interface
 	 * going down recently.
 	 */
-	if (!sa_equal((struct sockaddr *)src, rt->rt_gateway)) {
-		RTFREE_LOCKED(rt);
+	if (!sa_equal((struct sockaddr *)src, &nh->gw_sa))
 		return (EINVAL);
-	}
-	if (rt->rt_ifa != ifa && ifa->ifa_addr->sa_family != AF_LINK) {
-		RTFREE_LOCKED(rt);
+	if (nh->nh_ifa != ifa && ifa->ifa_addr->sa_family != AF_LINK)
 		return (EINVAL);
-	}
 
 	/* If host route already exists, ignore redirect. */
-	if (rt->rt_flags & RTF_HOST) {
-		RTFREE_LOCKED(rt);
+	if (nh->nh_flags & NHF_HOST)
 		return (EEXIST);
-	}
 
 	/* If the prefix is directly reachable, ignore redirect. */
-	if (!(rt->rt_flags & RTF_GATEWAY)) {
-		RTFREE_LOCKED(rt);
+	if (!(nh->nh_flags & NHF_GATEWAY))
 		return (EEXIST);
-	}
 
-	RTFREE_LOCKED(rt);
 	return (0);
 }
 
Index: sys/netinet6/icmp6.c
===================================================================
--- sys/netinet6/icmp6.c
+++ sys/netinet6/icmp6.c
@@ -93,6 +93,7 @@
 #include <net/if_llatbl.h>
 #include <net/if_types.h>
 #include <net/route.h>
+#include <net/route/nhop.h>
 #include <net/vnet.h>
 
 #include <netinet/in.h>
@@ -2412,7 +2413,7 @@
 }
 
 void
-icmp6_redirect_output(struct mbuf *m0, struct rtentry *rt)
+icmp6_redirect_output(struct mbuf *m0, struct nhop_object *nh)
 {
 	struct ifnet *ifp;	/* my outgoing interface */
 	struct in6_addr *ifp_ll6;
@@ -2435,7 +2436,7 @@
 		goto fail;
 
 	/* sanity check */
-	if (!m0 || !rt || !(rt->rt_flags & RTF_UP) || !(ifp = rt->rt_ifp))
+	if (!m0 || !nh || !(NH_IS_VALID(nh)) || !(ifp = nh->nh_ifp))
 		goto fail;
 
 	/*
@@ -2469,7 +2470,7 @@
 	m = m_getcl(M_NOWAIT, MT_DATA, M_PKTHDR);
 	if (m == NULL)
 		goto fail;
-	M_SETFIB(m, rt->rt_fibnum);
+	M_SETFIB(m, M_GETFIB(m0));
 	maxlen = M_TRAILINGSPACE(m);
 	maxlen = min(IPV6_MMTU, maxlen);
 	/* just for safety */
@@ -2491,9 +2492,9 @@
 	}
 
 	/* get ip6 linklocal address for the router. */
-	if (rt->rt_gateway && (rt->rt_flags & RTF_GATEWAY)) {
+	if (nh->nh_flags & NHF_GATEWAY) {
 		struct sockaddr_in6 *sin6;
-		sin6 = (struct sockaddr_in6 *)rt->rt_gateway;
+		sin6 = &nh->gw6_sa;
 		router_ll6 = &sin6->sin6_addr;
 		if (!IN6_IS_ADDR_LINKLOCAL(router_ll6))
 			router_ll6 = (struct in6_addr *)NULL;
@@ -2517,7 +2518,7 @@
 	nd_rd->nd_rd_type = ND_REDIRECT;
 	nd_rd->nd_rd_code = 0;
 	nd_rd->nd_rd_reserved = 0;
-	if (rt->rt_flags & RTF_GATEWAY) {
+	if (nh->nh_flags & NHF_GATEWAY) {
 		/*
 		 * nd_rd->nd_rd_target must be a link-local address in
 		 * better router cases.
Index: sys/netinet6/ip6_fastfwd.c
===================================================================
--- sys/netinet6/ip6_fastfwd.c
+++ sys/netinet6/ip6_fastfwd.c
@@ -40,6 +40,7 @@
 #include <net/if.h>
 #include <net/if_var.h>
 #include <net/route.h>
+#include <net/route/nhop.h>
 #include <net/pfil.h>
 #include <net/vnet.h>
 
@@ -55,30 +56,35 @@
 #include <netinet6/nd6.h>
 
 static int
-ip6_findroute(struct nhop6_basic *pnh, const struct sockaddr_in6 *dst,
+ip6_findroute(struct nhop_object **pnh, const struct sockaddr_in6 *dst,
     struct mbuf *m)
 {
+	struct nhop_object *nh;
 
-	if (fib6_lookup_nh_basic(M_GETFIB(m), &dst->sin6_addr,
-	    dst->sin6_scope_id, 0, dst->sin6_flowinfo, pnh) != 0) {
+	nh = fib6_lookup_nh_ptr(M_GETFIB(m), &dst->sin6_addr,
+	    dst->sin6_scope_id, NHR_NONE, m->m_pkthdr.flowid);
+       if (nh == NULL) {
 		IP6STAT_INC(ip6s_noroute);
 		IP6STAT_INC(ip6s_cantforward);
 		icmp6_error(m, ICMP6_DST_UNREACH,
 		    ICMP6_DST_UNREACH_NOROUTE, 0);
 		return (EHOSTUNREACH);
 	}
-	if (pnh->nh_flags & NHF_BLACKHOLE) {
+	if (nh->nh_flags & NHF_BLACKHOLE) {
 		IP6STAT_INC(ip6s_cantforward);
 		m_freem(m);
 		return (EHOSTUNREACH);
 	}
 
-	if (pnh->nh_flags & NHF_REJECT) {
+	if (nh->nh_flags & NHF_REJECT) {
 		IP6STAT_INC(ip6s_cantforward);
 		icmp6_error(m, ICMP6_DST_UNREACH,
 		    ICMP6_DST_UNREACH_REJECT, 0);
 		return (EHOSTUNREACH);
 	}
+
+	*pnh = nh;
+
 	return (0);
 }
 
@@ -86,7 +92,7 @@
 ip6_tryforward(struct mbuf *m)
 {
 	struct sockaddr_in6 dst;
-	struct nhop6_basic nh;
+	struct nhop_object *nh;
 	struct m_tag *fwd_tag;
 	struct ip6_hdr *ip6;
 	struct ifnet *rcvif;
@@ -196,9 +202,9 @@
 		goto dropin;
 	}
 	if (!PFIL_HOOKED_OUT(V_inet6_pfil_head)) {
-		if (m->m_pkthdr.len > nh.nh_mtu) {
-			in6_ifstat_inc(nh.nh_ifp, ifs6_in_toobig);
-			icmp6_error(m, ICMP6_PACKET_TOO_BIG, 0, nh.nh_mtu);
+		if (m->m_pkthdr.len > nh->nh_mtu) {
+			in6_ifstat_inc(nh->nh_ifp, ifs6_in_toobig);
+			icmp6_error(m, ICMP6_PACKET_TOO_BIG, 0, nh->nh_mtu);
 			m = NULL;
 			goto dropout;
 		}
@@ -208,7 +214,7 @@
 	/*
 	 * Outgoing packet firewall processing.
 	 */
-	if (pfil_run_hooks(V_inet6_pfil_head, &m, nh.nh_ifp, PFIL_OUT |
+	if (pfil_run_hooks(V_inet6_pfil_head, &m, nh->nh_ifp, PFIL_OUT |
 	    PFIL_FWD, NULL) != PFIL_PASS)
 		goto dropout;
 
@@ -216,9 +222,9 @@
 	 * We used slow path processing for packets with scoped addresses.
 	 * So, scope checks aren't needed here.
 	 */
-	if (m->m_pkthdr.len > nh.nh_mtu) {
-		in6_ifstat_inc(nh.nh_ifp, ifs6_in_toobig);
-		icmp6_error(m, ICMP6_PACKET_TOO_BIG, 0, nh.nh_mtu);
+	if (m->m_pkthdr.len > nh->nh_mtu) {
+		in6_ifstat_inc(nh->nh_ifp, ifs6_in_toobig);
+		icmp6_error(m, ICMP6_PACKET_TOO_BIG, 0, nh->nh_mtu);
 		m = NULL;
 		goto dropout;
 	}
@@ -272,16 +278,17 @@
 	}
 
 	m_clrprotoflags(m);	/* Avoid confusing lower layers. */
-	IP_PROBE(send, NULL, NULL, ip6, nh.nh_ifp, NULL, ip6);
+	IP_PROBE(send, NULL, NULL, ip6, nh->nh_ifp, NULL, ip6);
 
-	dst.sin6_addr = nh.nh_addr;
-	error = (*nh.nh_ifp->if_output)(nh.nh_ifp, m,
+	if (nh->nh_flags & NHF_GATEWAY)
+		dst.sin6_addr = nh->gw6_sa.sin6_addr;
+	error = (*nh->nh_ifp->if_output)(nh->nh_ifp, m,
 	    (struct sockaddr *)&dst, NULL);
 	if (error != 0) {
-		in6_ifstat_inc(nh.nh_ifp, ifs6_out_discard);
+		in6_ifstat_inc(nh->nh_ifp, ifs6_out_discard);
 		IP6STAT_INC(ip6s_cantforward);
 	} else {
-		in6_ifstat_inc(nh.nh_ifp, ifs6_out_forward);
+		in6_ifstat_inc(nh->nh_ifp, ifs6_out_forward);
 		IP6STAT_INC(ip6s_forward);
 	}
 	return (NULL);
@@ -289,7 +296,7 @@
 	in6_ifstat_inc(rcvif, ifs6_in_discard);
 	goto drop;
 dropout:
-	in6_ifstat_inc(nh.nh_ifp, ifs6_out_discard);
+	in6_ifstat_inc(nh->nh_ifp, ifs6_out_discard);
 drop:
 	if (m != NULL)
 		m_freem(m);
Index: sys/netinet6/ip6_forward.c
===================================================================
--- sys/netinet6/ip6_forward.c
+++ sys/netinet6/ip6_forward.c
@@ -401,7 +401,7 @@
 	switch (error) {
 	case 0:
 		if (type == ND_REDIRECT) {
-			icmp6_redirect_output(mcopy, rt);
+			icmp6_redirect_output(mcopy, rt->rt_nhop);
 			goto out;
 		}
 		goto freecopy;