[msan] A comment for the chained-origin-depot hash function.

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@212801 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 13 insertions, 0 deletions

diff --git a/lib/msan/msan_chained_origin_depot.cc b/lib/msan/msan_chained_origin_depot.cc
index faf04614a..8e5decd76 100644
--- a/lib/msan/msan_chained_origin_depot.cc
+++ b/lib/msan/msan_chained_origin_depot.cc
@@ -19,6 +19,19 @@ namespace __msan {
 struct ChainedOriginDepotDesc {
   u32 here_id;
   u32 prev_id;
+  /* This is murmur2 hash for the 64->32 bit case.
+     It does not behave all that well because the keys have a very biased
+     distribution (I've seen 7-element buckets with the table only 14% full).
+
+     here_id is built of
+     * (1 bits) Reserved, zero.
+     * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
+     * (23 bits) Sequential number (each part has each own sequence).
+
+     prev_id has either the same distribution as here_id (but with 3:8:21)
+     split, or one of two reserved values (-1) or (-2). Either case can
+     dominate depending on the workload.
+  */
   u32 hash() const {
     const u32 m = 0x5bd1e995;
     const u32 seed = 0x9747b28c;