sanitizer_common: add HashMap class

[dvyukov]

Summary

HashMap is a single-threaded, dynamically-resized hashmap
with open addressing and linear probing.
Will be used in subsequent commits.

Depends on D113922.

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_hashmap.h

104

sanitizer_common.h has IsPowerOfTwo() which is equivalent

compiler-rt/lib/sanitizer_common/tests/sanitizer_hashmap_test.cpp

70

For new datastructures like this I find a random test that does differential fuzzing of sorts is quite helpful.

Something like:

RandOp() // returns random op
RandKey() // returns random key in range [A;B]
RandVal() // returns random val in range [X;Y]

std::unordered_map<int, long> reference; // assumes it's correct
HashMap<int, long> under_test;

for (int iter = 0; iter < 10000; iter++) {
  switch(RandOp()) {
    case kInsert: {
      int k = RandKey();
      int v = RandVal();
      under_test.Insert(k, v);
      reference.emplace_back(k, v);
    }
    case kRemove: // check that removal matches
    case kFind: // check that found values match
  }
  // check that various properties match, in this case probably just that size matches.
}
...

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_hashmap.h

39

I think this pre-condition is excessive and might actually cause subtle mistakes by callers that don't expect this or don't care.

Right now I see you use DCHECK() everywhere to check that the key isn't already present, but then Insert does another CHECK.

I think a cleaner API would be to mark this function [[nodiscard]] (do we already have a macro?) and have it return a bool if insertion succeeded or not. That way the decision if the key should not be present is pushed to the caller, for who it might matter or not.

But there's no fundamental limitation to why Insert can't be called with the key already present. I'd make the behaviour similar to unordered_map::emplace().

[dvyukov]

return bool from Insert
add random test

[dvyukov]

PTAL

[melver]

Nice.

[vitalybuka]

How about I upload patch with DenseMap forked from LLVM? it needs just a few changes for compiler-rt?

[dvyukov]

In D113996#3135360, @vitalybuka wrote:

How about I upload patch with DenseMap forked from LLVM? it needs just a few changes for compiler-rt?

Hard to say, DenseMap*.h is 1000+ LOC... what runtime difference does it make?
Can it be made to use a single large mmap? I think that' the only solution that will work well for sanitizer runtimes (doing lots of small allocations will require passing in allocator cache, and increasing in size allocations won't work well because we don't reuse memory between size classes, so it will be quadratic memory w/o mmap).
Overall I am happy to use anything that allows me to write Map<K,V>.

[vitalybuka]

In D113996#3135377, @dvyukov wrote:

In D113996#3135360, @vitalybuka wrote:

How about I upload patch with DenseMap forked from LLVM? it needs just a few changes for compiler-rt?

Hard to say, DenseMap*.h is 1000+ LOC... what runtime difference does it make?

few changes (without counting trowing away most of the stuff, like iterators and small set)
It's not about runtime, I already did that for my current work, in local checkout.

Can it be made to use a single large mmap? I think that' the only solution that will work well for sanitizer runtimes (doing lots of small allocations will require passing in allocator cache, and increasing in size allocations won't work well because we don't reuse memory between size classes, so it will be quadratic memory w/o mmap).

Yes. That's how I use it.

Overall I am happy to use anything that allows me to write Map<K,V>.

The same for me. I guess I can prefectly use HashMap as well. Quadratic probing is nice but is not requirement for me.
I'll cleanup my stuff and upload. I did that patch about a month ago, maybe it looks worse than I remember.

compiler-rt/lib/sanitizer_common/sanitizer_hashmap.h

25

constexpr constructor would be nice, but I can fix it later for my needs.

39

+1 it would be nice to have more conventional interface where it returns <KV*, bool new_inserted>

40

const K &k, const V &v and below?

53

this one a little bit scary.
presence of a single cluster with 8 elements will trigger grow. Then Grow will redistributed them into precisely two hashes with high prob to create another large cluster, trigger another Grow, making load factor of the table quite low.

Can be fixed in followup patches if needed.

74

can you use sentinel values here instead bool flag which will add padding?

[vitalybuka]

D114048

[vitalybuka]

I amuse this can be abandoned?

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_flag_parser.h
   sanitizer_flags.h
   sanitizer_flags.inc
   sanitizer_flat_map.h
   sanitizer_freebsd.h
   sanitizer_fuchsia.h
   sanitizer_getauxval.h
   sanitizer_hash.h
