From 65cdd5bd2acccc8e6d854f0310f3deb5fb5dbaf6 Mon Sep 17 00:00:00 2001 From: weiyu Date: Thu, 13 Feb 2020 17:37:49 -0800 Subject: [PATCH] Need to handle recursive calls --- funcinst.cc | 40 ++++++++++++++++++++++++----------- funcinst.h | 11 +++++----- funcnode.cc | 59 +++++++++++++++++++++++++++++----------------------- funcnode.h | 14 ++++--------- newfuzzer.cc | 1 - 5 files changed, 70 insertions(+), 55 deletions(-) diff --git a/funcinst.cc b/funcinst.cc index 4c584452..30c92d2b 100644 --- a/funcinst.cc +++ b/funcinst.cc @@ -5,7 +5,7 @@ FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) : single_location(true), execution_number(0), associated_reads(), - thrd_marker() /* The marker for FuncNode starts from 1 */ + thrd_markers() { ASSERT(act); ASSERT(func_node); @@ -48,28 +48,44 @@ bool FuncInst::add_succ(FuncInst * other) return true; } -void FuncInst::set_associated_read(thread_id_t tid, uint64_t read_val, uint32_t marker) +void FuncInst::set_associated_read(thread_id_t tid, int index, uint32_t marker, uint64_t read_val) { int thread_id = id_to_int(tid); - int old_size = associated_reads.size(); - if (old_size < thread_id + 1) { - for (int i = old_size; i < thread_id + 1; i++ ) { - associated_reads.push_back(VALUE_NONE); - thrd_marker.push_back(0); + if (associated_reads.size() < (uint) thread_id + 1) { + int old_size = associated_reads.size(); + int new_size = thread_id + 1; + + associated_reads.resize(new_size); + thrd_markers.resize(new_size); + + for (int i = old_size; i < new_size; i++ ) { + associated_reads[i] = new ModelVector(); + thrd_markers[i] = new ModelVector(); + } + } + + ModelVector * read_values = associated_reads[thread_id]; + ModelVector * markers = thrd_markers[thread_id]; + if (read_values->size() < (uint) index + 1) { + int old_size = read_values->size(); + + for (int i = old_size; i < index + 1; i++) { + read_values->push_back(VALUE_NONE); + markers->push_back(0); } } - thrd_marker[thread_id] = marker; - associated_reads[thread_id] = read_val; + (*read_values)[index] = read_val; + (*markers)[index] = marker; } -uint64_t FuncInst::get_associated_read(thread_id_t tid, uint32_t marker) +uint64_t FuncInst::get_associated_read(thread_id_t tid, int index, uint32_t marker) { int thread_id = id_to_int(tid); - if (thrd_marker[thread_id] == marker) - return associated_reads[thread_id]; + if ( (*thrd_markers[thread_id])[index] == marker) + return (*associated_reads[thread_id])[index]; else return VALUE_NONE; } diff --git a/funcinst.h b/funcinst.h index ca733f67..c4d41eec 100644 --- a/funcinst.h +++ b/funcinst.h @@ -2,11 +2,10 @@ #define __FUNCINST_H__ #include "action.h" +#include "classlist.h" #include "hashtable.h" #include "threads-model.h" -class ModelAction; - typedef ModelList func_inst_list_mt; class FuncInst { @@ -40,8 +39,8 @@ public: void set_execution_number(int new_number) { execution_number = new_number; } int get_execution_number() { return execution_number; } - void set_associated_read(thread_id_t tid, uint64_t read_val, uint32_t marker); - uint64_t get_associated_read(thread_id_t tid, uint32_t marker); + void set_associated_read(thread_id_t tid, int index, uint32_t marker, uint64_t read_val); + uint64_t get_associated_read(thread_id_t tid, int index, uint32_t marker); void print(); @@ -65,8 +64,8 @@ private: bool single_location; int execution_number; - ModelVector associated_reads; - ModelVector thrd_marker; + ModelVector< ModelVector * > associated_reads; + ModelVector< ModelVector * > thrd_markers; /** * Collisions store a list of FuncInsts with the same position diff --git a/funcnode.cc b/funcnode.cc index 5a0969d2..5d372f30 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -10,10 +10,10 @@ FuncNode::FuncNode(ModelHistory * history) : history(history), - exit_count(0), inst_counter(1), marker(1), - thrd_marker(), + thrd_markers(), + thrd_recursion_depth(), func_inst_map(), inst_list(), entry_insts(), @@ -22,7 +22,6 @@ FuncNode::FuncNode(ModelHistory * history) : thrd_loc_inst_map(), thrd_predicate_tree_position(), thrd_predicate_trace(), - failed_predicates(), edge_table(32), out_edges() { @@ -166,7 +165,7 @@ void FuncNode::add_entry_inst(FuncInst * inst) void FuncNode::function_entry_handler(thread_id_t tid) { - set_marker(tid); + init_marker(tid); init_inst_act_map(tid); init_local_maps(tid); init_predicate_tree_data_structure(tid); @@ -174,7 +173,9 @@ void FuncNode::function_entry_handler(thread_id_t tid) void FuncNode::function_exit_handler(thread_id_t tid) { - exit_count++; + int thread_id = id_to_int(tid); + thrd_recursion_depth[thread_id]--; + thrd_markers[thread_id]->pop_back(); reset_inst_act_map(tid); reset_local_maps(tid); @@ -282,7 +283,8 @@ void FuncNode::update_predicate_tree(ModelAction * next_act) { thread_id_t tid = next_act->get_tid(); int thread_id = id_to_int(tid); - int this_marker = thrd_marker[thread_id]; + uint32_t this_marker = thrd_markers[thread_id]->back(); + int recursion_depth = thrd_recursion_depth[thread_id]; loc_inst_map_t * loc_inst_map = thrd_loc_inst_map[thread_id]; inst_pred_map_t * inst_pred_map = thrd_inst_pred_map[thread_id]; @@ -291,7 +293,7 @@ void FuncNode::update_predicate_tree(ModelAction * next_act) Predicate * curr_pred = get_predicate_tree_position(tid); while (true) { FuncInst * next_inst = get_inst(next_act); - next_inst->set_associated_read(tid, next_act->get_reads_from_value(), this_marker); + next_inst->set_associated_read(tid, recursion_depth, this_marker, next_act->get_reads_from_value()); Predicate * unset_predicate = NULL; bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &unset_predicate); @@ -363,7 +365,9 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, /* Check if a branch with func_inst and corresponding predicate exists */ bool branch_found = false; thread_id_t tid = next_act->get_tid(); - int this_marker = thrd_marker[id_to_int(tid)]; + int thread_id = id_to_int(tid); + uint32_t this_marker = thrd_markers[thread_id]->back(); + int recursion_depth = thrd_recursion_depth[thread_id]; ModelVector * branches = (*curr_pred)->get_children(); for (uint i = 0;i < branches->size();i++) { @@ -401,7 +405,7 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, FuncInst * to_be_compared; to_be_compared = pred_expression->func_inst; - last_read = to_be_compared->get_associated_read(tid, this_marker); + last_read = to_be_compared->get_associated_read(tid, recursion_depth, this_marker); ASSERT(last_read != VALUE_NONE); next_read = next_act->get_reads_from_value(); @@ -696,31 +700,40 @@ inst_act_map_t * FuncNode::get_inst_act_map(thread_id_t tid) return (*thrd_inst_act_map)[thread_id]; } -void FuncNode::set_marker(thread_id_t tid) +void FuncNode::init_marker(thread_id_t tid) { marker++; - uint thread_id = id_to_int(tid); - for (uint i = thrd_marker.size(); i < thread_id + 1; i++) { - thrd_marker.push_back(0); + + int thread_id = id_to_int(tid); + int old_size = thrd_markers.size(); + + if (old_size < thread_id + 1) { + thrd_markers.resize(thread_id + 1); + + for (int i = old_size; i < thread_id + 1; i++) { + thrd_markers[i] = new ModelVector(); + thrd_recursion_depth.push_back(-1); + } } - thrd_marker[thread_id] = marker; + thrd_markers[thread_id]->push_back(marker); + thrd_recursion_depth[thread_id]++; } /* Make sure elements of maps are initialized properly when threads enter functions */ void FuncNode::init_local_maps(thread_id_t tid) { int thread_id = id_to_int(tid); - uint old_size = thrd_loc_inst_map.size(); + int old_size = thrd_loc_inst_map.size(); - if (old_size <= (uint) thread_id) { - uint new_size = thread_id + 1; + if (old_size < thread_id + 1) { + int new_size = thread_id + 1; thrd_loc_inst_map.resize(new_size); thrd_inst_id_map.resize(new_size); thrd_inst_pred_map.resize(new_size); - for (uint i = old_size; i < new_size; i++) { + for (int i = old_size; i < new_size; i++) { thrd_loc_inst_map[i] = new loc_inst_map_t(128); thrd_inst_id_map[i] = new inst_id_map_t(128); thrd_inst_pred_map[i] = new inst_pred_map_t(128); @@ -742,7 +755,7 @@ void FuncNode::init_predicate_tree_data_structure(thread_id_t tid) int thread_id = id_to_int(tid); int old_size = thrd_predicate_tree_position.size(); - if (old_size <= thread_id + 1) { + if (old_size < thread_id + 1) { thrd_predicate_tree_position.resize(thread_id + 1); thrd_predicate_trace.resize(thread_id + 1); @@ -761,6 +774,7 @@ void FuncNode::reset_predicate_tree_data_structure(thread_id_t tid) int thread_id = id_to_int(tid); thrd_predicate_tree_position[thread_id]->pop_back(); + // Free memories allocated in init_predicate_tree_data_structure predicate_trace_t * trace = thrd_predicate_trace[thread_id]->back(); delete trace; thrd_predicate_trace[thread_id]->pop_back(); @@ -827,15 +841,8 @@ int FuncNode::compute_distance(FuncNode * target, int max_step) return -1; } -void FuncNode::add_failed_predicate(Predicate * pred) -{ - failed_predicates.add(pred); -} - void FuncNode::update_predicate_tree_weight(thread_id_t tid) { - failed_predicates.reset(); - predicate_trace_t * trace = thrd_predicate_trace[id_to_int(tid)]->back(); // Update predicate weights based on prediate trace diff --git a/funcnode.h b/funcnode.h index 354534d5..133d5522 100644 --- a/funcnode.h +++ b/funcnode.h @@ -47,8 +47,6 @@ public: void update_predicate_tree(ModelAction * act); bool follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act, Predicate ** unset_predicate); - uint32_t get_exit_count() { return exit_count; } - void add_to_val_loc_map(uint64_t val, void * loc); void add_to_val_loc_map(value_set_t * values, void * loc); void update_loc_may_equal_map(void * new_loc, loc_set_t * old_locations); @@ -67,8 +65,6 @@ public: ModelList * get_out_edges() { return &out_edges; } int compute_distance(FuncNode * target, int max_step = MAX_DIST); - void add_failed_predicate(Predicate * pred); - void print_predicate_tree(); MEMALLOC @@ -79,12 +75,12 @@ private: Predicate * predicate_tree_entry; // A dummy node whose children are the real entries Predicate * predicate_tree_exit; // A dummy node - uint32_t exit_count; uint32_t inst_counter; uint32_t marker; - ModelVector thrd_marker; + ModelVector< ModelVector *> thrd_markers; + ModelVector thrd_recursion_depth; - void set_marker(thread_id_t tid); + void init_marker(thread_id_t tid); /* Use source line number as the key of hashtable, to check if * atomic operation with this line number has been added or not @@ -103,7 +99,7 @@ private: /* Number FuncInsts to detect loops when updating predicate trees */ ModelVector thrd_inst_id_map; - /* Delect read actions at the same locations when updating predicate trees */ + /* Detect read actions at the same locations when updating predicate trees */ ModelVector thrd_loc_inst_map; void init_local_maps(thread_id_t tid); @@ -136,8 +132,6 @@ private: void init_predicate_tree_data_structure(thread_id_t tid); void reset_predicate_tree_data_structure(thread_id_t tid); - PredSet failed_predicates; - /* Store the relation between this FuncNode and other FuncNodes */ HashTable edge_table; diff --git a/newfuzzer.cc b/newfuzzer.cc index 299156b8..35e16d2e 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -89,7 +89,6 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set // Add failed predicate to NewFuzzer and FuncNode failed_predicates.put(selected_branch, true); - func_node->add_failed_predicate(selected_branch); selected_branch->incr_fail_count(); //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()); -- 2.34.1