In additional to the tailq of IPv6 addresses add the hash table.

For now use 256 buckets and fnv_hash function. Use xor'ed 32-bit
s6_addr32 parts of in6_addr structure as a hash key. Update
in6_localip and in6_is_addr_deprecated to use hash table for fastest
lookup.

Sponsored by:	Yandex LLC
Discussed with:	dwmalone, glebius, bz

3 files changed, 40 insertions, 10 deletions

diff --git a/sys/netinet6/in6.c b/sys/netinet6/in6.c
index 8da46cf..e260e5d 100644
--- a/sys/netinet6/in6.c
+++ b/sys/netinet6/in6.c
@@ -1149,6 +1149,8 @@ in6_update_ifa(struct ifnet *ifp, struct in6_aliasreq *ifra,
 		ifa_ref(&ia->ia_ifa);			/* in6_ifaddrhead */
 		IN6_IFADDR_WLOCK();
 		TAILQ_INSERT_TAIL(&V_in6_ifaddrhead, ia, ia_link);
+		LIST_INSERT_HEAD(IN6ADDR_HASH(&ifra->ifra_addr.sin6_addr),
+		    ia, ia6_hash);
 		IN6_IFADDR_WUNLOCK();
 	}
 
@@ -1534,6 +1536,7 @@ in6_unlink_ifa(struct in6_ifaddr *ia, struct ifnet *ifp)
 	 */
 	IN6_IFADDR_WLOCK();
 	TAILQ_REMOVE(&V_in6_ifaddrhead, ia, ia_link);
+	LIST_REMOVE(ia, ia6_hash);
 	IN6_IFADDR_WUNLOCK();
 
 	/*
@@ -2083,7 +2086,7 @@ in6_localip(struct in6_addr *in6)
 	struct in6_ifaddr *ia;
 
 	IN6_IFADDR_RLOCK();
-	TAILQ_FOREACH(ia, &V_in6_ifaddrhead, ia_link) {
+	LIST_FOREACH(ia, IN6ADDR_HASH(in6), ia6_hash) {
 		if (IN6_ARE_ADDR_EQUAL(in6, &ia->ia_addr.sin6_addr)) {
 			IN6_IFADDR_RUNLOCK();
 			return (1);
@@ -2093,22 +2096,20 @@ in6_localip(struct in6_addr *in6)
 	return (0);
 }
 
-
 int
 in6_is_addr_deprecated(struct sockaddr_in6 *sa6)
 {
 	struct in6_ifaddr *ia;
 
 	IN6_IFADDR_RLOCK();
-	TAILQ_FOREACH(ia, &V_in6_ifaddrhead, ia_link) {
-		if (IN6_ARE_ADDR_EQUAL(&ia->ia_addr.sin6_addr,
-		    &sa6->sin6_addr) &&
-		    (ia->ia6_flags & IN6_IFF_DEPRECATED) != 0) {
-			IN6_IFADDR_RUNLOCK();
-			return (1); /* true */
+	LIST_FOREACH(ia, IN6ADDR_HASH(&sa6->sin6_addr), ia6_hash) {
+		if (IN6_ARE_ADDR_EQUAL(IA6_IN6(ia), &sa6->sin6_addr)) {
+			if (ia->ia6_flags & IN6_IFF_DEPRECATED) {
+				IN6_IFADDR_RUNLOCK();
+				return (1); /* true */
+			}
+			break;
 		}
-
-		/* XXX: do we still have to go thru the rest of the list? */
 	}
 	IN6_IFADDR_RUNLOCK();
 
diff --git a/sys/netinet6/in6_var.h b/sys/netinet6/in6_var.h
index 71a05f3..e8b6b9e 100644
--- a/sys/netinet6/in6_var.h
+++ b/sys/netinet6/in6_var.h
@@ -67,6 +67,7 @@
 #include <sys/tree.h>
 
 #ifdef _KERNEL
+#include <sys/fnv_hash.h>
 #include <sys/libkern.h>
 #endif
 
