Add sleep score

[c11tester.git] / newfuzzer.cc

diff --git a/newfuzzer.cc b/newfuzzer.cc
index e290db4187e35e27717c3eee27290c1f38d5e368..1d373e8572c1bdd0ccdb80eaeb37d35120f09d58 100644 (file)
--- a/newfuzzer.cc
+++ b/newfuzzer.cc
@@ -47,6 +47,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
        if (read != thrd_last_read_act[thread_id]) {
                FuncNode * func_node = history->get_curr_func_node(tid);
                Predicate * curr_pred = func_node->get_predicate_tree_position(tid);
+
                FuncInst * read_inst = func_node->get_inst(read);
                Predicate * selected_branch = selectBranch(tid, curr_pred, read_inst);
 
@@ -72,13 +73,11 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
                        execution->restore_last_seq_num();
 
                        conditional_sleep(read_thread);
-
                        // Returning -1 stops the while loop of ModelExecution::process_read
                        return -1;
                } else {
                        Predicate * selected_branch = get_selected_child_branch(tid);
-//                     selected_branch->incr_count();
-                       failed_predicates.put(selected_branch, true);
+                       update_predicate_score(selected_branch, 1);
 
                        SnapVector<ModelAction *> * pruned_writes = thrd_pruned_writes[thread_id];
                        for (uint i = 0; i < pruned_writes->size(); i++) {
@@ -128,8 +127,8 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func
                        branches.push_back(child);
 
                        // max of (exploration counts + 1)
-                       if (child->get_count() + 1 > numerator)
-                               numerator = child->get_count() + 1;
+                       if (child->get_expl_count() + 1 > numerator)
+                               numerator = child->get_expl_count() + 1;
                }
        }
 
@@ -147,6 +146,10 @@ 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;
 }
 
@@ -172,12 +175,12 @@ int NewFuzzer::choose_index(SnapVector<Predicate *> * branches, uint32_t numerat
                return 0;
 
        double total_factor = 0;
-       SnapVector<double> factors = SnapVector<double>( branches->size() );
+       SnapVector<double> factors = SnapVector<double>( branches->size() + 1 );
        for (uint i = 0; i < branches->size(); i++) {
                Predicate * branch = (*branches)[i];
-               double factor = (double) numerator / (branch->get_count() + 1);
+               double factor = (double) numerator / (branch->get_expl_count() + 5 * branch->get_fail_count() + 1);
                total_factor += factor;
-               factors[i] = factor;
+               factors.push_back(factor);
        }
 
        double prob = (double) random() / RAND_MAX;
@@ -185,9 +188,9 @@ int NewFuzzer::choose_index(SnapVector<Predicate *> * branches, uint32_t numerat
        int index = 0;
 
        for (uint i = 0; i < factors.size(); i++) {
-               prob_sum += (double) factors[i] / total_factor;
+               index = i;
+               prob_sum += (double) (factors[i] / total_factor);
                if (prob_sum > prob) {
-                       index = i;
                        break;
                }
        }
@@ -349,9 +352,13 @@ void NewFuzzer::wake_up_paused_threads(int * threadlist, int * numthreads)
        history->remove_waiting_write(tid);
        history->remove_waiting_thread(tid);
 
-       //model_print("thread %d is woken up\n", tid);
        threadlist[*numthreads] = tid;
        (*numthreads)++;
+
+       Predicate * selected_branch = get_selected_child_branch(tid);
+       update_predicate_score(selected_branch, 3);
+
+       model_print("thread %d is woken up\n", tid);
 }
 
 /* Wake up conditional sleeping threads if the desired write is available */
@@ -371,6 +378,11 @@ void NewFuzzer::notify_paused_thread(Thread * thread)
        thread_id_t tid = thread->get_id();
        history->remove_waiting_write(tid);
        history->remove_waiting_thread(tid);
+
+       Predicate * selected_branch = get_selected_child_branch(tid);
+       update_predicate_score(selected_branch, 4);
+
+       model_print("** thread %d is woken up\n", tid);
 }
 
 /* Find threads that may write values that the pending read action is waiting for
@@ -409,6 +421,33 @@ bool NewFuzzer::find_threads(ModelAction * pending_read)
        return finds_waiting_for;
 }
 
+/* Update predicate counts and scores (asynchronous) when the read value is not available
+ *
+ * @param type
+ *        type 1: find_threads return false
+ *        type 2: find_threads return true, but the fuzzer decides that that thread shall not sleep based on sleep score
+ *        type 3: threads are put to sleep but woken up before the waited value appears
+ *        type 4: threads are put to sleep and the waited vaule appears (success)
+ */
+void NewFuzzer::update_predicate_score(Predicate * predicate, int type)
+{
+       switch (type) {
+               case 1:
+                       predicate->incr_fail_count();
+
+                       /* Do not choose this predicate when reselecting a new branch */
+                       failed_predicates.put(predicate, true);
+               case 2:
+                       predicate->incr_fail_count();
+                       predicate->decr_sleep_score(1);
+               case 3:
+                       predicate->incr_fail_count();
+                       predicate->incr_sleep_score(10);
+               case 4:
+                       predicate->decr_sleep_score(10);
+       }
+}
+
 bool NewFuzzer::shouldWait(const ModelAction * act)
 {
        return random() & 1;