move codes around in history.cc, and NewFuzzer::selectWrite is half working
authorweiyu <weiyuluo1232@gmail.com>
Wed, 28 Aug 2019 22:27:43 +0000 (15:27 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Wed, 28 Aug 2019 22:27:43 +0000 (15:27 -0700)
fuzzer.h
history.cc
newfuzzer.cc
newfuzzer.h

index d291268..56e40a9 100644 (file)
--- a/fuzzer.h
+++ b/fuzzer.h
@@ -3,16 +3,18 @@
 #include "classlist.h"
 #include "mymemory.h"
 #include "stl-model.h"
+#include "threads-model.h"
 
 class Fuzzer {
 public:
        Fuzzer() {}
        virtual int selectWrite(ModelAction *read, SnapVector<ModelAction *>* rf_set);
+       virtual Predicate * get_selected_child_branch(thread_id_t tid) = 0;
        Thread * selectThread(int * threadlist, int numthreads);
        Thread * selectNotify(action_list_t * waiters);
        bool shouldSleep(const ModelAction *sleep);
        bool shouldWake(const ModelAction *sleep);
-       virtual void register_engine(ModelHistory * history, ModelExecution * execution) {}
+       virtual void register_engine(ModelHistory * history, ModelExecution * execution) = 0;
        MEMALLOC
 private:
 };
index b546cd0..9bd78d6 100644 (file)
@@ -6,7 +6,7 @@
 
 #include "model.h"
 #include "execution.h"
-
+#include "newfuzzer.h"
 
 /** @brief Constructor */
 ModelHistory::ModelHistory() :
@@ -51,6 +51,7 @@ 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);
 }
 
 /* @param func_id a non-zero value */
