[NFC][lsan] Avoid O(N^2) algorithm

[vitalybuka]

Summary

Usually root_regions size is small so unlikey
this change will provide a noticable difference.

However it's easy to make sure that even with
large number of root_regions it works reasonably
fast.

[MaskRay]

D151779 added an interaction algorithm of two region lists using a scan line algorithm. The algorithm needs to maintain a sorted event array.

This problem has a property that the second region list (mapped_regions) is sorted and the first region list (root_regions) can be sorted in place.
I think we can open code a specialized version of the interaction algorithm just in lib/lsan, similar to merging two sorted list, with a space complexity of O(1).

[vitalybuka]

In D151781#4384399, @MaskRay wrote:

D151779 added an interaction algorithm of two region lists using a scan line algorithm. The algorithm needs to maintain a sorted event array.

This problem has a property that the second region list (mapped_regions) is sorted and the first region list (root_regions) can be sorted in place.
I think we can open code a specialized version of the interaction algorithm just in lib/lsan, similar to merging two sorted list, with a space complexity of O(1).

I don't realy concerned with space complexity here.
Seems like D151779 is simple, general and good enough to solve the proplem.

[MaskRay]

In D151781#4385143, @vitalybuka wrote:

In D151781#4384399, @MaskRay wrote:

D151779 added an interaction algorithm of two region lists using a scan line algorithm. The algorithm needs to maintain a sorted event array.

This problem has a property that the second region list (mapped_regions) is sorted and the first region list (root_regions) can be sorted in place.
I think we can open code a specialized version of the interaction algorithm just in lib/lsan, similar to merging two sorted list, with a space complexity of O(1).

I don't realy concerned with space complexity here.
Seems like D151779 is simple, general and good enough to solve the proplem.

Yes, it's simple enough, but a merge style algorithm for intersection will be simpler :)

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

vector<pair<int, int>> intersect(vector<pair<int, int>> &a, const vector<pair<int, int>> &b) {
  assert(is_sorted(a.begin(), a.end()));
  assert(is_sorted(b.begin(), b.end()));
  vector<pair<int, int>> ret;
  auto ia = a.begin();
  auto ib = b.begin();
  while (ia != a.end() && ib != b.end()) {
    // We don't merge [10,12) [12,14) into [10,14), but ScanRangeForPointers is happy with that.
    auto l = max(ia->first, ib->first);
    auto r = min(ia->second, ib->second);
    if (l < r)
      ret.emplace_back(l, r);
    if (ia->second < ib->second)
      ++ia;
    else
      ++ib;
  }
  return ret;
}

int main() {
  vector<pair<int, int>> a{{1,2}, {2,4}, {5,8}, {10,12}, {12,14}, {14, 16}};
  vector<pair<int, int>> b{{1,5}, {6,7}, {7,9}, {10,12}, {12,14}, {14, 16}};
  for (auto x : intersect(a, b))
    printf("[%d, %d)\n", x.first, x.second);
}

[vitalybuka]

In D151781#4385251, @MaskRay wrote:

In D151781#4385143, @vitalybuka wrote:

In D151781#4384399, @MaskRay wrote:

D151779 added an interaction algorithm of two region lists using a scan line algorithm. The algorithm needs to maintain a sorted event array.

This problem has a property that the second region list (mapped_regions) is sorted and the first region list (root_regions) can be sorted in place.
I think we can open code a specialized version of the interaction algorithm just in lib/lsan, similar to merging two sorted list, with a space complexity of O(1).

I don't realy concerned with space complexity here.
Seems like D151779 is simple, general and good enough to solve the proplem.

Yes, it's simple enough, but a merge style algorithm for intersection will be simpler :)

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

vector<pair<int, int>> intersect(vector<pair<int, int>> &a, const vector<pair<int, int>> &b) {
  assert(is_sorted(a.begin(), a.end()));
  assert(is_sorted(b.begin(), b.end()));
  vector<pair<int, int>> ret;
  auto ia = a.begin();
  auto ib = b.begin();
  while (ia != a.end() && ib != b.end()) {
    // We don't merge [10,12) [12,14) into [10,14), but ScanRangeForPointers is happy with that.

This is not general^, and unnecessary rely on user behavior.

  auto l = max(ia->first, ib->first);
  auto r = min(ia->second, ib->second);
  if (l < r)
    ret.emplace_back(l, r);
  if (ia->second < ib->second)
    ++ia;
  else
    ++ib;
}
return ret;

}

