newfuzzer.cc

   1 #include "newfuzzer.h"
   2 #include "threads-model.h"
   3 #include "action.h"
   4 #include "history.h"
   5 #include "funcnode.h"
   6 #include "funcinst.h"
   7 #include "concretepredicate.h"
   8 #include "waitobj.h"
   9
  10 #include "model.h"
  11 #include "schedule.h"
  12 #include "execution.h"
  13
  14 NewFuzzer::NewFuzzer() :
  15         thrd_last_read_act(),
  16         thrd_last_func_inst(),
  17         available_branches_tmp_storage(),
  18         thrd_selected_child_branch(),
  19         thrd_pruned_writes(),
  20         paused_thread_list(),
  21         paused_thread_table(128),
  22         failed_predicates(32),
  23         dist_info_vec()
  24 {}
  25
  26 /**
  27  * @brief Register the ModelHistory and ModelExecution engine
  28  */
  29 void NewFuzzer::register_engine(ModelChecker *_model, ModelExecution *execution)
  30 {
  31         this->history = _model->get_history();
  32         this->execution = execution;
  33 }
  34
  35 int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set)
  36 {
  37 //      return random() % rf_set->size();
  38
  39         thread_id_t tid = read->get_tid();
  40         int thread_id = id_to_int(tid);
  41
  42         if (thrd_last_read_act.size() <= (uint) thread_id) {
  43                 thrd_last_read_act.resize(thread_id + 1);
  44                 thrd_last_func_inst.resize(thread_id + 1);
  45         }
  46
  47         // A new read action is encountered, select a random child branch of current predicate
  48         if (read != thrd_last_read_act[thread_id]) {
  49                 FuncNode * func_node = history->get_curr_func_node(tid);
  50                 Predicate * curr_pred = func_node->get_predicate_tree_position(tid);
  51                 FuncInst * read_inst = func_node->get_inst(read);
  52                 inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid);
  53
  54                 if (curr_pred != NULL)  {
  55                         Predicate * selected_branch = NULL;
  56
  57                         if (check_branch_inst(curr_pred, read_inst, inst_act_map, rf_set))
  58                                 selected_branch = selectBranch(tid, curr_pred, read_inst);
  59                         else {
  60                                 // no child of curr_pred matches read_inst, check back edges
  61                                 PredSet * back_edges = curr_pred->get_backedges();
  62                                 PredSetIter * it = back_edges->iterator();
  63
  64                                 while (it->hasNext()) {
  65                                         curr_pred = it->next();
  66                                         if (check_branch_inst(curr_pred, read_inst, inst_act_map, rf_set)) {
  67                                                 selected_branch = selectBranch(tid, curr_pred, read_inst);
  68                                                 break;
  69                                         }
  70                                 }
  71
  72                                 delete it;
  73                         }
  74
  75                         prune_writes(tid, selected_branch, rf_set, inst_act_map);
  76                 }
  77
  78                 if (!failed_predicates.isEmpty())
  79                         failed_predicates.reset();
  80
  81                 thrd_last_read_act[thread_id] = read;
  82                 thrd_last_func_inst[thread_id] = read_inst;
  83         }
  84
  85         // The chosen branch fails, reselect new branches
  86         while ( rf_set->size() == 0 ) {
  87                 Predicate * selected_branch = get_selected_child_branch(tid);
  88                 FuncNode * func_node = history->get_curr_func_node(tid);
  89
  90                 // Add failed predicate to NewFuzzer and FuncNode
  91                 failed_predicates.put(selected_branch, true);
  92                 func_node->add_failed_predicate(selected_branch);
  93                 selected_branch->incr_fail_count();
  94
  95                 //model_print("the %d read action of thread %d at %p is unsuccessful\n", read->get_seq_number(), read_thread->get_id(), read->get_location());
  96
  97                 SnapVector<ModelAction *> * pruned_writes = thrd_pruned_writes[thread_id];
  98                 for (uint i = 0;i < pruned_writes->size();i++) {
  99                         rf_set->push_back( (*pruned_writes)[i] );
 100                 }
 101
 102                 // Reselect a predicate and prune writes
 103                 Predicate * curr_pred = selected_branch->get_parent();
 104                 FuncInst * read_inst = thrd_last_func_inst[thread_id];
 105                 selected_branch = selectBranch(tid, curr_pred, read_inst);
 106
 107                 inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid);
 108                 prune_writes(tid, selected_branch, rf_set, inst_act_map);
 109
 110                 ASSERT(selected_branch);
 111         }
 112
 113         int random_index = random() % rf_set->size();
 114
 115         return random_index;
 116 }
 117
 118 /* Check if children of curr_pred match read_inst.
 119  * @return False if no child matches read_inst
 120  */
 121 bool NewFuzzer::check_branch_inst(Predicate * curr_pred, FuncInst * read_inst,
 122                                                                                                                                         inst_act_map_t * inst_act_map, SnapVector<ModelAction *> * rf_set)
 123 {
 124         available_branches_tmp_storage.clear();
 125
 126         ASSERT(!rf_set->empty());
 127         if (curr_pred == NULL || read_inst == NULL)
 128                 return false;
 129
 130         ModelVector<Predicate *> * children = curr_pred->get_children();
 131         bool any_child_match = false;
 132
 133         /* Iterate over all predicate children */
 134         for (uint i = 0;i < children->size();i++) {
 135                 Predicate * branch = (*children)[i];
 136
 137                 /* The children predicates may have different FuncInsts */
 138                 if (branch->get_func_inst() == read_inst) {
 139                         any_child_match = true;
 140                         branch->incr_total_checking_count();
 141                         available_branches_tmp_storage.push_back(branch);
 142                 }
 143         }
 144
 145         return any_child_match;
 146 }
 147
 148 /* Select a random branch from the children of curr_pred
 149  * @return The selected branch
 150  */
 151 Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst)
 152 {
 153         int thread_id = id_to_int(tid);
 154         if ( thrd_selected_child_branch.size() <= (uint) thread_id)
 155                 thrd_selected_child_branch.resize(thread_id + 1);
 156
 157         if (curr_pred == NULL || read_inst == NULL) {
 158                 thrd_selected_child_branch[thread_id] = NULL;
 159                 return NULL;
 160         }
 161
 162         // predicate children have not been generated
 163         if (available_branches_tmp_storage.size() == 0) {
 164                 thrd_selected_child_branch[thread_id] = NULL;
 165                 return NULL;
 166         }
 167
 168         int index = choose_branch_index(&available_branches_tmp_storage);
 169         Predicate * random_branch = available_branches_tmp_storage[ index ];
 170         thrd_selected_child_branch[thread_id] = random_branch;
 171
 172         /* Remove the chosen branch from vec in case that this
 173          * branch fails and need to choose another one */
 174         available_branches_tmp_storage[index] = available_branches_tmp_storage.back();
 175         available_branches_tmp_storage.pop_back();
 176
 177         return random_branch;
 178 }
 179
 180 /**
 181  * @brief Select a branch from the given predicate branch
 182  */
 183 int NewFuzzer::choose_branch_index(SnapVector<Predicate *> * branches)
 184 {
 185         if (branches->size() == 1)
 186                 return 0;
 187
 188         double total_weight = 0;
 189         SnapVector<double> weights;
 190         for (uint i = 0;i < branches->size();i++) {
 191                 Predicate * branch = (*branches)[i];
 192                 double weight = branch->get_weight();
 193                 total_weight += weight;
 194                 weights.push_back(weight);
 195         }
 196
 197         double prob = (double) random() / RAND_MAX;
 198         double prob_sum = 0;
 199         int index = 0;
 200
 201         for (uint i = 0;i < weights.size();i++) {
 202                 index = i;
 203                 prob_sum += (double) (weights[i] / total_weight);
 204                 if (prob_sum > prob) {
 205                         break;
 206                 }
 207         }
 208
 209         return index;
 210 //      return random() % branches->size();
 211 }
 212
 213 Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid)
 214 {
 215         int thread_id = id_to_int(tid);
 216         if (thrd_selected_child_branch.size() <= (uint) thread_id)
 217                 return NULL;
 218
 219         return thrd_selected_child_branch[thread_id];
 220 }
 221
 222 /* Remove writes from the rf_set that do not satisfie the selected predicate,
 223  * and store them in thrd_pruned_writes
 224  *
 225  * @return true if rf_set is pruned
 226  */
 227 bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred,
 228                                                                                                                  SnapVector<ModelAction *> * rf_set, inst_act_map_t * inst_act_map)
 229 {
 230         if (pred == NULL)
 231                 return false;
 232
 233         PredExprSet * pred_expressions = pred->get_pred_expressions();
 234         if (pred_expressions->getSize() == 0)   // unset predicates
 235                 return false;
 236
 237         int thread_id = id_to_int(tid);
 238         uint old_size = thrd_pruned_writes.size();
 239         if (thrd_pruned_writes.size() <= (uint) thread_id) {
 240                 uint new_size = thread_id + 1;
 241                 thrd_pruned_writes.resize(new_size);
 242                 for (uint i = old_size;i < new_size;i++)
 243                         thrd_pruned_writes[i] = new SnapVector<ModelAction *>();
 244         }
 245         SnapVector<ModelAction *> * pruned_writes = thrd_pruned_writes[thread_id];
 246         pruned_writes->clear(); // clear the old pruned_writes set
 247
 248         bool pruned = false;
 249         uint index = 0;
 250
 251         while ( index < rf_set->size() ) {
 252                 ModelAction * write_act = (*rf_set)[index];
 253                 uint64_t write_val = write_act->get_write_value();
 254                 bool no_predicate = false;
 255                 bool satisfy_predicate = check_predicate_expressions(pred_expressions, inst_act_map, write_val, &no_predicate);
 256
 257                 if (no_predicate)
 258                         return false;
 259
 260                 if (!satisfy_predicate) {
 261                         ASSERT(rf_set != NULL);
 262                         (*rf_set)[index] = rf_set->back();
 263                         rf_set->pop_back();
 264                         pruned_writes->push_back(write_act);
 265                         pruned = true;
 266                 } else
 267                         index++;
 268         }
 269
 270         return pruned;
 271 }
 272
 273 /* @brief Put a thread to sleep because no writes in rf_set satisfies the selected predicate.
 274  *
 275  * @param thread A thread whose last action is a read
 276  */
 277 void NewFuzzer::conditional_sleep(Thread * thread)
 278 {
 279         int index = paused_thread_list.size();
 280
 281         model->getScheduler()->add_sleep(thread);
 282         paused_thread_list.push_back(thread);
 283         paused_thread_table.put(thread, index); // Update table
 284
 285         /* Add the waiting condition to ModelHistory */
 286         ModelAction * read = thread->get_pending();
 287         thread_id_t tid = thread->get_id();
 288         FuncNode * func_node = history->get_curr_func_node(tid);
 289         inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid);
 290
 291         Predicate * selected_branch = get_selected_child_branch(tid);
 292         ConcretePredicate * concrete = selected_branch->evaluate(inst_act_map, tid);
 293         concrete->set_location(read->get_location());
 294
 295         history->add_waiting_write(concrete);
 296         /* history->add_waiting_thread is already called in find_threads */
 297 }
 298
 299 bool NewFuzzer::has_paused_threads()
 300 {
 301         return paused_thread_list.size() != 0;
 302 }
 303
 304 Thread * NewFuzzer::selectThread(int * threadlist, int numthreads)
 305 {
 306         if (numthreads == 0 && has_paused_threads()) {
 307                 wake_up_paused_threads(threadlist, &numthreads);
 308                 //model_print("list size: %d, active t id: %d\n", numthreads, threadlist[0]);
 309         }
 310
 311         int random_index = random() % numthreads;
 312         int thread = threadlist[random_index];
 313         thread_id_t curr_tid = int_to_id(thread);
 314         return execution->get_thread(curr_tid);
 315 }
 316
 317 /* Force waking up one of threads paused by Fuzzer, because otherwise
 318  * the Fuzzer is not making progress
 319  */
 320 void NewFuzzer::wake_up_paused_threads(int * threadlist, int * numthreads)
 321 {
 322         int random_index = random() % paused_thread_list.size();
 323         Thread * thread = paused_thread_list[random_index];
 324         model->getScheduler()->remove_sleep(thread);
 325
 326         Thread * last_thread = paused_thread_list.back();
 327         paused_thread_list[random_index] = last_thread;
 328         paused_thread_list.pop_back();
 329         paused_thread_table.put(last_thread, random_index);     // Update table
 330         paused_thread_table.remove(thread);
 331
 332         thread_id_t tid = thread->get_id();
 333         history->remove_waiting_write(tid);
 334         history->remove_waiting_thread(tid);
 335
 336         threadlist[*numthreads] = tid;
 337         (*numthreads)++;
 338
 339 /*--
 340         Predicate * selected_branch = get_selected_child_branch(tid);
 341         update_predicate_score(selected_branch, SLEEP_FAIL_TYPE3);
 342  */
 343
 344         model_print("thread %d is woken up\n", tid);
 345 }
 346
 347 /* Wake up conditional sleeping threads if the desired write is available */
 348 void NewFuzzer::notify_paused_thread(Thread * thread)
 349 {
 350         ASSERT(paused_thread_table.contains(thread));
 351
 352         int index = paused_thread_table.get(thread);
 353         model->getScheduler()->remove_sleep(thread);
 354
 355         Thread * last_thread = paused_thread_list.back();
 356         paused_thread_list[index] = last_thread;
 357         paused_thread_list.pop_back();
 358         paused_thread_table.put(last_thread, index);    // Update table
 359         paused_thread_table.remove(thread);
 360
 361         thread_id_t tid = thread->get_id();
 362         history->remove_waiting_write(tid);
 363         history->remove_waiting_thread(tid);
 364
 365 /*--
 366         Predicate * selected_branch = get_selected_child_branch(tid);
 367         update_predicate_score(selected_branch, SLEEP_SUCCESS);
 368  */
 369
 370         model_print("** thread %d is woken up\n", tid);
 371 }
 372
 373 /* Find threads that may write values that the pending read action is waiting for.
 374  * Side effect: waiting thread related info are stored in dist_info_vec
 375  *
 376  * @return True if any thread is found
 377  */
 378 bool NewFuzzer::find_threads(ModelAction * pending_read)
 379 {
 380         ASSERT(pending_read->is_read());
 381
 382         void * location = pending_read->get_location();
 383         thread_id_t self_id = pending_read->get_tid();
 384         bool finds_waiting_for = false;
 385
 386         SnapVector<FuncNode *> * func_node_list = history->getWrFuncNodes(location);
 387         for (uint i = 0;i < func_node_list->size();i++) {
 388                 FuncNode * target_node = (*func_node_list)[i];
 389                 for (uint i = 1;i < execution->get_num_threads();i++) {
 390                         thread_id_t tid = int_to_id(i);
 391                         if (tid == self_id)
 392                                 continue;
 393
 394                         FuncNode * node = history->get_curr_func_node(tid);
 395                         /* It is possible that thread tid is not in any FuncNode */
 396                         if (node == NULL)
 397                                 continue;
 398
 399                         int distance = node->compute_distance(target_node);
 400                         if (distance != -1) {
 401                                 finds_waiting_for = true;
 402                                 //model_print("thread: %d; distance from node %d to node %d: %d\n", tid, node->get_func_id(), target_node->get_func_id(), distance);
 403
 404                                 dist_info_vec.push_back(node_dist_info(tid, target_node, distance));
 405                         }
 406                 }
 407         }
 408
 409         return finds_waiting_for;
 410 }
 411
 412 bool NewFuzzer::check_predicate_expressions(PredExprSet * pred_expressions,
 413                                                                                                                                                                                 inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate)
 414 {
 415         bool satisfy_predicate = true;
 416
 417         PredExprSetIter * pred_expr_it = pred_expressions->iterator();
 418         while (pred_expr_it->hasNext()) {
 419                 struct pred_expr * expression = pred_expr_it->next();
 420                 bool equality;
 421
 422                 switch (expression->token) {
 423                 case NOPREDICATE:
 424                         *no_predicate = true;
 425                         break;
 426                 case EQUALITY:
 427                         FuncInst * to_be_compared;
 428                         ModelAction * last_act;
 429                         uint64_t last_read;
 430
 431                         to_be_compared = expression->func_inst;
 432                         last_act = inst_act_map->get(to_be_compared);
 433                         last_read = last_act->get_reads_from_value();
 434
 435                         equality = (write_val == last_read);
 436                         if (equality != expression->value)
 437                                 satisfy_predicate = false;
 438                         break;
 439                 case NULLITY:
 440                         // TODO: implement likely to be null
 441                         equality = ((void*) (write_val & 0xffffffff) == NULL);
 442                         if (equality != expression->value)
 443                                 satisfy_predicate = false;
 444                         break;
 445                 default:
 446                         model_print("unknown predicate token\n");
 447                         break;
 448                 }
 449
 450                 if (!satisfy_predicate)
 451                         break;
 452         }
 453
 454         delete pred_expr_it;
 455         return satisfy_predicate;
 456 }
 457
 458 bool NewFuzzer::shouldWait(const ModelAction * act)
 459 {
 460         return random() & 1;
 461 }