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         read_from_index(0),
  29         future_values(),
  30         future_index(-1)
  31 {
  32         if (act)
  33                 act->set_node(this);
  34 }
  35
  36 /** @brief Node desctructor */
  37 Node::~Node()
  38 {
  39         if (action)
  40                 delete action;
  41 }
  42
  43 /** Prints debugging info for the ModelAction associated with this Node */
  44 void Node::print()
  45 {
  46         if (action)
  47                 action->print();
  48         else
  49                 printf("******** empty action ********\n");
  50 }
  51
  52 /** @brief Prints info about may_read_from set */
  53 void Node::print_may_read_from()
  54 {
  55         readfrom_set_t::iterator it;
  56         for (it = may_read_from.begin(); it != may_read_from.end(); it++)
  57                 (*it)->print();
  58 }
  59
  60 void Node::set_promise(uint32_t i) {
  61         if (i>=promises.size())
  62                 promises.resize(i+1,0);
  63         promises[i]=1;
  64 }
  65
  66 bool Node::get_promise(uint32_t i) {
  67         return (promises[i]==2);
  68 }
  69
  70 bool Node::increment_promises() {
  71         for (unsigned int i=0;i<promises.size();i++) {
  72                 if (promises[i]==1) {
  73                         promises[i]=2;
  74                         while (i>0) {
  75                                 i--;
  76                                 if (promises[i]==2)
  77                                         promises[i]=1;
  78                         }
  79                         return true;
  80                 }
  81         }
  82         return false;
  83 }
  84
  85 bool Node::promises_empty() {
  86         for (unsigned int i=0;i<promises.size();i++)
  87                 if (promises[i]==1)
  88                         return false;
  89         return true;
  90 }
  91
  92 /**
  93  * Adds a value from a weakly ordered future write to backtrack to.
  94  * @param value is the value to backtrack to.
  95  */
  96
  97 bool Node::add_future_value(uint64_t value) {
  98         for(unsigned int i=0;i<future_values.size();i++)
  99                 if (future_values[i]==value)
 100                         return false;
 101
 102         future_values.push_back(value);
 103         return true;
 104 }
 105
 106 /**
 107  * Checks whether the future_values set for this node is empty.
 108  * @return true if the future_values set is empty.
 109  */
 110
 111 bool Node::futurevalues_empty() {
 112         return ((future_index+1)>=future_values.size());
 113 }
 114
 115
 116 /**
 117  * Checks if the Thread associated with this thread ID has been explored from
 118  * this Node already.
 119  * @param tid is the thread ID to check
 120  * @return true if this thread choice has been explored already, false
 121  * otherwise
 122  */
 123 bool Node::has_been_explored(thread_id_t tid)
 124 {
 125         int id = id_to_int(tid);
 126         return explored_children[id];
 127 }
 128
 129 /**
 130  * Checks if the backtracking set is empty.
 131  * @return true if the backtracking set is empty
 132  */
 133 bool Node::backtrack_empty()
 134 {
 135         return (numBacktracks == 0);
 136 }
 137
 138
 139 /**
 140  * Checks whether the readsfrom set for this node is empty.
 141  * @return true if the readsfrom set is empty.
 142  */
 143 bool Node::readsfrom_empty() {
 144         return ((read_from_index+1)>=may_read_from.size());
 145 }
 146
 147
 148
 149 /**
 150  * Mark the appropriate backtracking information for exploring a thread choice.
 151  * @param act The ModelAction to explore
 152  */
 153 void Node::explore_child(ModelAction *act)
 154 {
 155         explore(act->get_tid());
 156 }
 157
 158 /**
 159  * Records a backtracking reference for a thread choice within this Node.
 160  * Provides feedback as to whether this thread choice is already set for
 161  * backtracking.
 162  * @return false if the thread was already set to be backtracked, true
 163  * otherwise
 164  */
 165 bool Node::set_backtrack(thread_id_t id)
 166 {
 167         int i = id_to_int(id);
 168         if (backtrack[i])
 169                 return false;
 170         backtrack[i] = true;
 171         numBacktracks++;
 172         return true;
 173 }
 174
 175 thread_id_t Node::get_next_backtrack()
 176 {
 177         /** @todo Find next backtrack */
 178         unsigned int i;
 179         for (i = 0; i < backtrack.size(); i++)
 180                 if (backtrack[i] == true)
 181                         break;
 182         /* Backtrack set was empty? */
 183         ASSERT(i != backtrack.size());
 184
 185         backtrack[i] = false;
 186         numBacktracks--;
 187         return int_to_id(i);
 188 }
 189
 190 bool Node::is_enabled(Thread *t)
 191 {
 192         return id_to_int(t->get_id()) < num_threads;
 193 }
 194
 195 /**
 196  * Add an action to the may_read_from set.
 197  * @param act is the action to add
 198  */
 199 void Node::add_read_from(const ModelAction *act)
 200 {
 201         may_read_from.push_back(act);
 202 }
 203
 204 /**
 205  * Gets the next 'future_value' value from this Node. Only valid for a node
 206  * where this->action is a 'read'.
 207  * @return The first element in future_values
 208  */
 209
 210 uint64_t Node::get_future_value() {
 211         ASSERT(future_index<future_values.size());
 212         return future_values[future_index];
 213 }
 214
 215 /**
 216  * Gets the next 'may_read_from' action from this Node. Only valid for a node
 217  * where this->action is a 'read'.
 218  * @todo Perform reads_from backtracking/replay properly, so that this function
 219  * may remove elements from may_read_from
 220  * @return The first element in may_read_from
 221  */
 222 const ModelAction * Node::get_read_from() {
 223         if (read_from_index<may_read_from.size())
 224                 return may_read_from[read_from_index];
 225         else
 226                 return NULL;
 227 }
 228
 229 /**
 230  * Increments the index into the readsfrom set to explore the next item.
 231  * @return Returns false if we have explored all items.
 232  */
 233 bool Node::increment_read_from() {
 234         read_from_index++;
 235         return (read_from_index<may_read_from.size());
 236 }
 237
 238 /**
 239  * Increments the index into the future_values set to explore the next item.
 240  * @return Returns false if we have explored all values.
 241  */
 242
 243 bool Node::increment_future_values() {
 244         future_index++;
 245         return (future_index<future_values.size());
 246 }
 247
 248 void Node::explore(thread_id_t tid)
 249 {
 250         int i = id_to_int(tid);
 251         if (backtrack[i]) {
 252                 backtrack[i] = false;
 253                 numBacktracks--;
 254         }
 255         explored_children[i] = true;
 256 }
 257
 258 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
 259                                                node_list_t::iterator end)
 260 {
 261         node_list_t::iterator it;
 262
 263         for (it = start; it != end; it++)
 264                 delete (*it);
 265         list->erase(start, end);
 266 }
 267
 268 NodeStack::NodeStack()
 269         : total_nodes(0)
 270 {
 271         node_list.push_back(new Node());
 272         total_nodes++;
 273         iter = node_list.begin();
 274 }
 275
 276 NodeStack::~NodeStack()
 277 {
 278         clear_node_list(&node_list, node_list.begin(), node_list.end());
 279 }
 280
 281 void NodeStack::print()
 282 {
 283         node_list_t::iterator it;
 284         printf("............................................\n");
 285         printf("NodeStack printing node_list:\n");
 286         for (it = node_list.begin(); it != node_list.end(); it++) {
 287                 if (it == this->iter)
 288                         printf("vvv following action is the current iterator vvv\n");
 289                 (*it)->print();
 290         }
 291         printf("............................................\n");
 292 }
 293
 294 ModelAction * NodeStack::explore_action(ModelAction *act)
 295 {
 296         DBG();
 297
 298         ASSERT(!node_list.empty());
 299         node_list_t::iterator it=iter;
 300         it++;
 301
 302         if (it != node_list.end()) {
 303                 iter++;
 304                 return (*iter)->get_action();
 305         }
 306
 307         /* Record action */
 308         get_head()->explore_child(act);
 309         node_list.push_back(new Node(act, get_head(), model->get_num_threads()));
 310         total_nodes++;
 311         iter++;
 312         return NULL;
 313 }
 314
 315 /**
 316  * Empties the stack of all trailing nodes after a given position and calls the
 317  * destructor for each. This function is provided an offset which determines
 318  * how many nodes (relative to the current replay state) to save before popping
 319  * the stack.
 320  * @param numAhead gives the number of Nodes (including this Node) to skip over
 321  * before removing nodes.
 322  */
 323 void NodeStack::pop_restofstack(int numAhead)
 324 {
 325         /* Diverging from previous execution; clear out remainder of list */
 326         node_list_t::iterator it = iter;
 327         while (numAhead--)
 328                 it++;
 329         clear_node_list(&node_list, it, node_list.end());
 330 }
 331
 332 Node * NodeStack::get_head()
 333 {
 334         if (node_list.empty())
 335                 return NULL;
 336         return *iter;
 337 }
 338
 339 Node * NodeStack::get_next()
 340 {
 341         node_list_t::iterator it = iter;
 342         if (node_list.empty()) {
 343                 DEBUG("Empty\n");
 344                 return NULL;
 345         }
 346         it++;
 347         if (it == node_list.end()) {
 348                 DEBUG("At end\n");
 349                 return NULL;
 350         }
 351         return *it;
 352 }
 353
 354 void NodeStack::reset_execution()
 355 {
 356         iter = node_list.begin();
 357 }