From owner-freebsd-net@FreeBSD.ORG Thu Aug 29 19:53:44 2013 Return-Path: Delivered-To: net@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTP id D8EEED3E for ; Thu, 29 Aug 2013 19:53:44 +0000 (UTC) (envelope-from btv1==9536076923e==tgubatayao@barracuda.com) Received: from bsf03.barracuda.com (bsf03.barracuda.com [64.235.145.83]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id AFDCE24B4 for ; Thu, 29 Aug 2013 19:53:44 +0000 (UTC) X-ASG-Debug-ID: 1377804860-05b9635b395d6430001-oFaieN Received: from bn-scl-fe06.Cudanet.local (mail.barracuda.com [10.8.1.48]) by bsf03.barracuda.com with ESMTP id GwE9GMdeuZwZMBSB (version=TLSv1 cipher=AES128-SHA bits=128 verify=NO); Thu, 29 Aug 2013 12:34:20 -0700 (PDT) X-Barracuda-Envelope-From: tgubatayao@barracuda.com Received: from bn-scl-be04.Cudanet.local (10.8.1.56) by bn-scl-fe06.Cudanet.local (10.8.1.48) with Microsoft SMTP Server (TLS) id 8.3.298.1; Thu, 29 Aug 2013 12:34:21 -0700 Received: from BN-SCL-MBX03.Cudanet.local ([fe80::e5b6:9fef:a4d2:a5ba]) by bn-scl-be04.Cudanet.local ([::1]) with mapi; Thu, 29 Aug 2013 12:34:20 -0700 From: "T.C. Gubatayao" To: Alan Somers Date: Thu, 29 Aug 2013 12:33:58 -0700 Subject: Re: Flow ID, LACP, and igb Thread-Topic: Flow ID, LACP, and igb X-ASG-Orig-Subj: Re: Flow ID, LACP, and igb Thread-Index: Ac6k7rUiDkFvYNlHSL69A2ttEnQXYA== Message-ID: <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com> References: <521BBD21.4070304@freebsd.org> <521EE8DA.3060107@freebsd.org> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-apple-encoding-hint: 513 x-universally-unique-identifier: 608f5fdc-5bd1-4080-bc50-c66091b62866 x-apple-mail-remote-attachments: YES x-apple-base-url: x-msg://3642/ x-apple-windows-friendly: 1 x-apple-mail-signature: x-uniform-type-identifier: com.apple.mail-draft acceptlanguage: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Barracuda-Connect: mail.barracuda.com[10.8.1.48] X-Barracuda-Start-Time: 1377804860 X-Barracuda-Encrypted: AES128-SHA X-Barracuda-URL: http://10.8.98.66:8000/cgi-mod/mark.cgi X-Barracuda-BRTS-Status: 1 X-Virus-Scanned: by bsmtpd at barracuda.com X-Barracuda-Spam-Score: 0.62 X-Barracuda-Spam-Status: No, SCORE=0.62 using per-user scores of TAG_LEVEL=1000.0 QUARANTINE_LEVEL=1000.0 KILL_LEVEL=9.0 tests=COMMA_SUBJECT, THREAD_INDEX, THREAD_TOPIC X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.2.139766 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 0.01 THREAD_INDEX thread-index: AcO7Y8iR61tzADqsRmmc5wNiFHEOig== 0.01 THREAD_TOPIC Thread-Topic: ...(Japanese Subject)... 0.60 COMMA_SUBJECT Subject is like 'Re: FDSDS, this is a subject' Cc: Jack F Vogel , "Justin T. Gibbs" , Andre Oppermann , "net@freebsd.org" X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 29 Aug 2013 19:53:44 -0000 On Aug 29, 2013, at 12:45 PM, Alan Somers wrote: > I pulled all four hash functions out into userland and microbenchmarked t= hem. > The upshot is that hash32 and fnv_hash are the fastest, jenkins_hash is > slower, and siphash24 is the slowest. Also, Clang resulted in much faste= r > code than gcc. I didn't realize that you were testing incremental hashing with 4 and 6 byt= e keys. There might be advantages to conditionally filling out a contiguous key and then performing the hash on that. You could guarantee key alignment, f= or =20 one, and this would benefit the hashes which perform word-sized reads.=20 Based on my quick tests, lookup3 and SipHash improve significantly. T.C. diff -u a/lagg_hash.c b/lagg_hash.c --- a/lagg_hash.c 2013-08-29 14:21:17.255307349 -0400 +++ b/lagg_hash.c 2013-08-29 15:16:31.135653259 -0400 @@ -7,22 +7,30 @@ #include #include #include - -uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t); +#include =20 #define ITERATIONS 100000000 =20 typedef uint32_t do_hash_t(void); =20 -// Pad the MACs with 0s because jenkins_hash operates on 32-bit inputs -const uint8_t ether_shost[] =3D {181, 16, 73, 9, 219, 22, 0, 0}; -const uint8_t ether_dhost[] =3D {69, 170, 210, 111, 24, 120, 0, 0}; +const uint8_t ether_shost[] =3D {181, 16, 73, 9, 219, 22}; +const uint8_t ether_dhost[] =3D {69, 170, 210, 111, 24, 120}; +const uint8_t ether_hosts[] =3D { 181, 16, 73, 9, 219, 22, + 69, 170, 210, 111, 24, 120 }; const struct in_addr ip_src =3D {.s_addr =3D 1329258245}; const struct in_addr ip_dst =3D {.s_addr =3D 1319097119}; +const struct in_addr ips[2] =3D { { .s_addr =3D 1329258245 }, + { .s_addr =3D 1319097119 } }; const uint32_t ports =3D 3132895450; const uint8_t sipkey[16] =3D {7, 239, 255, 43, 68, 53, 56, 225, 98, 81, 177, 80, 92, 235, 242, 39}; =20 +struct key { + uint8_t ether_hosts[12]; + struct in_addr ips[2]; + uint16_t ports[2]; +} __attribute__((packed)); + /* * Simulate how lagg_hashmbuf uses FNV hash for a TCP/IP packet * No VLAN tagging @@ -58,6 +66,15 @@ return (p); } =20 +static __inline init_key(struct key *key) +{ + + /* Simulate copying the info out of the mbuf. */ + memcpy(key->ether_hosts, ether_hosts, sizeof(ether_hosts)); + memcpy(key->ips, ips, sizeof(ips)); + memcpy(key->ports, &ports, sizeof(ports)); +} + /* * Simulate how lagg_hashmbuf would use siphash24 for a TCP/IP packet * No VLAN tagging @@ -65,16 +82,11 @@ uint32_t do_siphash24(void) { SIPHASH_CTX ctx; + struct key key; =20 - SipHash24_Init(&ctx); - SipHash_SetKey(&ctx, sipkey); + init_key(&key); =20 - SipHash_Update(&ctx, ether_shost, 6); - SipHash_Update(&ctx, ether_dhost, 6); - SipHash_Update(&ctx, &ip_src, sizeof(struct in_addr)); - SipHash_Update(&ctx, &ip_dst, sizeof(struct in_addr)); - SipHash_Update(&ctx, &ports, sizeof(ports)); - return (SipHash_End(&ctx) & 0xFFFFFFFF); + return (SipHash24(&ctx, sipkey, &key, sizeof(key)) & 0xFFFFFFFF); } =20 /* @@ -83,19 +95,11 @@ */ uint32_t do_jenkins(void) { - /* Jenkins hash does not recommend any specific initializer */ - uint32_t p =3D FNV1_32_INIT; + struct key key; =20 - /*=20 - * jenkins_hash uses 32-bit inputs, so we need to present the MACs = as - * arrays of 2 32-bit values - */ - p =3D jenkins_hash32((uint32_t*)ether_shost, 2, p); - p =3D jenkins_hash32((uint32_t*)ether_dhost, 2, p); - p =3D jenkins_hash32((uint32_t*)&ip_src, sizeof(struct in_addr) / 4= , p); - p =3D jenkins_hash32((uint32_t*)&ip_dst, sizeof(struct in_addr) / 4= , p); - p =3D jenkins_hash32(&ports, sizeof(ports) / 4, p); - return (p); + init_key(&key); + + return (jenkins_hash(&key, sizeof(key), FNV1_32_INIT)); } =20 =20 diff -u a/siphash.h b/siphash.h --- a/siphash.h 2013-08-29 14:21:21.851306417 -0400 +++ b/siphash.h 2013-08-29 14:26:44.470240137 -0400 @@ -73,8 +73,8 @@ void SipHash_Final(void *, SIPHASH_CTX *); uint64_t SipHash_End(SIPHASH_CTX *); =20 -#define SipHash24(x, y, z, i) SipHashX((x), 2, 4, (y), (z), (i)); -#define SipHash48(x, y, z, i) SipHashX((x), 4, 8, (y), (z), (i)); +#define SipHash24(x, y, z, i) SipHashX((x), 2, 4, (y), (z), (i)) +#define SipHash48(x, y, z, i) SipHashX((x), 4, 8, (y), (z), (i)) uint64_t SipHashX(SIPHASH_CTX *, int, int, const uint8_t [16], const void = *, size_t); =20