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