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
18namespace __tsan {
19
20TEST(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
36TEST(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
52TEST(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
67TEST(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
80TEST(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
102TEST(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
137const int kThreads = 4;
138const int kClocks = 4;
139
140// SimpleSyncClock and SimpleThreadClock implement the same thing as
141// SyncClock and ThreadClock, but in a very simple way.
142struct SimpleSyncClock {
143  u64 clock[kThreads];
144  uptr size;
145
146  SimpleSyncClock() {
147    Reset();
148  }
149
150  void Reset() {
151    size = 0;
152    for (uptr i = 0; i < kThreads; i++)
153      clock[i] = 0;
154  }
155
156  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
171struct SimpleThreadClock {
172  u64 clock[kThreads];
173  uptr size;
174  unsigned tid;
175
176  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
183  void tick() {
184    clock[tid]++;
185  }
186
187  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
194  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
201  void acq_rel(SimpleSyncClock *dst) {
202    acquire(dst);
203    release(dst);
204  }
205
206  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
213  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
228static 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
337TEST(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