history.cc

   1 #include <inttypes.h>
   2 #include "history.h"
   3 #include "action.h"
   4 #include "funcnode.h"
   5 #include "funcinst.h"
   6 #include "common.h"
   7 #include "concretepredicate.h"
   8
   9 #include "model.h"
  10 #include "execution.h"
  11 #include "newfuzzer.h"
  12
  13 /** @brief Constructor */
  14 ModelHistory::ModelHistory() :
  15         func_counter(1),        /* function id starts with 1 */
  16         func_map(),
  17         func_map_rev(),
  18         func_nodes(),
  19         write_history(),                // snapshot data structure
  20         loc_func_nodes_map(),           // shapshot data structure
  21         loc_wr_func_nodes_map(),        // shapshot data structure
  22         thrd_last_entered_func(),       // snapshot data structure
  23         loc_waiting_writes_map(),       // snapshot data structure
  24         thrd_waiting_write()            // snapshot data structure
  25 {}
  26
  27 void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
  28 {
  29         //model_print("thread %d entering func %d\n", tid, func_id);
  30         uint id = id_to_int(tid);
  31         SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
  32         SnapVector< SnapList<action_list_t *> *> *
  33                 thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists();
  34
  35         if ( thrd_func_list->size() <= id ) {
  36                 uint oldsize = thrd_func_list->size();
  37                 thrd_func_list->resize( id + 1 );
  38                 thrd_func_act_lists->resize( id + 1 );
  39
  40                 for (uint i = oldsize; i < id + 1; i++) {
  41                         new (&(*thrd_func_list)[i]) func_id_list_t();
  42                         // push 0 as a dummy function id to a void seg fault
  43                         (*thrd_func_list)[i].push_back(0);
  44
  45                         (*thrd_func_act_lists)[i] = new SnapList<action_list_t *>();
  46                 }
  47         }
  48
  49         while ( thrd_last_entered_func.size() <= id ) {
  50                 thrd_last_entered_func.push_back(0);    // 0 is a dummy function id
  51         }
  52
  53         SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
  54         func_act_lists->push_back( new action_list_t() );
  55
  56         uint32_t last_entered_func_id = thrd_last_entered_func[id];
  57         thrd_last_entered_func[id] = func_id;
  58         (*thrd_func_list)[id].push_back(func_id);
  59
  60         if ( func_nodes.size() <= func_id )
  61                 resize_func_nodes( func_id + 1 );
  62
  63         FuncNode * func_node = func_nodes[func_id];
  64         func_node->init_predicate_tree_position(tid);
  65         func_node->init_inst_act_map(tid);
  66
  67         /* Add edges between FuncNodes */
  68         if (last_entered_func_id != 0) {
  69                 FuncNode * last_func_node = func_nodes[last_entered_func_id];
  70                 last_func_node->add_out_edge(func_node);
  71         }
  72 }
  73
  74 /* @param func_id a non-zero value */
  75 void ModelHistory::exit_function(const uint32_t func_id, thread_id_t tid)
  76 {
  77         uint32_t id = id_to_int(tid);
  78         SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
  79         SnapVector< SnapList<action_list_t *> *> *
  80                 thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists();
  81
  82         SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
  83         uint32_t last_func_id = (*thrd_func_list)[id].back();
  84
  85         if (last_func_id == func_id) {
  86                 FuncNode * func_node = func_nodes[func_id];
  87                 func_node->set_predicate_tree_position(tid, NULL);
  88                 func_node->reset_inst_act_map(tid);
  89
  90                 action_list_t * curr_act_list = func_act_lists->back();
  91
  92                 /* defer the processing of curr_act_list until the function has exits a few times
  93                  * (currently twice) so that more information can be gathered to infer nullity predicates.
  94                  */
  95                 func_node->incr_exit_count();
  96                 if (func_node->get_exit_count() >= 2) {
  97                         SnapList<action_list_t *> * action_list_buffer = func_node->get_action_list_buffer();
  98                         while (action_list_buffer->size() > 0) {
  99                                 action_list_t * act_list = action_list_buffer->back();
 100                                 action_list_buffer->pop_back();
 101                                 func_node->update_tree(act_list);
 102                         }
 103
 104                         func_node->update_tree(curr_act_list);
 105                 } else
 106                         func_node->get_action_list_buffer()->push_front(curr_act_list);
 107
 108                 (*thrd_func_list)[id].pop_back();
 109                 func_act_lists->pop_back();
 110         } else {
 111                 model_print("trying to exit with a wrong function id\n");
 112                 model_print("--- last_func: %d, func_id: %d\n", last_func_id, func_id);
 113         }
 114         //model_print("thread %d exiting func %d\n", tid, func_id);
 115 }
 116
 117 void ModelHistory::resize_func_nodes(uint32_t new_size)
 118 {
 119         uint32_t old_size = func_nodes.size();
 120
 121         if ( old_size < new_size )
 122                 func_nodes.resize(new_size);
 123
 124         for (uint32_t id = old_size; id < new_size; id++) {
 125                 const char * func_name = func_map_rev[id];
 126                 FuncNode * func_node = new FuncNode(this);
 127                 func_node->set_func_id(id);
 128                 func_node->set_func_name(func_name);
 129                 func_nodes[id] = func_node;
 130         }
 131 }
 132
 133 void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
 134 {
 135         /* return if thread i has not entered any function or has exited
 136            from all functions */
 137         SnapVector<func_id_list_t> * thrd_func_list = model->get_execution()->get_thrd_func_list();
 138         SnapVector< SnapList<action_list_t *> *> *
 139                 thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists();
 140
 141         uint32_t id = id_to_int(tid);
 142         if ( thrd_func_list->size() <= id )
 143                 return;
 144
 145         /* get the function id that thread i is currently in */
 146         uint32_t func_id = (*thrd_func_list)[id].back();
 147         SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
 148
 149         if (act->is_write()) {
 150                 void * location = act->get_location();
 151                 uint64_t value = act->get_write_value();
 152                 update_write_history(location, value);
 153
 154                 /* Update FuncNodes that may read from this location */
 155                 SnapList<FuncNode *> * func_nodes = loc_func_nodes_map.get(location);
 156                 if (func_nodes != NULL) {
 157                         sllnode<FuncNode *> * it = func_nodes->begin();
 158                         for (; it != NULL; it = it->getNext()) {
 159                                 FuncNode * func_node = it->getVal();
 160                                 func_node->add_to_val_loc_map(value, location);
 161                         }
 162                 }
 163
 164                 check_waiting_write(act);
 165         }
 166
 167         /* the following does not care about actions without a position */
 168         if (func_id == 0 || act->get_position() == NULL)
 169                 return;
 170
 171         bool second_part_of_rmw = act->is_rmwc() || act->is_rmw();
 172
 173         action_list_t * curr_act_list = func_act_lists->back();
 174         ASSERT(curr_act_list != NULL);
 175
 176         modelclock_t curr_seq_number = act->get_seq_number();
 177         /* Skip actions that are second part of a read modify write or actions with the same sequence number */
 178         if (curr_act_list->size() != 0) {
 179                 ModelAction * last_act = curr_act_list->back();
 180                 if (second_part_of_rmw || last_act->get_seq_number() == curr_seq_number)
 181                         return;
 182         }
 183
 184         /* skip actions that are paused by fuzzer (sequence number is 0) */
 185         if (curr_seq_number == 0)
 186                 return;
 187
 188         FuncNode * func_node = func_nodes[func_id];
 189
 190         /* add to curr_inst_list */
 191         curr_act_list->push_back(act);
 192         func_node->add_inst(act);
 193
 194         if (act->is_read()) {
 195                 func_node->update_inst_act_map(tid, act);
 196
 197                 // Update predicate tree position
 198                 Fuzzer * fuzzer = model->get_execution()->getFuzzer();
 199                 Predicate * selected_branch = fuzzer->get_selected_child_branch(tid);
 200                 func_node->set_predicate_tree_position(tid, selected_branch);
 201         }
 202 }
 203
 204 /* Return the FuncNode given its func_id  */
 205 FuncNode * ModelHistory::get_func_node(uint32_t func_id)
 206 {
 207         if (func_nodes.size() <= func_id)       // this node has not been added to func_nodes
 208                 return NULL;
 209
 210         return func_nodes[func_id];
 211 }
 212
 213 /* Return the current FuncNode when given a thread id */
 214 FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid)
 215 {
 216         int thread_id = id_to_int(tid);
 217         SnapVector<func_id_list_t> * thrd_func_list =  model->get_execution()->get_thrd_func_list();
 218         uint32_t func_id = (*thrd_func_list)[thread_id].back();
 219         FuncNode * func_node = func_nodes[func_id];
 220
 221         return func_node;
 222 }
 223
 224 void ModelHistory::update_write_history(void * location, uint64_t write_val)
 225 {
 226         value_set_t * write_set = write_history.get(location);
 227
 228         if (write_set == NULL) {
 229                 write_set = new value_set_t();
 230                 write_history.put(location, write_set);
 231         }
 232
 233         write_set->add(write_val);
 234 }
 235
 236 void ModelHistory::update_loc_func_nodes_map(void * location, FuncNode * node)
 237 {
 238         SnapList<FuncNode *> * func_node_list = loc_func_nodes_map.get(location);
 239         if (func_node_list == NULL) {
 240                 func_node_list = new SnapList<FuncNode *>();
 241                 loc_func_nodes_map.put(location, func_node_list);
 242         }
 243
 244         func_node_list->push_back(node);
 245 }
 246
 247 void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node)
 248 {
 249         SnapList<FuncNode *> * func_node_list = loc_wr_func_nodes_map.get(location);
 250         if (func_node_list == NULL) {
 251                 func_node_list = new SnapList<FuncNode *>();
 252                 loc_func_nodes_map.put(location, func_node_list);
 253         }
 254
 255         func_node_list->push_back(node);
 256 }
 257
 258 /* When a thread is paused by Fuzzer, keep track of the condition it is waiting for */
 259 void ModelHistory::add_waiting_write(ConcretePredicate * concrete)
 260 {
 261         void * location = concrete->get_location();
 262         SnapVector<ConcretePredicate *> * waiting_conditions = loc_waiting_writes_map.get(location);
 263         if (waiting_conditions == NULL) {
 264                 waiting_conditions = new SnapVector<ConcretePredicate *>();
 265                 loc_waiting_writes_map.put(location, waiting_conditions);
 266         }
 267
 268         /* waiting_conditions should not have duplications */
 269         waiting_conditions->push_back(concrete);
 270
 271         int thread_id = id_to_int(concrete->get_tid());
 272         int oldsize = thrd_waiting_write.size();
 273
 274         if (oldsize <= thread_id) {
 275                 for (int i = oldsize; i < thread_id + 1; i++)
 276                         thrd_waiting_write.resize(thread_id + 1);
 277         }
 278
 279         thrd_waiting_write[thread_id] = concrete;
 280 }
 281
 282 void ModelHistory::remove_waiting_write(thread_id_t tid)
 283 {
 284         ConcretePredicate * concrete = thrd_waiting_write[ id_to_int(tid) ];
 285         void * location = concrete->get_location();
 286         SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map.get(location);
 287
 288         for (uint i = 0; i < concrete_preds->size(); i++) {
 289                 ConcretePredicate * current = (*concrete_preds)[i];
 290                 if (concrete == current) {
 291                         (*concrete_preds)[i] = concrete_preds->back();
 292                         concrete_preds->pop_back();
 293                         break;
 294                 }
 295         }
 296
 297         int thread_id = id_to_int( concrete->get_tid() );
 298         thrd_waiting_write[thread_id] = NULL;
 299         delete concrete;
 300 }
 301
 302 /* Check if any other thread is waiting for this write action. If so, wake them up */
 303 void ModelHistory::check_waiting_write(ModelAction * write_act)
 304 {
 305         void * location = write_act->get_location();
 306         uint64_t value = write_act->get_write_value();
 307         SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map.get(location);
 308         SnapVector<ConcretePredicate *> to_remove = SnapVector<ConcretePredicate *>();
 309         if (concrete_preds == NULL)
 310                 return;
 311
 312         uint index = 0;
 313         while (index < concrete_preds->size()) {
 314                 ConcretePredicate * concrete_pred = (*concrete_preds)[index];
 315                 SnapVector<struct concrete_pred_expr> * concrete_exprs = concrete_pred->getExpressions();
 316                 bool satisfy_predicate = true;
 317                 /* Check if the written value satisfies every predicate expression */
 318                 for (uint i = 0; i < concrete_exprs->size(); i++) {
 319                         struct concrete_pred_expr concrete = (*concrete_exprs)[i];
 320                         bool equality;
 321                         switch (concrete.token) {
 322                                 case EQUALITY:
 323                                         equality = (value == concrete.value);
 324                                         break;
 325                                 case NULLITY:
 326                                         equality = ((void*)value == NULL);
 327                                         break;
 328                                 default:
 329                                         model_print("unknown predicate token");
 330                                         break;
 331                         }
 332
 333                         if (equality != concrete.equality) {
 334                                 satisfy_predicate = false;
 335                                 break;
 336                         }
 337                 }
 338
 339                 if (satisfy_predicate) {
 340                         to_remove.push_back(concrete_pred);
 341                 }
 342
 343                 index++;
 344         }
 345
 346         for (uint i = 0; i < to_remove.size(); i++) {
 347                 ConcretePredicate * concrete_pred = to_remove[i];
 348
 349                 /* Wake up threads */
 350                 thread_id_t tid = concrete_pred->get_tid();
 351                 Thread * thread = model->get_thread(tid);
 352
 353                 model_print("** thread %d is woken up\n", thread->get_id());
 354                 model->get_execution()->getFuzzer()->notify_paused_thread(thread);
 355         }
 356 }
 357
 358 /* Reallocate some snapshotted memories when new executions start */
 359 void ModelHistory::set_new_exec_flag()
 360 {
 361         for (uint i = 1; i < func_nodes.size(); i++) {
 362                 FuncNode * func_node = func_nodes[i];
 363                 func_node->set_new_exec_flag();
 364         }
 365 }
 366
 367 void ModelHistory::dump_func_node_graph()
 368 {
 369         model_print("digraph func_node_graph {\n");
 370         for (uint i = 1; i < func_nodes.size(); i++) {
 371                 FuncNode * node = func_nodes[i];
 372                 ModelList<FuncNode *> * out_edges = node->get_out_edges();
 373
 374                 model_print("\"%p\" [label=\"%s\"]\n", node, node->get_func_name());
 375                 mllnode<FuncNode *> * it;
 376                 for (it = out_edges->begin(); it != NULL; it = it->getNext()) {
 377                         FuncNode * other = it->getVal();
 378                         model_print("\"%p\" -> \"%p\"\n", node, other);
 379                 }
 380         }
 381         model_print("}\n");
 382 }
 383
 384 void ModelHistory::print_func_node()
 385 {
 386         /* function id starts with 1 */
 387         for (uint32_t i = 1; i < func_nodes.size(); i++) {
 388                 FuncNode * func_node = func_nodes[i];
 389
 390                 func_inst_list_mt * entry_insts = func_node->get_entry_insts();
 391                 model_print("function %s has entry actions\n", func_node->get_func_name());
 392
 393                 mllnode<FuncInst*>* it;
 394                 for (it = entry_insts->begin();it != NULL;it=it->getNext()) {
 395                         FuncInst *inst = it->getVal();
 396                         model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position());
 397                 }
 398         }
 399 }