nodestack.cc

   1 #include "nodestack.h"
   2 #include "action.h"
   3 #include "common.h"
   4 #include "model.h"
   5
   6 /**
   7  * @brief Node constructor
   8  *
   9  * Constructs a single Node for use in a NodeStack. Each Node is associated
  10  * with exactly one ModelAction (exception: the first Node should be created
  11  * as an empty stub, to represent the first thread "choice") and up to one
  12  * parent.
  13  *
  14  * @param act The ModelAction to associate with this Node. May be NULL.
  15  * @param par The parent Node in the NodeStack. May be NULL if there is no
  16  * parent.
  17  * @param nthreads The number of threads which exist at this point in the
  18  * execution trace.
  19  */
  20 Node::Node(ModelAction *act, Node *par, int nthreads)
  21         : action(act),
  22         parent(par),
  23         num_threads(nthreads),
  24         explored_children(num_threads),
  25         backtrack(num_threads),
  26         numBacktracks(0),
  27         may_read_from()
  28 {
  29         if (act)
  30                 act->set_node(this);
  31 }
  32
  33 /** @brief Node desctructor */
  34 Node::~Node()
  35 {
  36         if (action)
  37                 delete action;
  38 }
  39
  40 /** Prints debugging info for the ModelAction associated with this Node */
  41 void Node::print()
  42 {
  43         if (action)
  44                 action->print();
  45         else
  46                 printf("******** empty action ********\n");
  47 }
  48
  49 /**
  50  * Checks if the Thread associated with this thread ID has been explored from
  51  * this Node already.
  52  * @param tid is the thread ID to check
  53  * @return true if this thread choice has been explored already, false
  54  * otherwise
  55  */
  56 bool Node::has_been_explored(thread_id_t tid)
  57 {
  58         int id = id_to_int(tid);
  59         return explored_children[id];
  60 }
  61
  62 /**
  63  * Checks if the backtracking set is empty.
  64  * @return true if the backtracking set is empty
  65  */
  66 bool Node::backtrack_empty()
  67 {
  68         return numBacktracks == 0;
  69 }
  70
  71 /**
  72  * Mark the appropriate backtracking infromation for exploring a thread choice.
  73  * @param act The ModelAction to explore
  74  */
  75 void Node::explore_child(ModelAction *act)
  76 {
  77         explore(act->get_tid());
  78 }
  79
  80 /**
  81  * Records a backtracking reference for a thread choice within this Node.
  82  * Provides feedback as to whether this thread choice is already set for
  83  * backtracking.
  84  * @return false if the thread was already set to be backtracked, true
  85  * otherwise
  86  */
  87 bool Node::set_backtrack(thread_id_t id)
  88 {
  89         int i = id_to_int(id);
  90         if (backtrack[i])
  91                 return false;
  92         backtrack[i] = true;
  93         numBacktracks++;
  94         return true;
  95 }
  96
  97 thread_id_t Node::get_next_backtrack()
  98 {
  99         /* TODO: find next backtrack */
 100         unsigned int i;
 101         for (i = 0; i < backtrack.size(); i++)
 102                 if (backtrack[i] == true)
 103                         break;
 104         if (i >= backtrack.size())
 105                 return THREAD_ID_T_NONE;
 106         backtrack[i] = false;
 107         numBacktracks--;
 108         return int_to_id(i);
 109 }
 110
 111 bool Node::is_enabled(Thread *t)
 112 {
 113         return id_to_int(t->get_id()) < num_threads;
 114 }
 115
 116 /**
 117  * Add an action to the may_read_from set.
 118  * @param act is the action to add
 119  */
 120 void Node::add_read_from(ModelAction *act)
 121 {
 122         may_read_from.insert(act);
 123 }
 124
 125 void Node::explore(thread_id_t tid)
 126 {
 127         int i = id_to_int(tid);
 128         if (backtrack[i]) {
 129                 backtrack[i] = false;
 130                 numBacktracks--;
 131         }
 132         explored_children[i] = true;
 133 }
 134
 135 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
 136                                                node_list_t::iterator end)
 137 {
 138         node_list_t::iterator it;
 139
 140         for (it = start; it != end; it++)
 141                 delete (*it);
 142         list->erase(start, end);
 143 }
 144
 145 NodeStack::NodeStack()
 146         : total_nodes(0)
 147 {
 148         node_list.push_back(new Node());
 149         total_nodes++;
 150         iter = node_list.begin();
 151 }
 152
 153 NodeStack::~NodeStack()
 154 {
 155         clear_node_list(&node_list, node_list.begin(), node_list.end());
 156 }
 157
 158 void NodeStack::print()
 159 {
 160         node_list_t::iterator it;
 161         printf("............................................\n");
 162         printf("NodeStack printing node_list:\n");
 163         for (it = node_list.begin(); it != node_list.end(); it++) {
 164                 if (it == this->iter)
 165                         printf("vvv following action is the current iterator vvv\n");
 166                 (*it)->print();
 167         }
 168         printf("............................................\n");
 169 }
 170
 171 ModelAction * NodeStack::explore_action(ModelAction *act)
 172 {
 173         DBG();
 174
 175         ASSERT(!node_list.empty());
 176
 177         if (get_head()->has_been_explored(act->get_tid())) {
 178                 iter++;
 179                 return (*iter)->get_action();
 180         }
 181
 182         /* Diverging from previous execution; clear out remainder of list */
 183         node_list_t::iterator it = iter;
 184         it++;
 185         clear_node_list(&node_list, it, node_list.end());
 186
 187         /* Record action */
 188         get_head()->explore_child(act);
 189         node_list.push_back(new Node(act, get_head(), model->get_num_threads()));
 190         total_nodes++;
 191         iter++;
 192         return NULL;
 193 }
 194
 195 Node * NodeStack::get_head()
 196 {
 197         if (node_list.empty())
 198                 return NULL;
 199         return *iter;
 200 }
 201
 202 Node * NodeStack::get_next()
 203 {
 204         node_list_t::iterator it = iter;
 205         if (node_list.empty()) {
 206                 DEBUG("Empty\n");
 207                 return NULL;
 208         }
 209         it++;
 210         if (it == node_list.end()) {
 211                 DEBUG("At end\n");
 212                 return NULL;
 213         }
 214         return *it;
 215 }
 216
 217 void NodeStack::reset_execution()
 218 {
 219         iter = node_list.begin();
 220 }