From 083d657845b7e12a09d1644adb4b6836b22dd32e Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Wed, 12 Feb 2014 07:05:24 +0000 Subject: [PATCH] [sanitizer] added a bit vector class to be used in a deadlock detector llvm-svn: 201210 --- compiler-rt/lib/sanitizer_common/CMakeLists.txt | 1 + .../lib/sanitizer_common/sanitizer_bitvector.h | 143 +++++++++++++++++++++ .../lib/sanitizer_common/tests/CMakeLists.txt | 1 + .../tests/sanitizer_bitvector_test.cc | 91 +++++++++++++ 4 files changed, 236 insertions(+) create mode 100644 compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h create mode 100644 compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt index 2722325..bd2ca81 100644 --- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt @@ -44,6 +44,7 @@ set(SANITIZER_HEADERS sanitizer_atomic.h sanitizer_atomic_clang.h sanitizer_atomic_msvc.h + sanitizer_bitvector.h sanitizer_common.h sanitizer_common_interceptors.inc sanitizer_common_interceptors_ioctl.inc diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h b/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h new file mode 100644 index 0000000..bef680c --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h @@ -0,0 +1,143 @@ +//===-- sanitizer_bitvector.h -----------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Specializer BitVector implementation. +// +//===----------------------------------------------------------------------===// + +#ifndef SANITIZER_BITVECTOR_H +#define SANITIZER_BITVECTOR_H + +#include "sanitizer_common.h" + +namespace __sanitizer { + +// Fixed size bit vector based on a single basic integer. +template +class BasicBitVector { + public: + enum SizeEnum { kSize = sizeof(basic_int_t) * 8 }; + uptr size() const { return kSize; } + // No CTOR. + void clear() { bits_ = 0; } + bool empty() const { return bits_ == 0; } + void setBit(uptr idx) { bits_ |= mask(idx); } + void clearBit(uptr idx) { bits_ &= ~mask(idx); } + bool getBit(uptr idx) const { return bits_ & mask(idx); } + uptr getAndClearFirstOne() { + CHECK(!empty()); + // FIXME: change to LeastSignificantSetBitIndex? + uptr idx = MostSignificantSetBitIndex(bits_); + clearBit(idx); + return idx; + } + + private: + basic_int_t mask(uptr idx) const { + CHECK_LE(idx, size()); + return (basic_int_t)1UL << idx; + } + basic_int_t bits_; +}; + +// Fixed size bit vector of (kLevel1Size*BV::kSize**2) bits. +// The implementation is optimized for a sparse bit vector, i.e. the one +// that has few set bits. +template > +class TwoLevelBitVector { + // This is essentially a 2-level bit vector. + // Set bit in the first level BV indicates that there are set bits + // in the corresponding BV of the second level. + // This structure allows O(kLevel1Size) time for clear() and empty(), + // as well fast handling of sparse BVs. + public: + enum SizeEnum { kSize = BV::kSize * BV::kSize * kLevel1Size }; + // No CTOR. + uptr size() const { return kSize; } + void clear() { + for (uptr i = 0; i < kLevel1Size; i++) + l1_[i].clear(); + } + bool empty() { + for (uptr i = 0; i < kLevel1Size; i++) + if (!l1_[i].empty()) + return false; + return true; + } + void setBit(uptr idx) { + check(idx); + uptr i0 = idx0(idx); + uptr i1 = idx1(idx); + uptr i2 = idx2(idx); + if (!l1_[i0].getBit(i1)) { + l1_[i0].setBit(i1); + l2_[i0][i1].clear(); + } + l2_[i0][i1].setBit(i2); + // Printf("%s: %zd => %zd %zd %zd\n", __FUNCTION__, idx, i0, i1, i2); + } + void clearBit(uptr idx) { + check(idx); + uptr i0 = idx0(idx); + uptr i1 = idx1(idx); + uptr i2 = idx2(idx); + if (l1_[i0].getBit(i1)) { + l2_[i0][i1].clearBit(i2); + if (l2_[i0][i1].empty()) + l1_[i0].clearBit(i1); + } + } + bool getBit(uptr idx) { + check(idx); + uptr i0 = idx0(idx); + uptr i1 = idx1(idx); + uptr i2 = idx2(idx); + // Printf("%s: %zd => %zd %zd %zd\n", __FUNCTION__, idx, i0, i1, i2); + return l1_[i0].getBit(i1) && l2_[i0][i1].getBit(i2); + } + uptr getAndClearFirstOne() { + for (uptr i0 = 0; i0 < kLevel1Size; i0++) { + if (l1_[i0].empty()) continue; + uptr i1 = l1_[i0].getAndClearFirstOne(); + uptr i2 = l2_[i0][i1].getAndClearFirstOne(); + if (!l2_[i0][i1].empty()) + l1_[i0].setBit(i1); + uptr res = i0 * BV::kSize * BV::kSize + i1 * BV::kSize + i2; + // Printf("getAndClearFirstOne: %zd %zd %zd => %zd\n", i0, i1, i2, res); + return res; + } + CHECK(0); + return 0; + } + + private: + void check(uptr idx) { CHECK_LE(idx, size()); } + uptr idx0(uptr idx) { + uptr res = idx / (BV::kSize * BV::kSize); + CHECK_LE(res, kLevel1Size); + return res; + } + uptr idx1(uptr idx) { + uptr res = (idx / BV::kSize) % BV::kSize; + CHECK_LE(res, BV::kSize); + return res; + } + uptr idx2(uptr idx) { + uptr res = idx % BV::kSize; + CHECK_LE(res, BV::kSize); + return res; + } + + BV l1_[kLevel1Size]; + BV l2_[kLevel1Size][BV::kSize]; +}; + +} // namespace __sanitizer + +#endif // SANITIZER_BITVECTOR_H diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt index b666743..551c312 100644 --- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt @@ -3,6 +3,7 @@ include(CompilerRTCompile) set(SANITIZER_UNITTESTS sanitizer_allocator_test.cc sanitizer_atomic_test.cc + sanitizer_bitvector_test.cc sanitizer_common_test.cc sanitizer_flags_test.cc sanitizer_format_interceptor_test.cc diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc new file mode 100644 index 0000000..adc6838 --- /dev/null +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc @@ -0,0 +1,91 @@ +//===-- sanitizer_bitvector_test.cc ---------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file is a part of Sanitizer runtime. +// Tests for sanitizer_bitvector.h. +// +//===----------------------------------------------------------------------===// +#include "sanitizer_common/sanitizer_bitvector.h" + +#include "sanitizer_test_utils.h" + +#include "gtest/gtest.h" + +#include +#include +#include + +using namespace __sanitizer; +using namespace std; + +template +void TestBitVector(uptr expected_size) { + BV bv; + EXPECT_EQ(expected_size, BV::kSize); + bv.clear(); + EXPECT_TRUE(bv.empty()); + bv.setBit(13); + EXPECT_FALSE(bv.empty()); + EXPECT_FALSE(bv.getBit(12)); + EXPECT_FALSE(bv.getBit(14)); + EXPECT_TRUE(bv.getBit(13)); + bv.clearBit(13); + EXPECT_FALSE(bv.getBit(13)); + + // test random bits + bv.clear(); + set s; + for (uptr it = 0; it < 1000; it++) { + uptr bit = ((uptr)my_rand() % bv.size()); + EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); + switch (my_rand() % 2) { + case 0: + bv.setBit(bit); + s.insert(bit); + break; + case 1: + bv.clearBit(bit); + s.erase(bit); + break; + } + EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1); + } + + // test getAndClearFirstOne. + vectorbits(bv.size()); + for (uptr it = 0; it < 30; it++) { + // iota + for (size_t j = 0; j < bits.size(); j++) bits[j] = j; + random_shuffle(bits.begin(), bits.end()); + uptr n_bits = ((uptr)my_rand() % bv.size()) + 1; + EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size()); + bv.clear(); + set s(bits.begin(), bits.begin() + n_bits); + for (uptr i = 0; i < n_bits; i++) { + bv.setBit(bits[i]); + s.insert(bits[i]); + } + while (!bv.empty()) { + uptr idx = bv.getAndClearFirstOne(); + EXPECT_TRUE(s.erase(idx)); + } + EXPECT_TRUE(s.empty()); + } +} + +TEST(SanitizerCommon, BasicBitVector) { + TestBitVector >(SANITIZER_WORDSIZE); +} + +TEST(SanitizerCommon, TwoLevelBitVector) { + uptr ws = SANITIZER_WORDSIZE; + TestBitVector >(ws * ws); + TestBitVector >(ws * ws * 2); + TestBitVector >(ws * ws * 3); +} -- 2.7.4