Design a method to select predicate branches based on exploration counts

diff --git a/funcinst.cc b/funcinst.cc
index 4fcf0e7cdb225e72ecb2da1c7286428bfcd90e89..44bb167e2193f411fe129a3a51c54e4127124421 100644 (file)
--- a/funcinst.cc
+++ b/funcinst.cc
@@ -4,7 +4,7 @@
 FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) :
        single_location(true),
        execution_number(model->get_execution_number()),
 FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) :
        single_location(true),
        execution_number(model->get_execution_number()),

-       marker(0)       /* The marker for FuncNode starts from 1 */
+       action_marker(0)        /* The marker for FuncNode starts from 1 */

 {
        ASSERT(act);
        ASSERT(func_node);
 {
        ASSERT(act);
        ASSERT(func_node);


@@ -50,12 +50,12 @@ bool FuncInst::add_succ(FuncInst * other)
 void FuncInst::set_associated_act(ModelAction * act, uint32_t marker)
 {
        associated_act = act;
 void FuncInst::set_associated_act(ModelAction * act, uint32_t marker)
 {
        associated_act = act;

-       this->marker = marker;
+       action_marker = marker;

 }
 
 ModelAction * FuncInst::get_associated_act(uint32_t marker)
 {
 }
 
 ModelAction * FuncInst::get_associated_act(uint32_t marker)
 {

-       if (marker == this->marker)
+       if (action_marker == marker)

                return associated_act;
        else
                return NULL;
                return associated_act;
        else
                return NULL;

diff --git a/funcinst.h b/funcinst.h
index fe4adb48313abb87ca5418628c6107c418183812..98af6bcb297a02c15fb1aa88fd3d9343bacb72b6 100644 (file)
--- a/funcinst.h
+++ b/funcinst.h
@@ -65,7 +65,7 @@ private:
        int execution_number;
 
        ModelAction * associated_act;
        int execution_number;
 
        ModelAction * associated_act;

-       uint32_t marker;
+       uint32_t action_marker;

 
        /* Currently not in use. May remove this field later
         *
 
        /* Currently not in use. May remove this field later
         *

diff --git a/funcnode.cc b/funcnode.cc
index 05974d781ad52bfac0445b3dcaeb98dfabcd990d..75cb0cb82fa1b9d4ea9e35e5f6671d0e4054f67b 100644 (file)
--- a/funcnode.cc
+++ b/funcnode.cc
@@ -306,6 +306,7 @@ void FuncNode::update_predicate_tree(action_list_t * act_list)
                        inst_id_map.put(next_inst, inst_counter++);
 
                it = it->getNext();
                        inst_id_map.put(next_inst, inst_counter++);
 
                it = it->getNext();

+               curr_pred->incr_count();

        }
 }
 
        }
 }
 

diff --git a/history.cc b/history.cc
index 4fde914419161b3697561d5f71936065c40017f8..34ec08011bfa3d60008c158e95a6f69158d3cedc 100644 (file)
--- a/history.cc
+++ b/history.cc
@@ -341,7 +341,7 @@ void ModelHistory::check_waiting_write(ModelAction * write_act)
                /* Check if the written value satisfies every predicate expression */
                for (uint i = 0; i < concrete_exprs->size(); i++) {
                        struct concrete_pred_expr concrete = (*concrete_exprs)[i];
                /* Check if the written value satisfies every predicate expression */
                for (uint i = 0; i < concrete_exprs->size(); i++) {
                        struct concrete_pred_expr concrete = (*concrete_exprs)[i];

-                       bool equality;
+                       bool equality = false;

                        switch (concrete.token) {
                                case EQUALITY:
                                        equality = (value == concrete.value);
                        switch (concrete.token) {
                                case EQUALITY:
                                        equality = (value == concrete.value);

diff --git a/newfuzzer.cc b/newfuzzer.cc
index 4863d47c765c1368a550253888f99606e64eb632..e290db4187e35e27717c3eee27290c1f38d5e368 100644 (file)
--- a/newfuzzer.cc
+++ b/newfuzzer.cc
@@ -77,6 +77,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
                        return -1;
                } else {
                        Predicate * selected_branch = get_selected_child_branch(tid);
                        return -1;
                } else {
                        Predicate * selected_branch = get_selected_child_branch(tid);

+//                     selected_branch->incr_count();

                        failed_predicates.put(selected_branch, true);
 
                        SnapVector<ModelAction *> * pruned_writes = thrd_pruned_writes[thread_id];
                        failed_predicates.put(selected_branch, true);
 
                        SnapVector<ModelAction *> * pruned_writes = thrd_pruned_writes[thread_id];


@@ -119,11 +120,16 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func
 
        ModelVector<Predicate *> * children = curr_pred->get_children();
        SnapVector<Predicate *> branches;
 
        ModelVector<Predicate *> * children = curr_pred->get_children();
        SnapVector<Predicate *> branches;

+       uint32_t numerator = 1;

 
        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);
 
        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);

+
+                       // max of (exploration counts + 1)
+                       if (child->get_count() + 1 > numerator)
+                               numerator = child->get_count() + 1;

                }
        }
 
                }
        }
 


@@ -134,13 +140,61 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func
        }
 
        // randomly select a branch
        }
 
        // randomly select a branch

