From 4ba63eb5064000a0974833515006355d173bdcf9 Mon Sep 17 00:00:00 2001 From: weiyu Date: Thu, 12 Sep 2019 19:02:10 -0700 Subject: [PATCH] Add edges between FuncNodes --- funcnode.cc | 39 +++++++++++++++++++++++++++++++++++++-- funcnode.h | 13 ++++++++++++- history.cc | 17 ++++++++++++++++- history.h | 2 ++ 4 files changed, 67 insertions(+), 4 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index 19601fac..c490ba22 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -2,12 +2,14 @@ FuncNode::FuncNode(ModelHistory * history) : history(history), - predicate_tree_initialized(false), exit_count(0), func_inst_map(), inst_list(), entry_insts(), - predicate_tree_position() + predicate_tree_position(), + edge_table(32), + out_edges(), + in_edges() { predicate_tree_entry = new Predicate(NULL, true); predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true); @@ -603,6 +605,39 @@ inst_act_map_t * FuncNode::get_inst_act_map(thread_id_t tid) return (*thrd_inst_act_map)[thread_id]; } +/* Add FuncNodes that this node may follow */ +void FuncNode::add_out_edge(FuncNode * other) +{ + if ( !edge_table.contains(other) ) { + edge_table.put(other, OUT_EDGE); + out_edges.push_back(other); + return; + } + + edge_type_t edge = edge_table.get(other); + if (edge == IN_EDGE) { + edge_table.put(other, BI_EDGE); + out_edges.push_back(other); + } +} + +/* Add FuncNodes that come before this node */ +void FuncNode::add_in_edge(FuncNode * other) +{ + if ( !edge_table.contains(other) ) { + edge_table.put(other, IN_EDGE); + in_edges.push_back(other); + return; + } + + edge_type_t edge = edge_table.get(other); + if (edge == OUT_EDGE) { + edge_table.put(other, BI_EDGE); + in_edges.push_back(other); + } +} + + void FuncNode::print_predicate_tree() { model_print("digraph function_%s {\n", func_name); diff --git a/funcnode.h b/funcnode.h index c70bc59c..a2037dc3 100644 --- a/funcnode.h +++ b/funcnode.h @@ -11,6 +11,10 @@ typedef ModelList func_inst_list_mt; typedef HashTable inst_act_map_t; +typedef enum edge_type { + IN_EDGE, OUT_EDGE, BI_EDGE +} edge_type_t; + class FuncNode { public: FuncNode(ModelHistory * history); @@ -53,6 +57,9 @@ public: void update_inst_act_map(thread_id_t tid, ModelAction * read_act); inst_act_map_t * get_inst_act_map(thread_id_t tid); + void add_out_edge(FuncNode * other); + void add_in_edge(FuncNode * other); + void print_predicate_tree(); void print_val_loc_map(); void print_last_read(thread_id_t tid); @@ -62,7 +69,6 @@ private: uint32_t func_id; const char * func_name; ModelHistory * history; - bool predicate_tree_initialized; Predicate * predicate_tree_entry; // a dummy node whose children are the real entries uint32_t exit_count; @@ -99,6 +105,11 @@ private: /* A run-time map from FuncInst to ModelAction for each thread; needed by NewFuzzer */ SnapVector * thrd_inst_act_map; + + /* Store the relation between this FuncNode and other FuncNodes */ + HashTable edge_table; + ModelList out_edges; /* FuncNodes that follow this node */ + ModelList in_edges; /* FuncNodes that comes before this node */ }; #endif /* __FUNCNODE_H__ */ diff --git a/history.cc b/history.cc index 8a605fbf..42a218e0 100644 --- a/history.cc +++ b/history.cc @@ -42,9 +42,10 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) } SnapList * func_act_lists = (*thrd_func_act_lists)[id]; + func_act_lists->push_back( new action_list_t() ); + uint32_t last_func_id = (*thrd_func_list)[id].back(); (*thrd_func_list)[id].push_back(func_id); - func_act_lists->push_back( new action_list_t() ); if ( func_nodes.size() <= func_id ) resize_func_nodes( func_id + 1 ); @@ -52,6 +53,12 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) FuncNode * func_node = func_nodes[func_id]; func_node->init_predicate_tree_position(tid); func_node->init_inst_act_map(tid); + + /* Add edges between FuncNodes */ + if (last_func_id != 0) { + FuncNode * last_func_node = func_nodes[last_func_id]; + add_edges_between(last_func_node, func_node); + } } /* @param func_id a non-zero value */ @@ -178,6 +185,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) if (act->is_read()) { func_node->update_inst_act_map(tid, act); + // Update predicate tree position Fuzzer * fuzzer = model->get_execution()->getFuzzer(); Predicate * selected_branch = fuzzer->get_selected_child_branch(tid); func_node->set_predicate_tree_position(tid, selected_branch); @@ -225,6 +233,13 @@ void ModelHistory::set_new_exec_flag() } } +/* Add edges between FuncNodes */ +void ModelHistory::add_edges_between(FuncNode * prev_node, FuncNode * next_node) +{ + prev_node->add_out_edge(next_node); + next_node->add_in_edge(prev_node); +} + void ModelHistory::print_write() { } diff --git a/history.h b/history.h index 0a51e640..7a01d402 100644 --- a/history.h +++ b/history.h @@ -51,6 +51,8 @@ private: /* Map a location to FuncNodes that may read from it */ HashTable *, uintptr_t, 4> loc_func_nodes_map; + + void add_edges_between(FuncNode * prev_node, FuncNode * next_node); }; #endif /* __HISTORY_H__ */ -- 2.34.1