[sanitizer] Remove id and replace link with u32

[vitalybuka]

Summary

This lets us reduce size of Node, similar to D111183 proposal.

Depends on D111610.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

28

nice

compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

66

This effectively makes kReservedBits at least 1, so we could reduce kNodesSize1/2 by half.

[vitalybuka]

rebase

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

 namespace {
 struct ChainedOriginDepotDesc {
   u32 here_id;
   u32 prev_id;
 };
 
 struct ChainedOriginDepotNode {
   using hash_type = u32;
-  ChainedOriginDepotNode *link;
-  u32 id;
+  u32 link;
   u32 here_id;
   u32 prev_id;
 
   typedef ChainedOriginDepotDesc args_type;
 
   bool eq(hash_type hash, const args_type &args) const;
 
   static uptr allocated() { return 0; }
 
   static hash_type hash(const args_type &args);
 
   static bool is_valid(const args_type &args);
 
   void store(const args_type &args, hash_type other_hash);
 
   args_type load() const;
 
   struct Handle {
-    const ChainedOriginDepotNode *node_;
-    Handle() : node_(nullptr) {}
-    explicit Handle(const ChainedOriginDepotNode *node) : node_(node) {}
+    const ChainedOriginDepotNode *node_ = nullptr;
+    u32 id_ = 0;
+    Handle(const ChainedOriginDepotNode *node, u32 id) : node_(node), id_(id) {}
     bool valid() const { return node_; }
-    u32 id() const { return node_->id; }
+    u32 id() const { return id_; }
     int here_id() const { return node_->here_id; }
     int prev_id() const { return node_->prev_id; }
   };
 
-  Handle get_handle() const;
+  static Handle get_handle(u32 id);
 
   typedef Handle handle_type;
 };
 
 }  // namespace
 
 static StackDepotBase<ChainedOriginDepotNode, 4, 20> depot;
 
void ChainedOriginDepotNode::store(const args_type &args,
   prev_id = args.prev_id;
 }
 
 ChainedOriginDepotNode::args_type ChainedOriginDepotNode::load() const {
   args_type ret = {here_id, prev_id};
   return ret;
 }
 
