From: weiyu Date: Tue, 1 Oct 2019 02:28:24 +0000 (-0700) Subject: Notify threads paused by the Fuzzer when the desired write is available X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=commitdiff_plain;h=51ee3f71895aafae7e7292174862b3ad42c801a6 Notify threads paused by the Fuzzer when the desired write is available --- diff --git a/concretepredicate.h b/concretepredicate.h index 6319a2ee..f0eaeea9 100644 --- a/concretepredicate.h +++ b/concretepredicate.h @@ -13,7 +13,9 @@ public: void add_expression(token_t token, uint64_t value, bool equality); SnapVector * getExpressions() { return &expressions; } + void set_location(void * loc) { location = loc; } void * get_location() { return location; } + thread_id_t get_tid() { return tid; } SNAPSHOTALLOC private: diff --git a/fuzzer.h b/fuzzer.h index 64875f2d..0d5734d0 100644 --- a/fuzzer.h +++ b/fuzzer.h @@ -11,7 +11,9 @@ public: virtual int selectWrite(ModelAction *read, SnapVector* rf_set); virtual Predicate * get_selected_child_branch(thread_id_t tid) = 0; virtual bool has_paused_threads() { return false; } + virtual void notify_paused_thread(Thread * thread) = 0; virtual Thread * selectThread(int * threadlist, int numthreads); + Thread * selectNotify(action_list_t * waiters); bool shouldSleep(const ModelAction *sleep); bool shouldWake(const ModelAction *sleep); diff --git a/history.cc b/history.cc index 4b03e7ff..24350181 100644 --- a/history.cc +++ b/history.cc @@ -4,6 +4,7 @@ #include "funcnode.h" #include "funcinst.h" #include "common.h" +#include "concretepredicate.h" #include "model.h" #include "execution.h" @@ -17,7 +18,10 @@ ModelHistory::ModelHistory() : func_nodes(), write_history(), // snapshot data structure loc_func_nodes_map(), // shapshot data structure - thrd_last_entered_func() // snapshot data structure + loc_wr_func_nodes_map(), // shapshot data structure + thrd_last_entered_func(), // snapshot data structure + loc_waiting_writes_map(), // snapshot data structure + thrd_waiting_write() // snapshot data structure {} void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) @@ -156,6 +160,8 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) func_node->add_to_val_loc_map(value, location); } } + + check_waiting_write(act); } /* the following does not care about actions without a position */ @@ -195,7 +201,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) } } -/* return the FuncNode given its func_id */ +/* Return the FuncNode given its func_id */ FuncNode * ModelHistory::get_func_node(uint32_t func_id) { if (func_nodes.size() <= func_id) // this node has not been added to func_nodes @@ -204,6 +210,17 @@ FuncNode * ModelHistory::get_func_node(uint32_t func_id) return func_nodes[func_id]; } +/* Return the current FuncNode when given a thread id */ +FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid) +{ + int thread_id = id_to_int(tid); + SnapVector * thrd_func_list = model->get_execution()->get_thrd_func_list(); + uint32_t func_id = (*thrd_func_list)[thread_id].back(); + FuncNode * func_node = func_nodes[func_id]; + + return func_node; +} + void ModelHistory::update_write_history(void * location, uint64_t write_val) { value_set_t * write_set = write_history.get(location); @@ -238,6 +255,106 @@ void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node func_node_list->push_back(node); } +/* When a thread is paused by Fuzzer, keep track of the condition it is waiting for */ +void ModelHistory::add_waiting_write(ConcretePredicate * concrete) +{ + void * location = concrete->get_location(); + SnapVector * waiting_conditions = loc_waiting_writes_map.get(location); + if (waiting_conditions == NULL) { + waiting_conditions = new SnapVector(); + loc_waiting_writes_map.put(location, waiting_conditions); + } + + /* waiting_conditions should not have duplications */ + waiting_conditions->push_back(concrete); + + int thread_id = id_to_int(concrete->get_tid()); + int oldsize = thrd_waiting_write.size(); + + if (oldsize <= thread_id) { + for (int i = oldsize; i < thread_id + 1; i++) + thrd_waiting_write.resize(thread_id + 1); + } + + thrd_waiting_write[thread_id] = concrete; +} + +void ModelHistory::remove_waiting_write(thread_id_t tid) +{ + ConcretePredicate * concrete = thrd_waiting_write[ id_to_int(tid) ]; + void * location = concrete->get_location(); + SnapVector * concrete_preds = loc_waiting_writes_map.get(location); + + for (uint i = 0; i < concrete_preds->size(); i++) { + ConcretePredicate * current = (*concrete_preds)[i]; + if (concrete == current) { + (*concrete_preds)[i] = concrete_preds->back(); + concrete_preds->pop_back(); + break; + } + } + + int thread_id = id_to_int( concrete->get_tid() ); + thrd_waiting_write[thread_id] = NULL; + delete concrete; +} + +/* Check if any other thread is waiting for this write action. If so, wake them up */ +void ModelHistory::check_waiting_write(ModelAction * write_act) +{ + void * location = write_act->get_location(); + uint64_t value = write_act->get_write_value(); + SnapVector * concrete_preds = loc_waiting_writes_map.get(location); + SnapVector to_remove = SnapVector(); + if (concrete_preds == NULL) + return; + + uint index = 0; + while (index < concrete_preds->size()) { + ConcretePredicate * concrete_pred = (*concrete_preds)[index]; + SnapVector * concrete_exprs = concrete_pred->getExpressions(); + bool satisfy_predicate = true; + /* Check if the written value satisfies every predicate expression */ + for (uint i = 0; i < concrete_exprs->size(); i++) { + struct concrete_pred_expr concrete = (*concrete_exprs)[i]; + bool equality; + switch (concrete.token) { + case EQUALITY: + equality = (value == concrete.value); + break; + case NULLITY: + equality = ((void*)value == NULL); + break; + default: + model_print("unknown predicate token"); + break; + } + + if (equality != concrete.equality) { + satisfy_predicate = false; + break; + } + } + + if (satisfy_predicate) { + to_remove.push_back(concrete_pred); + } + + index++; + } + + for (uint i = 0; i < to_remove.size(); i++) { + ConcretePredicate * concrete_pred = to_remove[i]; + + /* Wake up threads */ + thread_id_t tid = concrete_pred->get_tid(); + Thread * thread = model->get_thread(tid); + + model_print("** thread %d is woken up\n", thread->get_id()); + model->get_execution()->getFuzzer()->notify_paused_thread(thread); + } +} + /* Reallocate some snapshotted memories when new executions start */ void ModelHistory::set_new_exec_flag() { diff --git a/history.h b/history.h index 51f26304..5a3657c4 100644 --- a/history.h +++ b/history.h @@ -26,12 +26,18 @@ public: ModelVector * getFuncNodes() { return &func_nodes; } FuncNode * get_func_node(uint32_t func_id); + FuncNode * get_curr_func_node(thread_id_t tid); void update_write_history(void * location, uint64_t write_val); HashTable * getWriteHistory() { return &write_history; } void update_loc_func_nodes_map(void * location, FuncNode * node); void update_loc_wr_func_nodes_map(void * location, FuncNode * node); + void add_waiting_write(ConcretePredicate * concrete); + void remove_waiting_write(thread_id_t tid); + void check_waiting_write(ModelAction * write_act); + SnapVector * getThrdWaitingWrite() { return &thrd_waiting_write; } + void set_new_exec_flag(); void dump_func_node_graph(); void print_func_node(); @@ -59,6 +65,9 @@ private: /* Keeps track of the last function entered by each thread */ SnapVector thrd_last_entered_func; + + HashTable *, uintptr_t, 4> loc_waiting_writes_map; + SnapVector thrd_waiting_write; }; #endif /* __HISTORY_H__ */ diff --git a/newfuzzer.cc b/newfuzzer.cc index d5814217..00219b63 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -16,7 +16,8 @@ NewFuzzer::NewFuzzer() : thrd_curr_pred(), thrd_selected_child_branch(), thrd_pruned_writes(), - paused_thread_set() + paused_thread_set(), + paused_thread_table(128) {} /** @@ -42,9 +43,7 @@ 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); + FuncNode * func_node = history->get_curr_func_node(tid); inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid); Predicate * curr_pred = func_node->get_predicate_tree_position(tid); FuncInst * read_inst = func_node->get_inst(read); @@ -53,7 +52,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set 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()); @@ -198,6 +197,8 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, index++; } + delete concrete_pred; + return pruned; } @@ -207,8 +208,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 + + /* */ + 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() @@ -230,25 +246,45 @@ 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); - model_print("thread %d is woken up\n", thread->get_id()); - threadlist[*numthreads] = thread->get_id(); + thread_id_t tid = thread->get_id(); + history->remove_waiting_write(tid); + + 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); } bool NewFuzzer::shouldWait(const ModelAction * act) diff --git a/newfuzzer.h b/newfuzzer.h index d6fa3a4f..c152c5d9 100644 --- a/newfuzzer.h +++ b/newfuzzer.h @@ -12,6 +12,7 @@ public: int selectWrite(ModelAction *read, SnapVector* rf_set); Predicate * get_selected_child_branch(thread_id_t tid); bool has_paused_threads(); + void notify_paused_thread(Thread * thread); Thread * selectThread(int * threadlist, int numthreads); Thread * selectNotify(action_list_t * waiters); @@ -34,14 +35,13 @@ private: bool prune_writes(thread_id_t tid, Predicate * pred, SnapVector * rf_set, inst_act_map_t * inst_act_map); Predicate * selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst); - /* Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. - * Only used by selectWrite; + /* The set of Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. Only used by selectWrite. */ SnapVector paused_thread_set; + HashTable paused_thread_table; void conditional_sleep(Thread * thread); void wake_up_paused_threads(int * threadlist, int * numthreads); - bool notify_conditional_sleep(Thread * thread); }; #endif /* end of __NEWFUZZER_H__ */