nodestack.cc

   1 #define __STDC_FORMAT_MACROS
   2 #include <inttypes.h>
   3
   4 #include <string.h>
   5
   6 #include "nodestack.h"
   7 #include "action.h"
   8 #include "common.h"
   9 #include "model.h"
  10 #include "threads-model.h"
  11 #include "modeltypes.h"
  12
  13 /**
  14  * @brief Node constructor
  15  *
  16  * Constructs a single Node for use in a NodeStack. Each Node is associated
  17  * with exactly one ModelAction (exception: the first Node should be created
  18  * as an empty stub, to represent the first thread "choice") and up to one
  19  * parent.
  20  *
  21  * @param act The ModelAction to associate with this Node. May be NULL.
  22  * @param par The parent Node in the NodeStack. May be NULL if there is no
  23  * parent.
  24  * @param nthreads The number of threads which exist at this point in the
  25  * execution trace.
  26  */
  27 Node::Node(ModelAction *act, Node *par, int nthreads, Node *prevfairness) :
  28         read_from_status(READ_FROM_PAST),
  29         action(act),
  30         parent(par),
  31         num_threads(nthreads),
  32         explored_children(num_threads),
  33         backtrack(num_threads),
  34         fairness(num_threads),
  35         numBacktracks(0),
  36         enabled_array(NULL),
  37         read_from_past(),
  38         read_from_past_idx(0),
  39         future_values(),
  40         future_index(-1),
  41         relseq_break_writes(),
  42         relseq_break_index(0),
  43         misc_index(0),
  44         misc_max(0)
  45 {
  46         ASSERT(act);
  47         act->set_node(this);
  48         int currtid = id_to_int(act->get_tid());
  49         int prevtid = prevfairness ? id_to_int(prevfairness->action->get_tid()) : 0;
  50
  51         if (model->params.fairwindow != 0) {
  52                 for (int i = 0; i < num_threads; i++) {
  53                         ASSERT(i < ((int)fairness.size()));
  54                         struct fairness_info *fi = &fairness[i];
  55                         struct fairness_info *prevfi = (parent && i < parent->get_num_threads()) ? &parent->fairness[i] : NULL;
  56                         if (prevfi) {
  57                                 *fi = *prevfi;
  58                         }
  59                         if (parent && parent->is_enabled(int_to_id(i))) {
  60                                 fi->enabled_count++;
  61                         }
  62                         if (i == currtid) {
  63                                 fi->turns++;
  64                                 fi->priority = false;
  65                         }
  66                         /* Do window processing */
  67                         if (prevfairness != NULL) {
  68                                 if (prevfairness->parent->is_enabled(int_to_id(i)))
  69                                         fi->enabled_count--;
  70                                 if (i == prevtid) {
  71                                         fi->turns--;
  72                                 }
  73                                 /* Need full window to start evaluating
  74                                  * conditions
  75                                  * If we meet the enabled count and have no
  76                                  * turns, give us priority */
  77                                 if ((fi->enabled_count >= model->params.enabledcount) &&
  78                                                 (fi->turns == 0))
  79                                         fi->priority = true;
  80                         }
  81                 }
  82         }
  83 }
  84
  85 /** @brief Node desctructor */
  86 Node::~Node()
  87 {
  88         delete action;
  89         if (enabled_array)
  90                 model_free(enabled_array);
  91 }
  92
  93 /** Prints debugging info for the ModelAction associated with this Node */
  94 void Node::print() const
  95 {
  96         action->print();
  97         model_print("          backtrack: %s", backtrack_empty() ? "empty" : "non-empty ");
  98         for (int i = 0; i < (int)backtrack.size(); i++)
  99                 if (backtrack[i] == true)
 100                         model_print("[%d]", i);
 101         model_print("\n");
 102
 103         model_print("          read from past: %s", read_from_past_empty() ? "empty" : "non-empty ");
 104         for (int i = read_from_past_idx + 1; i < (int)read_from_past.size(); i++)
 105                 model_print("[%d]", read_from_past[i]->get_seq_number());
 106         model_print("\n");
 107
 108         model_print("          future values: %s", future_value_empty() ? "empty" : "non-empty ");
 109         for (int i = future_index + 1; i < (int)future_values.size(); i++)
 110                 model_print("[%#" PRIx64 "]", future_values[i].value);
 111         model_print("\n");
 112
 113         model_print("          promises: %s\n", promise_empty() ? "empty" : "non-empty");
 114         model_print("          misc: %s\n", misc_empty() ? "empty" : "non-empty");
 115         model_print("          rel seq break: %s\n", relseq_break_empty() ? "empty" : "non-empty");
 116 }
 117
 118 /**
 119  * Sets a promise to explore meeting with the given node.
 120  * @param i is the promise index.
 121  */
 122 void Node::set_promise(unsigned int i, bool is_rmw)
 123 {
 124         if (i >= promises.size())
 125                 promises.resize(i + 1, PROMISE_IGNORE);
 126         if (promises[i] == PROMISE_IGNORE) {
 127                 promises[i] = PROMISE_UNFULFILLED;
 128                 if (is_rmw)
 129                         promises[i] |= PROMISE_RMW;
 130         }
 131 }
 132
 133 /**
 134  * Looks up whether a given promise should be satisfied by this node.
 135  * @param i The promise index.
 136  * @return true if the promise should be satisfied by the given model action.
 137  */
 138 bool Node::get_promise(unsigned int i) const
 139 {
 140         return (i < promises.size()) && ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED);
 141 }
 142
 143 /**
 144  * Increments to the next combination of promises.
 145  * @return true if we have a valid combination.
 146  */
 147 bool Node::increment_promise()
 148 {
 149         DBG();
 150         unsigned int rmw_count = 0;
 151         for (unsigned int i = 0; i < promises.size(); i++) {
 152                 if (promises[i] == (PROMISE_RMW|PROMISE_FULFILLED))
 153                         rmw_count++;
 154         }
 155
 156         for (unsigned int i = 0; i < promises.size(); i++) {
 157                 if ((promises[i] & PROMISE_MASK) == PROMISE_UNFULFILLED) {
 158                         if ((rmw_count > 0) && (promises[i] & PROMISE_RMW)) {
 159                                 //sending our value to two rmws... not going to work..try next combination
 160                                 continue;
 161                         }
 162                         promises[i] = (promises[i] & PROMISE_RMW) | PROMISE_FULFILLED;
 163                         while (i > 0) {
 164                                 i--;
 165                                 if ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED)
 166                                         promises[i] = (promises[i] & PROMISE_RMW) | PROMISE_UNFULFILLED;
 167                         }
 168                         return true;
 169                 } else if (promises[i] == (PROMISE_RMW|PROMISE_FULFILLED)) {
 170                         rmw_count--;
 171                 }
 172         }
 173         return false;
 174 }
 175
 176 /**
 177  * Returns whether the promise set is empty.
 178  * @return true if we have explored all promise combinations.
 179  */
 180 bool Node::promise_empty() const
 181 {
 182         bool fulfilledrmw = false;
 183         for (int i = promises.size() - 1; i >= 0; i--) {
 184                 if (promises[i] == PROMISE_UNFULFILLED)
 185                         return false;
 186                 if (!fulfilledrmw && ((promises[i] & PROMISE_MASK) == PROMISE_UNFULFILLED))
 187                         return false;
 188                 if (promises[i] == (PROMISE_FULFILLED | PROMISE_RMW))
 189                         fulfilledrmw = true;
 190         }
 191         return true;
 192 }
 193
 194 void Node::set_misc_max(int i)
 195 {
 196         misc_max = i;
 197 }
 198
 199 int Node::get_misc() const
 200 {
 201         return misc_index;
 202 }
 203
 204 bool Node::increment_misc()
 205 {
 206         return (misc_index < misc_max) && ((++misc_index) < misc_max);
 207 }
 208
 209 bool Node::misc_empty() const
 210 {
 211         return (misc_index + 1) >= misc_max;
 212 }
 213
 214 /**
 215  * Checks if the Thread associated with this thread ID has been explored from
 216  * this Node already.
 217  * @param tid is the thread ID to check
 218  * @return true if this thread choice has been explored already, false
 219  * otherwise
 220  */
 221 bool Node::has_been_explored(thread_id_t tid) const
 222 {
 223         int id = id_to_int(tid);
 224         return explored_children[id];
 225 }
 226
 227 /**
 228  * Checks if the backtracking set is empty.
 229  * @return true if the backtracking set is empty
 230  */
 231 bool Node::backtrack_empty() const
 232 {
 233         return (numBacktracks == 0);
 234 }
 235
 236 /**
 237  * Mark the appropriate backtracking information for exploring a thread choice.
 238  * @param act The ModelAction to explore
 239  */
 240 void Node::explore_child(ModelAction *act, enabled_type_t *is_enabled)
 241 {
 242         if (!enabled_array)
 243                 enabled_array = (enabled_type_t *)model_malloc(sizeof(enabled_type_t) * num_threads);
 244         if (is_enabled != NULL)
 245                 memcpy(enabled_array, is_enabled, sizeof(enabled_type_t) * num_threads);
 246         else {
 247                 for (int i = 0; i < num_threads; i++)
 248                         enabled_array[i] = THREAD_DISABLED;
 249         }
 250
 251         explore(act->get_tid());
 252 }
 253
 254 /**
 255  * Records a backtracking reference for a thread choice within this Node.
 256  * Provides feedback as to whether this thread choice is already set for
 257  * backtracking.
 258  * @return false if the thread was already set to be backtracked, true
 259  * otherwise
 260  */
 261 bool Node::set_backtrack(thread_id_t id)
 262 {
 263         int i = id_to_int(id);
 264         ASSERT(i < ((int)backtrack.size()));
 265         if (backtrack[i])
 266                 return false;
 267         backtrack[i] = true;
 268         numBacktracks++;
 269         return true;
 270 }
 271
 272 thread_id_t Node::get_next_backtrack()
 273 {
 274         /** @todo Find next backtrack */
 275         unsigned int i;
 276         for (i = 0; i < backtrack.size(); i++)
 277                 if (backtrack[i] == true)
 278                         break;
 279         /* Backtrack set was empty? */
 280         ASSERT(i != backtrack.size());
 281
 282         backtrack[i] = false;
 283         numBacktracks--;
 284         return int_to_id(i);
 285 }
 286
 287 void Node::clear_backtracking()
 288 {
 289         for (unsigned int i = 0; i < backtrack.size(); i++)
 290                 backtrack[i] = false;
 291         for (unsigned int i = 0; i < explored_children.size(); i++)
 292                 explored_children[i] = false;
 293 }
 294
 295 bool Node::is_enabled(Thread *t) const
 296 {
 297         int thread_id = id_to_int(t->get_id());
 298         return thread_id < num_threads && (enabled_array[thread_id] != THREAD_DISABLED);
 299 }
 300
 301 enabled_type_t Node::enabled_status(thread_id_t tid) const
 302 {
 303         int thread_id = id_to_int(tid);
 304         if (thread_id < num_threads)
 305                 return enabled_array[thread_id];
 306         else
 307                 return THREAD_DISABLED;
 308 }
 309
 310 bool Node::is_enabled(thread_id_t tid) const
 311 {
 312         int thread_id = id_to_int(tid);
 313         return thread_id < num_threads && (enabled_array[thread_id] != THREAD_DISABLED);
 314 }
 315
 316 bool Node::has_priority(thread_id_t tid) const
 317 {
 318         return fairness[id_to_int(tid)].priority;
 319 }
 320
 321 /*********************************** read from ********************************/
 322
 323 /**
 324  * Get the current state of the may-read-from set iteration
 325  * @return The read-from type we should currently be checking (past or future)
 326  */
 327 read_from_type_t Node::get_read_from_status()
 328 {
 329         if (read_from_status == READ_FROM_PAST && read_from_past.empty())
 330                 increment_read_from();
 331         return read_from_status;
 332 }
 333
 334 /**
 335  * Iterate one step in the may-read-from iteration. This includes a step in
 336  * reading from the either the past or the future.
 337  * @return True if there is a new read-from to explore; false otherwise
 338  */
 339 bool Node::increment_read_from()
 340 {
 341         promises.clear();
 342         if (increment_read_from_past()) {
 343                read_from_status = READ_FROM_PAST;
 344                return true;
 345         } else if (increment_future_value()) {
 346                 read_from_status = READ_FROM_FUTURE;
 347                 return true;
 348         }
 349         read_from_status = READ_FROM_NONE;
 350         return false;
 351 }
 352
 353 /**
 354  * @return True if there are any new read-froms to explore
 355  */
 356 bool Node::read_from_empty() const
 357 {
 358         return read_from_past_empty() && future_value_empty();
 359 }
 360
 361 /**
 362  * Get the total size of the may-read-from set, including both past and future
 363  * values
 364  * @return The size of may-read-from
 365  */
 366 unsigned int Node::read_from_size() const
 367 {
 368         return read_from_past.size() + future_values.size();
 369 }
 370
 371 /******************************* end read from ********************************/
 372
 373 /****************************** read from past ********************************/
 374
 375 /** @brief Prints info about read_from_past set */
 376 void Node::print_read_from_past()
 377 {
 378         for (unsigned int i = 0; i < read_from_past.size(); i++)
 379                 read_from_past[i]->print();
 380 }
 381
 382 /**
 383  * Add an action to the read_from_past set.
 384  * @param act is the action to add
 385  */
 386 void Node::add_read_from_past(const ModelAction *act)
 387 {
 388         read_from_past.push_back(act);
 389 }
 390
 391 /**
 392  * Gets the next 'read_from_past' action from this Node. Only valid for a node
 393  * where this->action is a 'read'.
 394  * @return The first element in read_from_past
 395  */
 396 const ModelAction * Node::get_read_from_past() const
 397 {
 398         if (read_from_past_idx < read_from_past.size())
 399                 return read_from_past[read_from_past_idx];
 400         else
 401                 return NULL;
 402 }
 403
 404 const ModelAction * Node::get_read_from_past(int i) const
 405 {
 406         return read_from_past[i];
 407 }
 408
 409 int Node::get_read_from_past_size() const
 410 {
 411         return read_from_past.size();
 412 }
 413
 414 /**
 415  * Checks whether the readsfrom set for this node is empty.
 416  * @return true if the readsfrom set is empty.
 417  */
 418 bool Node::read_from_past_empty() const
 419 {
 420         return ((read_from_past_idx + 1) >= read_from_past.size());
 421 }
 422
 423 /**
 424  * Increments the index into the readsfrom set to explore the next item.
 425  * @return Returns false if we have explored all items.
 426  */
 427 bool Node::increment_read_from_past()
 428 {
 429         DBG();
 430         if (read_from_past_idx < read_from_past.size()) {
 431                 read_from_past_idx++;
 432                 return read_from_past_idx < read_from_past.size();
 433         }
 434         return false;
 435 }
 436
 437 /************************** end read from past ********************************/
 438
 439 /****************************** future values *********************************/
 440
 441 /**
 442  * Adds a value from a weakly ordered future write to backtrack to. This
 443  * operation may "fail" if the future value has already been run (within some
 444  * sloppiness window of this expiration), or if the futurevalues set has
 445  * reached its maximum.
 446  * @see model_params.maxfuturevalues
 447  *
 448  * @param value is the value to backtrack to.
 449  * @return True if the future value was successully added; false otherwise
 450  */
 451 bool Node::add_future_value(struct future_value fv)
 452 {
 453         uint64_t value = fv.value;
 454         modelclock_t expiration = fv.expiration;
 455         thread_id_t tid = fv.tid;
 456         int idx = -1; /* Highest index where value is found */
 457         for (unsigned int i = 0; i < future_values.size(); i++) {
 458                 if (future_values[i].value == value && future_values[i].tid == tid) {
 459                         if (expiration <= future_values[i].expiration)
 460                                 return false;
 461                         idx = i;
 462                 }
 463         }
 464         if (idx > future_index) {
 465                 /* Future value hasn't been explored; update expiration */
 466                 future_values[idx].expiration = expiration;
 467                 return true;
 468         } else if (idx >= 0 && expiration <= future_values[idx].expiration + model->params.expireslop) {
 469                 /* Future value has been explored and is within the "sloppy" window */
 470                 return false;
 471         }
 472
 473         /* Limit the size of the future-values set */
 474         if (model->params.maxfuturevalues > 0 &&
 475                         (int)future_values.size() >= model->params.maxfuturevalues)
 476                 return false;
 477
 478         future_values.push_back(fv);
 479         return true;
 480 }
 481
 482 /**
 483  * Gets the next 'future_value' from this Node. Only valid for a node where
 484  * this->action is a 'read'.
 485  * @return The first element in future_values
 486  */
 487 struct future_value Node::get_future_value() const
 488 {
 489         ASSERT(future_index >= 0 && future_index < ((int)future_values.size()));
 490         return future_values[future_index];
 491 }
 492
 493 /**
 494  * Checks whether the future_values set for this node is empty.
 495  * @return true if the future_values set is empty.
 496  */
 497 bool Node::future_value_empty() const
 498 {
 499         return ((future_index + 1) >= ((int)future_values.size()));
 500 }
 501
 502 /**
 503  * Increments the index into the future_values set to explore the next item.
 504  * @return Returns false if we have explored all values.
 505  */
 506 bool Node::increment_future_value()
 507 {
 508         DBG();
 509         if (future_index < ((int)future_values.size())) {
 510                 future_index++;
 511                 return (future_index < ((int)future_values.size()));
 512         }
 513         return false;
 514 }
 515
 516 /************************** end future values *********************************/
 517
 518 /**
 519  * Add a write ModelAction to the set of writes that may break the release
 520  * sequence. This is used during replay exploration of pending release
 521  * sequences. This Node must correspond to a release sequence fixup action.
 522  *
 523  * @param write The write that may break the release sequence. NULL means we
 524  * allow the release sequence to synchronize.
 525  */
 526 void Node::add_relseq_break(const ModelAction *write)
 527 {
 528         relseq_break_writes.push_back(write);
 529 }
 530
 531 /**
 532  * Get the write that may break the current pending release sequence,
 533  * according to the replay / divergence pattern.
 534  *
 535  * @return A write that may break the release sequence. If NULL, that means
 536  * the release sequence should not be broken.
 537  */
 538 const ModelAction * Node::get_relseq_break() const
 539 {
 540         if (relseq_break_index < (int)relseq_break_writes.size())
 541                 return relseq_break_writes[relseq_break_index];
 542         else
 543                 return NULL;
 544 }
 545
 546 /**
 547  * Increments the index into the relseq_break_writes set to explore the next
 548  * item.
 549  * @return Returns false if we have explored all values.
 550  */
 551 bool Node::increment_relseq_break()
 552 {
 553         DBG();
 554         promises.clear();
 555         if (relseq_break_index < ((int)relseq_break_writes.size())) {
 556                 relseq_break_index++;
 557                 return (relseq_break_index < ((int)relseq_break_writes.size()));
 558         }
 559         return false;
 560 }
 561
 562 /**
 563  * @return True if all writes that may break the release sequence have been
 564  * explored
 565  */
 566 bool Node::relseq_break_empty() const
 567 {
 568         return ((relseq_break_index + 1) >= ((int)relseq_break_writes.size()));
 569 }
 570
 571 void Node::explore(thread_id_t tid)
 572 {
 573         int i = id_to_int(tid);
 574         ASSERT(i < ((int)backtrack.size()));
 575         if (backtrack[i]) {
 576                 backtrack[i] = false;
 577                 numBacktracks--;
 578         }
 579         explored_children[i] = true;
 580 }
 581
 582 NodeStack::NodeStack() :
 583         node_list(),
 584         head_idx(-1),
 585         total_nodes(0)
 586 {
 587         total_nodes++;
 588 }
 589
 590 NodeStack::~NodeStack()
 591 {
 592         for (unsigned int i = 0; i < node_list.size(); i++)
 593                 delete node_list[i];
 594 }
 595
 596 void NodeStack::print() const
 597 {
 598         model_print("............................................\n");
 599         model_print("NodeStack printing node_list:\n");
 600         for (unsigned int it = 0; it < node_list.size(); it++) {
 601                 if ((int)it == this->head_idx)
 602                         model_print("vvv following action is the current iterator vvv\n");
 603                 node_list[it]->print();
 604         }
 605         model_print("............................................\n");
 606 }
 607
 608 /** Note: The is_enabled set contains what actions were enabled when
 609  *  act was chosen. */
 610 ModelAction * NodeStack::explore_action(ModelAction *act, enabled_type_t *is_enabled)
 611 {
 612         DBG();
 613
 614         if ((head_idx + 1) < (int)node_list.size()) {
 615                 head_idx++;
 616                 return node_list[head_idx]->get_action();
 617         }
 618
 619         /* Record action */
 620         Node *head = get_head();
 621         Node *prevfairness = NULL;
 622         if (head) {
 623                 head->explore_child(act, is_enabled);
 624                 if (model->params.fairwindow != 0 && head_idx > (int)model->params.fairwindow)
 625                         prevfairness = node_list[head_idx - model->params.fairwindow];
 626         }
 627
 628         int next_threads = model->get_num_threads();
 629         if (act->get_type() == THREAD_CREATE)
 630                 next_threads++;
 631         node_list.push_back(new Node(act, head, next_threads, prevfairness));
 632         total_nodes++;
 633         head_idx++;
 634         return NULL;
 635 }
 636
 637 /**
 638  * Empties the stack of all trailing nodes after a given position and calls the
 639  * destructor for each. This function is provided an offset which determines
 640  * how many nodes (relative to the current replay state) to save before popping
 641  * the stack.
 642  * @param numAhead gives the number of Nodes (including this Node) to skip over
 643  * before removing nodes.
 644  */
 645 void NodeStack::pop_restofstack(int numAhead)
 646 {
 647         /* Diverging from previous execution; clear out remainder of list */
 648         unsigned int it = head_idx + numAhead;
 649         for (unsigned int i = it; i < node_list.size(); i++)
 650                 delete node_list[i];
 651         node_list.resize(it);
 652         node_list.back()->clear_backtracking();
 653 }
 654
 655 Node * NodeStack::get_head() const
 656 {
 657         if (node_list.empty() || head_idx < 0)
 658                 return NULL;
 659         return node_list[head_idx];
 660 }
 661
 662 Node * NodeStack::get_next() const
 663 {
 664         if (node_list.empty()) {
 665                 DEBUG("Empty\n");
 666                 return NULL;
 667         }
 668         unsigned int it = head_idx + 1;
 669         if (it == node_list.size()) {
 670                 DEBUG("At end\n");
 671                 return NULL;
 672         }
 673         return node_list[it];
 674 }
 675
 676 void NodeStack::reset_execution()
 677 {
 678         head_idx = -1;
 679 }