+  sanitizer_hashmap.h
   sanitizer_interceptors_ioctl_netbsd.inc
   sanitizer_interface_internal.h
   sanitizer_internal_defs.h
   sanitizer_lfstack.h
   sanitizer_libc.h
   sanitizer_libignore.h
   sanitizer_linux.h
   sanitizer_list.h

compiler-rt/lib/sanitizer_common/sanitizer_hashmap.h

+//===-- sanitizer_hashmap.h -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is shared between sanitizers run-time libraries.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_HASHMAP_H
+#define SANITIZER_HASHMAP_H
+
+#include "sanitizer_common.h"
+#include "sanitizer_hash.h"
+
+namespace __sanitizer {
+
+// A single-threaded, dynamically-resized hashmap
+// with open addressing and linear probing.
+// Currently supports only POD K/V types.
+template <typename K, typename V>
+class HashMap {
+ public:
+  HashMap() {
+    // We need at least kProbes elements,
+    // but otherwise use how many fits into a page.
+    Init(Max(kProbes, 1ul << MostSignificantSetBitIndex(GetPageSizeCached() /
+                                                        sizeof(Elem))));
+  }
+  ~HashMap() { UnmapOrDie(elems_, mem_size_); }
+  HashMap(const HashMap &) = delete;
+  HashMap &operator=(const HashMap &) = delete;
+
+  // Inserts element (k, v) into the map if it's not in the map yet.
+  // Returns true if the element was inserted.
+  WARN_UNUSED_RESULT
+  bool Insert(K k, V v) {
+    if (Find(k))
+      return false;
+    const uptr h = hash(k);
+    for (;;) {
+      for (uptr i = 0; i < kProbes; i++) {
+        auto &elem = elems_[index(h, i)];
+        CHECK(!elem.filled || elem.k != k);
+        if (elem.filled)
+          continue;
+        elem = {k, v, true};
+        return true;
+      }
+      Grow();
+    }
+  }
+
+  // Removes the element with key k from the map.
+  // Returns true if the element was found and removed.
+  // If v is passed, v is set to the element's value.
+  bool Remove(K k, V *v = nullptr) { return FindRemove(k, v, true); }
+
+  // Searches for the element with key k.
+  // Returns true if the element was found.
+  // If v is passed, v is set to the element's value.
+  WARN_UNUSED_RESULT
+  bool Find(K k, V *v = nullptr) { return FindRemove(k, v, false); }
+
+ private:
+  static constexpr uptr kProbes = 8;
+
+  struct Elem {
+    K k;
+    V v;
+    bool filled;
+  };
+
+  Elem *elems_;
+  uptr size_;
+  uptr mem_size_;
+
+  static uptr hash(K k) {
+    static_assert(sizeof(K) <= sizeof(u64), "bad key size");
+    MurMur2Hash64Builder murmur2;
+    murmur2.add(static_cast<u64>(k));
+    return murmur2.get();
+  }
+
+  uptr index(uptr h, uptr i) const { return (h + i) & (size_ - 1); }
+
+  bool FindRemove(K k, V *v, bool remove) {
+    const uptr h = hash(k);
+    for (uptr i = 0; i < kProbes; i++) {
+      auto &elem = elems_[index(h, i)];
+      if (!elem.filled || elem.k != k)
+        continue;
+      if (v)
+        *v = elem.v;
+      if (remove)
+        elem.filled = false;
+      return true;
+    }
+    return false;
+  }
+
+  void Init(uptr size) {
+    // Index uses & to calculate modulo.
+    CHECK(IsPowerOfTwo(size));
+    size_ = size;
+    mem_size_ = RoundUpTo(size_ * sizeof(Elem), GetPageSizeCached());
+    elems_ = static_cast<Elem *>(MmapOrDie(mem_size_, "HashMap"));
+  }
+
+  void Grow() {
+    Elem *elems = elems_;
+    uptr size = size_;
+    uptr mem_size = mem_size_;
+    Init(size * 2);
+    for (uptr i = 0; i < size; i++) {
+      Elem &elem = elems[i];
+      if (elem.filled)
+        CHECK(Insert(elem.k, elem.v));
+    }
+    UnmapOrDie(elems, mem_size);
+  }
+};
+
+}  // namespace __sanitizer
+
+#endif  // #ifndef SANITIZER_HASHMAP_H

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

