X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=newfuzzer.cc;h=b0874c85b5c2b2714a1bacd1d5f7194053953846;hp=eefd553ec565ea2c70553cc260ce145c2b08c861;hb=0acd7ac85bd6004e53e1283a2900ffef7debeed8;hpb=0a4d633bc8a0f700621ec57104267d66e5165f35 diff --git a/newfuzzer.cc b/newfuzzer.cc index eefd553e..b0874c85 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -1,19 +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 "schedule.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) {} /** @@ -39,21 +43,19 @@ 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); } - // No write 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); @@ -61,6 +63,9 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set execution->restore_last_seq_num(); conditional_sleep(read_thread); + + find_threads(read); + return -1; /* SnapVector * pruned_writes = thrd_pruned_writes[thread_id]; @@ -195,6 +200,8 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, index++; } + delete concrete_pred; + return pruned; } @@ -204,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() @@ -217,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; @@ -227,25 +248,71 @@ Thread * NewFuzzer::selectThread(int * threadlist, int numthreads) return model->get_thread(curr_tid); } -/* Force waking up one of threads paused by Fuzzer */ +/* 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)++; } -/* Notify one of conditional sleeping threads if the desired write is available */ -bool NewFuzzer::notify_conditional_sleep(Thread * thread) +/* 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)