cyclegraph.cc

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