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                 if (clock_may_race(currClock, thread, readClock, readThread)) {
  80                         /* We have a datarace */
  81                         reportDataRace();
  82                 }
  83         }
  84
  85         /* Check for datarace against last write. */
  86
  87         modelclock_t writeClock = record->writeClock;
  88         thread_id_t writeThread = record->writeThread;
  89
  90         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
  91                 /* We have a datarace */
  92                 reportDataRace();
  93         }
  94
  95         record->numReads=0;
  96         record->writeThread=thread;
  97         modelclock_t ourClock = currClock->getClock(thread);
  98         record->writeClock=ourClock;
  99 }
 100
 101 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
 102         uint64_t * shadow=lookupAddressEntry(location);
 103         uint64_t shadowval=*shadow;
 104
 105         /* Do full record */
 106         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 107                 fullRaceCheckWrite(thread, shadow, currClock);
 108                 return;
 109         }
 110
 111         int threadid = id_to_int(thread);
 112         modelclock_t ourClock = currClock->getClock(thread);
 113
 114         /* Thread ID is too large or clock is too large. */
 115         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 116                 expandRecord(shadow);
 117                 fullRaceCheckWrite(thread, shadow, currClock);
 118                 return;
 119         }
 120
 121         /* Check for datarace against last read. */
 122
 123         modelclock_t readClock = READVECTOR(shadowval);
 124         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 125
 126         if (clock_may_race(currClock, thread, readClock, readThread)) {
 127                 /* We have a datarace */
 128                 reportDataRace();
 129         }
 130
 131         /* Check for datarace against last write. */
 132
 133         modelclock_t writeClock = WRITEVECTOR(shadowval);
 134         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 135
 136         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 137                 /* We have a datarace */
 138                 reportDataRace();
 139         }
 140         *shadow = ENCODEOP(0, 0, threadid, ourClock);
 141 }
 142
 143 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
 144         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
 145
 146         /* Check for datarace against last write. */
 147
 148         modelclock_t writeClock = record->writeClock;
 149         thread_id_t writeThread = record->writeThread;
 150
 151         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 152                 /* We have a datarace */
 153                 reportDataRace();
 154         }
 155
 156         /* Shorten vector when possible */
 157
 158         int copytoindex=0;
 159
 160         for(int i=0;i<record->numReads;i++) {
 161                 modelclock_t readClock = record->readClock[i];
 162                 thread_id_t readThread = record->thread[i];
 163
 164                 /* TODO: should this have different logic than all the other
 165                  * 'clock_may_race' calls? */
 166                 if (readThread != thread && currClock->getClock(readThread) <= readClock) {
 167                         /* Still need this read in vector */
 168                         if (copytoindex!=i) {
 169                                 record->readClock[copytoindex]=record->readClock[i];
 170                                 record->thread[copytoindex]=record->thread[i];
 171                         }
 172                         copytoindex++;
 173                 }
 174         }
 175
 176         if (copytoindex>=record->capacity) {
 177                 int newCapacity=record->capacity*2;
 178                 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
 179                 modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity);
 180                 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
 181                 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t));
 182                 free(record->readClock);
 183                 free(record->thread);
 184                 record->readClock=newreadClock;
 185                 record->thread=newthread;
 186                 record->capacity=newCapacity;
 187         }
 188
 189         modelclock_t ourClock = currClock->getClock(thread);
 190
 191         record->thread[copytoindex]=thread;
 192         record->readClock[copytoindex]=ourClock;
 193         record->numReads=copytoindex+1;
 194 }
 195
 196 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
 197         uint64_t * shadow=lookupAddressEntry(location);
 198         uint64_t shadowval=*shadow;
 199
 200         /* Do full record */
 201         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 202                 fullRaceCheckRead(thread, shadow, currClock);
 203                 return;
 204         }
 205
 206         int threadid = id_to_int(thread);
 207         modelclock_t ourClock = currClock->getClock(thread);
 208
 209         /* Thread ID is too large or clock is too large. */
 210         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 211                 expandRecord(shadow);
 212                 fullRaceCheckRead(thread, shadow, currClock);
 213                 return;
 214         }
 215
 216         /* Check for datarace against last write. */
 217
 218         modelclock_t writeClock = WRITEVECTOR(shadowval);
 219         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 220
 221         if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 222                 /* We have a datarace */
 223                 reportDataRace();
 224         }
 225
 226         modelclock_t readClock = READVECTOR(shadowval);
 227         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 228
 229         if (clock_may_race(currClock, thread, readClock, readThread)) {
 230                 /* We don't subsume this read... Have to expand record. */
 231                 expandRecord(shadow);
 232                 fullRaceCheckRead(thread, shadow, currClock);
 233                 return;
 234         }
 235
 236         *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);
 237 }