From 926e6a993b8d578b3ccb763bcc8adb699d9059df Mon Sep 17 00:00:00 2001 From: weiyu Date: Wed, 18 Sep 2019 17:55:27 -0700 Subject: [PATCH] Keep track of which FuncNodes may write to a memory location --- funcnode.cc | 28 +++++++++++++++++----------- funcnode.h | 17 ++++++++++++----- history.cc | 52 ++++++++++++++++++++++++++++++---------------------- history.h | 10 ++++++++-- 4 files changed, 67 insertions(+), 40 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index 93e6b09d..3db02269 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -13,9 +13,10 @@ FuncNode::FuncNode(ModelHistory * history) : predicate_tree_entry = new Predicate(NULL, true); predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true); - // memories that are reclaimed after each execution + // Memories that are reclaimed after each execution action_list_buffer = new SnapList(); read_locations = new loc_set_t(); + write_locations = new loc_set_t(); val_loc_map = new HashTable(); loc_may_equal_map = new HashTable(); thrd_inst_act_map = new SnapVector(); @@ -33,6 +34,7 @@ void FuncNode::set_new_exec_flag() action_list_buffer = new SnapList(); read_locations = new loc_set_t(); + write_locations = new loc_set_t(); val_loc_map = new HashTable(); loc_may_equal_map = new HashTable(); thrd_inst_act_map = new SnapVector(); @@ -143,23 +145,28 @@ void FuncNode::update_tree(action_list_t * act_list) for (sllnode * it = act_list->begin(); it != NULL; it = it->getNext()) { ModelAction * act = it->getVal(); FuncInst * func_inst = get_inst(act); + void * loc = act->get_location(); if (func_inst == NULL) continue; inst_list.push_back(func_inst); + bool act_added = false; - /* NOTE: for rmw actions, func_inst and act may have different - * action types because of action type conversion in ModelExecution - * func_inst->is_write() <==> pure writes (excluding rmw) */ - if (func_inst->is_write()) { - // model_print("write detected\n"); + if (act->is_write()) { rw_act_list.push_back(act); + act_added = true; + if (!write_locations->contains(loc)) { + write_locations->add(loc); + history->update_loc_wr_func_nodes_map(loc, this); + } + } - /* func_inst->is_read() <==> read + rmw */ - if (func_inst->is_read()) { - rw_act_list.push_back(act); + if (act->is_read()) { + if (!act_added) + rw_act_list.push_back(act); + /* If func_inst may only read_from a single location, then: * * The first time an action reads from some location, @@ -167,12 +174,11 @@ void FuncNode::update_tree(action_list_t * act_list) * location from ModelHistory and notify ModelHistory * that this FuncNode may read from this location. */ - void * loc = act->get_location(); if (!read_locations->contains(loc) && func_inst->is_single_location()) { read_locations->add(loc); value_set_t * write_values = write_history->get(loc); add_to_val_loc_map(write_values, loc); - history->add_to_loc_func_nodes_map(loc, this); + history->update_loc_func_nodes_map(loc, this); } } } diff --git a/funcnode.h b/funcnode.h index 3a353fd8..22d92835 100644 --- a/funcnode.h +++ b/funcnode.h @@ -91,13 +91,18 @@ private: /* Store action_lists when calls to update_tree are deferred */ SnapList * action_list_buffer; - /* read_locations: set of locations read by this FuncNode - * val_loc_map: keep track of locations that have the same values written to; - * loc_may_equal_map: look up locations that may share the same value as key; - * deduced from val_loc_map; */ + /* Set of locations read by this FuncNode */ loc_set_t * read_locations; + + /* Set of locations written to by this FuncNode */ + loc_set_t * write_locations; + + /* Keeps track of locations that have the same values written to */ HashTable * val_loc_map; + + /* Keeps track of locations that may share the same value as key, deduced from val_loc_map */ HashTable * loc_may_equal_map; + // value_set_t * values_may_read_from; /* Run-time position in the predicate tree for each thread */ @@ -108,7 +113,9 @@ private: /* Store the relation between this FuncNode and other FuncNodes */ HashTable edge_table; - ModelList out_edges; /* FuncNodes that follow this node */ + + /* FuncNodes that follow this node */ + ModelList out_edges; }; #endif /* __FUNCNODE_H__ */ diff --git a/history.cc b/history.cc index cb5307a9..568cecb5 100644 --- a/history.cc +++ b/history.cc @@ -144,17 +144,16 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) if (act->is_write()) { void * location = act->get_location(); uint64_t value = act->get_write_value(); - add_to_write_history(location, value); + update_write_history(location, value); - /* update FuncNodes */ + /* Update FuncNodes that may read from this location */ SnapList * func_nodes = loc_func_nodes_map.get(location); - sllnode * it = NULL; - if (func_nodes != NULL) - it = func_nodes->begin(); - - for (; it != NULL; it = it->getNext()) { - FuncNode * func_node = it->getVal(); - func_node->add_to_val_loc_map(value, 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); + } } } @@ -167,19 +166,17 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) action_list_t * curr_act_list = func_act_lists->back(); ASSERT(curr_act_list != NULL); - ModelAction * last_act = NULL; - if (curr_act_list->size() != 0) - last_act = curr_act_list->back(); - - /* skip actions that are paused by fuzzer (sequence number is 0), - * that are second part of a read modify write or actions with the same sequence number */ modelclock_t curr_seq_number = act->get_seq_number(); - if (curr_seq_number == 0 || second_part_of_rmw || - (last_act != NULL && last_act->get_seq_number() == curr_seq_number) ) - return; + /* Skip actions that are second part of a read modify write or actions with the same sequence number */ + if (curr_act_list->size() != 0) { + ModelAction * last_act = curr_act_list->back(); + if (second_part_of_rmw || last_act->get_seq_number() == curr_seq_number) + return; + } - if ( func_nodes.size() <= func_id ) - resize_func_nodes( func_id + 1 ); + /* skip actions that are paused by fuzzer (sequence number is 0) */ + if (curr_seq_number == 0) + return; FuncNode * func_node = func_nodes[func_id]; @@ -206,7 +203,7 @@ FuncNode * ModelHistory::get_func_node(uint32_t func_id) return func_nodes[func_id]; } -void ModelHistory::add_to_write_history(void * location, uint64_t write_val) +void ModelHistory::update_write_history(void * location, uint64_t write_val) { value_set_t * write_set = write_history.get(location); @@ -218,7 +215,7 @@ void ModelHistory::add_to_write_history(void * location, uint64_t write_val) write_set->add(write_val); } -void ModelHistory::add_to_loc_func_nodes_map(void * location, FuncNode * node) +void ModelHistory::update_loc_func_nodes_map(void * location, FuncNode * node) { SnapList * func_node_list = loc_func_nodes_map.get(location); if (func_node_list == NULL) { @@ -229,6 +226,17 @@ void ModelHistory::add_to_loc_func_nodes_map(void * location, FuncNode * node) func_node_list->push_back(node); } +void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node) +{ + SnapList * 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->push_back(node); +} + /* Reallocate some snapshotted memories when new executions start */ void ModelHistory::set_new_exec_flag() { diff --git a/history.h b/history.h index ee07ba4f..e85aa81a 100644 --- a/history.h +++ b/history.h @@ -27,9 +27,10 @@ public: ModelVector * getFuncNodes() { return &func_nodes; } FuncNode * get_func_node(uint32_t func_id); - void add_to_write_history(void * location, uint64_t write_val); + void update_write_history(void * location, uint64_t write_val); HashTable * getWriteHistory() { return &write_history; } - void add_to_loc_func_nodes_map(void * location, FuncNode * node); + void update_loc_func_nodes_map(void * location, FuncNode * node); + void update_loc_wr_func_nodes_map(void * location, FuncNode * node); void set_new_exec_flag(); void dump_func_node_graph(); @@ -47,11 +48,16 @@ private: ModelVector func_nodes; + /* Map a location to a set of values that have been written to it */ HashTable write_history; /* Map a location to FuncNodes that may read from it */ HashTable *, uintptr_t, 4> loc_func_nodes_map; + /* Map a location to FuncNodes that may write to it */ + HashTable *, uintptr_t, 4> loc_wr_func_nodes_map; + + /* Keeps track of the last function entered by each thread */ SnapVector thrd_last_entered_func; void add_edges_between(FuncNode * prev_node, FuncNode * next_node); }; -- 2.34.1