int main() {

vector<pair<int, int>> a{{1,2}, {2,4}, {5,8}, {10,12}, {12,14}, {14, 16}};
vector<pair<int, int>> b{{1,5}, {6,7}, {7,9}, {10,12}, {12,14}, {14, 16}};
for (auto x : intersect(a, b))
  printf("[%d, %d)\n", x.first, x.second);

}

It's not complicated, but it need some time to realize if this will handled overlapping regions in one of inputs (seems it will not).

also it's going to be annoying to templatize to support XOR or AND version if needed.

compiler-rt/lib/lsan/lsan_common.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LSAN_COMMON_H
 #define LSAN_COMMON_H
 
 #include "sanitizer_common/sanitizer_allocator.h"
 #include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_common_range.h"
 #include "sanitizer_common/sanitizer_internal_defs.h"
 #include "sanitizer_common/sanitizer_platform.h"
 #include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_stoptheworld.h"
 #include "sanitizer_common/sanitizer_symbolizer.h"
 #include "sanitizer_common/sanitizer_thread_registry.h"
 
 // LeakSanitizer relies on some Glibc's internals (e.g. TLS machinery) on Linux.

 };
 
 enum IgnoreObjectResult {
   kIgnoreObjectSuccess,
   kIgnoreObjectAlreadyIgnored,
   kIgnoreObjectInvalid
 };
 
-struct Range {
-  uptr begin;
-  uptr end;
-};
-
 //// --------------------------------------------------------------------------
 //// Poisoning prototypes.
 //// --------------------------------------------------------------------------
 
 // Returns true if [addr, addr + sizeof(void *)) is poisoned.
 bool WordIsPoisoned(uptr addr);
 
 //// --------------------------------------------------------------------------

 
 typedef InternalMmapVector<uptr> Frontier;
 
 // Platform-specific functions.
 void InitializePlatformSpecificModules();
 void ProcessGlobalRegions(Frontier *frontier);
 void ProcessPlatformSpecificAllocations(Frontier *frontier);
 
-struct Region {
-  uptr begin;
-  uptr end;
-};
-
 // LockStuffAndStopTheWorld can start to use Scan* calls to collect into
 // this Frontier vector before the StopTheWorldCallback actually runs.
 // This is used when the OS has a unified callback API for suspending
 // threads and enumerating roots.
 struct CheckForLeaksParam {
   Frontier frontier;
   LeakedChunks leaks;
   tid_t caller_tid;
   uptr caller_sp;
   bool success = false;
 };
 
+using Region = Range;
+
 bool HasRootRegions();
 void ScanRootRegions(Frontier *frontier,
                      const InternalMmapVectorNoCtor<Region> &region);
 // Run stoptheworld while holding any platform-specific locks, as well as the
 // allocator and thread registry locks.
 void LockStuffAndStopTheWorld(StopTheWorldCallback callback,
                               CheckForLeaksParam* argument);
 

compiler-rt/lib/lsan/lsan_common.cpp

#    endif
   // Add pointers reachable from ThreadContexts
   ProcessThreadRegistry(frontier);
 }
 
 #  endif  // SANITIZER_FUCHSIA
 
 bool HasRootRegions() { return !root_regions.empty(); }
 
-static void ScanRootRegion(Frontier *frontier, const Region &root_region,
-                           uptr region_begin, uptr region_end,
-                           bool is_readable) {
-  uptr intersection_begin = Max(root_region.begin, region_begin);
-  uptr intersection_end = Min(region_end, root_region.end);
-  if (intersection_begin >= intersection_end)
-    return;
-  LOG_POINTERS("Root region %p-%p intersects with mapped region %p-%p (%s)\n",
-               (void *)root_region.begin, (void *)root_region.end,
-               (void *)region_begin, (void *)region_end,
-               is_readable ? "readable" : "unreadable");
-  if (is_readable)
-    ScanRangeForPointers(intersection_begin, intersection_end, frontier, "ROOT",
-                         kReachable);
-}
-
 void ScanRootRegions(Frontier *frontier,
                      const InternalMmapVectorNoCtor<Region> &mapped_regions) {
-  if (!flags()->use_root_regions || mapped_regions.empty())
+  if (!flags()->use_root_regions)
     return;
 
-  for (const auto &m : mapped_regions)
-    for (const auto &r : root_regions)
-      ScanRootRegion(frontier, r, m.begin, m.end, true);
+  InternalMmapVector<Region> intersection;
+  Intersect(mapped_regions, root_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);
+  }
 }
 
 // Scans root regions for heap pointers.
 static void ProcessRootRegions(Frontier *frontier) {
   if (!flags()->use_root_regions || !HasRootRegions())
     return;
   MemoryMappingLayout proc_maps(/*cache_enabled*/ true);
   MemoryMappedSegment segment;