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 bool Node::is_enabled(thread_id_t tid)
 228 {
 229         int thread_id=id_to_int(tid);
 230         return thread_id < num_threads && enabled_array[thread_id];
 231 }
 232
 233 /**
 234  * Add an action to the may_read_from set.
 235  * @param act is the action to add
 236  */
 237 void Node::add_read_from(const ModelAction *act)
 238 {
 239         may_read_from.push_back(act);
 240 }
 241
 242 /**
 243  * Gets the next 'future_value' value from this Node. Only valid for a node
 244  * where this->action is a 'read'.
 245  * @return The first element in future_values
 246  */
 247 uint64_t Node::get_future_value() {
 248         ASSERT(future_index<future_values.size());
 249         return future_values[future_index].value;
 250 }
 251
 252 modelclock_t Node::get_future_value_expiration() {
 253         ASSERT(future_index<future_values.size());
 254         return future_values[future_index].expiration;
 255 }
 256
 257
 258 int Node::get_read_from_size() {
 259         return may_read_from.size();
 260 }
 261
 262 const ModelAction * Node::get_read_from_at(int i) {
 263         return may_read_from[i];
 264 }
 265
 266 /**
 267  * Gets the next 'may_read_from' action from this Node. Only valid for a node
 268  * where this->action is a 'read'.
 269  * @return The first element in may_read_from
 270  */
 271 const ModelAction * Node::get_read_from() {
 272         if (read_from_index < may_read_from.size())
 273                 return may_read_from[read_from_index];
 274         else
 275                 return NULL;
 276 }
 277
 278 /**
 279  * Increments the index into the readsfrom set to explore the next item.
 280  * @return Returns false if we have explored all items.
 281  */
 282 bool Node::increment_read_from() {
 283         read_from_index++;
 284         return (read_from_index < may_read_from.size());
 285 }
 286
 287 /**
 288  * Increments the index into the future_values set to explore the next item.
 289  * @return Returns false if we have explored all values.
 290  */
 291 bool Node::increment_future_value() {
 292         future_index++;
 293         return (future_index < future_values.size());
 294 }
 295
 296 void Node::explore(thread_id_t tid)
 297 {
 298         int i = id_to_int(tid);
 299         if (backtrack[i]) {
 300                 backtrack[i] = false;
 301                 numBacktracks--;
 302         }
 303         explored_children[i] = true;
 304 }
 305
 306 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
 307                                                node_list_t::iterator end)
 308 {
 309         node_list_t::iterator it;
 310
 311         for (it = start; it != end; it++)
 312                 delete (*it);
 313         list->erase(start, end);
 314 }
 315
 316 NodeStack::NodeStack()
 317         : total_nodes(0)
 318 {
 319         node_list.push_back(new Node());
 320         total_nodes++;
 321         iter = node_list.begin();
 322 }
 323
 324 NodeStack::~NodeStack()
 325 {
 326         clear_node_list(&node_list, node_list.begin(), node_list.end());
 327 }
 328
 329 void NodeStack::print()
 330 {
 331         node_list_t::iterator it;
 332         printf("............................................\n");
 333         printf("NodeStack printing node_list:\n");
 334         for (it = node_list.begin(); it != node_list.end(); it++) {
 335                 if (it == this->iter)
 336                         printf("vvv following action is the current iterator vvv\n");
 337                 (*it)->print();
 338         }
 339         printf("............................................\n");
 340 }
 341
 342 ModelAction * NodeStack::explore_action(ModelAction *act, bool * is_enabled)
 343 {
 344         DBG();
 345
 346         ASSERT(!node_list.empty());
 347         node_list_t::iterator it=iter;
 348         it++;
 349
 350         if (it != node_list.end()) {
 351                 iter++;
 352                 return (*iter)->get_action();
 353         }
 354
 355         /* Record action */
 356         get_head()->explore_child(act);
 357         node_list.push_back(new Node(act, get_head(), model->get_num_threads(), is_enabled));
 358         total_nodes++;
 359         iter++;
 360         return NULL;
 361 }
 362
 363 /**
 364  * Empties the stack of all trailing nodes after a given position and calls the
 365  * destructor for each. This function is provided an offset which determines
 366  * how many nodes (relative to the current replay state) to save before popping
 367  * the stack.
 368  * @param numAhead gives the number of Nodes (including this Node) to skip over
 369  * before removing nodes.
 370  */
 371 void NodeStack::pop_restofstack(int numAhead)
 372 {
 373         /* Diverging from previous execution; clear out remainder of list */
 374         node_list_t::iterator it = iter;
 375         while (numAhead--)
 376                 it++;
 377         clear_node_list(&node_list, it, node_list.end());
 378 }
 379
 380 Node * NodeStack::get_head()
 381 {
 382         if (node_list.empty())
 383                 return NULL;
 384         return *iter;
 385 }
 386
 387 Node * NodeStack::get_next()
 388 {
 389         node_list_t::iterator it = iter;
 390         if (node_list.empty()) {
 391                 DEBUG("Empty\n");
 392                 return NULL;
 393         }
 394         it++;
 395         if (it == node_list.end()) {
 396                 DEBUG("At end\n");
 397                 return NULL;
 398         }
 399         return *it;
 400 }
 401
 402 void NodeStack::reset_execution()
 403 {
 404         iter = node_list.begin();
 405 }