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 <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)
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);
}
_______________________________________________
svn-src-head@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
