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