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(NULL)
  28 {
  29         if (act)
  30                 act->set_node(this);
  31         if (act && act->is_read())
  32                 may_read_from = new action_set_t();
  33 }
  34
  35 /** @brief Node desctructor */
  36 Node::~Node()
  37 {
  38         if (action)
  39                 delete action;
  40 }
  41
  42 /** Prints debugging info for the ModelAction associated with this Node */
  43 void Node::print()
  44 {
  45         if (action)
  46                 action->print();
  47         else
  48                 printf("******** empty action ********\n");
  49 }
  50
  51 /**
  52  * Checks if the Thread associated with this thread ID has been explored from
  53  * this Node already.
  54  * @param tid is the thread ID to check
  55  * @return true if this thread choice has been explored already, false
  56  * otherwise
  57  */
  58 bool Node::has_been_explored(thread_id_t tid)
  59 {
  60         int id = id_to_int(tid);
  61         return explored_children[id];
  62 }
  63
  64 /**
  65  * Checks if the backtracking set is empty.
  66  * @return true if the backtracking set is empty
  67  */
  68 bool Node::backtrack_empty()
  69 {
  70         return numBacktracks == 0;
  71 }
  72
  73 /**
  74  * Mark the appropriate backtracking infromation for exploring a thread choice.
  75  * @param act The ModelAction to explore
  76  */
  77 void Node::explore_child(ModelAction *act)
  78 {
  79         explore(act->get_tid());
  80 }
  81
  82 /**
  83  * Records a backtracking reference for a thread choice within this Node.
  84  * Provides feedback as to whether this thread choice is already set for
  85  * backtracking.
  86  * @return false if the thread was already set to be backtracked, true
  87  * otherwise
  88  */
  89 bool Node::set_backtrack(thread_id_t id)
  90 {
  91         int i = id_to_int(id);
  92         if (backtrack[i])
  93                 return false;
  94         backtrack[i] = true;
  95         numBacktracks++;
  96         return true;
  97 }
  98
  99 thread_id_t Node::get_next_backtrack()
 100 {
 101         /* TODO: find next backtrack */
 102         unsigned int i;
 103         for (i = 0; i < backtrack.size(); i++)
 104                 if (backtrack[i] == true)
 105                         break;
 106         if (i >= backtrack.size())
 107                 return THREAD_ID_T_NONE;
 108         backtrack[i] = false;
 109         numBacktracks--;
 110         return int_to_id(i);
 111 }
 112
 113 bool Node::is_enabled(Thread *t)
 114 {
 115         return id_to_int(t->get_id()) < num_threads;
 116 }
 117
 118 /**
 119  * Add an action to the may_read_from set.
 120  * @param act is the action to add
 121  */
 122 void Node::add_read_from(ModelAction *act)
 123 {
 124         ASSERT(may_read_from);
 125         may_read_from->insert(act);
 126 }
 127
 128 void Node::explore(thread_id_t tid)
 129 {
 130         int i = id_to_int(tid);
 131         if (backtrack[i]) {
 132                 backtrack[i] = false;
 133                 numBacktracks--;
 134         }
 135         explored_children[i] = true;
 136 }
 137
 138 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
 139                                                node_list_t::iterator end)
 140 {
 141         node_list_t::iterator it;
 142
 143         for (it = start; it != end; it++)
 144                 delete (*it);
 145         list->erase(start, end);
 146 }
 147
 148 NodeStack::NodeStack()
 149         : total_nodes(0)
 150 {
 151         node_list.push_back(new Node());
 152         total_nodes++;
 153         iter = node_list.begin();
 154 }
 155
 156 NodeStack::~NodeStack()
 157 {
 158         clear_node_list(&node_list, node_list.begin(), node_list.end());
 159 }
 160
 161 void NodeStack::print()
 162 {
 163         node_list_t::iterator it;
 164         printf("............................................\n");
 165         printf("NodeStack printing node_list:\n");
 166         for (it = node_list.begin(); it != node_list.end(); it++) {
 167                 if (it == this->iter)
 168                         printf("vvv following action is the current iterator vvv\n");
 169                 (*it)->print();
 170         }
 171         printf("............................................\n");
 172 }
 173
 174 ModelAction * NodeStack::explore_action(ModelAction *act)
 175 {
 176         DBG();
 177
 178         ASSERT(!node_list.empty());
 179
 180         if (get_head()->has_been_explored(act->get_tid())) {
 181                 iter++;
 182                 return (*iter)->get_action();
 183         }
 184
 185         /* Diverging from previous execution; clear out remainder of list */
 186         node_list_t::iterator it = iter;
 187         it++;
 188         clear_node_list(&node_list, it, node_list.end());
 189
 190         /* Record action */
 191         get_head()->explore_child(act);
 192         node_list.push_back(new Node(act, get_head(), model->get_num_threads()));
 193         total_nodes++;
 194         iter++;
 195         return NULL;
 196 }
 197
 198 Node * NodeStack::get_head()
 199 {
 200         if (node_list.empty())
 201                 return NULL;
 202         return *iter;
 203 }
 204
 205 Node * NodeStack::get_next()
 206 {
 207         node_list_t::iterator it = iter;
 208         if (node_list.empty()) {
 209                 DEBUG("Empty\n");
 210                 return NULL;
 211         }
 212         it++;
 213         if (it == node_list.end()) {
 214                 DEBUG("At end\n");
 215                 return NULL;
 216         }
 217         return *it;
 218 }
 219
 220 void NodeStack::reset_execution()
 221 {
 222         iter = node_list.begin();
 223 }