Fix NewFuzzer::selectWrite - check back edges
authorweiyu <weiyuluo1232@gmail.com>
Wed, 4 Dec 2019 20:29:02 +0000 (12:29 -0800)
committerweiyu <weiyuluo1232@gmail.com>
Wed, 4 Dec 2019 20:29:02 +0000 (12:29 -0800)
cmodelint.cc
execution.cc
fuzzer.h
history.cc
newfuzzer.cc
newfuzzer.h
predicate.cc
predicate.h

index 1a03153..ea34324 100644 (file)
@@ -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<const char *> * 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<const char *> * 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());
 }
index 6057ec5..21207fe 100644 (file)
@@ -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<ModelAction *> *
        }
 
        // 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);
index c5248d7..d31c226 100644 (file)
--- 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:
 };
index e48f1c8..03515b5 100644 (file)
@@ -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);
        }
 }
 
index c7d70ac..4d6a296 100644 (file)
@@ -33,7 +33,7 @@ void NewFuzzer::register_engine(ModelHistory * history, ModelExecution *executio
 
 int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * 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<ModelAction *> * 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<ModelAction *> * rf_set
        return random_index;
 }
 
-void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_inst,
-                                                                                                                                                        inst_act_map_t * inst_act_map, SnapVector<ModelAction *> * 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<ModelAction *> * rf_set)
 {
        ASSERT(!rf_set->empty());
        if (curr_pred == NULL || read_inst == NULL)
-               return;
+               return false;
 
        ModelVector<Predicate *> * 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<Predicate *> * children = curr_pred->get_children();
        SnapVector<Predicate *> 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<ModelAction *> * rf_set, inst_act_map_t * inst_act_map)
+SnapVector<ModelAction *> * 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)
index 76f13ce..9f30ec6 100644 (file)
@@ -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<Predicate *> thrd_selected_child_branch;
        SnapVector< SnapVector<ModelAction *> *> thrd_pruned_writes;
 
-       void check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, inst_act_map_t * inst_act_map, SnapVector<ModelAction *> * rf_set);
+       bool check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, inst_act_map_t * inst_act_map, SnapVector<ModelAction *> * 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<ModelAction *> * rf_set, inst_act_map_t * inst_act_map);
        int choose_index(SnapVector<Predicate *> * branches, uint32_t numerator);
 
index 1fd1d94..7fec1a4 100644 (file)
@@ -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)
 {
index 2fdd6c5..11f4624 100644 (file)
@@ -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<Predicate *> * get_children() { return &children; }
        Predicate * get_parent() { return parent; }
        Predicate * get_exit() { return exit; }