[NFC][lsan] Use hash table to track root regions

[vitalybuka]

Summary

This avoid O(N) in __lsan_unregister_root_region.

[MaskRay]

This avoid O(N^2) in __lsan_unregister_root_region.

O(N) ?

Is there a pessimistic case where size(root_regions) is in the scale of 1000+ ?

[vitalybuka]

In D151784#4384412, @MaskRay wrote:

This avoid O(N^2) in __lsan_unregister_root_region.

O(N) ?

Yes. N^2 is for entire app

Is there a pessimistic case where size(root_regions) is in the scale of 1000+ ?

Yes, it should make a difference of 1000+ but I don't know such examples. But it should be possible.
I was debugging perf regression and suspected this place.
But the real reason was request calls MemoryMappingLayout which is already fixed.

[MaskRay]

Thanks!

compiler-rt/lib/lsan/lsan_common.cpp

524–536

Add a space after using RootRegions.

Add a comment like // A map that contains (region, count) pairs. Regions are non-overlapping.

528

We can just use alignas instead of ALIGNED.

Actually, static RootRegions *regions = new RootRegions();. The function-local static variable is constructed when executed for the first time.

#include <assert.h>
#include <stdio.h>

struct A {
  A() { puts("a"); }
  ~A() { assert(0); }
};

static A& foo() {
  puts("foo");
  static A *a = new A;
  return *a;
}

int main() {
  puts("main");
  foo();
  foo();
}

[MaskRay]

compiler-rt/lib/lsan/lsan_common.cpp

524–536

Sorry, I mean add a blank line after using RootRegions

[vitalybuka]

update

[vitalybuka]

compiler-rt/lib/lsan/lsan_common.cpp

524–536

Add a space after using RootRegions.

Add a comment like // A map that contains (region, count) pairs. Regions are non-overlapping.

when in practice they should not be overlapping, we didn't enforce that before, I don't see good reason to enforce now.
this is one of reasons I use that algorithm

528

we don't have cxa_guard for static
BTW, maybe you have ideas how to easily get this without linking libc++

compiler-rt/lib/lsan/lsan_common.cpp

bool LeakSuppressionContext::Suppress(u32 stack_trace_id, uptr hit_count,
   return true;
 }
 
 static LeakSuppressionContext *GetSuppressionContext() {
   CHECK(suppression_ctx);
   return suppression_ctx;
 }
 
-static InternalMmapVectorNoCtor<Region> root_regions;
-
 void InitCommonLsan() {
   if (common_flags()->detect_leaks) {
     // Initialization which can fail or print warnings should only be done if
     // LSan is actually enabled.
     InitializeSuppressions();
     InitializePlatformSpecificModules();
   }
 }
#    endif
   }
 
   // Add pointers reachable from ThreadContexts
   ProcessThreadRegistry(frontier);
 }
 
 #  endif  // SANITIZER_FUCHSIA
 
-bool HasRootRegions() { return !root_regions.empty(); }
+// A map that contains [region_begin, region_end) pairs.
+using RootRegions = DenseMap<detail::DenseMapPair<uptr, uptr>, uptr>;
+
+static RootRegions &GetRootRegionsLocked() {
+  global_mutex.CheckLocked();
+  static RootRegions *regions = nullptr;
+  alignas(RootRegions) static char placeholder[sizeof(RootRegions)];
+  if (!regions)
+    regions = new (placeholder) RootRegions();
+  return *regions;
+}
+
+bool HasRootRegions() { return !GetRootRegionsLocked().empty(); }
 
 void ScanRootRegions(Frontier *frontier,
                      const InternalMmapVectorNoCtor<Region> &mapped_regions) {
   if (!flags()->use_root_regions)
     return;
 
+  InternalMmapVector<Region> regions;
+  GetRootRegionsLocked().forEach([&](const auto &kv) {
+    regions.push_back({kv.first.first, kv.first.second});
+    return true;
+  });
+
   InternalMmapVector<Region> intersection;
-  Intersect(mapped_regions, root_regions, intersection);
+  Intersect(mapped_regions, regions, intersection);
 
   for (const Region &r : intersection) {
     LOG_POINTERS("Root region intersects with mapped region at %p-%p\n",
                  (void *)r.begin, (void *)r.end);
     ScanRangeForPointers(r.begin, r.end, frontier, "ROOT", kReachable);
   }
 }
 

 void __lsan_register_root_region(const void *begin, uptr size) {
 #if CAN_SANITIZE_LEAKS
   VReport(1, "Registered root region at %p of size %zu\n", begin, size);
   uptr b = reinterpret_cast<uptr>(begin);
   uptr e = b + size;
   CHECK_LT(b, e);
 
   Lock l(&global_mutex);
-  root_regions.push_back({b, e});
+  ++GetRootRegionsLocked()[{b, e}];
 #endif  // CAN_SANITIZE_LEAKS
 }
 
 SANITIZER_INTERFACE_ATTRIBUTE
 void __lsan_unregister_root_region(const void *begin, uptr size) {
 #if CAN_SANITIZE_LEAKS
   uptr b = reinterpret_cast<uptr>(begin);
   uptr e = b + size;
   CHECK_LT(b, e);
+  VReport(1, "Unregistered root region at %p of size %zu\n", begin, size);
 
   {
     Lock l(&global_mutex);
-    for (uptr i = 0; i < root_regions.size(); i++) {
-      Region region = root_regions[i];
-      if (region.begin == b && region.end == e) {
-        uptr last_index = root_regions.size() - 1;
-        root_regions[i] = root_regions[last_index];
-        root_regions.pop_back();
-        VReport(1, "Unregistered root region at %p of size %zu\n", begin, size);
-        return;
-      }
-    }
-  }
+    if (auto *f = GetRootRegionsLocked().find({b, e})) {
+      if (--(f->second) == 0)
+        GetRootRegionsLocked().erase(f);
   Report(
       "__lsan_unregister_root_region(): region at %p of size %zu has not "
       "been registered.\n",
       begin, size);
   Die();
 #endif  // CAN_SANITIZE_LEAKS
 }