1//===-- tsan_sync.cc ------------------------------------------------------===//
2//
3// This file is distributed under the University of Illinois Open Source
4// License. See LICENSE.TXT for details.
5//
6//===----------------------------------------------------------------------===//
7//
8// This file is a part of ThreadSanitizer (TSan), a race detector.
9//
10//===----------------------------------------------------------------------===//
11#include "sanitizer_common/sanitizer_placement_new.h"
12#include "tsan_sync.h"
13#include "tsan_rtl.h"
14#include "tsan_mman.h"
15
16namespace __tsan {
17
18void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
19
20SyncVar::SyncVar()
21    : mtx(MutexTypeSyncVar, StatMtxSyncVar) {
22  Reset(0);
23}
24
25void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) {
26  this->addr = addr;
27  this->uid = uid;
28  this->next = 0;
29
30  creation_stack_id = 0;
31  if (!SANITIZER_GO)  // Go does not use them
32    creation_stack_id = CurrentStackId(thr, pc);
33  if (common_flags()->detect_deadlocks)
34    DDMutexInit(thr, pc, this);
35}
36
37void SyncVar::Reset(Processor *proc) {
38  uid = 0;
39  creation_stack_id = 0;
40  owner_tid = kInvalidTid;
41  last_lock = 0;
42  recursion = 0;
43  atomic_store_relaxed(&flags, 0);
44
45  if (proc == 0) {
46    CHECK_EQ(clock.size(), 0);
47    CHECK_EQ(read_clock.size(), 0);
48  } else {
49    clock.Reset(&proc->clock_cache);
50    read_clock.Reset(&proc->clock_cache);
51  }
52}
53
54MetaMap::MetaMap()
55    : block_alloc_("heap block allocator")
56    , sync_alloc_("sync allocator") {
57  atomic_store(&uid_gen_, 0, memory_order_relaxed);
58}
59
60void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
61  u32 idx = block_alloc_.Alloc(&thr->proc()->block_cache);
62  MBlock *b = block_alloc_.Map(idx);
63  b->siz = sz;
64  b->tag = 0;
65  b->tid = thr->tid;
66  b->stk = CurrentStackId(thr, pc);
67  u32 *meta = MemToMeta(p);
68  DCHECK_EQ(*meta, 0);
69  *meta = idx | kFlagBlock;
70}
71
72uptr MetaMap::FreeBlock(Processor *proc, uptr p) {
73  MBlock* b = GetBlock(p);
74  if (b == 0)
75    return 0;
76  uptr sz = RoundUpTo(b->siz, kMetaShadowCell);
77  FreeRange(proc, p, sz);
78  return sz;
79}
80
81bool MetaMap::FreeRange(Processor *proc, uptr p, uptr sz) {
82  bool has_something = false;
83  u32 *meta = MemToMeta(p);
84  u32 *end = MemToMeta(p + sz);
85  if (end == meta)
86    end++;
87  for (; meta < end; meta++) {
88    u32 idx = *meta;
89    if (idx == 0) {
90      // Note: don't write to meta in this case -- the block can be huge.
91      continue;
92    }
93    *meta = 0;
94    has_something = true;
95    while (idx != 0) {
96      if (idx & kFlagBlock) {
97        block_alloc_.Free(&proc->block_cache, idx & ~kFlagMask);
98        break;
99      } else if (idx & kFlagSync) {
100        DCHECK(idx & kFlagSync);
101        SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
102        u32 next = s->next;
103        s->Reset(proc);
104        sync_alloc_.Free(&proc->sync_cache, idx & ~kFlagMask);
105        idx = next;
106      } else {
107        CHECK(0);
108      }
109    }
110  }
111  return has_something;
112}
113
114// ResetRange removes all meta objects from the range.
115// It is called for large mmap-ed regions. The function is best-effort wrt
116// freeing of meta objects, because we don't want to page in the whole range
117// which can be huge. The function probes pages one-by-one until it finds a page
118// without meta objects, at this point it stops freeing meta objects. Because
119// thread stacks grow top-down, we do the same starting from end as well.
120void MetaMap::ResetRange(Processor *proc, uptr p, uptr sz) {
121  if (SANITIZER_GO) {
122    // UnmapOrDie/MmapFixedNoReserve does not work on Windows,
123    // so we do the optimization only for C/C++.
124    FreeRange(proc, p, sz);
125    return;
126  }
127  const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize;
128  const uptr kPageSize = GetPageSizeCached() * kMetaRatio;
129  if (sz <= 4 * kPageSize) {
130    // If the range is small, just do the normal free procedure.
131    FreeRange(proc, p, sz);
132    return;
133  }
134  // First, round both ends of the range to page size.
135  uptr diff = RoundUp(p, kPageSize) - p;
136  if (diff != 0) {
137    FreeRange(proc, p, diff);
138    p += diff;
139    sz -= diff;
140  }
141  diff = p + sz - RoundDown(p + sz, kPageSize);
142  if (diff != 0) {
143    FreeRange(proc, p + sz - diff, diff);
144    sz -= diff;
145  }
146  // Now we must have a non-empty page-aligned range.
147  CHECK_GT(sz, 0);
148  CHECK_EQ(p, RoundUp(p, kPageSize));
149  CHECK_EQ(sz, RoundUp(sz, kPageSize));
150  const uptr p0 = p;
151  const uptr sz0 = sz;
152  // Probe start of the range.
153  for (uptr checked = 0; sz > 0; checked += kPageSize) {
154    bool has_something = FreeRange(proc, p, kPageSize);
155    p += kPageSize;
156    sz -= kPageSize;
157    if (!has_something && checked > (128 << 10))
158      break;
159  }
160  // Probe end of the range.
161  for (uptr checked = 0; sz > 0; checked += kPageSize) {
162    bool has_something = FreeRange(proc, p + sz - kPageSize, kPageSize);
163    sz -= kPageSize;
164    // Stacks grow down, so sync object are most likely at the end of the region
165    // (if it is a stack). The very end of the stack is TLS and tsan increases
166    // TLS by at least 256K, so check at least 512K.
167    if (!has_something && checked > (512 << 10))
168      break;
169  }
170  // Finally, page out the whole range (including the parts that we've just
171  // freed). Note: we can't simply madvise, because we need to leave a zeroed
172  // range (otherwise __tsan_java_move can crash if it encounters a left-over
173  // meta objects in java heap).
174  uptr metap = (uptr)MemToMeta(p0);
175  uptr metasz = sz0 / kMetaRatio;
176  UnmapOrDie((void*)metap, metasz);
177  if (!MmapFixedNoReserve(metap, metasz))
178    Die();
179}
180
181MBlock* MetaMap::GetBlock(uptr p) {
182  u32 *meta = MemToMeta(p);
183  u32 idx = *meta;
184  for (;;) {
185    if (idx == 0)
186      return 0;
187    if (idx & kFlagBlock)
188      return block_alloc_.Map(idx & ~kFlagMask);
189    DCHECK(idx & kFlagSync);
190    SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
191    idx = s->next;
192  }
193}
194
195SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
196                              uptr addr, bool write_lock) {
197  return GetAndLock(thr, pc, addr, write_lock, true);
198}
199
200SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) {
201  return GetAndLock(0, 0, addr, write_lock, false);
202}
203
204SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc,
205                             uptr addr, bool write_lock, bool create) {
206  u32 *meta = MemToMeta(addr);
207  u32 idx0 = *meta;
208  u32 myidx = 0;
209  SyncVar *mys = 0;
210  for (;;) {
211    u32 idx = idx0;
212    for (;;) {
213      if (idx == 0)
214        break;
215      if (idx & kFlagBlock)
216        break;
217      DCHECK(idx & kFlagSync);
218      SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
219      if (s->addr == addr) {
220        if (myidx != 0) {
221          mys->Reset(thr->proc());
222          sync_alloc_.Free(&thr->proc()->sync_cache, myidx);
223        }
224        if (write_lock)
225          s->mtx.Lock();
226        else
227          s->mtx.ReadLock();
228        return s;
229      }
230      idx = s->next;
231    }
232    if (!create)
233      return 0;
234    if (*meta != idx0) {
235      idx0 = *meta;
236      continue;
237    }
238
239    if (myidx == 0) {
240      const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
241      myidx = sync_alloc_.Alloc(&thr->proc()->sync_cache);
242      mys = sync_alloc_.Map(myidx);
243      mys->Init(thr, pc, addr, uid);
244    }
245    mys->next = idx0;
246    if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0,
247        myidx | kFlagSync, memory_order_release)) {
248      if (write_lock)
249        mys->mtx.Lock();
250      else
251        mys->mtx.ReadLock();
252      return mys;
253    }
254  }
255}
256
257void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
258  // src and dst can overlap,
259  // there are no concurrent accesses to the regions (e.g. stop-the-world).
260  CHECK_NE(src, dst);
261  CHECK_NE(sz, 0);
262  uptr diff = dst - src;
263  u32 *src_meta = MemToMeta(src);
264  u32 *dst_meta = MemToMeta(dst);
265  u32 *src_meta_end = MemToMeta(src + sz);
266  uptr inc = 1;
267  if (dst > src) {
268    src_meta = MemToMeta(src + sz) - 1;
269    dst_meta = MemToMeta(dst + sz) - 1;
270    src_meta_end = MemToMeta(src) - 1;
271    inc = -1;
272  }
273  for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
274    CHECK_EQ(*dst_meta, 0);
275    u32 idx = *src_meta;
276    *src_meta = 0;
277    *dst_meta = idx;
278    // Patch the addresses in sync objects.
279    while (idx != 0) {
280      if (idx & kFlagBlock)
281        break;
282      CHECK(idx & kFlagSync);
283      SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
284      s->addr += diff;
285      idx = s->next;
286    }
287  }
288}
289
290void MetaMap::OnProcIdle(Processor *proc) {
291  block_alloc_.FlushCache(&proc->block_cache);
292  sync_alloc_.FlushCache(&proc->sync_cache);
293}
294
295}  // namespace __tsan
296