cyclegraph.cc

   1 #include "cyclegraph.h"
   2 #include "action.h"
   3 #include "common.h"
   4
   5 /** Initializes a CycleGraph object. */
   6 CycleGraph::CycleGraph() :
   7         hasCycles(false),
   8         oldCycles(false),
   9         hasRMWViolation(false),
  10         oldRMWViolation(false)
  11 {
  12 }
  13
  14 /** CycleGraph destructor */
  15 CycleGraph::~CycleGraph() {
  16 }
  17
  18 /**
  19  * @brief Returns the CycleNode corresponding to a given ModelAction
  20  * @param action The ModelAction to find a node for
  21  * @return The CycleNode paired with this action
  22  */
  23 CycleNode * CycleGraph::getNode(const ModelAction *action) {
  24         CycleNode *node=actionToNode.get(action);
  25         if (node==NULL) {
  26                 node=new CycleNode(action);
  27                 actionToNode.put(action, node);
  28 #if SUPPORT_MOD_ORDER_DUMP
  29                 nodeList.push_back(node);
  30 #endif
  31         }
  32         return node;
  33 }
  34
  35 /**
  36  * Adds an edge between two ModelActions. The ModelAction @a to is ordered
  37  * after the ModelAction @a from.
  38  * @param to The edge points to this ModelAction
  39  * @param from The edge comes from this ModelAction
  40  */
  41 void CycleGraph::addEdge(const ModelAction *from, const ModelAction *to) {
  42         ASSERT(from);
  43         ASSERT(to);
  44         ASSERT(from != to);
  45
  46         CycleNode *fromnode=getNode(from);
  47         CycleNode *tonode=getNode(to);
  48
  49         if (!hasCycles) {
  50                 // Check for Cycles
  51                 hasCycles=checkReachable(tonode, fromnode);
  52         }
  53
  54         if (fromnode->addEdge(tonode))
  55                 rollbackvector.push_back(fromnode);
  56
  57
  58         CycleNode * rmwnode=fromnode->getRMW();
  59
  60         //If the fromnode has a rmwnode that is not the tonode, we
  61         //should add an edge between its rmwnode and the tonode
  62
  63         //If tonode is also a rmw, don't do this check as the execution is
  64         //doomed and we'll catch the problem elsewhere, but we want to allow
  65         //for the possibility of sending to's write value to rmwnode
  66
  67         if (rmwnode!=NULL&&!to->is_rmw()) {
  68                 if (!hasCycles) {
  69                         // Check for Cycles
  70                         hasCycles=checkReachable(tonode, rmwnode);
  71                 }
  72
  73                 if (rmwnode->addEdge(tonode))
  74                         rollbackvector.push_back(rmwnode);
  75         }
  76 }
  77
  78 /** Handles special case of a RMW action.  The ModelAction rmw reads
  79  *  from the ModelAction from.  The key differences are: (1) no write
  80  *  can occur in between the rmw and the from action.  Only one RMW
  81  *  action can read from a given write.
  82  */
  83 void CycleGraph::addRMWEdge(const ModelAction *from, const ModelAction *rmw) {
  84         ASSERT(from);
  85         ASSERT(rmw);
  86         ASSERT(from != rmw);
  87
  88         CycleNode *fromnode=getNode(from);
  89         CycleNode *rmwnode=getNode(rmw);
  90
  91         /* Two RMW actions cannot read from the same write. */
  92         if (fromnode->setRMW(rmwnode)) {
  93                 hasRMWViolation=true;
  94         } else {
  95                 rmwrollbackvector.push_back(fromnode);
  96         }
  97
  98         /* Transfer all outgoing edges from the from node to the rmw node */
  99         /* This process should not add a cycle because either:
 100          * (1) The rmw should not have any incoming edges yet if it is the
 101          * new node or
 102          * (2) the fromnode is the new node and therefore it should not
 103          * have any outgoing edges.
 104          */
 105         std::vector<CycleNode *> * edges=fromnode->getEdges();
 106         for(unsigned int i=0;i<edges->size();i++) {
 107                 CycleNode * tonode=(*edges)[i];
 108                 if (tonode!=rmwnode) {
 109                         if (rmwnode->addEdge(tonode))
 110                                 rollbackvector.push_back(rmwnode);
 111                 }
 112         }
 113
 114
 115         if (!hasCycles) {
 116                 // With promises we could be setting up a cycle here if we aren't
 117                 // careful...avoid it..
 118                 hasCycles=checkReachable(rmwnode, fromnode);
 119         }
 120         if(fromnode->addEdge(rmwnode))
 121                 rollbackvector.push_back(fromnode);
 122 }
 123
 124 #if SUPPORT_MOD_ORDER_DUMP
 125 void CycleGraph::dumpNodes(FILE *file) {
 126   for(unsigned int i=0;i<nodeList.size();i++) {
 127                 CycleNode *cn=nodeList[i];
 128                 std::vector<CycleNode *> * edges=cn->getEdges();
 129                 const ModelAction *action=cn->getAction();
 130                 fprintf(file, "N%u [label=\"%u, T%u\"];\n",action->get_seq_number(),action->get_seq_number(), action->get_tid());
 131                 if (cn->getRMW()!=NULL) {
 132                         fprintf(file, "N%u -> N%u[style=dotted];\n", action->get_seq_number(), cn->getRMW()->getAction()->get_seq_number());
 133                 }
 134                 for(unsigned int j=0;j<edges->size();j++) {
 135                   CycleNode *dst=(*edges)[j];
 136                         const ModelAction *dstaction=dst->getAction();
 137       fprintf(file, "N%u -> N%u;\n", action->get_seq_number(), dstaction->get_seq_number());
 138           }
 139         }
 140 }
 141
 142 void CycleGraph::dumpGraphToFile(const char *filename) {
 143         char buffer[200];
 144   sprintf(buffer, "%s.dot",filename);
 145   FILE *file=fopen(buffer, "w");
 146   fprintf(file, "digraph %s {\n",filename);
 147         dumpNodes(file);
 148   fprintf(file,"}\n");
 149   fclose(file);
 150 }
 151 #endif
 152
 153 /**
 154  * Checks whether one ModelAction can reach another.
 155  * @param from The ModelAction from which to begin exploration
 156  * @param to The ModelAction to reach
 157  * @return True, @a from can reach @a to; otherwise, false
 158  */
 159 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) {
 160         CycleNode *fromnode = actionToNode.get(from);
 161         CycleNode *tonode = actionToNode.get(to);
 162
 163         if (!fromnode || !tonode)
 164                 return false;
 165
 166         return checkReachable(fromnode, tonode);
 167 }
 168
 169 /**
 170  * Checks whether one CycleNode can reach another.
 171  * @param from The CycleNode from which to begin exploration
 172  * @param to The CycleNode to reach
 173  * @return True, @a from can reach @a to; otherwise, false
 174  */
 175 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
 176         std::vector<CycleNode *, ModelAlloc<CycleNode *> > queue;
 177         HashTable<CycleNode *, CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free> discovered;
 178
 179         queue.push_back(from);
 180         discovered.put(from, from);
 181         while(!queue.empty()) {
 182                 CycleNode * node=queue.back();
 183                 queue.pop_back();
 184                 if (node==to)
 185                         return true;
 186
 187                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
 188                         CycleNode *next=(*node->getEdges())[i];
 189                         if (!discovered.contains(next)) {
 190                                 discovered.put(next,next);
 191                                 queue.push_back(next);
 192                         }
 193                 }
 194         }
 195         return false;
 196 }
 197
 198 void CycleGraph::startChanges() {
 199         ASSERT(rollbackvector.size()==0);
 200         ASSERT(rmwrollbackvector.size()==0);
 201         ASSERT(oldCycles==hasCycles);
 202         ASSERT(oldRMWViolation==hasRMWViolation);
 203 }
 204
 205 /** Commit changes to the cyclegraph. */
 206 void CycleGraph::commitChanges() {
 207         rollbackvector.resize(0);
 208         rmwrollbackvector.resize(0);
 209         oldCycles=hasCycles;
 210         oldRMWViolation=hasRMWViolation;
 211 }
 212
 213 /** Rollback changes to the previous commit. */
 214 void CycleGraph::rollbackChanges() {
 215         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
 216                 rollbackvector[i]->popEdge();
 217         }
 218
 219         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
 220                 rmwrollbackvector[i]->clearRMW();
 221         }
 222
 223         hasCycles = oldCycles;
 224         hasRMWViolation = oldRMWViolation;
 225         rollbackvector.resize(0);
 226         rmwrollbackvector.resize(0);
 227 }
 228
 229 /** @returns whether a CycleGraph contains cycles. */
 230 bool CycleGraph::checkForCycles() {
 231         return hasCycles;
 232 }
 233
 234 bool CycleGraph::checkForRMWViolation() {
 235         return hasRMWViolation;
 236 }
 237
 238 /**
 239  * Constructor for a CycleNode.
 240  * @param modelaction The ModelAction for this node
 241  */
 242 CycleNode::CycleNode(const ModelAction *modelaction) :
 243         action(modelaction),
 244         hasRMW(NULL)
 245 {
 246 }
 247
 248 /** @returns a vector of the edges from a CycleNode. */
 249 std::vector<CycleNode *> * CycleNode::getEdges() {
 250         return &edges;
 251 }
 252
 253 /**
 254  * Adds an edge from this CycleNode to another CycleNode.
 255  * @param node The node to which we add a directed edge
 256  */
 257 bool CycleNode::addEdge(CycleNode *node) {
 258         for(unsigned int i=0;i<edges.size();i++)
 259                 if (edges[i]==node)
 260                         return false;
 261         edges.push_back(node);
 262         return true;
 263 }
 264
 265 /** @returns the RMW CycleNode that reads from the current CycleNode */
 266 CycleNode * CycleNode::getRMW() {
 267         return hasRMW;
 268 }
 269
 270 /**
 271  * Set a RMW action node that reads from the current CycleNode.
 272  * @param node The RMW that reads from the current node
 273  * @return True, if this node already was read by another RMW; false otherwise
 274  * @see CycleGraph::addRMWEdge
 275  */
 276 bool CycleNode::setRMW(CycleNode *node) {
 277         if (hasRMW!=NULL)
 278                 return true;
 279         hasRMW=node;
 280         return false;
 281 }