From 6b3ae49d3243b1387abafe686ae8ef99c01227ac Mon Sep 17 00:00:00 2001 From: Vitaly Buka Date: Tue, 30 May 2023 22:47:33 -0700 Subject: [PATCH] [sanitizer] Calculate Range sets intersection Will be used to handle Root Regions in LSAN D151781. Reviewed By: MaskRay Differential Revision: https://reviews.llvm.org/D151779 --- compiler-rt/lib/sanitizer_common/CMakeLists.txt | 1 + .../sanitizer_common/sanitizer_common_range.cpp | 60 ++++++++++++++++++++ .../lib/sanitizer_common/sanitizer_common_range.h | 39 +++++++++++++ .../lib/sanitizer_common/tests/CMakeLists.txt | 1 + .../tests/sanitizer_common_range_test.cpp | 66 ++++++++++++++++++++++ 5 files changed, 167 insertions(+) create mode 100644 compiler-rt/lib/sanitizer_common/sanitizer_common_range.cpp create mode 100644 compiler-rt/lib/sanitizer_common/sanitizer_common_range.h create mode 100644 compiler-rt/lib/sanitizer_common/tests/sanitizer_common_range_test.cpp diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt index c4fdc7a..d4187a9 100644 --- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt @@ -3,6 +3,7 @@ set(SANITIZER_SOURCES_NOTERMINATION sanitizer_allocator.cpp + sanitizer_common_range.cpp sanitizer_common.cpp sanitizer_deadlock_detector1.cpp sanitizer_deadlock_detector2.cpp diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_range.cpp b/compiler-rt/lib/sanitizer_common/sanitizer_common_range.cpp new file mode 100644 index 0000000..fcdb928 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_range.cpp @@ -0,0 +1,60 @@ +//===-- 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 a, ArrayRef b, + InternalMmapVectorNoCtor &output) { + output.clear(); + + struct Event { + uptr val; + s8 diff1; + s8 diff2; + }; + + InternalMmapVector 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 diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_range.h b/compiler-rt/lib/sanitizer_common/sanitizer_common_range.h new file mode 100644 index 0000000..76e3d04 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_range.h @@ -0,0 +1,39 @@ +//===-- 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 a, ArrayRef b, + InternalMmapVectorNoCtor &output); + +} // namespace __sanitizer + +#endif // SANITIZER_COMMON_REGION_H diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt index 40aa8e7..4924a9e 100644 --- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt @@ -16,6 +16,7 @@ set(SANITIZER_UNITTESTS 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 diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_range_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_range_test.cpp new file mode 100644 index 0000000..2a2e1de --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_range_test.cpp @@ -0,0 +1,66 @@ +//===-- 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 + +#include "gtest/gtest.h" +#include "sanitizer_common/sanitizer_common.h" + +namespace __sanitizer { + +class SanitizerCommon + : public testing::TestWithParam, std::vector, std::vector>> {}; + +TEST_P(SanitizerCommon, Intersect) { + { + InternalMmapVector output; + Intersect(std::get<0>(GetParam()), std::get<1>(GetParam()), output); + EXPECT_EQ(std::get<2>(GetParam()), + std::vector(output.begin(), output.end())); + } + { + InternalMmapVector output; + Intersect(std::get<1>(GetParam()), std::get<0>(GetParam()), output); + EXPECT_EQ(std::get<2>(GetParam()), + std::vector(output.begin(), output.end())); + } +} + +static void PrintTo(const Range &r, std::ostream *os) { + *os << "[" << r.begin << ", " << r.end << ")"; +} + +static const std::tuple, std::vector, + std::vector> + 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 -- 2.7.4