From ca293a527c74c31998a55e447e1e72244ec2a2f5 Mon Sep 17 00:00:00 2001 From: weiyu Date: Wed, 4 Dec 2019 12:29:02 -0800 Subject: [PATCH] Fix NewFuzzer::selectWrite - check back edges --- cmodelint.cc | 61 +++++++++++++++--------------- execution.cc | 19 +++++----- fuzzer.h | 1 + history.cc | 17 ++++++++- newfuzzer.cc | 102 +++++++++++++++++++++++++++++++-------------------- newfuzzer.h | 4 +- predicate.cc | 18 +++++++++ predicate.h | 1 + 8 files changed, 140 insertions(+), 83 deletions(-) diff --git a/cmodelint.cc b/cmodelint.cc index 1a03153f..ea34324b 100644 --- a/cmodelint.cc +++ b/cmodelint.cc @@ -341,46 +341,45 @@ void cds_atomic_thread_fence(int atomic_index, const char * position) { void cds_func_entry(const char * funcName) { ensureModel(); - /* - Thread * th = thread_current(); - uint32_t func_id; - - ModelHistory *history = model->get_history(); - if ( !history->getFuncMap()->contains(funcName) ) { - // add func id to func map - func_id = history->get_func_counter(); - history->incr_func_counter(); - history->getFuncMap()->put(funcName, func_id); - - // add func id to reverse func map - ModelVector * func_map_rev = history->getFuncMapRev(); - if ( func_map_rev->size() <= func_id ) - func_map_rev->resize( func_id + 1 ); - func_map_rev->at(func_id) = funcName; - } else { - func_id = history->getFuncMap()->get(funcName); - } - - history->enter_function(func_id, th->get_id()); - */ + Thread * th = thread_current(); + uint32_t func_id; + + ModelHistory *history = model->get_history(); + if ( !history->getFuncMap()->contains(funcName) ) { + // add func id to func map + func_id = history->get_func_counter(); + history->incr_func_counter(); + history->getFuncMap()->put(funcName, func_id); + + // add func id to reverse func map + ModelVector * func_map_rev = history->getFuncMapRev(); + if ( func_map_rev->size() <= func_id ) + func_map_rev->resize( func_id + 1 ); + + func_map_rev->at(func_id) = funcName; + } else { + func_id = history->getFuncMap()->get(funcName); + } + + history->enter_function(func_id, th->get_id()); } void cds_func_exit(const char * funcName) { ensureModel(); -/* Thread * th = thread_current(); - uint32_t func_id; - - ModelHistory *history = model->get_history(); - func_id = history->getFuncMap()->get(funcName); + Thread * th = thread_current(); + uint32_t func_id; + ModelHistory *history = model->get_history(); + func_id = history->getFuncMap()->get(funcName); +/* * func_id not found; this could happen in the case where a function calls cds_func_entry * when the model has been defined yet, but then an atomic inside the function initializes * the model. And then cds_func_exit is called upon the function exiting. * - if (func_id == 0) - return; - - history->exit_function(func_id, th->get_id()); */ + if (func_id == 0) + return; + + history->exit_function(func_id, th->get_id()); } diff --git a/execution.cc b/execution.cc index 6057ec51..21207fef 100644 --- a/execution.cc +++ b/execution.cc @@ -268,7 +268,7 @@ ModelAction * ModelExecution::convertNonAtomicStore(void * location) { add_normal_write_to_lists(act); add_write_to_lists(act); w_modification_order(act); -// model->get_history()->process_action(act, act->get_tid()); + model->get_history()->process_action(act, act->get_tid()); return act; } @@ -288,14 +288,13 @@ bool ModelExecution::process_read(ModelAction *curr, SnapVector * } // Remove writes that violate read modification order - /* - for (uint i = 0; i < rf_set->size(); i++) { - ModelAction * rf = (*rf_set)[i]; - if (!r_modification_order(curr, rf, NULL, NULL, true)) { - (*rf_set)[i] = rf_set->back(); - rf_set->pop_back(); - } - }*/ + for (uint i = 0; i < rf_set->size(); i++) { + ModelAction * rf = (*rf_set)[i]; + if (!r_modification_order(curr, rf, NULL, NULL, true)) { + (*rf_set)[i] = rf_set->back(); + rf_set->pop_back(); + } + } while(true) { int index = fuzzer->selectWrite(curr, rf_set); @@ -1706,7 +1705,7 @@ Thread * ModelExecution::take_step(ModelAction *curr) ASSERT(curr); /* Process this action in ModelHistory for records */ -// model->get_history()->process_action( curr, curr->get_tid() ); + model->get_history()->process_action( curr, curr->get_tid() ); if (curr_thrd->is_blocked() || curr_thrd->is_complete()) scheduler->remove_thread(curr_thrd); diff --git a/fuzzer.h b/fuzzer.h index c5248d72..d31c2267 100644 --- a/fuzzer.h +++ b/fuzzer.h @@ -18,6 +18,7 @@ public: bool shouldWake(const ModelAction *sleep); virtual bool shouldWait(const ModelAction *wait) = 0; virtual void register_engine(ModelHistory * history, ModelExecution * execution) = 0; + virtual Predicate * get_selected_child_branch(thread_id_t tid) = 0; SNAPSHOTALLOC private: }; diff --git a/history.cc b/history.cc index e48f1c8d..03515b53 100644 --- a/history.cc +++ b/history.cc @@ -174,7 +174,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) func_node->add_to_val_loc_map(value, location); } - check_waiting_write(act); + // check_waiting_write(act); } uint32_t func_id = (*thrd_func_list)[thread_id].back(); @@ -200,6 +200,21 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) if (act->is_read()) { func_node->update_inst_act_map(tid, act); + + Fuzzer * fuzzer = model->get_execution()->getFuzzer(); + Predicate * selected_branch = fuzzer->get_selected_child_branch(tid); + func_node->set_predicate_tree_position(tid, selected_branch); + } + + if (act->is_write()) { + Predicate * curr_pred = func_node->get_predicate_tree_position(tid); + FuncInst * curr_inst = func_node->get_inst(act); + + if (curr_pred) { + // Follow child + curr_pred = curr_pred->get_single_child(curr_inst); + } + func_node->set_predicate_tree_position(tid, curr_pred); } } diff --git a/newfuzzer.cc b/newfuzzer.cc index c7d70ac6..4d6a2963 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -33,7 +33,7 @@ void NewFuzzer::register_engine(ModelHistory * history, ModelExecution *executio int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set) { - return random() % rf_set->size(); +// return random() % rf_set->size(); thread_id_t tid = read->get_tid(); int thread_id = id_to_int(tid); @@ -50,9 +50,27 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set FuncInst * read_inst = func_node->get_inst(read); inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid); - check_store_visibility(curr_pred, read_inst, inst_act_map, rf_set); - Predicate * selected_branch = selectBranch(tid, curr_pred, read_inst); - prune_writes(tid, selected_branch, rf_set, inst_act_map); + if (curr_pred != NULL) { + Predicate * selected_branch = NULL; + + if (check_store_visibility(curr_pred, read_inst, inst_act_map, rf_set)) + selected_branch = selectBranch(tid, curr_pred, read_inst); + else { + // no child of curr_pred matches read_inst, check back edges + PredSet * back_edges = curr_pred->get_backedges(); + PredSetIter * it = back_edges->iterator(); + + while (it->hasNext()) { + curr_pred = it->next(); + if (check_store_visibility(curr_pred, read_inst, inst_act_map, rf_set)) { + selected_branch = selectBranch(tid, curr_pred, read_inst); + break; + } + } + } + + prune_writes(tid, selected_branch, rf_set, inst_act_map); + } if (!failed_predicates.isEmpty()) failed_predicates.reset(); @@ -90,14 +108,21 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set return random_index; } -void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, - inst_act_map_t * inst_act_map, SnapVector * rf_set) +/* For children of curr_pred that matches read_inst. + * If any store in rf_set satisfies the a child's predicate, + * increment the store visibility count for it. + * + * @return False if no child matches read_inst + */ +bool NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, +inst_act_map_t * inst_act_map, SnapVector * rf_set) { ASSERT(!rf_set->empty()); if (curr_pred == NULL || read_inst == NULL) - return; + return false; ModelVector * children = curr_pred->get_children(); + bool any_child_match = false; /* Iterate over all predicate children */ for (uint i = 0;i < children->size();i++) { @@ -106,6 +131,7 @@ void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_in /* The children predicates may have different FuncInsts */ if (branch->get_func_inst() == read_inst) { PredExprSet * pred_expressions = branch->get_pred_expressions(); + any_child_match = true; /* Do not check unset predicates */ if (pred_expressions->isEmpty()) @@ -127,8 +153,9 @@ void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_in } } } - } + + return any_child_match; } @@ -149,7 +176,7 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func ModelVector * children = curr_pred->get_children(); SnapVector branches; - for (uint i = 0;i < children->size();i++) { + for (uint i = 0; i < children->size(); i++) { Predicate * child = (*children)[i]; if (child->get_func_inst() == read_inst && !failed_predicates.contains(child)) { branches.push_back(child); @@ -166,10 +193,6 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func Predicate * random_branch = branches[ index ]; thrd_selected_child_branch[thread_id] = random_branch; - // Update predicate tree position - FuncNode * func_node = history->get_curr_func_node(tid); - func_node->set_predicate_tree_position(tid, random_branch); - return random_branch; } @@ -236,7 +259,7 @@ Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid) * @return true if rf_set is pruned */ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, - SnapVector * rf_set, inst_act_map_t * inst_act_map) +SnapVector * rf_set, inst_act_map_t * inst_act_map) { if (pred == NULL) return false; @@ -481,7 +504,7 @@ bool NewFuzzer::find_threads(ModelAction * pending_read) */ bool NewFuzzer::check_predicate_expressions(PredExprSet * pred_expressions, - inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate) +inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate) { bool satisfy_predicate = true; @@ -491,30 +514,31 @@ bool NewFuzzer::check_predicate_expressions(PredExprSet * pred_expressions, bool equality; switch (expression->token) { - case NOPREDICATE: - *no_predicate = true; - break; - case EQUALITY: - FuncInst * to_be_compared; - ModelAction * last_act; - uint64_t last_read; - - to_be_compared = expression->func_inst; - last_act = inst_act_map->get(to_be_compared); - last_read = last_act->get_reads_from_value(); - - equality = (write_val == last_read); - if (equality != expression->value) - satisfy_predicate = false; - break; - case NULLITY: - equality = ((void*)write_val == NULL); - if (equality != expression->value) - satisfy_predicate = false; - break; - default: - model_print("unknown predicate token\n"); - break; + case NOPREDICATE: + *no_predicate = true; + break; + case EQUALITY: + FuncInst * to_be_compared; + ModelAction * last_act; + uint64_t last_read; + + to_be_compared = expression->func_inst; + last_act = inst_act_map->get(to_be_compared); + last_read = last_act->get_reads_from_value(); + + equality = (write_val == last_read); + if (equality != expression->value) + satisfy_predicate = false; + break; + case NULLITY: + // TODO: implement likely to be null + equality = ((void*) (write_val & 0xffffffff) == NULL); + if (equality != expression->value) + satisfy_predicate = false; + break; + default: + model_print("unknown predicate token\n"); + break; } if (!satisfy_predicate) diff --git a/newfuzzer.h b/newfuzzer.h index 76f13ce6..9f30ec6d 100644 --- a/newfuzzer.h +++ b/newfuzzer.h @@ -35,6 +35,7 @@ public: bool shouldWait(const ModelAction * wait); void register_engine(ModelHistory * history, ModelExecution * execution); + Predicate * get_selected_child_branch(thread_id_t tid); SNAPSHOTALLOC private: @@ -47,9 +48,8 @@ private: SnapVector thrd_selected_child_branch; SnapVector< SnapVector *> thrd_pruned_writes; - void check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, inst_act_map_t * inst_act_map, SnapVector * rf_set); + bool check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, inst_act_map_t * inst_act_map, SnapVector * rf_set); Predicate * selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst); - Predicate * get_selected_child_branch(thread_id_t tid); bool prune_writes(thread_id_t tid, Predicate * pred, SnapVector * rf_set, inst_act_map_t * inst_act_map); int choose_index(SnapVector * branches, uint32_t numerator); diff --git a/predicate.cc b/predicate.cc index 1fd1d949..7fec1a4e 100644 --- a/predicate.cc +++ b/predicate.cc @@ -65,6 +65,24 @@ void Predicate::copy_predicate_expr(Predicate * other) } } +/* Return the single child branch of this predicate. + * Return NULL if this predicate has no children. + */ +Predicate * Predicate::get_single_child(FuncInst * inst) +{ + int size = children.size(); + if (size == 0) + return NULL; + + /* Should only have one child */ + ASSERT(size == 1); + Predicate * child = children[0]; + + ASSERT(child->get_func_inst() == inst); + + return child; +} + /* Evaluate predicate expressions against the given inst_act_map */ ConcretePredicate * Predicate::evaluate(inst_act_map_t * inst_act_map, thread_id_t tid) { diff --git a/predicate.h b/predicate.h index 2fdd6c59..11f46249 100644 --- a/predicate.h +++ b/predicate.h @@ -25,6 +25,7 @@ public: void add_backedge(Predicate * back_pred) { backedges.add(back_pred); } void copy_predicate_expr(Predicate * other); + Predicate * get_single_child(FuncInst * inst); ModelVector * get_children() { return &children; } Predicate * get_parent() { return parent; } Predicate * get_exit() { return exit; } -- 2.34.1