svn commit: r287481 - head/sys/netinet
Gleb Smirnoff
glebius at FreeBSD.org
Sat Sep 5 10:15:21 UTC 2015
Author: glebius
Date: Sat Sep 5 10:15:19 2015
New Revision: 287481
URL: https://svnweb.freebsd.org/changeset/base/287481
Log:
Use Jenkins hash for TCP syncache.
o Unlike xor, in Jenkins hash every bit of input affects virtually
every bit of output, thus salting the hash actually works. With
xor salting only provides a false sense of security, since if
hash(x) collides with hash(y), then of course, hash(x) ^ salt
would also collide with hash(y) ^ salt. [1]
o Jenkins provides much better distribution than xor, very close to
ideal.
TCP connection setup/teardown benchmark has shown a 10% increase
with default hash size, and with bigger hashes that still provide
possibility for collisions. With enormous hash size, when dataset is
by an order of magnitude smaller than hash size, the benchmark has
shown 4% decrease in performance decrease, which is expected and
acceptable.
Noticed by: Jeffrey Knockel <jeffk cs.unm.edu> [1]
Benchmarks by: jch
Reviewed by: jch, pkelsey, delphij
Security: strengthens protection against hash collision DoS
Sponsored by: Nginx, Inc.
Modified:
head/sys/netinet/in_pcb.h
head/sys/netinet/tcp_syncache.c
head/sys/netinet/tcp_syncache.h
Modified: head/sys/netinet/in_pcb.h
==============================================================================
--- head/sys/netinet/in_pcb.h Sat Sep 5 08:55:51 2015 (r287480)
+++ head/sys/netinet/in_pcb.h Sat Sep 5 10:15:19 2015 (r287481)
@@ -79,6 +79,8 @@ struct in_addr_4in6 {
/*
* NOTE: ipv6 addrs should be 64-bit aligned, per RFC 2553. in_conninfo has
* some extra padding to accomplish this.
+ * NOTE 2: tcp_syncache.c uses first 5 32-bit words, which identify fport,
+ * lport, faddr to generate hash, so these fields shouldn't be moved.
*/
struct in_endpoints {
u_int16_t ie_fport; /* foreign port */
Modified: head/sys/netinet/tcp_syncache.c
==============================================================================
--- head/sys/netinet/tcp_syncache.c Sat Sep 5 08:55:51 2015 (r287480)
+++ head/sys/netinet/tcp_syncache.c Sat Sep 5 10:15:19 2015 (r287481)
@@ -40,6 +40,7 @@ __FBSDID("$FreeBSD$");
#include <sys/param.h>
#include <sys/systm.h>
+#include <sys/hash.h>
#include <sys/kernel.h>
#include <sys/sysctl.h>
#include <sys/limits.h>
@@ -186,27 +187,6 @@ SYSCTL_INT(_net_inet_tcp_syncache, OID_A
static MALLOC_DEFINE(M_SYNCACHE, "syncache", "TCP syncache");
-#define SYNCACHE_HASH(inc, mask) \
- ((V_tcp_syncache.hash_secret ^ \
- (inc)->inc_faddr.s_addr ^ \
- ((inc)->inc_faddr.s_addr >> 16) ^ \
- (inc)->inc_fport ^ (inc)->inc_lport) & mask)
-
-#define SYNCACHE_HASH6(inc, mask) \
- ((V_tcp_syncache.hash_secret ^ \
- (inc)->inc6_faddr.s6_addr32[0] ^ \
- (inc)->inc6_faddr.s6_addr32[3] ^ \
- (inc)->inc_fport ^ (inc)->inc_lport) & mask)
-
-#define ENDPTS_EQ(a, b) ( \
- (a)->ie_fport == (b)->ie_fport && \
- (a)->ie_lport == (b)->ie_lport && \
- (a)->ie_faddr.s_addr == (b)->ie_faddr.s_addr && \
- (a)->ie_laddr.s_addr == (b)->ie_laddr.s_addr \
-)
-
-#define ENDPTS6_EQ(a, b) (memcmp(a, b, sizeof(*a)) == 0)
-
#define SCH_LOCK(sch) mtx_lock(&(sch)->sch_mtx)
#define SCH_UNLOCK(sch) mtx_unlock(&(sch)->sch_mtx)
#define SCH_LOCK_ASSERT(sch) mtx_assert(&(sch)->sch_mtx, MA_OWNED)
@@ -486,41 +466,29 @@ syncache_lookup(struct in_conninfo *inc,
{
struct syncache *sc;
struct syncache_head *sch;
+ uint32_t hash;
-#ifdef INET6
- if (inc->inc_flags & INC_ISIPV6) {
- sch = &V_tcp_syncache.hashbase[
- SYNCACHE_HASH6(inc, V_tcp_syncache.hashmask)];
- *schp = sch;
-
- SCH_LOCK(sch);
+ /*
+ * The hash is built on foreign port + local port + foreign address.
+ * We rely on the fact that struct in_conninfo starts with 16 bits
+ * of foreign port, then 16 bits of local port then followed by 128
+ * bits of foreign address. In case of IPv4 address, the first 3
+ * 32-bit words of the address always are zeroes.
+ */
+ hash = jenkins_hash32((uint32_t *)&inc->inc_ie, 5,
+ V_tcp_syncache.hash_secret) & V_tcp_syncache.hashmask;
- /* Circle through bucket row to find matching entry. */
- TAILQ_FOREACH(sc, &sch->sch_bucket, sc_hash) {
- if (ENDPTS6_EQ(&inc->inc_ie, &sc->sc_inc.inc_ie))
- return (sc);
- }
- } else
-#endif
- {
- sch = &V_tcp_syncache.hashbase[
- SYNCACHE_HASH(inc, V_tcp_syncache.hashmask)];
- *schp = sch;
+ sch = &V_tcp_syncache.hashbase[hash];
+ *schp = sch;
+ SCH_LOCK(sch);
- SCH_LOCK(sch);
+ /* Circle through bucket row to find matching entry. */
+ TAILQ_FOREACH(sc, &sch->sch_bucket, sc_hash)
+ if (bcmp(&inc->inc_ie, &sc->sc_inc.inc_ie,
+ sizeof(struct in_endpoints)) == 0)
+ break;
- /* Circle through bucket row to find matching entry. */
- TAILQ_FOREACH(sc, &sch->sch_bucket, sc_hash) {
-#ifdef INET6
- if (sc->sc_inc.inc_flags & INC_ISIPV6)
- continue;
-#endif
- if (ENDPTS_EQ(&inc->inc_ie, &sc->sc_inc.inc_ie))
- return (sc);
- }
- }
- SCH_LOCK_ASSERT(*schp);
- return (NULL); /* always returns with locked sch */
+ return (sc); /* Always returns with locked sch. */
}
/*
Modified: head/sys/netinet/tcp_syncache.h
==============================================================================
--- head/sys/netinet/tcp_syncache.h Sat Sep 5 08:55:51 2015 (r287480)
+++ head/sys/netinet/tcp_syncache.h Sat Sep 5 10:15:19 2015 (r287481)
@@ -118,7 +118,7 @@ struct tcp_syncache {
u_int bucket_limit;
u_int cache_limit;
u_int rexmt_limit;
- u_int hash_secret;
+ uint32_t hash_secret;
struct vnet *vnet;
struct syncookie_secret secret;
};
More information about the svn-src-head
mailing list