Add support for equal-cost multipath IP.

To minimise path disruptions, this implements recommendations made in RFC2992 -
the hash-threshold mechanism to select paths based on source/destination IP
address pairs, and inserts multipath routes in the middle of the route table.

To enable multipath distribution, use:
   sysctl net.inet.ip.multipath=1
and/or:
   sysctl net.inet6.ip6.multipath=1

testing norby@
ok claudio@ henning@ hshoexer@

16 files changed, 196 insertions, 68 deletions

diff --git a/sys/net/radix.c b/sys/net/radix.c
index 7f0650bf695..5847d511fee 100644
--- a/sys/net/radix.c
+++ b/sys/net/radix.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix.c,v 1.20 2006/02/06 17:37:28 jmc Exp $	*/
+/*	$OpenBSD: radix.c,v 1.21 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$NetBSD: radix.c,v 1.20 2003/08/07 16:32:56 agc Exp $	*/
 
 /*
@@ -537,14 +537,18 @@ rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 			/* permit multipath, if enabled for the family */
 			if (rn_mpath_capable(head) && netmask == tt->rn_mask) {
 				/*
-				 * go down to the end of multipaths, so that
-				 * new entry goes into the end of rn_dupedkey
-				 * chain.
+				 * Try to insert the new node in the middle
+				 * of the list of any preexisting multipaths,
+				 * to reduce the number of path disruptions
+				 * that occur as a result of an insertion,
+				 * per RFC2992.
 				 */
+				int mid = rn_mpath_count(tt) / 2;
 				do {
 					t = tt;
 					tt = tt->rn_dupedkey;
-				} while (tt && t->rn_mask == tt->rn_mask);
+				} while (tt && t->rn_mask == tt->rn_mask
+				    && --mid > 0);
 				break;
 			}
 #endif
diff --git a/sys/net/radix_mpath.c b/sys/net/radix_mpath.c
index a44d2adc8c8..31e89e4d095 100644
--- a/sys/net/radix_mpath.c
+++ b/sys/net/radix_mpath.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.c,v 1.5 2006/06/16 16:49:39 henning Exp $	*/
+/*	$OpenBSD: radix_mpath.c,v 1.6 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$KAME: radix_mpath.c,v 1.13 2002/10/28 21:05:59 itojun Exp $	*/
 
 /*
@@ -46,6 +46,13 @@
 #include <net/route.h>
 #include <dev/rndvar.h>
 
+#include <netinet/in.h>
+
+extern int ipmultipath;
+extern int ip6_multipath;
+
+u_int32_t rn_mpath_hash(struct route *, u_int32_t *);
+
 /*
  * give some jitter to hash, to avoid synchronization between routers
  */
@@ -54,7 +61,6 @@ static u_int32_t hashjitter;
 int
 rn_mpath_capable(struct radix_node_head *rnh)
 {
-
 	return rnh->rnh_multipath;
 }
 
@@ -208,35 +214,52 @@ rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt,
 	return 0;
 }
 
+/*
+ * allocate a route, potentially using multipath to select the peer.
+ */
 void
-rtalloc_mpath(struct route *ro, int hash, u_int tableid)
+rtalloc_mpath(struct route *ro, u_int32_t *srcaddrp, u_int tableid)
 {
-	struct radix_node *rn0, *rn;
-	int n;
+#if defined(INET) || defined(INET6)
+	struct radix_node *rn;
+	int hash, npaths, threshold;
+#endif
 
 	/*
-	 * XXX we don't attempt to lookup cached route again; what should
-	 * be done for sendto(2) case?
-	 */
+	 * return a cached entry if it is still valid, otherwise we increase
+	 * the risk of disrupting local flows.
+	 */ 
 	if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP))
-		return;				 /* XXX */
+		return;
 	ro->ro_rt = rtalloc1(&ro->ro_dst, 1, tableid);
+
 	/* if the route does not exist or it is not multipath, don't care */
-	if (!ro->ro_rt || !rn_mpath_next((struct radix_node *)ro->ro_rt))
+	if (!ro->ro_rt || !(ro->ro_rt->rt_flags & RTF_MPATH))
 		return;
 
