#include "action.h"
#include "execution.h"
#include "stl-model.h"
+#include <execinfo.h>
static struct ShadowTable *root;
-static SnapVector<DataRace *> *unrealizedraces;
static void *memory_base;
static void *memory_top;
+static RaceSet * raceset;
static const ModelExecution * get_execution()
{
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<DataRace *>();
+ raceset = new RaceSet();
}
void * table_calloc(size_t size)
return &basetable->array[((uintptr_t)address) & MASK16BIT];
}
+
+bool hasNonAtomicStore(const void *address) {
+ uint64_t * shadow = lookupAddressEntry(address);
+ uint64_t shadowval = *shadow;
+ if (ISSHORTRECORD(shadowval)) {
+ //Do we have a non atomic write with a non-zero clock
+ return ((WRITEVECTOR(shadowval) != 0) && !(ATOMICMASK & shadowval));
+ } else {
+ if (shadowval == 0)
+ return false;
+ struct RaceRecord *record = (struct RaceRecord *)shadowval;
+ return !record->isAtomic && record->writeClock != 0;
+ }
+}
+
+void setAtomicStoreFlag(const void *address) {
+ uint64_t * shadow = lookupAddressEntry(address);
+ uint64_t shadowval = *shadow;
+ if (ISSHORTRECORD(shadowval)) {
+ *shadow = shadowval | ATOMICMASK;
+ } else {
+ if (shadowval == 0)
+ return;
+ struct RaceRecord *record = (struct RaceRecord *)shadowval;
+ record->isAtomic = 1;
+ }
+}
+
+void getStoreThreadAndClock(const void *address, thread_id_t * thread, modelclock_t * clock) {
+ uint64_t * shadow = lookupAddressEntry(address);
+ uint64_t shadowval = *shadow;
+ if (ISSHORTRECORD(shadowval)) {
+ //Do we have a non atomic write with a non-zero clock
+ *thread = WRTHREADID(shadowval);
+ *clock = WRITEVECTOR(shadowval);
+ } else {
+ struct RaceRecord *record = (struct RaceRecord *)shadowval;
+ *thread = record->writeThread;
+ *clock = record->writeClock;
+ }
+}
+
/**
* Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
* to check the potential for a data race.
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->thread = (thread_id_t *)snapshot_malloc(sizeof(thread_id_t) * INITCAPACITY);
+ record->readClock = (modelclock_t *)snapshot_malloc(sizeof(modelclock_t) * INITCAPACITY);
record->numReads = 1;
+ ASSERT(readThread >= 0);
record->thread[0] = readThread;
record->readClock[0] = readClock;
}
+ if (shadowval & ATOMICMASK)
+ record->isAtomic = 1;
*shadow = (uint64_t) record;
}
+#define FIRST_STACK_FRAME 2
+
+unsigned int race_hash(struct DataRace *race) {
+ unsigned int hash = 0;
+ for(int i=FIRST_STACK_FRAME;i < race->numframes;i++) {
+ hash ^= ((uintptr_t)race->backtrace[i]);
+ hash = (hash >> 3) | (hash << 29);
+ }
+ return hash;
+}
+
+
+bool race_equals(struct DataRace *r1, struct DataRace *r2) {
+ if (r1->numframes != r2->numframes)
+ return false;
+ for(int i=FIRST_STACK_FRAME;i < r1->numframes;i++) {
+ if (r1->backtrace[i] != r2->backtrace[i])
+ return false;
+ }
+ return true;
+}
+
/** 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, const void *address)
+static struct DataRace * 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));
+ struct DataRace *race = (struct DataRace *)model_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->switch_to_master(NULL);
-}
-
-/**
- * @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 */
- for (unsigned i = 0;i < unrealizedraces->size();i++) {
- struct DataRace *race = (*unrealizedraces)[i];
- if (clock_may_race(race->newaction->get_cv(), race->newaction->get_tid(), race->oldclock, race->oldthread)) {
- assert_race(race);
- race_asserted = true;
- }
- snapshot_free(race);
- }
- unrealizedraces->clear();
- return race_asserted;
- }
- return false;
+ return race;
}
/**
*/
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()
- );
+ model_print("Race detected at location: \n");
+ backtrace_symbols_fd(race->backtrace, race->numframes, model_out);
+ model_print("\nData race detected @ address %p:\n"
+ " Access 1: %5s in thread %2d @ clock %3u\n"
+ " Access 2: %5s in thread %2d @ clock %3u\n\n",
+ 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 DataRace * fullRaceCheckWrite(thread_id_t thread, void *location, uint64_t *shadow, ClockVector *currClock)
{
struct RaceRecord *record = (struct RaceRecord *)(*shadow);
+ struct DataRace * race = NULL;
/* Check for datarace against last read. */
if (clock_may_race(currClock, thread, readClock, readThread)) {
/* We have a datarace */
- reportDataRace(readThread, readClock, false, get_execution()->get_parent_action(thread), true, location);
+ race = reportDataRace(readThread, readClock, false, get_execution()->get_parent_action(thread), true, location);
+ goto Exit;
}
}
/* Check for datarace against last write. */
- modelclock_t writeClock = record->writeClock;
- thread_id_t writeThread = record->writeThread;
+ {
+ modelclock_t writeClock = record->writeClock;
+ thread_id_t writeThread = record->writeThread;
- if (clock_may_race(currClock, thread, writeClock, writeThread)) {
- /* We have a datarace */
- reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), true, location);
+ if (clock_may_race(currClock, thread, writeClock, writeThread)) {
+ /* We have a datarace */
+ race = reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), true, location);
+ goto Exit;
+ }
}
-
+Exit:
record->numReads = 0;
record->writeThread = thread;
+ record->isAtomic = 0;
modelclock_t ourClock = currClock->getClock(thread);
record->writeClock = ourClock;
+ return race;
}
/** This function does race detection on a write. */
uint64_t *shadow = lookupAddressEntry(location);
uint64_t shadowval = *shadow;
ClockVector *currClock = get_execution()->get_cv(thread);
+ if (currClock == NULL)
+ return;
+ struct DataRace * race = NULL;
/* Do full record */
if (shadowval != 0 && !ISSHORTRECORD(shadowval)) {
- fullRaceCheckWrite(thread, location, shadow, currClock);
+ race = fullRaceCheckWrite(thread, location, shadow, currClock);
+ goto Exit;
+ }
+
+ {
+ int threadid = id_to_int(thread);
+ modelclock_t ourClock = currClock->getClock(thread);
+
+ /* Thread ID is too large or clock is too large. */
+ if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
+ expandRecord(shadow);
+ race = fullRaceCheckWrite(thread, location, shadow, currClock);
+ goto Exit;
+ }
+
+
+
+ {
+ /* Check for datarace against last read. */
+
+ modelclock_t readClock = READVECTOR(shadowval);
+ thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
+
+ if (clock_may_race(currClock, thread, readClock, readThread)) {
+ /* We have a datarace */
+ race = reportDataRace(readThread, readClock, false, get_execution()->get_parent_action(thread), true, location);
+ goto ShadowExit;
+ }
+ }
+
+ {
+ /* Check for datarace against last write. */
+
+ modelclock_t writeClock = WRITEVECTOR(shadowval);
+ thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
+
+ if (clock_may_race(currClock, thread, writeClock, writeThread)) {
+ /* We have a datarace */
+ race = reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), true, location);
+ goto ShadowExit;
+ }
+ }
+
+ShadowExit:
+ *shadow = ENCODEOP(0, 0, threadid, ourClock);
+ }
+
+Exit:
+ if (race) {
+ race->numframes=backtrace(race->backtrace, sizeof(race->backtrace)/sizeof(void*));
+ if (raceset->add(race))
+ assert_race(race);
+ else model_free(race);
+ }
+}
+
+/** This function does race detection for a write on an expanded record. */
+void fullRecordWrite(thread_id_t thread, void *location, uint64_t *shadow, ClockVector *currClock) {
+ struct RaceRecord *record = (struct RaceRecord *)(*shadow);
+ record->numReads = 0;
+ record->writeThread = thread;
+ modelclock_t ourClock = currClock->getClock(thread);
+ record->writeClock = ourClock;
+ record->isAtomic = 1;
+}
+
+/** This function just updates metadata on atomic write. */
+void recordWrite(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)) {
+ fullRecordWrite(thread, location, shadow, currClock);
return;
}
/* Thread ID is too large or clock is too large. */
if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
expandRecord(shadow);
- fullRaceCheckWrite(thread, location, shadow, currClock);
+ fullRecordWrite(thread, location, shadow, currClock);
return;
}
- /* Check for datarace against last read. */
-
- modelclock_t readClock = READVECTOR(shadowval);
- thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
-
- if (clock_may_race(currClock, thread, readClock, readThread)) {
- /* We have a datarace */
- reportDataRace(readThread, readClock, false, get_execution()->get_parent_action(thread), true, location);
- }
-
- /* Check for datarace against last write. */
+ *shadow = ENCODEOP(0, 0, threadid, ourClock) | ATOMICMASK;
+}
- modelclock_t writeClock = WRITEVECTOR(shadowval);
- thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
- if (clock_may_race(currClock, thread, writeClock, writeThread)) {
- /* We have a datarace */
- 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, const void *location, uint64_t *shadow, ClockVector *currClock)
+struct DataRace * fullRaceCheckRead(thread_id_t thread, const void *location, uint64_t *shadow, ClockVector *currClock)
{
struct RaceRecord *record = (struct RaceRecord *) (*shadow);
-
+ struct DataRace * race = NULL;
/* Check for datarace against last write. */
modelclock_t writeClock = record->writeClock;
if (clock_may_race(currClock, thread, writeClock, writeThread)) {
/* We have a datarace */
- reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), false, location);
+ race = reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), false, location);
}
/* Shorten vector when possible */
modelclock_t readClock = record->readClock[i];
thread_id_t readThread = record->thread[i];
- /* Note that is not really a datarace check as reads cannott
+ /* Note that is not really a datarace check as reads cannot
actually race. It is just determining that this read subsumes
another in the sense that either this read races or neither
read races. Note that readClock can't actually be zero, so it
if (clock_may_race(currClock, thread, readClock, readThread)) {
/* Still need this read in vector */
if (copytoindex != i) {
+ ASSERT(record->thread[i] >= 0);
record->readClock[copytoindex] = record->readClock[i];
record->thread[copytoindex] = record->thread[i];
}
}
}
- 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;
+ if (__builtin_popcount(copytoindex) <= 1) {
+ if (copytoindex == 0) {
+ int newCapacity = INITCAPACITY;
+ record->thread = (thread_id_t *)snapshot_malloc(sizeof(thread_id_t) * newCapacity);
+ record->readClock = (modelclock_t *)snapshot_malloc(sizeof(modelclock_t) * newCapacity);
+ } else if (copytoindex>=INITCAPACITY) {
+ int newCapacity = copytoindex * 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, copytoindex * sizeof(thread_id_t));
+ std::memcpy(newreadClock, record->readClock, copytoindex * sizeof(modelclock_t));
+ snapshot_free(record->readClock);
+ snapshot_free(record->thread);
+ record->readClock = newreadClock;
+ record->thread = newthread;
+ }
}
modelclock_t ourClock = currClock->getClock(thread);
+ ASSERT(thread >= 0);
record->thread[copytoindex] = thread;
record->readClock[copytoindex] = ourClock;
record->numReads = copytoindex + 1;
+ return race;
}
/** This function does race detection on a read. */
uint64_t *shadow = lookupAddressEntry(location);
uint64_t shadowval = *shadow;
ClockVector *currClock = get_execution()->get_cv(thread);
+ if (currClock == NULL)
+ return;
+
+ struct DataRace * race = NULL;
/* Do full record */
if (shadowval != 0 && !ISSHORTRECORD(shadowval)) {
- fullRaceCheckRead(thread, location, shadow, currClock);
- return;
+ race = fullRaceCheckRead(thread, location, shadow, currClock);
+ goto Exit;
}
- int threadid = id_to_int(thread);
- modelclock_t ourClock = currClock->getClock(thread);
+ {
+ int threadid = id_to_int(thread);
+ modelclock_t ourClock = currClock->getClock(thread);
- /* Thread ID is too large or clock is too large. */
- if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
- expandRecord(shadow);
- fullRaceCheckRead(thread, location, shadow, currClock);
- return;
- }
+ /* Thread ID is too large or clock is too large. */
+ if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) {
+ expandRecord(shadow);
+ race = fullRaceCheckRead(thread, location, shadow, currClock);
+ goto Exit;
+ }
- /* Check for datarace against last write. */
+ /* Check for datarace against last write. */
- modelclock_t writeClock = WRITEVECTOR(shadowval);
- thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
+ modelclock_t writeClock = WRITEVECTOR(shadowval);
+ thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
- if (clock_may_race(currClock, thread, writeClock, writeThread)) {
- /* We have a datarace */
- reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), false, location);
- }
+ if (clock_may_race(currClock, thread, writeClock, writeThread)) {
+ /* We have a datarace */
+ race = reportDataRace(writeThread, writeClock, true, get_execution()->get_parent_action(thread), false, location);
+ goto ShadowExit;
+ }
- modelclock_t readClock = READVECTOR(shadowval);
- thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
+ShadowExit:
+ {
+ modelclock_t readClock = READVECTOR(shadowval);
+ thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
- if (clock_may_race(currClock, thread, readClock, readThread)) {
- /* We don't subsume this read... Have to expand record. */
- expandRecord(shadow);
- fullRaceCheckRead(thread, location, shadow, currClock);
- return;
- }
-
- *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock);
-}
+ if (clock_may_race(currClock, thread, readClock, readThread)) {
+ /* We don't subsume this read... Have to expand record. */
+ expandRecord(shadow);
+ fullRaceCheckRead(thread, location, shadow, currClock);
+ goto Exit;
+ }
+ }
-bool haveUnrealizedRaces()
-{
- return !unrealizedraces->empty();
+ *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock) | (shadowval & ATOMICMASK);
+ }
+Exit:
+ if (race) {
+ race->numframes=backtrace(race->backtrace, sizeof(race->backtrace)/sizeof(void*));
+ if (raceset->add(race))
+ assert_race(race);
+ else model_free(race);
+ }
}
projects / c11tester.git / blobdiff