datarace.cc

   1 #include "datarace.h"
   2 #include "threads.h"
   3 #include <stdio.h>
   4 #include <cstring>
   5
   6 struct ShadowTable *root;
   7
   8 /** This function initialized the data race detector. */
   9
  10 void initRaceDetector() {
  11         root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
  12 }
  13
  14 /** This function looks up the entry in the shadow table corresponding
  15                 to a given address.*/
  16
  17 static uint64_t * lookupAddressEntry(void * address) {
  18         struct ShadowTable *currtable=root;
  19 #ifdef BIT48
  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));
  23         }
  24 #endif
  25
  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));
  29         }
  30         return &basetable->array[((uintptr_t)address)&MASK16BIT];
  31 }
  32
  33 /**
  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
  41  */
  42 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
  43                            modelclock_t clock2, thread_id_t tid2)
  44 {
  45         return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
  46 }
  47
  48 /**
  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
  51  * stamps. */
  52
  53 static void expandRecord(uint64_t * shadow) {
  54         uint64_t shadowval=*shadow;
  55
  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));
  60
  61         struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
  62         record->writeThread=writeThread;
  63         record->writeClock=writeClock;
  64
  65         if (readClock!=0) {
  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);
  69                 record->numReads=1;
  70                 record->thread[0]=readThread;
  71                 record->readClock[0]=readClock;
  72         }
  73         *shadow=(uint64_t) record;
  74 }
  75
  76 /** This function is called when we detect a data race.*/
  77
  78 static void reportDataRace() {
  79         printf("The reportDataRace method should report useful things about this datarace!\n");
  80 }
  81
  82 /** This function does race detection for a write on an expanded
  83  *              record. */
  84
  85 void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
  86         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
  87
  88         /* Check for datarace against last read. */
  89
  90         for(int i=0;i<record->numReads;i++) {
  91                 modelclock_t readClock = record->readClock[i];
  92                 thread_id_t readThread = record->thread[i];
  93
  94                 /* Note that readClock can't actuall be zero here, so it could be
  95                          optimized. */
  96
  97                 if (clock_may_race(currClock, thread, readClock, readThread)) {
  98                         /* We have a datarace */
  99                         reportDataRace();
 100                 }
 101         }
 102
 103         /* Check for datarace against last write. */
 104
 105         modelclock_t writeClock = record->writeClock;
 106         thread_id_t writeThread = record->writeThread;
 107
 108         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 109                 /* We have a datarace */
 110                 reportDataRace();
 111         }
 112
 113         record->numReads=0;
 114         record->writeThread=thread;
 115         modelclock_t ourClock = currClock->getClock(thread);
 116         record->writeClock=ourClock;
 117 }
 118
 119 /** This function does race detection on a write.
 120  */
 121
 122 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
 123         uint64_t * shadow=lookupAddressEntry(location);
 124         uint64_t shadowval=*shadow;
 125
 126         /* Do full record */
 127         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 128                 fullRaceCheckWrite(thread, shadow, currClock);
 129                 return;
 130         }
 131
 132         int threadid = id_to_int(thread);
 133         modelclock_t ourClock = currClock->getClock(thread);
 134
 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);
 139                 return;
 140         }
 141
 142         /* Check for datarace against last read. */
 143
 144         modelclock_t readClock = READVECTOR(shadowval);
 145         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 146
 147         if (clock_may_race(currClock, thread, readClock, readThread)) {
 148                 /* We have a datarace */
 149                 reportDataRace();
 150         }
 151
 152         /* Check for datarace against last write. */
 153
 154         modelclock_t writeClock = WRITEVECTOR(shadowval);
 155         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 156
 157         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 158                 /* We have a datarace */
 159                 reportDataRace();
 160         }
 161         *shadow = ENCODEOP(0, 0, threadid, ourClock);
 162 }
 163
 164 /** This function does race detection on a read for an expanded
 165  *      record. */
 166
 167 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
 168         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
 169
 170         /* Check for datarace against last write. */
 171
 172         modelclock_t writeClock = record->writeClock;
 173         thread_id_t writeThread = record->writeThread;
 174
 175         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 176                 /* We have a datarace */
 177                 reportDataRace();
 178         }
 179
 180         /* Shorten vector when possible */
 181
 182         int copytoindex=0;
 183
 184         for(int i=0;i<record->numReads;i++) {
 185                 modelclock_t readClock = record->readClock[i];
 186                 thread_id_t readThread = record->thread[i];
 187
 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.  */
 193
 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];
 199                         }
 200                         copytoindex++;
 201                 }
 202         }
 203
 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;
 215         }
 216
 217         modelclock_t ourClock = currClock->getClock(thread);
 218
 219         record->thread[copytoindex]=thread;
 220         record->readClock[copytoindex]=ourClock;
 221         record->numReads=copytoindex+1;
 222 }
 223
 224 /** This function does race detection on a read. */
 225
 226 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
 227         uint64_t * shadow=lookupAddressEntry(location);
 228         uint64_t shadowval=*shadow;
 229
 230         /* Do full record */
 231         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 232                 fullRaceCheckRead(thread, shadow, currClock);
 233                 return;
 234         }
 235
 236         int threadid = id_to_int(thread);
 237         modelclock_t ourClock = currClock->getClock(thread);
 238
 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);
 243                 return;
 244         }
 245
 246         /* Check for datarace against last write. */
 247
 248         modelclock_t writeClock = WRITEVECTOR(shadowval);
 249         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 250
 251         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 252                 /* We have a datarace */
 253                 reportDataRace();
 254         }
 255
 256         modelclock_t readClock = READVECTOR(shadowval);
 257         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 258
 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);
 263                 return;
 264         }
 265
 266         *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);
 267 }