-	/* beyond here, we use rn as the master copy */
-	rn0 = rn = (struct radix_node *)ro->ro_rt;
-	n = rn_mpath_count(rn0);
+	/* check if multipath routing is enabled for the specified protocol */
+	if (!(0
+#ifdef INET
+	    || (ipmultipath && ro->ro_dst.sa_family == AF_INET)
+#endif
+#ifdef INET6
+	    || (ip6_multipath && ro->ro_dst.sa_family == AF_INET6)
+#endif
+	    ))
+		return;
 
-	/* gw selection by Modulo-N Hash (RFC2991) XXX need improvement? */
-	hash += hashjitter;
-	hash %= n;
-	while (hash-- > 0 && rn) {
+#if defined(INET) || defined(INET6)
+	/* gw selection by Hash-Threshold (RFC 2992) */
+	rn = (struct radix_node *)ro->ro_rt;
+	npaths = rn_mpath_count(rn);
+	hash = rn_mpath_hash(ro, srcaddrp) & 0xffff;
+	threshold = 1 + (0xffff / npaths);
+	while (hash > threshold && rn) {
 		/* stay within the multipath routes */
 		if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)
 			break;
 		rn = rn->rn_dupedkey;
+		hash -= threshold;
 	}
 
 	/* XXX try filling rt_gwroute and avoid unreachable gw  */
@@ -248,6 +271,7 @@ rtalloc_mpath(struct route *ro, int hash, u_int tableid)
 	rtfree(ro->ro_rt);
 	ro->ro_rt = (struct rtentry *)rn;
 	ro->ro_rt->rt_refcnt++;
+#endif
 }
 
 int
@@ -255,7 +279,8 @@ rn_mpath_inithead(void **head, int off)
 {
 	struct radix_node_head *rnh;
 
-	hashjitter = arc4random();
+	while (hashjitter == 0)
+		hashjitter = arc4random();
 	if (rn_inithead(head, off) == 1) {
 		rnh = (struct radix_node_head *)*head;
 		rnh->rnh_multipath = 1;
@@ -263,3 +288,70 @@ rn_mpath_inithead(void **head, int off)
 	} else
 		return 0;
 }
