From owner-svn-src-all@freebsd.org Sat Sep 5 10:15:21 2015 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 2AEBF9CACF8; Sat, 5 Sep 2015 10:15:21 +0000 (UTC) (envelope-from glebius@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 104651B99; Sat, 5 Sep 2015 10:15:21 +0000 (UTC) (envelope-from glebius@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.70]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id t85AFKWr086346; Sat, 5 Sep 2015 10:15:20 GMT (envelope-from glebius@FreeBSD.org) Received: (from glebius@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id t85AFKue086342; Sat, 5 Sep 2015 10:15:20 GMT (envelope-from glebius@FreeBSD.org) Message-Id: <201509051015.t85AFKue086342@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: glebius set sender to glebius@FreeBSD.org using -f From: Gleb Smirnoff Date: Sat, 5 Sep 2015 10:15:20 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r287481 - head/sys/netinet 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.20 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, 05 Sep 2015 10:15:21 -0000 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 [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 #include +#include #include #include #include @@ -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; };