[ovs-discuss] [PATCH] hash: Improve 128-bit hash to 32-bit output.

[Joe Stringer]

Previously, when using the 128-bit hash in conjunction with the 32-bit
hash tables, we would ignore the upper 96 bits rather than attempting to
redistribute the hash across the 32-bit output space. This patch adds a
new function to translate the hash down from 128 bits to 32 bits for
this use case.

XXX: Also modify the u64 accessors for ovs_u128 on big_endian systems.
XXX: Also don't exit immediately on hash test failure.

Signed-off-by: Joe Stringer <joestrin...@nicira.com>
---
Resend due to GMail wrapping long lines.
---
 include/openvswitch/types.h   |    4 ++++
 lib/dpif-netdev.c             |    2 +-
 lib/hash.h                    |   11 +++++++++++
 ofproto/ofproto-dpif-upcall.c |    2 +-
 tests/test-hash.c             |    5 ++---
 5 files changed, 19 insertions(+), 5 deletions(-)

diff --git a/include/openvswitch/types.h b/include/openvswitch/types.h
index 2afb7b7..efd44fc 100644
--- a/include/openvswitch/types.h
+++ b/include/openvswitch/types.h
@@ -84,7 +84,11 @@ typedef struct {
 typedef union {
     uint32_t u32[4];
     struct {
+#ifdef WORDS_BIGENDIAN
+        uint64_t hi, lo;
+#else
         uint64_t lo, hi;
+#endif
     } u64;
 } ovs_u128;
 
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 890870c..e07cb80 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -1162,7 +1162,7 @@ static void dp_netdev_flow_unref(struct dp_netdev_flow 
*flow)
 static uint32_t
 dp_netdev_flow_hash(const ovs_u128 *ufid)
 {
-    return ufid->u32[0];
+    return hash128_to_32(ufid);
 }
 
 static void
diff --git a/lib/hash.h b/lib/hash.h
index c2820dd..818fcca 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -35,6 +35,7 @@ hash_rot(uint32_t x, int k)
 uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis);
 void hash_bytes128(const void *_, size_t n_bytes, uint32_t basis,
                    ovs_u128 *out);
+uint32_t hash128_to_32(const ovs_u128 *hash);
 
 static inline uint32_t hash_int(uint32_t x, uint32_t basis);
 static inline uint32_t hash_2words(uint32_t, uint32_t);
@@ -84,6 +85,16 @@ static inline uint32_t mhash_finish(uint32_t hash)
     return hash;
 }
 
+static inline uint32_t hash128_to_32(const ovs_u128 *hash)
+{
+    uint32_t h1, h2;
+
+    h1 = mhash_add(hash->u32[0], hash->u32[1]);
+    h2 = mhash_add(hash->u32[2], hash->u32[3]);
+
+    return mhash_finish(mhash_add(h1, h2));
+}
+
 #if !(defined(__SSE4_2__) && defined(__x86_64__))
 /* Mhash-based implementation. */
 
diff --git a/ofproto/ofproto-dpif-upcall.c b/ofproto/ofproto-dpif-upcall.c
index 4a7a829..8b2a38d 100644
--- a/ofproto/ofproto-dpif-upcall.c
+++ b/ofproto/ofproto-dpif-upcall.c
@@ -1247,7 +1247,7 @@ handle_upcalls(struct udpif *udpif, struct upcall 
*upcalls,
 static uint32_t
 get_ufid_hash(const ovs_u128 *ufid)
 {
-    return ufid->u32[0];
+    return hash128_to_32(ufid);
 }
 
 static struct udpif_key *
diff --git a/tests/test-hash.c b/tests/test-hash.c
index d7e2e6b..80d24ed 100644
--- a/tests/test-hash.c
+++ b/tests/test-hash.c
@@ -74,8 +74,8 @@ hash_bytes128_cb(uint32_t input)
 {
     ovs_u128 hash;
 
-    hash_bytes128(&input, sizeof input, 0, &hash);
-    return hash.u64.lo;
+    hash_bytes128(&input, sizeof input, 233, &hash);
+    return hash128_to_32(&hash);
 }
 
 static void
@@ -101,7 +101,6 @@ check_word_hash(uint32_t (*hash)(uint32_t), const char 
*name,
                     printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
                     printf("%d bits of output starting at bit %d "
                            "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
-                    exit(1);
                 }
             }
         }
-- 
1.7.10.4

_______________________________________________
discuss mailing list
discuss@openvswitch.org
http://openvswitch.org/mailman/listinfo/discuss