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         func_inst_list_t read_inst_list;
 116         HashTable<FuncInst *, uint64_t, uintptr_t, 4> read_val_map;
 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_inst_list.push_back(func_inst);
 132                         read_val_map.put(func_inst, act->get_reads_from_value());
 133                 }
 134         }
 135
 136         update_inst_tree(&inst_list);
 137         update_predicate_tree(&read_inst_list, &read_val_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(func_inst_list_t * inst_list, HashTable<FuncInst *, uint64_t, uintptr_t, 4> * read_val_map)
 225 {
 226         if (inst_list == NULL || inst_list->size() == 0)
 227                 return;
 228 /*
 229         if (predicate_tree_initialized) {
 230                 return;
 231         }
 232         predicate_tree_initialized = true;
 233 */
 234         HashTable<void *, FuncInst *, uintptr_t, 4> loc_inst_map(128);
 235         /* map a FuncInst to the parent of its predicate */
 236         HashTable<FuncInst *, Predicate *, uintptr_t, 0> inst_pred_map(128);
 237
 238         sllnode<FuncInst *> *it = inst_list->begin();
 239         Predicate * curr_pred = predicate_tree_entry;
 240
 241         while (it != NULL) {
 242                 FuncInst * curr_inst = it->getVal();
 243                 Predicate * old_pred = curr_pred;
 244                 bool branch_found = follow_branch(&curr_pred, curr_inst, read_val_map, &loc_inst_map);
 245
 246                 // check back edges
 247                 if (!branch_found) {
 248                         Predicate * back_pred = curr_pred->get_backedge();
 249                         if (back_pred != NULL) {
 250                                 curr_pred = back_pred;
 251                                 continue;
 252                         }
 253
 254                         if (inst_pred_map.contains(curr_inst)) {
 255                                 back_pred = inst_pred_map.get(curr_inst);
 256                                 curr_pred->set_backedge(back_pred);
 257                                 curr_pred = back_pred;
 258                                 continue;
 259                         }
 260                 }
 261
 262                 if (!inst_pred_map.contains(curr_inst))
 263                         inst_pred_map.put(curr_inst, old_pred);
 264
 265                 if (!branch_found) {
 266                         if ( loc_inst_map.contains(curr_inst->get_location()) ) {
 267                                 Predicate * new_pred1 = new Predicate(curr_inst);
 268                                 new_pred1->add_predicate(EQUALITY, curr_inst->get_location(), true);
 269
 270                                 Predicate * new_pred2 = new Predicate(curr_inst);
 271                                 new_pred2->add_predicate(EQUALITY, curr_inst->get_location(), false);
 272
 273                                 curr_pred->add_child(new_pred1);
 274                                 curr_pred->add_child(new_pred2);
 275                                 //new_pred1->add_parent(curr_pred);
 276                                 //new_pred2->add_parent(curr_pred);
 277
 278                                 FuncInst * last_inst = loc_inst_map.get(curr_inst->get_location());
 279                                 uint64_t last_read = read_val_map->get(last_inst);
 280                                 if ( last_read == read_val_map->get(curr_inst) )
 281                                         curr_pred = new_pred1;
 282                                 else
 283                                         curr_pred = new_pred2;
 284                         } else {
 285                                 Predicate * new_pred = new Predicate(curr_inst);
 286                                 curr_pred->add_child(new_pred);
 287                                 //new_pred->add_parent(curr_pred);
 288
 289                                 curr_pred = new_pred;
 290                         }
 291                 }
 292
 293                 loc_inst_map.put(curr_inst->get_location(), curr_inst);
 294                 it = it->getNext();
 295         }
 296
 297         model_print("function %s\n", func_name);
 298         print_predicate_tree();
 299 }
 300
 301 /* Given curr_pred and next_inst, find the branch following curr_pred that contains next_inst and the correct predicate
 302  * @return true if branch found, false otherwise.
 303  */
 304 bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst,
 305         HashTable<FuncInst *, uint64_t, uintptr_t, 4> * read_val_map, HashTable<void *, FuncInst *, uintptr_t, 4> * loc_inst_map)
 306 {
 307         /* check if a branch with func_inst and corresponding predicate exists */
 308         bool branch_found = false;
 309         ModelVector<Predicate *> * branches = (*curr_pred)->get_children();
 310         for (uint i = 0; i < branches->size(); i++) {
 311                 Predicate * branch = (*branches)[i];
 312                 if (branch->get_func_inst() != next_inst)
 313                         continue;
 314
 315                 PredExprSet * pred_expressions = branch->get_pred_expressions();
 316
 317                 /* no predicate, follow the only branch */
 318                 if (pred_expressions->getSize() == 0) {
 319 //                      model_print("no predicate exists: "); next_inst->print();
 320                         *curr_pred = branch;
 321                         branch_found = true;
 322                         break;
 323                 }
 324
 325                 PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 326                 while (pred_expr_it->hasNext()) {
 327                         pred_expr * pred_expression = pred_expr_it->next();
 328                         uint64_t last_read, curr_read;
 329                         FuncInst * last_inst;
 330                         bool equality;
 331
 332                         switch(pred_expression->token) {
 333                                 case EQUALITY:
 334                                         last_inst = loc_inst_map->get(next_inst->get_location());
 335                                         last_read = read_val_map->get(last_inst);
 336                                         curr_read = read_val_map->get(next_inst);
 337                                         equality = (last_read == curr_read);
 338                                         if (equality == pred_expression->value) {
 339                                                 *curr_pred = branch;
 340 //                                              model_print("predicate: token: %d, location: %p, value: %d - ", pred_expression->token, pred_expression->location, pred_expression->value); next_inst->print();
 341                                                 branch_found = true;
 342                                         }
 343                                         break;
 344                                 case NULLITY:
 345                                         break;
 346                                 default:
 347                                         model_print("unkown predicate token\n");
 348                                         break;
 349                         }
 350                 }
 351
 352         }
 353
 354         return branch_found;
 355 }
 356
 357 void FuncNode::print_predicate_tree()
 358 {
 359         model_print("digraph function_%s {\n", func_name);
 360         predicate_tree_entry->print_pred_subtree();
 361         model_print("}\n");     // end of graph
 362 }
 363
 364 /* @param tid thread id
 365  * Print the values read by the last read actions for each memory location
 366  */
 367 /*
 368 void FuncNode::print_last_read(uint32_t tid)
 369 {
 370         ASSERT(thrd_read_map.size() > tid);
 371         read_map_t * read_map = thrd_read_map[tid];
 372
 373         mllnode<void *> * it;
 374         for (it = read_locations.begin();it != NULL;it=it->getNext()) {
 375                 if ( !read_map->contains(it->getVal()) )
 376                         break;
 377
 378                 uint64_t read_val = read_map->get(it->getVal());
 379                 model_print("last read of thread %d at %p: 0x%x\n", tid, it->getVal(), read_val);
 380         }
 381 }
 382 */