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 if (clock_may_race(currClock, thread, readClock, readThread)) {
80 /* We have a datarace */
85 /* Check for datarace against last write. */
87 modelclock_t writeClock = record->writeClock;
88 thread_id_t writeThread = record->writeThread;
90 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
91 /* We have a datarace */
96 record->writeThread=thread;
97 modelclock_t ourClock = currClock->getClock(thread);
98 record->writeClock=ourClock;
101 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
102 uint64_t * shadow=lookupAddressEntry(location);
103 uint64_t shadowval=*shadow;
106 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
107 fullRaceCheckWrite(thread, shadow, currClock);
111 int threadid = id_to_int(thread);
112 modelclock_t ourClock = currClock->getClock(thread);
114 /* Thread ID is too large or clock is too large. */
115 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
116 expandRecord(shadow);
117 fullRaceCheckWrite(thread, shadow, currClock);
121 /* Check for datarace against last read. */
123 modelclock_t readClock = READVECTOR(shadowval);
124 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
126 if (clock_may_race(currClock, thread, readClock, readThread)) {
127 /* We have a datarace */
131 /* Check for datarace against last write. */
133 modelclock_t writeClock = WRITEVECTOR(shadowval);
134 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
136 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
137 /* We have a datarace */
140 *shadow = ENCODEOP(0, 0, threadid, ourClock);
143 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
144 struct RaceRecord * record=(struct RaceRecord *) (*shadow);
146 /* Check for datarace against last write. */
148 modelclock_t writeClock = record->writeClock;
149 thread_id_t writeThread = record->writeThread;
151 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
152 /* We have a datarace */
156 /* Shorten vector when possible */
160 for(int i=0;i<record->numReads;i++) {
161 modelclock_t readClock = record->readClock[i];
162 thread_id_t readThread = record->thread[i];
164 /* TODO: should this have different logic than all the other
165 * 'clock_may_race' calls? */
166 if (readThread != thread && currClock->getClock(readThread) <= readClock) {
167 /* Still need this read in vector */
168 if (copytoindex!=i) {
169 record->readClock[copytoindex]=record->readClock[i];
170 record->thread[copytoindex]=record->thread[i];
176 if (copytoindex>=record->capacity) {
177 int newCapacity=record->capacity*2;
178 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
179 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
180 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
181 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
182 free(record->readClock);
183 free(record->thread);
184 record->readClock=newreadClock;
185 record->thread=newthread;
186 record->capacity=newCapacity;
189 modelclock_t ourClock = currClock->getClock(thread);
191 record->thread[copytoindex]=thread;
192 record->readClock[copytoindex]=ourClock;
193 record->numReads=copytoindex+1;
196 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
197 uint64_t * shadow=lookupAddressEntry(location);
198 uint64_t shadowval=*shadow;
201 if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
202 fullRaceCheckRead(thread, shadow, currClock);
206 int threadid = id_to_int(thread);
207 modelclock_t ourClock = currClock->getClock(thread);
209 /* Thread ID is too large or clock is too large. */
210 if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
211 expandRecord(shadow);
212 fullRaceCheckRead(thread, shadow, currClock);
216 /* Check for datarace against last write. */
218 modelclock_t writeClock = WRITEVECTOR(shadowval);
219 thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
221 if (clock_may_race(currClock, thread, writeClock, writeThread)) {
222 /* We have a datarace */
226 modelclock_t readClock = READVECTOR(shadowval);
227 thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
229 if (clock_may_race(currClock, thread, readClock, readThread)) {
230 /* We don't subsume this read... Have to expand record. */
231 expandRecord(shadow);
232 fullRaceCheckRead(thread, shadow, currClock);
236 *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);