X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=newfuzzer.cc;h=b0874c85b5c2b2714a1bacd1d5f7194053953846;hp=98d56f2192fa7872364453fba10227cd04fb038e;hb=0acd7ac85bd6004e53e1283a2900ffef7debeed8;hpb=d55f961768e13c12ab9d7b6a4f7f1490748f18c5 diff --git a/newfuzzer.cc b/newfuzzer.cc index 98d56f21..b0874c85 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -1,17 +1,23 @@ #include "newfuzzer.h" #include "threads-model.h" -#include "model.h" #include "action.h" -#include "execution.h" +#include "history.h" #include "funcnode.h" +#include "funcinst.h" +#include "predicate.h" +#include "concretepredicate.h" + +#include "model.h" #include "schedule.h" +#include "execution.h" NewFuzzer::NewFuzzer() : thrd_last_read_act(), thrd_curr_pred(), thrd_selected_child_branch(), thrd_pruned_writes(), - paused_thread_set() + paused_thread_set(), + paused_thread_table(128) {} /** @@ -25,6 +31,8 @@ void NewFuzzer::register_engine(ModelHistory * history, ModelExecution *executio int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set) { +// return random() % rf_set->size(); + thread_id_t tid = read->get_tid(); int thread_id = id_to_int(tid); @@ -35,29 +43,29 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set if (read != thrd_last_read_act[thread_id]) { thrd_last_read_act[thread_id] = read; - SnapVector * thrd_func_list = execution->get_thrd_func_list(); - uint32_t func_id = (*thrd_func_list)[thread_id].back(); - FuncNode * func_node = history->get_func_node(func_id); - inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid); + FuncNode * func_node = history->get_curr_func_node(tid); Predicate * curr_pred = func_node->get_predicate_tree_position(tid); FuncInst * read_inst = func_node->get_inst(read); - Predicate * selected_branch = selectBranch(tid, curr_pred, read_inst); + + inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid); prune_writes(tid, selected_branch, rf_set, inst_act_map); } - // TODO: make this thread sleep if no write satisfies the chosen predicate - // if no read satisfies the selected predicate + // No write satisfies the selected predicate, so pause this thread. if ( rf_set->size() == 0 ) { Thread * read_thread = execution->get_thread(tid); - model_print("the %d read action of thread %d is unsuccessful\n", read->get_seq_number(), read_thread->get_id()); + 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()); // reset thread pending action and revert sequence numbers read_thread->set_pending(read); read->reset_seq_number(); execution->restore_last_seq_num(); - + conditional_sleep(read_thread); + + find_threads(read); + return -1; /* SnapVector * pruned_writes = thrd_pruned_writes[thread_id]; @@ -147,39 +155,32 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, bool pruned = false; uint index = 0; + + ConcretePredicate * concrete_pred = pred->evaluate(inst_act_map, tid); + SnapVector * concrete_exprs = concrete_pred->getExpressions(); + while ( index < rf_set->size() ) { ModelAction * write_act = (*rf_set)[index]; + uint64_t write_val = write_act->get_write_value(); bool satisfy_predicate = true; - PredExprSetIter * pred_expr_it = pred_expressions->iterator(); - while (pred_expr_it->hasNext()) { - struct pred_expr * expression = pred_expr_it->next(); - uint64_t write_val = write_act->get_write_value(); + for (uint i = 0; i < concrete_exprs->size(); i++) { + struct concrete_pred_expr concrete = (*concrete_exprs)[i]; bool equality; - // No predicate, return false - if (expression->token == NOPREDICATE) - return pruned; - - switch(expression->token) { + switch (concrete.token) { + case NOPREDICATE: + return false; case EQUALITY: - FuncInst * to_be_compared; - ModelAction * last_act; - uint64_t last_read; - - to_be_compared = expression->func_inst; - last_act = inst_act_map->get(to_be_compared); - last_read = last_act->get_reads_from_value(); - - equality = (write_val == last_read); - if (equality != expression->value) + equality = (write_val == concrete.value); + if (equality != concrete.equality) satisfy_predicate = false; break; case NULLITY: equality = ((void*)write_val == NULL); - if (equality != expression->value) - satisfy_predicate = false; - break; + if (equality != concrete.equality) + satisfy_predicate = false; + break; default: model_print("unknown predicate token\n"); break; @@ -199,6 +200,8 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, index++; } + delete concrete_pred; + return pruned; } @@ -208,8 +211,23 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, */ void NewFuzzer::conditional_sleep(Thread * thread) { + int index = paused_thread_set.size(); + model->getScheduler()->add_sleep(thread); paused_thread_set.push_back(thread); + paused_thread_table.put(thread, index); // Update table + + /* Add the waiting condition to ModelHistory */ + ModelAction * read = thread->get_pending(); + thread_id_t tid = thread->get_id(); + FuncNode * func_node = history->get_curr_func_node(tid); + inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid); + + Predicate * selected_branch = get_selected_child_branch(tid); + ConcretePredicate * concrete = selected_branch->evaluate(inst_act_map, tid); + concrete->set_location(read->get_location()); + + history->add_waiting_write(concrete); } bool NewFuzzer::has_paused_threads() @@ -221,8 +239,7 @@ Thread * NewFuzzer::selectThread(int * threadlist, int numthreads) { if (numthreads == 0 && has_paused_threads()) { wake_up_paused_threads(threadlist, &numthreads); - model_print("list size: %d\n", numthreads); - model_print("active t id: %d\n", threadlist[0]); + model_print("list size: %d, active t id: %d\n", numthreads, threadlist[0]); } int random_index = random() % numthreads; @@ -231,20 +248,73 @@ Thread * NewFuzzer::selectThread(int * threadlist, int numthreads) return model->get_thread(curr_tid); } +/* Force waking up one of threads paused by Fuzzer, because otherwise + * the Fuzzer is not making progress + */ void NewFuzzer::wake_up_paused_threads(int * threadlist, int * numthreads) { int random_index = random() % paused_thread_set.size(); Thread * thread = paused_thread_set[random_index]; model->getScheduler()->remove_sleep(thread); - paused_thread_set[random_index] = paused_thread_set.back(); + Thread * last_thread = paused_thread_set.back(); + paused_thread_set[random_index] = last_thread; paused_thread_set.pop_back(); + paused_thread_table.put(last_thread, random_index); // Update table + paused_thread_table.remove(thread); + + thread_id_t tid = thread->get_id(); + history->remove_waiting_write(tid); - model_print("thread %d is woken up\n", thread->get_id()); - threadlist[*numthreads] = thread->get_id(); + model_print("thread %d is woken up\n", tid); + threadlist[*numthreads] = tid; (*numthreads)++; } +/* Wake up conditional sleeping threads if the desired write is available */ +void NewFuzzer::notify_paused_thread(Thread * thread) +{ + ASSERT(paused_thread_table.contains(thread)); + + int index = paused_thread_table.get(thread); + model->getScheduler()->remove_sleep(thread); + + Thread * last_thread = paused_thread_set.back(); + paused_thread_set[index] = last_thread; + paused_thread_set.pop_back(); + paused_thread_table.put(last_thread, index); // Update table + paused_thread_table.remove(thread); + + thread_id_t tid = thread->get_id(); + history->remove_waiting_write(tid); +} + +/* Find threads that may write values that the pending read action is waiting for */ +void NewFuzzer::find_threads(ModelAction * pending_read) +{ + void * location = pending_read->get_location(); + thread_id_t self_id = pending_read->get_tid(); + + SnapVector * func_node_list = history->getWrFuncNodes(location); + for (uint i = 0; i < func_node_list->size(); i++) { + FuncNode * target_node = (*func_node_list)[i]; + model_print("node %s may write to loc %p\n", target_node->get_func_name(), location); + + for (uint i = 1; i < execution->get_num_threads(); i++) { + thread_id_t tid = int_to_id(i); + if (tid == self_id) + continue; + + FuncNode * node = history->get_curr_func_node(tid); + if (node == NULL) + continue; + + int distance = node->compute_distance(target_node); + model_print("thread: %d; distance from node %d to node %d: %d\n", tid, node->get_func_id(), target_node->get_func_id(), distance); + } + } +} + bool NewFuzzer::shouldWait(const ModelAction * act) { return random() & 1;