Notify threads paused by the Fuzzer when the desired write is available
authorweiyu <weiyuluo1232@gmail.com>
Tue, 1 Oct 2019 02:28:24 +0000 (19:28 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Tue, 1 Oct 2019 02:28:24 +0000 (19:28 -0700)
concretepredicate.h
fuzzer.h
history.cc
history.h
newfuzzer.cc
newfuzzer.h

index 6319a2e..f0eaeea 100644 (file)
@@ -13,7 +13,9 @@ public:
 
        void add_expression(token_t token, uint64_t value, bool equality);
        SnapVector<struct concrete_pred_expr> * getExpressions() { return &expressions; }
+       void set_location(void * loc) { location = loc; }
        void * get_location() { return location; }
+       thread_id_t get_tid() { return tid; }
 
        SNAPSHOTALLOC
 private:
index 64875f2..0d5734d 100644 (file)
--- a/fuzzer.h
+++ b/fuzzer.h
@@ -11,7 +11,9 @@ public:
        virtual int selectWrite(ModelAction *read, SnapVector<ModelAction *>* rf_set);
        virtual Predicate * get_selected_child_branch(thread_id_t tid) = 0;
        virtual bool has_paused_threads() { return false; }
+       virtual void notify_paused_thread(Thread * thread) = 0;
        virtual Thread * selectThread(int * threadlist, int numthreads);
+
        Thread * selectNotify(action_list_t * waiters);
        bool shouldSleep(const ModelAction *sleep);
        bool shouldWake(const ModelAction *sleep);
index 4b03e7f..2435018 100644 (file)
@@ -4,6 +4,7 @@
 #include "funcnode.h"
 #include "funcinst.h"
 #include "common.h"
+#include "concretepredicate.h"
 
 #include "model.h"
 #include "execution.h"
@@ -17,7 +18,10 @@ ModelHistory::ModelHistory() :
        func_nodes(),
        write_history(),                // snapshot data structure
        loc_func_nodes_map(),           // shapshot data structure
-       thrd_last_entered_func()        // snapshot data structure
+       loc_wr_func_nodes_map(),        // shapshot data structure
+       thrd_last_entered_func(),       // snapshot data structure
+       loc_waiting_writes_map(),       // snapshot data structure
+       thrd_waiting_write()            // snapshot data structure
 {}
 
 void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
@@ -156,6 +160,8 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
                                func_node->add_to_val_loc_map(value, location);
                        }
                }
+
+               check_waiting_write(act);
        }
 
        /* the following does not care about actions without a position */
@@ -195,7 +201,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
        }
 }
 
-/* return the FuncNode given its func_id  */
+/* Return the FuncNode given its func_id  */
 FuncNode * ModelHistory::get_func_node(uint32_t func_id)
 {
        if (func_nodes.size() <= func_id)       // this node has not been added to func_nodes
@@ -204,6 +210,17 @@ FuncNode * ModelHistory::get_func_node(uint32_t func_id)
        return func_nodes[func_id];
 }
 
+/* Return the current FuncNode when given a thread id */
+FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid)
+{
+       int thread_id = id_to_int(tid);
+       SnapVector<func_id_list_t> * thrd_func_list =  model->get_execution()->get_thrd_func_list();
+       uint32_t func_id = (*thrd_func_list)[thread_id].back();
+       FuncNode * func_node = func_nodes[func_id];
+
+       return func_node;
+}
+
 void ModelHistory::update_write_history(void * location, uint64_t write_val)
 {
        value_set_t * write_set = write_history.get(location);
@@ -238,6 +255,106 @@ void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node
        func_node_list->push_back(node);
 }
 
