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@

4 files changed, 33 insertions, 20 deletions

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++;