Add a hash table that contains the list of internet addresses, and use

this in place of the in_ifaddr list when appropriate.  This improves
performance on hosts which have a large number of IP aliases.

6 files changed, 113 insertions, 63 deletions

diff --git a/sys/netinet/if_ether.c b/sys/netinet/if_ether.c
index cbd4e1f..ce1fb20 100644
--- a/sys/netinet/if_ether.c
+++ b/sys/netinet/if_ether.c
@@ -526,7 +526,8 @@ in_arpinput(m)
 	struct iso88025_header *th = (struct iso88025_header *)0;
 	register struct llinfo_arp *la = 0;
 	register struct rtentry *rt;
-	struct in_ifaddr *ia, *maybe_ia = 0;
+	struct ifaddr *ifa;
+	struct in_ifaddr *ia;
 	struct sockaddr_dl *sdl;
 	struct sockaddr sa;
 	struct in_addr isaddr, itaddr, myaddr;
@@ -542,30 +543,36 @@ in_arpinput(m)
 	op = ntohs(ea->arp_op);
 	(void)memcpy(&isaddr, ea->arp_spa, sizeof (isaddr));
 	(void)memcpy(&itaddr, ea->arp_tpa, sizeof (itaddr));
-	TAILQ_FOREACH(ia, &in_ifaddrhead, ia_link) {
-		/*
-		 * For a bridge, we want to check the address irrespective
-		 * of the receive interface. (This will change slightly
-		 * when we have clusters of interfaces).
-		 */
 #ifdef BRIDGE
 #define BRIDGE_TEST (do_bridge)
 #else
 #define BRIDGE_TEST (0) /* cc will optimise the test away */
 #endif
-		if ((BRIDGE_TEST) || (ia->ia_ifp == &ac->ac_if)) {
-			maybe_ia = ia;
-			if ((itaddr.s_addr == ia->ia_addr.sin_addr.s_addr) ||
-			     (isaddr.s_addr == ia->ia_addr.sin_addr.s_addr)) {
-				break;
-			}
-		}
-	}
-	if (maybe_ia == 0) {
+	/*
+	 * For a bridge, we want to check the address irrespective
+	 * of the receive interface. (This will change slightly
+	 * when we have clusters of interfaces).
+	 */
+	LIST_FOREACH(ia, INADDR_HASH(itaddr.s_addr), ia_hash)
+		if ((BRIDGE_TEST || (ia->ia_ifp == &ac->ac_if)) &&
+		    itaddr.s_addr == ia->ia_addr.sin_addr.s_addr)
+			goto match;
+	LIST_FOREACH(ia, INADDR_HASH(isaddr.s_addr), ia_hash)
+		if ((BRIDGE_TEST || (ia->ia_ifp == &ac->ac_if)) &&
+		    isaddr.s_addr == ia->ia_addr.sin_addr.s_addr)
+			goto match;
+	/*
+	 * No match, use the first address on the receive interface
+	 * as a dummy address for the rest of the function.
+	 */
+	ifa = TAILQ_FIRST(&ac->ac_if.if_addrhead);
+	if (ifa == NULL) {
 		m_freem(m);
 		return;
 	}
-	myaddr = ia ? ia->ia_addr.sin_addr : maybe_ia->ia_addr.sin_addr;
+	ia = ifatoia(ifa);
+match:
+	myaddr = ia->ia_addr.sin_addr;
 	if (!bcmp((caddr_t)ea->arp_sha, (caddr_t)ac->ac_enaddr,
 	    sizeof (ea->arp_sha))) {
 		m_freem(m);	/* it's from me, ignore it. */
diff --git a/sys/netinet/in.c b/sys/netinet/in.c
index d56d28e..a6643df 100644
--- a/sys/netinet/in.c
+++ b/sys/netinet/in.c
@@ -193,6 +193,7 @@ in_control(so, cmd, data, ifp, td)
 	register struct ifreq *ifr = (struct ifreq *)data;
 	register struct in_ifaddr *ia = 0, *iap;
 	register struct ifaddr *ifa;
+	struct in_addr dst;
 	struct in_ifaddr *oia;
 	struct in_aliasreq *ifra = (struct in_aliasreq *)data;
 	struct sockaddr_in oldaddr;
@@ -215,21 +216,25 @@ in_control(so, cmd, data, ifp, td)
 	 * Find address for this interface, if it exists.
 	 *
 	 * If an alias address was specified, find that one instead of
-	 * the first one on the interface.
+	 * the first one on the interface, if possible.
 	 */
-	if (ifp)
-		TAILQ_FOREACH(iap, &in_ifaddrhead, ia_link)
-			if (iap->ia_ifp == ifp) {
-				if (((struct sockaddr_in *)&ifr->ifr_addr)->sin_addr.s_addr ==
-				    iap->ia_addr.sin_addr.s_addr) {
+	if (ifp) {
+		dst = ((struct sockaddr_in *)&ifr->ifr_addr)->sin_addr;
+		LIST_FOREACH(iap, INADDR_HASH(dst.s_addr), ia_hash)
+			if (iap->ia_ifp == ifp &&
+			    iap->ia_addr.sin_addr.s_addr == dst.s_addr) {
+				ia = iap;
+				break;
+			}
+		if (ia == NULL)
+			TAILQ_FOREACH(ifa, &ifp->if_addrhead, ifa_link) {
+				iap = ifatoia(ifa);
+				if (iap->ia_addr.sin_family == AF_INET) {
 					ia = iap;
 					break;
-				} else if (ia == NULL) {
-					ia = iap;
-					if (ifr->ifr_addr.sa_family != AF_INET)
-						break;
 				}
 			}
+	}
 
 	switch (cmd) {
 
@@ -423,9 +428,9 @@ in_control(so, cmd, data, ifp, td)
 
 		ifa = &ia->ia_ifa;
 		TAILQ_REMOVE(&ifp->if_addrhead, ifa, ifa_link);
-		oia = ia;
-		TAILQ_REMOVE(&in_ifaddrhead, oia, ia_link);
-		IFAFREE(&oia->ia_ifa);
+		TAILQ_REMOVE(&in_ifaddrhead, ia, ia_link);
+		LIST_REMOVE(ia, ia_hash);
+		IFAFREE(&ia->ia_ifa);
 		splx(s);
 		break;
 
@@ -650,6 +655,7 @@ in_ifinit(ifp, ia, sin, scrub)
 
 	oldaddr = ia->ia_addr;
 	ia->ia_addr = *sin;
+	LIST_INSERT_HEAD(INADDR_HASH(ia->ia_addr.sin_addr.s_addr), ia, ia_hash);
 	/*
 	 * Give the interface a chance to initialize
 	 * if this is its first address,
diff --git a/sys/netinet/in_var.h b/sys/netinet/in_var.h
index 7cef6ea..968eb2d 100644
--- a/sys/netinet/in_var.h
+++ b/sys/netinet/in_var.h
@@ -38,6 +38,7 @@
 #define _NETINET_IN_VAR_H_
 
 #include <sys/queue.h>
+#include <sys/fnv_hash.h>
 
 /*
  * Interface address, Internet version.  One of these structures
@@ -55,7 +56,8 @@ struct in_ifaddr {
 	u_long	ia_subnet;		/* subnet number, including net */
 	u_long	ia_subnetmask;		/* mask of subnet part */
 	struct	in_addr ia_netbroadcast; /* to recognize net broadcasts */
-	TAILQ_ENTRY(in_ifaddr) ia_link;	/* tailq macro glue */
+	LIST_ENTRY(in_ifaddr) ia_hash;	/* entry in bucket of inet addresses */
+	TAILQ_ENTRY(in_ifaddr) ia_link;	/* list of internet addresses */
 	struct	sockaddr_in ia_addr;	/* reserve space for interface name */
 	struct	sockaddr_in ia_dstaddr; /* reserve space for broadcast addr */
 #define	ia_broadaddr	ia_dstaddr
@@ -81,11 +83,25 @@ struct	in_aliasreq {
 
 
 #ifdef	_KERNEL
-extern	TAILQ_HEAD(in_ifaddrhead, in_ifaddr) in_ifaddrhead;
 extern	struct	ifqueue	ipintrq;		/* ip packet input queue */
 extern	struct	in_addr zeroin_addr;
 extern	u_char	inetctlerrmap[];
 
+/* 
+ * Hash table for IP addresses.
+ */
+extern	LIST_HEAD(in_ifaddrhashhead, in_ifaddr) *in_ifaddrhashtbl;
+extern	TAILQ_HEAD(in_ifaddrhead, in_ifaddr) in_ifaddrhead;
+extern	u_long in_ifaddrhmask;			/* mask for hash table */
+
+#define INADDR_NHASH_LOG2       9
+#define INADDR_NHASH		(1 << INADDR_NHASH_LOG2)
+#define INADDR_HMASK		(INREASS_NHASH - 1)
+#define INADDR_HASHVAL(x)	fnv_32_buf((&(x)), sizeof(x), FNV1_32_INIT)
+#define INADDR_HASH(x) \
+	(&in_ifaddrhashtbl[INADDR_HASHVAL(x) & in_ifaddrhmask])
+
+
 /*
  * Macro for finding the interface (ifnet structure) corresponding to one
  * of our IP addresses.
diff --git a/sys/netinet/ip_icmp.c b/sys/netinet/ip_icmp.c
index 5664516..f2071af 100644
--- a/sys/netinet/ip_icmp.c
+++ b/sys/netinet/ip_icmp.c
@@ -461,7 +461,6 @@ icmp_input(m, off)
 			goto reflect;
 
 	case ICMP_MASKREQ:
-#define	satosin(sa)	((struct sockaddr_in *)(sa))
 		if (icmpmaskrepl == 0)
 			break;
 		/*
@@ -584,8 +583,9 @@ static void
 icmp_reflect(m)
 	struct mbuf *m;
 {
-	register struct ip *ip = mtod(m, struct ip *);
-	register struct in_ifaddr *ia;
+	struct ip *ip = mtod(m, struct ip *);
+	struct ifaddr *ifa;
+	struct in_ifaddr *ia;
 	struct in_addr t;
 	struct mbuf *opts = 0;
 	int optlen = (IP_VHL_HL(ip->ip_vhl) << 2) - sizeof(struct ip);
@@ -604,23 +604,30 @@ icmp_reflect(m)
 	 * or anonymous), use the address which corresponds
 	 * to the incoming interface.
 	 */
-	TAILQ_FOREACH(ia, &in_ifaddrhead, ia_link) {
+	LIST_FOREACH(ia, INADDR_HASH(t.s_addr), ia_hash)
 		if (t.s_addr == IA_SIN(ia)->sin_addr.s_addr)
-			break;
-		if (ia->ia_ifp && (ia->ia_ifp->if_flags & IFF_BROADCAST) &&
-		    t.s_addr == satosin(&ia->ia_broadaddr)->sin_addr.s_addr)
-			break;
-	}
+			goto match;
+	if (m->m_pkthdr.rcvif->if_flags & IFF_BROADCAST) {
+		TAILQ_FOREACH(ifa, &m->m_pkthdr.rcvif->if_addrhead, ifa_link) {
+			if (ifa->ifa_addr->sa_family != AF_INET)
+				continue;
+                        ia = ifatoia(ifa);
+                        if (satosin(&ia->ia_broadaddr)->sin_addr.s_addr ==
+                            t.s_addr)
+                                goto match;
+        	}
+        }
+	KASSERT(m->m_pkthdr.rcvif != NULL, ("icmp_reflect: NULL rcvif"));
 	icmpdst.sin_addr = t;
-	if ((ia == (struct in_ifaddr *)0) && m->m_pkthdr.rcvif)
-		ia = (struct in_ifaddr *)ifaof_ifpforaddr(
-			(struct sockaddr *)&icmpdst, m->m_pkthdr.rcvif);
+	ia = (struct in_ifaddr *)ifaof_ifpforaddr(
+	    (struct sockaddr *)&icmpdst, m->m_pkthdr.rcvif);
 	/*
 	 * The following happens if the packet was not addressed to us,
 	 * and was received on an interface with no IP address.
 	 */
-	if (ia == (struct in_ifaddr *)0)
+	if (ia == NULL)
 		ia = TAILQ_FIRST(&in_ifaddrhead);
+match:
 	t = IA_SIN(ia)->sin_addr;
 	ip->ip_src = t;
 	ip->ip_ttl = ip_defttl;
diff --git a/sys/netinet/ip_input.c b/sys/netinet/ip_input.c
index 0f391f1..fa345f6 100644
--- a/sys/netinet/ip_input.c
+++ b/sys/netinet/ip_input.c
@@ -146,11 +146,15 @@ SYSCTL_INT(_net_inet_ip, OID_AUTO, check_interface, CTLFLAG_RW,
 static int	ipprintfs = 0;
 #endif
 
+static int	ipqmaxlen = IFQ_MAXLEN;
+
 extern	struct domain inetdomain;
 extern	struct protosw inetsw[];
 u_char	ip_protox[IPPROTO_MAX];
-static int	ipqmaxlen = IFQ_MAXLEN;
-struct	in_ifaddrhead in_ifaddrhead; /* first inet address */
+struct	in_ifaddrhead in_ifaddrhead; 		/* first inet address */
+struct	in_ifaddrhashhead *in_ifaddrhashtbl;	/* inet addr hash table  */
+u_long 	in_ifaddrhmask;				/* mask for hash table */
+
 SYSCTL_INT(_net_inet_ip, IPCTL_INTRQMAXLEN, intr_queue_maxlen, CTLFLAG_RW,
     &ipintrq.ifq_maxlen, 0, "Maximum size of the IP input queue");
 SYSCTL_INT(_net_inet_ip, IPCTL_INTRQDROPS, intr_queue_drops, CTLFLAG_RD,
@@ -234,6 +238,7 @@ ip_init()
 	register int i;
 
 	TAILQ_INIT(&in_ifaddrhead);
+	in_ifaddrhashtbl = hashinit(INADDR_NHASH, M_IFADDR, &in_ifaddrhmask);
 	pr = pffindproto(PF_INET, IPPROTO_RAW, SOCK_RAW);
 	if (pr == 0)
 		panic("ip_init");
@@ -273,6 +278,7 @@ ip_input(struct mbuf *m)
 	struct ip *ip;
 	struct ipq *fp;
 	struct in_ifaddr *ia = NULL;
+	struct ifaddr *ifa;
 	int    i, hlen, checkif;
 	u_short sum;
 	u_int16_t divert_cookie;		/* firewall cookie */
@@ -557,12 +563,10 @@ pass:
 	    ((m->m_pkthdr.rcvif->if_flags & IFF_LOOPBACK) == 0) &&
 	    (ip_fw_fwd_addr == NULL);
 
-	TAILQ_FOREACH(ia, &in_ifaddrhead, ia_link) {
-
-#ifdef BOOTP_COMPAT
-		if (IA_SIN(ia)->sin_addr.s_addr == INADDR_ANY)
-			goto ours;
-#endif
+	/*
+	 * Check for exact addresses in the hash bucket.
+	 */
+	LIST_FOREACH(ia, INADDR_HASH(pkt_dst.s_addr), ia_hash) {
 		/*
 		 * If the address matches, verify that the packet
 		 * arrived via the correct interface if checking is
@@ -571,20 +575,29 @@ pass:
 		if (IA_SIN(ia)->sin_addr.s_addr == pkt_dst.s_addr && 
 		    (!checkif || ia->ia_ifp == m->m_pkthdr.rcvif))
 			goto ours;
-		/*
-		 * Only accept broadcast packets that arrive via the
-		 * matching interface.  Reception of forwarded directed
-		 * broadcasts would be handled via ip_forward() and
-		 * ether_output() with the loopback into the stack for
-		 * SIMPLEX interfaces handled by ether_output().
-		 */
-		if (ia->ia_ifp == m->m_pkthdr.rcvif &&
-		    ia->ia_ifp && ia->ia_ifp->if_flags & IFF_BROADCAST) {
+	}
+	/*
+	 * Check for broadcast addresses.
+	 *
+	 * Only accept broadcast packets that arrive via the matching
+	 * interface.  Reception of forwarded directed broadcasts would
+	 * be handled via ip_forward() and ether_output() with the loopback
+	 * into the stack for SIMPLEX interfaces handled by ether_output().
+	 */
+	if (m->m_pkthdr.rcvif->if_flags & IFF_BROADCAST) {
+	        TAILQ_FOREACH(ifa, &m->m_pkthdr.rcvif->if_addrhead, ifa_link) {
+			if (ifa->ifa_addr->sa_family != AF_INET)
+				continue;
+			ia = ifatoia(ifa);
 			if (satosin(&ia->ia_broadaddr)->sin_addr.s_addr ==
 			    pkt_dst.s_addr)
 				goto ours;
 			if (ia->ia_netbroadcast.s_addr == pkt_dst.s_addr)
 				goto ours;
+#ifdef BOOTP_COMPAT
+			if (IA_SIN(ia)->sin_addr.s_addr == INADDR_ANY)
+				goto ours;
+#endif
 		}
 	}
 	if (IN_MULTICAST(ntohl(ip->ip_dst.s_addr))) {
diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c
index 49e2c74..71c7ad2 100644
--- a/sys/netinet/ip_output.c
+++ b/sys/netinet/ip_output.c
@@ -713,7 +713,8 @@ skip_ipsec:
 			 * as the packet runs through ip_input() as
 			 * it is done through a ISR.
 			 */
-			TAILQ_FOREACH(ia, &in_ifaddrhead, ia_link) {
+			LIST_FOREACH(ia,
+			    INADDR_HASH(dst->sin_addr.s_addr), ia_hash) {
 				/*
 				 * If the addr to forward to is one
 				 * of ours, we pretend to