+/* When a thread is paused by Fuzzer, keep track of the condition it is waiting for */
+void ModelHistory::add_waiting_write(ConcretePredicate * concrete)
+{
+       void * location = concrete->get_location();
+       SnapVector<ConcretePredicate *> * waiting_conditions = loc_waiting_writes_map.get(location);
+       if (waiting_conditions == NULL) {
+               waiting_conditions = new SnapVector<ConcretePredicate *>();
+               loc_waiting_writes_map.put(location, waiting_conditions);
+       }
+
+       /* waiting_conditions should not have duplications */
+       waiting_conditions->push_back(concrete);
+
+       int thread_id = id_to_int(concrete->get_tid());
+       int oldsize = thrd_waiting_write.size();
+
+       if (oldsize <= thread_id) {
+               for (int i = oldsize; i < thread_id + 1; i++)
+                       thrd_waiting_write.resize(thread_id + 1);
+       }
+
+       thrd_waiting_write[thread_id] = concrete;
+}
+
+void ModelHistory::remove_waiting_write(thread_id_t tid)
+{
+       ConcretePredicate * concrete = thrd_waiting_write[ id_to_int(tid) ];
+       void * location = concrete->get_location();
+       SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map.get(location);
+
+       for (uint i = 0; i < concrete_preds->size(); i++) {
+               ConcretePredicate * current = (*concrete_preds)[i];
+               if (concrete == current) {
+                       (*concrete_preds)[i] = concrete_preds->back();
+                       concrete_preds->pop_back();
+                       break;
+               }
+       }
+
+       int thread_id = id_to_int( concrete->get_tid() );
+       thrd_waiting_write[thread_id] = NULL;
+       delete concrete;
+}
+
+/* Check if any other thread is waiting for this write action. If so, wake them up */
+void ModelHistory::check_waiting_write(ModelAction * write_act)
+{
+       void * location = write_act->get_location();
+       uint64_t value = write_act->get_write_value();
+       SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map.get(location);
+       SnapVector<ConcretePredicate *> to_remove = SnapVector<ConcretePredicate *>();
+       if (concrete_preds == NULL)
+               return;
+
+       uint index = 0;
+       while (index < concrete_preds->size()) {
+               ConcretePredicate * concrete_pred = (*concrete_preds)[index];
+               SnapVector<struct concrete_pred_expr> * concrete_exprs = concrete_pred->getExpressions();
+               bool satisfy_predicate = true;
+               /* 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;
+                       switch (concrete.token) {
+                               case EQUALITY:
+                                       equality = (value == concrete.value);
+                                       break;
+                               case NULLITY:
+                                       equality = ((void*)value == NULL);
+                                       break;
+                               default:
+                                       model_print("unknown predicate token");
+                                       break;
+                       }
+
+                       if (equality != concrete.equality) {
+                               satisfy_predicate = false;
+                               break;
+                       }
+               }
+
+               if (satisfy_predicate) {
+                       to_remove.push_back(concrete_pred);
+               }
+
+               index++;
+       }
+
+       for (uint i = 0; i < to_remove.size(); i++) {
+               ConcretePredicate * concrete_pred = to_remove[i];
+
+               /* Wake up threads */
+               thread_id_t tid = concrete_pred->get_tid();
+               Thread * thread = model->get_thread(tid);
+
+               model_print("** thread %d is woken up\n", thread->get_id());
+               model->get_execution()->getFuzzer()->notify_paused_thread(thread);
+       }
+}
+
 /* Reallocate some snapshotted memories when new executions start */
 void ModelHistory::set_new_exec_flag()
 {
index 51f2630..5a3657c 100644 (file)
--- a/history.h
+++ b/history.h
@@ -26,12 +26,18 @@ public:
 
        ModelVector<FuncNode *> * getFuncNodes() { return &func_nodes; }
        FuncNode * get_func_node(uint32_t func_id);
+       FuncNode * get_curr_func_node(thread_id_t tid);
 
        void update_write_history(void * location, uint64_t write_val);
        HashTable<void *, value_set_t *, uintptr_t, 4> * getWriteHistory() { return &write_history; }
        void update_loc_func_nodes_map(void * location, FuncNode * node);
        void update_loc_wr_func_nodes_map(void * location, FuncNode * node);
 
+       void add_waiting_write(ConcretePredicate * concrete);
+       void remove_waiting_write(thread_id_t tid);
+       void check_waiting_write(ModelAction * write_act);
+       SnapVector<ConcretePredicate *> * getThrdWaitingWrite() { return &thrd_waiting_write; }
+
        void set_new_exec_flag();
        void dump_func_node_graph();
        void print_func_node();
@@ -59,6 +65,9 @@ private:
 
        /* Keeps track of the last function entered by each thread */
        SnapVector<uint32_t> thrd_last_entered_func;
+
+       HashTable<void *, SnapVector<ConcretePredicate *> *, uintptr_t, 4> loc_waiting_writes_map;
+       SnapVector<ConcretePredicate *> thrd_waiting_write;
 };
 
 #endif /* __HISTORY_H__ */
index d581421..00219b6 100644 (file)
@@ -16,7 +16,8 @@ NewFuzzer::NewFuzzer() :
        thrd_curr_pred(),
        thrd_selected_child_branch(),
        thrd_pruned_writes(),
