7 struct ShadowTable *root;
8 std::vector<struct DataRace *> unrealizedraces;
10 /** This function initialized the data race detector. */
11 void initRaceDetector() {
12 root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
15 /** This function looks up the entry in the shadow table corresponding to a
17 static uint64_t * lookupAddressEntry(void * address) {
18 struct ShadowTable *currtable=root;
20 currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&MASK16BIT];
21 if (currtable==NULL) {
22 currtable=(struct ShadowTable *) (root->array[(((uintptr_t)address)>>32)&MASK16BIT]=calloc(sizeof(struct ShadowTable),1));
26 struct ShadowBaseTable * basetable=(struct ShadowBaseTable *) currtable->array[(((uintptr_t)address)>>16)&MASK16BIT];
27 if (basetable==NULL) {
28 basetable=(struct ShadowBaseTable *) (currtable->array[(((uintptr_t)address)>>16)&MASK16BIT]=calloc(sizeof(struct ShadowBaseTable),1));
30 return &basetable->array[((uintptr_t)address)&MASK16BIT];
34 * Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
35 * to check the potential for a data race.
36 * @param clock1 The current clock vector
37 * @param tid1 The current thread; paired with clock1
38 * @param clock2 The clock value for the potentially-racing action
39 * @param tid2 The thread ID for the potentially-racing action
40 * @return true if the current clock allows a race with the event at clock2/tid2
42 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
43 modelclock_t clock2, thread_id_t tid2)
45 return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
49 * Expands a record from the compact form to the full form. This is
50 * necessary for multiple readers or for very large thread ids or time
52 static void expandRecord(uint64_t * shadow) {
53 uint64_t shadowval=*shadow;
55 modelclock_t readClock = READVECTOR(shadowval);
56 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
57 modelclock_t writeClock = WRITEVECTOR(shadowval);
58 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
60 struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
61 record->writeThread=writeThread;
62 record->writeClock=writeClock;
65 record->capacity=INITCAPACITY;
66 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
67 record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity);
69 record->thread[0]=readThread;
70 record->readClock[0]=readClock;
72 *shadow=(uint64_t) record;
75 /** This function is called when we detect a data race.*/
76 static void reportDataRace(thread_id_t oldthread, modelclock_t oldclock, bool isoldwrite, ModelAction *newaction, bool isnewwrite, void *address) {
77 struct DataRace * race=(struct DataRace *)malloc(sizeof(struct DataRace));
78 race->oldthread=oldthread;
79 race->oldclock=oldclock;
80 race->isoldwrite=isoldwrite;
81 race->newaction=newaction;
82 race->isnewwrite=isnewwrite;
83 race->address=address;
84 unrealizedraces.push_back(race);
86 /* If the race is realized, bail out now. */
87 if (checkDataRaces()) {
89 model->switch_to_master(NULL);
93 /** This function goes through the list of unrealized data races,
94 * removes the impossible ones, and print the realized ones. */
96 bool checkDataRaces() {
97 if (model->isfeasibleprefix()) {
98 /* Prune the non-racing unrealized dataraces */
99 unsigned int i,newloc=0;
100 for(i=0;i<unrealizedraces.size();i++) {
101 struct DataRace * race=unrealizedraces[i];
102 if (clock_may_race(race->newaction->get_cv(), race->newaction->get_tid(), race->oldclock, race->oldthread)) {
103 unrealizedraces[newloc++]=race;
107 unrealizedraces.resize(newloc);
109 if (unrealizedraces.size()!=0) {
110 /* We have an actual realized race. */
111 for(i=0;i<unrealizedraces.size();i++) {
112 struct DataRace * race=unrealizedraces[i];
121 void printRace(struct DataRace * race) {
122 printf("Datarace detected\n");
123 printf("Location %p\n", race->address);
124 printf("Initial access: thread %u clock %u, iswrite %u\n",race->oldthread,race->oldclock, race->isoldwrite);
125 printf("Second access: thread %u clock %u, iswrite %u\n", race->newaction->get_tid(), race->newaction->get_seq_number() , race->isnewwrite);
128 /** This function does race detection for a write on an expanded record. */
129 void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
130 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
132 /* Check for datarace against last read. */
134 for(int i=0;i<record->numReads;i++) {
135 modelclock_t readClock = record->readClock[i];
136 thread_id_t readThread = record->thread[i];
138 /* Note that readClock can't actuall be zero here, so it could be
141 if (clock_may_race(currClock, thread, readClock, readThread)) {
142 /* We have a datarace */
143 reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
147 /* Check for datarace against last write. */
149 modelclock_t writeClock = record->writeClock;
150 thread_id_t writeThread = record->writeThread;
152 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
153 /* We have a datarace */
154 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
158 record->writeThread=thread;
159 modelclock_t ourClock = currClock->getClock(thread);
160 record->writeClock=ourClock;
163 /** This function does race detection on a write. */
164 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
165 uint64_t * shadow=lookupAddressEntry(location);
166 uint64_t shadowval=*shadow;
169 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
170 fullRaceCheckWrite(thread, location, shadow, currClock);
174 int threadid = id_to_int(thread);
175 modelclock_t ourClock = currClock->getClock(thread);
177 /* Thread ID is too large or clock is too large. */
178 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
179 expandRecord(shadow);
180 fullRaceCheckWrite(thread, location, shadow, currClock);
184 /* Check for datarace against last read. */
186 modelclock_t readClock = READVECTOR(shadowval);
187 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
189 if (clock_may_race(currClock, thread, readClock, readThread)) {
190 /* We have a datarace */
191 reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
194 /* Check for datarace against last write. */
196 modelclock_t writeClock = WRITEVECTOR(shadowval);
197 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
199 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
200 /* We have a datarace */
201 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
203 *shadow = ENCODEOP(0, 0, threadid, ourClock);
206 /** This function does race detection on a read for an expanded record. */
207 void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
208 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
210 /* Check for datarace against last write. */
212 modelclock_t writeClock = record->writeClock;
213 thread_id_t writeThread = record->writeThread;
215 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
216 /* We have a datarace */
217 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
220 /* Shorten vector when possible */
224 for(int i=0;i<record->numReads;i++) {
225 modelclock_t readClock = record->readClock[i];
226 thread_id_t readThread = record->thread[i];
228 /* Note that is not really a datarace check as reads cannott
229 actually race. It is just determining that this read subsumes
230 another in the sense that either this read races or neither
231 read races. Note that readClock can't actually be zero, so it
232 could be optimized. */
234 if (clock_may_race(currClock, thread, readClock, readThread)) {
235 /* Still need this read in vector */
236 if (copytoindex!=i) {
237 record->readClock[copytoindex]=record->readClock[i];
238 record->thread[copytoindex]=record->thread[i];
244 if (copytoindex>=record->capacity) {
245 int newCapacity=record->capacity*2;
246 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
247 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
248 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
249 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
250 free(record->readClock);
251 free(record->thread);
252 record->readClock=newreadClock;
253 record->thread=newthread;
254 record->capacity=newCapacity;
257 modelclock_t ourClock = currClock->getClock(thread);
259 record->thread[copytoindex]=thread;
260 record->readClock[copytoindex]=ourClock;
261 record->numReads=copytoindex+1;
264 /** This function does race detection on a read. */
265 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
266 uint64_t * shadow=lookupAddressEntry(location);
267 uint64_t shadowval=*shadow;
270 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
271 fullRaceCheckRead(thread, location, shadow, currClock);
275 int threadid = id_to_int(thread);
276 modelclock_t ourClock = currClock->getClock(thread);
278 /* Thread ID is too large or clock is too large. */
279 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
280 expandRecord(shadow);
281 fullRaceCheckRead(thread, location, shadow, currClock);
285 /* Check for datarace against last write. */
287 modelclock_t writeClock = WRITEVECTOR(shadowval);
288 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
290 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
291 /* We have a datarace */
292 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
295 modelclock_t readClock = READVECTOR(shadowval);
296 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
298 if (clock_may_race(currClock, thread, readClock, readThread)) {
299 /* We don't subsume this read... Have to expand record. */
300 expandRecord(shadow);
301 fullRaceCheckRead(thread, location, shadow, currClock);
305 *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock);