[sanitizer] Add iterator to AddrHashMap

[bruening]

Summary

Adds an iterator to the AddrHashMap class used by sanitizer runtime
libraries. Adds a test of the new iterator.

[kcc]

Please don't commit w/o Dmitry's LGTM

[vitalybuka]

lib/sanitizer_common/sanitizer_addrhashmap.h

113

I think logic could be simpler if Iterator contained temp copy of HashValue<T*>
and operator* returns reference to it.

E.g.:
class Iterator {

const HashValue<T*>& operator*() {
  return curr_item_;
}

 Iterator& operator++() {
    // all logic here,
    curr_item_ = something.
  }

 HashValue<T*> curr_item_;

}

121

add == nullptr should not be possible according line 139

130

This will hide bugs. We should crash here if someone increments end().

136

Iterating concurrent hash map looks scary in general, and not very efficient.
This will hold bucket locked entire iterator lifetime.
Maybe safer to consider some alternatives, like exporting entire table as array.
So you can get array under the log, and do whatever you want after release.

[dvyukov]

lib/sanitizer_common/sanitizer_addrhashmap.h

91

remove the template, and just use T*
simpler and less typing

92

s/HashValue/Value/

It's already in the scope of Addr_Hash_Map.

101

please move all the code out of the class declaration to the bottom of the file

you can see that it is done for all member functions here, I wanted the declaration to remain at least minimally readable (to the point it is possible with C++)

105

this won't work: iterator can hold mutex lock

if you copy the iterator, you will double unlock the mutex and corrupt its state

do you plan to use them? if not, = delete

124

this must be acquire to pair with release in the release function

but unfortunately that's not enough: elements can be concurrently removed and overwritten
that's ok for normal usages because lookup for an element should not race with its removal, embed elements are not compacted, and accesses to add elements are protected with read lock

I think the simplest fix would be to read lock the cell whenever you access it (both embed and add elements).

136

unless I am missing something, this can double-lock the mutex if a cell contains more than 1 add element

need more tests to catch it

lib/sanitizer_common/tests/sanitizer_addrhashmap_test.cc

1

s/bitvector/addrhashmap/

11

s/bitvector/addrhashmap/

[bruening]

AddrHashMap has significant limitations that make it unsuitable for most of our use cases for hashtables and we're going to need to add a separate, more general-purpose table: the data being read-only after creation, and most importantly, the fixed-size table that cannot resize and adapt to the size of the app, are blockers for us. Abandoning this CL.

lib/sanitizer_common/sanitizer_addrhashmap.h

private:
     Cell                  *cell_;
     uptr                   addr_;
     uptr                   addidx_;
     bool                   created_;
     bool                   remove_;
     bool                   create_;
   };
 
+  template<typename U>
+  struct HashValue {
+    HashValue<U>(uptr a, U v) : addr(a), value(v) {}
+    uptr addr;
+    U value;
+  };
+
+  class Iterator {
+   public:
+    Iterator(AddrHashMap<T, kSize>* map) :
+      map_(map), bucket_idx_(0), embed_idx_(0), add_idx_(0) {
+      if (operator*().addr == 0)
+        operator++();
+    }
+    Iterator(const Iterator& src) = default;
+    Iterator& operator=(const Iterator& src) = default;
+    ~Iterator() {
+      if (bucket_idx_ < kSize && embed_idx_ >= kBucketSize) {
+        Bucket *b = &map_->table_[bucket_idx_];
+        b->mtx.ReadUnlock();
+      }
+    }
+    HashValue<T*> operator*() {
+      Bucket *b = &map_->table_[bucket_idx_];
+      Cell *c;
+      if (embed_idx_ < kBucketSize) {
+        c = &b->cells[embed_idx_];
+      } else {
+        AddBucket *add = (AddBucket*)atomic_load(&b->add, memory_order_relaxed);
+        if (add == nullptr)
+          return HashValue<T*>(0, nullptr);
+        c = &add->cells[add_idx_];
+      }
+      uptr addr = atomic_load(&c->addr, memory_order_relaxed);
+      return HashValue<T*>(addr, &c->val);
+    }
+    Iterator& operator++() {
+      do {
+        if (bucket_idx_ == kSize)
+          return *this;
+        if (embed_idx_ < kBucketSize) {
+          ++embed_idx_;
+        } else {
+          Bucket *b = &map_->table_[bucket_idx_];
+          // We must hold the read lock across the iteration.
+          b->mtx.ReadLock();
+          AddBucket *add = (AddBucket*)atomic_load(&b->add,
+                                                   memory_order_relaxed);
+          if (add == nullptr || ++add_idx_ >= add->size) {
+            b->mtx.ReadUnlock();
+            add_idx_ = 0;
+            embed_idx_ = 0;
+            ++bucket_idx_;
+          }
+        }
+      } while (operator*().addr == 0);
+      return *this;
+    }
+    Iterator operator++(int) {
+      Iterator temp(*this);
+      operator++();
+      return temp;
+    }
+    // Decrement not supported.
+    bool operator==(const Iterator& vs) const {
+      return (vs.map_ == map_ && vs.bucket_idx_ == bucket_idx_ &&
+              vs.embed_idx_ == embed_idx_ && vs.add_idx_ == add_idx_);
+    }
+    bool operator!=(const Iterator& vs) const {
+      return (vs.map_ != map_ || vs.bucket_idx_ != bucket_idx_ ||
+              vs.embed_idx_ != embed_idx_ || vs.add_idx_ != add_idx_);
+    }
+
+   private:
+    Iterator(AddrHashMap<T, kSize>* map, uptr bucket_idx) :
+      map_(map), bucket_idx_(bucket_idx), embed_idx_(0), add_idx_(0) {}
+    friend AddrHashMap<T, kSize>;
+    AddrHashMap<T, kSize> *map_;
+    uptr bucket_idx_;
+    uptr embed_idx_;
+    uptr add_idx_;
+  };
+
+  // We do not support erase or insert iterators.
+  Iterator begin() { return Iterator(this); }
+  Iterator end() { return Iterator(this, kSize); }
+
  private:
   friend class Handle;
