Flow ID, LACP, and igb

[Alan Somers]

On Thu, Aug 29, 2013 at 1:33 PM, T.C. Gubatayao <tgubatayao at barracuda.com>wrote:

> On Aug 29, 2013, at 12:45 PM, Alan Somers <asomers at freebsd.org> wrote:
>
> > I pulled all four hash functions out into userland and microbenchmarked
> them.
> > 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
> faster
> > code than gcc.
>
> I didn't realize that you were testing incremental hashing with 4 and 6
> byte
> keys.
>
> There might be advantages to conditionally filling out a contiguous key
> and then performing the hash on that.  You could guarantee key alignment,
> for
> one, and this would benefit the hashes which perform word-sized reads.
>
> Based on my quick tests, lookup3 and SipHash improve significantly.
>

They're faster, but even with this change, jenkins_hash is still 6 times
slower than FNV hash.  Also, your technique of copying the hashable fields
into a separate buffer would need modification to work with different types
of packet and different LAGG_F_HASH[234] flags.  Because different packets
have different hashable fields, struct key would need to be expanded to
include the vlan tag, IPV6 addresses, and IPv6 flowid.  lagg_hashmbuf would
then have to zero the unused fields.  In any case, that's not going to make
Jenkins and SipHash24 more likely to beat FNV.


>
> 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 <sys/hash.h>
>  #include <sys/fnv_hash.h>
>  #include <sys/time.h>
> -
> -uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t);
> +#include <string.h>
>
>  #define ITERATIONS     100000000
>
>  typedef uint32_t do_hash_t(void);
>
> -// Pad the MACs with 0s because jenkins_hash operates on 32-bit inputs
> -const uint8_t ether_shost[] = {181, 16, 73, 9, 219, 22, 0, 0};
> -const uint8_t ether_dhost[] = {69, 170, 210, 111, 24, 120, 0, 0};
> +const uint8_t ether_shost[] = {181, 16, 73, 9, 219, 22};
> +const uint8_t ether_dhost[] = {69, 170, 210, 111, 24, 120};
> +const uint8_t ether_hosts[] = { 181, 16, 73, 9, 219, 22,
> +                               69, 170, 210, 111, 24, 120 };
>  const struct in_addr ip_src = {.s_addr = 1329258245};
>  const struct in_addr ip_dst = {.s_addr = 1319097119};
> +const struct in_addr ips[2] = { { .s_addr = 1329258245 },
> +                               { .s_addr = 1319097119 } };
>  const uint32_t ports = 3132895450;
>  const uint8_t sipkey[16] = {7, 239, 255, 43, 68, 53, 56, 225,
>                             98, 81, 177, 80, 92, 235, 242, 39};
>
> +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);
>  }
>
> +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;
>
> -       SipHash24_Init(&ctx);
> -       SipHash_SetKey(&ctx, sipkey);
> +       init_key(&key);
>
> -       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);
>  }
>
>  /*
> @@ -83,19 +95,11 @@
>   */
>  uint32_t do_jenkins(void)
>  {
> -       /* Jenkins hash does not recommend any specific initializer */
> -       uint32_t p = FNV1_32_INIT;
> +       struct key key;
>
> -       /*
> -        * jenkins_hash uses 32-bit inputs, so we need to present the MACs
> as
> -        * arrays of 2 32-bit values
> -        */
> -       p = jenkins_hash32((uint32_t*)ether_shost, 2, p);
> -       p = jenkins_hash32((uint32_t*)ether_dhost, 2, p);
> -       p = jenkins_hash32((uint32_t*)&ip_src, sizeof(struct in_addr) / 4,
> p);
> -       p = jenkins_hash32((uint32_t*)&ip_dst, sizeof(struct in_addr) / 4,
> p);
> -       p = jenkins_hash32(&ports, sizeof(ports) / 4, p);
> -       return (p);
> +       init_key(&key);
> +
> +       return (jenkins_hash(&key, sizeof(key), FNV1_32_INIT));
>  }
>
>
> 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 *);
>
> -#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);
>
>