From dc8e9b89ec62b6da4816ec4e31fe2971cbcdcb54 Mon Sep 17 00:00:00 2001 From: weiyu Date: Wed, 2 Oct 2019 18:26:36 -0700 Subject: [PATCH] Toward computing which threads a paused thread may wait for --- funcnode.cc | 2 +- history.cc | 69 +++++++++++++++++++++++++++++++++++++---------------- history.h | 14 ++++++++--- 3 files changed, 61 insertions(+), 24 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index a402ecb4..9228dc77 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -181,7 +181,7 @@ void FuncNode::update_tree(action_list_t * act_list) read_locations->add(loc); value_set_t * write_values = write_history->get(loc); add_to_val_loc_map(write_values, loc); - history->update_loc_func_nodes_map(loc, this); + history->update_loc_rd_func_nodes_map(loc, this); } } } diff --git a/history.cc b/history.cc index faccdacb..3e0644ed 100644 --- a/history.cc +++ b/history.cc @@ -19,11 +19,12 @@ ModelHistory::ModelHistory() : { /* The following are snapshot data structures */ write_history = new HashTable(); - loc_func_nodes_map = new HashTable *, uintptr_t, 0>(); - loc_wr_func_nodes_map = new HashTable *, uintptr_t, 0>(); + loc_rd_func_nodes_map = new HashTable *, uintptr_t, 0>(); + loc_wr_func_nodes_map = new HashTable *, uintptr_t, 0>(); loc_waiting_writes_map = new HashTable *, uintptr_t, 0>(); thrd_waiting_write = new SnapVector(); - func_inst_act_maps = new HashTable *, int, 0>(); + func_inst_act_maps = new HashTable *, int, 0>(128); + func_threads_map = new HashTable *, int, 0>(128); } void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) @@ -155,13 +156,10 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) update_write_history(location, value); /* Update FuncNodes that may read from this location */ - SnapList * func_nodes = loc_func_nodes_map->get(location); - if (func_nodes != NULL) { - sllnode * it = func_nodes->begin(); - for (; it != NULL; it = it->getNext()) { - FuncNode * func_node = it->getVal(); - func_node->add_to_val_loc_map(value, location); - } + SnapVector * func_node_list = getRdFuncNodes(location); + for (uint i = 0; i < func_node_list->size(); i++) { + FuncNode * func_node = (*func_node_list)[i]; + func_node->add_to_val_loc_map(value, location); } check_waiting_write(act); @@ -232,26 +230,38 @@ void ModelHistory::update_write_history(void * location, uint64_t write_val) write_set->add(write_val); } -void ModelHistory::update_loc_func_nodes_map(void * location, FuncNode * node) +void ModelHistory::update_loc_rd_func_nodes_map(void * location, FuncNode * node) +{ + SnapVector * func_node_list = getRdFuncNodes(location); + func_node_list->push_back(node); +} + +void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node) { - SnapList * func_node_list = loc_func_nodes_map->get(location); + SnapVector * func_node_list = getWrFuncNodes(location); + func_node_list->push_back(node); +} + +SnapVector * ModelHistory::getRdFuncNodes(void * location) +{ + SnapVector * func_node_list = loc_rd_func_nodes_map->get(location); if (func_node_list == NULL) { - func_node_list = new SnapList(); - loc_func_nodes_map->put(location, func_node_list); + func_node_list = new SnapVector(); + loc_wr_func_nodes_map->put(location, func_node_list); } - func_node_list->push_back(node); + return func_node_list; } -void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node) +SnapVector * ModelHistory::getWrFuncNodes(void * location) { - SnapList * func_node_list = loc_wr_func_nodes_map->get(location); + SnapVector * func_node_list = loc_wr_func_nodes_map->get(location); if (func_node_list == NULL) { - func_node_list = new SnapList(); - loc_func_nodes_map->put(location, func_node_list); + func_node_list = new SnapVector(); + loc_wr_func_nodes_map->put(location, func_node_list); } - func_node_list->push_back(node); + return func_node_list; } /* When a thread is paused by Fuzzer, keep track of the condition it is waiting for */ @@ -387,6 +397,25 @@ bool ModelHistory::skip_action(ModelAction * act, SnapList * curr return false; } +void ModelHistory::update_func_threads_map(uint32_t func_id, thread_id_t tid) +{ + SnapVector * thread_ids = get_calling_threads(func_id); + thread_ids->push_back(tid); +} + +/* Return a vector of thread_id's that have called this function before */ +SnapVector * ModelHistory::get_calling_threads(uint32_t func_id) +{ + SnapVector * thread_ids = func_threads_map->get(func_id); + if (thread_ids == NULL) { + /* Make sure the result can be iterated without checking nullity */ + thread_ids = new SnapVector(); + func_threads_map->put(func_id, thread_ids); + } + + return thread_ids; +} + /* Reallocate some snapshotted memories when new executions start */ void ModelHistory::set_new_exec_flag() { diff --git a/history.h b/history.h index ce75e2ac..869aecf5 100644 --- a/history.h +++ b/history.h @@ -30,8 +30,10 @@ public: 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_rd_func_nodes_map(void * location, FuncNode * node); void update_loc_wr_func_nodes_map(void * location, FuncNode * node); + SnapVector * getRdFuncNodes(void * location); + SnapVector * getWrFuncNodes(void * location); void add_waiting_write(ConcretePredicate * concrete); void remove_waiting_write(thread_id_t tid); @@ -40,6 +42,9 @@ public: SnapVector * getThrdInstActMap(uint32_t func_id); + void update_func_threads_map(uint32_t func_id, thread_id_t tid); + SnapVector * get_calling_threads(uint32_t func_id); + void set_new_exec_flag(); void dump_func_node_graph(); void print_func_node(); @@ -60,10 +65,10 @@ private: HashTable * write_history; /* Map a location to FuncNodes that may read from it */ - HashTable *, uintptr_t, 0> * loc_func_nodes_map; + HashTable *, uintptr_t, 0> * loc_rd_func_nodes_map; /* Map a location to FuncNodes that may write to it */ - HashTable *, uintptr_t, 0> * loc_wr_func_nodes_map; + HashTable *, uintptr_t, 0> * loc_wr_func_nodes_map; HashTable *, uintptr_t, 0> * loc_waiting_writes_map; SnapVector * thrd_waiting_write; @@ -73,6 +78,9 @@ private: HashTable *, int, 0> * func_inst_act_maps; bool skip_action(ModelAction * act, SnapList * curr_act_list); + + /* Map func_id to threads that have called this function */ + HashTable *, int, 0> * func_threads_map; }; #endif /* __HISTORY_H__ */ -- 2.34.1