[sanitizer] Calculate Range sets intersection

[vitalybuka]

Summary

Will be used to handle Root Regions in LSAN D151781.

[MaskRay]

compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp

52 ↗

(On Diff #526910)

Perhaps DCHECK_GE

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp

52 ↗

(On Diff #526910)

lgtm, seems too obvious to be true

[vitalybuka]

DCHECK

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp

52 ↗

(On Diff #526910)

lgtm, seems too obvious to be true

I tried to say "will do" :)

[MaskRay]

compiler-rt/lib/sanitizer_common/sanitizer_common_region.cpp

9 ↗

(On Diff #527271)

This comment is different from sanitizer_common_region.h. Does this file need a comment when the header has one?

20 ↗

(On Diff #527271)

if (a.empty() || b.empty()) can be removed as the generic algorithm can handle the cases.

compiler-rt/lib/sanitizer_common/sanitizer_common_region.h

9 ↗

(On Diff #527271)

For now, this comment can state that this file computes the intersection between two arrays of ranges.

20 ↗

(On Diff #527271)

Using Region to represent a range is fine in lsan, but the term may be confusing in sanitizer_common.

Range or Interval may be better.

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

40 ↗

(On Diff #527271)

static?

const Region& => const Region &

std::ostream* => std::ostream *

[MaskRay]

Better to state in the summary that this file is going to be used by lsan.

[vitalybuka]

update

[vitalybuka]

updates

[MaskRay]

Will be used to handle Root Regions in LSAN.

Since you already have the lsan patch, you can attach its Dxxxx number in the commit message :)

[vitalybuka]

In D151779#4388497, @MaskRay wrote:

Will be used to handle Root Regions in LSAN.

Since you already have the lsan patch, you can attach its Dxxxx number in the commit message :)

Done. Usually I think "stack" is enough to track dependecies.

[MaskRay]

In D151779#4388504, @vitalybuka wrote:

In D151779#4388497, @MaskRay wrote:

Will be used to handle Root Regions in LSAN.

Since you already have the lsan patch, you can attach its Dxxxx number in the commit message :)

Done. Usually I think "stack" is enough to track dependecies.

Yes, "stack" is enough for people who visit Phabricator. Dxxxx will be helpful for people who just read commit messages:)

compiler-rt/lib/sanitizer_common/CMakeLists.txt

 # Build system for the common Sanitizer runtime support library components.
 # These components are shared between AddressSanitizer and ThreadSanitizer.
 
 set(SANITIZER_SOURCES_NOTERMINATION
   sanitizer_allocator.cpp
+  sanitizer_common_range.cpp
   sanitizer_common.cpp
   sanitizer_deadlock_detector1.cpp
   sanitizer_deadlock_detector2.cpp
   sanitizer_errno.cpp
   sanitizer_file.cpp
   sanitizer_flags.cpp
   sanitizer_flag_parser.cpp
   sanitizer_fuchsia.cpp

compiler-rt/lib/sanitizer_common/sanitizer_common_range.h

+//===-- sanitizer_common_range.h --------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Contais Range and related utilities.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_COMMON_REGION_H
+#define SANITIZER_COMMON_REGION_H
+
+#include "sanitizer_common.h"
+
+namespace __sanitizer {
+
+struct Range {
+  uptr begin;
+  uptr end;
+};
+
+inline bool operator==(const Range &lhs, const Range &rhs) {
+  return lhs.begin == rhs.begin && lhs.end == rhs.end;
+}
+
+inline bool operator!=(const Range &lhs, const Range &rhs) {
+  return !(lhs == rhs);
+}
+
+// Calculates intersection of two sets of regions in O(N log N) time.
+void Intersect(ArrayRef<Range> a, ArrayRef<Range> b,
+               InternalMmapVectorNoCtor<Range> &output);
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_COMMON_REGION_H

compiler-rt/lib/sanitizer_common/sanitizer_common_range.cpp

+//===-- sanitizer_common_range.cpp ----------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common_range.h"
+
+namespace __sanitizer {
+
+void Intersect(ArrayRef<Range> a, ArrayRef<Range> b,
+               InternalMmapVectorNoCtor<Range> &output) {
+  output.clear();
+
+  struct Event {
+    uptr val;
+    s8 diff1;
+    s8 diff2;
+  };
+
+  InternalMmapVector<Event> events;
+  for (const Range &r : a) {
+    CHECK_LE(r.begin, r.end);
+    events.push_back({r.begin, 1, 0});
+    events.push_back({r.end, -1, 0});
+  }
+
+  for (const Range &r : b) {
+    CHECK_LE(r.begin, r.end);
+    events.push_back({r.begin, 0, 1});
+    events.push_back({r.end, 0, -1});
+  }
+
+  Sort(events.data(), events.size(),
+       [](const Event &lh, const Event &rh) { return lh.val < rh.val; });
+
+  uptr start = 0;
+  sptr state1 = 0;
+  sptr state2 = 0;
+  for (const auto &e : events) {
+    if (e.val != start) {
+      DCHECK_GE(state1, 0);
+      DCHECK_GE(state2, 0);
+      if (state1 && state2) {
+        if (!output.empty() && start == output.back().end)
+          output.back().end = e.val;
+        else
+          output.push_back({start, e.val});
+      }
+      start = e.val;
+    }
+
+    state1 += e.diff1;
+    state2 += e.diff2;
+  }
+}
+
+}  // namespace __sanitizer

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

 
 set(SANITIZER_UNITTESTS
   sanitizer_addrhashmap_test.cpp
   sanitizer_allocator_test.cpp
   sanitizer_atomic_test.cpp
   sanitizer_bitvector_test.cpp
   sanitizer_bvgraph_test.cpp
   sanitizer_chained_origin_depot_test.cpp
+  sanitizer_common_range_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_dense_map_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_flat_map_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_hash_test.cpp
   sanitizer_ioctl_test.cpp

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

+//===-- sanitizer_common_region_test.cpp ----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer/AddressSanitizer runtime.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_common_range.h"
+
+#include <algorithm>
+
+#include "gtest/gtest.h"
+#include "sanitizer_common/sanitizer_common.h"
+
+namespace __sanitizer {
+
+class SanitizerCommon
+    : public testing::TestWithParam<std::tuple<
+          std::vector<Range>, std::vector<Range>, std::vector<Range>>> {};
+
+TEST_P(SanitizerCommon, Intersect) {
+  {
+    InternalMmapVector<Range> output;
+    Intersect(std::get<0>(GetParam()), std::get<1>(GetParam()), output);
+    EXPECT_EQ(std::get<2>(GetParam()),
+              std::vector<Range>(output.begin(), output.end()));
+  }
+  {
+    InternalMmapVector<Range> output;
+    Intersect(std::get<1>(GetParam()), std::get<0>(GetParam()), output);
+    EXPECT_EQ(std::get<2>(GetParam()),
+              std::vector<Range>(output.begin(), output.end()));
+  }
+}
+
+static void PrintTo(const Range &r, std::ostream *os) {
+  *os << "[" << r.begin << ", " << r.end << ")";
+}
+
+static const std::tuple<std::vector<Range>, std::vector<Range>,
+                        std::vector<Range>>
+    kTests[] = {
+        {{}, {}, {}},
+        {{{100, 1000}}, {{5000, 10000}}, {}},
+        {{{100, 1000}, {200, 2000}}, {{5000, 10000}, {6000, 11000}}, {}},
+        {{{100, 1000}}, {{100, 1000}}, {{100, 1000}}},
+        {{{100, 1000}}, {{50, 150}}, {{100, 150}}},
+        {{{100, 1000}}, {{150, 250}}, {{150, 250}}},
+        {{{100, 1000}, {100, 1000}}, {{100, 1000}}, {{100, 1000}}},
+        {{{100, 1000}}, {{500, 1500}}, {{500, 1000}}},
+        {{{100, 200}}, {{200, 300}, {1, 1000}}, {{100, 200}}},
+        {{{100, 200}, {200, 300}}, {{100, 300}}, {{100, 300}}},
+        {{{100, 200}, {200, 300}, {300, 400}}, {{150, 350}}, {{150, 350}}},
+        {{{100, 200}, {300, 400}, {500, 600}},
+         {{0, 1000}},
+         {{100, 200}, {300, 400}, {500, 600}}},
+};
+
+INSTANTIATE_TEST_SUITE_P(SanitizerCommonEmpty, SanitizerCommon,
+                         testing::ValuesIn(kTests));
+
+}  // namespace __sanitizer