Optimize data race detector
authorweiyu <weiyuluo1232@gmail.com>
Tue, 21 Apr 2020 21:18:55 +0000 (14:18 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Tue, 21 Apr 2020 21:18:55 +0000 (14:18 -0700)
datarace.cc
datarace.h
librace.cc

index 8af2b1e..8cb0c8f 100644 (file)
@@ -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)
+*/
+
index 6039202..a9bc92f 100644 (file)
@@ -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
  */
index 15ee94e..1d1ebbf 100644 (file)
@@ -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));