X-Git-Url: http://plrg.eecs.uci.edu/git/?p=model-checker.git;a=blobdiff_plain;f=datarace.cc;h=e6bbe05c29ddb2dd83e454751cab04ff8d201233;hp=832a220a3148796940cf2c84ba154bca5932fd9b;hb=fe5cffdbd16698d2508cdb472212189ab12bde4f;hpb=9b784333e1a62ed6d258e96502a5733041389c8f

diff --git a/datarace.cc b/datarace.cc
index 832a220..e6bbe05 100644
--- a/datarace.cc
+++ b/datarace.cc
@@ -1,46 +1,72 @@
 #include "datarace.h"
-#include "threads.h"
+#include "model.h"
+#include "threads-model.h"
 #include <stdio.h>
 #include <cstring>
+#include "mymemory.h"
+#include "clockvector.h"
 
 struct ShadowTable *root;
+std::vector<struct DataRace *> unrealizedraces;
 
+/** This function initialized the data race detector. */
 void initRaceDetector() {
-	root=(struct ShadowTable *) calloc(sizeof(struct ShadowTable),1);
+	root = (struct ShadowTable *)snapshot_calloc(sizeof(struct ShadowTable), 1);
 }
 
-static uint64_t * lookupAddressEntry(void * address) {
+/** This function looks up the entry in the shadow table corresponding to a
+ * given address.*/
+static uint64_t * lookupAddressEntry(const void * address) {
 	struct ShadowTable *currtable=root;
-#ifdef BIT48
-	currtable=(struct ShadowTable *) currtable->array[(((uintptr_t)address)>>32)&0xffff];
+#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 *)(root->array[(((uintptr_t)address)>>32)&MASK16BIT] = snapshot_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));
-	}	
+		basetable = (struct ShadowBaseTable *)(currtable->array[(((uintptr_t)address)>>16)&MASK16BIT] = snapshot_calloc(sizeof(struct ShadowBaseTable), 1));
+	}
 	return &basetable->array[((uintptr_t)address)&MASK16BIT];
 }
 
+/**
+ * Compares a current clock-vector/thread-ID pair with a clock/thread-ID pair
+ * to check the potential for a data race.
+ * @param clock1 The current clock vector
+ * @param tid1 The current thread; paired with clock1
+ * @param clock2 The clock value for the potentially-racing action
+ * @param tid2 The thread ID for the potentially-racing action
+ * @return true if the current clock allows a race with the event at clock2/tid2
+ */
+static bool clock_may_race(ClockVector *clock1, thread_id_t tid1,
+                           modelclock_t clock2, thread_id_t tid2)
+{
+	return tid1 != tid2 && clock2 != 0 && clock1->getClock(tid2) <= clock2;
+}
+
+/**
+ * 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;
 
-	int readClock = READVECTOR(shadowval);
+	modelclock_t readClock = READVECTOR(shadowval);
 	thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
-	int writeClock = WRITEVECTOR(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));
+	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 *) malloc(sizeof(thread_id_t)*record->capacity);
-		record->readClock=(int *) malloc(sizeof(int)*record->capacity);
+		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;
@@ -48,94 +74,153 @@ static void expandRecord(uint64_t * shadow) {
 	*shadow=(uint64_t) record;
 }
 
-static void reportDataRace() {
-	printf("The reportDataRace method should report useful things about this datarace!\n");
+/** 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) {
+	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();
+		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()) {
+		/* Prune the non-racing unrealized dataraces */
+		unsigned int i,newloc=0;
+		for(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)) {
+				unrealizedraces[newloc++]=race;
+			}
+		}
+		if (newloc!=i)
+			unrealizedraces.resize(newloc);
+
+		if (unrealizedraces.size()!=0) {
+			/* We have an actual realized race. */
+			for(i=0;i<unrealizedraces.size();i++) {
+				struct DataRace * race=unrealizedraces[i];
+				printRace(race);
+			}
+			return true;
+		}
+	}
+	return false;
+}
+
+void printRace(struct DataRace *race)
+{
+	printf("Datarace detected @ address %p:\n", race->address);
+	printf("    Access 1: %5s in thread %2d @ clock %3u\n",
+			race->isoldwrite ? "write" : "read",
+			id_to_int(race->oldthread), race->oldclock);
+	printf("    Access 2: %5s in thread %2d @ clock %3u\n",
+			race->isnewwrite ? "write" : "read",
+			id_to_int(race->newaction->get_tid()), race->newaction->get_seq_number());
 }
 
-void fullRaceCheckWrite(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
+/** 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);
 
 	/* Check for datarace against last read. */
 
 	for(int i=0;i<record->numReads;i++) {
-		int readClock = record->readClock[i];
+		modelclock_t readClock = record->readClock[i];
 		thread_id_t readThread = record->thread[i];
-		
-		if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) {
+
+		/* Note that readClock can't actuall be zero here, so it could be
+			 optimized. */
+
+		if (clock_may_race(currClock, thread, readClock, readThread)) {
 			/* We have a datarace */
-			reportDataRace();
+			reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
 		}
 	}
-	
+
 	/* Check for datarace against last write. */
-	
-	int writeClock = record->writeClock;
+
+	modelclock_t writeClock = record->writeClock;
 	thread_id_t writeThread = record->writeThread;
-	
-	if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
+
+	if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 		/* We have a datarace */
-		reportDataRace();
+		reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
 	}
