diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp b/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp --- a/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp +++ b/compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp @@ -24,8 +24,7 @@ struct ChainedOriginDepotNode { using hash_type = u32; - ChainedOriginDepotNode *link; - u32 id; + u32 link; u32 here_id; u32 prev_id; @@ -44,16 +43,16 @@ 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; }; @@ -118,8 +117,8 @@ 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() {} @@ -131,8 +130,7 @@ 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; } diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.h b/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.h --- a/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.h @@ -22,11 +22,11 @@ // 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(); }; @@ -55,7 +55,7 @@ private: struct IdDescPair { u32 id; - StackDepotNode *desc; + const StackDepotNode *desc; static bool IdComparator(const IdDescPair &a, const IdDescPair &b); }; diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp b/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp --- a/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp +++ b/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp @@ -24,9 +24,8 @@ 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; @@ -58,18 +57,19 @@ 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; @@ -88,13 +88,10 @@ 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) { @@ -115,6 +112,10 @@ #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) { @@ -126,12 +127,13 @@ 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); diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h b/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h --- a/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h @@ -24,10 +24,13 @@ template 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; @@ -38,7 +41,7 @@ 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); @@ -54,11 +57,12 @@ 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; @@ -68,27 +72,27 @@ }; template -Node *StackDepotBase::find(Node *s, - args_type args, - hash_type hash) { +u32 StackDepotBase::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; - } + s = node.link; } - return nullptr; + return 0; } template -Node *StackDepotBase::lock( - atomic_uintptr_t *p) { +u32 StackDepotBase::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 @@ -98,46 +102,45 @@ template void StackDepotBase::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 -typename StackDepotBase::handle_type -StackDepotBase::Put(args_type args, - bool *inserted) { +u32 StackDepotBase::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 @@ -149,8 +152,6 @@ if (!nodes.contains(id)) return args_type(); const Node &node = nodes[id]; - if (node.id != id) - return args_type(); return node.load(); } @@ -164,21 +165,22 @@ template void StackDepotBase::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 void StackDepotBase::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; } } }