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 static void expandRecord(uint64_t * shadow) {
  29         uint64_t shadowval=*shadow;
  30
  31         int readClock = READVECTOR(shadowval);
  32         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
  33         int writeClock = WRITEVECTOR(shadowval);
  34         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
  35
  36         struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord));
  37         record->writeThread=writeThread;
  38         record->writeClock=writeClock;
  39
  40         if (readClock!=0) {
  41                 record->capacity=INITCAPACITY;
  42                 record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity);
  43                 record->readClock=(int *) malloc(sizeof(int)*record->capacity);
  44                 record->numReads=1;
  45                 record->thread[0]=readThread;
  46                 record->readClock[0]=readClock;
  47         }
  48         *shadow=(uint64_t) record;
  49 }
  50
  51 static void reportDataRace() {
  52         printf("The reportDataRace method should report useful things about this datarace!\n");
  53 }
  54
  55 void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
  56         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
  57
  58         /* Check for datarace against last read. */
  59
  60         for(int i=0;i<record->numReads;i++) {
  61                 int readClock = record->readClock[i];
  62                 thread_id_t readThread = record->thread[i];
  63
  64                 if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) {
  65                         /* We have a datarace */
  66                         reportDataRace();
  67                 }
  68         }
  69
  70         /* Check for datarace against last write. */
  71
  72         int writeClock = record->writeClock;
  73         thread_id_t writeThread = record->writeThread;
  74
  75         if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
  76                 /* We have a datarace */
  77                 reportDataRace();
  78         }
  79
  80         record->numReads=0;
  81         record->writeThread=thread;
  82         int ourClock = currClock->getClock(thread);
  83         record->writeClock=ourClock;
  84 }
  85
  86 void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) {
  87         uint64_t * shadow=lookupAddressEntry(location);
  88         uint64_t shadowval=*shadow;
  89
  90         /* Do full record */
  91         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
  92                 fullRaceCheckWrite(thread, shadow, currClock);
  93                 return;
  94         }
  95
  96         int threadid = id_to_int(thread);
  97         int ourClock = currClock->getClock(thread);
  98
  99         /* Thread ID is too large or clock is too large. */
 100         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 101                 expandRecord(shadow);
 102                 fullRaceCheckWrite(thread, shadow, currClock);
 103                 return;
 104         }
 105
 106         /* Check for datarace against last read. */
 107
 108         int readClock = READVECTOR(shadowval);
 109         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 110
 111         if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) {
 112                 /* We have a datarace */
 113                 reportDataRace();
 114         }
 115
 116         /* Check for datarace against last write. */
 117
 118         int writeClock = WRITEVECTOR(shadowval);
 119         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 120
 121         if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
 122                 /* We have a datarace */
 123                 reportDataRace();
 124         }
 125         *shadow = ENCODEOP(0, 0, threadid, ourClock);
 126 }
 127
 128 void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
 129         struct RaceRecord * record=(struct RaceRecord *) (*shadow);
 130
 131         /* Check for datarace against last write. */
 132
 133         int writeClock = record->writeClock;
 134         thread_id_t writeThread = record->writeThread;
 135
 136         if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
 137                 /* We have a datarace */
 138                 reportDataRace();
 139         }
 140
 141         /* Shorten vector when possible */
 142
 143         int copytoindex=0;
 144
 145         for(int i=0;i<record->numReads;i++) {
 146                 int readClock = record->readClock[i];
 147                 thread_id_t readThread = record->thread[i];
 148
 149                 if (readThread != thread && currClock->getClock(readThread) <= readClock) {
 150                         /* Still need this read in vector */
 151                         if (copytoindex!=i) {
 152                                 record->readClock[copytoindex]=record->readClock[i];
 153                                 record->thread[copytoindex]=record->thread[i];
 154                         }
 155                         copytoindex++;
 156                 }
 157         }
 158
 159         if (copytoindex>=record->capacity) {
 160                 int newCapacity=record->capacity*2;
 161                 thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity);
 162                 int * newreadClock=(int *) malloc(sizeof(int)*newCapacity);
 163                 std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t));
 164                 std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(int));
 165                 free(record->readClock);
 166                 free(record->thread);
 167                 record->readClock=newreadClock;
 168                 record->thread=newthread;
 169                 record->capacity=newCapacity;
 170         }
 171
 172         int ourClock = currClock->getClock(thread);
 173
 174         record->thread[copytoindex]=thread;
 175         record->readClock[copytoindex]=ourClock;
 176         record->numReads=copytoindex+1;
 177 }
 178
 179 void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) {
 180         uint64_t * shadow=lookupAddressEntry(location);
 181         uint64_t shadowval=*shadow;
 182
 183         /* Do full record */
 184         if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
 185                 fullRaceCheckRead(thread, shadow, currClock);
 186                 return;
 187         }
 188
 189         int threadid = id_to_int(thread);
 190         int ourClock = currClock->getClock(thread);
 191
 192         /* Thread ID is too large or clock is too large. */
 193         if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
 194                 expandRecord(shadow);
 195                 fullRaceCheckRead(thread, shadow, currClock);
 196                 return;
 197         }
 198
 199         /* Check for datarace against last write. */
 200
 201         int writeClock = WRITEVECTOR(shadowval);
 202         thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
 203
 204         if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
 205                 /* We have a datarace */
 206                 reportDataRace();
 207         }
 208
 209         int readClock = READVECTOR(shadowval);
 210         thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 211
 212         if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) {
 213                 /* We don't subsume this read... Have to expand record. */
 214                 expandRecord(shadow);
 215                 fullRaceCheckRead(thread, shadow, currClock);
 216                 return;
 217         }
 218
 219         *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);
 220 }