-       int random_index = random() % branches.size();
-       Predicate * random_branch = branches[ random_index ];
+       // int random_index = random() % branches.size();
+       // Predicate * random_branch = branches[ random_index ];
+
+       int index = choose_index(&branches, numerator);
+       Predicate * random_branch = branches[ index ];

        thrd_selected_child_branch[thread_id] = random_branch;
 
        return random_branch;
 }
 
        thrd_selected_child_branch[thread_id] = random_branch;
 
        return random_branch;
 }
 

+/**
+ * @brief Select a branch from the given predicate branches based
+ * on their exploration counts.
+ *
+ * Let b_1, ..., b_n be branches with exploration counts c_1, ..., c_n
+ * M := max(c_1, ..., c_n) + 1
+ * Factor f_i := M / (c_i + 1)
+ * The probability p_i that branch b_i is selected:
+ *     p_i := f_i / (f_1 + ... + f_n)
+ *          = \fraction{ 1/(c_i + 1) }{ 1/(c_1 + 1) + ... + 1/(c_n + 1) }
+ *
+ * Note: (1) c_i + 1 is used because counts may be 0.
+ *      (2) The numerator of f_i is chosen to reduce the effect of underflow
+ *     
+ * @param numerator is M defined above
+ */
+int NewFuzzer::choose_index(SnapVector<Predicate *> * branches, uint32_t numerator)
+{
+       if (branches->size() == 1)
+               return 0;
+
+       double total_factor = 0;
+       SnapVector<double> factors = SnapVector<double>( branches->size() );
+       for (uint i = 0; i < branches->size(); i++) {
+               Predicate * branch = (*branches)[i];
+               double factor = (double) numerator / (branch->get_count() + 1);
+               total_factor += factor;
+               factors[i] = factor;
+       }
+
+       double prob = (double) random() / RAND_MAX;
+       double prob_sum = 0;
+       int index = 0;
+
+       for (uint i = 0; i < factors.size(); i++) {
+               prob_sum += (double) factors[i] / total_factor;
+               if (prob_sum > prob) {
+                       index = i;
+                       break;
+               }
+       }
+
+       return index;
+}
+

 Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid)
 {
        int thread_id = id_to_int(tid);
 Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid)
 {
        int thread_id = id_to_int(tid);

diff --git a/newfuzzer.h b/newfuzzer.h
index d1037a61f5481378c46d5f317d0c071ba7afdb82..a4699bdd5d394897fc7f7e286ad553111a07bf77 100644 (file)
--- a/newfuzzer.h
+++ b/newfuzzer.h
@@ -35,6 +35,7 @@ private:
 
        bool prune_writes(thread_id_t tid, Predicate * pred, SnapVector<ModelAction *> * rf_set, inst_act_map_t * inst_act_map);
        Predicate * selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst);
 
        bool prune_writes(thread_id_t tid, Predicate * pred, SnapVector<ModelAction *> * rf_set, inst_act_map_t * inst_act_map);
        Predicate * selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst);

+       int choose_index(SnapVector<Predicate *> * branches, uint32_t numerator);

 
        /* The set of Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. Only used by selectWrite.
         */
 
        /* The set of Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. Only used by selectWrite.
         */

diff --git a/predicate.cc b/predicate.cc
index 9e2f16210f2779b2d9b289840115b90bf35cbc0f..a64737e80e0dc511f93f2381583cddf207c04a86 100644 (file)
--- a/predicate.cc
+++ b/predicate.cc
@@ -6,6 +6,7 @@ Predicate::Predicate(FuncInst * func_inst, bool is_entry) :
        func_inst(func_inst),
        entry_predicate(is_entry),
        does_write(false),
        func_inst(func_inst),
        entry_predicate(is_entry),
        does_write(false),

+       exploration_count(0),

        pred_expressions(16),
        children(),
        parent(NULL),
        pred_expressions(16),
        children(),
        parent(NULL),


@@ -129,6 +130,7 @@ void Predicate::print_predicate()
        if (does_write) {
                model_print("Does write\n");
        }
        if (does_write) {
                model_print("Does write\n");
        }

+       model_print("Count: %d\n", exploration_count);

        model_print("\"];\n");
 }
 
        model_print("\"];\n");
 }
 

diff --git a/predicate.h b/predicate.h
index 4c26a9ddb8bace0986dbb54abda505d8090b3969..b85eab0d0af58f2fa342991721fc03f91e244e57 100644 (file)
--- a/predicate.h
+++ b/predicate.h
@@ -37,6 +37,9 @@ public:
 
        ConcretePredicate * evaluate(inst_act_map_t * inst_act_map, thread_id_t tid);
 
 
        ConcretePredicate * evaluate(inst_act_map_t * inst_act_map, thread_id_t tid);
 

+       uint32_t get_count() { return exploration_count; }
+       void incr_count() { exploration_count++; }
+

        void print_predicate();
        void print_pred_subtree();
 
        void print_predicate();
        void print_pred_subtree();
 


@@ -45,6 +48,7 @@ private:
        FuncInst * func_inst;
        bool entry_predicate;
        bool does_write;
        FuncInst * func_inst;
        bool entry_predicate;
        bool does_write;

+       uint32_t exploration_count;

 
        /* May have multiple predicate expressions */
        PredExprSet pred_expressions;
 
        /* May have multiple predicate expressions */
        PredExprSet pred_expressions;