[ovs-dev] project idea for someone: hash function sensitivity

Ben Pfaff blp at ovn.org
Mon Aug 6 22:49:16 UTC 2018


In theory, all the OVS tests should pass if we change the hash
function.  In practice, some of them fail because changing the hash
function changes ordering of some of the output of the tests.  Currently
I see the following failures:

 805: tunnel.at:512      tunnel - ERSPAN v1/v2 metadata
 1038: dpif-netdev.at:193 dpif-netdev - meters
 1174: ofproto-dpif.at:6653 ofproto-dpif - sFlow packet sampling - tunnel push
 1783: ovsdb-execution.at:1140 index uniqueness checking
      ovsdb execute execution positive
 1813: ovsdb-tool.at:29   index uniqueness checking
      ovsdb file positive
 1850: ovsdb-server.at:41 index uniqueness checking
      ovsdb server positive unix
 1891: ovsdb-server.at:1248 index uniqueness checking
      ovsdb server positive ssl
 1917: ovsdb-server.at:1322 index uniqueness checking
      ovsdb server positive tcp
 1943: ovsdb-server.at:1395 index uniqueness checking
      ovsdb server positive transient
 2286: ovsdb-cluster.at:45 index uniqueness checking - cluster of 1
      ovsdb server positive unix cluster cluster1
 2311: ovsdb-cluster.at:54 index uniqueness checking - cluster of 3
      ovsdb server positive unix cluster cluster3
 2336: ovsdb-cluster.at:63 index uniqueness checking - cluster of 5
      ovsdb server positive unix cluster cluster5
 2342: ovsdb-cluster.at:217 OVSDB 3-server torture test - kill/restart leader
      ovsdb server positive unix cluster cluster3
 2343: ovsdb-cluster.at:221 OVSDB 3-server torture test - kill/restart follower 1
      ovsdb server positive unix cluster cluster3
 2344: ovsdb-cluster.at:225 OVSDB 3-server torture test - kill/restart follower 2
      ovsdb server positive unix cluster cluster3
 2345: ovsdb-cluster.at:229 OVSDB 5-server torture test - kill/restart leader
      ovsdb server positive unix cluster cluster5
 2346: ovsdb-cluster.at:233 OVSDB 5-server torture test - kill/restart follower 1
      ovsdb server positive unix cluster cluster5
 2347: ovsdb-cluster.at:237 OVSDB 5-server torture test - kill/restart follower 2
      ovsdb server positive unix cluster cluster5
 2348: ovsdb-cluster.at:241 OVSDB 5-server torture test - kill/restart follower 3
      ovsdb server positive unix cluster cluster5
 2349: ovsdb-cluster.at:245 OVSDB 5-server torture test - kill/restart follower 4
      ovsdb server positive unix cluster cluster5
 2350: ovsdb-cluster.at:250 OVSDB 3-server torture test - remove/re-add leader
      ovsdb server positive unix cluster cluster3
 2351: ovsdb-cluster.at:254 OVSDB 3-server torture test - remove/re-add follower 1
      ovsdb server positive unix cluster cluster3
 2352: ovsdb-cluster.at:258 OVSDB 3-server torture test - remove/re-add follower 2
      ovsdb server positive unix cluster cluster3
 2353: ovsdb-cluster.at:262 OVSDB 5-server torture test - remove/re-add leader
      ovsdb server positive unix cluster cluster5
 2354: ovsdb-cluster.at:266 OVSDB 5-server torture test - remove/re-add follower 1
      ovsdb server positive unix cluster cluster5
 2355: ovsdb-cluster.at:270 OVSDB 5-server torture test - remove/re-add follower 2
      ovsdb server positive unix cluster cluster5
 2356: ovsdb-cluster.at:274 OVSDB 5-server torture test - remove/re-add follower 3
      ovsdb server positive unix cluster cluster5
 2357: ovsdb-cluster.at:278 OVSDB 5-server torture test - remove/re-add follower 4
      ovsdb server positive unix cluster cluster5

Your mission, if you choose to accept it, is to fix some of these.
Sometimes this amounts to, for example, adding a "sort" filter to the
testsuite itself, or by sorting output in ofp-print.c or ovs-ofctl.c.
There might be other bugs exposed other ways, too.

You can probably reproduce these test failures by applying the following
patch:

diff --git a/lib/hash.h b/lib/hash.h
index a642a1e97954..30aeb6de5d38 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -87,7 +87,7 @@ static inline uint32_t mhash_finish(uint32_t hash)
     hash ^= hash >> 13;
     hash *= 0xc2b2ae35;
     hash ^= hash >> 16;
-    return hash;
+    return ~hash;
 }
 
 static inline uint32_t hash_add(uint32_t hash, uint32_t data);
@@ -350,7 +350,7 @@ static inline uint32_t hash_boolean(bool x, uint32_t basis)
 {
     const uint32_t P0 = 0xc2b73583;   /* This is hash_int(1, 0). */
     const uint32_t P1 = 0xe90f1258;   /* This is hash_int(2, 0). */
-    return (x ? P0 : P1) ^ hash_rot(basis, 1);
+    return ~(x ? P0 : P1) ^ hash_rot(basis, 1);
 }
 
 /* Helper functions for calling hash_add() for several 32- or 64-bit words in a


More information about the dev mailing list