-	
+
 	record->numReads=0;
 	record->writeThread=thread;
-	int ourClock = currClock->getClock(thread);
+	modelclock_t ourClock = currClock->getClock(thread);
 	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;
 
 	/* Do full record */
 	if (shadowval!=0&&!ISSHORTRECORD(shadowval)) {
-		fullRaceCheckWrite(thread, shadow, currClock);
+		fullRaceCheckWrite(thread, location, shadow, currClock);
 		return;
 	}
 
 	int threadid = id_to_int(thread);
-	int ourClock = currClock->getClock(thread);
-	
+	modelclock_t 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);
+		fullRaceCheckWrite(thread, location, shadow, currClock);
 		return;
 	}
-	
+
 	/* Check for datarace against last read. */
 
-	int readClock = READVECTOR(shadowval);
+	modelclock_t readClock = READVECTOR(shadowval);
 	thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 
-	if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) {
+	if (clock_may_race(currClock, thread, readClock, readThread)) {
 		/* We have a datarace */
-		reportDataRace();
+		reportDataRace(readThread, readClock, false, model->get_parent_action(thread), true, location);
 	}
 
 	/* Check for datarace against last write. */
 
-	int writeClock = WRITEVECTOR(shadowval);
+	modelclock_t writeClock = WRITEVECTOR(shadowval);
 	thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
-	
-	if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
+
+	if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 		/* We have a datarace */
-		reportDataRace();
+		reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), true, location);
 	}
 	*shadow = ENCODEOP(0, 0, threadid, ourClock);
 }
 
-void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currClock) {
+/** 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 RaceRecord * record=(struct RaceRecord *) (*shadow);
 
 	/* Check for datarace against last write. */
-	
-	int writeClock = record->writeClock;
+
+	modelclock_t writeClock = record->writeClock;
 	thread_id_t writeThread = record->writeThread;
-	
-	if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
+
+	if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 		/* We have a datarace */
-		reportDataRace();
+		reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
 	}
 
 	/* Shorten vector when possible */
@@ -143,10 +228,16 @@ void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currC
 	int copytoindex=0;
 
 	for(int i=0;i<record->numReads;i++) {
-		int readClock = record->readClock[i];
+		modelclock_t readClock = record->readClock[i];
 		thread_id_t readThread = record->thread[i];
-		
-		if (readThread != thread && currClock->getClock(readThread) <= readClock) {
+
+		/*  Note that is not really a datarace check as reads cannott
+				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
+				could be optimized.  */
+
+		if (clock_may_race(currClock, thread, readClock, readThread)) {
 			/* Still need this read in vector */
 			if (copytoindex!=i) {
 				record->readClock[copytoindex]=record->readClock[i];
@@ -155,66 +246,67 @@ void fullRaceCheckRead(thread_id_t thread, uint64_t * shadow, ClockVector *currC
 			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);		
+		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(int));
-		free(record->readClock);
-		free(record->thread);
+		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;
 	}
 
-	int ourClock = currClock->getClock(thread);
-	
+	modelclock_t 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) {
+/** This function does race detection on a read. */
+void raceCheckRead(thread_id_t thread, const 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);
+		fullRaceCheckRead(thread, location, shadow, currClock);
 		return;
 	}
 
 	int threadid = id_to_int(thread);
-	int ourClock = currClock->getClock(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, shadow, currClock);
+		fullRaceCheckRead(thread, location, shadow, currClock);
 		return;
 	}
 
 	/* Check for datarace against last write. */
 
-	int writeClock = WRITEVECTOR(shadowval);
+	modelclock_t writeClock = WRITEVECTOR(shadowval);
 	thread_id_t writeThread = int_to_id(WRTHREADID(shadowval));
-	
-	if (writeThread != thread && writeClock != 0 && currClock->getClock(writeThread) <= writeClock) {
+
+	if (clock_may_race(currClock, thread, writeClock, writeThread)) {
 		/* We have a datarace */
-		reportDataRace();
+		reportDataRace(writeThread, writeClock, true, model->get_parent_action(thread), false, location);
 	}
-	
-	int readClock = READVECTOR(shadowval);
+
+	modelclock_t readClock = READVECTOR(shadowval);
 	thread_id_t readThread = int_to_id(RDTHREADID(shadowval));
 
-	if (readThread != thread && readClock != 0 && currClock->getClock(readThread) <= readClock) {
+	if (clock_may_race(currClock, thread, readClock, readThread)) {
 		/* We don't subsume this read... Have to expand record. */
 		expandRecord(shadow);
-		fullRaceCheckRead(thread, shadow, currClock);
+		fullRaceCheckRead(thread, location, shadow, currClock);
 		return;
 	}
-		
-	*shadow = ENCODEOP(writeThread, writeClock, threadid, ourClock);
+
+	*shadow = ENCODEOP(threadid, ourClock, id_to_int(writeThread), writeClock);
 }