datarace.cc

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