X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=cyclegraph.cc;h=1d9533f4ba9b6f2fa61ae0018bb36dc22de5abcc;hp=aa3d24548a554ab039074282f5bab3246e3d3ccd;hb=251ac4b4bf3a9f2d3cfacc1e6618200ca1c431ac;hpb=e00292b5adf2b85eb1c6e2399159b5c28fde48eb

diff --git a/cyclegraph.cc b/cyclegraph.cc
index aa3d2454..1d9533f4 100644
--- a/cyclegraph.cc
+++ b/cyclegraph.cc
@@ -1,99 +1,122 @@
 #include "cyclegraph.h"
 #include "action.h"
 #include "common.h"
+#include "threads-model.h"
+#include "clockvector.h"
 
 /** Initializes a CycleGraph object. */
 CycleGraph::CycleGraph() :
-	hasCycles(false),
-	oldCycles(false),
-	hasRMWViolation(false),
-	oldRMWViolation(false)
+	queue(new SnapVector<const CycleNode *>())
 {
 }
 
 /** CycleGraph destructor */
-CycleGraph::~CycleGraph() {
+CycleGraph::~CycleGraph()
+{
+	delete queue;
+}
+
+/**
+ * Add a CycleNode to the graph, corresponding to a store ModelAction
+ * @param act The write action that should be added
+ * @param node The CycleNode that corresponds to the store
+ */
+void CycleGraph::putNode(const ModelAction *act, CycleNode *node)
+{
+	actionToNode.put(act, node);
+#if SUPPORT_MOD_ORDER_DUMP
+	nodeList.push_back(node);
+#endif
+}
+
+/** @return The corresponding CycleNode, if exists; otherwise NULL */
+CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
+{
+	return actionToNode.get(act);
 }
 
 /**
  * @brief Returns the CycleNode corresponding to a given ModelAction
+ *
+ * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
+ *
  * @param action The ModelAction to find a node for
  * @return The CycleNode paired with this action
  */
-CycleNode * CycleGraph::getNode(const ModelAction *action) {
-	CycleNode *node=actionToNode.get(action);
-	if (node==NULL) {
-		node=new CycleNode(action);
-		actionToNode.put(action, node);
-#if SUPPORT_MOD_ORDER_DUMP
-		nodeList.push_back(node);
-#endif
+CycleNode * CycleGraph::getNode(ModelAction *action)
+{
+	CycleNode *node = getNode_noCreate(action);
+	if (node == NULL) {
+		node = new CycleNode(action);
+		putNode(action, node);
 	}
 	return node;
 }
 
 /**
- * Adds an edge between two ModelActions. The ModelAction @a to is ordered
- * after the ModelAction @a from.
- * @param to The edge points to this ModelAction
- * @param from The edge comes from this ModelAction
+ * Adds an edge between two CycleNodes.
+ * @param fromnode The edge comes from this CycleNode
+ * @param tonode The edge points to this CycleNode
+ * @return True, if new edge(s) are added; otherwise false
  */
-void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to) {
-	ASSERT(from);
-	ASSERT(to);
-	ASSERT(from != to);
-
-	CycleNode *fromnode=getNode(from);
-	CycleNode *tonode=getNode(to);
-
-	if (!hasCycles) {
-		// Check for Cycles
-		hasCycles=checkReachable(tonode, fromnode);
+void CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode, bool forceedge)
+{
+	//quick check whether edge is redundant
+	if (checkReachable(fromnode, tonode) && !forceedge) {
+		return;
 	}
 
-	if (fromnode->addEdge(tonode))
-		rollbackvector.push_back(fromnode);
-
-
-	CycleNode * rmwnode=fromnode->getRMW();
-
-	//If the fromnode has a rmwnode that is not the tonode, we
-	//should add an edge between its rmwnode and the tonode
-
-	//If tonode is also a rmw, don't do this check as the execution is
-	//doomed and we'll catch the problem elsewhere, but we want to allow
-	//for the possibility of sending to's write value to rmwnode
+	/*
+	 * If the fromnode has a rmwnode, we should
+	 * follow its RMW chain to add an edge at the end.
+	 */
+	while (CycleNode * nextnode = fromnode->getRMW()) {
+		if (nextnode == tonode)
+			break;
+		fromnode = nextnode;
+	}
 
-	if (rmwnode!=NULL&&!to->is_rmw()) {
-		if (!hasCycles) {
-			// Check for Cycles
-			hasCycles=checkReachable(tonode, rmwnode);
+	fromnode->addEdge(tonode);	//Add edge to edgeSrcNode
+
+	/* Propagate clock vector changes */
+	if (tonode->cv->merge(fromnode->cv)) {
+		queue->push_back(tonode);
+		while(!queue->empty()) {
+			const CycleNode *node = queue->back();
+			queue->pop_back();
+			unsigned int numedges = node->getNumEdges();
+			for(unsigned int i = 0;i < numedges;i++) {
+				CycleNode * enode = node->getEdge(i);
+				if (enode->cv->merge(node->cv))
+					queue->push_back(enode);
+			}
 		}
-
-		if (rmwnode->addEdge(tonode))
-			rollbackvector.push_back(rmwnode);
 	}
 }
 
-/** Handles special case of a RMW action.  The ModelAction rmw reads
- *  from the ModelAction from.  The key differences are: (1) no write
- *  can occur in between the rmw and the from action.  Only one RMW
- *  action can read from a given write.
+/**
+ * @brief Add an edge between a write and the RMW which reads from it
+ *
+ * Handles special case of a RMW action, where the ModelAction rmw reads from
+ * the ModelAction from. The key differences are:
+ *  -# No write can occur in between the @a rmw and @a from actions.
+ *  -# Only one RMW action can read from a given write.
+ *
+ * @param from The edge comes from this ModelAction
+ * @param rmw The edge points to this ModelAction; this action must read from
+ * the ModelAction from
  */
-void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw) {
+void CycleGraph::addRMWEdge(ModelAction *from, ModelAction *rmw)
+{
 	ASSERT(from);
 	ASSERT(rmw);
-	ASSERT(from != rmw);
 
-	CycleNode *fromnode=getNode(from);
-	CycleNode *rmwnode=getNode(rmw);
+	CycleNode *fromnode = getNode(from);
+	CycleNode *rmwnode = getNode(rmw);
+	/* We assume that this RMW has no RMW reading from it yet */
+	ASSERT(!rmwnode->getRMW());
 
-	/* Two RMW actions cannot read from the same write. */
-	if (fromnode->setRMW(rmwnode)) {
-		hasRMWViolation=true;
-	} else {
-		rmwrollbackvector.push_back(fromnode);
-	}
+	fromnode->setRMW(rmwnode);
 
 	/* Transfer all outgoing edges from the from node to the rmw node */
 	/* This process should not add a cycle because either:
@@ -102,63 +125,164 @@ void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw) {
 	 * (2) the fromnode is the new node and therefore it should not
 	 * have any outgoing edges.
 	 */
-	std::vector<CycleNode *> * edges=fromnode->getEdges();
-	for(unsigned int i=0;i<edges->size();i++) {
-		CycleNode * tonode=(*edges)[i];
-		if (tonode!=rmwnode) {
-			if (rmwnode->addEdge(tonode))
-				rollbackvector.push_back(rmwnode);
+	for (unsigned int i = 0;i < fromnode->getNumEdges();i++) {
+		CycleNode *tonode = fromnode->getEdge(i);
+		if (tonode != rmwnode) {
+			rmwnode->addEdge(tonode);
 		}
+		tonode->removeInEdge(fromnode);
 	}
+	fromnode->edges.clear();
 
+	addNodeEdge(fromnode, rmwnode, true);
+}
 
-	if (!hasCycles) {
-		// With promises we could be setting up a cycle here if we aren't
-		// careful...avoid it..
-		hasCycles=checkReachable(rmwnode, fromnode);
+void CycleGraph::addEdges(SnapList<ModelAction *> * edgeset, ModelAction *to) {
+	for(sllnode<ModelAction*> * it = edgeset->begin();it!=NULL;) {
+		ModelAction *act = it->getVal();
+		CycleNode *node = getNode(act);
+		sllnode<ModelAction*> * it2 = it;
+		it2=it2->getNext();
+		for(;it2!=NULL; ) {
+			ModelAction *act2 = it2->getVal();
+			CycleNode *node2 = getNode(act2);
+			if (checkReachable(node, node2)) {
+				it = edgeset->erase(it);
+				goto endouterloop;
+			} else if (checkReachable(node2, node)) {
+				it2 = edgeset->erase(it2);
+				goto endinnerloop;
+			}
+			it2=it2->getNext();
+endinnerloop:
+			;
+		}
+		it=it->getNext();
+endouterloop:
+		;
+	}
+	for(sllnode<ModelAction*> *it = edgeset->begin();it!=NULL;it=it->getNext()) {
+		ModelAction *from = it->getVal();
+		addEdge(from, to, from->get_tid() == to->get_tid());
 	}
-	if(fromnode->addEdge(rmwnode))
-		rollbackvector.push_back(fromnode);
+}
+
+/**
+ * @brief Adds an edge between objects
+ *
+ * This function will add an edge between any two objects which can be
+ * associated with a CycleNode. That is, if they have a CycleGraph::getNode
+ * implementation.
+ *
+ * The object to is ordered after the object from.
+ *
+ * @param to The edge points to this object, of type T
+ * @param from The edge comes from this object, of type U
+ * @return True, if new edge(s) are added; otherwise false
+ */
+
+void CycleGraph::addEdge(ModelAction *from, ModelAction *to)
+{
+	ASSERT(from);
+	ASSERT(to);
+
+	CycleNode *fromnode = getNode(from);
+	CycleNode *tonode = getNode(to);
+
+	addNodeEdge(fromnode, tonode, false);
+}
+
+void CycleGraph::addEdge(ModelAction *from, ModelAction *to, bool forceedge)
+{
+	ASSERT(from);
+	ASSERT(to);
+
+	CycleNode *fromnode = getNode(from);
+	CycleNode *tonode = getNode(to);
+
+	addNodeEdge(fromnode, tonode, forceedge);
 }
 
 #if SUPPORT_MOD_ORDER_DUMP
-void CycleGraph::dumpNodes(FILE *file) {
-  for(unsigned int i=0;i<nodeList.size();i++) {
-		CycleNode *cn=nodeList[i];
-		std::vector<CycleNode *> * edges=cn->getEdges();
-		const ModelAction *action=cn->getAction();
-		fprintf(file, "N%u [label=\"%u, T%u\"];\n",action->get_seq_number(),action->get_seq_number(), action->get_tid());
-		if (cn->getRMW()!=NULL) {
-			fprintf(file, "N%u -> N%u[style=dotted];\n", action->get_seq_number(), cn->getRMW()->getAction()->get_seq_number());
-		}
-		for(unsigned int j=0;j<edges->size();j++) {
-		  CycleNode *dst=(*edges)[j];
-			const ModelAction *dstaction=dst->getAction();
-      fprintf(file, "N%u -> N%u;\n", action->get_seq_number(), dstaction->get_seq_number());
-	  }
+
+static void print_node(FILE *file, const CycleNode *node, int label)
+{
+	const ModelAction *act = node->getAction();
+	modelclock_t idx = act->get_seq_number();
+	fprintf(file, "N%u", idx);
+	if (label)
+		fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
+}
+
+static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
+{
+	print_node(file, from, 0);
+	fprintf(file, " -> ");
+	print_node(file, to, 0);
+	if (prop && strlen(prop))
+		fprintf(file, " [%s]", prop);
+	fprintf(file, ";\n");
+}
+
+void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
+{
+	print_node(file, getNode(act), 1);
+}
+
+void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop)
+{
+	CycleNode *fromnode = getNode(from);
+	CycleNode *tonode = getNode(to);
+
+	print_edge(file, fromnode, tonode, prop);
+}
+
+void CycleGraph::dumpNodes(FILE *file) const
+{
+	for (unsigned int i = 0;i < nodeList.size();i++) {
+		CycleNode *n = nodeList[i];
+		print_node(file, n, 1);
+		fprintf(file, ";\n");
+		if (n->getRMW())
+			print_edge(file, n, n->getRMW(), "style=dotted");
+		for (unsigned int j = 0;j < n->getNumEdges();j++)
+			print_edge(file, n, n->getEdge(j), NULL);
 	}
 }
 
-void CycleGraph::dumpGraphToFile(const char *filename) {
+void CycleGraph::dumpGraphToFile(const char *filename) const
+{
 	char buffer[200];
-  sprintf(buffer, "%s.dot",filename);
-  FILE *file=fopen(buffer, "w");
-  fprintf(file, "digraph %s {\n",filename);
+	sprintf(buffer, "%s.dot", filename);
+	FILE *file = fopen(buffer, "w");
+	fprintf(file, "digraph %s {\n", filename);
 	dumpNodes(file);
-  fprintf(file,"}\n");
-  fclose(file);	
+	fprintf(file, "}\n");
+	fclose(file);
 }
 #endif
 
 /**
- * Checks whether one ModelAction can reach another.
+ * Checks whether one CycleNode can reach another.
+ * @param from The CycleNode from which to begin exploration
+ * @param to The CycleNode to reach
+ * @return True, @a from can reach @a to; otherwise, false
+ */
+bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
+{
+	return to->cv->synchronized_since(from->action);
+}
+
+/**
+ * Checks whether one ModelAction can reach another ModelAction
  * @param from The ModelAction from which to begin exploration
  * @param to The ModelAction to reach
  * @return True, @a from can reach @a to; otherwise, false
  */
-bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) {
-	CycleNode *fromnode = actionToNode.get(from);
-	CycleNode *tonode = actionToNode.get(to);
+bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
+{
+	CycleNode *fromnode = getNode_noCreate(from);
+	CycleNode *tonode = getNode_noCreate(to);
 
 	if (!fromnode || !tonode)
 		return false;
@@ -166,104 +290,101 @@ bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to)
 	return checkReachable(fromnode, tonode);
 }
 
-/**
- * Checks whether one CycleNode can reach another.
- * @param from The CycleNode from which to begin exploration
- * @param to The CycleNode to reach
- * @return True, @a from can reach @a to; otherwise, false
- */
-bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
-	std::vector<CycleNode *, ModelAlloc<CycleNode *> > queue;
-	HashTable<CycleNode *, CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free> discovered;
-
-	queue.push_back(from);
-	discovered.put(from, from);
-	while(!queue.empty()) {
-		CycleNode * node=queue.back();
-		queue.pop_back();
-		if (node==to)
-			return true;
-
-		for(unsigned int i=0;i<node->getEdges()->size();i++) {
-			CycleNode *next=(*node->getEdges())[i];
-			if (!discovered.contains(next)) {
-				discovered.put(next,next);
-				queue.push_back(next);
-			}
-		}
+void CycleGraph::freeAction(const ModelAction * act) {
+	CycleNode *cn = actionToNode.remove(act);
+	for(unsigned int i=0;i<cn->edges.size();i++) {
+		CycleNode *dst = cn->edges[i];
+		dst->removeInEdge(cn);
 	}
-	return false;
+	for(unsigned int i=0;i<cn->inedges.size();i++) {
+		CycleNode *src = cn->inedges[i];
+		src->removeEdge(cn);
+	}
+	delete cn;
 }
 
-void CycleGraph::startChanges() {
-	ASSERT(rollbackvector.size()==0);
-	ASSERT(rmwrollbackvector.size()==0);
-	ASSERT(oldCycles==hasCycles);
-	ASSERT(oldRMWViolation==hasRMWViolation);
+/**
+ * @brief Constructor for a CycleNode
+ * @param act The ModelAction for this node
+ */
+CycleNode::CycleNode(ModelAction *act) :
+	action(act),
+	hasRMW(NULL),
+	cv(new ClockVector(NULL, act))
+{
 }
 
-/** Commit changes to the cyclegraph. */
-void CycleGraph::commitChanges() {
-	rollbackvector.resize(0);
-	rmwrollbackvector.resize(0);
-	oldCycles=hasCycles;
-	oldRMWViolation=hasRMWViolation;
+CycleNode::~CycleNode() {
+	delete cv;
 }
 
-/** Rollback changes to the previous commit. */
-void CycleGraph::rollbackChanges() {
-	for (unsigned int i = 0; i < rollbackvector.size(); i++) {
-		rollbackvector[i]->popEdge();
+void CycleNode::removeInEdge(CycleNode *src) {
+	for(unsigned int i=0;i < inedges.size();i++) {
+		if (inedges[i] == src) {
+			inedges[i] = inedges[inedges.size()-1];
+			inedges.pop_back();
+			break;
+		}
 	}
+}
 
-	for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
-		rmwrollbackvector[i]->clearRMW();
+void CycleNode::removeEdge(CycleNode *dst) {
+	for(unsigned int i=0;i < edges.size();i++) {
+		if (edges[i] == dst) {
+			edges[i] = edges[edges.size()-1];
+			edges.pop_back();
+			break;
+		}
 	}
-
-	hasCycles = oldCycles;
-	hasRMWViolation = oldRMWViolation;
-	rollbackvector.resize(0);
-	rmwrollbackvector.resize(0);
 }
 
-/** @returns whether a CycleGraph contains cycles. */
-bool CycleGraph::checkForCycles() {
-	return hasCycles;
+/**
+ * @param i The index of the edge to return
+ * @returns The CycleNode edge indexed by i
+ */
+CycleNode * CycleNode::getEdge(unsigned int i) const
+{
+	return edges[i];
 }
 
-bool CycleGraph::checkForRMWViolation() {
-	return hasRMWViolation;
+/** @returns The number of edges leaving this CycleNode */
+unsigned int CycleNode::getNumEdges() const
+{
+	return edges.size();
 }
 
 /**
- * Constructor for a CycleNode.
- * @param modelaction The ModelAction for this node
+ * @param i The index of the edge to return
+ * @returns The CycleNode edge indexed by i
  */
-CycleNode::CycleNode(const ModelAction *modelaction) :
-	action(modelaction),
-	hasRMW(NULL)
+CycleNode * CycleNode::getInEdge(unsigned int i) const
 {
+	return inedges[i];
 }
 
-/** @returns a vector of the edges from a CycleNode. */
-std::vector<CycleNode *> * CycleNode::getEdges() {
-	return &edges;
+/** @returns The number of edges leaving this CycleNode */
+unsigned int CycleNode::getNumInEdges() const
+{
+	return inedges.size();
 }
 
 /**
  * Adds an edge from this CycleNode to another CycleNode.
  * @param node The node to which we add a directed edge
+ * @return True if this edge is a new edge; false otherwise
  */
-bool CycleNode::addEdge(CycleNode *node) {
-	for(unsigned int i=0;i<edges.size();i++)
-		if (edges[i]==node)
-			return false;
+void CycleNode::addEdge(CycleNode *node)
+{
+	for (unsigned int i = 0;i < edges.size();i++)
+		if (edges[i] == node)
+			return;
 	edges.push_back(node);
-	return true;
+	node->inedges.push_back(this);
 }
 
 /** @returns the RMW CycleNode that reads from the current CycleNode */
-CycleNode * CycleNode::getRMW() {
+CycleNode * CycleNode::getRMW() const
+{
 	return hasRMW;
 }
 
@@ -273,9 +394,10 @@ CycleNode * CycleNode::getRMW() {
  * @return True, if this node already was read by another RMW; false otherwise
  * @see CycleGraph::addRMWEdge
  */
-bool CycleNode::setRMW(CycleNode *node) {
-	if (hasRMW!=NULL)
+bool CycleNode::setRMW(CycleNode *node)
+{
+	if (hasRMW != NULL)
 		return true;
-	hasRMW=node;
+	hasRMW = node;
 	return false;
 }