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