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