set(SANITIZER_UNITTESTS
   sanitizer_bvgraph_test.cpp
   sanitizer_chained_origin_depot_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_flat_map_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_hash_test.cpp
+  sanitizer_hashmap_test.cpp
   sanitizer_ioctl_test.cpp
   sanitizer_libc_test.cpp
   sanitizer_linux_test.cpp
   sanitizer_list_test.cpp
   sanitizer_mac_test.cpp
   sanitizer_mutex_test.cpp
   sanitizer_nolibc_test.cpp
   sanitizer_posix_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_hashmap_test.cpp

+//===-- sanitizer_hashmap_test.cpp ----------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of *Sanitizer runtime.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_hashmap.h"
+
+#include <unordered_map>
+
+#include "gtest/gtest.h"
+
+namespace __sanitizer {
+
+TEST(HashMap, Basic) {
+  HashMap<int, long> m;
+  EXPECT_FALSE(m.Find(0));
+  EXPECT_FALSE(m.Find(1));
+  EXPECT_FALSE(m.Remove(0));
+  EXPECT_FALSE(m.Remove(1));
+
+  EXPECT_TRUE(m.Insert(1, 2));
+  EXPECT_FALSE(m.Find(0));
+  long v = 0;
+  EXPECT_TRUE(m.Find(1, &v));
+  EXPECT_EQ(v, 2);
+  EXPECT_FALSE(m.Remove(0));
+  v = 0;
+  EXPECT_TRUE(m.Remove(1, &v));
+  EXPECT_EQ(v, 2);
+  EXPECT_FALSE(m.Find(1));
+
+  EXPECT_TRUE(m.Insert(10, 11));
+  EXPECT_TRUE(m.Insert(20, 22));
+  v = 0;
+  EXPECT_TRUE(m.Find(10, &v));
+  EXPECT_EQ(v, 11);
+  v = 0;
+  EXPECT_TRUE(m.Find(20, &v));
+  EXPECT_EQ(v, 22);
+  v = 0;
+  EXPECT_TRUE(m.Remove(10, &v));
+  EXPECT_EQ(v, 11);
+  v = 0;
+  EXPECT_TRUE(m.Remove(20, &v));
+  EXPECT_EQ(v, 22);
+}
+
+TEST(HashMap, Grow) {
+  HashMap<int, long> m;
+  const int kCount = 10000;
+  for (int i = 0; i < kCount; i++) EXPECT_TRUE(m.Insert(i, i + 100));
+  EXPECT_FALSE(m.Find(kCount));
+  for (int i = 0; i < kCount; i++) {
+    long v = 0;
+    EXPECT_TRUE(m.Find(i, &v));
+    EXPECT_EQ(v, i + 100);
+  }
+  for (int i = 0; i < kCount; i++) {
+    long v = 0;
+    EXPECT_TRUE(m.Remove(i, &v));
+    EXPECT_EQ(v, i + 100);
+  }
+  for (int i = 0; i < kCount; i++) EXPECT_FALSE(m.Find(i));
+}
+
+TEST(HashMap, Random) {
+  std::unordered_map<int, int> m0;
+  HashMap<int, int> m1;
+  unsigned seed = 0;
+  for (int i = 0; i < 10000; i++) {
+    const int k = rand_r(&seed) % 100;
+    switch (rand_r(&seed) % 3) {
+      case 0: {
+        const int v = rand_r(&seed);
+        auto r0 = m0.emplace(k, v);
+        bool r1 = m1.Insert(k, v);
+        EXPECT_EQ(r0.second, r1);
+        break;
+      }
+      case 1: {
+        auto r0 = m0.find(k);
+        int v1 = 0;
+        bool r1 = m1.Find(k, &v1);
+        EXPECT_EQ(r0 != m0.end(), r1);
+        if (r1)
+          EXPECT_EQ(r0->second, v1);
+        break;
+      }
+      case 2: {
+        auto r0 = m0.erase(k);
+        bool r1 = m1.Remove(k);
+        EXPECT_EQ(r0, r1);
+        break;
+      }
+    }
+  }
+}
+
+}  // namespace __sanitizer