model.cc

   1 #include <stdio.h>
   2
   3 #include "model.h"
   4 #include "schedule.h"
   5 #include "common.h"
   6
   7 ModelChecker *model;
   8
   9 ModelChecker::ModelChecker()
  10 {
  11         /* First thread created (system_thread) will have id 1 */
  12         this->used_thread_id = 0;
  13         /* Initialize default scheduler */
  14         this->scheduler = new Scheduler();
  15
  16         num_executions = 0;
  17         this->current_action = NULL;
  18         this->exploring = NULL;
  19         this->nextThread = THREAD_ID_T_NONE;
  20
  21         rootNode = new TreeNode(NULL);
  22         currentNode = rootNode;
  23         action_trace = new action_list_t();
  24 }
  25
  26 ModelChecker::~ModelChecker()
  27 {
  28         delete action_trace;
  29         delete this->scheduler;
  30         delete rootNode;
  31 }
  32
  33 int ModelChecker::get_next_id()
  34 {
  35         return ++used_thread_id;
  36 }
  37
  38 void ModelChecker::add_system_thread(Thread *t)
  39 {
  40         this->system_thread = t;
  41 }
  42
  43 Thread * ModelChecker::schedule_next_thread()
  44 {
  45         Thread *t;
  46         if (nextThread == THREAD_ID_T_NONE)
  47                 return NULL;
  48         t = thread_map[nextThread];
  49         if (t == NULL)
  50                 DEBUG("*** error: thread not in thread_map: id = %d\n", nextThread);
  51         return t;
  52 }
  53
  54 /*
  55  * get_next_replay_thread() - Choose the next thread in the replay sequence
  56  *
  57  * If we've reached the 'diverge' point, then we pick a thread from the
  58  *   backtracking set.
  59  * Otherwise, we simply return the next thread in the sequence.
  60  */
  61 thread_id_t ModelChecker::get_next_replay_thread()
  62 {
  63         ModelAction *next;
  64         thread_id_t tid;
  65
  66         next = exploring->get_state();
  67
  68         if (next == exploring->get_diverge()) {
  69                 TreeNode *node = next->get_node();
  70
  71                 /* Reached divergence point; discard our current 'exploring' */
  72                 DEBUG("*** Discard 'Backtrack' object ***\n");
  73                 tid = node->getNextBacktrack();
  74                 delete exploring;
  75                 exploring = NULL;
  76         } else {
  77                 tid = next->get_tid();
  78         }
  79         DEBUG("*** ModelChecker chose next thread = %d ***\n", tid);
  80         return tid;
  81 }
  82
  83 thread_id_t ModelChecker::advance_backtracking_state()
  84 {
  85         /* Have we completed exploring the preselected path? */
  86         if (exploring == NULL)
  87                 return THREAD_ID_T_NONE;
  88
  89         /* Else, we are trying to replay an execution */
  90         exploring->advance_state();
  91         if (exploring->get_state() == NULL)
  92                 DEBUG("*** error: reached end of backtrack trace\n");
  93
  94         return get_next_replay_thread();
  95 }
  96
  97 bool ModelChecker::next_execution()
  98 {
  99         num_executions++;
 100         if ((exploring = model->get_next_backtrack()) == NULL)
 101                 return false;
 102         model->reset_to_initial_state();
 103         nextThread = get_next_replay_thread();
 104         return true;
 105 }
 106
 107 ModelAction * ModelChecker::get_last_conflict(ModelAction *act)
 108 {
 109         void *loc = act->get_location();
 110         action_type type = act->get_type();
 111         thread_id_t id = act->get_tid();
 112
 113         switch (type) {
 114                 case THREAD_CREATE:
 115                 case THREAD_YIELD:
 116                 case THREAD_JOIN:
 117                         return NULL;
 118                 case ATOMIC_READ:
 119                 case ATOMIC_WRITE:
 120                 default:
 121                         break;
 122         }
 123         /* linear search: from most recent to oldest */
 124         action_list_t::reverse_iterator rit;
 125         for (rit = action_trace->rbegin(); rit != action_trace->rend(); rit++) {
 126                 ModelAction *prev = *rit;
 127                 if (prev->get_location() != loc)
 128                         continue;
 129                 if (type == ATOMIC_READ && prev->get_type() != ATOMIC_WRITE)
 130                         continue;
 131                 /* Conflict from the same thread is not really a conflict */
 132                 if (id == prev->get_tid())
 133                         return NULL;
 134                 return prev;
 135         }
 136         return NULL;
 137 }
 138
 139 void ModelChecker::set_backtracking(ModelAction *act)
 140 {
 141         ModelAction *prev;
 142         TreeNode *node;
 143
 144         prev = get_last_conflict(act);
 145         if (prev == NULL)
 146                 return;
 147
 148         node = prev->get_node();
 149
 150         /* Check if this has been explored already */
 151         if (node->hasBeenExplored(act->get_tid()))
 152                 return;
 153         /* If this is a new backtracking point, mark the tree */
 154         if (node->setBacktrack(act->get_tid()) != 0)
 155                 return;
 156
 157         printf("Setting backtrack: conflict = %d, instead tid = %d\n",
 158                         prev->get_tid(), act->get_tid());
 159         prev->print();
 160         act->print();
 161
 162         Backtrack *back = new Backtrack(prev, action_trace);
 163         backtrack_list.push_back(back);
 164 }
 165
 166 void ModelChecker::check_current_action(void)
 167 {
 168         ModelAction *next = this->current_action;
 169
 170         if (!next) {
 171                 DEBUG("trying to push NULL action...\n");
 172                 return;
 173         }
 174         nextThread = advance_backtracking_state();
 175         next->set_node(currentNode);
 176         set_backtracking(next);
 177         currentNode = currentNode->exploreChild(next->get_tid());
 178         this->action_trace->push_back(next);
 179 }
 180
 181 void ModelChecker::print_trace(void)
 182 {
 183         action_list_t::iterator it;
 184
 185         printf("\n");
 186         printf("---------------------------------------------------------------------\n");
 187         printf("Number of executions: %d\n", num_executions);
 188         printf("Total nodes created: %d\n\n", TreeNode::getTotalNodes());
 189
 190         scheduler->print();
 191
 192         printf("\nTrace:\n\n");
 193
 194         for (it = action_trace->begin(); it != action_trace->end(); it++) {
 195                 DBG();
 196                 (*it)->print();
 197         }
 198         printf("---------------------------------------------------------------------\n");
 199 }
 200
 201 int ModelChecker::add_thread(Thread *t)
 202 {
 203         thread_map[t->get_id()] = t;
 204         scheduler->add_thread(t);
 205         return 0;
 206 }
 207
 208 void ModelChecker::remove_thread(Thread *t)
 209 {
 210         scheduler->remove_thread(t);
 211 }
 212
 213 int ModelChecker::switch_to_master(ModelAction *act)
 214 {
 215         Thread *old, *next;
 216
 217         DBG();
 218         old = thread_current();
 219         set_current_action(act);
 220         old->set_state(THREAD_READY);
 221         next = system_thread;
 222         return old->swap(next);
 223 }
 224
 225 ModelAction::ModelAction(action_type_t type, memory_order order, void *loc, int value)
 226 {
 227         Thread *t = thread_current();
 228         ModelAction *act = this;
 229
 230         act->type = type;
 231         act->order = order;
 232         act->location = loc;
 233         act->tid = t->get_id();
 234         act->value = value;
 235 }
 236
 237 void ModelAction::print(void)
 238 {
 239         const char *type_str;
 240         switch (this->type) {
 241         case THREAD_CREATE:
 242                 type_str = "thread create";
 243                 break;
 244         case THREAD_YIELD:
 245                 type_str = "thread yield";
 246                 break;
 247         case THREAD_JOIN:
 248                 type_str = "thread join";
 249                 break;
 250         case ATOMIC_READ:
 251                 type_str = "atomic read";
 252                 break;
 253         case ATOMIC_WRITE:
 254                 type_str = "atomic write";
 255                 break;
 256         default:
 257                 type_str = "unknown type";
 258         }
 259
 260         printf("Thread: %d\tAction: %s\tMO: %d\tLoc: %#014zx\tValue: %d\n", tid, type_str, order, (size_t)location, value);
 261 }