funcnode.cc

   1 #include "funcnode.h"
   2
   3 FuncNode::FuncNode(ModelHistory * history) :
   4         history(history),
   5         predicate_tree_initialized(false),
   6         exit_count(0),
   7         func_inst_map(),
   8         inst_list(),
   9         entry_insts(),
  10 //      thrd_read_map(),
  11         action_list_buffer()
  12 {
  13         predicate_tree_entry = new Predicate(NULL, true);
  14         predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true);
  15
  16         // memory will be reclaimed after each execution
  17         read_locations = new loc_set_t();
  18         val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0>();
  19 }
  20
  21 void FuncNode::set_new_exec_flag()
  22 {
  23 //      for (uint i = 0; i < thrd_read_map.size(); i++)
  24 //              thrd_read_map[i] = new read_map_t();
  25
  26         for (mllnode<FuncInst *> * it = inst_list.begin(); it != NULL; it = it->getNext()) {
  27                 FuncInst * inst = it->getVal();
  28                 inst->reset_location();
  29         }
  30
  31         read_locations = new loc_set_t();
  32         val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0>();
  33 }
  34
  35 /* Check whether FuncInst with the same type, position, and location
  36  * as act has been added to func_inst_map or not. If not, add it.
  37  *
  38  * Note: currently, actions with the same position are filtered out by process_action,
  39  * so the collision list of FuncInst is not used. May remove it later.
  40  */
  41 void FuncNode::add_inst(ModelAction *act)
  42 {
  43         ASSERT(act);
  44         const char * position = act->get_position();
  45
  46         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  47          * actions are not tagged with their source line numbers
  48          */
  49         if (position == NULL)
  50                 return;
  51
  52         if ( func_inst_map.contains(position) ) {
  53                 FuncInst * inst = func_inst_map.get(position);
  54
  55                 ASSERT(inst->get_type() == act->get_type());
  56
  57                 // locations are set to NULL when new executions start
  58                 if (inst->get_location() == NULL)
  59                         inst->set_location(act->get_location());
  60
  61                 if (inst->get_location() != act->get_location())
  62                         inst->not_single_location();
  63
  64                 return;
  65         }
  66
  67         FuncInst * func_inst = new FuncInst(act, this);
  68
  69         func_inst_map.put(position, func_inst);
  70         inst_list.push_back(func_inst);
  71 }
  72
  73 /* Get the FuncInst with the same type, position, and location
  74  * as act
  75  *
  76  * @return FuncInst with the same type, position, and location as act */
  77 FuncInst * FuncNode::get_inst(ModelAction *act)
  78 {
  79         ASSERT(act);
  80         const char * position = act->get_position();
  81
  82         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  83          * actions are not tagged with their source line numbers
  84          */
  85         if (position == NULL)
  86                 return NULL;
  87
  88         FuncInst * inst = func_inst_map.get(position);
  89         if (inst == NULL)
  90                 return NULL;
  91
  92         action_type inst_type = inst->get_type();
  93         action_type act_type = act->get_type();
  94
  95         // else if branch: an RMWRCAS action is converted to a RMW or READ action
  96         if (inst_type == act_type)
  97                 return inst;
  98         else if (inst_type == ATOMIC_RMWRCAS &&
  99                         (act_type == ATOMIC_RMW || act_type == ATOMIC_READ))
 100                 return inst;
 101
 102         return NULL;
 103 }
 104
 105
 106 void FuncNode::add_entry_inst(FuncInst * inst)
 107 {
 108         if (inst == NULL)
 109                 return;
 110
 111         mllnode<FuncInst *> * it;
 112         for (it = entry_insts.begin(); it != NULL; it = it->getNext()) {
 113                 if (inst == it->getVal())
 114                         return;
 115         }
 116
 117         entry_insts.push_back(inst);
 118 }
 119
 120 /**
 121  * @brief Convert ModelAdtion list to FuncInst list
 122  * @param act_list A list of ModelActions
 123  */
 124 void FuncNode::update_tree(action_list_t * act_list)
 125 {
 126         if (act_list == NULL || act_list->size() == 0)
 127                 return;
 128
 129         HashTable<void *, value_set_t *, uintptr_t, 4> * write_history = history->getWriteHistory();
 130
 131         /* build inst_list from act_list for later processing */
 132         func_inst_list_t inst_list;
 133         action_list_t read_act_list;
 134
 135         for (sllnode<ModelAction *> * it = act_list->begin(); it != NULL; it = it->getNext()) {
 136                 ModelAction * act = it->getVal();
 137                 FuncInst * func_inst = get_inst(act);
 138
 139                 if (func_inst == NULL)
 140                         continue;
 141
 142                 inst_list.push_back(func_inst);
 143
 144                 if (func_inst->is_read()) {
 145                         read_act_list.push_back(act);
 146
 147                         /* the first time an action reads from some location, import all the values that have
 148                          * been written to this location from ModelHistory and notify ModelHistory that this
 149                          * FuncNode may read from this location.
 150                          */
 151                         void * loc = act->get_location();
 152                         if (!read_locations->contains(loc)) {
 153                                 read_locations->add(loc);
 154                                 value_set_t * write_values = write_history->get(loc);
 155                                 add_to_val_loc_map(write_values, loc);
 156                                 history->add_to_loc_func_nodes_map(loc, this);
 157                         }
 158                 }
 159         }
 160
 161 //      model_print("function %s\n", func_name);
 162         update_inst_tree(&inst_list);
 163         update_predicate_tree(&read_act_list);
 164 //      deep_update(predicate_tree_entry);
 165
 166 //      print_predicate_tree();
 167 }
 168
 169 /**
 170  * @brief Link FuncInsts in inst_list  - add one FuncInst to another's predecessors and successors
 171  * @param inst_list A list of FuncInsts
 172  */
 173 void FuncNode::update_inst_tree(func_inst_list_t * inst_list)
 174 {
 175         if (inst_list == NULL)
 176                 return;
 177         else if (inst_list->size() == 0)
 178                 return;
 179
 180         /* start linking */
 181         sllnode<FuncInst *>* it = inst_list->begin();
 182         sllnode<FuncInst *>* prev;
 183
 184         /* add the first instruction to the list of entry insts */
 185         FuncInst * entry_inst = it->getVal();
 186         add_entry_inst(entry_inst);
 187
 188         it = it->getNext();
 189         while (it != NULL) {
 190                 prev = it->getPrev();
 191
 192                 FuncInst * prev_inst = prev->getVal();
 193                 FuncInst * curr_inst = it->getVal();
 194
 195                 prev_inst->add_succ(curr_inst);
 196                 curr_inst->add_pred(prev_inst);
 197
 198                 it = it->getNext();
 199         }
 200 }
 201
 202 /* @param tid thread id
 203  * Store the values read by atomic read actions into thrd_read_map */
 204 void FuncNode::store_read(ModelAction * act, uint32_t tid)
 205 {
 206 /*
 207         ASSERT(act);
 208
 209         void * location = act->get_location();
 210         uint64_t read_from_val = act->get_reads_from_value();
 211
 212         // resize and initialize
 213         uint32_t old_size = thrd_read_map.size();
 214         if (old_size <= tid) {
 215                 thrd_read_map.resize(tid + 1);
 216                 for (uint32_t i = old_size; i < tid + 1;i++)
 217                         thrd_read_map[i] = new read_map_t();
 218         }
 219
 220         read_map_t * read_map = thrd_read_map[tid];
 221         read_map->put(location, read_from_val);
 222 */
 223 }
 224
 225 uint64_t FuncNode::query_last_read(void * location, uint32_t tid)
 226 {
 227 /*
 228         if (thrd_read_map.size() <= tid)
 229                 return VALUE_NONE;
 230
 231         read_map_t * read_map = thrd_read_map[tid];
 232
 233         // last read value not found
 234         if ( !read_map->contains(location) )
 235                 return VALUE_NONE;
 236
 237         uint64_t read_val = read_map->get(location);
 238         return read_val;
 239 */
 240 }
 241
 242 /* @param tid thread id
 243  * Reset read map for a thread. This function shall only be called
 244  * when a thread exits a function
 245  */
 246 void FuncNode::clear_read_map(uint32_t tid)
 247 {
 248 /*
 249         if (thrd_read_map.size() <= tid)
 250                 return;
 251
 252         thrd_read_map[tid]->reset();
 253 */
 254 }
 255
 256 void FuncNode::update_predicate_tree(action_list_t * act_list)
 257 {
 258         if (act_list == NULL || act_list->size() == 0)
 259                 return;
 260 /*
 261         if (predicate_tree_initialized) {
 262                 return;
 263         }
 264         predicate_tree_initialized = true;
 265 */
 266         /* map a FuncInst to the its predicate */
 267         HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
 268
 269         // number FuncInsts to detect loops
 270         HashTable<FuncInst *, uint32_t, uintptr_t, 0> inst_id_map(128);
 271         uint32_t inst_counter = 0;
 272
 273         HashTable<void *, ModelAction *, uintptr_t, 0> loc_act_map(128);
 274         HashTable<FuncInst *, ModelAction *, uintptr_t, 0> inst_act_map(128);
 275
 276         sllnode<ModelAction *> *it = act_list->begin();
 277         Predicate * curr_pred = predicate_tree_entry;
 278         while (it != NULL) {
 279                 ModelAction * next_act = it->getVal();
 280                 FuncInst * next_inst = get_inst(next_act);
 281                 SnapVector<Predicate *> * unset_predicates = new SnapVector<Predicate *>();
 282
 283                 bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &inst_act_map, unset_predicates);
 284
 285                 // no predicate expressions, follow the only branch
 286                 if (!branch_found && unset_predicates->size() != 0) {
 287                         ASSERT(unset_predicates->size() == 1);
 288                         Predicate * one_branch = (*unset_predicates)[0];
 289                         curr_pred = one_branch;
 290                         branch_found = true;
 291                 }
 292
 293                 delete unset_predicates;
 294
 295                 // detect loops
 296                 if (!branch_found && inst_id_map.contains(next_inst)) {
 297                         FuncInst * curr_inst = curr_pred->get_func_inst();
 298                         uint32_t curr_id = inst_id_map.get(curr_inst);
 299                         uint32_t next_id = inst_id_map.get(next_inst);
 300
 301                         if (curr_id >= next_id) {
 302                                 Predicate * old_pred = inst_pred_map.get(next_inst);
 303                                 Predicate * back_pred = old_pred->get_parent();
 304
 305                                 curr_pred->add_backedge(back_pred);
 306                                 curr_pred = back_pred;
 307
 308                                 continue;
 309                         }
 310                 }
 311
 312                 if (!branch_found) {
 313                         if ( loc_act_map.contains(next_act->get_location()) ) {
 314                                 ModelAction * last_act = loc_act_map.get(next_act->get_location());
 315                                 FuncInst * last_inst = get_inst(last_act);
 316
 317                                 Predicate * new_pred1 = new Predicate(next_inst);
 318                                 new_pred1->add_predicate_expr(EQUALITY, last_inst, true);
 319
 320                                 Predicate * new_pred2 = new Predicate(next_inst);
 321                                 new_pred2->add_predicate_expr(EQUALITY, last_inst, false);
 322
 323                                 curr_pred->add_child(new_pred1);
 324                                 curr_pred->add_child(new_pred2);
 325                                 new_pred1->set_parent(curr_pred);
 326                                 new_pred2->set_parent(curr_pred);
 327
 328                                 uint64_t last_read = last_act->get_reads_from_value();
 329                                 uint64_t next_read = next_act->get_reads_from_value();
 330
 331                                 if ( last_read == next_read )
 332                                         curr_pred = new_pred1;
 333                                 else
 334                                         curr_pred = new_pred2;
 335                         } else if (!next_inst->is_single_location()) {
 336                                 Predicate * new_pred1 = new Predicate(next_inst);
 337                                 new_pred1->add_predicate_expr(NULLITY, NULL, true);
 338
 339                                 Predicate * new_pred2 = new Predicate(next_inst);
 340                                 new_pred2->add_predicate_expr(NULLITY, NULL, false);
 341
 342                                 curr_pred->add_child(new_pred1);
 343                                 curr_pred->add_child(new_pred2);
 344                                 new_pred1->set_parent(curr_pred);
 345                                 new_pred2->set_parent(curr_pred);
 346
 347                                 uint64_t next_read = next_act->get_reads_from_value();
 348                                 bool isnull = ((void*)next_read == NULL);
 349                                 if (isnull)
 350                                         curr_pred = new_pred1;
 351                                 else
 352                                         curr_pred = new_pred2;
 353                         } else {
 354                                 Predicate * new_pred = new Predicate(next_inst);
 355                                 curr_pred->add_child(new_pred);
 356                                 new_pred->set_parent(curr_pred);
 357
 358                                 if (curr_pred->is_entry_predicate())
 359                                         new_pred->add_predicate_expr(NOPREDICATE, NULL, true);
 360
 361                                 curr_pred = new_pred;
 362                         }
 363                 }
 364
 365                 inst_pred_map.put(next_inst, curr_pred);
 366                 if (!inst_id_map.contains(next_inst))
 367                         inst_id_map.put(next_inst, inst_counter++);
 368
 369                 loc_act_map.put(next_act->get_location(), next_act);
 370                 inst_act_map.put(next_inst, next_act);
 371                 it = it->getNext();
 372         }
 373 }
 374
 375 void FuncNode::deep_update(Predicate * curr_pred)
 376 {
 377         FuncInst * func_inst = curr_pred->get_func_inst();
 378         if (func_inst != NULL && !func_inst->is_single_location()) {
 379                 bool has_null_pred = false;
 380                 PredExprSet * pred_expressions = curr_pred->get_pred_expressions();
 381                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 382                 while (pred_expr_it->hasNext()) {
 383                         pred_expr * pred_expression = pred_expr_it->next();
 384                         if (pred_expression->token == NULLITY) {
 385                                 has_null_pred = true;
 386                                 break;
 387                         }
 388                 }
 389
 390                 if (!has_null_pred) {
 391 //                      func_inst->print();
 392                         Predicate * another_branch = new Predicate(func_inst);
 393                         another_branch->copy_predicate_expr(curr_pred);
 394                         another_branch->add_predicate_expr(NULLITY, NULL, 1);
 395                         curr_pred->add_predicate_expr(NULLITY, NULL, 0);
 396
 397                         Predicate * parent = curr_pred->get_parent();
 398                         parent->add_child(another_branch);
 399                 }
 400         }
 401
 402         ModelVector<Predicate *> * branches = curr_pred->get_children();
 403         for (uint i = 0; i < branches->size(); i++) {
 404                 Predicate * branch = (*branches)[i];
 405                 deep_update(branch);
 406         }
 407 }
 408
 409 /* Given curr_pred and next_inst, find the branch following curr_pred that
 410  * contains next_inst and the correct predicate.
 411  * @return true if branch found, false otherwise.
 412  */
 413 bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act,
 414         HashTable<FuncInst *, ModelAction *, uintptr_t, 0> * inst_act_map,
 415         SnapVector<Predicate *> * unset_predicates)
 416 {
 417         /* check if a branch with func_inst and corresponding predicate exists */
 418         bool branch_found = false;
 419         ModelVector<Predicate *> * branches = (*curr_pred)->get_children();
 420         for (uint i = 0; i < branches->size(); i++) {
 421                 Predicate * branch = (*branches)[i];
 422                 if (branch->get_func_inst() != next_inst)
 423                         continue;
 424
 425                 /* check against predicate expressions */
 426                 bool predicate_correct = true;
 427                 PredExprSet * pred_expressions = branch->get_pred_expressions();
 428                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 429
 430                 if (pred_expressions->getSize() == 0) {
 431                         predicate_correct = false;
 432                         unset_predicates->push_back(branch);
 433                 }
 434
 435                 while (pred_expr_it->hasNext()) {
 436                         pred_expr * pred_expression = pred_expr_it->next();
 437                         uint64_t last_read, next_read;
 438                         bool equality;
 439
 440                         switch(pred_expression->token) {
 441                                 case NOPREDICATE:
 442                                         predicate_correct = true;
 443                                         break;
 444                                 case EQUALITY:
 445                                         FuncInst * to_be_compared;
 446                                         ModelAction * last_act;
 447
 448                                         to_be_compared = pred_expression->func_inst;
 449                                         last_act = inst_act_map->get(to_be_compared);
 450
 451                                         last_read = last_act->get_reads_from_value();
 452                                         next_read = next_act->get_reads_from_value();
 453                                         equality = (last_read == next_read);
 454                                         if (equality != pred_expression->value)
 455                                                 predicate_correct = false;
 456
 457                                         break;
 458                                 case NULLITY:
 459                                         next_read = next_act->get_reads_from_value();
 460                                         equality = ((void*)next_read == NULL);
 461                                         if (equality != pred_expression->value)
 462                                                 predicate_correct = false;
 463                                         break;
 464                                 default:
 465                                         predicate_correct = false;
 466                                         model_print("unkown predicate token\n");
 467                                         break;
 468                         }
 469                 }
 470
 471                 if (predicate_correct) {
 472                         *curr_pred = branch;
 473                         branch_found = true;
 474                         break;
 475                 }
 476         }
 477
 478         return branch_found;
 479 }
 480
 481 void FuncNode::add_to_val_loc_map(uint64_t val, void * loc)
 482 {
 483         loc_set_t * locations = val_loc_map->get(val);
 484
 485         if (locations == NULL) {
 486                 locations = new loc_set_t();
 487                 val_loc_map->put(val, locations);
 488         }
 489
 490         locations->add(loc);
 491
 492 /*
 493         model_print("val %llx: ", val);
 494         loc_set_iter * it = locations->iterator();
 495         while (it->hasNext()) {
 496                 void * location = it->next();
 497                 model_print("%p ", location);
 498         }
 499         model_print("\n");
 500 */
 501 }
 502
 503 void FuncNode::add_to_val_loc_map(value_set_t * values, void * loc)
 504 {
 505         value_set_iter * it = values->iterator();
 506         while (it->hasNext()) {
 507                 uint64_t val = it->next();
 508                 add_to_val_loc_map(val, loc);
 509         }
 510 }
 511
 512
 513 void FuncNode::print_predicate_tree()
 514 {
 515         model_print("digraph function_%s {\n", func_name);
 516         predicate_tree_entry->print_pred_subtree();
 517         model_print("}\n");     // end of graph
 518 }
 519
 520 /* @param tid thread id
 521  * Print the values read by the last read actions for each memory location
 522  */
 523 /*
 524 void FuncNode::print_last_read(uint32_t tid)
 525 {
 526         ASSERT(thrd_read_map.size() > tid);
 527         read_map_t * read_map = thrd_read_map[tid];
 528
 529         mllnode<void *> * it;
 530         for (it = read_locations.begin();it != NULL;it=it->getNext()) {
 531                 if ( !read_map->contains(it->getVal()) )
 532                         break;
 533
 534                 uint64_t read_val = read_map->get(it->getVal());
 535                 model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
 536         }
 537 }
 538 */