1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
//===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===//
//
// 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.
// The deadlock detector maintains a directed graph of lock acquisitions.
// When a lock event happens, the detector checks if the locks already held by
// the current thread are reachable from the newly acquired lock.
//
// FIXME: this is work in progress, nothing really works yet.
//
//===----------------------------------------------------------------------===//
#ifndef SANITIZER_DEADLOCK_DETECTOR_H
#define SANITIZER_DEADLOCK_DETECTOR_H
#include "sanitizer_common.h"
#include "sanitizer_bvgraph.h"
namespace __sanitizer {
// Thread-local state for DeadlockDetector.
// It contains the locks currently held by the owning thread.
class DeadlockDetectorTLS {
public:
// No CTOR.
void clear() { n_locks_ = 0; }
void addLock(uptr node) {
CHECK_LT(n_locks_, ARRAY_SIZE(locks_));
locks_[n_locks_++] = node;
}
void removeLock(uptr node) {
CHECK_NE(n_locks_, 0U);
for (sptr i = n_locks_ - 1; i >= 0; i--) {
if (locks_[i] == node) {
locks_[i] = locks_[n_locks_ - 1];
n_locks_--;
return;
}
}
CHECK(0);
}
uptr numLocks() const { return n_locks_; }
uptr getLock(uptr idx) const {
CHECK_LT(idx, n_locks_);
return locks_[idx];
}
private:
uptr n_locks_;
uptr locks_[64];
};
// DeadlockDetector.
// For deadlock detection to work we need one global DeadlockDetector object
// and one DeadlockDetectorTLS object per evey thread.
// This class is not thread safe, all concurrent accesses should be guarded
// by an external lock.
template <class BV>
class DeadlockDetector {
public:
typedef BV BitVector;
uptr size() const { return g_.size(); }
// No CTOR.
void clear() {
current_epoch_ = 0;
available_nodes_.clear();
recycled_nodes_.clear();
g_.clear();
}
// Allocate new deadlock detector node.
// If we are out of available nodes first try to recycle some.
// If there is nothing to recycle, flush the graph and increment the epoch.
// Associate 'data' (opaque user's object) with the new node.
uptr newNode(uptr data) {
if (!available_nodes_.empty())
return getAvailableNode(data);
if (!recycled_nodes_.empty()) {
CHECK(available_nodes_.empty());
available_nodes_.setUnion(recycled_nodes_);
recycled_nodes_.clear();
// FIXME: actually recycle nodes in the graph.
return getAvailableNode(data);
}
// We are out of vacant nodes. Flush and increment the current_epoch_.
uptr new_epoch = current_epoch_ + size();
clear();
current_epoch_ = new_epoch;
available_nodes_.setAll();
return getAvailableNode(data);
}
// Get data associated with the node created by newNode().
uptr getData(uptr node) const { return data_[nodeToIndex(node)]; }
void removeNode(uptr node) {
uptr idx = nodeToIndex(node);
CHECK(!available_nodes_.getBit(idx));
CHECK(recycled_nodes_.setBit(idx));
// FIXME: also remove from the graph.
}
// 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;
cur_locks.clear();
uptr cur_idx = nodeToIndex(cur_node);
for (uptr i = 0, n = dtls->numLocks(); i < n; i++) {
uptr prev_node = dtls->getLock(i);
uptr prev_idx = nodeToIndex(prev_node);
g_.addEdge(prev_idx, cur_idx);
cur_locks.setBit(prev_idx);
// Printf("OnLock %zx; prev %zx\n", cur_node, dtls->getLock(i));
}
dtls->addLock(cur_node);
return g_.isReachable(cur_idx, cur_locks);
}
// Handle the unlock event.
void onUnlock(DeadlockDetectorTLS *dtls, uptr node) {
dtls->removeLock(node);
}
private:
void check_idx(uptr idx) const { CHECK_LT(idx, size()); }
void check_node(uptr node) const {
CHECK_GE(node, size());
CHECK_EQ(current_epoch_, node / size() * size());
}
uptr indexToNode(uptr idx) {
check_idx(idx);
return idx + current_epoch_;
}
uptr nodeToIndex(uptr node) {
check_node(node);
return node % size();
}
uptr getAvailableNode(uptr data) {
uptr idx = available_nodes_.getAndClearFirstOne();
data_[idx] = data;
return indexToNode(idx);
}
uptr current_epoch_;
BV available_nodes_;
BV recycled_nodes_;
BVGraph<BV> g_;
uptr data_[BV::kSize];
};
} // namespace __sanitizer
#endif // SANITIZER_DEADLOCK_DETECTOR_H
|
