From owner-svn-src-all@FreeBSD.ORG Sat Dec 15 20:04:25 2012 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 64392669; Sat, 15 Dec 2012 20:04:25 +0000 (UTC) (envelope-from ae@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) by mx1.freebsd.org (Postfix) with ESMTP id 433628FC12; Sat, 15 Dec 2012 20:04:25 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.5/8.14.5) with ESMTP id qBFK4Pwd027938; Sat, 15 Dec 2012 20:04:25 GMT (envelope-from ae@svn.freebsd.org) Received: (from ae@localhost) by svn.freebsd.org (8.14.5/8.14.5/Submit) id qBFK4Oo7027935; Sat, 15 Dec 2012 20:04:24 GMT (envelope-from ae@svn.freebsd.org) Message-Id: <201212152004.qBFK4Oo7027935@svn.freebsd.org> From: "Andrey V. Elsukov" Date: Sat, 15 Dec 2012 20:04:24 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r244272 - head/sys/netinet6 X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 15 Dec 2012 20:04:25 -0000 Author: ae Date: Sat Dec 15 20:04:24 2012 New Revision: 244272 URL: http://svnweb.freebsd.org/changeset/base/244272 Log: 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 Modified: head/sys/netinet6/in6.c head/sys/netinet6/in6_var.h head/sys/netinet6/ip6_input.c Modified: head/sys/netinet6/in6.c ============================================================================== --- head/sys/netinet6/in6.c Sat Dec 15 18:21:09 2012 (r244271) +++ head/sys/netinet6/in6.c Sat Dec 15 20:04:24 2012 (r244272) @@ -1149,6 +1149,8 @@ in6_update_ifa(struct ifnet *ifp, struct 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, st */ 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(); Modified: head/sys/netinet6/in6_var.h ============================================================================== --- head/sys/netinet6/in6_var.h Sat Dec 15 18:21:09 2012 (r244271) +++ head/sys/netinet6/in6_var.h Sat Dec 15 20:04:24 2012 (r244272) @@ -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) Modified: head/sys/netinet6/ip6_input.c ============================================================================== --- head/sys/netinet6/ip6_input.c Sat Dec 15 18:21:09 2012 (r244271) +++ head/sys/netinet6/ip6_input.c Sat Dec 15 20:04:24 2012 (r244272) @@ -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); }