From f7e1577b22ac26c12dc57a43de2761aa9249227c Mon Sep 17 00:00:00 2001 From: Brian Demsky Date: Mon, 18 Jun 2012 11:43:32 -0700 Subject: [PATCH] builds --- Makefile | 6 +++--- cyclegraph.cc | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++ cyclegraph.h | 37 ++++++++++++++++++++++++++++++++ hashtable.h | 57 ++++++++++++++++++++++++++++++++++++++----------- model.cc | 6 ++++++ mymemory.cc | 3 --- 6 files changed, 150 insertions(+), 18 deletions(-) create mode 100644 cyclegraph.cc create mode 100644 cyclegraph.h diff --git a/Makefile b/Makefile index b65830fa..ddc89cb2 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 -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 -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 +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 SHMEM_CC=snapshot.cc malloc.c mymemory.cc SHMEM_O=snapshot.o malloc.o mymemory.o diff --git a/cyclegraph.cc b/cyclegraph.cc new file mode 100644 index 00000000..c1fea4f3 --- /dev/null +++ b/cyclegraph.cc @@ -0,0 +1,59 @@ +#include "cyclegraph.h" + +CycleGraph::CycleGraph() { + hasCycles=false; +} + +CycleNode * CycleGraph::getNode(ModelAction * action) { + CycleNode *node=actionToNode.get(action); + if (node==NULL) { + node=new CycleNode(action); + actionToNode.put(action, node); + } + return node; +} + +void CycleGraph::addEdge(ModelAction *from, ModelAction *to) { + CycleNode *fromnode=getNode(from); + CycleNode *tonode=getNode(to); + if (!hasCycles) { + // Check for Cycles + hasCycles=checkReachable(fromnode, tonode); + } + fromnode->addEdge(tonode); +} + +bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) { + std::vector queue; + HashTable discovered; + + queue.push_back(from); + discovered.put(from, from); + while(!queue.empty()) { + class CycleNode * node=queue.back(); + queue.pop_back(); + if (node==to) + return true; + + for(unsigned int i=0;igetEdges()->size();i++) { + CycleNode *next=(*node->getEdges())[i]; + if (!discovered.contains(next)) { + discovered.put(next,next); + queue.push_back(next); + } + } + } + return false; +} + +CycleNode::CycleNode(ModelAction *modelaction) { + action=modelaction; +} + +std::vector * CycleNode::getEdges() { + return &edges; +} + +void CycleNode::addEdge(CycleNode * node) { + edges.push_back(node); +} diff --git a/cyclegraph.h b/cyclegraph.h new file mode 100644 index 00000000..ed534170 --- /dev/null +++ b/cyclegraph.h @@ -0,0 +1,37 @@ +#ifndef CYCLEGRAPH_H +#define CYCLEGRAPH_H + +#include "hashtable.h" +#include "action.h" +#include + +class CycleNode; + +/** @brief A graph of Model Actions for tracking cycles. */ +class CycleGraph { + public: + CycleGraph(); + void addEdge(ModelAction *from, ModelAction *to); + bool checkForCycles(); + + private: + CycleNode * getNode(ModelAction *); + HashTable actionToNode; + bool checkReachable(CycleNode *from, CycleNode *to); + + bool hasCycles; + +}; + +class CycleNode { + public: + CycleNode(ModelAction *action); + void addEdge(CycleNode * node); + std::vector * getEdges(); + + private: + ModelAction *action; + std::vector edges; +}; + +#endif diff --git a/hashtable.h b/hashtable.h index ee7dc19f..f372f9e7 100644 --- a/hashtable.h +++ b/hashtable.h @@ -11,12 +11,12 @@ template struct hashlistnode<_Key,_Val> *next; }; -template +template class HashTable { public: - HashTable(unsigned int initialcapacity, double factor) { + HashTable(unsigned int initialcapacity=1024, double factor=0.5) { // Allocate space for the hash table - table = calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val> *)); + table = (struct hashlistnode<_Key,_Val> **) calloc(initialcapacity, sizeof(struct hashlistnode<_Key,_Val> *)); loadfactor = factor; capacity = initialcapacity; threshold = initialcapacity*loadfactor; @@ -25,17 +25,38 @@ template } ~HashTable() { + for(unsigned int i=0;i * bin = table[i]; + while(bin!=NULL) { + struct hashlistnode<_Key,_Val> * next=bin->next; + free(bin); + bin=next; + } + } free(table); } + + void reset() { + for(int i=0;i * bin = table[i]; + while(bin!=NULL) { + struct hashlistnode<_Key,_Val> * next=bin->next; + free(bin); + bin=next; + } + } + memset(table, 0, capacity*sizeof(struct hashlistnode<_Key, _Val> *)); + size=0; + } - void insert(_Key key, _Val val) { + void put(_Key key, _Val val) { if(size > threshold) { //Resize unsigned int newsize = capacity << 1; resize(newsize); } - struct hashlistnode<_Key,_Val> *ptr = table[(key & mask)>>_Shift]; + struct hashlistnode<_Key,_Val> *ptr = table[(((_KeyInt)key) & mask)>>_Shift]; size++; struct hashlistnode<_Key,_Val> *search = ptr; @@ -47,15 +68,15 @@ template search=search->next; } - struct hashlistnode<_Key,_Val> *newptr=malloc(sizeof(struct hashlistnode<_Key,_Val>)); + struct hashlistnode<_Key,_Val> *newptr=(struct hashlistnode<_Key,_Val> *)malloc(sizeof(struct hashlistnode<_Key,_Val>)); newptr->key=key; newptr->val=val; newptr->next=ptr; - table[(key&mask)>>_Shift]=newptr; + table[(((_KeyInt)key)&mask)>>_Shift]=newptr; } _Val get(_Key key) { - struct hashlistnode<_Key,_Val> *search = table[(key & mask)>>_Shift]; + struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift]; while(search!=NULL) { if (search->key==key) { @@ -65,13 +86,25 @@ template } return (_Val)0; } + + bool contains(_Key key) { + struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift]; + + while(search!=NULL) { + if (search->key==key) { + return true; + } + search=search->next; + } + return false; + } void resize(unsigned int newsize) { struct hashlistnode<_Key,_Val> ** oldtable = table; struct hashlistnode<_Key,_Val> ** newtable; unsigned int oldcapacity = capacity; - if((newtable = calloc(newsize, sizeof(struct hashlistnode<_Key,_Val> *))) == NULL) { + if((newtable = (struct hashlistnode<_Key,_Val> **) calloc(newsize, sizeof(struct hashlistnode<_Key,_Val> *))) == NULL) { printf("Calloc error %s %d\n", __FILE__, __LINE__); exit(-1); } @@ -88,8 +121,8 @@ template _Key key=bin->key; struct hashlistnode<_Key, _Val> * next=bin->next; - unsigned int index = (key & mask) >>_Shift; - struct hashlistnode<_Key, _Val> tmp=newtable[index]; + unsigned int index = (((_KeyInt)key) & mask) >>_Shift; + struct hashlistnode<_Key, _Val> * tmp=newtable[index]; bin->next=tmp; newtable[index]=bin; bin = next; @@ -102,7 +135,7 @@ template private: struct hashlistnode<_Key,_Val> **table; unsigned int capacity; - _Key mask; + _KeyInt mask; unsigned int size; unsigned int threshold; double loadfactor; diff --git a/model.cc b/model.cc index 27b6cd6a..09052850 100644 --- a/model.cc +++ b/model.cc @@ -258,6 +258,12 @@ void ModelChecker::check_current_action(void) add_action_to_lists(curr); } + +/** + * Adds an action to the per-object, per-thread action vector. + * @param act is the ModelAction to add. + */ + void ModelChecker::add_action_to_lists(ModelAction *act) { action_trace->push_back(act); diff --git a/mymemory.cc b/mymemory.cc index 2c5adc0a..88018e26 100644 --- a/mymemory.cc +++ b/mymemory.cc @@ -13,9 +13,6 @@ int howManyFreed = 0; static mspace sStaticSpace = NULL; #endif -//SUBRAMANIAN!!! PLEASE FIX THE MALLOC/FREE/CALLOC/ETC FOR FORK-BASED APPROACH -//YOU HAVE NOT DONE THIS!!!!!!!!!!! - /** Non-snapshotting malloc for our use. */ void *MYMALLOC(size_t size) { -- 2.34.1