[sanitizer] Remove StackDepotReverseMap

[vitalybuka]

Summary

Now StackDepotGet can retrive the stack in O(1).

Depends on D111612.

[vitalybuka]

rebase

compiler-rt/lib/lsan/lsan_common.h

public:
   LeakReport() {}
   void AddLeakedChunk(uptr chunk, u32 stack_trace_id, uptr leaked_size,
                       ChunkTag tag);
   void ReportTopLeaks(uptr max_leaks);
   void PrintSummary();
   uptr ApplySuppressions();
   uptr UnsuppressedLeakCount();
   uptr IndirectUnsuppressedLeakCount();
-  const StackDepotReverseMap &stack_depot() { return stack_depot_; }
 
  private:
   void PrintReportForLeak(uptr index);
   void PrintLeakedObjectsForLeak(uptr index);
 
   u32 next_id_ = 0;
-  StackDepotReverseMap stack_depot_;
   InternalMmapVector<Leak> leaks_;
   InternalMmapVector<LeakedObject> leaked_objects_;
 };
 
 typedef InternalMmapVector<uptr> Frontier;
 
 // Platform-specific functions.
 void InitializePlatformSpecificModules();

compiler-rt/lib/lsan/lsan_common.cpp

static uptr GetCallerPC(const StackTrace &stack) {
   // The top frame is our malloc/calloc/etc. The next frame is the caller.
   if (stack.size >= 2)
     return stack.trace[1];
   return 0;
 }
 
 struct InvalidPCParam {
   Frontier *frontier;
-  const StackDepotReverseMap *stack_depot;
   bool skip_linker_allocations;
 };
 
 // ForEachChunk callback. If the caller pc is invalid or is within the linker,
 // mark as reachable. Called by ProcessPlatformSpecificAllocations.
 static void MarkInvalidPCCb(uptr chunk, void *arg) {
   CHECK(arg);
   InvalidPCParam *param = reinterpret_cast<InvalidPCParam *>(arg);
   chunk = GetUserBegin(chunk);
   LsanMetadata m(chunk);
   if (m.allocated() && m.tag() != kReachable && m.tag() != kIgnored) {
     u32 stack_id = m.stack_trace_id();
     uptr caller_pc = 0;
     if (stack_id > 0)
-      caller_pc = GetCallerPC(param->stack_depot->Get(stack_id));
+      caller_pc = GetCallerPC(StackDepotGet(stack_id));
     // If caller_pc is unknown, this chunk may be allocated in a coroutine. Mark
     // it as reachable, as we can't properly report its allocation stack anyway.
     if (caller_pc == 0 || (param->skip_linker_allocations &&
                            GetLinker()->containsAddress(caller_pc))) {
       m.set_tag(kReachable);
       param->frontier->push_back(chunk);
     }
   }

 // mechanism kicks in, and thus we don't recognize it as allocated memory. We
 // can't special-case it either, since we don't know its size.
 // Our solution is to include in the root set all allocations made from
 // ld-linux.so (which is where allocate_and_init() is implemented). This is
 // guaranteed to include all dynamic TLS blocks (and possibly other allocations
 // which we don't care about).
 // On all other platforms, this simply checks to ensure that the caller pc is
 // valid before reporting chunks as leaked.
-static void ProcessPC(Frontier *frontier,
-                      const StackDepotReverseMap &stack_depot) {
+static void ProcessPC(Frontier *frontier) {
   InvalidPCParam arg;
   arg.frontier = frontier;
-  arg.stack_depot = &stack_depot;
   arg.skip_linker_allocations =
       flags()->use_tls && flags()->use_ld_allocations && GetLinker() != nullptr;
   ForEachChunk(MarkInvalidPCCb, &arg);
 }
 
 // Sets the appropriate tag on each chunk.
 static void ClassifyAllChunks(SuspendedThreadsList const &suspended_threads,
-                              const StackDepotReverseMap &stack_depot,
                               Frontier *frontier) {
   const InternalMmapVector<u32> &suppressed_stacks =
       GetSuppressionContext()->GetSortedSuppressedStacks();
   if (!suppressed_stacks.empty()) {
     ForEachChunk(IgnoredSuppressedCb,
                  const_cast<InternalMmapVector<u32> *>(&suppressed_stacks));
   }
   ForEachChunk(CollectIgnoredCb, frontier);
   ProcessGlobalRegions(frontier);
   ProcessThreads(suspended_threads, frontier);
   ProcessRootRegions(frontier);
   FloodFillTag(frontier, kReachable);
 
   CHECK_EQ(0, frontier->size());
-  ProcessPC(frontier, stack_depot);
+  ProcessPC(frontier);
 
   // The check here is relatively expensive, so we do this in a separate flood
   // fill. That way we can skip the check for chunks that are reachable
   // otherwise.
   LOG_POINTERS("Processing platform-specific allocations.\n");
   ProcessPlatformSpecificAllocations(frontier);
   FloodFillTag(frontier, kReachable);
 

 #endif  // !SANITIZER_FUCHSIA
 
 static void CheckForLeaksCallback(const SuspendedThreadsList &suspended_threads,
                                   void *arg) {
   CheckForLeaksParam *param = reinterpret_cast<CheckForLeaksParam *>(arg);
   CHECK(param);
   CHECK(!param->success);
   ReportUnsuspendedThreads(suspended_threads);
-  ClassifyAllChunks(suspended_threads, param->leak_report.stack_depot(),
-                    &param->frontier);
+  ClassifyAllChunks(suspended_threads, &param->frontier);
   ForEachChunk(CollectLeaksCb, &param->leak_report);
   // Clean up for subsequent leak checks. This assumes we did not overwrite any
   // kIgnored tags.
   ForEachChunk(ResetTagsCb, nullptr);
   param->success = true;
 }
 
 static bool PrintResults(LeakReport &report) {

 // use a hash table.
 const uptr kMaxLeaksConsidered = 5000;
 
 void LeakReport::AddLeakedChunk(uptr chunk, u32 stack_trace_id,
                                 uptr leaked_size, ChunkTag tag) {
   CHECK(tag == kDirectlyLeaked || tag == kIndirectlyLeaked);
 
   if (u32 resolution = flags()->resolution) {
-    StackTrace stack = stack_depot_.Get(stack_trace_id);
+    StackTrace stack = StackDepotGet(stack_trace_id);
     stack.size = Min(stack.size, resolution);
     stack_trace_id = StackDepotPut(stack);
   }
 
   bool is_directly_leaked = (tag == kDirectlyLeaked);
   uptr i;
   for (i = 0; i < leaks_.size(); i++) {
     if (leaks_[i].stack_trace_id == stack_trace_id &&
void LeakReport::PrintReportForLeak(uptr index) {
   Decorator d;
   Printf("%s", d.Leak());
   Printf("%s leak of %zu byte(s) in %zu object(s) allocated from:\n",
          leaks_[index].is_directly_leaked ? "Direct" : "Indirect",
          leaks_[index].total_size, leaks_[index].hit_count);
   Printf("%s", d.Default());
 
   CHECK(leaks_[index].stack_trace_id);
-  stack_depot_.Get(leaks_[index].stack_trace_id).Print();
+  StackDepotGet(leaks_[index].stack_trace_id).Print();
 
   if (flags()->report_objects) {
     Printf("Objects leaked above:\n");
     PrintLeakedObjectsForLeak(index);
     Printf("\n");
   }
 }
 
void LeakReport::PrintSummary() {
   ReportErrorSummary(summary.data());
 }
 
 uptr LeakReport::ApplySuppressions() {
   LeakSuppressionContext *suppressions = GetSuppressionContext();
   uptr new_suppressions = false;
   for (uptr i = 0; i < leaks_.size(); i++) {
     Suppression *s = suppressions->GetSuppressionForStack(
-        leaks_[i].stack_trace_id, stack_depot_.Get(leaks_[i].stack_trace_id));
+        leaks_[i].stack_trace_id, StackDepotGet(leaks_[i].stack_trace_id));
     if (s) {
       s->weight += leaks_[i].total_size;
       atomic_store_relaxed(&s->hit_count, atomic_load_relaxed(&s->hit_count) +
           leaks_[i].hit_count);
       leaks_[i].is_suppressed = true;
       ++new_suppressions;
     }
   }

compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.h

 StackDepotHandle StackDepotPut_WithHandle(StackTrace stack);
 // Retrieves a stored stack trace by the id.
 StackTrace StackDepotGet(u32 id);
 
 void StackDepotLockAll();
 void StackDepotUnlockAll();
 void StackDepotPrintAll();
 
-// Instantiating this class creates a snapshot of StackDepot which can be
-// efficiently queried with StackDepotGet(). You can use it concurrently with
-// StackDepot, but the snapshot is only guaranteed to contain those stack traces
-// which were stored before it was instantiated.
-class StackDepotReverseMap {
- public:
-  StackDepotReverseMap() = default;
-  StackTrace Get(u32 id) const;
-
- private:
-  struct IdDescPair {
-    u32 id;
-    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

#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++) {
-    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())
-    return StackTrace();
-  IdDescPair pair = {id, nullptr};
-  uptr idx = InternalLowerBound(map_, pair, IdDescPair::IdComparator);
-  if (idx > map_.size() || map_[idx].id != id)
-    return StackTrace();
-  return map_[idx].desc->load();
-}
-
 } // namespace __sanitizer

compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

public:
   }
 
   void LockAll();
   void UnlockAll();
   void PrintAll();
 
  private:
   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;

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

TEST(SanitizerCommon, StackDepotPrintNoLock) {
   StackDepotPrintAll();
   for (u32 i = 0; i < n; ++i) {
     uptr array[] = {0x111, 0x222, i, 0x444, 0x777};
     StackTrace s(array, ARRAY_SIZE(array));
     CHECK_EQ(idx2id[i], StackDepotPut(s));
   }
 }
 
-TEST(SanitizerCommon, StackDepotReverseMap) {
-  uptr array1[] = {1, 2, 3, 4, 5};
-  uptr array2[] = {7, 1, 3, 0};
-  uptr array3[] = {10, 2, 5, 3};
-  uptr array4[] = {1, 3, 2, 5};
-  u32 ids[4] = {0};
-  StackTrace s1(array1, ARRAY_SIZE(array1));
-  StackTrace s2(array2, ARRAY_SIZE(array2));
-  StackTrace s3(array3, ARRAY_SIZE(array3));
-  StackTrace s4(array4, ARRAY_SIZE(array4));
-  ids[0] = StackDepotPut(s1);
-  ids[1] = StackDepotPut(s2);
-  ids[2] = StackDepotPut(s3);
-  ids[3] = StackDepotPut(s4);
-
-  StackDepotReverseMap map;
-
-  for (uptr i = 0; i < 4; i++) {
-    StackTrace stack = StackDepotGet(ids[i]);
-    StackTrace from_map = map.Get(ids[i]);
-    EXPECT_EQ(stack.size, from_map.size);
-    EXPECT_EQ(stack.trace, from_map.trace);
-  }
-}
-
 }  // namespace __sanitizer