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::dumpGraphToFile(const char *filename) {
 126         char buffer[200];
 127   sprintf(buffer, "%s.dot",filename);
 128   FILE *file=fopen(buffer, "w");
 129   fprintf(file, "digraph %s {\n",filename);
 130   for(unsigned int i=0;i<nodeList.size();i++) {
 131                 CycleNode *cn=nodeList[i];
 132                 std::vector<CycleNode *> * edges=cn->getEdges();
 133                 const ModelAction *action=cn->getAction();
 134                 fprintf(file, "N%u [label=\"%u, T%u\"];\n",action->get_seq_number(),action->get_seq_number(), action->get_tid());
 135                 if (cn->getRMW()!=NULL) {
 136                         fprintf(file, "N%u -> N%u[style=dotted];\n", action->get_seq_number(), cn->getRMW()->getAction()->get_seq_number());
 137                 }
 138                 for(unsigned int j=0;j<edges->size();j++) {
 139                   CycleNode *dst=(*edges)[j];
 140                         const ModelAction *dstaction=dst->getAction();
 141       fprintf(file, "N%u -> N%u;\n", action->get_seq_number(), dstaction->get_seq_number());
 142           }
 143         }
 144   fprintf(file,"}\n");
 145   fclose(file);
 146 }
 147 #endif
 148
 149 /**
 150  * Checks whether one ModelAction can reach another.
 151  * @param from The ModelAction from which to begin exploration
 152  * @param to The ModelAction to reach
 153  * @return True, @a from can reach @a to; otherwise, false
 154  */
 155 bool CycleGraph::checkReachable(const ModelAction *from, const ModelAction *to) {
 156         CycleNode *fromnode = actionToNode.get(from);
 157         CycleNode *tonode = actionToNode.get(to);
 158
 159         if (!fromnode || !tonode)
 160                 return false;
 161
 162         return checkReachable(fromnode, tonode);
 163 }
 164
 165 /**
 166  * Checks whether one CycleNode can reach another.
 167  * @param from The CycleNode from which to begin exploration
 168  * @param to The CycleNode to reach
 169  * @return True, @a from can reach @a to; otherwise, false
 170  */
 171 bool CycleGraph::checkReachable(CycleNode *from, CycleNode *to) {
 172         std::vector<CycleNode *, MyAlloc<CycleNode *> > queue;
 173         HashTable<CycleNode *, CycleNode *, uintptr_t, 4, MYMALLOC, MYCALLOC, MYFREE> discovered;
 174
 175         queue.push_back(from);
 176         discovered.put(from, from);
 177         while(!queue.empty()) {
 178                 CycleNode * node=queue.back();
 179                 queue.pop_back();
 180                 if (node==to)
 181                         return true;
 182
 183                 for(unsigned int i=0;i<node->getEdges()->size();i++) {
 184                         CycleNode *next=(*node->getEdges())[i];
 185                         if (!discovered.contains(next)) {
 186                                 discovered.put(next,next);
 187                                 queue.push_back(next);
 188                         }
 189                 }
 190         }
 191         return false;
 192 }
 193
 194 void CycleGraph::startChanges() {
 195         ASSERT(rollbackvector.size()==0);
 196         ASSERT(rmwrollbackvector.size()==0);
 197         ASSERT(oldCycles==hasCycles);
 198         ASSERT(oldRMWViolation==hasRMWViolation);
 199 }
 200
 201 /** Commit changes to the cyclegraph. */
 202 void CycleGraph::commitChanges() {
 203         rollbackvector.resize(0);
 204         rmwrollbackvector.resize(0);
 205         oldCycles=hasCycles;
 206         oldRMWViolation=hasRMWViolation;
 207 }
 208
 209 /** Rollback changes to the previous commit. */
 210 void CycleGraph::rollbackChanges() {
 211         for (unsigned int i = 0; i < rollbackvector.size(); i++) {
 212                 rollbackvector[i]->popEdge();
 213         }
 214
 215         for (unsigned int i = 0; i < rmwrollbackvector.size(); i++) {
 216                 rmwrollbackvector[i]->clearRMW();
 217         }
 218
 219         hasCycles = oldCycles;
 220         hasRMWViolation = oldRMWViolation;
 221         rollbackvector.resize(0);
 222         rmwrollbackvector.resize(0);
 223 }
 224
 225 /** @returns whether a CycleGraph contains cycles. */
 226 bool CycleGraph::checkForCycles() {
 227         return hasCycles;
 228 }
 229
 230 bool CycleGraph::checkForRMWViolation() {
 231         return hasRMWViolation;
 232 }
 233
 234 /**
 235  * Constructor for a CycleNode.
 236  * @param modelaction The ModelAction for this node
 237  */
 238 CycleNode::CycleNode(const ModelAction *modelaction) :
 239         action(modelaction),
 240         hasRMW(NULL)
 241 {
 242 }
 243
 244 /** @returns a vector of the edges from a CycleNode. */
 245 std::vector<CycleNode *> * CycleNode::getEdges() {
 246         return &edges;
 247 }
 248
 249 /**
 250  * Adds an edge from this CycleNode to another CycleNode.
 251  * @param node The node to which we add a directed edge
 252  */
 253 bool CycleNode::addEdge(CycleNode *node) {
 254         for(unsigned int i=0;i<edges.size();i++)
 255                 if (edges[i]==node)
 256                         return false;
 257         edges.push_back(node);
 258         return true;
 259 }
 260
 261 /** @returns the RMW CycleNode that reads from the current CycleNode */
 262 CycleNode * CycleNode::getRMW() {
 263         return hasRMW;
 264 }
 265
 266 /**
 267  * Set a RMW action node that reads from the current CycleNode.
 268  * @param node The RMW that reads from the current node
 269  * @return True, if this node already was read by another RMW; false otherwise
 270  * @see CycleGraph::addRMWEdge
 271  */
 272 bool CycleNode::setRMW(CycleNode *node) {
 273         if (hasRMW!=NULL)
 274                 return true;
 275         hasRMW=node;
 276         return false;
 277 }