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 <sys/time.h>
17#include <time.h>
18
19namespace __tsan {
20
21ClockCache cache;
22
23TEST(Clock, VectorBasic) {
24  ThreadClock clk(0);
25  ASSERT_EQ(clk.size(), 1U);
26  clk.tick();
27  ASSERT_EQ(clk.size(), 1U);
28  ASSERT_EQ(clk.get(0), 1U);
29  clk.set(&cache, 3, clk.get(3) + 1);
30  ASSERT_EQ(clk.size(), 4U);
31  ASSERT_EQ(clk.get(0), 1U);
32  ASSERT_EQ(clk.get(1), 0U);
33  ASSERT_EQ(clk.get(2), 0U);
34  ASSERT_EQ(clk.get(3), 1U);
35  clk.set(&cache, 3, clk.get(3) + 1);
36  ASSERT_EQ(clk.get(3), 2U);
37}
38
39TEST(Clock, ChunkedBasic) {
40  ThreadClock vector(0);
41  SyncClock chunked;
42  ASSERT_EQ(vector.size(), 1U);
43  ASSERT_EQ(chunked.size(), 0U);
44  vector.acquire(&cache, &chunked);
45  ASSERT_EQ(vector.size(), 1U);
46  ASSERT_EQ(chunked.size(), 0U);
47  vector.release(&cache, &chunked);
48  ASSERT_EQ(vector.size(), 1U);
49  ASSERT_EQ(chunked.size(), 1U);
50  vector.acq_rel(&cache, &chunked);
51  ASSERT_EQ(vector.size(), 1U);
52  ASSERT_EQ(chunked.size(), 1U);
53  chunked.Reset(&cache);
54}
55
56static const uptr interesting_sizes[] = {0, 1, 2, 30, 61, 62, 63, 64, 65, 66,
57    100, 124, 125, 126, 127, 128, 129, 130, 188, 189, 190, 191, 192, 193, 254,
58    255};
59
60TEST(Clock, Iter) {
61  const uptr n = ARRAY_SIZE(interesting_sizes);
62  for (uptr fi = 0; fi < n; fi++) {
63    const uptr size = interesting_sizes[fi];
64    SyncClock sync;
65    ThreadClock vector(0);
66    for (uptr i = 0; i < size; i++)
67      vector.set(&cache, i, i + 1);
68    if (size != 0)
69      vector.release(&cache, &sync);
70    uptr i = 0;
71    for (ClockElem &ce : sync) {
72      ASSERT_LT(i, size);
73      ASSERT_EQ(sync.get_clean(i), ce.epoch);
74      i++;
75    }
76    ASSERT_EQ(i, size);
77    sync.Reset(&cache);
78  }
79}
80
81TEST(Clock, AcquireRelease) {
82  ThreadClock vector1(100);
83  vector1.tick();
84  SyncClock chunked;
85  vector1.release(&cache, &chunked);
86  ASSERT_EQ(chunked.size(), 101U);
87  ThreadClock vector2(0);
88  vector2.acquire(&cache, &chunked);
89  ASSERT_EQ(vector2.size(), 101U);
90  ASSERT_EQ(vector2.get(0), 0U);
91  ASSERT_EQ(vector2.get(1), 0U);
92  ASSERT_EQ(vector2.get(99), 0U);
93  ASSERT_EQ(vector2.get(100), 1U);
94  chunked.Reset(&cache);
95}
96
97TEST(Clock, RepeatedAcquire) {
98  ThreadClock thr1(1);
99  thr1.tick();
100  ThreadClock thr2(2);
101  thr2.tick();
102
103  SyncClock sync;
104  thr1.ReleaseStore(&cache, &sync);
105
106  thr2.acquire(&cache, &sync);
107  thr2.acquire(&cache, &sync);
108
109  sync.Reset(&cache);
110}
111
112TEST(Clock, ManyThreads) {
113  SyncClock chunked;
114  for (unsigned i = 0; i < 200; i++) {
115    ThreadClock vector(0);
116    vector.tick();
117    vector.set(&cache, i, i + 1);
118    vector.release(&cache, &chunked);
119    ASSERT_EQ(i + 1, chunked.size());
120    vector.acquire(&cache, &chunked);
121    ASSERT_EQ(i + 1, vector.size());
122  }
123
124  for (unsigned i = 0; i < 200; i++) {
125    printf("i=%d\n", i);
126    ASSERT_EQ(i + 1, chunked.get(i));
127  }
128
129  ThreadClock vector(1);
130  vector.acquire(&cache, &chunked);
131  ASSERT_EQ(200U, vector.size());
132  for (unsigned i = 0; i < 200; i++)
133    ASSERT_EQ(i + 1, vector.get(i));
134
135  chunked.Reset(&cache);
136}
137
138TEST(Clock, DifferentSizes) {
139  {
140    ThreadClock vector1(10);
141    vector1.tick();
142    ThreadClock vector2(20);
143    vector2.tick();
144    {
145      SyncClock chunked;
146      vector1.release(&cache, &chunked);
147      ASSERT_EQ(chunked.size(), 11U);
148      vector2.release(&cache, &chunked);
149      ASSERT_EQ(chunked.size(), 21U);
150      chunked.Reset(&cache);
151    }
152    {
153      SyncClock chunked;
154      vector2.release(&cache, &chunked);
155      ASSERT_EQ(chunked.size(), 21U);
156      vector1.release(&cache, &chunked);
157      ASSERT_EQ(chunked.size(), 21U);
158      chunked.Reset(&cache);
159    }
160    {
161      SyncClock chunked;
162      vector1.release(&cache, &chunked);
163      vector2.acquire(&cache, &chunked);
164      ASSERT_EQ(vector2.size(), 21U);
165      chunked.Reset(&cache);
166    }
167    {
168      SyncClock chunked;
169      vector2.release(&cache, &chunked);
170      vector1.acquire(&cache, &chunked);
171      ASSERT_EQ(vector1.size(), 21U);
172      chunked.Reset(&cache);
173    }
174  }
175}
176
177TEST(Clock, Growth) {
178  {
179    ThreadClock vector(10);
180    vector.tick();
181    vector.set(&cache, 5, 42);
182    SyncClock sync;
183    vector.release(&cache, &sync);
184    ASSERT_EQ(sync.size(), 11U);
185    ASSERT_EQ(sync.get(0), 0ULL);
186    ASSERT_EQ(sync.get(1), 0ULL);
187    ASSERT_EQ(sync.get(5), 42ULL);
188    ASSERT_EQ(sync.get(9), 0ULL);
189    ASSERT_EQ(sync.get(10), 1ULL);
190    sync.Reset(&cache);
191  }
192  {
193    ThreadClock vector1(10);
194    vector1.tick();
195    ThreadClock vector2(20);
196    vector2.tick();
197    SyncClock sync;
198    vector1.release(&cache, &sync);
199    vector2.release(&cache, &sync);
200    ASSERT_EQ(sync.size(), 21U);
201    ASSERT_EQ(sync.get(0), 0ULL);
202    ASSERT_EQ(sync.get(10), 1ULL);
203    ASSERT_EQ(sync.get(19), 0ULL);
204    ASSERT_EQ(sync.get(20), 1ULL);
205    sync.Reset(&cache);
206  }
207  {
208    ThreadClock vector(100);
209    vector.tick();
210    vector.set(&cache, 5, 42);
211    vector.set(&cache, 90, 84);
212    SyncClock sync;
213    vector.release(&cache, &sync);
214    ASSERT_EQ(sync.size(), 101U);
215    ASSERT_EQ(sync.get(0), 0ULL);
216    ASSERT_EQ(sync.get(1), 0ULL);
217    ASSERT_EQ(sync.get(5), 42ULL);
218    ASSERT_EQ(sync.get(60), 0ULL);
219    ASSERT_EQ(sync.get(70), 0ULL);
220    ASSERT_EQ(sync.get(90), 84ULL);
221    ASSERT_EQ(sync.get(99), 0ULL);
222    ASSERT_EQ(sync.get(100), 1ULL);
223    sync.Reset(&cache);
224  }
225  {
226    ThreadClock vector1(10);
227    vector1.tick();
228    ThreadClock vector2(100);
229    vector2.tick();
230    SyncClock sync;
231    vector1.release(&cache, &sync);
232    vector2.release(&cache, &sync);
233    ASSERT_EQ(sync.size(), 101U);
234    ASSERT_EQ(sync.get(0), 0ULL);
235    ASSERT_EQ(sync.get(10), 1ULL);
236    ASSERT_EQ(sync.get(99), 0ULL);
237    ASSERT_EQ(sync.get(100), 1ULL);
238    sync.Reset(&cache);
239  }
240}
241
242TEST(Clock, Growth2) {
243  // Test clock growth for every pair of sizes:
244  const uptr n = ARRAY_SIZE(interesting_sizes);
245  for (uptr fi = 0; fi < n; fi++) {
246    for (uptr ti = fi + 1; ti < n; ti++) {
247      const uptr from = interesting_sizes[fi];
248      const uptr to = interesting_sizes[ti];
249      SyncClock sync;
250      ThreadClock vector(0);
251      for (uptr i = 0; i < from; i++)
252        vector.set(&cache, i, i + 1);
253      if (from != 0)
254        vector.release(&cache, &sync);
255      ASSERT_EQ(sync.size(), from);
256      for (uptr i = 0; i < from; i++)
257        ASSERT_EQ(sync.get(i), i + 1);
258      for (uptr i = 0; i < to; i++)
259        vector.set(&cache, i, i + 1);
260      vector.release(&cache, &sync);
261      ASSERT_EQ(sync.size(), to);
262      for (uptr i = 0; i < to; i++)
263        ASSERT_EQ(sync.get(i), i + 1);
264      vector.set(&cache, to + 1, to + 1);
265      vector.release(&cache, &sync);
266      ASSERT_EQ(sync.size(), to + 2);
267      for (uptr i = 0; i < to; i++)
268        ASSERT_EQ(sync.get(i), i + 1);
269      ASSERT_EQ(sync.get(to), 0U);
270      ASSERT_EQ(sync.get(to + 1), to + 1);
271      sync.Reset(&cache);
272    }
273  }
274}
275
276const uptr kThreads = 4;
277const uptr kClocks = 4;
278
279// SimpleSyncClock and SimpleThreadClock implement the same thing as
280// SyncClock and ThreadClock, but in a very simple way.
281struct SimpleSyncClock {
282  u64 clock[kThreads];
283  uptr size;
284
285  SimpleSyncClock() {
286    Reset();
287  }
288
289  void Reset() {
290    size = 0;
291    for (uptr i = 0; i < kThreads; i++)
292      clock[i] = 0;
293  }
294
295  bool verify(const SyncClock *other) const {
296    for (uptr i = 0; i < min(size, other->size()); i++) {
297      if (clock[i] != other->get(i))
298        return false;
299    }
300    for (uptr i = min(size, other->size()); i < max(size, other->size()); i++) {
301      if (i < size && clock[i] != 0)
302        return false;
303      if (i < other->size() && other->get(i) != 0)
304        return false;
305    }
306    return true;
307  }
308};
309
310struct SimpleThreadClock {
311  u64 clock[kThreads];
312  uptr size;
313  unsigned tid;
314
315  explicit SimpleThreadClock(unsigned tid) {
316    this->tid = tid;
317    size = tid + 1;
318    for (uptr i = 0; i < kThreads; i++)
319      clock[i] = 0;
320  }
321
322  void tick() {
323    clock[tid]++;
324  }
325
326  void acquire(const SimpleSyncClock *src) {
327    if (size < src->size)
328      size = src->size;
329    for (uptr i = 0; i < kThreads; i++)
330      clock[i] = max(clock[i], src->clock[i]);
331  }
332
333  void release(SimpleSyncClock *dst) const {
334    if (dst->size < size)
335      dst->size = size;
336    for (uptr i = 0; i < kThreads; i++)
337      dst->clock[i] = max(dst->clock[i], clock[i]);
338  }
339
340  void acq_rel(SimpleSyncClock *dst) {
341    acquire(dst);
342    release(dst);
343  }
344
345  void ReleaseStore(SimpleSyncClock *dst) const {
346    if (dst->size < size)
347      dst->size = size;
348    for (uptr i = 0; i < kThreads; i++)
349      dst->clock[i] = clock[i];
350  }
351
352  bool verify(const ThreadClock *other) const {
353    for (uptr i = 0; i < min(size, other->size()); i++) {
354      if (clock[i] != other->get(i))
355        return false;
356    }
357    for (uptr i = min(size, other->size()); i < max(size, other->size()); i++) {
358      if (i < size && clock[i] != 0)
359        return false;
360      if (i < other->size() && other->get(i) != 0)
361        return false;
362    }
363    return true;
364  }
365};
366
367static bool ClockFuzzer(bool printing) {
368  // Create kThreads thread clocks.
369  SimpleThreadClock *thr0[kThreads];
370  ThreadClock *thr1[kThreads];
371  unsigned reused[kThreads];
372  for (unsigned i = 0; i < kThreads; i++) {
373    reused[i] = 0;
374    thr0[i] = new SimpleThreadClock(i);
375    thr1[i] = new ThreadClock(i, reused[i]);
376  }
377
378  // Create kClocks sync clocks.
379  SimpleSyncClock *sync0[kClocks];
380  SyncClock *sync1[kClocks];
381  for (unsigned i = 0; i < kClocks; i++) {
382    sync0[i] = new SimpleSyncClock();
383    sync1[i] = new SyncClock();
384  }
385
386  // Do N random operations (acquire, release, etc) and compare results
387  // for SimpleThread/SyncClock and real Thread/SyncClock.
388  for (int i = 0; i < 10000; i++) {
389    unsigned tid = rand() % kThreads;
390    unsigned cid = rand() % kClocks;
391    thr0[tid]->tick();
392    thr1[tid]->tick();
393
394    switch (rand() % 6) {
395    case 0:
396      if (printing)
397        printf("acquire thr%d <- clk%d\n", tid, cid);
398      thr0[tid]->acquire(sync0[cid]);
399      thr1[tid]->acquire(&cache, sync1[cid]);
400      break;
401    case 1:
402      if (printing)
403        printf("release thr%d -> clk%d\n", tid, cid);
404      thr0[tid]->release(sync0[cid]);
405      thr1[tid]->release(&cache, sync1[cid]);
406      break;
407    case 2:
408      if (printing)
409        printf("acq_rel thr%d <> clk%d\n", tid, cid);
410      thr0[tid]->acq_rel(sync0[cid]);
411      thr1[tid]->acq_rel(&cache, sync1[cid]);
412      break;
413    case 3:
414      if (printing)
415        printf("rel_str thr%d >> clk%d\n", tid, cid);
416      thr0[tid]->ReleaseStore(sync0[cid]);
417      thr1[tid]->ReleaseStore(&cache, sync1[cid]);
418      break;
419    case 4:
420      if (printing)
421        printf("reset clk%d\n", cid);
422      sync0[cid]->Reset();
423      sync1[cid]->Reset(&cache);
424      break;
425    case 5:
426      if (printing)
427        printf("reset thr%d\n", tid);
428      u64 epoch = thr0[tid]->clock[tid] + 1;
429      reused[tid]++;
430      delete thr0[tid];
431      thr0[tid] = new SimpleThreadClock(tid);
432      thr0[tid]->clock[tid] = epoch;
433      delete thr1[tid];
434      thr1[tid] = new ThreadClock(tid, reused[tid]);
435      thr1[tid]->set(epoch);
436      break;
437    }
438
439    if (printing) {
440      for (unsigned i = 0; i < kThreads; i++) {
441        printf("thr%d: ", i);
442        thr1[i]->DebugDump(printf);
443        printf("\n");
444      }
445      for (unsigned i = 0; i < kClocks; i++) {
446        printf("clk%d: ", i);
447        sync1[i]->DebugDump(printf);
448        printf("\n");
449      }
450
451      printf("\n");
452    }
453
454    if (!thr0[tid]->verify(thr1[tid]) || !sync0[cid]->verify(sync1[cid])) {
455      if (!printing)
456        return false;
457      printf("differs with model:\n");
458      for (unsigned i = 0; i < kThreads; i++) {
459        printf("thr%d: clock=[", i);
460        for (uptr j = 0; j < thr0[i]->size; j++)
461          printf("%s%llu", j == 0 ? "" : ",", thr0[i]->clock[j]);
462        printf("]\n");
463      }
464      for (unsigned i = 0; i < kClocks; i++) {
465        printf("clk%d: clock=[", i);
466        for (uptr j = 0; j < sync0[i]->size; j++)
467          printf("%s%llu", j == 0 ? "" : ",", sync0[i]->clock[j]);
468        printf("]\n");
469      }
470      return false;
471    }
472  }
473
474  for (unsigned i = 0; i < kClocks; i++) {
475    sync1[i]->Reset(&cache);
476  }
477  return true;
478}
479
480TEST(Clock, Fuzzer) {
481  struct timeval tv;
482  gettimeofday(&tv, NULL);
483  int seed = tv.tv_sec + tv.tv_usec;
484  printf("seed=%d\n", seed);
485  srand(seed);
486  if (!ClockFuzzer(false)) {
487    // Redo the test with the same seed, but logging operations.
488    srand(seed);
489    ClockFuzzer(true);
490    ASSERT_TRUE(false);
491  }
492}
493
494}  // namespace __tsan
495