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