From fbc13c8288d44ea54017153b1b09a7dadf5e9c48 Mon Sep 17 00:00:00 2001 From: weiyu Date: Tue, 21 Apr 2020 14:18:55 -0700 Subject: [PATCH] Optimize data race detector --- datarace.cc | 395 ++++++++++++++++++++++++++++++++++++++++++++++------ datarace.h | 11 +- librace.cc | 27 +++- 3 files changed, 385 insertions(+), 48 deletions(-) diff --git a/datarace.cc b/datarace.cc index 8af2b1e6..8cb0c8fc 100644 --- a/datarace.cc +++ b/datarace.cc @@ -283,7 +283,6 @@ void raceCheckWrite(thread_id_t thread, void *location) { /* Check for datarace against last read. */ - modelclock_t readClock = READVECTOR(shadowval); thread_id_t readThread = int_to_id(RDTHREADID(shadowval)); @@ -704,74 +703,390 @@ Exit: } } -void raceCheckReadOpt(thread_id_t thread, const void * addr, int bytes) +static inline void raceCheckRead_firstIt(thread_id_t thread, const void * location, uint64_t *old_val, uint64_t *new_val) { - const ModelExecution * execution = get_execution(); - ClockVector *currClock = execution->get_cv(thread); + uint64_t *shadow = lookupAddressEntry(location); + uint64_t shadowval = *shadow; + + ClockVector *currClock = get_execution()->get_cv(thread); if (currClock == NULL) return; - int threadid = id_to_int(thread); - modelclock_t ourClock = currClock->getClock(thread); - bool should_expand = threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR; + struct DataRace * race = NULL; - bool hasRace = false; + /* Do full record */ + if (shadowval != 0 && !ISSHORTRECORD(shadowval)) { + race = fullRaceCheckRead(thread, location, shadow, currClock); + goto Exit; + } - for (int i = 0; i < bytes; i++) { - const void * location = (void *)(((uintptr_t)addr) + i); - uint64_t *shadow = lookupAddressEntry(location); - uint64_t shadowval = *shadow; + { + int threadid = id_to_int(thread); + modelclock_t ourClock = currClock->getClock(thread); - struct DataRace * race = NULL; + /* 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; + } - /* Do full record */ - if (shadowval != 0 && !ISSHORTRECORD(shadowval)) { + /* 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), false, location); + } + + 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); + struct RaceRecord *record = (struct RaceRecord *) (*shadow); + record->thread[1] = thread; + record->readClock[1] = ourClock; + record->numReads++; + + goto Exit; + } + + *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); + } + + + *old_val = shadowval; + *new_val = *shadow; +} + +static inline void raceCheckRead_otherIt(thread_id_t thread, const void * location, uint64_t first_shadowval, uint64_t updated_shadowval) +{ + uint64_t *shadow = lookupAddressEntry(location); + uint64_t shadowval = *shadow; + + if (shadowval != 0 && shadowval == first_shadowval) { + *shadow = updated_shadowval; + return; + } + + ClockVector *currClock = get_execution()->get_cv(thread); + if (currClock == NULL) + return; + + struct DataRace * race = NULL; + + /* Do full record */ + if (shadowval != 0 && !ISSHORTRECORD(shadowval)) { + race = fullRaceCheckRead(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 = fullRaceCheckRead(thread, location, shadow, currClock); goto Exit; } + /* 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), false, location); + } + + 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); + struct RaceRecord *record = (struct RaceRecord *) (*shadow); + record->thread[1] = thread; + record->readClock[1] = ourClock; + record->numReads++; + + goto Exit; + } + + *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); + } +} + +void raceCheckRead64(thread_id_t thread, const void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckRead_firstIt(thread, location, &old_shadowval, &new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 1), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 2), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 3), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 4), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 5), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 6), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 7), old_shadowval, new_shadowval); +} + +void raceCheckRead32(thread_id_t thread, const void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckRead_firstIt(thread, location, &old_shadowval, &new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 1), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 2), old_shadowval, new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 3), old_shadowval, new_shadowval); +} + +void raceCheckRead16(thread_id_t thread, const void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckRead_firstIt(thread, location, &old_shadowval, &new_shadowval); + raceCheckRead_otherIt(thread, (const void *)(((uintptr_t)location) + 1), old_shadowval, new_shadowval); +} + +void raceCheckRead8(thread_id_t thread, const void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckRead_firstIt(thread, location, &old_shadowval, &new_shadowval); +} + +static inline void raceCheckWrite_firstIt(thread_id_t thread, void * location, uint64_t *old_val, uint64_t *new_val) +{ + 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)) { + 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; + } + { - /* Thread ID is too large or clock is too large. */ - if (should_expand) { - expandRecord(shadow); - race = fullRaceCheckRead(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 there is already has a race, skip check - if (!hasRace && clock_may_race(currClock, thread, writeClock, writeThread)) { + if (clock_may_race(currClock, thread, writeClock, writeThread)) { /* We have a datarace */ - race = reportDataRace(writeThread, writeClock, true, execution->get_parent_action(thread), false, location); + 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); + } + + *old_val = shadowval; + *new_val = *shadow; +} + +static inline void raceCheckWrite_otherIt(thread_id_t thread, void * location, uint64_t first_shadowval, uint64_t updated_shadowval) +{ + uint64_t *shadow = lookupAddressEntry(location); + uint64_t shadowval = *shadow; + + if (shadowval != 0 && shadowval == first_shadowval) { + *shadow = updated_shadowval; + return; + } + + ClockVector *currClock = get_execution()->get_cv(thread); + if (currClock == NULL) + return; + + struct DataRace * race = NULL; + /* Do full record */ + if (shadowval != 0 && !ISSHORTRECORD(shadowval)) { + 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 don't subsume this read... Have to expand record. */ - expandRecord(shadow); - struct RaceRecord *record = (struct RaceRecord *) (*shadow); - record->thread[1] = thread; - record->readClock[1] = ourClock; - record->numReads++; - - goto Exit; + /* 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)); - *shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock) | (shadowval & ATOMICMASK); + 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) { - hasRace = true; - race->numframes=backtrace(race->backtrace, sizeof(race->backtrace)/sizeof(void*)); - if (raceset->add(race)) - assert_race(race); - else model_free(race); - } + if (race) { + race->numframes=backtrace(race->backtrace, sizeof(race->backtrace)/sizeof(void*)); + if (raceset->add(race)) + assert_race(race); + else model_free(race); } } + +void raceCheckWrite64(thread_id_t thread, void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckWrite_firstIt(thread, location, &old_shadowval, &new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 1), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 2), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 3), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 4), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 5), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 6), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 7), old_shadowval, new_shadowval); +} + +void raceCheckWrite32(thread_id_t thread, void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckWrite_firstIt(thread, location, &old_shadowval, &new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 1), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 2), old_shadowval, new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 3), old_shadowval, new_shadowval); +} + +void raceCheckWrite16(thread_id_t thread, void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckWrite_firstIt(thread, location, &old_shadowval, &new_shadowval); + raceCheckWrite_otherIt(thread, (void *)(((uintptr_t)location) + 1), old_shadowval, new_shadowval); +} + +void raceCheckWrite8(thread_id_t thread, void *location) +{ + uint64_t old_shadowval, new_shadowval; + old_shadowval = new_shadowval = 0; + + raceCheckWrite_firstIt(thread, location, &old_shadowval, &new_shadowval); +} + +/* +#define RACECHECKWRITE(size) \ + void raceCheckWrite ## size(thread_id_t thread, void *location) { \ + uint64_t old_shadowval, new_shadowval; \ + old_shadowval = new_shadowval = 0; \ + raceCheckWrite_firstit(thread, location, &old_shadowval, &new_shadowval); \ + for (int i=1; i < size / 8;i++) { \ + raceCheckWrite_otherit(thread, (void *)(((char *)location) + 1), old_shadowval, new_shadowval); \ + } \ + } + +RACECHECKWRITE(8) +RACECHECKWRITE(16) +RACECHECKWRITE(32) +RACECHECKWRITE(64) + +#define RACECHECKREAD(size) \ + void raceCheckRead ## size(thread_id_t thread, void *location) { \ + uint64_t old_shadowval, new_shadowval; \ + old_shadowval = new_shadowval = 0; \ + raceCheckRead_firstit(thread, location, &old_shadowval, &new_shadowval); \ + for (int i=1; i < size / 8;i++) { \ + raceCheckRead_otherit(thread, (void *)(((char *)location) + 1), old_shadowval, new_shadowval); \ + } \ + } + +RACECHECKREAD(8) +RACECHECKREAD(16) +RACECHECKREAD(32) +RACECHECKREAD(64) +*/ + diff --git a/datarace.h b/datarace.h index 60392029..a9bc92f6 100644 --- a/datarace.h +++ b/datarace.h @@ -46,7 +46,6 @@ void initRaceDetector(); void raceCheckWrite(thread_id_t thread, void *location); void atomraceCheckWrite(thread_id_t thread, void *location); void raceCheckRead(thread_id_t thread, const void *location); -void raceCheckReadOpt(thread_id_t thread, const void *location, int bytes); void atomraceCheckRead(thread_id_t thread, const void *location); void recordWrite(thread_id_t thread, void *location); @@ -56,6 +55,16 @@ bool hasNonAtomicStore(const void *location); void setAtomicStoreFlag(const void *location); void getStoreThreadAndClock(const void *address, thread_id_t * thread, modelclock_t * clock); +void raceCheckRead8(thread_id_t thread, const void *location); +void raceCheckRead16(thread_id_t thread, const void *location); +void raceCheckRead32(thread_id_t thread, const void *location); +void raceCheckRead64(thread_id_t thread, const void *location); + +void raceCheckWrite8(thread_id_t thread, void *location); +void raceCheckWrite16(thread_id_t thread, void *location); +void raceCheckWrite32(thread_id_t thread, void *location); +void raceCheckWrite64(thread_id_t thread, void *location); + /** * @brief A record of information for detecting data races */ diff --git a/librace.cc b/librace.cc index 15ee94eb..1d1ebbfc 100644 --- a/librace.cc +++ b/librace.cc @@ -107,7 +107,9 @@ void cds_store8(void *addr) if (!model) return; thread_id_t tid = thread_current()->get_id(); - raceCheckWrite(tid, addr); + raceCheckWrite8(tid, addr); + +// raceCheckWrite(tid, addr); } void cds_store16(void *addr) @@ -116,8 +118,10 @@ void cds_store16(void *addr) if (!model) return; thread_id_t tid = thread_current()->get_id(); - raceCheckWrite(tid, addr); - raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 1)); + raceCheckWrite16(tid, addr); + +// raceCheckWrite(tid, addr); +// raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 1)); } void cds_store32(void *addr) @@ -126,10 +130,14 @@ void cds_store32(void *addr) if (!model) return; thread_id_t tid = thread_current()->get_id(); + raceCheckWrite32(tid, addr); + +/* raceCheckWrite(tid, addr); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 1)); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 2)); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 3)); +*/ } void cds_store64(void *addr) @@ -138,6 +146,9 @@ void cds_store64(void *addr) if (!model) return; thread_id_t tid = thread_current()->get_id(); + raceCheckWrite64(tid, addr); + +/* raceCheckWrite(tid, addr); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 1)); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 2)); @@ -146,6 +157,7 @@ void cds_store64(void *addr) raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 5)); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 6)); raceCheckWrite(tid, (void *)(((uintptr_t)addr) + 7)); +*/ } void cds_load8(const void *addr) { @@ -153,7 +165,8 @@ void cds_load8(const void *addr) { return; thread_id_t tid = thread_current()->get_id(); - raceCheckReadOpt(tid, addr, 1); + raceCheckRead8(tid, addr); + // raceCheckRead(tid, addr); } @@ -162,7 +175,7 @@ void cds_load16(const void *addr) { return; thread_id_t tid = thread_current()->get_id(); - raceCheckReadOpt(tid, addr, 2); + raceCheckRead16(tid, addr); // raceCheckRead(tid, addr); // raceCheckRead(tid, (const void *)(((uintptr_t)addr) + 1)); } @@ -172,7 +185,7 @@ void cds_load32(const void *addr) { return; thread_id_t tid = thread_current()->get_id(); - raceCheckReadOpt(tid, addr, 4); + raceCheckRead32(tid, addr); /* raceCheckRead(tid, addr); raceCheckRead(tid, (const void *)(((uintptr_t)addr) + 1)); @@ -186,7 +199,7 @@ void cds_load64(const void *addr) { return; thread_id_t tid = thread_current()->get_id(); - raceCheckReadOpt(tid, addr, 8); + raceCheckRead64(tid, addr); /* raceCheckRead(tid, addr); raceCheckRead(tid, (const void *)(((uintptr_t)addr) + 1)); -- 2.34.1