+
+/*
+ * hash function based on pf_hash in pf.c
+ */
+#define mix(a,b,c) \
+	do {					\
+		a -= b; a -= c; a ^= (c >> 13);	\
+		b -= c; b -= a; b ^= (a << 8);	\
+		c -= a; c -= b; c ^= (b >> 13);	\
+		a -= b; a -= c; a ^= (c >> 12);	\
+		b -= c; b -= a; b ^= (a << 16);	\
+		c -= a; c -= b; c ^= (b >> 5);	\
+		a -= b; a -= c; a ^= (c >> 3);	\
+		b -= c; b -= a; b ^= (a << 10);	\
+		c -= a; c -= b; c ^= (b >> 15);	\
+	} while (0)
+
+u_int32_t
+rn_mpath_hash(struct route *ro, u_int32_t *srcaddrp)
+{
+	u_int32_t a, b, c;
+
+	a = b = 0x9e3779b9;
+	c = hashjitter;
+
+	switch (ro->ro_dst.sa_family) {
+#ifdef INET
+	case AF_INET:
+	    {
+		struct sockaddr_in *sin_dst;
+
+		sin_dst = (struct sockaddr_in *)&ro->ro_dst;
+		a += sin_dst->sin_addr.s_addr;
+		b += srcaddrp ? srcaddrp[0] : 0;
+		mix(a, b, c);
+		break;
+	    }
+#endif /* INET */
+#ifdef INET6
+	case AF_INET6:
+	    {
+		struct sockaddr_in6 *sin6_dst;
+
+		sin6_dst = (struct sockaddr_in6 *)&ro->ro_dst;
+		a += sin6_dst->sin6_addr.s6_addr32[0];
+		b += sin6_dst->sin6_addr.s6_addr32[2];
+		c += srcaddrp ? srcaddrp[0] : 0;
+		mix(a, b, c);
+		a += sin6_dst->sin6_addr.s6_addr32[1];
+		b += sin6_dst->sin6_addr.s6_addr32[3];
+		c += srcaddrp ? srcaddrp[1] : 0;
+		mix(a, b, c);
+		a += sin6_dst->sin6_addr.s6_addr32[2];
+		b += sin6_dst->sin6_addr.s6_addr32[1];
+		c += srcaddrp ? srcaddrp[2] : 0;
+		mix(a, b, c);
+		a += sin6_dst->sin6_addr.s6_addr32[3];
+		b += sin6_dst->sin6_addr.s6_addr32[0];
+		c += srcaddrp ? srcaddrp[3] : 0;
+		mix(a, b, c);
+		break;
+	    }
+#endif /* INET6 */
+	}
+
+	return c;
+}
diff --git a/sys/net/radix_mpath.h b/sys/net/radix_mpath.h
index 0aea740f556..cf75be8e134 100644
--- a/sys/net/radix_mpath.h
+++ b/sys/net/radix_mpath.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: radix_mpath.h,v 1.4 2006/06/16 16:49:39 henning Exp $	*/
+/*	$OpenBSD: radix_mpath.h,v 1.5 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$KAME: radix_mpath.h,v 1.9 2004/03/30 11:21:49 keiichi Exp $	*/
 
 /*
@@ -50,7 +50,7 @@ int	rn_mpath_count(struct radix_node *);
 struct rtentry *rt_mpath_matchgate(struct rtentry *, struct sockaddr *);
 int	rt_mpath_conflict(struct radix_node_head *, struct rtentry *,
 	struct sockaddr *, int);
-void	rtalloc_mpath(struct route *, int, u_int tableid);
+void	rtalloc_mpath(struct route *, u_int32_t *, u_int tableid);
 int	rn_mpath_inithead(void **, int);
 #endif
 
diff --git a/sys/net/route.h b/sys/net/route.h
index 230b016f51d..e6e370c337f 100644
--- a/sys/net/route.h
+++ b/sys/net/route.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.h,v 1.45 2006/06/16 16:52:08 henning Exp $	*/
+/*	$OpenBSD: route.h,v 1.46 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$NetBSD: route.h,v 1.9 1996/02/13 22:00:49 christos Exp $	*/
 
 /*
@@ -343,6 +343,9 @@ void	 rt_timer_remove_all(struct rtentry *);
 unsigned long	rt_timer_count(struct rttimer_queue *);
 void	 rt_timer_timer(void *);
 void	 rtalloc(struct route *);
+#ifdef SMALL_KERNEL
+#define	rtalloc_mpath(r, s, t)	rtalloc(r)
+#endif
 struct rtentry *
 	 rtalloc1(struct sockaddr *, int, u_int);
 void	 rtalloc_noclone(struct route *, int);
diff --git a/sys/netinet/in.h b/sys/netinet/in.h
index 33a9fb60315..eb27cf0b2cb 100644
--- a/sys/netinet/in.h
+++ b/sys/netinet/in.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in.h,v 1.70 2006/05/29 20:42:27 claudio Exp $	*/
+/*	$OpenBSD: in.h,v 1.71 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$NetBSD: in.h,v 1.20 1996/02/13 23:41:47 christos Exp $	*/
 
 /*
@@ -473,7 +473,8 @@ struct ip_mreq {
 #define	IPCTL_IPSEC_IPCOMP_ALGORITHM	29
 #define	IPCTL_IFQUEUE		30
 #define	IPCTL_MFORWARDING	31
-#define	IPCTL_MAXID		32
+#define	IPCTL_MULTIPATH		32
+#define	IPCTL_MAXID		33
 
 #define	IPCTL_NAMES { \
 	{ 0, 0 }, \
@@ -508,6 +509,7 @@ struct ip_mreq {
 	{ "ipsec-comp-alg", CTLTYPE_STRING }, \
 	{ "ifq", CTLTYPE_NODE }, \
 	{ "mforwarding", CTLTYPE_INT }, \
+	{ "multipath", CTLTYPE_INT } \
 }
 #define	IPCTL_VARS { \
 	NULL, \
@@ -542,6 +544,7 @@ struct ip_mreq {
 	NULL, \
 	NULL, \
 	&ipmforwarding, \
+	&ipmultipath \
 }
 
 /* INET6 stuff */
