X-Git-Url: http://plrg.eecs.uci.edu/git/?p=cdsspec-compiler.git;a=blobdiff_plain;f=datarace.cc;h=653039b3307e3ebfb195e2dc99efda36ae123a7c;hp=1cc407bb991889545210f54ec313ae84c49cf412;hb=741d3d1160343d8545a783a2d05d3d0562b1c737;hpb=3c82af9a449b5cb3322809fd195a02e4a2ae37f4 diff --git a/datarace.cc b/datarace.cc index 1cc407b..653039b 100644 --- a/datarace.cc +++ b/datarace.cc @@ -1,33 +1,62 @@ #include "datarace.h" #include "model.h" -#include "threads.h" +#include "threads-model.h" #include #include - -struct ShadowTable *root; -std::vector unrealizedraces; +#include "mymemory.h" +#include "clockvector.h" +#include "config.h" +#include "action.h" +#include "execution.h" +#include "stl-model.h" + +static struct ShadowTable *root; +static SnapVector *unrealizedraces; +static void *memory_base; +static void *memory_top; + +static const ModelExecution * get_execution() +{ + return model->get_execution(); +} /** This function initialized the data race detector. */ -void initRaceDetector() { - root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1); +void initRaceDetector() +{ + root = (struct ShadowTable *)snapshot_calloc(sizeof(struct ShadowTable), 1); + memory_base = snapshot_calloc(sizeof(struct ShadowBaseTable) * SHADOWBASETABLES, 1); + memory_top = ((char *)memory_base) + sizeof(struct ShadowBaseTable) * SHADOWBASETABLES; + unrealizedraces = new SnapVector(); +} + +void * table_calloc(size_t size) +{ + if ((((char *)memory_base) + size) > memory_top) { + return snapshot_calloc(size, 1); + } else { + void *tmp = memory_base; + memory_base = ((char *)memory_base) + size; + return tmp; + } } /** This function looks up the entry in the shadow table corresponding to a * given address.*/ -static uint64_t * lookupAddressEntry(void * address) { - struct ShadowTable *currtable=root; +static uint64_t * lookupAddressEntry(const void *address) +{ + struct ShadowTable *currtable = root; #if BIT48 - currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&MASK16BIT]; - if (currtable==NULL) { - currtable=(struct ShadowTable *) (root->array[(((uintptr_t)address)>>32)&MASK16BIT]=calloc(sizeof(struct ShadowTable),1)); + currtable = (struct ShadowTable *) currtable->array[(((uintptr_t)address) >> 32) & MASK16BIT]; + if (currtable == NULL) { + currtable = (struct ShadowTable *)(root->array[(((uintptr_t)address) >> 32) & MASK16BIT] = table_calloc(sizeof(struct ShadowTable))); } #endif - struct ShadowBaseTable * basetable=(struct ShadowBaseTable *) currtable->array[(((uintptr_t)address)>>16)&MASK16BIT]; - if (basetable==NULL) { - basetable=(struct ShadowBaseTable *) (currtable->array[(((uintptr_t)address)>>16)&MASK16BIT]=calloc(sizeof(struct ShadowBaseTable),1)); + struct ShadowBaseTable *basetable = (struct ShadowBaseTable *)currtable->array[(((uintptr_t)address) >> 16) & MASK16BIT]; + if (basetable == NULL) { + basetable = (struct ShadowBaseTable *)(currtable->array[(((uintptr_t)address) >> 16) & MASK16BIT] = table_calloc(sizeof(struct ShadowBaseTable))); } - return &basetable->array[((uintptr_t)address)&MASK16BIT]; + return &basetable->array[((uintptr_t)address) & MASK16BIT]; } /** @@ -49,89 +78,107 @@ static bool clock_may_race(ClockVector *clock1, thread_id_t tid1, * Expands a record from the compact form to the full form. This is * necessary for multiple readers or for very large thread ids or time * stamps. */ -static void expandRecord(uint64_t * shadow) { - uint64_t shadowval=*shadow; +static void expandRecord(uint64_t *shadow) +{ + uint64_t shadowval = *shadow; modelclock_t readClock = READVECTOR(shadowval); thread_id_t readThread = int_to_id(RDTHREADID(shadowval)); modelclock_t writeClock = WRITEVECTOR(shadowval); thread_id_t writeThread = int_to_id(WRTHREADID(shadowval)); - struct RaceRecord * record=(struct RaceRecord *)calloc(1,sizeof(struct RaceRecord)); - record->writeThread=writeThread; - record->writeClock=writeClock; - - if (readClock!=0) { - record->capacity=INITCAPACITY; - record->thread=(thread_id_t *) malloc(sizeof(thread_id_t)*record->capacity); - record->readClock=(modelclock_t *) malloc(sizeof(modelclock_t)*record->capacity); - record->numReads=1; - record->thread[0]=readThread; - record->readClock[0]=readClock; + struct RaceRecord *record = (struct RaceRecord *)snapshot_calloc(1, sizeof(struct RaceRecord)); + record->writeThread = writeThread; + record->writeClock = writeClock; + + if (readClock != 0) { + record->capacity = INITCAPACITY; + record->thread = (thread_id_t *)snapshot_malloc(sizeof(thread_id_t) * record->capacity); + record->readClock = (modelclock_t *)snapshot_malloc(sizeof(modelclock_t) * record->capacity); + record->numReads = 1; + record->thread[0] = readThread; + record->readClock[0] = readClock; } - *shadow=(uint64_t) record; + *shadow = (uint64_t) record; } /** This function is called when we detect a data race.*/ -static void reportDataRace(thread_id_t oldthread, modelclock_t oldclock, bool isoldwrite, ModelAction *newaction, bool isnewwrite, void *address) { - struct DataRace * race=(struct DataRace *)malloc(sizeof(struct DataRace)); - race->oldthread=oldthread; - race->oldclock=oldclock; - race->isoldwrite=isoldwrite; - race->newaction=newaction; - race->isnewwrite=isnewwrite; - race->address=address; - unrealizedraces.push_back(race); +static void reportDataRace(thread_id_t oldthread, modelclock_t oldclock, bool isoldwrite, ModelAction *newaction, bool isnewwrite, const void *address) +{ + struct DataRace *race = (struct DataRace *)snapshot_malloc(sizeof(struct DataRace)); + race->oldthread = oldthread; + race->oldclock = oldclock; + race->isoldwrite = isoldwrite; + race->newaction = newaction; + race->isnewwrite = isnewwrite; + race->address = address; + unrealizedraces->push_back(race); /* If the race is realized, bail out now. */ - if (checkDataRaces()) { - model->set_assert(); + if (checkDataRaces()) model->switch_to_master(NULL); - } } -/** This function goes through the list of unrealized data races, - * removes the impossible ones, and print the realized ones. */ - -bool checkDataRaces() { - if (model->isfeasibleprefix()) { +/** + * @brief Check and report data races + * + * If the trace is feasible (a feasible prefix), clear out the list of + * unrealized data races, asserting any realized ones as execution bugs so that + * the model-checker will end the execution. + * + * @return True if any data races were realized + */ +bool checkDataRaces() +{ + if (get_execution()->isfeasibleprefix()) { + bool race_asserted = false; /* Prune the non-racing unrealized dataraces */ - unsigned int i,newloc=0; - for(i=0;isize(); i++) { + struct DataRace *race = (*unrealizedraces)[i]; if (clock_may_race(race->newaction->get_cv(), race->newaction->get_tid(), race->oldclock, race->oldthread)) { - unrealizedraces[newloc++]=race; - } - } - if (newloc!=i) - unrealizedraces.resize(newloc); - - if (unrealizedraces.size()!=0) { - /* We have an actual realized race. */ - for(i=0;iclear(); + return race_asserted; } return false; } -void printRace(struct DataRace * race) { - printf("Datarace detected\n"); - printf("Location %p\n", race->address); - printf("Initial access: thread %u clock %u, iswrite %u\n",race->oldthread,race->oldclock, race->isoldwrite); - printf("Second access: thread %u clock %u, iswrite %u\n", race->newaction->get_tid(), race->newaction->get_seq_number() , race->isnewwrite); +/** + * @brief Assert a data race + * + * Asserts a data race which is currently realized, causing the execution to + * end and stashing a message in the model-checker's bug list + * + * @param race The race to report + */ +void assert_race(struct DataRace *race) +{ + model->assert_bug( + "Data race detected @ address %p:\n" + " Access 1: %5s in thread %2d @ clock %3u\n" + " Access 2: %5s in thread %2d @ clock %3u", + race->address, + race->isoldwrite ? "write" : "read", + id_to_int(race->oldthread), + race->oldclock, + race->isnewwrite ? "write" : "read", + id_to_int(race->newaction->get_tid()), + race->newaction->get_seq_number() + ); } /** This function does race detection for a write on an expanded record. */ -void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) { - struct RaceRecord * record=(struct RaceRecord *) (*shadow); +void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t *shadow, ClockVector *currClock) +{ + struct RaceRecord *record = (struct RaceRecord *)(*shadow); /* Check for datarace against last read. */ - for(int i=0;inumReads;i++) { + for (int i = 0; i < record->numReads; i++) { modelclock_t readClock = record->readClock[i]; thread_id_t readThread = record->thread[i]; @@ -140,7 +187,7 @@ void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, C if (clock_may_race(currClock, thread, readClock, readThread)) { /* We have a datarace */ - reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location); + reportDataRace(readThread, readClock, false, get_execution()->get_parent_action(thread), true, location); } } @@ -151,22 +198,24 @@ void fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t * shadow, C if (clock_may_race(currClock, thread, writeClock, writeThread)) { /* We have a datarace */ - reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location); + reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), true, location); } - record->numReads=0; - record->writeThread=thread; + record->numReads = 0; + record->writeThread = thread; modelclock_t ourClock = currClock->getClock(thread); - record->writeClock=ourClock; + record->writeClock = ourClock; } /** This function does race detection on a write. */ -void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) { - uint64_t * shadow=lookupAddressEntry(location); - uint64_t shadowval=*shadow; +void raceCheckWrite(thread_id_t thread, void *location) +{ + uint64_t *shadow = lookupAddressEntry(location); + uint64_t shadowval = *shadow; + ClockVector *currClock = get_execution()->get_cv(thread); /* Do full record */ - if (shadowval!=0&&!ISSHORTRECORD(shadowval)) { + if (shadowval != 0 && !ISSHORTRECORD(shadowval)) { fullRaceCheckWrite(thread, location, shadow, currClock); return; } @@ -188,7 +237,7 @@ void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) if (clock_may_race(currClock, thread, readClock, readThread)) { /* We have a datarace */ - reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location); + reportDataRace(readThread, readClock, false, get_execution()->get_parent_action(thread), true, location); } /* Check for datarace against last write. */ @@ -198,14 +247,15 @@ void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) if (clock_may_race(currClock, thread, writeClock, writeThread)) { /* We have a datarace */ - reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location); + reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), true, location); } *shadow = ENCODEOP(0, 0, threadid, ourClock); } /** This function does race detection on a read for an expanded record. */ -void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, ClockVector *currClock) { - struct RaceRecord * record=(struct RaceRecord *) (*shadow); +void fullRaceCheckRead(thread_id_t thread, const void *location, uint64_t *shadow, ClockVector *currClock) +{ + struct RaceRecord *record = (struct RaceRecord *) (*shadow); /* Check for datarace against last write. */ @@ -214,14 +264,14 @@ void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, Cl if (clock_may_race(currClock, thread, writeClock, writeThread)) { /* We have a datarace */ - reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location); + reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), false, location); } /* Shorten vector when possible */ - int copytoindex=0; + int copytoindex = 0; - for(int i=0;inumReads;i++) { + for (int i = 0; i < record->numReads; i++) { modelclock_t readClock = record->readClock[i]; thread_id_t readThread = record->thread[i]; @@ -233,41 +283,43 @@ void fullRaceCheckRead(thread_id_t thread, void *location, uint64_t * shadow, Cl if (clock_may_race(currClock, thread, readClock, readThread)) { /* Still need this read in vector */ - if (copytoindex!=i) { - record->readClock[copytoindex]=record->readClock[i]; - record->thread[copytoindex]=record->thread[i]; + if (copytoindex != i) { + record->readClock[copytoindex] = record->readClock[i]; + record->thread[copytoindex] = record->thread[i]; } copytoindex++; } } - if (copytoindex>=record->capacity) { - int newCapacity=record->capacity*2; - thread_id_t *newthread=(thread_id_t *) malloc(sizeof(thread_id_t)*newCapacity); - modelclock_t * newreadClock=(modelclock_t *) malloc(sizeof(modelclock_t)*newCapacity); - std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t)); - std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(modelclock_t)); - free(record->readClock); - free(record->thread); - record->readClock=newreadClock; - record->thread=newthread; - record->capacity=newCapacity; + if (copytoindex >= record->capacity) { + int newCapacity = record->capacity * 2; + thread_id_t *newthread = (thread_id_t *)snapshot_malloc(sizeof(thread_id_t) * newCapacity); + modelclock_t *newreadClock = (modelclock_t *)snapshot_malloc(sizeof(modelclock_t) * newCapacity); + std::memcpy(newthread, record->thread, record->capacity * sizeof(thread_id_t)); + std::memcpy(newreadClock, record->readClock, record->capacity * sizeof(modelclock_t)); + snapshot_free(record->readClock); + snapshot_free(record->thread); + record->readClock = newreadClock; + record->thread = newthread; + record->capacity = newCapacity; } modelclock_t ourClock = currClock->getClock(thread); - record->thread[copytoindex]=thread; - record->readClock[copytoindex]=ourClock; - record->numReads=copytoindex+1; + record->thread[copytoindex] = thread; + record->readClock[copytoindex] = ourClock; + record->numReads = copytoindex + 1; } /** This function does race detection on a read. */ -void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) { - uint64_t * shadow=lookupAddressEntry(location); - uint64_t shadowval=*shadow; +void raceCheckRead(thread_id_t thread, const void *location) +{ + uint64_t *shadow = lookupAddressEntry(location); + uint64_t shadowval = *shadow; + ClockVector *currClock = get_execution()->get_cv(thread); /* Do full record */ - if (shadowval!=0&&!ISSHORTRECORD(shadowval)) { + if (shadowval != 0 && !ISSHORTRECORD(shadowval)) { fullRaceCheckRead(thread, location, shadow, currClock); return; } @@ -289,7 +341,7 @@ void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) { if (clock_may_race(currClock, thread, writeClock, writeThread)) { /* We have a datarace */ - reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location); + reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), false, location); } modelclock_t readClock = READVECTOR(shadowval); @@ -304,3 +356,8 @@ void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) { *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock); } + +bool haveUnrealizedRaces() +{ + return !unrealizedraces->empty(); +}