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