1603c4be006d8c53905d736bf1f19a49f5ce98276Alexey Samsonov//===-- tsan_clock_test.cc ------------------------------------------------===// 2da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// 3da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// The LLVM Compiler Infrastructure 4da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// 5da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// This file is distributed under the University of Illinois Open Source 6da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// License. See LICENSE.TXT for details. 7da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// 8da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany//===----------------------------------------------------------------------===// 9da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// 10da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// This file is a part of ThreadSanitizer (TSan), a race detector. 11da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany// 12da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany//===----------------------------------------------------------------------===// 13da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany#include "tsan_clock.h" 14da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany#include "tsan_rtl.h" 15da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany#include "gtest/gtest.h" 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <time.h> 17da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 18da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryanynamespace __tsan { 19da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 20da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya SerebryanyTEST(Clock, VectorBasic) { 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock clk(0); 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.size(), 1U); 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk.tick(); 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.size(), 1U); 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.get(0), 1U); 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk.set(3, clk.get(3) + 1); 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.size(), 4U); 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.get(0), 1U); 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.get(1), 0U); 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.get(2), 0U); 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.get(3), 1U); 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clk.set(3, clk.get(3) + 1); 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(clk.get(3), 2U); 34da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany} 35da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 36da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya SerebryanyTEST(Clock, ChunkedBasic) { 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector(0); 38da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector.size(), 1U); 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 0U); 41da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector.acquire(&chunked); 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector.size(), 1U); 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 0U); 44da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector.release(&chunked); 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector.size(), 1U); 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 1U); 47da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector.acq_rel(&chunked); 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector.size(), 1U); 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 1U); 50da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany} 51da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 52da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya SerebryanyTEST(Clock, AcquireRelease) { 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector1(100); 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector1.tick(); 55da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 56da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector1.release(&chunked); 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 101U); 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector2(0); 59da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector2.acquire(&chunked); 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector2.size(), 101U); 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector2.get(0), 0U); 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector2.get(1), 0U); 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector2.get(99), 0U); 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector2.get(100), 1U); 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(Clock, RepeatedAcquire) { 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock thr1(1); 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1.tick(); 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock thr2(2); 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr2.tick(); 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SyncClock sync; 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1.ReleaseStore(&sync); 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr2.acquire(&sync); 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr2.acquire(&sync); 78da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany} 79da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 80da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya SerebryanyTEST(Clock, ManyThreads) { 81da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < 100; i++) { 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector(0); 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector.tick(); 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector.set(i, 1); 86da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector.release(&chunked); 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(i + 1, chunked.size()); 88da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector.acquire(&chunked); 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(i + 1, vector.size()); 90da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany } 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < 100; i++) 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(1U, chunked.get(i)); 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector(1); 96da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector.acquire(&chunked); 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(100U, vector.size()); 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < 100; i++) 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(1U, vector.get(i)); 100da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany} 101da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 102da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya SerebryanyTEST(Clock, DifferentSizes) { 103da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany { 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector1(10); 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector1.tick(); 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock vector2(20); 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector2.tick(); 108da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany { 109da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 110da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector1.release(&chunked); 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 11U); 112da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector2.release(&chunked); 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 21U); 114da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany } 115da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany { 116da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 117da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector2.release(&chunked); 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 21U); 119da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector1.release(&chunked); 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(chunked.size(), 21U); 121da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany } 122da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany { 123da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 124da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector1.release(&chunked); 125da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector2.acquire(&chunked); 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector2.size(), 21U); 127da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany } 128da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany { 129da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany SyncClock chunked; 130da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector2.release(&chunked); 131da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany vector1.acquire(&chunked); 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_EQ(vector1.size(), 21U); 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesconst int kThreads = 4; 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesconst int kClocks = 4; 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// SimpleSyncClock and SimpleThreadClock implement the same thing as 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// SyncClock and ThreadClock, but in a very simple way. 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstruct SimpleSyncClock { 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u64 clock[kThreads]; 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size; 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SimpleSyncClock() { 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Reset(); 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void Reset() { 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines size = 0; 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kThreads; i++) 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clock[i] = 0; 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool verify(const SyncClock *other) const { 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < min(size, other->size()); i++) { 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (clock[i] != other->get(i)) 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = min(size, other->size()); i < max(size, other->size()); i++) { 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (i < size && clock[i] != 0) 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (i < other->size() && other->get(i) != 0) 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstruct SimpleThreadClock { 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u64 clock[kThreads]; 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size; 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unsigned tid; 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines explicit SimpleThreadClock(unsigned tid) { 1772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines this->tid = tid; 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines size = tid + 1; 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kThreads; i++) 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clock[i] = 0; 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void tick() { 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clock[tid]++; 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void acquire(const SimpleSyncClock *src) { 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (size < src->size) 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines size = src->size; 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kThreads; i++) 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clock[i] = max(clock[i], src->clock[i]); 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void release(SimpleSyncClock *dst) const { 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->size < size) 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->size = size; 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kThreads; i++) 1982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clock[i] = max(dst->clock[i], clock[i]); 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void acq_rel(SimpleSyncClock *dst) { 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines acquire(dst); 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines release(dst); 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void ReleaseStore(SimpleSyncClock *dst) const { 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (dst->size < size) 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->size = size; 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < kThreads; i++) 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dst->clock[i] = clock[i]; 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool verify(const ThreadClock *other) const { 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < min(size, other->size()); i++) { 2152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (clock[i] != other->get(i)) 2162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = min(size, other->size()); i < max(size, other->size()); i++) { 2192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (i < size && clock[i] != 0) 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 2212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (i < other->size() && other->get(i) != 0) 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 223da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany } 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 2252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstatic bool ClockFuzzer(bool printing) { 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Create kThreads thread clocks. 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SimpleThreadClock *thr0[kThreads]; 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ThreadClock *thr1[kThreads]; 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unsigned reused[kThreads]; 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kThreads; i++) { 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines reused[i] = 0; 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[i] = new SimpleThreadClock(i); 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[i] = new ThreadClock(i, reused[i]); 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Create kClocks sync clocks. 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SimpleSyncClock *sync0[kClocks]; 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SyncClock *sync1[kClocks]; 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kClocks; i++) { 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines sync0[i] = new SimpleSyncClock(); 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines sync1[i] = new SyncClock(); 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Do N random operations (acquire, release, etc) and compare results 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // for SimpleThread/SyncClock and real Thread/SyncClock. 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int i = 0; i < 10000; i++) { 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unsigned tid = rand() % kThreads; 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines unsigned cid = rand() % kClocks; 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid]->tick(); 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid]->tick(); 2542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines switch (rand() % 6) { 2562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines case 0: 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) 2582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("acquire thr%d <- clk%d\n", tid, cid); 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid]->acquire(sync0[cid]); 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid]->acquire(sync1[cid]); 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines case 1: 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("release thr%d -> clk%d\n", tid, cid); 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid]->release(sync0[cid]); 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid]->release(sync1[cid]); 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines case 2: 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("acq_rel thr%d <> clk%d\n", tid, cid); 2712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid]->acq_rel(sync0[cid]); 2722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid]->acq_rel(sync1[cid]); 2732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines case 3: 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("rel_str thr%d >> clk%d\n", tid, cid); 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid]->ReleaseStore(sync0[cid]); 2782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid]->ReleaseStore(sync1[cid]); 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines case 4: 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("reset clk%d\n", cid); 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines sync0[cid]->Reset(); 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines sync1[cid]->Reset(); 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines case 5: 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("reset thr%d\n", tid); 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u64 epoch = thr0[tid]->clock[tid] + 1; 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines reused[tid]++; 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines delete thr0[tid]; 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid] = new SimpleThreadClock(tid); 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr0[tid]->clock[tid] = epoch; 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines delete thr1[tid]; 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid] = new ThreadClock(tid, reused[tid]); 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[tid]->set(epoch); 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (printing) { 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kThreads; i++) { 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("thr%d: ", i); 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines thr1[i]->DebugDump(printf); 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("\n"); 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kClocks; i++) { 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("clk%d: ", i); 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines sync1[i]->DebugDump(printf); 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("\n"); 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("\n"); 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!thr0[tid]->verify(thr1[tid]) || !sync0[cid]->verify(sync1[cid])) { 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!printing) 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("differs with model:\n"); 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kThreads; i++) { 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("thr%d: clock=[", i); 3212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = 0; j < thr0[i]->size; j++) 3222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("%s%llu", j == 0 ? "" : ",", thr0[i]->clock[j]); 3232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("]\n"); 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (unsigned i = 0; i < kClocks; i++) { 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("clk%d: clock=[", i); 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = 0; j < sync0[i]->size; j++) 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("%s%llu", j == 0 ? "" : ",", sync0[i]->clock[j]); 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("]\n"); 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 3342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 3352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(Clock, Fuzzer) { 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines timespec ts; 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines clock_gettime(CLOCK_MONOTONIC, &ts); 3402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int seed = ts.tv_sec + ts.tv_nsec; 3412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines printf("seed=%d\n", seed); 3422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines srand(seed); 3432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!ClockFuzzer(false)) { 3442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Redo the test with the same seed, but logging operations. 3452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines srand(seed); 3462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ClockFuzzer(true); 3472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ASSERT_TRUE(false); 348da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany } 349da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany} 350da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany 351da4edd850db1a333c15fc3b0abc01a2e8d2f08feKostya Serebryany} // namespace __tsan 352