1 //===-- tsan_trace_test.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 "tsan_trace.h"
13 
14 #include <pthread.h>
15 
16 #include "gtest/gtest.h"
17 #include "tsan_rtl.h"
18 
19 #if SANITIZER_MAC || !defined(__x86_64__)
20 // These tests are currently crashing on Mac:
21 // https://reviews.llvm.org/D107911
22 // and on ppc64: https://reviews.llvm.org/D110546#3025422
23 // due to the way we create thread contexts
24 // (but they crashed on Mac with normal pthread_create as well).
25 // There must be some difference in thread initialization
26 // between normal execution and unit tests.
27 #  define TRACE_TEST(SUITE, NAME) TEST(SUITE, DISABLED_##NAME)
28 #else
29 #  define TRACE_TEST(SUITE, NAME) TEST(SUITE, NAME)
30 #endif
31 
32 namespace __tsan {
33 
34 // We need to run all trace tests in a new thread,
35 // so that the thread trace is empty initially.
36 template <uptr N>
37 struct ThreadArray {
38   ThreadArray() {
39     for (auto *&thr : threads) {
40       thr = static_cast<ThreadState *>(
41           MmapOrDie(sizeof(ThreadState), "ThreadState"));
42       Tid tid = ThreadCreate(cur_thread(), 0, 0, true);
43       Processor *proc = ProcCreate();
44       ProcWire(proc, thr);
45       ThreadStart(thr, tid, 0, ThreadType::Fiber);
46     }
47   }
48 
49   ~ThreadArray() {
50     for (uptr i = 0; i < N; i++) {
51       if (threads[i])
52         Finish(i);
53     }
54   }
55 
56   void Finish(uptr i) {
57     auto *thr = threads[i];
58     threads[i] = nullptr;
59     Processor *proc = thr->proc();
60     ThreadFinish(thr);
61     ProcUnwire(proc, thr);
62     ProcDestroy(proc);
63     UnmapOrDie(thr, sizeof(ThreadState));
64   }
65 
66   ThreadState *threads[N];
67   ThreadState *operator[](uptr i) { return threads[i]; }
68   ThreadState *operator->() { return threads[0]; }
69   operator ThreadState *() { return threads[0]; }
70 };
71 
72 TRACE_TEST(Trace, RestoreAccess) {
73   // A basic test with some function entry/exit events,
74   // some mutex lock/unlock events and some other distracting
75   // memory events.
76   ThreadArray<1> thr;
77   TraceFunc(thr, 0x1000);
78   TraceFunc(thr, 0x1001);
79   TraceMutexLock(thr, EventType::kLock, 0x4000, 0x5000, 0x6000);
80   TraceMutexLock(thr, EventType::kLock, 0x4001, 0x5001, 0x6001);
81   TraceMutexUnlock(thr, 0x5000);
82   TraceFunc(thr);
83   CHECK(TryTraceMemoryAccess(thr, 0x2001, 0x3001, 8, kAccessRead));
84   TraceMutexLock(thr, EventType::kRLock, 0x4002, 0x5002, 0x6002);
85   TraceFunc(thr, 0x1002);
86   CHECK(TryTraceMemoryAccess(thr, 0x2000, 0x3000, 8, kAccessRead));
87   // This is the access we want to find.
88   // The previous one is equivalent, but RestoreStack must prefer
89   // the last of the matchig accesses.
90   CHECK(TryTraceMemoryAccess(thr, 0x2002, 0x3000, 8, kAccessRead));
91   SlotPairLocker locker(thr, thr->fast_state.sid());
92   ThreadRegistryLock lock1(&ctx->thread_registry);
93   Lock lock2(&ctx->slot_mtx);
94   Tid tid = kInvalidTid;
95   VarSizeStackTrace stk;
96   MutexSet mset;
97   uptr tag = kExternalTagNone;
98   bool res = RestoreStack(EventType::kAccessExt, thr->fast_state.sid(),
99                           thr->fast_state.epoch(), 0x3000, 8, kAccessRead, &tid,
100                           &stk, &mset, &tag);
101   CHECK(res);
102   CHECK_EQ(tid, thr->tid);
103   CHECK_EQ(stk.size, 3);
104   CHECK_EQ(stk.trace[0], 0x1000);
105   CHECK_EQ(stk.trace[1], 0x1002);
106   CHECK_EQ(stk.trace[2], 0x2002);
107   CHECK_EQ(mset.Size(), 2);
108   CHECK_EQ(mset.Get(0).addr, 0x5001);
109   CHECK_EQ(mset.Get(0).stack_id, 0x6001);
110   CHECK_EQ(mset.Get(0).write, true);
111   CHECK_EQ(mset.Get(1).addr, 0x5002);
112   CHECK_EQ(mset.Get(1).stack_id, 0x6002);
113   CHECK_EQ(mset.Get(1).write, false);
114   CHECK_EQ(tag, kExternalTagNone);
115 }
116 
117 TRACE_TEST(Trace, MemoryAccessSize) {
118   // Test tracing and matching of accesses of different sizes.
119   struct Params {
120     uptr access_size, offset, size;
121     bool res;
122   };
123   Params tests[] = {
124       {1, 0, 1, true},  {4, 0, 2, true},
125       {4, 2, 2, true},  {8, 3, 1, true},
126       {2, 1, 1, true},  {1, 1, 1, false},
127       {8, 5, 4, false}, {4, static_cast<uptr>(-1l), 4, false},
128   };
129   for (auto params : tests) {
130     for (int type = 0; type < 3; type++) {
131       ThreadArray<1> thr;
132       Printf("access_size=%zu, offset=%zu, size=%zu, res=%d, type=%d\n",
133              params.access_size, params.offset, params.size, params.res, type);
134       TraceFunc(thr, 0x1000);
135       switch (type) {
136         case 0:
137           // This should emit compressed event.
138           CHECK(TryTraceMemoryAccess(thr, 0x2000, 0x3000, params.access_size,
139                                      kAccessRead));
140           break;
141         case 1:
142           // This should emit full event.
143           CHECK(TryTraceMemoryAccess(thr, 0x2000000, 0x3000, params.access_size,
144                                      kAccessRead));
145           break;
146         case 2:
147           TraceMemoryAccessRange(thr, 0x2000000, 0x3000, params.access_size,
148                                  kAccessRead);
149           break;
150       }
151       SlotPairLocker locker(thr, thr->fast_state.sid());
152       ThreadRegistryLock lock1(&ctx->thread_registry);
153       Lock lock2(&ctx->slot_mtx);
154       Tid tid = kInvalidTid;
155       VarSizeStackTrace stk;
156       MutexSet mset;
157       uptr tag = kExternalTagNone;
158       bool res =
159           RestoreStack(EventType::kAccessExt, thr->fast_state.sid(),
160                        thr->fast_state.epoch(), 0x3000 + params.offset,
161                        params.size, kAccessRead, &tid, &stk, &mset, &tag);
162       CHECK_EQ(res, params.res);
163       if (params.res) {
164         CHECK_EQ(stk.size, 2);
165         CHECK_EQ(stk.trace[0], 0x1000);
166         CHECK_EQ(stk.trace[1], type ? 0x2000000 : 0x2000);
167       }
168     }
169   }
170 }
171 
172 TRACE_TEST(Trace, RestoreMutexLock) {
173   // Check of restoration of a mutex lock event.
174   ThreadArray<1> thr;
175   TraceFunc(thr, 0x1000);
176   TraceMutexLock(thr, EventType::kLock, 0x4000, 0x5000, 0x6000);
177   TraceMutexLock(thr, EventType::kRLock, 0x4001, 0x5001, 0x6001);
178   TraceMutexLock(thr, EventType::kRLock, 0x4002, 0x5001, 0x6002);
179   SlotPairLocker locker(thr, thr->fast_state.sid());
180   ThreadRegistryLock lock1(&ctx->thread_registry);
181   Lock lock2(&ctx->slot_mtx);
182   Tid tid = kInvalidTid;
183   VarSizeStackTrace stk;
184   MutexSet mset;
185   uptr tag = kExternalTagNone;
186   bool res = RestoreStack(EventType::kLock, thr->fast_state.sid(),
187                           thr->fast_state.epoch(), 0x5001, 0, 0, &tid, &stk,
188                           &mset, &tag);
189   CHECK(res);
190   CHECK_EQ(stk.size, 2);
191   CHECK_EQ(stk.trace[0], 0x1000);
192   CHECK_EQ(stk.trace[1], 0x4002);
193   CHECK_EQ(mset.Size(), 2);
194   CHECK_EQ(mset.Get(0).addr, 0x5000);
195   CHECK_EQ(mset.Get(0).stack_id, 0x6000);
196   CHECK_EQ(mset.Get(0).write, true);
197   CHECK_EQ(mset.Get(1).addr, 0x5001);
198   CHECK_EQ(mset.Get(1).stack_id, 0x6001);
199   CHECK_EQ(mset.Get(1).write, false);
200 }
201 
202 TRACE_TEST(Trace, MultiPart) {
203   // Check replay of a trace with multiple parts.
204   ThreadArray<1> thr;
205   FuncEntry(thr, 0x1000);
206   FuncEntry(thr, 0x2000);
207   MutexPreLock(thr, 0x4000, 0x5000, 0);
208   MutexPostLock(thr, 0x4000, 0x5000, 0);
209   MutexPreLock(thr, 0x4000, 0x5000, 0);
210   MutexPostLock(thr, 0x4000, 0x5000, 0);
211   const uptr kEvents = 3 * sizeof(TracePart) / sizeof(Event);
212   for (uptr i = 0; i < kEvents; i++) {
213     FuncEntry(thr, 0x3000);
214     MutexPreLock(thr, 0x4002, 0x5002, 0);
215     MutexPostLock(thr, 0x4002, 0x5002, 0);
216     MutexUnlock(thr, 0x4003, 0x5002, 0);
217     FuncExit(thr);
218   }
219   FuncEntry(thr, 0x4000);
220   TraceMutexLock(thr, EventType::kRLock, 0x4001, 0x5001, 0x6001);
221   CHECK(TryTraceMemoryAccess(thr, 0x2002, 0x3000, 8, kAccessRead));
222   SlotPairLocker locker(thr, thr->fast_state.sid());
223   ThreadRegistryLock lock1(&ctx->thread_registry);
224   Lock lock2(&ctx->slot_mtx);
225   Tid tid = kInvalidTid;
226   VarSizeStackTrace stk;
227   MutexSet mset;
228   uptr tag = kExternalTagNone;
229   bool res = RestoreStack(EventType::kAccessExt, thr->fast_state.sid(),
230                           thr->fast_state.epoch(), 0x3000, 8, kAccessRead, &tid,
231                           &stk, &mset, &tag);
232   CHECK(res);
233   CHECK_EQ(tid, thr->tid);
234   CHECK_EQ(stk.size, 4);
235   CHECK_EQ(stk.trace[0], 0x1000);
236   CHECK_EQ(stk.trace[1], 0x2000);
237   CHECK_EQ(stk.trace[2], 0x4000);
238   CHECK_EQ(stk.trace[3], 0x2002);
239   CHECK_EQ(mset.Size(), 2);
240   CHECK_EQ(mset.Get(0).addr, 0x5000);
241   CHECK_EQ(mset.Get(0).write, true);
242   CHECK_EQ(mset.Get(0).count, 2);
243   CHECK_EQ(mset.Get(1).addr, 0x5001);
244   CHECK_EQ(mset.Get(1).write, false);
245   CHECK_EQ(mset.Get(1).count, 1);
246 }
247 
248 void CheckTraceState(uptr count, uptr finished, uptr excess, uptr recycle) {
249   Lock l(&ctx->slot_mtx);
250   Printf("CheckTraceState(%zu/%zu, %zu/%zu, %zu/%zu, %zu/%zu)\n",
251          ctx->trace_part_total_allocated, count,
252          ctx->trace_part_recycle_finished, finished,
253          ctx->trace_part_finished_excess, excess,
254          ctx->trace_part_recycle.Size(), recycle);
255   CHECK_EQ(ctx->trace_part_total_allocated, count);
256   CHECK_EQ(ctx->trace_part_recycle_finished, finished);
257   CHECK_EQ(ctx->trace_part_finished_excess, excess);
258   CHECK_EQ(ctx->trace_part_recycle.Size(), recycle);
259 }
260 
261 TRACE_TEST(TraceAlloc, SingleThread) {
262   TraceResetForTesting();
263   auto check_thread = [&](ThreadState *thr, uptr size, uptr count,
264                           uptr finished, uptr excess, uptr recycle) {
265     CHECK_EQ(thr->tctx->trace.parts.Size(), size);
266     CheckTraceState(count, finished, excess, recycle);
267   };
268   ThreadArray<2> threads;
269   check_thread(threads[0], 0, 0, 0, 0, 0);
270   TraceSwitchPartImpl(threads[0]);
271   check_thread(threads[0], 1, 1, 0, 0, 0);
272   TraceSwitchPartImpl(threads[0]);
273   check_thread(threads[0], 2, 2, 0, 0, 0);
274   TraceSwitchPartImpl(threads[0]);
275   check_thread(threads[0], 3, 3, 0, 0, 1);
276   TraceSwitchPartImpl(threads[0]);
277   check_thread(threads[0], 3, 3, 0, 0, 1);
278   threads.Finish(0);
279   CheckTraceState(3, 3, 0, 3);
280   threads.Finish(1);
281   CheckTraceState(3, 3, 0, 3);
282 }
283 
284 TRACE_TEST(TraceAlloc, FinishedThreadReuse) {
285   TraceResetForTesting();
286   constexpr uptr Hi = Trace::kFinishedThreadHi;
287   constexpr uptr kThreads = 4 * Hi;
288   ThreadArray<kThreads> threads;
289   for (uptr i = 0; i < kThreads; i++) {
290     Printf("thread %zu\n", i);
291     TraceSwitchPartImpl(threads[i]);
292     if (i <= Hi)
293       CheckTraceState(i + 1, i, 0, i);
294     else if (i <= 2 * Hi)
295       CheckTraceState(Hi + 1, Hi, i - Hi, Hi);
296     else
297       CheckTraceState(Hi + 1, Hi, Hi, Hi);
298     threads.Finish(i);
299     if (i < Hi)
300       CheckTraceState(i + 1, i + 1, 0, i + 1);
301     else if (i < 2 * Hi)
302       CheckTraceState(Hi + 1, Hi + 1, i - Hi + 1, Hi + 1);
303     else
304       CheckTraceState(Hi + 1, Hi + 1, Hi + 1, Hi + 1);
305   }
306 }
307 
308 TRACE_TEST(TraceAlloc, FinishedThreadReuse2) {
309   TraceResetForTesting();
310   // constexpr uptr Lo = Trace::kFinishedThreadLo;
311   // constexpr uptr Hi = Trace::kFinishedThreadHi;
312   constexpr uptr Min = Trace::kMinParts;
313   constexpr uptr kThreads = 10;
314   constexpr uptr kParts = 2 * Min;
315   ThreadArray<kThreads> threads;
316   for (uptr i = 0; i < kThreads; i++) {
317     Printf("thread %zu\n", i);
318     for (uptr j = 0; j < kParts; j++) TraceSwitchPartImpl(threads[i]);
319     if (i == 0)
320       CheckTraceState(Min, 0, 0, 1);
321     else
322       CheckTraceState(2 * Min, 0, Min, Min + 1);
323     threads.Finish(i);
324     if (i == 0)
325       CheckTraceState(Min, Min, 0, Min);
326     else
327       CheckTraceState(2 * Min, 2 * Min, Min, 2 * Min);
328   }
329 }
330 
331 }  // namespace __tsan
332