funcnode.cc

   1 #include "funcnode.h"
   2 #include <fcntl.h>
   3
   4 FuncNode::FuncNode() :
   5         predicate_tree_initialized(false),
   6         predicate_tree_entry(new Predicate(NULL, true)),
   7         func_inst_map(),
   8         inst_list(),
   9         entry_insts(),
  10         thrd_read_map(),
  11         predicate_tree_backedges()
  12 {}
  13
  14 /* Check whether FuncInst with the same type, position, and location
  15  * as act has been added to func_inst_map or not. If not, add it.
  16  *
  17  * Note: currently, actions with the same position are filtered out by process_action,
  18  * so the collision list of FuncInst is not used. May remove it later.
  19  */
  20 void FuncNode::add_inst(ModelAction *act)
  21 {
  22         ASSERT(act);
  23         const char * position = act->get_position();
  24
  25         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  26          * actions are not tagged with their source line numbers
  27          */
  28         if (position == NULL)
  29                 return;
  30
  31         if ( func_inst_map.contains(position) ) {
  32                 FuncInst * inst = func_inst_map.get(position);
  33
  34                 if (inst->get_type() != act->get_type() ) {
  35                         // model_print("action with a different type occurs at line number %s\n", position);
  36                         FuncInst * func_inst = inst->search_in_collision(act);
  37
  38                         if (func_inst != NULL)
  39                                 return;
  40
  41                         func_inst = new FuncInst(act, this);
  42                         inst->get_collisions()->push_back(func_inst);
  43                         inst_list.push_back(func_inst); // delete?
  44                 }
  45
  46                 return;
  47         }
  48
  49         FuncInst * func_inst = new FuncInst(act, this);
  50
  51         func_inst_map.put(position, func_inst);
  52         inst_list.push_back(func_inst);
  53 }
  54
  55 /* Get the FuncInst with the same type, position, and location
  56  * as act
  57  *
  58  * @return FuncInst with the same type, position, and location as act */
  59 FuncInst * FuncNode::get_inst(ModelAction *act)
  60 {
  61         ASSERT(act);
  62         const char * position = act->get_position();
  63
  64         /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK
  65          * actions are not tagged with their source line numbers
  66          */
  67         if (position == NULL)
  68                 return NULL;
  69
  70         FuncInst * inst = func_inst_map.get(position);
  71         if (inst == NULL)
  72                 return NULL;
  73
  74         action_type inst_type = inst->get_type();
  75         action_type act_type = act->get_type();
  76
  77         // else if branch: an RMWRCAS action is converted to a RMW or READ action
  78         if (inst_type == act_type)
  79                 return inst;
  80         else if (inst_type == ATOMIC_RMWRCAS &&
  81                         (act_type == ATOMIC_RMW || act_type == ATOMIC_READ))
  82                 return inst;
  83
  84         return NULL;
  85 }
  86
  87
  88 void FuncNode::add_entry_inst(FuncInst * inst)
  89 {
  90         if (inst == NULL)
  91                 return;
  92
  93         mllnode<FuncInst *> * it;
  94         for (it = entry_insts.begin(); it != NULL; it = it->getNext()) {
  95                 if (inst == it->getVal())
  96                         return;
  97         }
  98
  99         entry_insts.push_back(inst);
 100 }
 101
 102 /**
 103  * @brief Convert ModelAdtion list to FuncInst list
 104  * @param act_list A list of ModelActions
 105  */
 106 void FuncNode::update_tree(action_list_t * act_list)
 107 {
 108         if (act_list == NULL)
 109                 return;
 110         else if (act_list->size() == 0)
 111                 return;
 112
 113         /* build inst_list from act_list for later processing */
 114         func_inst_list_t inst_list;
 115         action_list_t read_act_list;
 116         HashTable<ModelAction *, FuncInst *, uintptr_t, 4> act_inst_map(128);
 117
 118         for (sllnode<ModelAction *> * it = act_list->begin(); it != NULL; it = it->getNext()) {
 119                 ModelAction * act = it->getVal();
 120                 FuncInst * func_inst = get_inst(act);
 121
 122                 if (func_inst == NULL)
 123                         continue;
 124
 125                 inst_list.push_back(func_inst);
 126
 127 //              model_print("position: %s ", act->get_position());
 128 //              act->print();
 129
 130                 if (func_inst->is_read()) {
 131                         read_act_list.push_back(act);
 132                         act_inst_map.put(act, func_inst);
 133                 }
 134         }
 135
 136         update_inst_tree(&inst_list);
 137         update_predicate_tree(&read_act_list, &act_inst_map);
 138 }
 139
 140 /**
 141  * @brief Link FuncInsts in inst_list  - add one FuncInst to another's predecessors and successors
 142  * @param inst_list A list of FuncInsts
 143  */
 144 void FuncNode::update_inst_tree(func_inst_list_t * inst_list)
 145 {
 146         if (inst_list == NULL)
 147                 return;
 148         else if (inst_list->size() == 0)
 149                 return;
 150
 151         /* start linking */
 152         sllnode<FuncInst *>* it = inst_list->begin();
 153         sllnode<FuncInst *>* prev;
 154
 155         /* add the first instruction to the list of entry insts */
 156         FuncInst * entry_inst = it->getVal();
 157         add_entry_inst(entry_inst);
 158
 159         it = it->getNext();
 160         while (it != NULL) {
 161                 prev = it->getPrev();
 162
 163                 FuncInst * prev_inst = prev->getVal();
 164                 FuncInst * curr_inst = it->getVal();
 165
 166                 prev_inst->add_succ(curr_inst);
 167                 curr_inst->add_pred(prev_inst);
 168
 169                 it = it->getNext();
 170         }
 171 }
 172
 173 /* @param tid thread id
 174  * Store the values read by atomic read actions into thrd_read_map */
 175 void FuncNode::store_read(ModelAction * act, uint32_t tid)
 176 {
 177         ASSERT(act);
 178
 179         void * location = act->get_location();
 180         uint64_t read_from_val = act->get_reads_from_value();
 181
 182         /* resize and initialize */
 183         uint32_t old_size = thrd_read_map.size();
 184         if (old_size <= tid) {
 185                 thrd_read_map.resize(tid + 1);
 186                 for (uint32_t i = old_size; i < tid + 1;i++)
 187                         thrd_read_map[i] = new read_map_t();
 188         }
 189
 190         read_map_t * read_map = thrd_read_map[tid];
 191         read_map->put(location, read_from_val);
 192
 193         /* Store the memory locations where atomic reads happen */
 194         // read_locations.add(location);
 195 }
 196
 197 uint64_t FuncNode::query_last_read(void * location, uint32_t tid)
 198 {
 199         if (thrd_read_map.size() <= tid)
 200                 return 0xdeadbeef;
 201
 202         read_map_t * read_map = thrd_read_map[tid];
 203
 204         /* last read value not found */
 205         if ( !read_map->contains(location) )
 206                 return 0xdeadbeef;
 207
 208         uint64_t read_val = read_map->get(location);
 209         return read_val;
 210 }
 211
 212 /* @param tid thread id
 213  * Reset read map for a thread. This function shall only be called
 214  * when a thread exits a function
 215  */
 216 void FuncNode::clear_read_map(uint32_t tid)
 217 {
 218         if (thrd_read_map.size() <= tid)
 219                 return;
 220
 221         thrd_read_map[tid]->reset();
 222 }
 223
 224 void FuncNode::update_predicate_tree(action_list_t * act_list, HashTable<ModelAction *, FuncInst *, uintptr_t, 4> * act_inst_map)
 225 {
 226         if (act_list == NULL || act_list->size() == 0)
 227                 return;
 228
 229 /*
 230         if (predicate_tree_initialized) {
 231                 return;
 232         }
 233         predicate_tree_initialized = true;
 234 */
 235         /* map a FuncInst to the parent of its predicate */
 236         HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
 237         HashTable<FuncInst *, uint64_t, uintptr_t, 4> read_val_map(128);
 238         HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map(128);
 239
 240         sllnode<ModelAction *> *it = act_list->begin();
 241         Predicate * curr_pred = predicate_tree_entry;
 242
 243         while (it != NULL) {
 244                 ModelAction * curr_act = it->getVal();
 245                 FuncInst * curr_inst = act_inst_map->get(curr_act);
 246                 Predicate * old_pred = curr_pred;
 247                 read_val_map.put(curr_inst, curr_act->get_reads_from_value());
 248
 249                 bool branch_found = follow_branch(&curr_pred, curr_inst, &read_val_map, &loc_inst_map);
 250
 251                 // check back edges
 252                 if (!branch_found) {
 253                         Predicate * back_pred = curr_pred->get_backedge();
 254                         if (back_pred != NULL) {
 255                                 curr_pred = back_pred;
 256                                 continue;
 257                         }
 258
 259                         if (inst_pred_map.contains(curr_inst)) {
 260                                 back_pred = inst_pred_map.get(curr_inst);
 261                                 curr_pred->set_backedge(back_pred);
 262                                 curr_pred = back_pred;
 263                                 continue;
 264                         }
 265                 }
 266
 267                 if (!inst_pred_map.contains(curr_inst))
 268                         inst_pred_map.put(curr_inst, old_pred);
 269
 270                 if (!branch_found) {
 271                         if ( loc_inst_map.contains(curr_inst->get_location()) ) {
 272                                 Predicate * new_pred1 = new Predicate(curr_inst);
 273                                 new_pred1->add_predicate(EQUALITY, curr_inst->get_location(), true);
 274
 275                                 Predicate * new_pred2 = new Predicate(curr_inst);
 276                                 new_pred2->add_predicate(EQUALITY, curr_inst->get_location(), false);
 277
 278                                 curr_pred->add_child(new_pred1);
 279                                 curr_pred->add_child(new_pred2);
 280                                 //new_pred1->add_parent(curr_pred);
 281                                 //new_pred2->add_parent(curr_pred);
 282
 283                                 FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location());
 284                                 uint64_t last_read = read_val_map.get(last_inst);
 285                                 if ( last_read == read_val_map.get(curr_inst) )
 286                                         curr_pred = new_pred1;
 287                                 else
 288                                         curr_pred = new_pred2;
 289                         } else {
 290                                 Predicate * new_pred = new Predicate(curr_inst);
 291                                 curr_pred->add_child(new_pred);
 292                                 //new_pred->add_parent(curr_pred);
 293
 294                                 curr_pred = new_pred;
 295                         }
 296                 }
 297
 298                 loc_inst_map.put(curr_inst->get_location(), curr_inst);
 299                 it = it->getNext();
 300         }
 301
 302         model_print("function %s\n", func_name);
 303         print_predicate_tree();
 304 }
 305
 306 /* Given curr_pred and next_inst, find the branch following curr_pred that contains next_inst and the correct predicate
 307  * @return true if branch found, false otherwise.
 308  */
 309 bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst,
 310         HashTable<FuncInst *, uint64_t, uintptr_t, 4> * read_val_map, HashTable<void *, FuncInst *, uintptr_t, 4> * loc_inst_map)
 311 {
 312         /* check if a branch with func_inst and corresponding predicate exists */
 313         bool branch_found = false;
 314         ModelVector<Predicate *> * branches = (*curr_pred)->get_children();
 315         for (uint i = 0; i < branches->size(); i++) {
 316                 Predicate * branch = (*branches)[i];
 317                 if (branch->get_func_inst() != next_inst)
 318                         continue;
 319
 320                 PredExprSet * pred_expressions = branch->get_pred_expressions();
 321
 322                 /* no predicate, follow the only branch */
 323                 if (pred_expressions->getSize() == 0) {
 324 //                      model_print("no predicate exists: "); next_inst->print();
 325                         *curr_pred = branch;
 326                         branch_found = true;
 327                         break;
 328                 }
 329
 330                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 331                 while (pred_expr_it->hasNext()) {
 332                         pred_expr * pred_expression = pred_expr_it->next();
 333                         uint64_t last_read, next_read;
 334                         FuncInst * last_inst;
 335                         bool equality;
 336
 337                         switch(pred_expression->token) {
 338                                 case EQUALITY:
 339                                         last_inst = loc_inst_map->get(next_inst->get_location());
 340                                         last_read = read_val_map->get(last_inst);
 341                                         next_read = read_val_map->get(next_inst);
 342                                         equality = (last_read == next_read);
 343
 344                                         if (equality == pred_expression->value) {
 345                                                 *curr_pred = branch;
 346 //                                              model_print("predicate: token: %d, location: %p, value: %d - ", pred_expression->token, pred_expression->location, pred_expression->value); next_inst->print();
 347                                                 branch_found = true;
 348                                         }
 349                                         break;
 350                                 case NULLITY:
 351                                         break;
 352                                 default:
 353                                         model_print("unkown predicate token\n");
 354                                         break;
 355                         }
 356                 }
 357
 358         }
 359
 360         return branch_found;
 361 }
 362
 363 void FuncNode::print_predicate_tree()
 364 {
 365         model_print("digraph function_%s {\n", func_name);
 366         predicate_tree_entry->print_pred_subtree();
 367         model_print("}\n");     // end of graph
 368 }
 369
 370 /* @param tid thread id
 371  * Print the values read by the last read actions for each memory location
 372  */
 373 /*
 374 void FuncNode::print_last_read(uint32_t tid)
 375 {
 376         ASSERT(thrd_read_map.size() > tid);
 377         read_map_t * read_map = thrd_read_map[tid];
 378
 379         mllnode<void *> * it;
 380         for (it = read_locations.begin();it != NULL;it=it->getNext()) {
 381                 if ( !read_map->contains(it->getVal()) )
 382                         break;
 383
 384                 uint64_t read_val = read_map->get(it->getVal());
 385                 model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
 386         }
 387 }
 388 */