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);
88 /** This function goes through the list of unrealized data races,
89 * removes the impossible ones, and print the realized ones. */
91 void checkDataRaces() {
93 /* Prune the non-racing unrealized dataraces */
94 unsigned int i,newloc=0;
95 for(i=0;i<unrealizedraces.size();i++) {
96 struct DataRace * race=unrealizedraces[i];
97 if (clock_may_race(race->newaction->get_cv(), race->newaction->get_tid(), race->oldclock, race->oldthread)) {
98 unrealizedraces[newloc++]=race;
102 unrealizedraces.resize(newloc);
103 for(i=0;i<unrealizedraces.size();i++) {
104 struct DataRace * race=unrealizedraces[i];
110 void printRace(struct DataRace * race) {
111 printf("Datarace detected\n");
112 printf("Location %p\n", race->address);
113 printf("Initial access: thread %u clock %u, iswrite %u\n",race->oldthread,race->oldclock, race->isoldwrite);
114 printf("Second access: thread %u, iswrite %u\n", race->newaction->get_tid(), race->isnewwrite);
117 /** This function does race detection for a write on an expanded record. */
118 void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
119 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
121 /* Check for datarace against last read. */
123 for(int i=0;i<record->numReads;i++) {
124 modelclock_t readClock = record->readClock[i];
125 thread_id_t readThread = record->thread[i];
127 /* Note that readClock can't actuall be zero here, so it could be
130 if (clock_may_race(currClock, thread, readClock, readThread)) {
131 /* We have a datarace */
132 reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
136 /* Check for datarace against last write. */
138 modelclock_t writeClock = record->writeClock;
139 thread_id_t writeThread = record->writeThread;
141 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
142 /* We have a datarace */
143 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
147 record->writeThread=thread;
148 modelclock_t ourClock = currClock->getClock(thread);
149 record->writeClock=ourClock;
152 /** This function does race detection on a write. */
153 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
154 uint64_t * shadow=lookupAddressEntry(location);
155 uint64_t shadowval=*shadow;
158 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
159 fullRaceCheckWrite(thread, location, shadow, currClock);
163 int threadid = id_to_int(thread);
164 modelclock_t ourClock = currClock->getClock(thread);
166 /* Thread ID is too large or clock is too large. */
167 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
168 expandRecord(shadow);
169 fullRaceCheckWrite(thread, location, shadow, currClock);
173 /* Check for datarace against last read. */
175 modelclock_t readClock = READVECTOR(shadowval);
176 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
178 if (clock_may_race(currClock, thread, readClock, readThread)) {
179 /* We have a datarace */
180 reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
183 /* Check for datarace against last write. */
185 modelclock_t writeClock = WRITEVECTOR(shadowval);
186 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
188 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
189 /* We have a datarace */
190 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
192 *shadow = ENCODEOP(0, 0, threadid, ourClock);
195 /** This function does race detection on a read for an expanded record. */
196 void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
197 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
199 /* Check for datarace against last write. */
201 modelclock_t writeClock = record->writeClock;
202 thread_id_t writeThread = record->writeThread;
204 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
205 /* We have a datarace */
206 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
209 /* Shorten vector when possible */
213 for(int i=0;i<record->numReads;i++) {
214 modelclock_t readClock = record->readClock[i];
215 thread_id_t readThread = record->thread[i];
217 /* Note that is not really a datarace check as reads cannott
218 actually race. It is just determining that this read subsumes
219 another in the sense that either this read races or neither
220 read races. Note that readClock can't actually be zero, so it
221 could be optimized. */
223 if (clock_may_race(currClock, thread, readClock, readThread)) {
224 /* Still need this read in vector */
225 if (copytoindex!=i) {
226 record->readClock[copytoindex]=record->readClock[i];
227 record->thread[copytoindex]=record->thread[i];
233 if (copytoindex>=record->capacity) {
234 int newCapacity=record->capacity*2;
235 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
236 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
237 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
238 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
239 free(record->readClock);
240 free(record->thread);
241 record->readClock=newreadClock;
242 record->thread=newthread;
243 record->capacity=newCapacity;
246 modelclock_t ourClock = currClock->getClock(thread);
248 record->thread[copytoindex]=thread;
249 record->readClock[copytoindex]=ourClock;
250 record->numReads=copytoindex+1;
253 /** This function does race detection on a read. */
254 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
255 uint64_t * shadow=lookupAddressEntry(location);
256 uint64_t shadowval=*shadow;
259 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
260 fullRaceCheckRead(thread, location, shadow, currClock);
264 int threadid = id_to_int(thread);
265 modelclock_t ourClock = currClock->getClock(thread);
267 /* Thread ID is too large or clock is too large. */
268 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
269 expandRecord(shadow);
270 fullRaceCheckRead(thread, location, shadow, currClock);
274 /* Check for datarace against last write. */
276 modelclock_t writeClock = WRITEVECTOR(shadowval);
277 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
279 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
280 /* We have a datarace */
281 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
284 modelclock_t readClock = READVECTOR(shadowval);
285 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
287 if (clock_may_race(currClock, thread, readClock, readThread)) {
288 /* We don't subsume this read... Have to expand record. */
289 expandRecord(shadow);
290 fullRaceCheckRead(thread, location, shadow, currClock);
294 *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock);