6 struct ShadowTable *root;
8 /** This function initialized the data race detector. */
10 void initRaceDetector() {
11 root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
14 /** This function looks up the entry in the shadow table corresponding
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
53 static void expandRecord(uint64_t * shadow) {
54 uint64_t shadowval=*shadow;
56 modelclock_t readClock = READVECTOR(shadowval);
57 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
58 modelclock_t writeClock = WRITEVECTOR(shadowval);
59 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
61 struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
62 record->writeThread=writeThread;
63 record->writeClock=writeClock;
66 record->capacity=INITCAPACITY;
67 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
68 record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity);
70 record->thread[0]=readThread;
71 record->readClock[0]=readClock;
73 *shadow=(uint64_t) record;
76 /** This function is called when we detect a data race.*/
78 static void reportDataRace() {
79 printf("The reportDataRace method should report useful things about this datarace!\n");
82 /** This function does race detection for a write on an expanded
85 void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
86 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
88 /* Check for datarace against last read. */
90 for(int i=0;i<record->numReads;i++) {
91 modelclock_t readClock = record->readClock[i];
92 thread_id_t readThread = record->thread[i];
94 /* Note that readClock can't actuall be zero here, so it could be
97 if (clock_may_race(currClock, thread, readClock, readThread)) {
98 /* We have a datarace */
103 /* Check for datarace against last write. */
105 modelclock_t writeClock = record->writeClock;
106 thread_id_t writeThread = record->writeThread;
108 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
109 /* We have a datarace */
114 record->writeThread=thread;
115 modelclock_t ourClock = currClock->getClock(thread);
116 record->writeClock=ourClock;
119 /** This function does race detection on a write.
122 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
123 uint64_t * shadow=lookupAddressEntry(location);
124 uint64_t shadowval=*shadow;
127 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
128 fullRaceCheckWrite(thread, shadow, currClock);
132 int threadid = id_to_int(thread);
133 modelclock_t ourClock = currClock->getClock(thread);
135 /* Thread ID is too large or clock is too large. */
136 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
137 expandRecord(shadow);
138 fullRaceCheckWrite(thread, shadow, currClock);
142 /* Check for datarace against last read. */
144 modelclock_t readClock = READVECTOR(shadowval);
145 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
147 if (clock_may_race(currClock, thread, readClock, readThread)) {
148 /* We have a datarace */
152 /* Check for datarace against last write. */
154 modelclock_t writeClock = WRITEVECTOR(shadowval);
155 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
157 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
158 /* We have a datarace */
161 *shadow = ENCODEOP(0, 0, threadid, ourClock);
164 /** This function does race detection on a read for an expanded
167 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
168 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
170 /* Check for datarace against last write. */
172 modelclock_t writeClock = record->writeClock;
173 thread_id_t writeThread = record->writeThread;
175 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
176 /* We have a datarace */
180 /* Shorten vector when possible */
184 for(int i=0;i<record->numReads;i++) {
185 modelclock_t readClock = record->readClock[i];
186 thread_id_t readThread = record->thread[i];
188 /* Note that is not really a datarace check as reads cannott
189 actually race. It is just determining that this read subsumes
190 another in the sense that either this read races or neither
191 read races. Note that readClock can't actually be zero, so it
192 could be optimized. */
194 if (clock_may_race(currClock, thread, readClock, readThread)) {
195 /* Still need this read in vector */
196 if (copytoindex!=i) {
197 record->readClock[copytoindex]=record->readClock[i];
198 record->thread[copytoindex]=record->thread[i];
204 if (copytoindex>=record->capacity) {
205 int newCapacity=record->capacity*2;
206 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
207 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
208 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
209 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
210 free(record->readClock);
211 free(record->thread);
212 record->readClock=newreadClock;
213 record->thread=newthread;
214 record->capacity=newCapacity;
217 modelclock_t ourClock = currClock->getClock(thread);
219 record->thread[copytoindex]=thread;
220 record->readClock[copytoindex]=ourClock;
221 record->numReads=copytoindex+1;
224 /** This function does race detection on a read. */
226 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
227 uint64_t * shadow=lookupAddressEntry(location);
228 uint64_t shadowval=*shadow;
231 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
232 fullRaceCheckRead(thread, shadow, currClock);
236 int threadid = id_to_int(thread);
237 modelclock_t ourClock = currClock->getClock(thread);
239 /* Thread ID is too large or clock is too large. */
240 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
241 expandRecord(shadow);
242 fullRaceCheckRead(thread, shadow, currClock);
246 /* Check for datarace against last write. */
248 modelclock_t writeClock = WRITEVECTOR(shadowval);
249 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
251 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
252 /* We have a datarace */
256 modelclock_t readClock = READVECTOR(shadowval);
257 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
259 if (clock_may_race(currClock, thread, readClock, readThread)) {
260 /* We don't subsume this read... Have to expand record. */
261 expandRecord(shadow);
262 fullRaceCheckRead(thread, shadow, currClock);
266 *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);