threads: allocate on user's snapshotting heap
[c11tester.git] / datarace.cc
1 #include "datarace.h"
2 #include "model.h"
3 #include "threads.h"
4 #include <stdio.h>
5 #include <cstring>
6 #include "mymemory.h"
7 #include "clockvector.h"
8
9 struct ShadowTable *root;
10 std::vector<struct DataRace *> unrealizedraces;
11
12 /** This function initialized the data race detector. */
13 void initRaceDetector() {
14         root = (struct ShadowTable *)snapshot_calloc(sizeof(struct ShadowTable), 1);
15 }
16
17 /** This function looks up the entry in the shadow table corresponding to a
18  * given address.*/
19 static uint64_t * lookupAddressEntry(void * address) {
20         struct ShadowTable *currtable=root;
21 #if BIT48
22         currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&MASK16BIT];
23         if (currtable==NULL) {
24                 currtable = (struct ShadowTable *)(root->array[(((uintptr_t)address)>>32)&MASK16BIT] = snapshot_calloc(sizeof(struct ShadowTable), 1));
25         }
26 #endif
27
28         struct ShadowBaseTable * basetable=(struct ShadowBaseTable *) currtable->array[(((uintptr_t)address)>>16)&MASK16BIT];
29         if (basetable==NULL) {
30                 basetable = (struct ShadowBaseTable *)(currtable->array[(((uintptr_t)address)>>16)&MASK16BIT] = snapshot_calloc(sizeof(struct ShadowBaseTable), 1));
31         }
32         return &basetable->array[((uintptr_t)address)&MASK16BIT];
33 }
34
35 /**
36  * Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
37  * to check the potential for a data race.
38  * @param clock1 The current clock vector
39  * @param tid1 The current thread; paired with clock1
40  * @param clock2 The clock value for the potentially-racing action
41  * @param tid2 The thread ID for the potentially-racing action
42  * @return true if the current clock allows a race with the event at clock2/tid2
43  */
44 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
45                            modelclock_t clock2, thread_id_t tid2)
46 {
47         return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
48 }
49
50 /**
51  * Expands a record from the compact form to the full form.  This is
52  * necessary for multiple readers or for very large thread ids or time
53  * stamps. */
54 static void expandRecord(uint64_t * shadow) {
55         uint64_t shadowval=*shadow;
56
57         modelclock_t readClock = READVECTOR(shadowval);
58         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
59         modelclock_t writeClock = WRITEVECTOR(shadowval);
60         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
61
62         struct RaceRecord *record = (struct RaceRecord *)snapshot_calloc(1, sizeof(struct RaceRecord));
63         record->writeThread=writeThread;
64         record->writeClock=writeClock;
65
66         if (readClock!=0) {
67                 record->capacity=INITCAPACITY;
68                 record->thread = (thread_id_t *)snapshot_malloc(sizeof(thread_id_t)*record->capacity);
69                 record->readClock = (modelclock_t *)snapshot_malloc(sizeof(modelclock_t)*record->capacity);
70                 record->numReads=1;
71                 record->thread[0]=readThread;
72                 record->readClock[0]=readClock;
73         }
74         *shadow=(uint64_t) record;
75 }
76
77 /** This function is called when we detect a data race.*/
78 static void reportDataRace(thread_id_t oldthread, modelclock_t oldclock, bool isoldwrite, ModelAction *newaction, bool isnewwrite, void *address) {
79         struct DataRace *race = (struct DataRace *)snapshot_malloc(sizeof(struct DataRace));
80         race->oldthread=oldthread;
81         race->oldclock=oldclock;
82         race->isoldwrite=isoldwrite;
83         race->newaction=newaction;
84         race->isnewwrite=isnewwrite;
85         race->address=address;
86         unrealizedraces.push_back(race);
87
88         /* If the race is realized, bail out now. */
89         if (checkDataRaces()) {
90                 model->set_assert();
91                 model->switch_to_master(NULL);
92         }
93 }
94
95 /** This function goes through the list of unrealized data races,
96  *      removes the impossible ones, and print the realized ones. */
97
98 bool checkDataRaces() {
99         if (model->isfeasibleprefix()) {
100                 /* Prune the non-racing unrealized dataraces */
101                 unsigned int i,newloc=0;
102                 for(i=0;i<unrealizedraces.size();i++) {
103                         struct DataRace * race=unrealizedraces[i];
104                         if (clock_may_race(race->newaction->get_cv(), race->newaction->get_tid(), race->oldclock, race->oldthread)) {
105                                 unrealizedraces[newloc++]=race;
106                         }
107                 }
108                 if (newloc!=i)
109                         unrealizedraces.resize(newloc);
110
111                 if (unrealizedraces.size()!=0) {
112                         /* We have an actual realized race. */
113                         for(i=0;i<unrealizedraces.size();i++) {
114                                 struct DataRace * race=unrealizedraces[i];
115                                 printRace(race);
116                         }
117                         return true;
118                 }
119         }
120         return false;
121 }
122
123 void printRace(struct DataRace * race) {
124         printf("Datarace detected\n");
125         printf("Location %p\n", race->address);
126         printf("Initial access: thread %u clock %u, iswrite %u\n", id_to_int(race->oldthread), race->oldclock, race->isoldwrite);
127         printf("Second access: thread %u clock %u, iswrite %u\n", id_to_int(race->newaction->get_tid()), race->newaction->get_seq_number(), race->isnewwrite);
128 }
129
130 /** This function does race detection for a write on an expanded record. */
131 void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
132         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
133
134         /* Check for datarace against last read. */
135
136         for(int i=0;i<record->numReads;i++) {
137                 modelclock_t readClock = record->readClock[i];
138                 thread_id_t readThread = record->thread[i];
139
140                 /* Note that readClock can't actuall be zero here, so it could be
141                          optimized. */
142
143                 if (clock_may_race(currClock, thread, readClock, readThread)) {
144                         /* We have a datarace */
145                         reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
146                 }
147         }
148
149         /* Check for datarace against last write. */
150
151         modelclock_t writeClock = record->writeClock;
152         thread_id_t writeThread = record->writeThread;
153
154         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
155                 /* We have a datarace */
156                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
157         }
158
159         record->numReads=0;
160         record->writeThread=thread;
161         modelclock_t ourClock = currClock->getClock(thread);
162         record->writeClock=ourClock;
163 }
164
165 /** This function does race detection on a write. */
166 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
167         uint64_t * shadow=lookupAddressEntry(location);
168         uint64_t shadowval=*shadow;
169
170         /* Do full record */
171         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
172                 fullRaceCheckWrite(thread, location, shadow, currClock);
173                 return;
174         }
175
176         int threadid = id_to_int(thread);
177         modelclock_t ourClock = currClock->getClock(thread);
178
179         /* Thread ID is too large or clock is too large. */
180         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
181                 expandRecord(shadow);
182                 fullRaceCheckWrite(thread, location, shadow, currClock);
183                 return;
184         }
185
186         /* Check for datarace against last read. */
187
188         modelclock_t readClock = READVECTOR(shadowval);
189         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
190
191         if (clock_may_race(currClock, thread, readClock, readThread)) {
192                 /* We have a datarace */
193                 reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
194         }
195
196         /* Check for datarace against last write. */
197
198         modelclock_t writeClock = WRITEVECTOR(shadowval);
199         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
200
201         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
202                 /* We have a datarace */
203                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
204         }
205         *shadow = ENCODEOP(0, 0, threadid, ourClock);
206 }
207
208 /** This function does race detection on a read for an expanded record. */
209 void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
210         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
211
212         /* Check for datarace against last write. */
213
214         modelclock_t writeClock = record->writeClock;
215         thread_id_t writeThread = record->writeThread;
216
217         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
218                 /* We have a datarace */
219                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
220         }
221
222         /* Shorten vector when possible */
223
224         int copytoindex=0;
225
226         for(int i=0;i<record->numReads;i++) {
227                 modelclock_t readClock = record->readClock[i];
228                 thread_id_t readThread = record->thread[i];
229
230                 /*  Note that is not really a datarace check as reads cannott
231                                 actually race.  It is just determining that this read subsumes
232                                 another in the sense that either this read races or neither
233                                 read races. Note that readClock can't actually be zero, so it
234                                 could be optimized.  */
235
236                 if (clock_may_race(currClock, thread, readClock, readThread)) {
237                         /* Still need this read in vector */
238                         if (copytoindex!=i) {
239                                 record->readClock[copytoindex]=record->readClock[i];
240                                 record->thread[copytoindex]=record->thread[i];
241                         }
242                         copytoindex++;
243                 }
244         }
245
246         if (copytoindex>=record->capacity) {
247                 int newCapacity=record->capacity*2;
248                 thread_id_t *newthread = (thread_id_t *)snapshot_malloc(sizeof(thread_id_t)*newCapacity);
249                 modelclock_t *newreadClock =( modelclock_t *)snapshot_malloc(sizeof(modelclock_t)*newCapacity);
250                 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
251                 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
252                 snapshot_free(record->readClock);
253                 snapshot_free(record->thread);
254                 record->readClock=newreadClock;
255                 record->thread=newthread;
256                 record->capacity=newCapacity;
257         }
258
259         modelclock_t ourClock = currClock->getClock(thread);
260
261         record->thread[copytoindex]=thread;
262         record->readClock[copytoindex]=ourClock;
263         record->numReads=copytoindex+1;
264 }
265
266 /** This function does race detection on a read. */
267 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
268         uint64_t * shadow=lookupAddressEntry(location);
269         uint64_t shadowval=*shadow;
270
271         /* Do full record */
272         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
273                 fullRaceCheckRead(thread, location, shadow, currClock);
274                 return;
275         }
276
277         int threadid = id_to_int(thread);
278         modelclock_t ourClock = currClock->getClock(thread);
279
280         /* Thread ID is too large or clock is too large. */
281         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
282                 expandRecord(shadow);
283                 fullRaceCheckRead(thread, location, shadow, currClock);
284                 return;
285         }
286
287         /* Check for datarace against last write. */
288
289         modelclock_t writeClock = WRITEVECTOR(shadowval);
290         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
291
292         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
293                 /* We have a datarace */
294                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
295         }
296
297         modelclock_t readClock = READVECTOR(shadowval);
298         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
299
300         if (clock_may_race(currClock, thread, readClock, readThread)) {
301                 /* We don't subsume this read... Have to expand record. */
302                 expandRecord(shadow);
303                 fullRaceCheckRead(thread, location, shadow, currClock);
304                 return;
305         }
306
307         *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock);
308 }