1// RUN: %clangxx_tsan -O1 %s %link_libcxx_tsan -o %t && %run %t 2>&1 | FileCheck %s
2
3#include <pthread.h>
4#include <stdlib.h>
5#include <stdio.h>
6#include <unistd.h>
7#include <time.h>
8#include <errno.h>
9#include <vector>
10#include <algorithm>
11#include <sys/time.h>
12
13const int kThreads = 4;
14const int kMutexes = 16 << 10;
15const int kIters = 400 << 10;
16const int kMaxPerThread = 10;
17
18const int kStateInited = 0;
19const int kStateNotInited = -1;
20const int kStateLocked = -2;
21
22struct Mutex {
23 int state;
24 pthread_rwlock_t m;
25};
26
27Mutex mtx[kMutexes];
28
29void check(int res) {
30 if (res != 0) {
31 printf("SOMETHING HAS FAILED\n");
32 exit(1);
33 }
34}
35
36bool cas(int *a, int oldval, int newval) {
37 return __atomic_compare_exchange_n(a, &oldval, newval, false,
38 __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
39}
40
41void *Thread(void *seed) {
42 unsigned rnd = (unsigned)(unsigned long)seed;
43 int err;
44 std::vector<int> locked;
45 for (int i = 0; i < kIters; i++) {
46 int what = rand_r(&rnd) % 10;
47 if (what < 4 && locked.size() < kMaxPerThread) {
48 // lock
49 int max_locked = -1;
50 if (!locked.empty()) {
51 max_locked = *std::max_element(locked.begin(), locked.end());
52 if (max_locked == kMutexes - 1) {
53 i--;
54 continue;
55 }
56 }
57 int id = (rand_r(&rnd) % (kMutexes - max_locked - 1)) + max_locked + 1;
58 Mutex *m = &mtx[id];
59 // init the mutex if necessary or acquire a reference
60 for (;;) {
61 int old = __atomic_load_n(&m->state, __ATOMIC_RELAXED);
62 if (old == kStateLocked) {
63 sched_yield();
64 continue;
65 }
66 int newv = old + 1;
67 if (old == kStateNotInited)
68 newv = kStateLocked;
69 if (cas(&m->state, old, newv)) {
70 if (old == kStateNotInited) {
71 if ((err = pthread_rwlock_init(&m->m, 0))) {
72 fprintf(stderr, "pthread_rwlock_init failed with %d\n", err);
73 exit(1);
74 }
75 if (!cas(&m->state, kStateLocked, 1)) {
76 fprintf(stderr, "init commit failed\n");
77 exit(1);
78 }
79 }
80 break;
81 }
82 }
83 // now we have an inited and referenced mutex, choose what to do
84 bool failed = false;
85 switch (rand_r(&rnd) % 4) {
86 case 0:
87 if ((err = pthread_rwlock_wrlock(&m->m))) {
88 fprintf(stderr, "pthread_rwlock_wrlock failed with %d\n", err);
89 exit(1);
90 }
91 break;
92 case 1:
93 if ((err = pthread_rwlock_rdlock(&m->m))) {
94 fprintf(stderr, "pthread_rwlock_rdlock failed with %d\n", err);
95 exit(1);
96 }
97 break;
98 case 2:
99 err = pthread_rwlock_trywrlock(&m->m);
100 if (err != 0 && err != EBUSY) {
101 fprintf(stderr, "pthread_rwlock_trywrlock failed with %d\n", err);
102 exit(1);
103 }
104 failed = err == EBUSY;
105 break;
106 case 3:
107 err = pthread_rwlock_tryrdlock(&m->m);
108 if (err != 0 && err != EBUSY) {
109 fprintf(stderr, "pthread_rwlock_tryrdlock failed with %d\n", err);
110 exit(1);
111 }
112 failed = err == EBUSY;
113 break;
114 }
115 if (failed) {
116 if (__atomic_fetch_sub(&m->state, 1, __ATOMIC_ACQ_REL) <= 0) {
117 fprintf(stderr, "failed to unref after failed trylock\n");
118 exit(1);
119 }
120 continue;
121 }
122 locked.push_back(id);
123 } else if (what < 9 && !locked.empty()) {
124 // unlock
125 int pos = rand_r(&rnd) % locked.size();
126 int id = locked[pos];
127 locked[pos] = locked[locked.size() - 1];
128 locked.pop_back();
129 Mutex *m = &mtx[id];
130 if ((err = pthread_rwlock_unlock(&m->m))) {
131 fprintf(stderr, "pthread_rwlock_unlock failed with %d\n", err);
132 exit(1);
133 }
134 if (__atomic_fetch_sub(&m->state, 1, __ATOMIC_ACQ_REL) <= 0) {
135 fprintf(stderr, "failed to unref after unlock\n");
136 exit(1);
137 }
138 } else {
139 // Destroy a random mutex.
140 int id = rand_r(&rnd) % kMutexes;
141 Mutex *m = &mtx[id];
142 if (!cas(&m->state, kStateInited, kStateLocked)) {
143 i--;
144 continue;
145 }
146 if ((err = pthread_rwlock_destroy(&m->m))) {
147 fprintf(stderr, "pthread_rwlock_destroy failed with %d\n", err);
148 exit(1);
149 }
150 if (!cas(&m->state, kStateLocked, kStateNotInited)) {
151 fprintf(stderr, "destroy commit failed\n");
152 exit(1);
153 }
154 }
155 }
156 // Unlock all previously locked mutexes, otherwise other threads can deadlock.
157 for (int i = 0; i < locked.size(); i++) {
158 int id = locked[i];
159 Mutex *m = &mtx[id];
160 if ((err = pthread_rwlock_unlock(&m->m))) {
161 fprintf(stderr, "pthread_rwlock_unlock failed with %d\n", err);
162 exit(1);
163 }
164 }
165 return 0;
166}
167
168int main() {
169 struct timeval tv;
170 gettimeofday(&tv, NULL);
171 unsigned s = tv.tv_sec + tv.tv_usec;
172 fprintf(stderr, "seed %d\n", s);
173 srand(s);
174 for (int i = 0; i < kMutexes; i++)
175 mtx[i].state = kStateNotInited;
176 pthread_t t[kThreads];
177 for (int i = 0; i < kThreads; i++)
178 pthread_create(&t[i], 0, Thread, (void*)(unsigned long)rand());
179 for (int i = 0; i < kThreads; i++)
180 pthread_join(t[i], 0);
181 fprintf(stderr, "DONE\n");
182 return 0;
183}
184
185// CHECK-NOT: WARNING: ThreadSanitizer
186// CHECK: DONE
187
188