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@

8 files changed, 38 insertions, 22 deletions

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 */