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

1 files changed, 11 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();