@@ -66,7 +67,8 @@ void ModelHistory::exit_function(const uint32_t func_id, thread_id_t tid)
 
        if (last_func_id == func_id) {
                FuncNode * func_node = func_nodes[func_id];
-               func_node->unset_predicate_tree_position(tid);
+               func_node->set_predicate_tree_position(tid, NULL);
+               func_node->reset_inst_act_map(tid);
                //func_node->clear_read_map(tid);
 
                action_list_t * curr_act_list = func_act_lists->back();
@@ -149,30 +151,36 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
        if (func_id == 0 || act->get_position() == NULL)
                return;
 
+       bool second_part_of_rmw = act->is_rmwc() || act->is_rmw();
+
+       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 second part of a read modify write or actions with the same sequence number
+       if (second_part_of_rmw ||
+               (last_act != NULL && last_act->get_seq_number() == act->get_seq_number()) )
+               return;
+
        if ( func_nodes.size() <= func_id )
                resize_func_nodes( func_id + 1 );
 
        FuncNode * func_node = func_nodes[func_id];
 
-//     if (act->is_read())
-//             func_node->store_read(act, tid);
-
        /* add to curr_inst_list */
-       bool second_part_of_rmw = act->is_rmwc() || act->is_rmw();
-       if (!second_part_of_rmw) {
-               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();
+       curr_act_list->push_back(act);
+       func_node->add_inst(act);
 
-               // do not add actions with the same sequence number twice
-               if (last_act != NULL && last_act->get_seq_number() == act->get_seq_number())
-                       return;
+       if (act->is_read()) {
+               func_node->update_inst_act_map(tid, act);
 
-               curr_act_list->push_back(act);
-               func_node->add_inst(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);
+               //func_node->store_read(act, tid);
        }
 }
 
index df3f2ca..8bef9cc 100644 (file)
@@ -5,6 +5,8 @@
 #include "execution.h"
 #include "funcnode.h"
 
+typedef HashTable<FuncInst *, ModelAction *, uintptr_t, 0> inst_act_map_t;
+
 NewFuzzer::NewFuzzer() :
        thrd_last_read_act(),
        thrd_curr_pred(),
@@ -30,14 +32,15 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
        if (thrd_last_read_act.size() <= (uint) thread_id)
                thrd_last_read_act.resize(thread_id + 1);
 
+       SnapVector<func_id_list_t> * thrd_func_list = execution->get_thrd_func_list();
+       uint32_t func_id = (*thrd_func_list)[thread_id].back();
+       FuncNode * func_node = history->get_func_node(func_id);
+       inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid);
+
        // A new read action is encountered, select a random child branch of current predicate
        if (read != thrd_last_read_act[thread_id]) {
                thrd_last_read_act[thread_id] = read;
 
-               SnapVector<func_id_list_t> * thrd_func_list = execution->get_thrd_func_list();
-               uint32_t func_id = (*thrd_func_list)[thread_id].back();
-
-               FuncNode * func_node = history->get_func_node(func_id);
                FuncInst * read_inst = func_node->get_inst(read);
                Predicate * curr_pred = func_node->get_predicate_tree_position(tid);
                selectBranch(thread_id, curr_pred, read_inst);
@@ -47,38 +50,67 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
        if (selected_branch == NULL)
                return random_index;
 
-       FuncInst * read_inst = selected_branch->get_func_inst();
        PredExprSet * pred_expressions = selected_branch->get_pred_expressions();
 
-       model_print("thread %d ", tid);
-       read_inst->print();
+//     FuncInst * read_inst = selected_branch->get_func_inst();
+//     model_print("thread %d ", tid);
+//     read_inst->print();
 
        // unset predicates
        if (pred_expressions->getSize() == 0)
                return random_index;
-/*
-       PredExprSetIter * pred_expr_it = pred_expressions->iterator();
-       while (pred_expr_it->hasNext()) {
-               struct pred_expr * expression = pred_expr_it->next();
-
-               switch(expression->token) {
-                       case NOPREDICATE:
-                               read_inst->print();
-                               read->print();
-                               model_print("no predicate\n");
+
+       for (uint index = 0; index < rf_set->size(); index++) {
+               ModelAction * write_act = (*rf_set)[index];
+               bool satisfy_predicate = true;
+
+               PredExprSetIter * pred_expr_it = pred_expressions->iterator();
+               while (pred_expr_it->hasNext()) {
+                       struct pred_expr * expression = pred_expr_it->next();
+                       uint64_t last_read, write_val;
+                       bool equality;
+
+                       if (expression->token == NOPREDICATE)
                                return random_index;
-                       case EQUALITY:
-                               model_print("equality predicate, under construction\n");
-                               break;
-                       case NULLITY:
-                               model_print("nullity predicate, under construction\n");
-                               break;
-                       default:
-                               model_print("unknown predicate token\n");
+
+                       switch(expression->token) {
+                               case EQUALITY:
+                                       FuncInst * to_be_compared;
+                                       ModelAction * last_act;
+
+                                       to_be_compared = expression->func_inst;
+                                       last_act = inst_act_map->get(to_be_compared);
+
+                                       last_read = last_act->get_reads_from_value();
+                                       write_val = write_act->get_write_value();
+
+                                       equality = (last_read == write_val);
+                                       if (equality != expression->value)
+                                               satisfy_predicate = false;
+
+                                       model_print("equality predicate\n");
+                                       break;
+                               case NULLITY:
+                                       model_print("nullity predicate, under construction\n");
+                                       break;
+                               default:
+                                       model_print("unknown predicate token\n");
+                                       break;
+                       }
+
+                       if (!satisfy_predicate)
                                break;
                }
+
+               /* TODO: collect all writes that satisfy predicate; if some of them violate
+                * modification graph, others can be chosen */
+               if (satisfy_predicate) {
+                       model_print("^_^ satisfy predicate\n");
+                       return index;
+               }
        }
-*/
+
+       // TODO: make this thread sleep if no write satisfies the chosen predicate
        return random_index;
 }
 
@@ -87,7 +119,7 @@ void NewFuzzer::selectBranch(int thread_id, Predicate * curr_pred, FuncInst * re
        if ( thrd_selected_child_branch.size() <= (uint) thread_id)
                thrd_selected_child_branch.resize(thread_id + 1);
 
-       if (read_inst == NULL) {
+       if (curr_pred == NULL || read_inst == NULL) {
                thrd_selected_child_branch[thread_id] = NULL;
                return;
        }
@@ -112,3 +144,12 @@ void NewFuzzer::selectBranch(int thread_id, Predicate * curr_pred, FuncInst * re
        Predicate * random_branch = branches[ random_index ];
        thrd_selected_child_branch[thread_id] = random_branch;
 }
+
+Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid)
+{
+       int thread_id = id_to_int(tid);
+       if (thrd_selected_child_branch.size() <= (uint) thread_id)
+               return NULL;
+
+       return thrd_selected_child_branch[thread_id];
+}
index 153c150..c70960e 100644 (file)
@@ -11,6 +11,7 @@ public:
        NewFuzzer();
        int selectWrite(ModelAction *read, SnapVector<ModelAction *>* rf_set);
        void selectBranch(int thread_id, Predicate * curr_pred, FuncInst * read_inst);
+       Predicate * get_selected_child_branch(thread_id_t tid);
 
        Thread * selectThread(int * threadlist, int numthreads);
        Thread * selectNotify(action_list_t * waiters);