1 #include "cyclegraph.h"
4 #include "threads-model.h"
6 /** Initializes a CycleGraph object. */
7 CycleGraph::CycleGraph() :
8 discovered(new HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free>(16)),
9 queue(new ModelVector<const CycleNode *>()),
15 /** CycleGraph destructor */
16 CycleGraph::~CycleGraph()
23 * Add a CycleNode to the graph, corresponding to a store ModelAction
24 * @param act The write action that should be added
25 * @param node The CycleNode that corresponds to the store
27 void CycleGraph::putNode(const ModelAction *act, CycleNode *node)
29 actionToNode.put(act, node);
30 #if SUPPORT_MOD_ORDER_DUMP
31 nodeList.push_back(node);
35 /** @return The corresponding CycleNode, if exists; otherwise NULL */
36 CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
38 return actionToNode.get(act);
42 * @brief Returns the CycleNode corresponding to a given ModelAction
44 * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
46 * @param action The ModelAction to find a node for
47 * @return The CycleNode paired with this action
49 CycleNode * CycleGraph::getNode(const ModelAction *action)
51 CycleNode *node = getNode_noCreate(action);
53 node = new CycleNode(action);
54 putNode(action, node);
60 * Adds an edge between two CycleNodes.
61 * @param fromnode The edge comes from this CycleNode
62 * @param tonode The edge points to this CycleNode
63 * @return True, if new edge(s) are added; otherwise false
65 bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
67 if (fromnode->addEdge(tonode)) {
68 rollbackvector.push_back(fromnode);
70 hasCycles = checkReachable(tonode, fromnode);
72 return false; /* No new edge */
75 * If the fromnode has a rmwnode that is not the tonode, we should
76 * follow its RMW chain to add an edge at the end, unless we encounter
77 * tonode along the way
79 CycleNode *rmwnode = fromnode->getRMW();
81 while (rmwnode != tonode && rmwnode->getRMW())
82 rmwnode = rmwnode->getRMW();
84 if (rmwnode != tonode) {
85 if (rmwnode->addEdge(tonode)) {
87 hasCycles = checkReachable(tonode, rmwnode);
89 rollbackvector.push_back(rmwnode);
97 * @brief Add an edge between a write and the RMW which reads from it
99 * Handles special case of a RMW action, where the ModelAction rmw reads from
100 * the ModelAction/Promise from. The key differences are:
101 * -# No write can occur in between the @a rmw and @a from actions.
102 * -# Only one RMW action can read from a given write.
104 * @param from The edge comes from this ModelAction/Promise
105 * @param rmw The edge points to this ModelAction; this action must read from
106 * the ModelAction/Promise from
108 template <typename T>
109 void CycleGraph::addRMWEdge(const T *from, const ModelAction *rmw)
114 CycleNode *fromnode = getNode(from);
115 CycleNode *rmwnode = getNode(rmw);
117 /* We assume that this RMW has no RMW reading from it yet */
118 ASSERT(!rmwnode->getRMW());
120 /* Two RMW actions cannot read from the same write. */
121 if (fromnode->setRMW(rmwnode))
124 rmwrollbackvector.push_back(fromnode);
126 /* Transfer all outgoing edges from the from node to the rmw node */
127 /* This process should not add a cycle because either:
128 * (1) The rmw should not have any incoming edges yet if it is the
130 * (2) the fromnode is the new node and therefore it should not
131 * have any outgoing edges.
133 for (unsigned int i = 0; i < fromnode->getNumEdges(); i++) {
134 CycleNode *tonode = fromnode->getEdge(i);
135 if (tonode != rmwnode) {
136 if (rmwnode->addEdge(tonode))
137 rollbackvector.push_back(rmwnode);
141 addNodeEdge(fromnode, rmwnode);
143 /* Instantiate two forms of CycleGraph::addRMWEdge */
144 template void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw);
147 * @brief Adds an edge between objects
149 * This function will add an edge between any two objects which can be
150 * associated with a CycleNode. That is, if they have a CycleGraph::getNode
153 * The object to is ordered after the object from.
155 * @param to The edge points to this object, of type T
156 * @param from The edge comes from this object, of type U
157 * @return True, if new edge(s) are added; otherwise false
159 template <typename T, typename U>
160 bool CycleGraph::addEdge(const T *from, const U *to)
165 CycleNode *fromnode = getNode(from);
166 CycleNode *tonode = getNode(to);
168 return addNodeEdge(fromnode, tonode);
170 /* Instantiate four forms of CycleGraph::addEdge */
171 template bool CycleGraph::addEdge(const ModelAction *from, const ModelAction *to);
173 #if SUPPORT_MOD_ORDER_DUMP
175 static void print_node(FILE *file, const CycleNode *node, int label)
177 const ModelAction *act = node->getAction();
178 modelclock_t idx = act->get_seq_number();
179 fprintf(file, "N%u", idx);
181 fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
184 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
186 print_node(file, from, 0);
187 fprintf(file, " -> ");
188 print_node(file, to, 0);
189 if (prop && strlen(prop))
190 fprintf(file, " [%s]", prop);
191 fprintf(file, ";\n");
194 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
196 print_node(file, getNode(act), 1);
199 template <typename T, typename U>
200 void CycleGraph::dot_print_edge(FILE *file, const T *from, const U *to, const char *prop)
202 CycleNode *fromnode = getNode(from);
203 CycleNode *tonode = getNode(to);
205 print_edge(file, fromnode, tonode, prop);
207 /* Instantiate two forms of CycleGraph::dot_print_edge */
208 template void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop);
210 void CycleGraph::dumpNodes(FILE *file) const
212 for (unsigned int i = 0; i < nodeList.size(); i++) {
213 CycleNode *n = nodeList[i];
214 print_node(file, n, 1);
215 fprintf(file, ";\n");
217 print_edge(file, n, n->getRMW(), "style=dotted");
218 for (unsigned int j = 0; j < n->getNumEdges(); j++)
219 print_edge(file, n, n->getEdge(j), NULL);
223 void CycleGraph::dumpGraphToFile(const char *filename) const
226 sprintf(buffer, "%s.dot", filename);
227 FILE *file = fopen(buffer, "w");
228 fprintf(file, "digraph %s {\n", filename);
230 fprintf(file, "}\n");
236 * Checks whether one CycleNode can reach another.
237 * @param from The CycleNode from which to begin exploration
238 * @param to The CycleNode to reach
239 * @return True, @a from can reach @a to; otherwise, false
241 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
245 queue->push_back(from);
246 discovered->put(from, from);
247 while (!queue->empty()) {
248 const CycleNode *node = queue->back();
252 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
253 CycleNode *next = node->getEdge(i);
254 if (!discovered->contains(next)) {
255 discovered->put(next, next);
256 queue->push_back(next);
264 * Checks whether one ModelAction/Promise can reach another ModelAction/Promise
265 * @param from The ModelAction or Promise from which to begin exploration
266 * @param to The ModelAction or Promise to reach
267 * @return True, @a from can reach @a to; otherwise, false
269 template <typename T, typename U>
270 bool CycleGraph::checkReachable(const T *from, const U *to) const
272 CycleNode *fromnode = getNode_noCreate(from);
273 CycleNode *tonode = getNode_noCreate(to);
275 if (!fromnode || !tonode)
278 return checkReachable(fromnode, tonode);
280 /* Instantiate four forms of CycleGraph::checkReachable */
281 template bool CycleGraph::checkReachable(const ModelAction *from,
282 const ModelAction *to) const;
284 /** @brief Begin a new sequence of graph additions which can be rolled back */
285 void CycleGraph::startChanges()
287 ASSERT(rollbackvector.empty());
288 ASSERT(rmwrollbackvector.empty());
289 ASSERT(oldCycles == hasCycles);
292 /** Commit changes to the cyclegraph. */
293 void CycleGraph::commitChanges()
295 rollbackvector.clear();
296 rmwrollbackvector.clear();
297 oldCycles = hasCycles;
300 /** Rollback changes to the previous commit. */
301 void CycleGraph::rollbackChanges()
303 for (unsigned int i = 0; i < rollbackvector.size(); i++)
304 rollbackvector[i]->removeEdge();
306 for (unsigned int i = 0; i < rmwrollbackvector.size(); i++)
307 rmwrollbackvector[i]->clearRMW();
309 hasCycles = oldCycles;
310 rollbackvector.clear();
311 rmwrollbackvector.clear();
314 /** @returns whether a CycleGraph contains cycles. */
315 bool CycleGraph::checkForCycles() const
321 * @brief Constructor for a CycleNode
322 * @param act The ModelAction for this node
324 CycleNode::CycleNode(const ModelAction *act) :
331 * @param i The index of the edge to return
332 * @returns The CycleNode edge indexed by i
334 CycleNode * CycleNode::getEdge(unsigned int i) const
339 /** @returns The number of edges leaving this CycleNode */
340 unsigned int CycleNode::getNumEdges() const
346 * @param i The index of the back edge to return
347 * @returns The CycleNode back-edge indexed by i
349 CycleNode * CycleNode::getBackEdge(unsigned int i) const
351 return back_edges[i];
354 /** @returns The number of edges entering this CycleNode */
355 unsigned int CycleNode::getNumBackEdges() const
357 return back_edges.size();
361 * @brief Remove an element from a vector
362 * @param v The vector
363 * @param n The element to remove
364 * @return True if the element was found; false otherwise
366 template <typename T>
367 static bool vector_remove_node(SnapVector<T>& v, const T n)
369 for (unsigned int i = 0; i < v.size(); i++) {
371 v.erase(v.begin() + i);
379 * @brief Remove a (forward) edge from this CycleNode
380 * @return The CycleNode which was popped, if one exists; otherwise NULL
382 CycleNode * CycleNode::removeEdge()
387 CycleNode *ret = edges.back();
389 vector_remove_node(ret->back_edges, this);
394 * @brief Remove a (back) edge from this CycleNode
395 * @return The CycleNode which was popped, if one exists; otherwise NULL
397 CycleNode * CycleNode::removeBackEdge()
399 if (back_edges.empty())
402 CycleNode *ret = back_edges.back();
403 back_edges.pop_back();
404 vector_remove_node(ret->edges, this);
409 * Adds an edge from this CycleNode to another CycleNode.
410 * @param node The node to which we add a directed edge
411 * @return True if this edge is a new edge; false otherwise
413 bool CycleNode::addEdge(CycleNode *node)
415 for (unsigned int i = 0; i < edges.size(); i++)
416 if (edges[i] == node)
418 edges.push_back(node);
419 node->back_edges.push_back(this);
423 /** @returns the RMW CycleNode that reads from the current CycleNode */
424 CycleNode * CycleNode::getRMW() const
430 * Set a RMW action node that reads from the current CycleNode.
431 * @param node The RMW that reads from the current node
432 * @return True, if this node already was read by another RMW; false otherwise
433 * @see CycleGraph::addRMWEdge
435 bool CycleNode::setRMW(CycleNode *node)