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