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 ModelAction *ModelChecker::get_last_conflict(ModelAction *act)
  43 {
  44         void *loc = act->get_location();
  45         action_type type = act->get_type();
  46         thread_id_t id = act->get_tid();
  47
  48         switch (type) {
  49                 case THREAD_CREATE:
  50                 case THREAD_YIELD:
  51                 case THREAD_JOIN:
  52                         return NULL;
  53                 case ATOMIC_READ:
  54                 case ATOMIC_WRITE:
  55                 default:
  56                         break;
  57         }
  58         action_list_t::reverse_iterator rit;
  59         for (rit = action_trace->rbegin(); rit != action_trace->rend(); rit++) {
  60                 ModelAction *prev = *rit;
  61                 if (prev->get_location() != loc)
  62                         continue;
  63                 if (type == ATOMIC_READ && prev->get_type() != ATOMIC_WRITE)
  64                         continue;
  65                 /* Conflict from the same thread is not really a conflict */
  66                 if (id == prev->get_tid())
  67                         return NULL;
  68                 return prev;
  69         }
  70         return NULL;
  71 }
  72
  73 void ModelChecker::set_backtracking(ModelAction *act)
  74 {
  75         ModelAction *prev;
  76         TreeNode *node;
  77
  78         prev = get_last_conflict(act);
  79         if (prev == NULL)
  80                 return;
  81
  82         node = prev->get_node();
  83
  84         /* Check if this has been explored already */
  85         if (node->hasBeenExplored(act->get_tid()))
  86                 return;
  87         /* If this is a new backtracking point, mark the tree */
  88         if (node->setBacktrack(act->get_tid()) != 0)
  89                 return;
  90
  91         printf("Setting backtrack: conflict = %d, instead tid = %d\n",
  92                         prev->get_tid(), act->get_tid());
  93         prev->print();
  94         act->print();
  95
  96         Backtrack *back = new Backtrack(prev, action_trace);
  97         backtrack_list.push_back(back);
  98 }
  99
 100 void ModelChecker::check_current_action(void)
 101 {
 102         ModelAction *next = this->current_action;
 103
 104         if (!next) {
 105                 DEBUG("trying to push NULL action...\n");
 106                 return;
 107         }
 108         next->set_node(currentNode);
 109         set_backtracking(next);
 110         currentNode = currentNode->exploreChild(next->get_tid());
 111         this->action_trace->push_back(next);
 112 }
 113
 114 void ModelChecker::print_trace(void)
 115 {
 116         action_list_t::iterator it;
 117
 118         printf("\n");
 119         printf("---------------------------------------------------------------------\n");
 120         printf("Total nodes created: %d\n\n", TreeNode::getTotalNodes());
 121
 122         for (it = action_trace->begin(); it != action_trace->end(); it++) {
 123                 DBG();
 124                 (*it)->print();
 125         }
 126         printf("---------------------------------------------------------------------\n");
 127 }
 128
 129 int ModelChecker::add_thread(Thread *t)
 130 {
 131         thread_map[t->get_id()] = t;
 132         return 0;
 133 }
 134
 135 int ModelChecker::switch_to_master(ModelAction *act)
 136 {
 137         Thread *old, *next;
 138
 139         DBG();
 140         old = thread_current();
 141         set_current_action(act);
 142         old->set_state(THREAD_READY);
 143         next = system_thread;
 144         return old->swap(next);
 145 }
 146
 147 ModelAction::ModelAction(action_type_t type, memory_order order, void *loc, int value)
 148 {
 149         Thread *t = thread_current();
 150         ModelAction *act = this;
 151
 152         act->type = type;
 153         act->order = order;
 154         act->location = loc;
 155         act->tid = t->get_id();
 156         act->value = value;
 157 }
 158
 159 void ModelAction::print(void)
 160 {
 161         const char *type_str;
 162         switch (this->type) {
 163         case THREAD_CREATE:
 164                 type_str = "thread create";
 165                 break;
 166         case THREAD_YIELD:
 167                 type_str = "thread yield";
 168                 break;
 169         case THREAD_JOIN:
 170                 type_str = "thread join";
 171                 break;
 172         case ATOMIC_READ:
 173                 type_str = "atomic read";
 174                 break;
 175         case ATOMIC_WRITE:
 176                 type_str = "atomic write";
 177                 break;
 178         default:
 179                 type_str = "unknown type";
 180         }
 181
 182         printf("Thread: %d\tAction: %s\tMO: %d\tLoc: %#014zx\tValue: %d\n", tid, type_str, order, (size_t)location, value);
 183 }