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