diff options
-rw-r--r-- | lib/sanitizer_common/sanitizer_bitvector.h | 71 | ||||
-rw-r--r-- | lib/sanitizer_common/sanitizer_bvgraph.h | 14 | ||||
-rw-r--r-- | lib/sanitizer_common/sanitizer_deadlock_detector.h | 4 | ||||
-rw-r--r-- | lib/sanitizer_common/sanitizer_flags.cc | 2 | ||||
-rw-r--r-- | lib/sanitizer_common/sanitizer_flags.h | 2 | ||||
-rw-r--r-- | lib/sanitizer_common/tests/sanitizer_bitvector_test.cc | 13 | ||||
-rw-r--r-- | lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc | 19 |
7 files changed, 112 insertions, 13 deletions
diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h index 2fb7d4f71..4ad379b91 100644 --- a/lib/sanitizer_common/sanitizer_bitvector.h +++ b/lib/sanitizer_common/sanitizer_bitvector.h @@ -72,6 +72,21 @@ class BasicBitVector { // Returns true if 'this' intersects with 'v'. bool intersectsWith(const BasicBitVector &v) const { return bits_ & v.bits_; } + // for (BasicBitVector<>::Iterator it(bv); it.hasNext();) { + // uptr idx = it.next(); + // use(idx); + // } + class Iterator { + public: + Iterator() { } + explicit Iterator(const BasicBitVector &bv) : bv_(bv) {} + bool hasNext() const { return !bv_.empty(); } + uptr next() { return bv_.getAndClearFirstOne(); } + void clear() { bv_.clear(); } + private: + BasicBitVector bv_; + }; + private: basic_int_t mask(uptr idx) const { CHECK_LT(idx, size()); @@ -109,7 +124,7 @@ class TwoLevelBitVector { } } - bool empty() { + bool empty() const { for (uptr i = 0; i < kLevel1Size; i++) if (!l1_[i].empty()) return false; @@ -226,6 +241,60 @@ class TwoLevelBitVector { return false; } + // for (TwoLevelBitVector<>::Iterator it(bv); it.hasNext();) { + // uptr idx = it.next(); + // use(idx); + // } + class Iterator { + public: + Iterator() { } + explicit Iterator(const TwoLevelBitVector &bv) : bv_(bv), i0_(0), i1_(0) { + it1_.clear(); + it2_.clear(); + } + + bool hasNext() const { + if (it1_.hasNext()) return true; + for (uptr i = i0_; i < kLevel1Size; i++) + if (!bv_.l1_[i].empty()) return true; + return false; + } + + uptr next() { + // Printf("++++: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), + // it2_.hasNext(), kSize); + if (!it1_.hasNext() && !it2_.hasNext()) { + for (; i0_ < kLevel1Size; i0_++) { + if (bv_.l1_[i0_].empty()) continue; + it1_ = typename BV::Iterator(bv_.l1_[i0_]); + // Printf("+i0: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), + // it2_.hasNext(), kSize); + break; + } + } + if (!it2_.hasNext()) { + CHECK(it1_.hasNext()); + i1_ = it1_.next(); + it2_ = typename BV::Iterator(bv_.l2_[i0_][i1_]); + // Printf("++i1: %zd %zd; %d %d; size %zd\n", i0_, i1_, it1_.hasNext(), + // it2_.hasNext(), kSize); + } + CHECK(it2_.hasNext()); + uptr i2 = it2_.next(); + uptr res = i0_ * BV::kSize * BV::kSize + i1_ * BV::kSize + i2; + // Printf("+ret: %zd %zd; %d %d; size %zd; res: %zd\n", i0_, i1_, + // it1_.hasNext(), it2_.hasNext(), kSize, res); + if (!it1_.hasNext() && !it2_.hasNext()) + i0_++; + return res; + } + + private: + const TwoLevelBitVector &bv_; + uptr i0_, i1_; + typename BV::Iterator it1_, it2_; + }; + private: void check(uptr idx) const { CHECK_LE(idx, size()); } diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h index 4aed87ab5..64da198b3 100644 --- a/lib/sanitizer_common/sanitizer_bvgraph.h +++ b/lib/sanitizer_common/sanitizer_bvgraph.h @@ -21,6 +21,7 @@ namespace __sanitizer { // Directed graph of fixed size implemented as an array of bit vectors. +// Not thread-safe, all accesses should be protected by an external lock. template<class BV> class BVGraph { public: @@ -46,7 +47,8 @@ class BVGraph { // Returns true if there is a path from the node 'from' // to any of the nodes in 'targets'. bool isReachable(uptr from, const BV &targets) { - BV to_visit, visited; + BV &to_visit = t1, + &visited = t2; to_visit.copyFrom(v[from]); visited.clear(); visited.setBit(from); @@ -67,10 +69,10 @@ class BVGraph { path[0] = from; if (targets.getBit(from)) return 1; - BV t; - t.copyFrom(v[from]); - while (!t.empty()) { - uptr idx = t.getAndClearFirstOne(); + // The function is recursive, so we don't want to create BV on stack. + // Instead of a getAndClearFirstOne loop we use the slower iterator. + for (typename BV::Iterator it(v[from]); it.hasNext(); ) { + uptr idx = it.next(); if (uptr res = findPath(idx, targets, path + 1, path_size - 1)) return res + 1; } @@ -83,6 +85,8 @@ class BVGraph { CHECK_LT(idx2, size()); } BV v[kSize]; + // Keep temporary vectors here since we can not create large objects on stack. + BV t1, t2; }; } // namespace __sanitizer diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h index fcdc3f2e5..ed05c0d67 100644 --- a/lib/sanitizer_common/sanitizer_deadlock_detector.h +++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h @@ -65,6 +65,7 @@ class DeadlockDetectorTLS { // and one DeadlockDetectorTLS object per evey thread. // This class is not thread safe, all concurrent accesses should be guarded // by an external lock. +// Not thread-safe, all accesses should be protected by an external lock. template <class BV> class DeadlockDetector { public: @@ -115,7 +116,7 @@ class DeadlockDetector { // Handle the lock event, return true if there is a cycle. // FIXME: handle RW locks, recusive locks, etc. bool onLock(DeadlockDetectorTLS *dtls, uptr cur_node) { - BV cur_locks; + BV &cur_locks = t1; cur_locks.clear(); uptr cur_idx = nodeToIndex(cur_node); for (uptr i = 0, n = dtls->numLocks(); i < n; i++) { @@ -163,6 +164,7 @@ class DeadlockDetector { BV recycled_nodes_; BVGraph<BV> g_; uptr data_[BV::kSize]; + BV t1; // Temporary object which we can not keep on stack. }; } // namespace __sanitizer diff --git a/lib/sanitizer_common/sanitizer_flags.cc b/lib/sanitizer_common/sanitizer_flags.cc index ff4c5c267..ad13a029e 100644 --- a/lib/sanitizer_common/sanitizer_flags.cc +++ b/lib/sanitizer_common/sanitizer_flags.cc @@ -40,6 +40,7 @@ void SetCommonFlagsDefaults(CommonFlags *f) { f->handle_segv = SANITIZER_NEEDS_SEGV; f->allow_user_segv_handler = false; f->use_sigaltstack = false; + f->detect_deadlocks = false; f->clear_shadow_mmap_threshold = 64 * 1024; } @@ -62,6 +63,7 @@ void ParseCommonFlagsFromString(CommonFlags *f, const char *str) { ParseFlag(str, &f->handle_segv, "handle_segv"); ParseFlag(str, &f->allow_user_segv_handler, "allow_user_segv_handler"); ParseFlag(str, &f->use_sigaltstack, "use_sigaltstack"); + ParseFlag(str, &f->detect_deadlocks, "detect_deadlocks"); ParseFlag(str, &f->clear_shadow_mmap_threshold, "clear_shadow_mmap_threshold"); diff --git a/lib/sanitizer_common/sanitizer_flags.h b/lib/sanitizer_common/sanitizer_flags.h index dbd8f695a..9632ca5f9 100644 --- a/lib/sanitizer_common/sanitizer_flags.h +++ b/lib/sanitizer_common/sanitizer_flags.h @@ -71,6 +71,8 @@ struct CommonFlags { bool allow_user_segv_handler; // If set, uses alternate stack for signal handling. bool use_sigaltstack; + // If set, deadlock detection is enabled. + bool detect_deadlocks; // Large shadow regions are zero-filled using mmap(NORESERVE) instead of // memset. This is the threshold size in bytes. uptr clear_shadow_mmap_threshold; diff --git a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc index d2d1a98ea..1637fa89d 100644 --- a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc @@ -26,12 +26,25 @@ using namespace std; // Check the 'bv' == 's' and that the indexes go in increasing order. +// Also check the BV::Iterator template <class BV> static void CheckBV(const BV &bv, const set<uptr> &s) { BV t; t.copyFrom(bv); set<uptr> t_s(s); uptr last_idx = bv.size(); + uptr count = 0; + for (typename BV::Iterator it(bv); it.hasNext();) { + uptr idx = it.next(); + count++; + if (last_idx != bv.size()) + EXPECT_LT(last_idx, idx); + last_idx = idx; + EXPECT_TRUE(s.count(idx)); + } + EXPECT_EQ(count, s.size()); + + last_idx = bv.size(); while (!t.empty()) { uptr idx = t.getAndClearFirstOne(); if (last_idx != bv.size()) diff --git a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc index 0e04ac870..f03720cd1 100644 --- a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc @@ -78,21 +78,21 @@ TEST(SanitizerCommon, BVGraph) { EXPECT_GT(num_reachable, 0); } -TEST(SanitizerCommon, BVGraph_isReachable) { - typedef TwoLevelBitVector<> BV; +template <class BV> +void Test_isReachable() { uptr path[5]; BVGraph<BV> g; g.clear(); BV target; target.clear(); - uptr t0 = 100; + uptr t0 = 0; uptr t1 = g.size() - 1; target.setBit(t0); target.setBit(t1); - uptr f0 = 0; - uptr f1 = 99; - uptr f2 = 200; + uptr f0 = 1; + uptr f1 = 2; + uptr f2 = g.size() / 2; uptr f3 = g.size() - 2; EXPECT_FALSE(g.isReachable(f0, target)); @@ -127,3 +127,10 @@ TEST(SanitizerCommon, BVGraph_isReachable) { EXPECT_TRUE(g.isReachable(f2, target)); EXPECT_TRUE(g.isReachable(f3, target)); } + +TEST(SanitizerCommon, BVGraph_isReachable) { + Test_isReachable<BasicBitVector<u8> >(); + Test_isReachable<BasicBitVector<> >(); + Test_isReachable<TwoLevelBitVector<> >(); + Test_isReachable<TwoLevelBitVector<3, BasicBitVector<u8> > >(); +} |