6 struct ShadowTable *root;
8 void initRaceDetector() {
9 root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
12 static uint64_t * lookupAddressEntry(void * address) {
13 struct ShadowTable *currtable=root;
15 currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&0xffff];
16 if (currtable==NULL) {
17 currtable=(struct ShadowTable *) (root->array[(((uintptr_t)address)>>32)&MASK16BIT]=calloc(sizeof(struct ShadowTable),1));
21 struct ShadowBaseTable * basetable=(struct ShadowBaseTable *) currtable->array[(((uintptr_t)address)>>16)&MASK16BIT];
22 if (basetable==NULL) {
23 basetable=(struct ShadowBaseTable *) (currtable->array[(((uintptr_t)address)>>16)&MASK16BIT]=calloc(sizeof(struct ShadowBaseTable),1));
25 return &basetable->array[((uintptr_t)address)&MASK16BIT];
29 * Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
30 * to check the potential for a data race.
31 * @param clock1 The current clock vector
32 * @param tid1 The current thread; paired with clock1
33 * @param clock2 The clock value for the potentially-racing action
34 * @param tid2 The thread ID for the potentially-racing action
35 * @return true if the current clock allows a race with the event at clock2/tid2
37 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
38 modelclock_t clock2, thread_id_t tid2)
40 return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
43 static void expandRecord(uint64_t * shadow) {
44 uint64_t shadowval=*shadow;
46 modelclock_t readClock = READVECTOR(shadowval);
47 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
48 modelclock_t writeClock = WRITEVECTOR(shadowval);
49 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
51 struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
52 record->writeThread=writeThread;
53 record->writeClock=writeClock;
56 record->capacity=INITCAPACITY;
57 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
58 record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity);
60 record->thread[0]=readThread;
61 record->readClock[0]=readClock;
63 *shadow=(uint64_t) record;
66 static void reportDataRace() {
67 printf("The reportDataRace method should report useful things about this datarace!\n");
70 void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
71 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
73 /* Check for datarace against last read. */
75 for(int i=0;i<record->numReads;i++) {
76 modelclock_t readClock = record->readClock[i];
77 thread_id_t readThread = record->thread[i];
79 /* Note that readClock can't actuall be zero here, so it could be
82 if (clock_may_race(currClock, thread, readClock, readThread)) {
83 /* We have a datarace */
88 /* Check for datarace against last write. */
90 modelclock_t writeClock = record->writeClock;
91 thread_id_t writeThread = record->writeThread;
93 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
94 /* We have a datarace */
99 record->writeThread=thread;
100 modelclock_t ourClock = currClock->getClock(thread);
101 record->writeClock=ourClock;
104 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
105 uint64_t * shadow=lookupAddressEntry(location);
106 uint64_t shadowval=*shadow;
109 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
110 fullRaceCheckWrite(thread, shadow, currClock);
114 int threadid = id_to_int(thread);
115 modelclock_t ourClock = currClock->getClock(thread);
117 /* Thread ID is too large or clock is too large. */
118 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
119 expandRecord(shadow);
120 fullRaceCheckWrite(thread, shadow, currClock);
124 /* Check for datarace against last read. */
126 modelclock_t readClock = READVECTOR(shadowval);
127 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
129 if (clock_may_race(currClock, thread, readClock, readThread)) {
130 /* We have a datarace */
134 /* Check for datarace against last write. */
136 modelclock_t writeClock = WRITEVECTOR(shadowval);
137 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
139 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
140 /* We have a datarace */
143 *shadow = ENCODEOP(0, 0, threadid, ourClock);
146 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
147 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
149 /* Check for datarace against last write. */
151 modelclock_t writeClock = record->writeClock;
152 thread_id_t writeThread = record->writeThread;
154 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
155 /* We have a datarace */
159 /* Shorten vector when possible */
163 for(int i=0;i<record->numReads;i++) {
164 modelclock_t readClock = record->readClock[i];
165 thread_id_t readThread = record->thread[i];
167 /* Note that is not really a datarace check as reads cannott
168 actually race. It is just determining that this read subsumes
169 another in the sense that either this read races or neither
170 read races. Note that readClock can't actually be zero, so it
171 could be optimized. */
173 if (clock_may_race(currClock, thread, readClock, readThread) {
174 /* Still need this read in vector */
175 if (copytoindex!=i) {
176 record->readClock[copytoindex]=record->readClock[i];
177 record->thread[copytoindex]=record->thread[i];
183 if (copytoindex>=record->capacity) {
184 int newCapacity=record->capacity*2;
185 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
186 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
187 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
188 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
189 free(record->readClock);
190 free(record->thread);
191 record->readClock=newreadClock;
192 record->thread=newthread;
193 record->capacity=newCapacity;
196 modelclock_t ourClock = currClock->getClock(thread);
198 record->thread[copytoindex]=thread;
199 record->readClock[copytoindex]=ourClock;
200 record->numReads=copytoindex+1;
203 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
204 uint64_t * shadow=lookupAddressEntry(location);
205 uint64_t shadowval=*shadow;
208 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
209 fullRaceCheckRead(thread, shadow, currClock);
213 int threadid = id_to_int(thread);
214 modelclock_t ourClock = currClock->getClock(thread);
216 /* Thread ID is too large or clock is too large. */
217 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
218 expandRecord(shadow);
219 fullRaceCheckRead(thread, shadow, currClock);
223 /* Check for datarace against last write. */
225 modelclock_t writeClock = WRITEVECTOR(shadowval);
226 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
228 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
229 /* We have a datarace */
233 modelclock_t readClock = READVECTOR(shadowval);
234 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
236 if (clock_may_race(currClock, thread, readClock, readThread)) {
237 /* We don't subsume this read... Have to expand record. */
238 expandRecord(shadow);
239 fullRaceCheckRead(thread, shadow, currClock);
243 *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);