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 = checkReachable(tonode, fromnode);
  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 = checkReachable(tonode, rmwnode);
  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 = checkReachable(rmwnode, fromnode);
 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 one ModelAction can reach another.
 165  * @param from The ModelAction from which to begin exploration
 166  * @param to The ModelAction to reach
 167  * @return True, @a from can reach @a to; otherwise, false
 168  */
 169 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) const
 170 {
 171         CycleNode *fromnode = actionToNode.get(from);
 172         CycleNode *tonode = actionToNode.get(to);
 173
 174         if (!fromnode || !tonode)
 175                 return false;
 176
 177         return checkReachable(fromnode, tonode);
 178 }
 179
 180 /**
 181  * Checks whether one CycleNode can reach another.
 182  * @param from The CycleNode from which to begin exploration
 183  * @param to The CycleNode to reach
 184  * @return True, @a from can reach @a to; otherwise, false
 185  */
 186 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
 187 {
 188         std::vector< const CycleNode *, ModelAlloc<const CycleNode *> > queue;
 189         discovered->reset();
 190
 191         queue.push_back(from);
 192         discovered->put(from, from);
 193         while (!queue.empty()) {
 194                 const CycleNode *node = queue.back();
 195                 queue.pop_back();
 196                 if (node == to)
 197                         return true;
 198
 199                 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
 200                         CycleNode *next = node->getEdge(i);
 201                         if (!discovered->contains(next)) {
 202                                 discovered->put(next, next);
 203                                 queue.push_back(next);
 204                         }
 205                 }
 206         }
 207         return false;
 208 }
 209
 210 bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) const
 211 {
 212         std::vector< CycleNode *, ModelAlloc<CycleNode *> > queue;
 213         discovered->reset();
 214         CycleNode *from = actionToNode.get(fromact);
 215
 216         queue.push_back(from);
 217         discovered->put(from, from);
 218         while (!queue.empty()) {
 219                 CycleNode *node = queue.back();
 220                 queue.pop_back();
 221
 222                 if (promise->increment_threads(node->getAction()->get_tid())) {
 223                         return true;
 224                 }
 225
 226                 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
 227                         CycleNode *next = node->getEdge(i);
 228                         if (!discovered->contains(next)) {
 229                                 discovered->put(next, next);
 230                                 queue.push_back(next);
 231                         }
 232                 }
 233         }
 234         return false;
 235 }
 236
 237 void CycleGraph::startChanges()
 238 {
 239         ASSERT(rollbackvector.size() == 0);
 240         ASSERT(rmwrollbackvector.size() == 0);
 241         ASSERT(oldCycles == hasCycles);
 242         ASSERT(oldRMWViolation == hasRMWViolation);
 243 }
 244
 245 /** Commit changes to the cyclegraph. */
 246 void CycleGraph::commitChanges()
 247 {
 248         rollbackvector.resize(0);
 249         rmwrollbackvector.resize(0);
 250         oldCycles = hasCycles;
 251         oldRMWViolation = hasRMWViolation;
 252 }
 253
 254 /** Rollback changes to the previous commit. */
 255 void CycleGraph::rollbackChanges()
 256 {
 257         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
 258                 rollbackvector[i]->popEdge();
 259         }
 260
 261         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
 262                 rmwrollbackvector[i]->clearRMW();
 263         }
 264
 265         hasCycles = oldCycles;
 266         hasRMWViolation = oldRMWViolation;
 267         rollbackvector.resize(0);
 268         rmwrollbackvector.resize(0);
 269 }
 270
 271 /** @returns whether a CycleGraph contains cycles. */
 272 bool CycleGraph::checkForCycles() const
 273 {
 274         return hasCycles;
 275 }
 276
 277 bool CycleGraph::checkForRMWViolation() const
 278 {
 279         return hasRMWViolation;
 280 }
 281
 282 /**
 283  * @brief Constructor for a CycleNode
 284  * @param act The ModelAction for this node
 285  */
 286 CycleNode::CycleNode(const ModelAction *act) :
 287         action(act),
 288         hasRMW(NULL)
 289 {
 290 }
 291
 292 /**
 293  * @param i The index of the edge to return
 294  * @returns The a CycleNode edge indexed by i
 295  */
 296 CycleNode * CycleNode::getEdge(unsigned int i) const
 297 {
 298         return edges[i];
 299 }
 300
 301 /** @returns The number of edges leaving this CycleNode */
 302 unsigned int CycleNode::getNumEdges() const
 303 {
 304         return edges.size();
 305 }
 306
 307 CycleNode * CycleNode::getBackEdge(unsigned int i) const
 308 {
 309         return back_edges[i];
 310 }
 311
 312 unsigned int CycleNode::getNumBackEdges() const
 313 {
 314         return back_edges.size();
 315 }
 316
 317 /**
 318  * Adds an edge from this CycleNode to another CycleNode.
 319  * @param node The node to which we add a directed edge
 320  * @return True if this edge is a new edge; false otherwise
 321  */
 322 bool CycleNode::addEdge(CycleNode *node)
 323 {
 324         for (unsigned int i = 0; i < edges.size(); i++)
 325                 if (edges[i] == node)
 326                         return false;
 327         edges.push_back(node);
 328         node->back_edges.push_back(this);
 329         return true;
 330 }
 331
 332 /** @returns the RMW CycleNode that reads from the current CycleNode */
 333 CycleNode * CycleNode::getRMW() const
 334 {
 335         return hasRMW;
 336 }
 337
 338 /**
 339  * Set a RMW action node that reads from the current CycleNode.
 340  * @param node The RMW that reads from the current node
 341  * @return True, if this node already was read by another RMW; false otherwise
 342  * @see CycleGraph::addRMWEdge
 343  */
 344 bool CycleNode::setRMW(CycleNode *node)
 345 {
 346         if (hasRMW != NULL)
 347                 return true;
 348         hasRMW = node;
 349         return false;
 350 }