1 //===-- tsan_clock_test.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 "tsan_clock.h"
14 #include "tsan_rtl.h"
15 #include "gtest/gtest.h"
16 #include <time.h>
17
18 namespace __tsan {
19
TEST(Clock,VectorBasic)20 TEST(Clock, VectorBasic) {
21 ThreadClock clk(0);
22 ASSERT_EQ(clk.size(), 1U);
23 clk.tick();
24 ASSERT_EQ(clk.size(), 1U);
25 ASSERT_EQ(clk.get(0), 1U);
26 clk.set(3, clk.get(3) + 1);
27 ASSERT_EQ(clk.size(), 4U);
28 ASSERT_EQ(clk.get(0), 1U);
29 ASSERT_EQ(clk.get(1), 0U);
30 ASSERT_EQ(clk.get(2), 0U);
31 ASSERT_EQ(clk.get(3), 1U);
32 clk.set(3, clk.get(3) + 1);
33 ASSERT_EQ(clk.get(3), 2U);
34 }
35
TEST(Clock,ChunkedBasic)36 TEST(Clock, ChunkedBasic) {
37 ThreadClock vector(0);
38 SyncClock chunked;
39 ASSERT_EQ(vector.size(), 1U);
40 ASSERT_EQ(chunked.size(), 0U);
41 vector.acquire(&chunked);
42 ASSERT_EQ(vector.size(), 1U);
43 ASSERT_EQ(chunked.size(), 0U);
44 vector.release(&chunked);
45 ASSERT_EQ(vector.size(), 1U);
46 ASSERT_EQ(chunked.size(), 1U);
47 vector.acq_rel(&chunked);
48 ASSERT_EQ(vector.size(), 1U);
49 ASSERT_EQ(chunked.size(), 1U);
50 }
51
TEST(Clock,AcquireRelease)52 TEST(Clock, AcquireRelease) {
53 ThreadClock vector1(100);
54 vector1.tick();
55 SyncClock chunked;
56 vector1.release(&chunked);
57 ASSERT_EQ(chunked.size(), 101U);
58 ThreadClock vector2(0);
59 vector2.acquire(&chunked);
60 ASSERT_EQ(vector2.size(), 101U);
61 ASSERT_EQ(vector2.get(0), 0U);
62 ASSERT_EQ(vector2.get(1), 0U);
63 ASSERT_EQ(vector2.get(99), 0U);
64 ASSERT_EQ(vector2.get(100), 1U);
65 }
66
TEST(Clock,RepeatedAcquire)67 TEST(Clock, RepeatedAcquire) {
68 ThreadClock thr1(1);
69 thr1.tick();
70 ThreadClock thr2(2);
71 thr2.tick();
72
73 SyncClock sync;
74 thr1.ReleaseStore(&sync);
75
76 thr2.acquire(&sync);
77 thr2.acquire(&sync);
78 }
79
TEST(Clock,ManyThreads)80 TEST(Clock, ManyThreads) {
81 SyncClock chunked;
82 for (unsigned i = 0; i < 100; i++) {
83 ThreadClock vector(0);
84 vector.tick();
85 vector.set(i, 1);
86 vector.release(&chunked);
87 ASSERT_EQ(i + 1, chunked.size());
88 vector.acquire(&chunked);
89 ASSERT_EQ(i + 1, vector.size());
90 }
91
92 for (unsigned i = 0; i < 100; i++)
93 ASSERT_EQ(1U, chunked.get(i));
94
95 ThreadClock vector(1);
96 vector.acquire(&chunked);
97 ASSERT_EQ(100U, vector.size());
98 for (unsigned i = 0; i < 100; i++)
99 ASSERT_EQ(1U, vector.get(i));
100 }
101
TEST(Clock,DifferentSizes)102 TEST(Clock, DifferentSizes) {
103 {
104 ThreadClock vector1(10);
105 vector1.tick();
106 ThreadClock vector2(20);
107 vector2.tick();
108 {
109 SyncClock chunked;
110 vector1.release(&chunked);
111 ASSERT_EQ(chunked.size(), 11U);
112 vector2.release(&chunked);
113 ASSERT_EQ(chunked.size(), 21U);
114 }
115 {
116 SyncClock chunked;
117 vector2.release(&chunked);
118 ASSERT_EQ(chunked.size(), 21U);
119 vector1.release(&chunked);
120 ASSERT_EQ(chunked.size(), 21U);
121 }
122 {
123 SyncClock chunked;
124 vector1.release(&chunked);
125 vector2.acquire(&chunked);
126 ASSERT_EQ(vector2.size(), 21U);
127 }
128 {
129 SyncClock chunked;
130 vector2.release(&chunked);
131 vector1.acquire(&chunked);
132 ASSERT_EQ(vector1.size(), 21U);
133 }
134 }
135 }
136
137 const int kThreads = 4;
138 const int kClocks = 4;
139
140 // SimpleSyncClock and SimpleThreadClock implement the same thing as
141 // SyncClock and ThreadClock, but in a very simple way.
142 struct SimpleSyncClock {
143 u64 clock[kThreads];
144 uptr size;
145
SimpleSyncClock__tsan::SimpleSyncClock146 SimpleSyncClock() {
147 Reset();
148 }
149
Reset__tsan::SimpleSyncClock150 void Reset() {
151 size = 0;
152 for (uptr i = 0; i < kThreads; i++)
153 clock[i] = 0;
154 }
155
verify__tsan::SimpleSyncClock156 bool verify(const SyncClock *other) const {
157 for (uptr i = 0; i < min(size, other->size()); i++) {
158 if (clock[i] != other->get(i))
159 return false;
160 }
161 for (uptr i = min(size, other->size()); i < max(size, other->size()); i++) {
162 if (i < size && clock[i] != 0)
163 return false;
164 if (i < other->size() && other->get(i) != 0)
165 return false;
166 }
167 return true;
168 }
169 };
170
171 struct SimpleThreadClock {
172 u64 clock[kThreads];
173 uptr size;
174 unsigned tid;
175
SimpleThreadClock__tsan::SimpleThreadClock176 explicit SimpleThreadClock(unsigned tid) {
177 this->tid = tid;
178 size = tid + 1;
179 for (uptr i = 0; i < kThreads; i++)
180 clock[i] = 0;
181 }
182
tick__tsan::SimpleThreadClock183 void tick() {
184 clock[tid]++;
185 }
186
acquire__tsan::SimpleThreadClock187 void acquire(const SimpleSyncClock *src) {
188 if (size < src->size)
189 size = src->size;
190 for (uptr i = 0; i < kThreads; i++)
191 clock[i] = max(clock[i], src->clock[i]);
192 }
193
release__tsan::SimpleThreadClock194 void release(SimpleSyncClock *dst) const {
195 if (dst->size < size)
196 dst->size = size;
197 for (uptr i = 0; i < kThreads; i++)
198 dst->clock[i] = max(dst->clock[i], clock[i]);
199 }
200
acq_rel__tsan::SimpleThreadClock201 void acq_rel(SimpleSyncClock *dst) {
202 acquire(dst);
203 release(dst);
204 }
205
ReleaseStore__tsan::SimpleThreadClock206 void ReleaseStore(SimpleSyncClock *dst) const {
207 if (dst->size < size)
208 dst->size = size;
209 for (uptr i = 0; i < kThreads; i++)
210 dst->clock[i] = clock[i];
211 }
212
verify__tsan::SimpleThreadClock213 bool verify(const ThreadClock *other) const {
214 for (uptr i = 0; i < min(size, other->size()); i++) {
215 if (clock[i] != other->get(i))
216 return false;
217 }
218 for (uptr i = min(size, other->size()); i < max(size, other->size()); i++) {
219 if (i < size && clock[i] != 0)
220 return false;
221 if (i < other->size() && other->get(i) != 0)
222 return false;
223 }
224 return true;
225 }
226 };
227
ClockFuzzer(bool printing)228 static bool ClockFuzzer(bool printing) {
229 // Create kThreads thread clocks.
230 SimpleThreadClock *thr0[kThreads];
231 ThreadClock *thr1[kThreads];
232 unsigned reused[kThreads];
233 for (unsigned i = 0; i < kThreads; i++) {
234 reused[i] = 0;
235 thr0[i] = new SimpleThreadClock(i);
236 thr1[i] = new ThreadClock(i, reused[i]);
237 }
238
239 // Create kClocks sync clocks.
240 SimpleSyncClock *sync0[kClocks];
241 SyncClock *sync1[kClocks];
242 for (unsigned i = 0; i < kClocks; i++) {
243 sync0[i] = new SimpleSyncClock();
244 sync1[i] = new SyncClock();
245 }
246
247 // Do N random operations (acquire, release, etc) and compare results
248 // for SimpleThread/SyncClock and real Thread/SyncClock.
249 for (int i = 0; i < 10000; i++) {
250 unsigned tid = rand() % kThreads;
251 unsigned cid = rand() % kClocks;
252 thr0[tid]->tick();
253 thr1[tid]->tick();
254
255 switch (rand() % 6) {
256 case 0:
257 if (printing)
258 printf("acquire thr%d <- clk%d\n", tid, cid);
259 thr0[tid]->acquire(sync0[cid]);
260 thr1[tid]->acquire(sync1[cid]);
261 break;
262 case 1:
263 if (printing)
264 printf("release thr%d -> clk%d\n", tid, cid);
265 thr0[tid]->release(sync0[cid]);
266 thr1[tid]->release(sync1[cid]);
267 break;
268 case 2:
269 if (printing)
270 printf("acq_rel thr%d <> clk%d\n", tid, cid);
271 thr0[tid]->acq_rel(sync0[cid]);
272 thr1[tid]->acq_rel(sync1[cid]);
273 break;
274 case 3:
275 if (printing)
276 printf("rel_str thr%d >> clk%d\n", tid, cid);
277 thr0[tid]->ReleaseStore(sync0[cid]);
278 thr1[tid]->ReleaseStore(sync1[cid]);
279 break;
280 case 4:
281 if (printing)
282 printf("reset clk%d\n", cid);
283 sync0[cid]->Reset();
284 sync1[cid]->Reset();
285 break;
286 case 5:
287 if (printing)
288 printf("reset thr%d\n", tid);
289 u64 epoch = thr0[tid]->clock[tid] + 1;
290 reused[tid]++;
291 delete thr0[tid];
292 thr0[tid] = new SimpleThreadClock(tid);
293 thr0[tid]->clock[tid] = epoch;
294 delete thr1[tid];
295 thr1[tid] = new ThreadClock(tid, reused[tid]);
296 thr1[tid]->set(epoch);
297 break;
298 }
299
300 if (printing) {
301 for (unsigned i = 0; i < kThreads; i++) {
302 printf("thr%d: ", i);
303 thr1[i]->DebugDump(printf);
304 printf("\n");
305 }
306 for (unsigned i = 0; i < kClocks; i++) {
307 printf("clk%d: ", i);
308 sync1[i]->DebugDump(printf);
309 printf("\n");
310 }
311
312 printf("\n");
313 }
314
315 if (!thr0[tid]->verify(thr1[tid]) || !sync0[cid]->verify(sync1[cid])) {
316 if (!printing)
317 return false;
318 printf("differs with model:\n");
319 for (unsigned i = 0; i < kThreads; i++) {
320 printf("thr%d: clock=[", i);
321 for (uptr j = 0; j < thr0[i]->size; j++)
322 printf("%s%llu", j == 0 ? "" : ",", thr0[i]->clock[j]);
323 printf("]\n");
324 }
325 for (unsigned i = 0; i < kClocks; i++) {
326 printf("clk%d: clock=[", i);
327 for (uptr j = 0; j < sync0[i]->size; j++)
328 printf("%s%llu", j == 0 ? "" : ",", sync0[i]->clock[j]);
329 printf("]\n");
330 }
331 return false;
332 }
333 }
334 return true;
335 }
336
TEST(Clock,Fuzzer)337 TEST(Clock, Fuzzer) {
338 timespec ts;
339 clock_gettime(CLOCK_MONOTONIC, &ts);
340 int seed = ts.tv_sec + ts.tv_nsec;
341 printf("seed=%d\n", seed);
342 srand(seed);
343 if (!ClockFuzzer(false)) {
344 // Redo the test with the same seed, but logging operations.
345 srand(seed);
346 ClockFuzzer(true);
347 ASSERT_TRUE(false);
348 }
349 }
350
351 } // namespace __tsan
352