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