funcnode.cc

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