6 struct ShadowTable *root;
8 /** This function initialized the data race detector. */
9 void initRaceDetector() {
10 root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
13 /** This function looks up the entry in the shadow table corresponding to a
15 static uint64_t * lookupAddressEntry(void * address) {
16 struct ShadowTable *currtable=root;
18 currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&MASK16BIT];
19 if (currtable==NULL) {
20 currtable=(struct ShadowTable *) (root->array[(((uintptr_t)address)>>32)&MASK16BIT]=calloc(sizeof(struct ShadowTable),1));
24 struct ShadowBaseTable * basetable=(struct ShadowBaseTable *) currtable->array[(((uintptr_t)address)>>16)&MASK16BIT];
25 if (basetable==NULL) {
26 basetable=(struct ShadowBaseTable *) (currtable->array[(((uintptr_t)address)>>16)&MASK16BIT]=calloc(sizeof(struct ShadowBaseTable),1));
28 return &basetable->array[((uintptr_t)address)&MASK16BIT];
32 * Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
33 * to check the potential for a data race.
34 * @param clock1 The current clock vector
35 * @param tid1 The current thread; paired with clock1
36 * @param clock2 The clock value for the potentially-racing action
37 * @param tid2 The thread ID for the potentially-racing action
38 * @return true if the current clock allows a race with the event at clock2/tid2
40 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
41 modelclock_t clock2, thread_id_t tid2)
43 return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
47 * Expands a record from the compact form to the full form. This is
48 * necessary for multiple readers or for very large thread ids or time
50 static void expandRecord(uint64_t * shadow) {
51 uint64_t shadowval=*shadow;
53 modelclock_t readClock = READVECTOR(shadowval);
54 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
55 modelclock_t writeClock = WRITEVECTOR(shadowval);
56 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
58 struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
59 record->writeThread=writeThread;
60 record->writeClock=writeClock;
63 record->capacity=INITCAPACITY;
64 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
65 record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity);
67 record->thread[0]=readThread;
68 record->readClock[0]=readClock;
70 *shadow=(uint64_t) record;
73 /** This function is called when we detect a data race.*/
74 static void reportDataRace() {
75 printf("The reportDataRace method should report useful things about this datarace!\n");
78 /** This function does race detection for a write on an expanded record. */
79 void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
80 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
82 /* Check for datarace against last read. */
84 for(int i=0;i<record->numReads;i++) {
85 modelclock_t readClock = record->readClock[i];
86 thread_id_t readThread = record->thread[i];
88 /* Note that readClock can't actuall be zero here, so it could be
91 if (clock_may_race(currClock, thread, readClock, readThread)) {
92 /* We have a datarace */
97 /* Check for datarace against last write. */
99 modelclock_t writeClock = record->writeClock;
100 thread_id_t writeThread = record->writeThread;
102 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
103 /* We have a datarace */
108 record->writeThread=thread;
109 modelclock_t ourClock = currClock->getClock(thread);
110 record->writeClock=ourClock;
113 /** This function does race detection on a write. */
114 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
115 uint64_t * shadow=lookupAddressEntry(location);
116 uint64_t shadowval=*shadow;
119 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
120 fullRaceCheckWrite(thread, shadow, currClock);
124 int threadid = id_to_int(thread);
125 modelclock_t ourClock = currClock->getClock(thread);
127 /* Thread ID is too large or clock is too large. */
128 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
129 expandRecord(shadow);
130 fullRaceCheckWrite(thread, shadow, currClock);
134 /* Check for datarace against last read. */
136 modelclock_t readClock = READVECTOR(shadowval);
137 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
139 if (clock_may_race(currClock, thread, readClock, readThread)) {
140 /* We have a datarace */
144 /* Check for datarace against last write. */
146 modelclock_t writeClock = WRITEVECTOR(shadowval);
147 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
149 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
150 /* We have a datarace */
153 *shadow = ENCODEOP(0, 0, threadid, ourClock);
156 /** This function does race detection on a read for an expanded record. */
157 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
158 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
160 /* Check for datarace against last write. */
162 modelclock_t writeClock = record->writeClock;
163 thread_id_t writeThread = record->writeThread;
165 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
166 /* We have a datarace */
170 /* Shorten vector when possible */
174 for(int i=0;i<record->numReads;i++) {
175 modelclock_t readClock = record->readClock[i];
176 thread_id_t readThread = record->thread[i];
178 /* Note that is not really a datarace check as reads cannott
179 actually race. It is just determining that this read subsumes
180 another in the sense that either this read races or neither
181 read races. Note that readClock can't actually be zero, so it
182 could be optimized. */
184 if (clock_may_race(currClock, thread, readClock, readThread)) {
185 /* Still need this read in vector */
186 if (copytoindex!=i) {
187 record->readClock[copytoindex]=record->readClock[i];
188 record->thread[copytoindex]=record->thread[i];
194 if (copytoindex>=record->capacity) {
195 int newCapacity=record->capacity*2;
196 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
197 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
198 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
199 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
200 free(record->readClock);
201 free(record->thread);
202 record->readClock=newreadClock;
203 record->thread=newthread;
204 record->capacity=newCapacity;
207 modelclock_t ourClock = currClock->getClock(thread);
209 record->thread[copytoindex]=thread;
210 record->readClock[copytoindex]=ourClock;
211 record->numReads=copytoindex+1;
214 /** This function does race detection on a read. */
215 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
216 uint64_t * shadow=lookupAddressEntry(location);
217 uint64_t shadowval=*shadow;
220 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
221 fullRaceCheckRead(thread, shadow, currClock);
225 int threadid = id_to_int(thread);
226 modelclock_t ourClock = currClock->getClock(thread);
228 /* Thread ID is too large or clock is too large. */
229 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
230 expandRecord(shadow);
231 fullRaceCheckRead(thread, shadow, currClock);
235 /* Check for datarace against last write. */
237 modelclock_t writeClock = WRITEVECTOR(shadowval);
238 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
240 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
241 /* We have a datarace */
245 modelclock_t readClock = READVECTOR(shadowval);
246 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
248 if (clock_may_race(currClock, thread, readClock, readThread)) {
249 /* We don't subsume this read... Have to expand record. */
250 expandRecord(shadow);
251 fullRaceCheckRead(thread, shadow, currClock);
255 *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);