cyclegraph.h

   1 /** @file cyclegraph.h @brief Data structure to track ordering
   2  *  constraints on modification order.  The idea is to see whether a
   3  *  total order exists that satisfies the ordering constriants.*/
   4
   5 #ifndef CYCLEGRAPH_H
   6 #define CYCLEGRAPH_H
   7
   8 #include "hashtable.h"
   9 #include <vector>
  10 #include <inttypes.h>
  11 #include "config.h"
  12 #include "mymemory.h"
  13
  14 class CycleNode;
  15 class ModelAction;
  16
  17 /** @brief A graph of Model Actions for tracking cycles. */
  18 class CycleGraph {
  19  public:
  20         CycleGraph();
  21         ~CycleGraph();
  22         void addEdge(const ModelAction *from, const ModelAction *to);
  23         bool checkForCycles();
  24         bool checkForRMWViolation();
  25         void addRMWEdge(const ModelAction *from, const ModelAction *rmw);
  26
  27         bool checkReachable(const ModelAction *from, const ModelAction *to);
  28         void startChanges();
  29         void commitChanges();
  30         void rollbackChanges();
  31 #if SUPPORT_MOD_ORDER_DUMP
  32         void dumpNodes(FILE *file);
  33         void dumpGraphToFile(const char * filename);
  34 #endif
  35
  36         SNAPSHOTALLOC
  37  private:
  38         CycleNode * getNode(const ModelAction *);
  39
  40         /** @brief A table for mapping ModelActions to CycleNodes */
  41         HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
  42 #if SUPPORT_MOD_ORDER_DUMP
  43         std::vector<CycleNode *> nodeList;
  44 #endif
  45
  46         bool checkReachable(CycleNode *from, CycleNode *to);
  47
  48         /** @brief A flag: true if this graph contains cycles */
  49         bool hasCycles;
  50         bool oldCycles;
  51
  52         bool hasRMWViolation;
  53         bool oldRMWViolation;
  54
  55         std::vector<CycleNode *> rollbackvector;
  56         std::vector<CycleNode *> rmwrollbackvector;
  57 };
  58
  59 /** @brief A node within a CycleGraph; corresponds to one ModelAction */
  60 class CycleNode {
  61  public:
  62         CycleNode(const ModelAction *action);
  63         bool addEdge(CycleNode * node);
  64         std::vector<CycleNode *> * getEdges();
  65         bool setRMW(CycleNode *);
  66         CycleNode* getRMW();
  67         const ModelAction * getAction() {return action;};
  68
  69         void popEdge() {
  70                 edges.pop_back();
  71         };
  72         void clearRMW() {
  73                 hasRMW=NULL;
  74         }
  75
  76         SNAPSHOTALLOC
  77  private:
  78         /** @brief The ModelAction that this node represents */
  79         const ModelAction *action;
  80
  81         /** @brief The edges leading out from this node */
  82         std::vector<CycleNode *> edges;
  83
  84         /** Pointer to a RMW node that reads from this node, or NULL, if none
  85          * exists */
  86         CycleNode * hasRMW;
  87 };
  88
  89 #endif