From 4f59148e575e01ed1896ff98f0e8a99ab689ebe5 Mon Sep 17 00:00:00 2001 From: Evgeniy Stepanov Date: Fri, 11 Jul 2014 09:09:37 +0000 Subject: [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 --- lib/msan/msan_chained_origin_depot.cc | 13 +++++++++++++ 1 file changed, 13 insertions(+) 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; -- cgit v1.2.1