From 6ae87790328612368a591aafd4b04c0db7aefec6 Mon Sep 17 00:00:00 2001 From: ae Date: Sat, 15 Dec 2012 20:04:24 +0000 Subject: 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 --- sys/netinet6/in6.c | 21 +++++++++++---------- sys/netinet6/in6_var.h | 24 ++++++++++++++++++++++++ sys/netinet6/ip6_input.c | 5 +++++ 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 #ifdef _KERNEL +#include #include #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); } -- cgit v1.1