-ChainedOriginDepotNode::Handle ChainedOriginDepotNode::get_handle() const {
-  return Handle(this);
+ChainedOriginDepotNode::Handle ChainedOriginDepotNode::get_handle(u32 id) {
+  return Handle(&depot.nodes[id], id);
 }
 
 ChainedOriginDepot::ChainedOriginDepot() {}
 
 StackDepotStats ChainedOriginDepot::GetStats() const {
   return depot.GetStats();
 }
 
 bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) {
   ChainedOriginDepotDesc desc = {here_id, prev_id};
   bool inserted;
-  ChainedOriginDepotNode::Handle h = depot.Put(desc, &inserted);
-  *new_id = h.valid() ? h.id() : 0;
+  *new_id = depot.Put(desc, &inserted);
   return inserted;
 }
 
 u32 ChainedOriginDepot::Get(u32 id, u32 *other) {
   ChainedOriginDepotDesc desc = depot.Get(id);
   *other = desc.prev_id;
   return desc.here_id;
 }
 
 void ChainedOriginDepot::LockAll() { depot.LockAll(); }
 
 void ChainedOriginDepot::UnlockAll() { depot.UnlockAll(); }
 
 }  // namespace __sanitizer

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.h

 #include "sanitizer_internal_defs.h"
 #include "sanitizer_stacktrace.h"
 
 namespace __sanitizer {
 
 // StackDepot efficiently stores huge amounts of stack traces.
 struct StackDepotNode;
 struct StackDepotHandle {
-  StackDepotNode *node_;
-  StackDepotHandle() : node_(nullptr) {}
-  explicit StackDepotHandle(StackDepotNode *node) : node_(node) {}
+  StackDepotNode *node_ = nullptr;
+  u32 id_ = 0;
+  StackDepotHandle(StackDepotNode *node, u32 id) : node_(node), id_(id) {}
   bool valid() const { return node_; }
-  u32 id() const;
+  u32 id() const { return id_; }
   int use_count() const;
   void inc_use_count_unsafe();
 };
 
 const int kStackDepotMaxUseCount = 1U << (SANITIZER_ANDROID ? 16 : 20);
 
 StackDepotStats StackDepotGetStats();
 u32 StackDepotPut(StackTrace stack);

 class StackDepotReverseMap {
  public:
   StackDepotReverseMap() = default;
   StackTrace Get(u32 id) const;
 
  private:
   struct IdDescPair {
     u32 id;
-    StackDepotNode *desc;
+    const StackDepotNode *desc;
 
     static bool IdComparator(const IdDescPair &a, const IdDescPair &b);
   };
 
   void Init() const;
 
   mutable InternalMmapVector<IdDescPair> map_;
 
   // Disallow evil constructors.
   StackDepotReverseMap(const StackDepotReverseMap&);
   void operator=(const StackDepotReverseMap&);
 };
 
 } // namespace __sanitizer
 
 #endif // SANITIZER_STACKDEPOT_H

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp

 
 namespace __sanitizer {
 
 static PersistentAllocator<uptr> traceAllocator;
 
 struct StackDepotNode {
   using hash_type = u64;
   hash_type stack_hash;
-  StackDepotNode *link;
   uptr *stack_trace;
-  u32 id;
+  u32 link;
   atomic_uint32_t tag_and_use_count;  // tag : 12 high bits; use_count : 20;
 
   static const u32 kTabSizeLog = SANITIZER_ANDROID ? 16 : 20;
   static const u32 kUseCountBits = 20;
   static const u32 kMaxUseCount = 1 << kUseCountBits;
   static const u32 kUseCountMask = (1 << kUseCountBits) - 1;
 
   typedef StackTrace args_type;
void store(const args_type &args, hash_type hash) {
     atomic_store(&tag_and_use_count, args.tag << kUseCountBits,
                  memory_order_relaxed);
     stack_hash = hash;
     stack_trace = traceAllocator.alloc(args.size + 1);
     *stack_trace = args.size;
     internal_memcpy(stack_trace + 1, args.trace, args.size * sizeof(uptr));
   }
   args_type load() const {
+    if (!stack_trace)
+      return {};
     u32 tag =
         atomic_load(&tag_and_use_count, memory_order_relaxed) >> kUseCountBits;
     return args_type(stack_trace + 1, *stack_trace, tag);
   }
-  StackDepotHandle get_handle() { return StackDepotHandle(this); }
+  static StackDepotHandle get_handle(u32 id);
 
   typedef StackDepotHandle handle_type;
 };
 
 COMPILER_CHECK(StackDepotNode::kMaxUseCount >= (u32)kStackDepotMaxUseCount);
 
-u32 StackDepotHandle::id() const { return node_->id; }
 int StackDepotHandle::use_count() const {
   return atomic_load(&node_->tag_and_use_count, memory_order_relaxed) &
          StackDepotNode::kUseCountMask;
 }
 void StackDepotHandle::inc_use_count_unsafe() {
   u32 prev =
       atomic_fetch_add(&node_->tag_and_use_count, 1, memory_order_relaxed) &
       StackDepotNode::kUseCountMask;
   CHECK_LT(prev + 1, StackDepotNode::kMaxUseCount);
 }
 
 // FIXME(dvyukov): this single reserved bit is used in TSan.
 typedef StackDepotBase<StackDepotNode, 1, StackDepotNode::kTabSizeLog>
     StackDepot;
 static StackDepot theDepot;
 
 StackDepotStats StackDepotGetStats() { return theDepot.GetStats(); }
 
-u32 StackDepotPut(StackTrace stack) {
-  StackDepotHandle h = theDepot.Put(stack);
-  return h.valid() ? h.id() : 0;
-}
+u32 StackDepotPut(StackTrace stack) { return theDepot.Put(stack); }
 
 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack) {
-  return theDepot.Put(stack);
+  return StackDepotNode::get_handle(theDepot.Put(stack));
 }
 
 StackTrace StackDepotGet(u32 id) {
   return theDepot.Get(id);
 }
 
 void StackDepotLockAll() {
   theDepot.LockAll();
 }
 
 void StackDepotUnlockAll() {
   theDepot.UnlockAll();
 }
 
 void StackDepotPrintAll() {
 #if !SANITIZER_GO
   theDepot.PrintAll();
 #endif
 }
 