diff --git a/sys/netinet/in_pcb.c b/sys/netinet/in_pcb.c
index a131aa4fa59..bbbfccd2e35 100644
--- a/sys/netinet/in_pcb.c
+++ b/sys/netinet/in_pcb.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in_pcb.c,v 1.87 2006/06/16 16:49:40 henning Exp $	*/
+/*	$OpenBSD: in_pcb.c,v 1.88 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$NetBSD: in_pcb.c,v 1.25 1996/02/13 23:41:53 christos Exp $	*/
 
 /*
@@ -775,7 +775,7 @@ in_pcbrtentry(inp)
 			ro->ro_dst.sa_len = sizeof(struct sockaddr_in6);
 			((struct sockaddr_in6 *) &ro->ro_dst)->sin6_addr =
 			    inp->inp_faddr6;
-			rtalloc(ro);
+			rtalloc_mpath(ro, &inp->inp_laddr6.s6_addr32[0], 0);
 			break;
 #endif /* INET6 */
 		case PF_INET:
@@ -784,7 +784,7 @@ in_pcbrtentry(inp)
 			ro->ro_dst.sa_family = AF_INET;
 			ro->ro_dst.sa_len = sizeof(ro->ro_dst);
 			satosin(&ro->ro_dst)->sin_addr = inp->inp_faddr;
-			rtalloc(ro);
+			rtalloc_mpath(ro, &inp->inp_laddr.s_addr, 0);
 			break;
 		}
 	}
@@ -821,7 +821,7 @@ in_selectsrc(sin, ro, soopts, mopts, errorp)
 		ro->ro_dst.sa_family = AF_INET;
 		ro->ro_dst.sa_len = sizeof(struct sockaddr_in);
 		satosin(&ro->ro_dst)->sin_addr = sin->sin_addr;
-		rtalloc(ro);
+		rtalloc_mpath(ro, NULL, 0);
 
 		/*
 		 * It is important to bzero out the rest of the
diff --git a/sys/netinet/ip_input.c b/sys/netinet/ip_input.c
index d069a75b358..8302a40f3c9 100644
--- a/sys/netinet/ip_input.c
+++ b/sys/netinet/ip_input.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip_input.c,v 1.141 2006/06/16 16:49:40 henning Exp $	*/
+/*	$OpenBSD: ip_input.c,v 1.142 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$NetBSD: ip_input.c,v 1.30 1996/03/16 23:53:58 christos Exp $	*/
 
 /*
@@ -88,6 +88,7 @@ char ipsec_def_comp[20];
 /* values controllable via sysctl */
 int	ipforwarding = 0;
 int	ipmforwarding = 0;
+int	ipmultipath = 0;
 int	ipsendredirects = 1;
 int	ip_dosourceroute = 0;
 int	ip_defttl = IPDEFTTL;
@@ -1437,7 +1438,7 @@ ip_forward(m, srcrt)
 		sin->sin_len = sizeof(*sin);
 		sin->sin_addr = ip->ip_dst;
 
-		rtalloc(&ipforward_rt);
+		rtalloc_mpath(&ipforward_rt, &ip->ip_src.s_addr, 0);
 		if (ipforward_rt.ro_rt == 0) {
 			icmp_error(m, ICMP_UNREACH, ICMP_UNREACH_HOST, dest, 0);
 			return;
@@ -1497,14 +1498,11 @@ ip_forward(m, srcrt)
 		ipstat.ips_forward++;
 		if (type)
 			ipstat.ips_redirectsent++;
-		else {
-			if (mcopy)
-				m_freem(mcopy);
-			return;
-		}
+		else 
+			goto freecopy;
 	}
 	if (mcopy == NULL)
-		return;
+		goto freert;
 
 	switch (error) {
 
@@ -1546,9 +1544,7 @@ ip_forward(m, srcrt)
 		 * source quench could be a big problem under DoS attacks,
 		 * or the underlying interface is rate-limited.
 		 */
-		if (mcopy)
-			m_freem(mcopy);
-		return;
+		goto freecopy;
 #else
 		type = ICMP_SOURCEQUENCH;
 		code = 0;
@@ -1557,6 +1553,20 @@ ip_forward(m, srcrt)
 	}
 
 	icmp_error(mcopy, type, code, dest, destmtu);
+	goto freert;
+
+ freecopy:
+	if (mcopy)
+		m_free(mcopy);
+ freert:
+#ifndef SMALL_KERNEL
+	if (ipmultipath && ipforward_rt.ro_rt &&
+	    (ipforward_rt.ro_rt->rt_flags & RTF_MPATH)) {
+		RTFREE(ipforward_rt.ro_rt);
+		ipforward_rt.ro_rt = 0;
+	}
+#endif
+	return;
 }
 
 int
diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c
index e241fea438f..65e8698445f 100644
--- a/sys/netinet/ip_output.c
+++ b/sys/netinet/ip_output.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip_output.c,v 1.179 2006/06/06 15:19:15 deraadt Exp $	*/
+/*	$OpenBSD: ip_output.c,v 1.180 2006/06/18 11:47:45 pascoe Exp $	*/
 /*	$NetBSD: ip_output.c,v 1.28 1996/02/13 23:43:07 christos Exp $	*/
 
 /*
@@ -219,7 +219,7 @@ ip_output(struct mbuf *m0, ...)
 			IFP_TO_IA(ifp, ia);
 		} else {
 			if (ro->ro_rt == 0)
-				rtalloc(ro);
+				rtalloc_mpath(ro, NULL, 0);
 
 			if (ro->ro_rt == 0) {
 				ipstat.ips_noroute++;
@@ -386,7 +386,7 @@ ip_output(struct mbuf *m0, ...)
 			IFP_TO_IA(ifp, ia);
 		} else {
 			if (ro->ro_rt == 0)
-				rtalloc(ro);
+				rtalloc_mpath(ro, &ip->ip_src.s_addr, 0);
 
 			if (ro->ro_rt == 0) {
 				ipstat.ips_noroute++;
diff --git a/sys/netinet6/frag6.c b/sys/netinet6/frag6.c
index 7f06cede88a..f971606a222 100644
--- a/sys/netinet6/frag6.c
+++ b/sys/netinet6/frag6.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: frag6.c,v 1.22 2005/11/20 19:25:16 brad Exp $	*/
+/*	$OpenBSD: frag6.c,v 1.23 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: frag6.c,v 1.40 2002/05/27 21:40:31 itojun Exp $	*/
 
 /*
@@ -212,7 +212,7 @@ frag6_input(mp, offp, proto)
 		dst->sin6_addr = ip6->ip6_dst;
 	}
 
-	rtalloc((struct route *)&ro);
+	rtalloc_mpath((struct route *)&ro, &ip6->ip6_src.s6_addr32[0], 0);
 
 	if (ro.ro_rt != NULL && ro.ro_rt->rt_ifa != NULL)
 		dstifp = ((struct in6_ifaddr *)ro.ro_rt->rt_ifa)->ia_ifp;
diff --git a/sys/netinet6/in6.h b/sys/netinet6/in6.h
index 4dc98f6f180..50c41795d97 100644
--- a/sys/netinet6/in6.h
+++ b/sys/netinet6/in6.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in6.h,v 1.38 2006/05/27 23:40:27 claudio Exp $	*/
+/*	$OpenBSD: in6.h,v 1.39 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: in6.h,v 1.83 2001/03/29 02:55:07 jinmei Exp $	*/
 
 /*
@@ -551,7 +551,8 @@ struct in6_pktinfo {
 /* New entries should be added here from current IPV6CTL_MAXID value. */
 /* to define items, should talk with KAME guys first, for *BSD compatibility */
 #define IPV6CTL_MFORWARDING	42
-#define IPV6CTL_MAXID		43
+#define IPV6CTL_MULTIPATH	43
+#define IPV6CTL_MAXID		44
 
 #define IPV6CTL_NAMES { \
 	{ 0, 0 }, \
@@ -597,6 +598,7 @@ struct in6_pktinfo {
 	{ 0, 0 }, \
 	{ "maxfrags", CTLTYPE_INT }, \
 	{ "mforwarding", CTLTYPE_INT }, \
+	{ "multipath", CTLTYPE_INT }, \
 }
 
 #define IPV6CTL_VARS { \
@@ -643,6 +645,7 @@ struct in6_pktinfo {
 	NULL, \
 	&ip6_maxfrags, \
 	&ip6_mforwarding, \
+	&ip6_multipath, \
 }
 
 #endif /* __BSD_VISIBLE */
diff --git a/sys/netinet6/in6_proto.c b/sys/netinet6/in6_proto.c
index 408c025e2de..1a881003002 100644
--- a/sys/netinet6/in6_proto.c
+++ b/sys/netinet6/in6_proto.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in6_proto.c,v 1.49 2006/06/16 15:18:42 pascoe Exp $	*/
+/*	$OpenBSD: in6_proto.c,v 1.50 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: in6_proto.c,v 1.66 2000/10/10 15:35:47 itojun Exp $	*/
 
 /*
@@ -255,6 +255,7 @@ struct domain inet6domain =
  */
 int	ip6_forwarding = 0;	/* no forwarding unless sysctl'd to enable */
 int	ip6_mforwarding = 0;	/* no multicast forwarding unless ... */
