1 #include "cyclegraph.h"
7 /** Initializes a CycleGraph object. */
8 CycleGraph::CycleGraph() :
9 discovered(new HashTable<CycleNode *, CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free>(16)),
12 hasRMWViolation(false),
13 oldRMWViolation(false)
17 /** CycleGraph destructor */
18 CycleGraph::~CycleGraph()
23 * @brief Returns the CycleNode corresponding to a given ModelAction
24 * @param action The ModelAction to find a node for
25 * @return The CycleNode paired with this action
27 CycleNode * CycleGraph::getNode(const ModelAction *action)
29 CycleNode *node = actionToNode.get(action);
31 node = new CycleNode(action);
32 actionToNode.put(action, node);
33 #if SUPPORT_MOD_ORDER_DUMP
34 nodeList.push_back(node);
41 * Adds an edge between two ModelActions. The ModelAction @a to is ordered
42 * after the ModelAction @a from.
43 * @param to The edge points to this ModelAction
44 * @param from The edge comes from this ModelAction
46 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to)
51 CycleNode *fromnode = getNode(from);
52 CycleNode *tonode = getNode(to);
55 // Reflexive edges are cycles
56 hasCycles = (from == to);
60 hasCycles = checkReachable(tonode, fromnode);
63 if (fromnode->addEdge(tonode))
64 rollbackvector.push_back(fromnode);
67 CycleNode *rmwnode = fromnode->getRMW();
70 * If the fromnode has a rmwnode that is not the tonode, we should add
71 * an edge between its rmwnode and the tonode
73 * If tonode is also a rmw, don't do this check as the execution is
74 * doomed and we'll catch the problem elsewhere, but we want to allow
75 * for the possibility of sending to's write value to rmwnode
77 if (rmwnode != NULL && !to->is_rmw()) {
80 hasCycles = checkReachable(tonode, rmwnode);
83 if (rmwnode->addEdge(tonode))
84 rollbackvector.push_back(rmwnode);
88 /** Handles special case of a RMW action. The ModelAction rmw reads
89 * from the ModelAction from. The key differences are: (1) no write
90 * can occur in between the rmw and the from action. Only one RMW
91 * action can read from a given write.
93 void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
98 CycleNode *fromnode = getNode(from);
99 CycleNode *rmwnode = getNode(rmw);
101 /* Two RMW actions cannot read from the same write. */
102 if (fromnode->setRMW(rmwnode)) {
103 hasRMWViolation = true;
105 rmwrollbackvector.push_back(fromnode);
108 /* Transfer all outgoing edges from the from node to the rmw node */
109 /* This process should not add a cycle because either:
110 * (1) The rmw should not have any incoming edges yet if it is the
112 * (2) the fromnode is the new node and therefore it should not
113 * have any outgoing edges.
115 for (unsigned int i = 0; i < fromnode->getNumEdges(); i++) {
116 CycleNode *tonode = fromnode->getEdge(i);
117 if (tonode != rmwnode) {
118 if (rmwnode->addEdge(tonode))
119 rollbackvector.push_back(rmwnode);
125 // Reflexive edges are cycles
126 hasCycles = (from == rmw);
129 // With promises we could be setting up a cycle here if we aren't
130 // careful...avoid it..
131 hasCycles = checkReachable(rmwnode, fromnode);
133 if (fromnode->addEdge(rmwnode))
134 rollbackvector.push_back(fromnode);
137 #if SUPPORT_MOD_ORDER_DUMP
138 void CycleGraph::dumpNodes(FILE *file)
140 for (unsigned int i = 0; i < nodeList.size(); i++) {
141 CycleNode *cn = nodeList[i];
142 const ModelAction *action = cn->getAction();
143 fprintf(file, "N%u [label=\"%u, T%u\"];\n",action->get_seq_number(),action->get_seq_number(), action->get_tid());
144 if (cn->getRMW() != NULL) {
145 fprintf(file, "N%u -> N%u[style=dotted];\n", action->get_seq_number(), cn->getRMW()->getAction()->get_seq_number());
147 for (unsigned int j = 0; j < cn->getNumEdges(); j++) {
148 CycleNode *dst = cn->getEdge(j);
149 const ModelAction *dstaction = dst->getAction();
150 fprintf(file, "N%u -> N%u;\n", action->get_seq_number(), dstaction->get_seq_number());
155 void CycleGraph::dumpGraphToFile(const char *filename)
158 sprintf(buffer, "%s.dot", filename);
159 FILE *file = fopen(buffer, "w");
160 fprintf(file, "digraph %s {\n", filename);
162 fprintf(file, "}\n");
168 * Checks whether one ModelAction can reach another.
169 * @param from The ModelAction from which to begin exploration
170 * @param to The ModelAction to reach
171 * @return True, @a from can reach @a to; otherwise, false
173 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to)
175 CycleNode *fromnode = actionToNode.get(from);
176 CycleNode *tonode = actionToNode.get(to);
178 if (!fromnode || !tonode)
181 return checkReachable(fromnode, tonode);
185 * Checks whether one CycleNode can reach another.
186 * @param from The CycleNode from which to begin exploration
187 * @param to The CycleNode to reach
188 * @return True, @a from can reach @a to; otherwise, false
190 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to)
192 std::vector< CycleNode *, ModelAlloc<CycleNode *> > queue;
195 queue.push_back(from);
196 discovered->put(from, from);
197 while (!queue.empty()) {
198 CycleNode *node = queue.back();
203 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
204 CycleNode *next = node->getEdge(i);
205 if (!discovered->contains(next)) {
206 discovered->put(next, next);
207 queue.push_back(next);
214 bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise)
216 std::vector< CycleNode *, ModelAlloc<CycleNode *> > queue;
218 CycleNode *from = actionToNode.get(fromact);
220 queue.push_back(from);
221 discovered->put(from, from);
222 while (!queue.empty()) {
223 CycleNode *node = queue.back();
226 if (promise->increment_threads(node->getAction()->get_tid())) {
230 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
231 CycleNode *next = node->getEdge(i);
232 if (!discovered->contains(next)) {
233 discovered->put(next, next);
234 queue.push_back(next);
241 void CycleGraph::startChanges()
243 ASSERT(rollbackvector.size() == 0);
244 ASSERT(rmwrollbackvector.size() == 0);
245 ASSERT(oldCycles == hasCycles);
246 ASSERT(oldRMWViolation == hasRMWViolation);
249 /** Commit changes to the cyclegraph. */
250 void CycleGraph::commitChanges()
252 rollbackvector.resize(0);
253 rmwrollbackvector.resize(0);
254 oldCycles = hasCycles;
255 oldRMWViolation = hasRMWViolation;
258 /** Rollback changes to the previous commit. */
259 void CycleGraph::rollbackChanges() {
260 for (unsigned int i = 0; i < rollbackvector.size(); i++) {
261 rollbackvector[i]->popEdge();
264 for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
265 rmwrollbackvector[i]->clearRMW();
268 hasCycles = oldCycles;
269 hasRMWViolation = oldRMWViolation;
270 rollbackvector.resize(0);
271 rmwrollbackvector.resize(0);
274 /** @returns whether a CycleGraph contains cycles. */
275 bool CycleGraph::checkForCycles() {
279 bool CycleGraph::checkForRMWViolation() {
280 return hasRMWViolation;
284 * Constructor for a CycleNode.
285 * @param modelaction The ModelAction for this node
287 CycleNode::CycleNode(const ModelAction *modelaction) :
294 * @param i The index of the edge to return
295 * @returns The a CycleNode edge indexed by i
297 CycleNode * CycleNode::getEdge(unsigned int i) const
302 /** @returns The number of edges leaving this CycleNode */
303 unsigned int CycleNode::getNumEdges() const
309 * Adds an edge from this CycleNode to another CycleNode.
310 * @param node The node to which we add a directed edge
312 bool CycleNode::addEdge(CycleNode *node)
314 for (unsigned int i = 0; i < edges.size(); i++)
315 if (edges[i] == node)
317 edges.push_back(node);
321 /** @returns the RMW CycleNode that reads from the current CycleNode */
322 CycleNode * CycleNode::getRMW() const
328 * Set a RMW action node that reads from the current CycleNode.
329 * @param node The RMW that reads from the current node
330 * @return True, if this node already was read by another RMW; false otherwise
331 * @see CycleGraph::addRMWEdge
333 bool CycleNode::setRMW(CycleNode *node)