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