+int	ip6_multipath = 0;	/* no using multipath routes unless ... */
 int	ip6_sendredirects = 1;
 int	ip6_defhlim = IPV6_DEFHLIM;
 int	ip6_defmcasthlim = IPV6_DEFAULT_MULTICAST_HOPS;
diff --git a/sys/netinet6/in6_src.c b/sys/netinet6/in6_src.c
index 967bd374ce9..cb35e0e1894 100644
--- a/sys/netinet6/in6_src.c
+++ b/sys/netinet6/in6_src.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in6_src.c,v 1.18 2006/06/16 16:49:40 henning Exp $	*/
+/*	$OpenBSD: in6_src.c,v 1.19 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: in6_src.c,v 1.36 2001/02/06 04:08:17 itojun Exp $	*/
 
 /*
@@ -245,7 +245,7 @@ in6_selectsrc(dstsock, opts, mopts, ro, laddr, errorp)
 				ro->ro_rt = rtalloc1(&((struct route *)ro)
 						     ->ro_dst, 0, 0);
 			} else {
-				rtalloc((struct route *)ro);
+				rtalloc_mpath((struct route *)ro, NULL, 0);
 			}
 		}
 
diff --git a/sys/netinet6/ip6_forward.c b/sys/netinet6/ip6_forward.c
index fb032ed174f..d5a11518ade 100644
--- a/sys/netinet6/ip6_forward.c
+++ b/sys/netinet6/ip6_forward.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip6_forward.c,v 1.34 2004/07/14 20:19:58 dhartmei Exp $	*/
+/*	$OpenBSD: ip6_forward.c,v 1.35 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: ip6_forward.c,v 1.75 2001/06/29 12:42:13 jinmei Exp $	*/
 
 /*
@@ -237,7 +237,8 @@ ip6_forward(m, srcrt)
 				ip6_forward_rt.ro_rt = 0;
 			}
 			/* this probably fails but give it a try again */
-			rtalloc((struct route *)&ip6_forward_rt);
+			rtalloc_mpath((struct route *)&ip6_forward_rt,
+			    &ip6->ip6_src.s6_addr32[0], 0);
 		}
 
 		if (ip6_forward_rt.ro_rt == 0) {
@@ -261,7 +262,8 @@ ip6_forward(m, srcrt)
 		dst->sin6_family = AF_INET6;
 		dst->sin6_addr = ip6->ip6_dst;
 
-		rtalloc((struct route *)&ip6_forward_rt);
+		rtalloc_mpath((struct route *)&ip6_forward_rt,
+		    &ip6->ip6_src.s6_addr32[0], 0);
 
 		if (ip6_forward_rt.ro_rt == 0) {
 			ip6stat.ip6s_noroute++;
@@ -303,7 +305,7 @@ ip6_forward(m, srcrt)
 			icmp6_error(mcopy, ICMP6_DST_UNREACH,
 				    ICMP6_DST_UNREACH_BEYONDSCOPE, 0);
 		m_freem(m);
-		return;
+		goto freert;
 	}
 
 #ifdef IPSEC
@@ -330,7 +332,7 @@ ip6_forward(m, srcrt)
 		error = ipsp_process_packet(m, tdb, AF_INET6, 0);
 		splx(s);
 		m_freem(mcopy);
-		return;  /* Nothing more to be done */
+		goto freert;
 	}
 #endif /* IPSEC */
 
@@ -344,7 +346,7 @@ ip6_forward(m, srcrt)
 			icmp6_error(mcopy, ICMP6_PACKET_TOO_BIG, 0, mtu);
 		}
 		m_freem(m);
-		return;
+		goto freert;
 	}
 
 	if (rt->rt_flags & RTF_GATEWAY)
@@ -381,7 +383,7 @@ ip6_forward(m, srcrt)
 			icmp6_error(mcopy, ICMP6_DST_UNREACH,
 				    ICMP6_DST_UNREACH_ADDR, 0);
 			m_freem(m);
