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