Skip site navigation (1)Skip section navigation (2) 
Date:      Sat, 5 Sep 2015 10:15:20 +0000 (UTC)
From:      Gleb Smirnoff <glebius@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r287481 - head/sys/netinet
Message-ID:  <201509051015.t85AFKue086342@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help 
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;
 };

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201509051015.t85AFKue086342>