From 967da83e032e31f1cf680ffacab1cc46565411cf Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 6 Jan 2009 12:55:14 -0800 Subject: [PATCH] Add lookup3-based hash for bytes, and remove FNV hash entirely. The lookup3 hash is superior to FNV. This change makes OpenFlow use lookup3 exclusively, by adding a variant of it that can hash arbitrary byte sequences. --- lib/flow.h | 6 +++--- lib/hash.c | 51 +++++++++++++++++++++++++++++++--------------- lib/hash.h | 9 +++----- lib/mac-learning.c | 9 ++++---- lib/tag.c | 4 ++-- tests/test-hmap.c | 2 +- vswitchd/bridge.c | 2 +- 7 files changed, 50 insertions(+), 33 deletions(-) diff --git a/lib/flow.h b/lib/flow.h index 63974c45..99b5752c 100644 --- a/lib/flow.h +++ b/lib/flow.h @@ -1,4 +1,4 @@ -/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford +/* Copyright (c) 2008, 2009 The Board of Trustees of The Leland Stanford * Junior University * * We are making the OpenFlow specification and associated documentation @@ -82,8 +82,8 @@ static inline size_t flow_hash(const struct flow *flow, uint32_t basis) { BUILD_ASSERT_DECL(!(sizeof *flow % sizeof(uint32_t))); - return hash_lookup3((const uint32_t *) flow, - sizeof *flow / sizeof(uint32_t), basis); + return hash_words((const uint32_t *) flow, + sizeof *flow / sizeof(uint32_t), basis); } #endif /* flow.h */ diff --git a/lib/hash.c b/lib/hash.c index 22caa923..104ce224 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -1,4 +1,4 @@ -/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford +/* Copyright (c) 2008, 2009 The Board of Trustees of The Leland Stanford * Junior University * * We are making the OpenFlow specification and associated documentation @@ -32,18 +32,7 @@ */ #include #include "hash.h" - -uint32_t -hash_fnv(const void *p_, size_t n, uint32_t basis) -{ - const uint8_t *p = p_; - uint32_t hash = basis; - while (n--) { - hash *= HASH_FNV_PRIME; - hash ^= *p++; - } - return hash; -} +#include /* This is the public domain lookup3 hash by Bob Jenkins from * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */ @@ -70,11 +59,10 @@ hash_fnv(const void *p_, size_t n, uint32_t basis) c ^= b; c -= rot(b, 24); \ } while (0) -/* Returns the hash of the 'n' uint32_t values at 'p', starting from 'basis'. - * Note especially that 'n' is a count of 32-bit words, not bytes, and that +/* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'. * 'p' must be properly aligned. */ uint32_t -hash_lookup3(const uint32_t *p, size_t n, uint32_t basis) +hash_words(const uint32_t *p, size_t n, uint32_t basis) { uint32_t a, b, c; @@ -106,3 +94,34 @@ hash_lookup3(const uint32_t *p, size_t n, uint32_t basis) return c; } +/* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */ +uint32_t +hash_bytes(const void *p_, size_t n, uint32_t basis) +{ + const uint8_t *p = p_; + uint32_t a, b, c; + uint32_t tmp[3]; + + a = b = c = 0xdeadbeef + n + basis; + + while (n >= sizeof tmp) { + memcpy(tmp, p, sizeof tmp); + a += tmp[0]; + b += tmp[1]; + c += tmp[2]; + mix(a, b, c); + n -= sizeof tmp; + p += sizeof tmp; + } + + if (n) { + tmp[0] = tmp[1] = tmp[2] = 0; + memcpy(tmp, p, n); + a += tmp[0]; + b += tmp[1]; + c += tmp[2]; + final(a, b, c); + } + + return c; +} diff --git a/lib/hash.h b/lib/hash.h index 44d7b054..a52d8ca7 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -1,4 +1,4 @@ -/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford +/* Copyright (c) 2008, 2009 The Board of Trustees of The Leland Stanford * Junior University * * We are making the OpenFlow specification and associated documentation @@ -36,10 +36,7 @@ #include #include -#define HASH_FNV_BASIS UINT32_C(2166136261) -#define HASH_FNV_PRIME UINT32_C(16777619) - -uint32_t hash_fnv(const void *, size_t, uint32_t basis); -uint32_t hash_lookup3(const uint32_t *, size_t n, uint32_t basis); +uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis); +uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis); #endif /* hash.h */ diff --git a/lib/mac-learning.c b/lib/mac-learning.c index 61c6fccb..aa1e3ad0 100644 --- a/lib/mac-learning.c +++ b/lib/mac-learning.c @@ -1,4 +1,4 @@ -/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford +/* Copyright (c) 2008, 2009 The Board of Trustees of The Leland Stanford * Junior University * * We are making the OpenFlow specification and associated documentation @@ -79,7 +79,7 @@ struct mac_learning { static uint32_t mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) { - return hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS) ^ vlan; + return hash_bytes(mac, ETH_ADDR_LEN, vlan); } static struct mac_entry * @@ -95,8 +95,9 @@ static tag_type make_unknown_mac_tag(const struct mac_learning *ml, const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) { - return tag_create_deterministic(hash_fnv(&ml->secret, sizeof ml->secret, - mac_table_hash(mac, vlan))); + uint32_t h = hash_bytes(&ml->secret, sizeof ml->secret, + mac_table_hash(mac, vlan)); + return tag_create_deterministic(h); } static struct list * diff --git a/lib/tag.c b/lib/tag.c index ed198fcb..11d4dbe7 100644 --- a/lib/tag.c +++ b/lib/tag.c @@ -1,4 +1,4 @@ -/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford +/* Copyright (c) 2008, 2009 The Board of Trustees of The Leland Stanford * Junior University * * We are making the OpenFlow specification and associated documentation @@ -61,7 +61,7 @@ tag_create_random(void) * * 'seed' should have data in all of its bits; if it has data only in its * low-order bits then the resulting tags will be poorly distributed. Use a - * hash function such as hash_lookup3() to generate 'seed' if necessary. */ + * hash function such as hash_bytes() to generate 'seed' if necessary. */ tag_type tag_create_deterministic(uint32_t seed) { diff --git a/tests/test-hmap.c b/tests/test-hmap.c index ee3289d1..962389fa 100644 --- a/tests/test-hmap.c +++ b/tests/test-hmap.c @@ -138,7 +138,7 @@ static size_t good_hash(int value) { const uint32_t x = value; - return hash_lookup3(&x, 1, 0x1234abcd); + return hash_words(&x, 1, 0x1234abcd); } static size_t diff --git a/vswitchd/bridge.c b/vswitchd/bridge.c index 9b88fcd4..4b8a343a 100644 --- a/vswitchd/bridge.c +++ b/vswitchd/bridge.c @@ -1174,7 +1174,7 @@ queue_tx(struct bridge *br, struct ofpbuf *msg) static struct bond_entry * lookup_bond_entry(const struct port *port, const uint8_t mac[ETH_ADDR_LEN]) { - size_t h = hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS); + size_t h = hash_bytes(mac, ETH_ADDR_LEN, 0); return &port->bond_hash[h & BOND_MASK]; } -- 2.30.2