-			return;
+			goto freert;
 		}
 		type = ND_REDIRECT;
 	}
@@ -458,12 +460,12 @@ ip6_forward(m, srcrt)
 senderr:
 #endif
 	if (mcopy == NULL)
-		return;
+		goto freert;
 	switch (error) {
 	case 0:
 		if (type == ND_REDIRECT) {
 			icmp6_redirect_output(mcopy, rt);
-			return;
+			goto freert;
 		}
 		goto freecopy;
 
@@ -485,9 +487,17 @@ senderr:
 		break;
 	}
 	icmp6_error(mcopy, type, code, 0);
-	return;
+	goto freert;
 
  freecopy:
 	m_freem(mcopy);
+ freert:
+#ifndef SMALL_KERNEL
+	if (ip6_multipath && ip6_forward_rt.ro_rt &&
+	    (ip6_forward_rt.ro_rt->rt_flags & RTF_MPATH)) {
+		RTFREE(ip6_forward_rt.ro_rt);
+		ip6_forward_rt.ro_rt = 0;
+	}
+#endif
 	return;
 }
diff --git a/sys/netinet6/ip6_input.c b/sys/netinet6/ip6_input.c
index 57a9a1f22f2..8a18ef8b167 100644
--- a/sys/netinet6/ip6_input.c
+++ b/sys/netinet6/ip6_input.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip6_input.c,v 1.67 2006/05/27 23:40:27 claudio Exp $	*/
+/*	$OpenBSD: ip6_input.c,v 1.68 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: ip6_input.c,v 1.188 2001/03/29 05:34:31 itojun Exp $	*/
 
 /*
@@ -413,7 +413,8 @@ ip6_input(m)
 		ip6_forward_rt.ro_dst.sin6_family = AF_INET6;
 		ip6_forward_rt.ro_dst.sin6_addr = ip6->ip6_dst;
 
-		rtalloc((struct route *)&ip6_forward_rt);
+		rtalloc_mpath((struct route *)&ip6_forward_rt,
+		    &ip6->ip6_src.s6_addr32[0], 0);
 	}
 
 #define rt6_key(r) ((struct sockaddr_in6 *)((r)->rt_nodes->rn_key))
diff --git a/sys/netinet6/ip6_output.c b/sys/netinet6/ip6_output.c
index 1515a2d9006..b9f247515d8 100644
--- a/sys/netinet6/ip6_output.c
+++ b/sys/netinet6/ip6_output.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip6_output.c,v 1.92 2006/06/16 16:49:40 henning Exp $	*/
+/*	$OpenBSD: ip6_output.c,v 1.93 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: ip6_output.c,v 1.172 2001/03/25 09:55:56 itojun Exp $	*/
 
 /*
@@ -530,7 +530,7 @@ ip6_output(m0, opt, ro, flags, im6o, ifpp)
 			 * non-bsdi always clone routes, if parent is
 			 * PRF_CLONING.
 			 */
-			rtalloc((struct route *)ro);
+			rtalloc_mpath((struct route *)ro, NULL, 0);
 		}
 		if (ro->ro_rt == 0) {
 			ip6stat.ip6s_noroute++;
diff --git a/sys/netinet6/ip6_var.h b/sys/netinet6/ip6_var.h
index 5c1faf6adec..58a523aa540 100644
--- a/sys/netinet6/ip6_var.h
+++ b/sys/netinet6/ip6_var.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip6_var.h,v 1.26 2006/05/27 23:40:27 claudio Exp $	*/
+/*	$OpenBSD: ip6_var.h,v 1.27 2006/06/18 11:47:46 pascoe Exp $	*/
 /*	$KAME: ip6_var.h,v 1.33 2000/06/11 14:59:20 jinmei Exp $	*/
 
 /*
@@ -207,6 +207,7 @@ extern int	ip6_defhlim;		/* default hop limit */
 extern int	ip6_defmcasthlim;	/* default multicast hop limit */
 extern int	ip6_forwarding;		/* act as router? */
 extern int	ip6_mforwarding;	/* act as multicast router? */
+extern int	ip6_multipath;		/* use multipath routes */
 extern int	ip6_sendredirect;	/* send ICMPv6 redirect? */
 extern int	ip6_forward_srcrt;	/* forward src-routed? */
 extern int	ip6_use_deprecated;	/* allow deprecated addr as source */