+  friend class Iterator;
   Bucket *table_;
 
   void acquire(Handle *h);
   void release(Handle *h);
   uptr calcHash(uptr addr);
 };
 
 template<typename T, uptr kSize>

lib/sanitizer_common/tests/CMakeLists.txt

 include(CompilerRTCompile)
 
 clang_compiler_add_cxx_check()
 
 # FIXME: use SANITIZER_COMMON_SUPPORTED_ARCH here
 filter_available_targets(SANITIZER_UNITTEST_SUPPORTED_ARCH x86_64 i386 mips64 mips64el)
 if(APPLE)
   darwin_filter_host_archs(SANITIZER_UNITTEST_SUPPORTED_ARCH SANITIZER_COMMON_SUPPORTED_ARCH)
 endif()
 
 set(SANITIZER_UNITTESTS
+  sanitizer_addrhashmap_test.cc
   sanitizer_allocator_test.cc
   sanitizer_atomic_test.cc
   sanitizer_bitvector_test.cc
   sanitizer_bvgraph_test.cc
   sanitizer_common_test.cc
   sanitizer_deadlock_detector_test.cc
   sanitizer_flags_test.cc
   sanitizer_format_interceptor_test.cc

lib/sanitizer_common/tests/sanitizer_addrhashmap_test.cc

+//===-- sanitizer_bitvector_test.cc ---------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of Sanitizer runtime.
+// Tests for sanitizer_bitvector.h.
+//
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common/sanitizer_addrhashmap.h"
+#include "sanitizer_test_utils.h"
+#include "gtest/gtest.h"
+
+using namespace __sanitizer;
+
+typedef AddrHashMap<int, 7> IntHashMap;
+
+static void addNewEntry(IntHashMap *IntMap, uptr Addr, int Value) {
+  IntHashMap::Handle H(IntMap, Addr, false/*!remove*/, true/*create*/);
+  EXPECT_TRUE(H.exists());
+  EXPECT_TRUE(H.created());
+  // Sort of awkward: works better with a struct.
+  *(H.operator->()) = Value;
+}
+
+TEST(SanitizerCommon, AddrHashMap) {
+  IntHashMap *IntMap;
+  static char HashMem[sizeof(*IntMap)];
+  IntMap = new((void *)&HashMem) IntHashMap();
+
+  uptr TestAddr = 0x1234;
+  addNewEntry(IntMap, TestAddr, 42);
+  // Handles need scope exit to work properly:
+  {
+    IntHashMap::Handle Lookup(IntMap, TestAddr, false/*!remove*/,
+                              false/*!create*/);
+    EXPECT_TRUE(Lookup.exists());
+    EXPECT_FALSE(Lookup.created());
+  }
+  {
+    IntHashMap::Handle Rm(IntMap, TestAddr, true/*remove*/);
+    EXPECT_TRUE(Rm.exists());
+  }
+  addNewEntry(IntMap, TestAddr, 42);
+  addNewEntry(IntMap, TestAddr+1, 43);
+  addNewEntry(IntMap, TestAddr+2, 44);
+
+  int Count = 0;
+  for (auto Iter = IntMap->begin(); Iter != IntMap->end(); ++Iter, ++Count) {
+    uptr Addr = (*Iter).addr;
+    int *Value = (*Iter).value;
+    EXPECT_TRUE(Addr >= TestAddr && Addr <= TestAddr+2);
+    EXPECT_TRUE(*Value >= 42 && *Value <= 44);
+  }
+  EXPECT_EQ(Count, 3);
+}