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