+StackDepotHandle StackDepotNode::get_handle(u32 id) {
+  return StackDepotHandle(&theDepot.nodes[id], id);
+}
+
 bool StackDepotReverseMap::IdDescPair::IdComparator(
     const StackDepotReverseMap::IdDescPair &a,
     const StackDepotReverseMap::IdDescPair &b) {
   return a.id < b.id;
 }
 
 void StackDepotReverseMap::Init() const {
   if (LIKELY(map_.capacity()))
     return;
   map_.reserve(StackDepotGetStats().n_uniq_ids + 100);
   for (int idx = 0; idx < StackDepot::kTabSize; idx++) {
-    atomic_uintptr_t *p = &theDepot.tab[idx];
-    uptr v = atomic_load(p, memory_order_consume);
-    StackDepotNode *s = (StackDepotNode*)(v & ~1);
-    for (; s; s = s->link) {
-      IdDescPair pair = {s->id, s};
+    u32 s = atomic_load(&theDepot.tab[idx], memory_order_consume) &
+            StackDepot::kUnlockMask;
+    for (; s;) {
+      const StackDepotNode &node = theDepot.nodes[s];
+      IdDescPair pair = {s, &node};
       map_.push_back(pair);
+      s = node.link;
     }
   }
   Sort(map_.data(), map_.size(), &IdDescPair::IdComparator);
 }
 
 StackTrace StackDepotReverseMap::Get(u32 id) const {
   Init();
   if (!map_.size())

compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

 #include "sanitizer_flat_map.h"
 #include "sanitizer_internal_defs.h"
 #include "sanitizer_mutex.h"
 
 namespace __sanitizer {
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 class StackDepotBase {
-  static constexpr u32 kIdSizeLog = sizeof(u32) * 8 - kReservedBits;
+  static constexpr u32 kIdSizeLog =
+      sizeof(u32) * 8 - Max(kReservedBits, 1 /* At least 1 bit for locking. */);
   static constexpr u32 kNodesSize1Log = kIdSizeLog / 2;
   static constexpr u32 kNodesSize2Log = kIdSizeLog - kNodesSize1Log;
   static constexpr int kTabSize = 1 << kTabSizeLog;  // Hash table size.
+  static constexpr u32 kUnlockMask = (1ull << kIdSizeLog) - 1;
+  static constexpr u32 kLockMask = ~kUnlockMask;
 
  public:
   typedef typename Node::args_type args_type;
   typedef typename Node::handle_type handle_type;
   typedef typename Node::hash_type hash_type;
 
   static constexpr u64 kNodesSize1 = 1ull << kNodesSize1Log;
   static constexpr u64 kNodesSize2 = 1ull << kNodesSize2Log;
 
   // Maps stack trace to an unique id.
-  handle_type Put(args_type args, bool *inserted = nullptr);
+  u32 Put(args_type args, bool *inserted = nullptr);
   // Retrieves a stored stack trace by the id.
   args_type Get(u32 id);
 
   StackDepotStats GetStats() const {
     return {
         atomic_load_relaxed(&n_uniq_ids),
         nodes.MemoryUsage() + Node::allocated(),
     };
   }
 
   void LockAll();
   void UnlockAll();
   void PrintAll();
 
  private:
-  static Node *find(Node *s, args_type args, hash_type hash);
-  static Node *lock(atomic_uintptr_t *p);
-  static void unlock(atomic_uintptr_t *p, Node *s);
-
-  atomic_uintptr_t tab[kTabSize];  // Hash table of Node's.
+  friend Node;
+  friend class StackDepotReverseMap;
+  u32 find(u32 s, args_type args, hash_type hash) const;
+  static u32 lock(atomic_uint32_t *p);
+  static void unlock(atomic_uint32_t *p, u32 s);
+  atomic_uint32_t tab[kTabSize];  // Hash table of Node's.
 
   atomic_uint32_t n_uniq_ids;
 
   TwoLevelMap<Node, kNodesSize1, kNodesSize2> nodes;
 
   friend class StackDepotReverseMap;
 };
 
 template <class Node, int kReservedBits, int kTabSizeLog>
-Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(Node *s,
-                                                             args_type args,
-                                                             hash_type hash) {
+u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::find(
+    u32 s, args_type args, hash_type hash) const {
   // Searches linked list s for the stack, returns its id.
-  for (; s; s = s->link) {
-    if (s->eq(hash, args)) {
+  for (; s;) {
+    const Node &node = nodes[s];
+    if (node.eq(hash, args))
       return s;
-    }
-  }
-  return nullptr;
+    s = node.link;
+  return 0;
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
-Node *StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock(
-    atomic_uintptr_t *p) {
+u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::lock(atomic_uint32_t *p) {
   // Uses the pointer lsb as mutex.
   for (int i = 0;; i++) {
-    uptr cmp = atomic_load(p, memory_order_relaxed);
-    if ((cmp & 1) == 0 &&
-        atomic_compare_exchange_weak(p, &cmp, cmp | 1, memory_order_acquire))
-      return (Node *)cmp;
+    u32 cmp = atomic_load(p, memory_order_relaxed);
+    if ((cmp & kLockMask) == 0 &&
+        atomic_compare_exchange_weak(p, &cmp, cmp | kLockMask,
+                                     memory_order_acquire))
+      return cmp;
     if (i < 10)
       proc_yield(10);
     else
       internal_sched_yield();
   }
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::unlock(
-    atomic_uintptr_t *p, Node *s) {
-  DCHECK_EQ((uptr)s & 1, 0);
-  atomic_store(p, (uptr)s, memory_order_release);
+    atomic_uint32_t *p, u32 s) {
+  DCHECK_EQ(s & kLockMask, 0);
+  atomic_store(p, s, memory_order_release);
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
-typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::handle_type
-StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
+u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,
                                                           bool *inserted) {
   if (inserted)
     *inserted = false;
   if (!LIKELY(Node::is_valid(args)))
-    return handle_type();
+    return 0;
   hash_type h = Node::hash(args);
-  atomic_uintptr_t *p = &tab[h % kTabSize];
-  uptr v = atomic_load(p, memory_order_consume);
-  Node *s = (Node *)(v & ~uptr(1));
+  atomic_uint32_t *p = &tab[h % kTabSize];
+  u32 v = atomic_load(p, memory_order_consume);
+  u32 s = v & kUnlockMask;
   // First, try to find the existing stack.
-  Node *node = find(s, args, h);
+  u32 node = find(s, args, h);
   if (LIKELY(node))
-    return node->get_handle();
+    return node;
+
   // If failed, lock, retry and insert new.
-  Node *s2 = lock(p);
+  u32 s2 = lock(p);
   if (s2 != s) {
     node = find(s2, args, h);
     if (node) {
       unlock(p, s2);
-      return node->get_handle();
+      return node;
     }
   }
-  u32 id = atomic_fetch_add(&n_uniq_ids, 1, memory_order_relaxed) + 1;
-  CHECK_NE(id, 0);
-  CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
-  s = &nodes[id];
-  s->id = id;
-  s->store(args, h);
-  s->link = s2;
+  s = atomic_fetch_add(&n_uniq_ids, 1, memory_order_relaxed) + 1;
+  CHECK_EQ(s & kUnlockMask, s);
+  CHECK_EQ(s & (((u32)-1) >> kReservedBits), s);
+  Node &new_node = nodes[s];
+  new_node.store(args, h);
+  new_node.link = s2;
   unlock(p, s);
   if (inserted) *inserted = true;
-  return s->get_handle();
+  return s;
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 typename StackDepotBase<Node, kReservedBits, kTabSizeLog>::args_type
 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Get(u32 id) {
   if (id == 0)
     return args_type();
   CHECK_EQ(id & (((u32)-1) >> kReservedBits), id);
   if (!nodes.contains(id))
     return args_type();
   const Node &node = nodes[id];
-  if (node.id != id)
-    return args_type();
   return node.load();
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::LockAll() {
   for (int i = 0; i < kTabSize; ++i) {
     lock(&tab[i]);
   }
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::UnlockAll() {
   for (int i = 0; i < kTabSize; ++i) {
-    atomic_uintptr_t *p = &tab[i];
+    atomic_uint32_t *p = &tab[i];
     uptr s = atomic_load(p, memory_order_relaxed);
-    unlock(p, (Node *)(s & ~uptr(1)));
+    unlock(p, s & kUnlockMask);
   }
 }
 
 template <class Node, int kReservedBits, int kTabSizeLog>
 void StackDepotBase<Node, kReservedBits, kTabSizeLog>::PrintAll() {
   for (int i = 0; i < kTabSize; ++i) {
-    atomic_uintptr_t *p = &tab[i];
-    uptr v = atomic_load(p, memory_order_consume);
-    Node *s = (Node *)(v & ~uptr(1));
-    for (; s; s = s->link) {
-      Printf("Stack for id %u:\n", s->id);
-      s->load().Print();
+    atomic_uint32_t *p = &tab[i];
+    u32 s = atomic_load(p, memory_order_consume) & kUnlockMask;
+    for (; s;) {
+      const Node &node = nodes[s];
+      Printf("Stack for id %u:\n", s);
+      node.load().Print();
+      s = node.link;
     }
   }
 }
 
 } // namespace __sanitizer
 
 #endif // SANITIZER_STACKDEPOTBASE_H