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