cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3 #include "common.h"
   4 #include "promise.h"
   5 #include "threads-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         queue(new ModelVector<const CycleNode *>()),
  11         hasCycles(false),
  12         oldCycles(false)
  13 {
  14 }
  15
  16 /** CycleGraph destructor */
  17 CycleGraph::~CycleGraph()
  18 {
  19         delete queue;
  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  * Add a CycleNode to the graph, corresponding to a Promise
  38  * @param promise The Promise that should be added
  39  * @param node The CycleNode that corresponds to the Promise
  40  */
  41 void CycleGraph::putNode(const Promise *promise, CycleNode *node)
  42 {
  43         promiseToNode.put(promise, node);
  44 #if SUPPORT_MOD_ORDER_DUMP
  45         nodeList.push_back(node);
  46 #endif
  47 }
  48
  49 /**
  50  * @brief Remove the Promise node from the graph
  51  * @param promise The promise to remove from the graph
  52  */
  53 void CycleGraph::erasePromiseNode(const Promise *promise)
  54 {
  55         promiseToNode.put(promise, NULL);
  56 #if SUPPORT_MOD_ORDER_DUMP
  57         /* Remove the promise node from nodeList */
  58         CycleNode *node = getNode_noCreate(promise);
  59         for (unsigned int i = 0; i < nodeList.size(); )
  60                 if (nodeList[i] == node)
  61                         nodeList.erase(nodeList.begin() + i);
  62                 else
  63                         i++;
  64 #endif
  65 }
  66
  67 /** @return The corresponding CycleNode, if exists; otherwise NULL */
  68 CycleNode * CycleGraph::getNode_noCreate(const ModelAction *act) const
  69 {
  70         return actionToNode.get(act);
  71 }
  72
  73 /** @return The corresponding CycleNode, if exists; otherwise NULL */
  74 CycleNode * CycleGraph::getNode_noCreate(const Promise *promise) const
  75 {
  76         return promiseToNode.get(promise);
  77 }
  78
  79 /**
  80  * @brief Returns the CycleNode corresponding to a given ModelAction
  81  *
  82  * Gets (or creates, if none exist) a CycleNode corresponding to a ModelAction
  83  *
  84  * @param action The ModelAction to find a node for
  85  * @return The CycleNode paired with this action
  86  */
  87 CycleNode * CycleGraph::getNode(const ModelAction *action)
  88 {
  89         CycleNode *node = getNode_noCreate(action);
  90         if (node == NULL) {
  91                 node = new CycleNode(action);
  92                 putNode(action, node);
  93         }
  94         return node;
  95 }
  96
  97 /**
  98  * @brief Returns a CycleNode corresponding to a promise
  99  *
 100  * Gets (or creates, if none exist) a CycleNode corresponding to a promised
 101  * value.
 102  *
 103  * @param promise The Promise generated by a reader
 104  * @return The CycleNode corresponding to the Promise
 105  */
 106 CycleNode * CycleGraph::getNode(const Promise *promise)
 107 {
 108         CycleNode *node = getNode_noCreate(promise);
 109         if (node == NULL) {
 110                 node = new CycleNode(promise);
 111                 putNode(promise, node);
 112         }
 113         return node;
 114 }
 115
 116 /**
 117  * Resolve/satisfy a Promise with a particular store ModelAction, taking care
 118  * of the CycleGraph cleanups, including merging any necessary CycleNodes.
 119  *
 120  * @param promise The Promise to resolve
 121  * @param writer The store that will resolve this Promise
 122  * @return false if the resolution results in a cycle (or fails in some other
 123  * way); true otherwise
 124  */
 125 bool CycleGraph::resolvePromise(const Promise *promise, ModelAction *writer)
 126 {
 127         CycleNode *promise_node = promiseToNode.get(promise);
 128         CycleNode *w_node = actionToNode.get(writer);
 129         ASSERT(promise_node);
 130
 131         if (w_node)
 132                 return mergeNodes(w_node, promise_node);
 133         /* No existing write-node; just convert the promise-node */
 134         promise_node->resolvePromise(writer);
 135         erasePromiseNode(promise_node->getPromise());
 136         putNode(writer, promise_node);
 137         return true;
 138 }
 139
 140 /**
 141  * @brief Merge two CycleNodes that represent the same write
 142  *
 143  * Note that this operation cannot be rolled back.
 144  *
 145  * @param w_node The write ModelAction node with which to merge
 146  * @param p_node The Promise node to merge. Will be destroyed after this
 147  * function.
 148  *
 149  * @return false if the merge cannot succeed; true otherwise
 150  */
 151 bool CycleGraph::mergeNodes(CycleNode *w_node, CycleNode *p_node)
 152 {
 153         ASSERT(!w_node->is_promise());
 154         ASSERT(p_node->is_promise());
 155
 156         const Promise *promise = p_node->getPromise();
 157         if (!promise->is_compatible(w_node->getAction()) ||
 158                         !promise->same_value(w_node->getAction()))
 159                 return false;
 160
 161         /* Transfer the RMW */
 162         CycleNode *promise_rmw = p_node->getRMW();
 163         if (promise_rmw && promise_rmw != w_node->getRMW() && w_node->setRMW(promise_rmw))
 164                 return false;
 165
 166         /* Transfer back edges to w_node */
 167         while (p_node->getNumBackEdges() > 0) {
 168                 CycleNode *back = p_node->removeBackEdge();
 169                 if (back == w_node)
 170                         continue;
 171                 addNodeEdge(back, w_node);
 172                 if (hasCycles)
 173                         return false;
 174         }
 175
 176         /* Transfer forward edges to w_node */
 177         while (p_node->getNumEdges() > 0) {
 178                 CycleNode *forward = p_node->removeEdge();
 179                 if (forward == w_node)
 180                         continue;
 181                 addNodeEdge(w_node, forward);
 182                 if (hasCycles)
 183                         return false;
 184         }
 185
 186         erasePromiseNode(promise);
 187         /* Not deleting p_node, to maintain consistency if mergeNodes() fails */
 188
 189         return !hasCycles;
 190 }
 191
 192 /**
 193  * Adds an edge between two CycleNodes.
 194  * @param fromnode The edge comes from this CycleNode
 195  * @param tonode The edge points to this CycleNode
 196  * @return True, if new edge(s) are added; otherwise false
 197  */
 198 bool CycleGraph::addNodeEdge(CycleNode *fromnode, CycleNode *tonode)
 199 {
 200         if (fromnode->addEdge(tonode)) {
 201                 rollbackvector.push_back(fromnode);
 202                 if (!hasCycles)
 203                         hasCycles = checkReachable(tonode, fromnode);
 204         } else
 205                 return false; /* No new edge */
 206
 207         /*
 208          * If the fromnode has a rmwnode that is not the tonode, we should
 209          * follow its RMW chain to add an edge at the end, unless we encounter
 210          * tonode along the way
 211          */
 212         CycleNode *rmwnode = fromnode->getRMW();
 213         if (rmwnode) {
 214                 while (rmwnode != tonode && rmwnode->getRMW())
 215                         rmwnode = rmwnode->getRMW();
 216
 217                 if (rmwnode != tonode) {
 218                         if (rmwnode->addEdge(tonode)) {
 219                                 if (!hasCycles)
 220                                         hasCycles = checkReachable(tonode, rmwnode);
 221
 222                                 rollbackvector.push_back(rmwnode);
 223                         }
 224                 }
 225         }
 226         return true;
 227 }
 228
 229 /**
 230  * @brief Add an edge between a write and the RMW which reads from it
 231  *
 232  * Handles special case of a RMW action, where the ModelAction rmw reads from
 233  * the ModelAction/Promise from. The key differences are:
 234  *  -# No write can occur in between the @a rmw and @a from actions.
 235  *  -# Only one RMW action can read from a given write.
 236  *
 237  * @param from The edge comes from this ModelAction/Promise
 238  * @param rmw The edge points to this ModelAction; this action must read from
 239  * the ModelAction/Promise from
 240  */
 241 template <typename T>
 242 void CycleGraph::addRMWEdge(const T *from, const ModelAction *rmw)
 243 {
 244         ASSERT(from);
 245         ASSERT(rmw);
 246
 247         CycleNode *fromnode = getNode(from);
 248         CycleNode *rmwnode = getNode(rmw);
 249
 250         /* We assume that this RMW has no RMW reading from it yet */
 251         ASSERT(!rmwnode->getRMW());
 252
 253         /* Two RMW actions cannot read from the same write. */
 254         if (fromnode->setRMW(rmwnode))
 255                 hasCycles = true;
 256         else
 257                 rmwrollbackvector.push_back(fromnode);
 258
 259         /* Transfer all outgoing edges from the from node to the rmw node */
 260         /* This process should not add a cycle because either:
 261          * (1) The rmw should not have any incoming edges yet if it is the
 262          * new node or
 263          * (2) the fromnode is the new node and therefore it should not
 264          * have any outgoing edges.
 265          */
 266         for (unsigned int i = 0; i < fromnode->getNumEdges(); i++) {
 267                 CycleNode *tonode = fromnode->getEdge(i);
 268                 if (tonode != rmwnode) {
 269                         if (rmwnode->addEdge(tonode))
 270                                 rollbackvector.push_back(rmwnode);
 271                 }
 272         }
 273
 274         addNodeEdge(fromnode, rmwnode);
 275 }
 276 /* Instantiate two forms of CycleGraph::addRMWEdge */
 277 template void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw);
 278 template void CycleGraph::addRMWEdge(const Promise *from, const ModelAction *rmw);
 279
 280 /**
 281  * @brief Adds an edge between objects
 282  *
 283  * This function will add an edge between any two objects which can be
 284  * associated with a CycleNode. That is, if they have a CycleGraph::getNode
 285  * implementation.
 286  *
 287  * The object to is ordered after the object from.
 288  *
 289  * @param to The edge points to this object, of type T
 290  * @param from The edge comes from this object, of type U
 291  * @return True, if new edge(s) are added; otherwise false
 292  */
 293 template <typename T, typename U>
 294 bool CycleGraph::addEdge(const T *from, const U *to)
 295 {
 296         ASSERT(from);
 297         ASSERT(to);
 298
 299         CycleNode *fromnode = getNode(from);
 300         CycleNode *tonode = getNode(to);
 301
 302         return addNodeEdge(fromnode, tonode);
 303 }
 304 /* Instantiate four forms of CycleGraph::addEdge */
 305 template bool CycleGraph::addEdge(const ModelAction *from, const ModelAction *to);
 306 template bool CycleGraph::addEdge(const ModelAction *from, const Promise *to);
 307 template bool CycleGraph::addEdge(const Promise *from, const ModelAction *to);
 308 template bool CycleGraph::addEdge(const Promise *from, const Promise *to);
 309
 310 #if SUPPORT_MOD_ORDER_DUMP
 311
 312 static void print_node(FILE *file, const CycleNode *node, int label)
 313 {
 314         if (node->is_promise()) {
 315                 const Promise *promise = node->getPromise();
 316                 int idx = promise->get_index();
 317                 fprintf(file, "P%u", idx);
 318                 if (label) {
 319                         int first = 1;
 320                         fprintf(file, " [label=\"P%d, T", idx);
 321                         for (unsigned int i = 0 ; i < promise->max_available_thread_idx(); i++)
 322                                 if (promise->thread_is_available(int_to_id(i))) {
 323                                         fprintf(file, "%s%u", first ? "": ",", i);
 324                                         first = 0;
 325                                 }
 326                         fprintf(file, "\"]");
 327                 }
 328         } else {
 329                 const ModelAction *act = node->getAction();
 330                 modelclock_t idx = act->get_seq_number();
 331                 fprintf(file, "N%u", idx);
 332                 if (label)
 333                         fprintf(file, " [label=\"N%u, T%u\"]", idx, act->get_tid());
 334         }
 335 }
 336
 337 static void print_edge(FILE *file, const CycleNode *from, const CycleNode *to, const char *prop)
 338 {
 339         print_node(file, from, 0);
 340         fprintf(file, " -> ");
 341         print_node(file, to, 0);
 342         if (prop && strlen(prop))
 343                 fprintf(file, " [%s]", prop);
 344         fprintf(file, ";\n");
 345 }
 346
 347 void CycleGraph::dot_print_node(FILE *file, const ModelAction *act)
 348 {
 349         print_node(file, getNode(act), 1);
 350 }
 351
 352 template <typename T, typename U>
 353 void CycleGraph::dot_print_edge(FILE *file, const T *from, const U *to, const char *prop)
 354 {
 355         CycleNode *fromnode = getNode(from);
 356         CycleNode *tonode = getNode(to);
 357
 358         print_edge(file, fromnode, tonode, prop);
 359 }
 360 /* Instantiate two forms of CycleGraph::dot_print_edge */
 361 template void CycleGraph::dot_print_edge(FILE *file, const Promise *from, const ModelAction *to, const char *prop);
 362 template void CycleGraph::dot_print_edge(FILE *file, const ModelAction *from, const ModelAction *to, const char *prop);
 363
 364 void CycleGraph::dumpNodes(FILE *file) const
 365 {
 366         for (unsigned int i = 0; i < nodeList.size(); i++) {
 367                 CycleNode *n = nodeList[i];
 368                 print_node(file, n, 1);
 369                 fprintf(file, ";\n");
 370                 if (n->getRMW())
 371                         print_edge(file, n, n->getRMW(), "style=dotted");
 372                 for (unsigned int j = 0; j < n->getNumEdges(); j++)
 373                         print_edge(file, n, n->getEdge(j), NULL);
 374         }
 375 }
 376
 377 void CycleGraph::dumpGraphToFile(const char *filename) const
 378 {
 379         char buffer[200];
 380         sprintf(buffer, "%s.dot", filename);
 381         FILE *file = fopen(buffer, "w");
 382         fprintf(file, "digraph %s {\n", filename);
 383         dumpNodes(file);
 384         fprintf(file, "}\n");
 385         fclose(file);
 386 }
 387 #endif
 388
 389 /**
 390  * Checks whether one CycleNode can reach another.
 391  * @param from The CycleNode from which to begin exploration
 392  * @param to The CycleNode to reach
 393  * @return True, @a from can reach @a to; otherwise, false
 394  */
 395 bool CycleGraph::checkReachable(const CycleNode *from, const CycleNode *to) const
 396 {
 397         discovered->reset();
 398         queue->clear();
 399         queue->push_back(from);
 400         discovered->put(from, from);
 401         while (!queue->empty()) {
 402                 const CycleNode *node = queue->back();
 403                 queue->pop_back();
 404                 if (node == to)
 405                         return true;
 406                 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
 407                         CycleNode *next = node->getEdge(i);
 408                         if (!discovered->contains(next)) {
 409                                 discovered->put(next, next);
 410                                 queue->push_back(next);
 411                         }
 412                 }
 413         }
 414         return false;
 415 }
 416
 417 /**
 418  * Checks whether one ModelAction/Promise can reach another ModelAction/Promise
 419  * @param from The ModelAction or Promise from which to begin exploration
 420  * @param to The ModelAction or Promise to reach
 421  * @return True, @a from can reach @a to; otherwise, false
 422  */
 423 template <typename T, typename U>
 424 bool CycleGraph::checkReachable(const T *from, const U *to) const
 425 {
 426         CycleNode *fromnode = getNode_noCreate(from);
 427         CycleNode *tonode = getNode_noCreate(to);
 428
 429         if (!fromnode || !tonode)
 430                 return false;
 431
 432         return checkReachable(fromnode, tonode);
 433 }
 434 /* Instantiate four forms of CycleGraph::checkReachable */
 435 template bool CycleGraph::checkReachable(const ModelAction *from,
 436                 const ModelAction *to) const;
 437 template bool CycleGraph::checkReachable(const ModelAction *from,
 438                 const Promise *to) const;
 439 template bool CycleGraph::checkReachable(const Promise *from,
 440                 const ModelAction *to) const;
 441 template bool CycleGraph::checkReachable(const Promise *from,
 442                 const Promise *to) const;
 443
 444 /** @return True, if the promise has failed; false otherwise */
 445 bool CycleGraph::checkPromise(const ModelAction *fromact, Promise *promise) const
 446 {
 447         discovered->reset();
 448         queue->clear();
 449         CycleNode *from = actionToNode.get(fromact);
 450
 451         queue->push_back(from);
 452         discovered->put(from, from);
 453         while (!queue->empty()) {
 454                 const CycleNode *node = queue->back();
 455                 queue->pop_back();
 456
 457                 if (node->getPromise() == promise)
 458                         return true;
 459                 if (!node->is_promise() &&
 460                                 promise->eliminate_thread(node->getAction()->get_tid()))
 461                         return true;
 462
 463                 for (unsigned int i = 0; i < node->getNumEdges(); i++) {
 464                         CycleNode *next = node->getEdge(i);
 465                         if (!discovered->contains(next)) {
 466                                 discovered->put(next, next);
 467                                 queue->push_back(next);
 468                         }
 469                 }
 470         }
 471         return false;
 472 }
 473
 474 /** @brief Begin a new sequence of graph additions which can be rolled back */
 475 void CycleGraph::startChanges()
 476 {
 477         ASSERT(rollbackvector.empty());
 478         ASSERT(rmwrollbackvector.empty());
 479         ASSERT(oldCycles == hasCycles);
 480 }
 481
 482 /** Commit changes to the cyclegraph. */
 483 void CycleGraph::commitChanges()
 484 {
 485         rollbackvector.clear();
 486         rmwrollbackvector.clear();
 487         oldCycles = hasCycles;
 488 }
 489
 490 /** Rollback changes to the previous commit. */
 491 void CycleGraph::rollbackChanges()
 492 {
 493         for (unsigned int i = 0; i < rollbackvector.size(); i++)
 494                 rollbackvector[i]->removeEdge();
 495
 496         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++)
 497                 rmwrollbackvector[i]->clearRMW();
 498
 499         hasCycles = oldCycles;
 500         rollbackvector.clear();
 501         rmwrollbackvector.clear();
 502 }
 503
 504 /** @returns whether a CycleGraph contains cycles. */
 505 bool CycleGraph::checkForCycles() const
 506 {
 507         return hasCycles;
 508 }
 509
 510 /**
 511  * @brief Constructor for a CycleNode
 512  * @param act The ModelAction for this node
 513  */
 514 CycleNode::CycleNode(const ModelAction *act) :
 515         action(act),
 516         promise(NULL),
 517         hasRMW(NULL)
 518 {
 519 }
 520
 521 /**
 522  * @brief Constructor for a Promise CycleNode
 523  * @param promise The Promise which was generated
 524  */
 525 CycleNode::CycleNode(const Promise *promise) :
 526         action(NULL),
 527         promise(promise),
 528         hasRMW(NULL)
 529 {
 530 }
 531
 532 /**
 533  * @param i The index of the edge to return
 534  * @returns The CycleNode edge indexed by i
 535  */
 536 CycleNode * CycleNode::getEdge(unsigned int i) const
 537 {
 538         return edges[i];
 539 }
 540
 541 /** @returns The number of edges leaving this CycleNode */
 542 unsigned int CycleNode::getNumEdges() const
 543 {
 544         return edges.size();
 545 }
 546
 547 /**
 548  * @param i The index of the back edge to return
 549  * @returns The CycleNode back-edge indexed by i
 550  */
 551 CycleNode * CycleNode::getBackEdge(unsigned int i) const
 552 {
 553         return back_edges[i];
 554 }
 555
 556 /** @returns The number of edges entering this CycleNode */
 557 unsigned int CycleNode::getNumBackEdges() const
 558 {
 559         return back_edges.size();
 560 }
 561
 562 /**
 563  * @brief Remove an element from a vector
 564  * @param v The vector
 565  * @param n The element to remove
 566  * @return True if the element was found; false otherwise
 567  */
 568 template <typename T>
 569 static bool vector_remove_node(SnapVector<T>& v, const T n)
 570 {
 571         for (unsigned int i = 0; i < v.size(); i++) {
 572                 if (v[i] == n) {
 573                         v.erase(v.begin() + i);
 574                         return true;
 575                 }
 576         }
 577         return false;
 578 }
 579
 580 /**
 581  * @brief Remove a (forward) edge from this CycleNode
 582  * @return The CycleNode which was popped, if one exists; otherwise NULL
 583  */
 584 CycleNode * CycleNode::removeEdge()
 585 {
 586         if (edges.empty())
 587                 return NULL;
 588
 589         CycleNode *ret = edges.back();
 590         edges.pop_back();
 591         vector_remove_node(ret->back_edges, this);
 592         return ret;
 593 }
 594
 595 /**
 596  * @brief Remove a (back) edge from this CycleNode
 597  * @return The CycleNode which was popped, if one exists; otherwise NULL
 598  */
 599 CycleNode * CycleNode::removeBackEdge()
 600 {
 601         if (back_edges.empty())
 602                 return NULL;
 603
 604         CycleNode *ret = back_edges.back();
 605         back_edges.pop_back();
 606         vector_remove_node(ret->edges, this);
 607         return ret;
 608 }
 609
 610 /**
 611  * Adds an edge from this CycleNode to another CycleNode.
 612  * @param node The node to which we add a directed edge
 613  * @return True if this edge is a new edge; false otherwise
 614  */
 615 bool CycleNode::addEdge(CycleNode *node)
 616 {
 617         for (unsigned int i = 0; i < edges.size(); i++)
 618                 if (edges[i] == node)
 619                         return false;
 620         edges.push_back(node);
 621         node->back_edges.push_back(this);
 622         return true;
 623 }
 624
 625 /** @returns the RMW CycleNode that reads from the current CycleNode */
 626 CycleNode * CycleNode::getRMW() const
 627 {
 628         return hasRMW;
 629 }
 630
 631 /**
 632  * Set a RMW action node that reads from the current CycleNode.
 633  * @param node The RMW that reads from the current node
 634  * @return True, if this node already was read by another RMW; false otherwise
 635  * @see CycleGraph::addRMWEdge
 636  */
 637 bool CycleNode::setRMW(CycleNode *node)
 638 {
 639         if (hasRMW != NULL)
 640                 return true;
 641         hasRMW = node;
 642         return false;
 643 }
 644
 645 /**
 646  * Convert a Promise CycleNode into a concrete-valued CycleNode. Should only be
 647  * used when there's no existing ModelAction CycleNode for this write.
 648  *
 649  * @param writer The ModelAction which wrote the future value represented by
 650  * this CycleNode
 651  */
 652 void CycleNode::resolvePromise(const ModelAction *writer)
 653 {
 654         ASSERT(is_promise());
 655         ASSERT(promise->is_compatible(writer));
 656         action = writer;
 657         promise = NULL;
 658         ASSERT(!is_promise());
 659 }