@@ -131,10 +132,13 @@ struct	in6_ifaddr {
 
 	/* multicast addresses joined from the kernel */
 	LIST_HEAD(, in6_multi_mship) ia6_memberships;
+	/* entry in bucket of inet6 addresses */
+	LIST_ENTRY(in6_ifaddr) ia6_hash;
 };
 
 /* List of in6_ifaddr's. */
 TAILQ_HEAD(in6_ifaddrhead, in6_ifaddr);
+LIST_HEAD(in6_ifaddrlisthead, in6_ifaddr);
 
 /* control structure to manage address selection policy */
 struct in6_addrpolicy {
@@ -499,7 +503,27 @@ struct	in6_rrenumreq {
 
 #ifdef _KERNEL
 VNET_DECLARE(struct in6_ifaddrhead, in6_ifaddrhead);
+VNET_DECLARE(struct in6_ifaddrlisthead *, in6_ifaddrhashtbl);
+VNET_DECLARE(u_long, in6_ifaddrhmask);
 #define	V_in6_ifaddrhead		VNET(in6_ifaddrhead)
+#define	V_in6_ifaddrhashtbl		VNET(in6_ifaddrhashtbl)
+#define	V_in6_ifaddrhmask		VNET(in6_ifaddrhmask)
+
+#define	IN6ADDR_NHASH_LOG2		8
+#define	IN6ADDR_NHASH			(1 << IN6ADDR_NHASH_LOG2)
+#define	IN6ADDR_HASHVAL(x)		(in6_addrhash(x))
+#define	IN6ADDR_HASH(x) \
+    (&V_in6_ifaddrhashtbl[IN6ADDR_HASHVAL(x) & V_in6_ifaddrhmask])
+
+static __inline uint32_t
+in6_addrhash(struct in6_addr *in6)
+{
+	uint32_t x;
+
+	x = in6->s6_addr32[0] ^ in6->s6_addr32[1] ^ in6->s6_addr32[2] ^
+	    in6->s6_addr32[3];
+	return (fnv_32_buf(&x, sizeof(x), FNV1_32_INIT));
+}
 
 extern struct rwlock in6_ifaddr_lock;
 #define	IN6_IFADDR_LOCK_ASSERT(	)	rw_assert(&in6_ifaddr_lock, RA_LOCKED)
diff --git a/sys/netinet6/ip6_input.c b/sys/netinet6/ip6_input.c
index f75a11f..45c4ff6 100644
--- a/sys/netinet6/ip6_input.c
+++ b/sys/netinet6/ip6_input.c
@@ -126,6 +126,8 @@ extern struct domain inet6domain;
 
 u_char ip6_protox[IPPROTO_MAX];
 VNET_DEFINE(struct in6_ifaddrhead, in6_ifaddrhead);
+VNET_DEFINE(struct in6_ifaddrlisthead *, in6_ifaddrhashtbl);
+VNET_DEFINE(u_long, in6_ifaddrhmask);
 
 static struct netisr_handler ip6_nh = {
 	.nh_name = "ip6",
@@ -170,6 +172,8 @@ ip6_init(void)
 	TUNABLE_INT_FETCH("net.inet6.ip6.no_radr", &V_ip6_no_radr);
 
 	TAILQ_INIT(&V_in6_ifaddrhead);
+	V_in6_ifaddrhashtbl = hashinit(IN6ADDR_NHASH, M_IFADDR,
+	    &V_in6_ifaddrhmask);
 
 	/* Initialize packet filter hooks. */
 	V_inet6_pfil_hook.ph_type = PFIL_TYPE_AF;
@@ -297,6 +301,7 @@ void
 ip6_destroy()
 {
 
+	hashdestroy(V_in6_ifaddrhashtbl, M_IFADDR, V_in6_ifaddrhmask);
 	nd6_destroy();
 	callout_drain(&V_in6_tmpaddrtimer_ch);
 }