datarace.cc

   1 #include "datarace.h"
   2 #include "model.h"
   3 #include "threads.h"
   4 #include <stdio.h>
   5 #include <cstring>
   6
   7 struct ShadowTable *root;
   8 std::vector<struct DataRace *> unrealizedraces;
   9
  10 /** This function initialized the data race detector. */
  11 void initRaceDetector() {
  12         root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
  13 }
  14
  15 /** This function looks up the entry in the shadow table corresponding to a
  16  * given address.*/
  17 static uint64_t * lookupAddressEntry(void * address) {
  18         struct ShadowTable *currtable=root;
  19 #if 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 static void expandRecord(uint64_t * shadow) {
  53         uint64_t shadowval=*shadow;
  54
  55         modelclock_t readClock = READVECTOR(shadowval);
  56         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
  57         modelclock_t writeClock = WRITEVECTOR(shadowval);
  58         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
  59
  60         struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
  61         record->writeThread=writeThread;
  62         record->writeClock=writeClock;
  63
  64         if (readClock!=0) {
  65                 record->capacity=INITCAPACITY;
  66                 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
  67                 record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity);
  68                 record->numReads=1;
  69                 record->thread[0]=readThread;
  70                 record->readClock[0]=readClock;
  71         }
  72         *shadow=(uint64_t) record;
  73 }
  74
  75 /** This function is called when we detect a data race.*/
  76 static void reportDataRace(thread_id_t oldthread, modelclock_t oldclock, bool isoldwrite, ModelAction *newaction, bool isnewwrite, void *address) {
  77         struct DataRace * race=(struct DataRace *)malloc(sizeof(struct DataRace));
  78         race->oldthread=oldthread;
  79         race->oldclock=oldclock;
  80         race->isoldwrite=isoldwrite;
  81         race->newaction=newaction;
  82         race->isnewwrite=isnewwrite;
  83         race->address=address;
  84         unrealizedraces.push_back(race);
  85
  86         /* If the race is realized, bail out now. */
  87         if (checkDataRaces()) {
  88                 model->set_assert();
  89                 model->switch_to_master(NULL);
  90         }
  91 }
  92
  93 /** This function goes through the list of unrealized data races,
  94  *      removes the impossible ones, and print the realized ones. */
  95
  96 bool checkDataRaces() {
  97         if (model->isfeasibleprefix()) {
  98                 /* Prune the non-racing unrealized dataraces */
  99                 unsigned int i,newloc=0;
 100                 for(i=0;i<unrealizedraces.size();i++) {
 101                         struct DataRace * race=unrealizedraces[i];
 102                         if (clock_may_race(race->newaction->get_cv(), race->newaction->get_tid(), race->oldclock, race->oldthread)) {
 103                                 unrealizedraces[newloc++]=race;
 104                         }
 105                 }
 106                 if (newloc!=i)
 107                         unrealizedraces.resize(newloc);
 108
 109                 if (unrealizedraces.size()!=0) {
 110                         /* We have an actual realized race. */
 111                         for(i=0;i<unrealizedraces.size();i++) {
 112                                 struct DataRace * race=unrealizedraces[i];
 113                                 printRace(race);
 114                         }
 115                         return true;
 116                 }
 117         }
 118         return false;
 119 }
 120
 121 void printRace(struct DataRace * race) {
 122         printf("Datarace detected\n");
 123         printf("Location %p\n", race->address);
 124         printf("Initial access: thread %u clock %u, iswrite %u\n",race->oldthread,race->oldclock, race->isoldwrite);
 125         printf("Second access: thread %u clock %u, iswrite %u\n", race->newaction->get_tid(), race->newaction->get_seq_number() , race->isnewwrite);
 126 }
 127
 128 /** This function does race detection for a write on an expanded record. */
 129 void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
 130         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
 131
 132         /* Check for datarace against last read. */
 133
 134         for(int i=0;i<record->numReads;i++) {
 135                 modelclock_t readClock = record->readClock[i];
 136                 thread_id_t readThread = record->thread[i];
 137
 138                 /* Note that readClock can't actuall be zero here, so it could be
 139                          optimized. */
 140
 141                 if (clock_may_race(currClock, thread, readClock, readThread)) {
 142                         /* We have a datarace */
 143                         reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
 144                 }
 145         }
 146
 147         /* Check for datarace against last write. */
 148
 149         modelclock_t writeClock = record->writeClock;
 150         thread_id_t writeThread = record->writeThread;
 151
 152         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 153                 /* We have a datarace */
 154                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
 155         }
 156
 157         record->numReads=0;
 158         record->writeThread=thread;
 159         modelclock_t ourClock = currClock->getClock(thread);
 160         record->writeClock=ourClock;
 161 }
 162
 163 /** This function does race detection on a write. */
 164 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
 165         uint64_t * shadow=lookupAddressEntry(location);
 166         uint64_t shadowval=*shadow;
 167
 168         /* Do full record */
 169         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 170                 fullRaceCheckWrite(thread, location, shadow, currClock);
 171                 return;
 172         }
 173
 174         int threadid = id_to_int(thread);
 175         modelclock_t ourClock = currClock->getClock(thread);
 176
 177         /* Thread ID is too large or clock is too large. */
 178         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 179                 expandRecord(shadow);
 180                 fullRaceCheckWrite(thread, location, shadow, currClock);
 181                 return;
 182         }
 183
 184         /* Check for datarace against last read. */
 185
 186         modelclock_t readClock = READVECTOR(shadowval);
 187         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 188
 189         if (clock_may_race(currClock, thread, readClock, readThread)) {
 190                 /* We have a datarace */
 191                 reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
 192         }
 193
 194         /* Check for datarace against last write. */
 195
 196         modelclock_t writeClock = WRITEVECTOR(shadowval);
 197         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 198
 199         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 200                 /* We have a datarace */
 201                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
 202         }
 203         *shadow = ENCODEOP(0, 0, threadid, ourClock);
 204 }
 205
 206 /** This function does race detection on a read for an expanded record. */
 207 void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) {
 208         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
 209
 210         /* Check for datarace against last write. */
 211
 212         modelclock_t writeClock = record->writeClock;
 213         thread_id_t writeThread = record->writeThread;
 214
 215         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 216                 /* We have a datarace */
 217                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
 218         }
 219
 220         /* Shorten vector when possible */
 221
 222         int copytoindex=0;
 223
 224         for(int i=0;i<record->numReads;i++) {
 225                 modelclock_t readClock = record->readClock[i];
 226                 thread_id_t readThread = record->thread[i];
 227
 228                 /*  Note that is not really a datarace check as reads cannott
 229                                 actually race.  It is just determining that this read subsumes
 230                                 another in the sense that either this read races or neither
 231                                 read races. Note that readClock can't actually be zero, so it
 232                                 could be optimized.  */
 233
 234                 if (clock_may_race(currClock, thread, readClock, readThread)) {
 235                         /* Still need this read in vector */
 236                         if (copytoindex!=i) {
 237                                 record->readClock[copytoindex]=record->readClock[i];
 238                                 record->thread[copytoindex]=record->thread[i];
 239                         }
 240                         copytoindex++;
 241                 }
 242         }
 243
 244         if (copytoindex>=record->capacity) {
 245                 int newCapacity=record->capacity*2;
 246                 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
 247                 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
 248                 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
 249                 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
 250                 free(record->readClock);
 251                 free(record->thread);
 252                 record->readClock=newreadClock;
 253                 record->thread=newthread;
 254                 record->capacity=newCapacity;
 255         }
 256
 257         modelclock_t ourClock = currClock->getClock(thread);
 258
 259         record->thread[copytoindex]=thread;
 260         record->readClock[copytoindex]=ourClock;
 261         record->numReads=copytoindex+1;
 262 }
 263
 264 /** This function does race detection on a read. */
 265 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
 266         uint64_t * shadow=lookupAddressEntry(location);
 267         uint64_t shadowval=*shadow;
 268
 269         /* Do full record */
 270         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 271                 fullRaceCheckRead(thread, location, shadow, currClock);
 272                 return;
 273         }
 274
 275         int threadid = id_to_int(thread);
 276         modelclock_t ourClock = currClock->getClock(thread);
 277
 278         /* Thread ID is too large or clock is too large. */
 279         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 280                 expandRecord(shadow);
 281                 fullRaceCheckRead(thread, location, shadow, currClock);
 282                 return;
 283         }
 284
 285         /* Check for datarace against last write. */
 286
 287         modelclock_t writeClock = WRITEVECTOR(shadowval);
 288         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 289
 290         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 291                 /* We have a datarace */
 292                 reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
 293         }
 294
 295         modelclock_t readClock = READVECTOR(shadowval);
 296         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 297
 298         if (clock_may_race(currClock, thread, readClock, readThread)) {
 299                 /* We don't subsume this read... Have to expand record. */
 300                 expandRecord(shadow);
 301                 fullRaceCheckRead(thread, location, shadow, currClock);
 302                 return;
 303         }
 304
 305         *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock);
 306 }