cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3 #include "common.h"
   4 #include "threads-model.h"
   5
   6 /** Initializes a CycleGraph object. */
   7 CycleGraph::CycleGraph() :
   8         discovered(new HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free>(16)),
   9         queue(new ModelVector<const CycleNode *>()),
  10         hasCycles(false),
  11         oldCycles(false)
  12 {
  13 }
  14
  15 /** CycleGraph destructor */
  16 CycleGraph::~CycleGraph()
  17 {
  18         delete queue;
  19         delete discovered;
  20 }
  21
  22 /**
  23  * Add a CycleNode to the graph, corresponding to a store ModelAction
  24  * @param act The write action that should be added
  25  * @param node The CycleNode that corresponds to the store
  26  */
  27 void CycleGraph::putNode(const ModelAction *act, CycleNode *node)
  28 {
  29         actionToNode.put(act, node);
  30 #if SUPPORT_MOD_ORDER_DUMP
  31         nodeList.push_back(node);
  32 #endif
  33 }
  34
  35 /** @return The corresponding CycleNode, if exists; otherwise NULL */
  36 CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
  37 {
  38         return actionToNode.get(act);
  39 }
  40
  41 /**
  42  * @brief Returns the CycleNode corresponding to a given ModelAction
  43  *
  44  * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
  45  *
  46  * @param action The ModelAction to find a node for
  47  * @return The CycleNode paired with this action
  48  */
  49 CycleNode * CycleGraph::getNode(const ModelAction *action)
  50 {
  51         CycleNode *node = getNode_noCreate(action);
  52         if (node == NULL) {
  53                 node = new CycleNode(action);
  54                 putNode(action, node);
  55         }
  56         return node;
  57 }
  58
  59 /**
  60  * Adds an edge between two CycleNodes.
  61  * @param fromnode The edge comes from this CycleNode
  62  * @param tonode The edge points to this CycleNode
  63  * @return True, if new edge(s) are added; otherwise false
  64  */
  65 bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
  66 {
  67         if (fromnode->addEdge(tonode)) {
  68                 rollbackvector.push_back(fromnode);
  69                 if (!hasCycles)
  70                         hasCycles = checkReachable(tonode, fromnode);
  71         } else
  72                 return false;/* No new edge */
  73
  74         /*
  75          * If the fromnode has a rmwnode that is not the tonode, we should
  76          * follow its RMW chain to add an edge at the end, unless we encounter
  77          * tonode along the way
  78          */
  79         CycleNode *rmwnode = fromnode->getRMW();
  80         if (rmwnode) {
  81                 while (rmwnode != tonode && rmwnode->getRMW())
  82                         rmwnode = rmwnode->getRMW();
  83
  84                 if (rmwnode != tonode) {
  85                         if (rmwnode->addEdge(tonode)) {
  86                                 if (!hasCycles)
  87                                         hasCycles = checkReachable(tonode, rmwnode);
  88
  89                                 rollbackvector.push_back(rmwnode);
  90                         }
  91                 }
  92         }
  93         return true;
  94 }
  95
  96 /**
  97  * @brief Add an edge between a write and the RMW which reads from it
  98  *
  99  * Handles special case of a RMW action, where the ModelAction rmw reads from
 100  * the ModelAction/Promise from. The key differences are:
 101  *  -# No write can occur in between the @a rmw and @a from actions.
 102  *  -# Only one RMW action can read from a given write.
 103  *
 104  * @param from The edge comes from this ModelAction/Promise
 105  * @param rmw The edge points to this ModelAction; this action must read from
 106  * the ModelAction/Promise from
 107  */
 108 template <typename T>
 109 void CycleGraph::addRMWEdge(const T *from, const ModelAction *rmw)
 110 {
 111         ASSERT(from);
 112         ASSERT(rmw);
 113
 114         CycleNode *fromnode = getNode(from);
 115         CycleNode *rmwnode = getNode(rmw);
 116
 117         /* We assume that this RMW has no RMW reading from it yet */
 118         ASSERT(!rmwnode->getRMW());
 119
 120         /* Two RMW actions cannot read from the same write. */
 121         if (fromnode->setRMW(rmwnode))
 122                 hasCycles = true;
 123         else
 124                 rmwrollbackvector.push_back(fromnode);
 125
 126         /* Transfer all outgoing edges from the from node to the rmw node */
 127         /* This process should not add a cycle because either:
 128          * (1) The rmw should not have any incoming edges yet if it is the
 129          * new node or
 130          * (2) the fromnode is the new node and therefore it should not
 131          * have any outgoing edges.
 132          */
 133         for (unsigned int i = 0;i < fromnode->getNumEdges();i++) {
 134                 CycleNode *tonode = fromnode->getEdge(i);
 135                 if (tonode != rmwnode) {
 136                         if (rmwnode->addEdge(tonode))
 137                                 rollbackvector.push_back(rmwnode);
 138                 }
 139         }
 140
 141         addNodeEdge(fromnode, rmwnode);
 142 }
 143 /* Instantiate two forms of CycleGraph::addRMWEdge */
 144 template void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw);
 145
 146 /**
 147  * @brief Adds an edge between objects
 148  *
 149  * This function will add an edge between any two objects which can be
 150  * associated with a CycleNode. That is, if they have a CycleGraph::getNode
 151  * implementation.
 152  *
 153  * The object to is ordered after the object from.
 154  *
 155  * @param to The edge points to this object, of type T
 156  * @param from The edge comes from this object, of type U
 157  * @return True, if new edge(s) are added; otherwise false
 158  */
 159 template <typename T, typename U>
 160 bool CycleGraph::addEdge(const T *from, const U *to)
 161 {
 162         ASSERT(from);
 163         ASSERT(to);
 164
 165         CycleNode *fromnode = getNode(from);
 166         CycleNode *tonode = getNode(to);
 167
 168         return addNodeEdge(fromnode, tonode);
 169 }
 170 /* Instantiate four forms of CycleGraph::addEdge */
 171 template bool CycleGraph::addEdge(const ModelAction *from, const ModelAction *to);
 172
 173 #if SUPPORT_MOD_ORDER_DUMP
 174
 175 static void print_node(FILE *file, const CycleNode *node, int label)
 176 {
 177         const ModelAction *act = node->getAction();
 178         modelclock_t idx = act->get_seq_number();
 179         fprintf(file, "N%u", idx);
 180         if (label)
 181                 fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
 182 }
 183
 184 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
 185 {
 186         print_node(file, from, 0);
 187         fprintf(file, " -> ");
 188         print_node(file, to, 0);
 189         if (prop && strlen(prop))
 190                 fprintf(file, " [%s]", prop);
 191         fprintf(file, ";\n");
 192 }
 193
 194 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
 195 {
 196         print_node(file, getNode(act), 1);
 197 }
 198
 199 template <typename T, typename U>
 200 void CycleGraph::dot_print_edge(FILE *file, const T *from, const U *to, const char *prop)
 201 {
 202         CycleNode *fromnode = getNode(from);
 203         CycleNode *tonode = getNode(to);
 204
 205         print_edge(file, fromnode, tonode, prop);
 206 }
 207 /* Instantiate two forms of CycleGraph::dot_print_edge */
 208 template void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop);
 209
 210 void CycleGraph::dumpNodes(FILE *file) const
 211 {
 212         for (unsigned int i = 0;i < nodeList.size();i++) {
 213                 CycleNode *n = nodeList[i];
 214                 print_node(file, n, 1);
 215                 fprintf(file, ";\n");
 216                 if (n->getRMW())
 217                         print_edge(file, n, n->getRMW(), "style=dotted");
 218                 for (unsigned int j = 0;j < n->getNumEdges();j++)
 219                         print_edge(file, n, n->getEdge(j), NULL);
 220         }
 221 }
 222
 223 void CycleGraph::dumpGraphToFile(const char *filename) const
 224 {
 225         char buffer[200];
 226         sprintf(buffer, "%s.dot", filename);
 227         FILE *file = fopen(buffer, "w");
 228         fprintf(file, "digraph %s {\n", filename);
 229         dumpNodes(file);
 230         fprintf(file, "}\n");
 231         fclose(file);
 232 }
 233 #endif
 234
 235 /**
 236  * Checks whether one CycleNode can reach another.
 237  * @param from The CycleNode from which to begin exploration
 238  * @param to The CycleNode to reach
 239  * @return True, @a from can reach @a to; otherwise, false
 240  */
 241 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
 242 {
 243         discovered->reset();
 244         queue->clear();
 245         queue->push_back(from);
 246         discovered->put(from, from);
 247         while (!queue->empty()) {
 248                 const CycleNode *node = queue->back();
 249                 queue->pop_back();
 250                 if (node == to)
 251                         return true;
 252                 for (unsigned int i = 0;i < node->getNumEdges();i++) {
 253                         CycleNode *next = node->getEdge(i);
 254                         if (!discovered->contains(next)) {
 255                                 discovered->put(next, next);
 256                                 queue->push_back(next);
 257                         }
 258                 }
 259         }
 260         return false;
 261 }
 262
 263 /**
 264  * Checks whether one ModelAction/Promise can reach another ModelAction/Promise
 265  * @param from The ModelAction or Promise from which to begin exploration
 266  * @param to The ModelAction or Promise to reach
 267  * @return True, @a from can reach @a to; otherwise, false
 268  */
 269 template <typename T, typename U>
 270 bool CycleGraph::checkReachable(const T *from, const U *to) const
 271 {
 272         CycleNode *fromnode = getNode_noCreate(from);
 273         CycleNode *tonode = getNode_noCreate(to);
 274
 275         if (!fromnode || !tonode)
 276                 return false;
 277
 278         return checkReachable(fromnode, tonode);
 279 }
 280 /* Instantiate four forms of CycleGraph::checkReachable */
 281 template bool CycleGraph::checkReachable(const ModelAction *from,
 282                                                                                                                                                                  const ModelAction *to) const;
 283
 284 /** @brief Begin a new sequence of graph additions which can be rolled back */
 285 void CycleGraph::startChanges()
 286 {
 287         ASSERT(rollbackvector.empty());
 288         ASSERT(rmwrollbackvector.empty());
 289         ASSERT(oldCycles == hasCycles);
 290 }
 291
 292 /** Commit changes to the cyclegraph. */
 293 void CycleGraph::commitChanges()
 294 {
 295         rollbackvector.clear();
 296         rmwrollbackvector.clear();
 297         oldCycles = hasCycles;
 298 }
 299
 300 /** Rollback changes to the previous commit. */
 301 void CycleGraph::rollbackChanges()
 302 {
 303         for (unsigned int i = 0;i < rollbackvector.size();i++)
 304                 rollbackvector[i]->removeEdge();
 305
 306         for (unsigned int i = 0;i < rmwrollbackvector.size();i++)
 307                 rmwrollbackvector[i]->clearRMW();
 308
 309         hasCycles = oldCycles;
 310         rollbackvector.clear();
 311         rmwrollbackvector.clear();
 312 }
 313
 314 /** @returns whether a CycleGraph contains cycles. */
 315 bool CycleGraph::checkForCycles() const
 316 {
 317         return hasCycles;
 318 }
 319
 320 /**
 321  * @brief Constructor for a CycleNode
 322  * @param act The ModelAction for this node
 323  */
 324 CycleNode::CycleNode(const ModelAction *act) :
 325         action(act),
 326         hasRMW(NULL)
 327 {
 328 }
 329
 330 /**
 331  * @param i The index of the edge to return
 332  * @returns The CycleNode edge indexed by i
 333  */
 334 CycleNode * CycleNode::getEdge(unsigned int i) const
 335 {
 336         return edges[i];
 337 }
 338
 339 /** @returns The number of edges leaving this CycleNode */
 340 unsigned int CycleNode::getNumEdges() const
 341 {
 342         return edges.size();
 343 }
 344
 345 /**
 346  * @brief Remove an element from a vector
 347  * @param v The vector
 348  * @param n The element to remove
 349  * @return True if the element was found; false otherwise
 350  */
 351 template <typename T>
 352 static bool vector_remove_node(SnapVector<T>& v, const T n)
 353 {
 354         for (unsigned int i = 0;i < v.size();i++) {
 355                 if (v[i] == n) {
 356                         v.erase(v.begin() + i);
 357                         return true;
 358                 }
 359         }
 360         return false;
 361 }
 362
 363 /**
 364  * @brief Remove a (forward) edge from this CycleNode
 365  * @return The CycleNode which was popped, if one exists; otherwise NULL
 366  */
 367 CycleNode * CycleNode::removeEdge()
 368 {
 369         if (edges.empty())
 370                 return NULL;
 371
 372         CycleNode *ret = edges.back();
 373         edges.pop_back();
 374         return ret;
 375 }
 376
 377 /**
 378  * Adds an edge from this CycleNode to another CycleNode.
 379  * @param node The node to which we add a directed edge
 380  * @return True if this edge is a new edge; false otherwise
 381  */
 382 bool CycleNode::addEdge(CycleNode *node)
 383 {
 384         for (unsigned int i = 0;i < edges.size();i++)
 385                 if (edges[i] == node)
 386                         return false;
 387         edges.push_back(node);
 388         return true;
 389 }
 390
 391 /** @returns the RMW CycleNode that reads from the current CycleNode */
 392 CycleNode * CycleNode::getRMW() const
 393 {
 394         return hasRMW;
 395 }
 396
 397 /**
 398  * Set a RMW action node that reads from the current CycleNode.
 399  * @param node The RMW that reads from the current node
 400  * @return True, if this node already was read by another RMW; false otherwise
 401  * @see CycleGraph::addRMWEdge
 402  */
 403 bool CycleNode::setRMW(CycleNode *node)
 404 {
 405         if (hasRMW != NULL)
 406                 return true;
 407         hasRMW = node;
 408         return false;
 409 }