-       paused_thread_set()
+       paused_thread_set(),
+       paused_thread_table(128)
 {}
 
 /**
@@ -42,9 +43,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
        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);
+               FuncNode * func_node = history->get_curr_func_node(tid);
                inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid);
                Predicate * curr_pred = func_node->get_predicate_tree_position(tid);
                FuncInst * read_inst = func_node->get_inst(read);
@@ -53,7 +52,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * rf_set
                prune_writes(tid, selected_branch, rf_set, inst_act_map);
        }
 
-       // No write satisfies the selected predicate
+       // No write satisfies the selected predicate, so pause this thread.
        if ( rf_set->size() == 0 ) {
                Thread * read_thread = execution->get_thread(tid);
                model_print("the %d read action of thread %d is unsuccessful\n", read->get_seq_number(), read_thread->get_id());
@@ -198,6 +197,8 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred,
                        index++;
        }
 
+       delete concrete_pred;
+
        return pruned;
 }
 
@@ -207,8 +208,23 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred,
  */
 void NewFuzzer::conditional_sleep(Thread * thread)
 {
+       int index = paused_thread_set.size();
+
        model->getScheduler()->add_sleep(thread);
        paused_thread_set.push_back(thread);
+       paused_thread_table.put(thread, index); // Update table
+
+       /*  */
+       ModelAction * read = thread->get_pending();
+       thread_id_t tid = thread->get_id();
+       FuncNode * func_node = history->get_curr_func_node(tid);
+       inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid);
+
+       Predicate * selected_branch = get_selected_child_branch(tid);
+       ConcretePredicate * concrete = selected_branch->evaluate(inst_act_map, tid);
+       concrete->set_location(read->get_location());
+
+       history->add_waiting_write(concrete);
 }
 
 bool NewFuzzer::has_paused_threads()
@@ -230,25 +246,45 @@ Thread * NewFuzzer::selectThread(int * threadlist, int numthreads)
        return model->get_thread(curr_tid);
 }
 
-/* Force waking up one of threads paused by Fuzzer */
+/* Force waking up one of threads paused by Fuzzer, because otherwise
+ * the Fuzzer is not making progress
+ */
 void NewFuzzer::wake_up_paused_threads(int * threadlist, int * numthreads)
 {
        int random_index = random() % paused_thread_set.size();
        Thread * thread = paused_thread_set[random_index];
        model->getScheduler()->remove_sleep(thread);
 
-       paused_thread_set[random_index] = paused_thread_set.back();
+       Thread * last_thread = paused_thread_set.back();
+       paused_thread_set[random_index] = last_thread;
        paused_thread_set.pop_back();
+       paused_thread_table.put(last_thread, random_index);     // Update table
+       paused_thread_table.remove(thread);
 
-       model_print("thread %d is woken up\n", thread->get_id());
-       threadlist[*numthreads] = thread->get_id();
+       thread_id_t tid = thread->get_id();
+       history->remove_waiting_write(tid);
+
+       model_print("thread %d is woken up\n", tid);
+       threadlist[*numthreads] = tid;
        (*numthreads)++;
 }
 
-/* Notify one of conditional sleeping threads if the desired write is available */
-bool NewFuzzer::notify_conditional_sleep(Thread * thread)
+/* Wake up conditional sleeping threads if the desired write is available */
+void NewFuzzer::notify_paused_thread(Thread * thread)
 {
-       
+       ASSERT(paused_thread_table.contains(thread));
+
+       int index = paused_thread_table.get(thread);
+       model->getScheduler()->remove_sleep(thread);
+
+       Thread * last_thread = paused_thread_set.back();
+       paused_thread_set[index] = last_thread;
+       paused_thread_set.pop_back();
+       paused_thread_table.put(last_thread, index);    // Update table
+       paused_thread_table.remove(thread);
+
+       thread_id_t tid = thread->get_id();
+       history->remove_waiting_write(tid);
 }
 
 bool NewFuzzer::shouldWait(const ModelAction * act)
index d6fa3a4..c152c5d 100644 (file)
@@ -12,6 +12,7 @@ public:
        int selectWrite(ModelAction *read, SnapVector<ModelAction *>* rf_set);
        Predicate * get_selected_child_branch(thread_id_t tid);
        bool has_paused_threads();
+       void notify_paused_thread(Thread * thread);
 
        Thread * selectThread(int * threadlist, int numthreads);
        Thread * selectNotify(action_list_t * waiters);
@@ -34,14 +35,13 @@ 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);
 
-       /* 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.
         */
        SnapVector<Thread *> paused_thread_set;
+       HashTable<Thread *, int, uintptr_t, 0> paused_thread_table;
 
        void conditional_sleep(Thread * thread);
        void wake_up_paused_threads(int * threadlist, int * numthreads);
-       bool notify_conditional_sleep(Thread * thread);
 };
 
 #endif /* end of __NEWFUZZER_H__ */