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 void initRaceDetector() {
  10         root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
  11 }
  12
  13 /** This function looks up the entry in the shadow table corresponding to a
  14  * given address.*/
  15 static uint64_t * lookupAddressEntry(void * address) {
  16         struct ShadowTable *currtable=root;
  17 #if BIT48
  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));
  21         }
  22 #endif
  23
  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));
  27         }
  28         return &basetable->array[((uintptr_t)address)&MASK16BIT];
  29 }
  30
  31 /**
  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
  39  */
  40 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
  41                            modelclock_t clock2, thread_id_t tid2)
  42 {
  43         return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
  44 }
  45
  46 /**
  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
  49  * stamps. */
  50 static void expandRecord(uint64_t * shadow) {
  51         uint64_t shadowval=*shadow;
  52
  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));
  57
  58         struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
  59         record->writeThread=writeThread;
  60         record->writeClock=writeClock;
  61
  62         if (readClock!=0) {
  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);
  66                 record->numReads=1;
  67                 record->thread[0]=readThread;
  68                 record->readClock[0]=readClock;
  69         }
  70         *shadow=(uint64_t) record;
  71 }
  72
  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");
  76 }
  77
  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);
  81
  82         /* Check for datarace against last read. */
  83
  84         for(int i=0;i<record->numReads;i++) {
  85                 modelclock_t readClock = record->readClock[i];
  86                 thread_id_t readThread = record->thread[i];
  87
  88                 /* Note that readClock can't actuall be zero here, so it could be
  89                          optimized. */
  90
  91                 if (clock_may_race(currClock, thread, readClock, readThread)) {
  92                         /* We have a datarace */
  93                         reportDataRace();
  94                 }
  95         }
  96
  97         /* Check for datarace against last write. */
  98
  99         modelclock_t writeClock = record->writeClock;
 100         thread_id_t writeThread = record->writeThread;
 101
 102         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 103                 /* We have a datarace */
 104                 reportDataRace();
 105         }
 106
 107         record->numReads=0;
 108         record->writeThread=thread;
 109         modelclock_t ourClock = currClock->getClock(thread);
 110         record->writeClock=ourClock;
 111 }
 112
 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;
 117
 118         /* Do full record */
 119         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 120                 fullRaceCheckWrite(thread, shadow, currClock);
 121                 return;
 122         }
 123
 124         int threadid = id_to_int(thread);
 125         modelclock_t ourClock = currClock->getClock(thread);
 126
 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);
 131                 return;
 132         }
 133
 134         /* Check for datarace against last read. */
 135
 136         modelclock_t readClock = READVECTOR(shadowval);
 137         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 138
 139         if (clock_may_race(currClock, thread, readClock, readThread)) {
 140                 /* We have a datarace */
 141                 reportDataRace();
 142         }
 143
 144         /* Check for datarace against last write. */
 145
 146         modelclock_t writeClock = WRITEVECTOR(shadowval);
 147         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 148
 149         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 150                 /* We have a datarace */
 151                 reportDataRace();
 152         }
 153         *shadow = ENCODEOP(0, 0, threadid, ourClock);
 154 }
 155
 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);
 159
 160         /* Check for datarace against last write. */
 161
 162         modelclock_t writeClock = record->writeClock;
 163         thread_id_t writeThread = record->writeThread;
 164
 165         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 166                 /* We have a datarace */
 167                 reportDataRace();
 168         }
 169
 170         /* Shorten vector when possible */
 171
 172         int copytoindex=0;
 173
 174         for(int i=0;i<record->numReads;i++) {
 175                 modelclock_t readClock = record->readClock[i];
 176                 thread_id_t readThread = record->thread[i];
 177
 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.  */
 183
 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];
 189                         }
 190                         copytoindex++;
 191                 }
 192         }
 193
 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;
 205         }
 206
 207         modelclock_t ourClock = currClock->getClock(thread);
 208
 209         record->thread[copytoindex]=thread;
 210         record->readClock[copytoindex]=ourClock;
 211         record->numReads=copytoindex+1;
 212 }
 213
 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;
 218
 219         /* Do full record */
 220         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 221                 fullRaceCheckRead(thread, shadow, currClock);
 222                 return;
 223         }
 224
 225         int threadid = id_to_int(thread);
 226         modelclock_t ourClock = currClock->getClock(thread);
 227
 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);
 232                 return;
 233         }
 234
 235         /* Check for datarace against last write. */
 236
 237         modelclock_t writeClock = WRITEVECTOR(shadowval);
 238         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 239
 240         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 241                 /* We have a datarace */
 242                 reportDataRace();
 243         }
 244
 245         modelclock_t readClock = READVECTOR(shadowval);
 246         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 247
 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);
 252                 return;
 253         }
 254
 255         *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);
 256 }