From 9b784333e1a62ed6d258e96502a5733041389c8f Mon Sep 17 00:00:00 2001 From: Brian Demsky Date: Fri, 6 Jul 2012 00:38:38 -0700 Subject: [PATCH] add support for datarace detection... --- Makefile | 6 +- clockvector.cc | 13 +++ clockvector.h | 1 + datarace.cc | 220 +++++++++++++++++++++++++++++++++++++++++++++++++ datarace.h | 59 +++++++++++++ 5 files changed, 296 insertions(+), 3 deletions(-) create mode 100644 datarace.cc create mode 100644 datarace.h diff --git a/Makefile b/Makefile index 6ef1e94d..a6ec00b9 100644 --- a/Makefile +++ b/Makefile @@ -8,9 +8,9 @@ LIB_SO=lib$(LIB_NAME).so USER_O=userprog.o USER_H=libthreads.h libatomic.h -MODEL_CC=libthreads.cc schedule.cc libatomic.cc model.cc threads.cc librace.cc action.cc nodestack.cc clockvector.cc main.cc snapshot-interface.cc cyclegraph.cc -MODEL_O=libthreads.o schedule.o libatomic.o model.o threads.o librace.o action.o nodestack.o clockvector.o main.o snapshot-interface.o cyclegraph.o -MODEL_H=libthreads.h schedule.h common.h libatomic.h model.h threads.h librace.h action.h nodestack.h clockvector.h snapshot-interface.h cyclegraph.h hashtable.h +MODEL_CC=libthreads.cc schedule.cc libatomic.cc model.cc threads.cc librace.cc action.cc nodestack.cc clockvector.cc main.cc snapshot-interface.cc cyclegraph.cc datarace.cc +MODEL_O=libthreads.o schedule.o libatomic.o model.o threads.o librace.o action.o nodestack.o clockvector.o main.o snapshot-interface.o cyclegraph.o datarace.o +MODEL_H=libthreads.h schedule.h common.h libatomic.h model.h threads.h librace.h action.h nodestack.h clockvector.h snapshot-interface.h cyclegraph.h hashtable.h datarace.h SHMEM_CC=snapshot.cc malloc.c mymemory.cc SHMEM_O=snapshot.o malloc.o mymemory.o diff --git a/clockvector.cc b/clockvector.cc index 95896ed3..1956b18a 100644 --- a/clockvector.cc +++ b/clockvector.cc @@ -84,6 +84,19 @@ bool ClockVector::synchronized_since(ModelAction *act) const return false; } +/** + * Gets the clock corresponding to a given thread id from the clock + * vector. */ + +int ClockVector::getClock(thread_id_t thread) { + int threadid = id_to_int(thread); + + if (threadid < num_threads) + return clock[threadid]; + else + return 0; +} + /** @brief Formats and prints this ClockVector's data. */ void ClockVector::print() const { diff --git a/clockvector.h b/clockvector.h index b7d72068..470914b1 100644 --- a/clockvector.h +++ b/clockvector.h @@ -19,6 +19,7 @@ public: bool synchronized_since(ModelAction *act) const; void print() const; + int getClock(thread_id_t thread); MEMALLOC private: diff --git a/datarace.cc b/datarace.cc new file mode 100644 index 00000000..832a220a --- /dev/null +++ b/datarace.cc @@ -0,0 +1,220 @@ +#include "datarace.h" +#include "threads.h" +#include +#include + +struct ShadowTable *root; + +void initRaceDetector() { + root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1); +} + +static uint64_t * lookupAddressEntry(void * address) { + struct ShadowTable *currtable=root; +#ifdef BIT48 + currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&0xffff]; + if (currtable==NULL) { + currtable=(struct ShadowTable *) (root->array[(((uintptr_t)address)>>32)&MASK16BIT]=calloc(sizeof(struct ShadowTable),1)); + } +#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)); + } + return &basetable->array[((uintptr_t)address)&MASK16BIT]; +} + +static void expandRecord(uint64_t * shadow) { + uint64_t shadowval=*shadow; + + int readClock = READVECTOR(shadowval); + thread_id_t readThread = int_to_id(RDTHREADID(shadowval)); + int 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=(int *) malloc(sizeof(int)*record->capacity); + record->numReads=1; + record->thread[0]=readThread; + record->readClock[0]=readClock; + } + *shadow=(uint64_t) record; +} + +static void reportDataRace() { + printf("The reportDataRace method should report useful things about this datarace!\n"); +} + +void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) { + struct RaceRecord * record=(struct RaceRecord *) (*shadow); + + /* Check for datarace against last read. */ + + for(int i=0;inumReads;i++) { + int readClock = record->readClock[i]; + thread_id_t readThread = record->thread[i]; + + if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) { + /* We have a datarace */ + reportDataRace(); + } + } + + /* Check for datarace against last write. */ + + int writeClock = record->writeClock; + thread_id_t writeThread = record->writeThread; + + if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) { + /* We have a datarace */ + reportDataRace(); + } + + record->numReads=0; + record->writeThread=thread; + int ourClock = currClock->getClock(thread); + record->writeClock=ourClock; +} + +void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock) { + uint64_t * shadow=lookupAddressEntry(location); + uint64_t shadowval=*shadow; + + /* Do full record */ + if (shadowval!=0&&!ISSHORTRECORD(shadowval)) { + fullRaceCheckWrite(thread, shadow, currClock); + return; + } + + int threadid = id_to_int(thread); + int ourClock = currClock->getClock(thread); + + /* Thread ID is too large or clock is too large. */ + if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) { + expandRecord(shadow); + fullRaceCheckWrite(thread, shadow, currClock); + return; + } + + /* Check for datarace against last read. */ + + int readClock = READVECTOR(shadowval); + thread_id_t readThread = int_to_id(RDTHREADID(shadowval)); + + if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) { + /* We have a datarace */ + reportDataRace(); + } + + /* Check for datarace against last write. */ + + int writeClock = WRITEVECTOR(shadowval); + thread_id_t writeThread = int_to_id(WRTHREADID(shadowval)); + + if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) { + /* We have a datarace */ + reportDataRace(); + } + *shadow = ENCODEOP(0, 0, threadid, ourClock); +} + +void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) { + struct RaceRecord * record=(struct RaceRecord *) (*shadow); + + /* Check for datarace against last write. */ + + int writeClock = record->writeClock; + thread_id_t writeThread = record->writeThread; + + if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) { + /* We have a datarace */ + reportDataRace(); + } + + /* Shorten vector when possible */ + + int copytoindex=0; + + for(int i=0;inumReads;i++) { + int readClock = record->readClock[i]; + thread_id_t readThread = record->thread[i]; + + if (readThread != thread && currClock->getClock(readThread) <= readClock) { + /* Still need this read in vector */ + 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); + int * newreadClock=(int *) malloc(sizeof(int)*newCapacity); + std::memcpy(newthread, record->thread, record->capacity*sizeof(thread_id_t)); + std::memcpy(newreadClock, record->readClock, record->capacity*sizeof(int)); + free(record->readClock); + free(record->thread); + record->readClock=newreadClock; + record->thread=newthread; + record->capacity=newCapacity; + } + + int ourClock = currClock->getClock(thread); + + record->thread[copytoindex]=thread; + record->readClock[copytoindex]=ourClock; + record->numReads=copytoindex+1; +} + +void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock) { + uint64_t * shadow=lookupAddressEntry(location); + uint64_t shadowval=*shadow; + + /* Do full record */ + if (shadowval!=0&&!ISSHORTRECORD(shadowval)) { + fullRaceCheckRead(thread, shadow, currClock); + return; + } + + int threadid = id_to_int(thread); + int ourClock = currClock->getClock(thread); + + /* Thread ID is too large or clock is too large. */ + if (threadid > MAXTHREADID || ourClock > MAXWRITEVECTOR) { + expandRecord(shadow); + fullRaceCheckRead(thread, shadow, currClock); + return; + } + + /* Check for datarace against last write. */ + + int writeClock = WRITEVECTOR(shadowval); + thread_id_t writeThread = int_to_id(WRTHREADID(shadowval)); + + if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) { + /* We have a datarace */ + reportDataRace(); + } + + int readClock = READVECTOR(shadowval); + thread_id_t readThread = int_to_id(RDTHREADID(shadowval)); + + if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) { + /* We don't subsume this read... Have to expand record. */ + expandRecord(shadow); + fullRaceCheckRead(thread, shadow, currClock); + return; + } + + *shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock); +} diff --git a/datarace.h b/datarace.h new file mode 100644 index 00000000..e3cab5d6 --- /dev/null +++ b/datarace.h @@ -0,0 +1,59 @@ +#ifndef DATARACE_H +#include "config.h" +#include +#include "clockvector.h" + +struct ShadowTable { + void * array[65536]; +}; + +struct ShadowBaseTable { + uint64_t array[65536]; +}; + +#define MASK16BIT 0xffff + +void initRaceDetector(); +void raceCheckWrite(thread_id_t thread, void *location, ClockVector *currClock); +void raceCheckRead(thread_id_t thread, void *location, ClockVector *currClock); + + + +/** Encoding idea: + * (void *) Either: + * (1) points to a full record or + * + * (2) encodes the information in a 64 bit word. Encoding is as + * follows: lowest bit set to 1, next 8 bits are read thread id, next + * 23 bits are read clock vector, next 8 bites are write thread id, + * next 23 bits are write clock vector. */ + +struct RaceRecord { + int *readClock; + thread_id_t *thread; + int capacity; + int numReads; + thread_id_t writeThread; + int writeClock; +}; + +#define INITCAPACITY 4 + +#define ISSHORTRECORD(x) ((x)&0x1) + +#define THREADMASK 0xff +#define RDTHREADID(x) (((x)>>1)&THREADMASK) +#define READMASK 0x07fffff +#define READVECTOR(x) (((x)>>9)&READMASK) + +#define WRTHREADID(x) (((x)>>32)&THREADMASK) + +#define WRITEMASK READMASK +#define WRITEVECTOR(x) (((x)>>40)&WRITEMASK) + +#define ENCODEOP(rdthread, rdtime, wrthread, wrtime) (0x1ULL | ((rdthread)<<1) | ((rdtime) << 9) | (((uint64_t)wrthread)<<32) | (((uint64_t)wrtime)<<40)) + +#define MAXTHREADID (THREADMASK-1) +#define MAXREADVECTOR (READMASK-1) +#define MAXWRITEVECTOR (WRITEMASK-1) +#endif -- 2.34.1