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