e3d0d8366694d53c44170ba589062df01d179aa0
[c11tester.git] / cyclegraph.cc
1 #include "cyclegraph.h"
2 #include "action.h"
3 #include "common.h"
4 #include "promise.h"
5 #include "model.h"
6
7 /** Initializes a CycleGraph object. */
8 CycleGraph::CycleGraph() :
9         discovered(new HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free>(16)),
10         hasCycles(false),
11         oldCycles(false),
12         hasRMWViolation(false),
13         oldRMWViolation(false)
14 {
15 }
16
17 /** CycleGraph destructor */
18 CycleGraph::~CycleGraph()
19 {
20         delete discovered;
21 }
22
23 /**
24  * Add a CycleNode to the graph, corresponding to a store ModelAction
25  * @param act The write action that should be added
26  * @param node The CycleNode that corresponds to the store
27  */
28 void CycleGraph::putNode(const ModelAction *act, CycleNode *node)
29 {
30         actionToNode.put(act, node);
31 #if SUPPORT_MOD_ORDER_DUMP
32         nodeList.push_back(node);
33 #endif
34 }
35
36 /**
37  * @brief Returns the CycleNode corresponding to a given ModelAction
38  * @param action The ModelAction to find a node for
39  * @return The CycleNode paired with this action
40  */
41 CycleNode * CycleGraph::getNode(const ModelAction *action)
42 {
43         CycleNode *node = actionToNode.get(action);
44         if (node == NULL) {
45                 node = new CycleNode(action);
46                 putNode(action, node);
47         }
48         return node;
49 }
50
51 /**
52  * Adds an edge between two ModelActions. The ModelAction @a to is ordered
53  * after the ModelAction @a from.
54  * @param to The edge points to this ModelAction
55  * @param from The edge comes from this ModelAction
56  */
57 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to)
58 {
59         ASSERT(from);
60         ASSERT(to);
61
62         CycleNode *fromnode = getNode(from);
63         CycleNode *tonode = getNode(to);
64
65         if (!hasCycles) {
66                 // Reflexive edges are cycles
67                 hasCycles = (from == to);
68         }
69         if (!hasCycles) {
70                 // Check for Cycles
71                 hasCycles = checkReachable(tonode, fromnode);
72         }
73
74         if (fromnode->addEdge(tonode))
75                 rollbackvector.push_back(fromnode);
76
77
78         CycleNode *rmwnode = fromnode->getRMW();
79
80         /*
81          * If the fromnode has a rmwnode that is not the tonode, we should add
82          * an edge between its rmwnode and the tonode
83          *
84          * If tonode is also a rmw, don't do this check as the execution is
85          * doomed and we'll catch the problem elsewhere, but we want to allow
86          * for the possibility of sending to's write value to rmwnode
87          */
88         if (rmwnode != NULL && !to->is_rmw()) {
89                 if (!hasCycles) {
90                         // Check for Cycles
91                         hasCycles = checkReachable(tonode, rmwnode);
92                 }
93
94                 if (rmwnode->addEdge(tonode))
95                         rollbackvector.push_back(rmwnode);
96         }
97 }
98
99 /** Handles special case of a RMW action.  The ModelAction rmw reads
100  *  from the ModelAction from.  The key differences are: (1) no write
101  *  can occur in between the rmw and the from action.  Only one RMW
102  *  action can read from a given write.
103  */
104 void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw)
105 {
106         ASSERT(from);
107         ASSERT(rmw);
108
109         CycleNode *fromnode = getNode(from);
110         CycleNode *rmwnode = getNode(rmw);
111
112         /* Two RMW actions cannot read from the same write. */
113         if (fromnode->setRMW(rmwnode)) {
114                 hasRMWViolation = true;
115         } else {
116                 rmwrollbackvector.push_back(fromnode);
117         }
118
119         /* Transfer all outgoing edges from the from node to the rmw node */
120         /* This process should not add a cycle because either:
121          * (1) The rmw should not have any incoming edges yet if it is the
122          * new node or
123          * (2) the fromnode is the new node and therefore it should not
124          * have any outgoing edges.
125          */
126         for (unsigned int i = 0; i < fromnode->getNumEdges(); i++) {
127                 CycleNode *tonode = fromnode->getEdge(i);
128                 if (tonode != rmwnode) {
129                         if (rmwnode->addEdge(tonode))
130                                 rollbackvector.push_back(rmwnode);
131                 }
132         }
133
134
135         if (!hasCycles) {
136                 // Reflexive edges are cycles
137                 hasCycles = (from == rmw);
138         }
139         if (!hasCycles) {
140                 // With promises we could be setting up a cycle here if we aren't
141                 // careful...avoid it..
142                 hasCycles = checkReachable(rmwnode, fromnode);
143         }
144         if (fromnode->addEdge(rmwnode))
145                 rollbackvector.push_back(fromnode);
146 }
147
148 #if SUPPORT_MOD_ORDER_DUMP
149 void CycleGraph::dumpNodes(FILE *file) const
150 {
151         for (unsigned int i = 0; i < nodeList.size(); i++) {
152                 CycleNode *cn = nodeList[i];
153                 const ModelAction *action = cn->getAction();
154                 fprintf(file, "N%u [label=\"%u, T%u\"];\n", action->get_seq_number(), action->get_seq_number(), action->get_tid());
155                 if (cn->getRMW() != NULL) {
156                         fprintf(file, "N%u -> N%u[style=dotted];\n", action->get_seq_number(), cn->getRMW()->getAction()->get_seq_number());
157                 }
158                 for (unsigned int j = 0; j < cn->getNumEdges(); j++) {
159                         CycleNode *dst = cn->getEdge(j);
160                         const ModelAction *dstaction = dst->getAction();
161                         fprintf(file, "N%u -> N%u;\n", action->get_seq_number(), dstaction->get_seq_number());
162                 }
163         }
164 }
165
166 void CycleGraph::dumpGraphToFile(const char *filename) const
167 {
168         char buffer[200];
169         sprintf(buffer, "%s.dot", filename);
170         FILE *file = fopen(buffer, "w");
171         fprintf(file, "digraph %s {\n", filename);
172         dumpNodes(file);
173         fprintf(file, "}\n");
174         fclose(file);
175 }
176 #endif
177
178 /**
179  * Checks whether one ModelAction can reach another.
180  * @param from The ModelAction from which to begin exploration
181  * @param to The ModelAction to reach
182  * @return True, @a from can reach @a to; otherwise, false
183  */
184 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
185 {
186         CycleNode *fromnode = actionToNode.get(from);
187         CycleNode *tonode = actionToNode.get(to);
188
189         if (!fromnode || !tonode)
190                 return false;
191
192         return checkReachable(fromnode, tonode);
193 }
194
195 /**
196  * Checks whether one CycleNode can reach another.
197  * @param from The CycleNode from which to begin exploration
198  * @param to The CycleNode to reach
199  * @return True, @a from can reach @a to; otherwise, false
200  */
201 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
202 {
203         std::vector< const CycleNode *, ModelAlloc<const CycleNode *> > queue;
204         discovered->reset();
205
206         queue.push_back(from);
207         discovered->put(from, from);
208         while (!queue.empty()) {
209                 const CycleNode *node = queue.back();
210                 queue.pop_back();
211                 if (node == to)
212                         return true;
213
214                 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
215                         CycleNode *next = node->getEdge(i);
216                         if (!discovered->contains(next)) {
217                                 discovered->put(next, next);
218                                 queue.push_back(next);
219                         }
220                 }
221         }
222         return false;
223 }
224
225 bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) const
226 {
227         std::vector< CycleNode *, ModelAlloc<CycleNode *> > queue;
228         discovered->reset();
229         CycleNode *from = actionToNode.get(fromact);
230
231         queue.push_back(from);
232         discovered->put(from, from);
233         while (!queue.empty()) {
234                 CycleNode *node = queue.back();
235                 queue.pop_back();
236
237                 if (promise->increment_threads(node->getAction()->get_tid())) {
238                         return true;
239                 }
240
241                 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
242                         CycleNode *next = node->getEdge(i);
243                         if (!discovered->contains(next)) {
244                                 discovered->put(next, next);
245                                 queue.push_back(next);
246                         }
247                 }
248         }
249         return false;
250 }
251
252 void CycleGraph::startChanges()
253 {
254         ASSERT(rollbackvector.size() == 0);
255         ASSERT(rmwrollbackvector.size() == 0);
256         ASSERT(oldCycles == hasCycles);
257         ASSERT(oldRMWViolation == hasRMWViolation);
258 }
259
260 /** Commit changes to the cyclegraph. */
261 void CycleGraph::commitChanges()
262 {
263         rollbackvector.resize(0);
264         rmwrollbackvector.resize(0);
265         oldCycles = hasCycles;
266         oldRMWViolation = hasRMWViolation;
267 }
268
269 /** Rollback changes to the previous commit. */
270 void CycleGraph::rollbackChanges()
271 {
272         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
273                 rollbackvector[i]->popEdge();
274         }
275
276         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
277                 rmwrollbackvector[i]->clearRMW();
278         }
279
280         hasCycles = oldCycles;
281         hasRMWViolation = oldRMWViolation;
282         rollbackvector.resize(0);
283         rmwrollbackvector.resize(0);
284 }
285
286 /** @returns whether a CycleGraph contains cycles. */
287 bool CycleGraph::checkForCycles() const
288 {
289         return hasCycles;
290 }
291
292 bool CycleGraph::checkForRMWViolation() const
293 {
294         return hasRMWViolation;
295 }
296
297 /**
298  * @brief Constructor for a CycleNode
299  * @param act The ModelAction for this node
300  */
301 CycleNode::CycleNode(const ModelAction *act) :
302         action(act),
303         hasRMW(NULL)
304 {
305 }
306
307 /**
308  * @param i The index of the edge to return
309  * @returns The a CycleNode edge indexed by i
310  */
311 CycleNode * CycleNode::getEdge(unsigned int i) const
312 {
313         return edges[i];
314 }
315
316 /** @returns The number of edges leaving this CycleNode */
317 unsigned int CycleNode::getNumEdges() const
318 {
319         return edges.size();
320 }
321
322 CycleNode * CycleNode::getBackEdge(unsigned int i) const
323 {
324         return back_edges[i];
325 }
326
327 unsigned int CycleNode::getNumBackEdges() const
328 {
329         return back_edges.size();
330 }
331
332 /**
333  * Adds an edge from this CycleNode to another CycleNode.
334  * @param node The node to which we add a directed edge
335  */
336 bool CycleNode::addEdge(CycleNode *node)
337 {
338         for (unsigned int i = 0; i < edges.size(); i++)
339                 if (edges[i] == node)
340                         return false;
341         edges.push_back(node);
342         node->back_edges.push_back(this);
343         return true;
344 }
345
346 /** @returns the RMW CycleNode that reads from the current CycleNode */
347 CycleNode * CycleNode::getRMW() const
348 {
349         return hasRMW;
350 }
351
352 /**
353  * Set a RMW action node that reads from the current CycleNode.
354  * @param node The RMW that reads from the current node
355  * @return True, if this node already was read by another RMW; false otherwise
356  * @see CycleGraph::addRMWEdge
357  */
358 bool CycleNode::setRMW(CycleNode *node)
359 {
360         if (hasRMW != NULL)
361                 return true;
362         hasRMW = node;
363         return false;
364 }