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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
|
//===-- tsan_sync.cc ------------------------------------------------------===//
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file is a part of ThreadSanitizer (TSan), a race detector.
//
//===----------------------------------------------------------------------===//
#include "sanitizer_common/sanitizer_placement_new.h"
#include "tsan_sync.h"
#include "tsan_rtl.h"
#include "tsan_mman.h"
namespace __tsan {
void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
SyncVar::SyncVar()
: mtx(MutexTypeSyncVar, StatMtxSyncVar) {
Reset(0);
}
void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) {
this->addr = addr;
this->uid = uid;
this->next = 0;
creation_stack_id = 0;
if (!SANITIZER_GO) // Go does not use them
creation_stack_id = CurrentStackId(thr, pc);
if (common_flags()->detect_deadlocks)
DDMutexInit(thr, pc, this);
}
void SyncVar::Reset(Processor *proc) {
uid = 0;
creation_stack_id = 0;
owner_tid = kInvalidTid;
last_lock = 0;
recursion = 0;
atomic_store_relaxed(&flags, 0);
if (proc == 0) {
CHECK_EQ(clock.size(), 0);
CHECK_EQ(read_clock.size(), 0);
} else {
clock.Reset(&proc->clock_cache);
read_clock.Reset(&proc->clock_cache);
}
}
MetaMap::MetaMap()
: block_alloc_("heap block allocator")
, sync_alloc_("sync allocator") {
atomic_store(&uid_gen_, 0, memory_order_relaxed);
}
void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
u32 idx = block_alloc_.Alloc(&thr->proc()->block_cache);
MBlock *b = block_alloc_.Map(idx);
b->siz = sz;
b->tag = 0;
b->tid = thr->tid;
b->stk = CurrentStackId(thr, pc);
u32 *meta = MemToMeta(p);
DCHECK_EQ(*meta, 0);
*meta = idx | kFlagBlock;
}
uptr MetaMap::FreeBlock(Processor *proc, uptr p) {
MBlock* b = GetBlock(p);
if (b == 0)
return 0;
uptr sz = RoundUpTo(b->siz, kMetaShadowCell);
FreeRange(proc, p, sz);
return sz;
}
bool MetaMap::FreeRange(Processor *proc, uptr p, uptr sz) {
bool has_something = false;
u32 *meta = MemToMeta(p);
u32 *end = MemToMeta(p + sz);
if (end == meta)
end++;
for (; meta < end; meta++) {
u32 idx = *meta;
if (idx == 0) {
// Note: don't write to meta in this case -- the block can be huge.
continue;
}
*meta = 0;
has_something = true;
while (idx != 0) {
if (idx & kFlagBlock) {
block_alloc_.Free(&proc->block_cache, idx & ~kFlagMask);
break;
} else if (idx & kFlagSync) {
DCHECK(idx & kFlagSync);
SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
u32 next = s->next;
s->Reset(proc);
sync_alloc_.Free(&proc->sync_cache, idx & ~kFlagMask);
idx = next;
} else {
CHECK(0);
}
}
}
return has_something;
}
// ResetRange removes all meta objects from the range.
// It is called for large mmap-ed regions. The function is best-effort wrt
// freeing of meta objects, because we don't want to page in the whole range
// which can be huge. The function probes pages one-by-one until it finds a page
// without meta objects, at this point it stops freeing meta objects. Because
// thread stacks grow top-down, we do the same starting from end as well.
void MetaMap::ResetRange(Processor *proc, uptr p, uptr sz) {
if (SANITIZER_GO) {
// UnmapOrDie/MmapFixedNoReserve does not work on Windows,
// so we do the optimization only for C/C++.
FreeRange(proc, p, sz);
return;
}
const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize;
const uptr kPageSize = GetPageSizeCached() * kMetaRatio;
if (sz <= 4 * kPageSize) {
// If the range is small, just do the normal free procedure.
FreeRange(proc, p, sz);
return;
}
// First, round both ends of the range to page size.
uptr diff = RoundUp(p, kPageSize) - p;
if (diff != 0) {
FreeRange(proc, p, diff);
p += diff;
sz -= diff;
}
diff = p + sz - RoundDown(p + sz, kPageSize);
if (diff != 0) {
FreeRange(proc, p + sz - diff, diff);
sz -= diff;
}
// Now we must have a non-empty page-aligned range.
CHECK_GT(sz, 0);
CHECK_EQ(p, RoundUp(p, kPageSize));
CHECK_EQ(sz, RoundUp(sz, kPageSize));
const uptr p0 = p;
const uptr sz0 = sz;
// Probe start of the range.
for (uptr checked = 0; sz > 0; checked += kPageSize) {
bool has_something = FreeRange(proc, p, kPageSize);
p += kPageSize;
sz -= kPageSize;
if (!has_something && checked > (128 << 10))
break;
}
// Probe end of the range.
for (uptr checked = 0; sz > 0; checked += kPageSize) {
bool has_something = FreeRange(proc, p + sz - kPageSize, kPageSize);
sz -= kPageSize;
// Stacks grow down, so sync object are most likely at the end of the region
// (if it is a stack). The very end of the stack is TLS and tsan increases
// TLS by at least 256K, so check at least 512K.
if (!has_something && checked > (512 << 10))
break;
}
// Finally, page out the whole range (including the parts that we've just
// freed). Note: we can't simply madvise, because we need to leave a zeroed
// range (otherwise __tsan_java_move can crash if it encounters a left-over
// meta objects in java heap).
uptr metap = (uptr)MemToMeta(p0);
uptr metasz = sz0 / kMetaRatio;
UnmapOrDie((void*)metap, metasz);
if (!MmapFixedNoReserve(metap, metasz))
Die();
}
MBlock* MetaMap::GetBlock(uptr p) {
u32 *meta = MemToMeta(p);
u32 idx = *meta;
for (;;) {
if (idx == 0)
return 0;
if (idx & kFlagBlock)
return block_alloc_.Map(idx & ~kFlagMask);
DCHECK(idx & kFlagSync);
SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
idx = s->next;
}
}
SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
uptr addr, bool write_lock) {
return GetAndLock(thr, pc, addr, write_lock, true);
}
SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) {
return GetAndLock(0, 0, addr, write_lock, false);
}
SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc,
uptr addr, bool write_lock, bool create) {
u32 *meta = MemToMeta(addr);
u32 idx0 = *meta;
u32 myidx = 0;
SyncVar *mys = 0;
for (;;) {
u32 idx = idx0;
for (;;) {
if (idx == 0)
break;
if (idx & kFlagBlock)
break;
DCHECK(idx & kFlagSync);
SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
if (s->addr == addr) {
if (myidx != 0) {
mys->Reset(thr->proc());
sync_alloc_.Free(&thr->proc()->sync_cache, myidx);
}
if (write_lock)
s->mtx.Lock();
else
s->mtx.ReadLock();
return s;
}
idx = s->next;
}
if (!create)
return 0;
if (*meta != idx0) {
idx0 = *meta;
continue;
}
if (myidx == 0) {
const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
myidx = sync_alloc_.Alloc(&thr->proc()->sync_cache);
mys = sync_alloc_.Map(myidx);
mys->Init(thr, pc, addr, uid);
}
mys->next = idx0;
if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0,
myidx | kFlagSync, memory_order_release)) {
if (write_lock)
mys->mtx.Lock();
else
mys->mtx.ReadLock();
return mys;
}
}
}
void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
// src and dst can overlap,
// there are no concurrent accesses to the regions (e.g. stop-the-world).
CHECK_NE(src, dst);
CHECK_NE(sz, 0);
uptr diff = dst - src;
u32 *src_meta = MemToMeta(src);
u32 *dst_meta = MemToMeta(dst);
u32 *src_meta_end = MemToMeta(src + sz);
uptr inc = 1;
if (dst > src) {
src_meta = MemToMeta(src + sz) - 1;
dst_meta = MemToMeta(dst + sz) - 1;
src_meta_end = MemToMeta(src) - 1;
inc = -1;
}
for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
CHECK_EQ(*dst_meta, 0);
u32 idx = *src_meta;
*src_meta = 0;
*dst_meta = idx;
// Patch the addresses in sync objects.
while (idx != 0) {
if (idx & kFlagBlock)
break;
CHECK(idx & kFlagSync);
SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
s->addr += diff;
idx = s->next;
}
}
}
void MetaMap::OnProcIdle(Processor *proc) {
block_alloc_.FlushCache(&proc->block_cache);
sync_alloc_.FlushCache(&proc->sync_cache);
}
} // namespace __tsan
|