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