datarace.cc

   1 #include "datarace.h"
   2 #include "threads.h"
   3 #include <stdio.h>
   4 #include <cstring>
   5
   6 struct ShadowTable *root;
   7
   8 void initRaceDetector() {
   9         root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
  10 }
  11
  12 static uint64_t * lookupAddressEntry(void * address) {
  13         struct ShadowTable *currtable=root;
  14 #ifdef BIT48
  15         currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&0xffff];
  16         if (currtable==NULL) {
  17                 currtable=(struct ShadowTable *) (root->array[(((uintptr_t)address)>>32)&MASK16BIT]=calloc(sizeof(struct ShadowTable),1));
  18         }
  19 #endif
  20
  21         struct ShadowBaseTable * basetable=(struct ShadowBaseTable *) currtable->array[(((uintptr_t)address)>>16)&MASK16BIT];
  22         if (basetable==NULL) {
  23                 basetable=(struct ShadowBaseTable *) (currtable->array[(((uintptr_t)address)>>16)&MASK16BIT]=calloc(sizeof(struct ShadowBaseTable),1));
  24         }
  25         return &basetable->array[((uintptr_t)address)&MASK16BIT];
  26 }
  27
  28 /**
  29  * Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
  30  * to check the potential for a data race.
  31  * @param clock1 The current clock vector
  32  * @param tid1 The current thread; paired with clock1
  33  * @param clock2 The clock value for the potentially-racing action
  34  * @param tid2 The thread ID for the potentially-racing action
  35  * @return true if the current clock allows a race with the event at clock2/tid2
  36  */
  37 static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
  38                            modelclock_t clock2, thread_id_t tid2)
  39 {
  40         return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
  41 }
  42
  43 static void expandRecord(uint64_t * shadow) {
  44         uint64_t shadowval=*shadow;
  45
  46         modelclock_t readClock = READVECTOR(shadowval);
  47         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
  48         modelclock_t writeClock = WRITEVECTOR(shadowval);
  49         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
  50
  51         struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
  52         record->writeThread=writeThread;
  53         record->writeClock=writeClock;
  54
  55         if (readClock!=0) {
  56                 record->capacity=INITCAPACITY;
  57                 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
  58                 record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity);
  59                 record->numReads=1;
  60                 record->thread[0]=readThread;
  61                 record->readClock[0]=readClock;
  62         }
  63         *shadow=(uint64_t) record;
  64 }
  65
  66 static void reportDataRace() {
  67         printf("The reportDataRace method should report useful things about this datarace!\n");
  68 }
  69
  70 void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
  71         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
  72
  73         /* Check for datarace against last read. */
  74
  75         for(int i=0;i<record->numReads;i++) {
  76                 modelclock_t readClock = record->readClock[i];
  77                 thread_id_t readThread = record->thread[i];
  78
  79                 /* Note that readClock can't actuall be zero here, so it could be
  80                          optimized. */
  81
  82                 if (clock_may_race(currClock, thread, readClock, readThread)) {
  83                         /* We have a datarace */
  84                         reportDataRace();
  85                 }
  86         }
  87
  88         /* Check for datarace against last write. */
  89
  90         modelclock_t writeClock = record->writeClock;
  91         thread_id_t writeThread = record->writeThread;
  92
  93         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
  94                 /* We have a datarace */
  95                 reportDataRace();
  96         }
  97
  98         record->numReads=0;
  99         record->writeThread=thread;
 100         modelclock_t ourClock = currClock->getClock(thread);
 101         record->writeClock=ourClock;
 102 }
 103
 104 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
 105         uint64_t * shadow=lookupAddressEntry(location);
 106         uint64_t shadowval=*shadow;
 107
 108         /* Do full record */
 109         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 110                 fullRaceCheckWrite(thread, shadow, currClock);
 111                 return;
 112         }
 113
 114         int threadid = id_to_int(thread);
 115         modelclock_t ourClock = currClock->getClock(thread);
 116
 117         /* Thread ID is too large or clock is too large. */
 118         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 119                 expandRecord(shadow);
 120                 fullRaceCheckWrite(thread, shadow, currClock);
 121                 return;
 122         }
 123
 124         /* Check for datarace against last read. */
 125
 126         modelclock_t readClock = READVECTOR(shadowval);
 127         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 128
 129         if (clock_may_race(currClock, thread, readClock, readThread)) {
 130                 /* We have a datarace */
 131                 reportDataRace();
 132         }
 133
 134         /* Check for datarace against last write. */
 135
 136         modelclock_t writeClock = WRITEVECTOR(shadowval);
 137         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 138
 139         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 140                 /* We have a datarace */
 141                 reportDataRace();
 142         }
 143         *shadow = ENCODEOP(0, 0, threadid, ourClock);
 144 }
 145
 146 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
 147         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
 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();
 157         }
 158
 159         /* Shorten vector when possible */
 160
 161         int copytoindex=0;
 162
 163         for(int i=0;i<record->numReads;i++) {
 164                 modelclock_t readClock = record->readClock[i];
 165                 thread_id_t readThread = record->thread[i];
 166
 167                 /*  Note that is not really a datarace check as reads cannott
 168                                 actually race.  It is just determining that this read subsumes
 169                                 another in the sense that either this read races or neither
 170                                 read races. Note that readClock can't actually be zero, so it
 171                                 could be optimized.  */
 172
 173                 if (clock_may_race(currClock, thread, readClock, readThread)) {
 174                         /* Still need this read in vector */
 175                         if (copytoindex!=i) {
 176                                 record->readClock[copytoindex]=record->readClock[i];
 177                                 record->thread[copytoindex]=record->thread[i];
 178                         }
 179                         copytoindex++;
 180                 }
 181         }
 182
 183         if (copytoindex>=record->capacity) {
 184                 int newCapacity=record->capacity*2;
 185                 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
 186                 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
 187                 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
 188                 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
 189                 free(record->readClock);
 190                 free(record->thread);
 191                 record->readClock=newreadClock;
 192                 record->thread=newthread;
 193                 record->capacity=newCapacity;
 194         }
 195
 196         modelclock_t ourClock = currClock->getClock(thread);
 197
 198         record->thread[copytoindex]=thread;
 199         record->readClock[copytoindex]=ourClock;
 200         record->numReads=copytoindex+1;
 201 }
 202
 203 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
 204         uint64_t * shadow=lookupAddressEntry(location);
 205         uint64_t shadowval=*shadow;
 206
 207         /* Do full record */
 208         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 209                 fullRaceCheckRead(thread, shadow, currClock);
 210                 return;
 211         }
 212
 213         int threadid = id_to_int(thread);
 214         modelclock_t ourClock = currClock->getClock(thread);
 215
 216         /* Thread ID is too large or clock is too large. */
 217         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 218                 expandRecord(shadow);
 219                 fullRaceCheckRead(thread, shadow, currClock);
 220                 return;
 221         }
 222
 223         /* Check for datarace against last write. */
 224
 225         modelclock_t writeClock = WRITEVECTOR(shadowval);
 226         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 227
 228         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 229                 /* We have a datarace */
 230                 reportDataRace();
 231         }
 232
 233         modelclock_t readClock = READVECTOR(shadowval);
 234         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 235
 236         if (clock_may_race(currClock, thread, readClock, readThread)) {
 237                 /* We don't subsume this read... Have to expand record. */
 238                 expandRecord(shadow);
 239                 fullRaceCheckRead(thread, shadow, currClock);
 240                 return;
 241         }
 242
 243         *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);
 244 }