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