Create WaitObj to store information about which thread is waiting for whom and is...
authorweiyu <weiyuluo1232@gmail.com>
Sat, 5 Oct 2019 01:39:15 +0000 (18:39 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Sat, 5 Oct 2019 01:39:15 +0000 (18:39 -0700)
Makefile
classlist.h
history.cc
history.h
newfuzzer.cc
waitobj.cc [new file with mode: 0644]
waitobj.h [new file with mode: 0644]

index 6a57d4a..f9d3424 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@ OBJECTS := libthreads.o schedule.o model.o threads.o librace.o action.o \
           snapshot.o malloc.o mymemory.o common.o mutex.o conditionvariable.o \
           context.o execution.o libannotate.o plugins.o pthread.o futex.o fuzzer.o \
           sleeps.o history.o funcnode.o funcinst.o predicate.o printf.o newfuzzer.o \
-          concretepredicate.o
+          concretepredicate.o waitobj.o
 
 CPPFLAGS += -Iinclude -I.
 LDFLAGS := -ldl -lrt -rdynamic -lpthread
index 4cd97b3..bebbf39 100644 (file)
@@ -3,6 +3,7 @@
 #include <inttypes.h>
 #include "stl-model.h"
 #include "hashset.h"
+#include "modeltypes.h"
 
 class ClockVector;
 class CycleGraph;
@@ -20,9 +21,11 @@ class FuncNode;
 class FuncInst;
 class Predicate;
 class ConcretePredicate;
+class WaitObj;
 
 struct model_snapshot_members;
 struct bug_message;
+
 typedef SnapList<ModelAction *> action_list_t;
 typedef SnapList<uint32_t> func_id_list_t;
 typedef SnapList<FuncInst *> func_inst_list_t;
@@ -35,6 +38,8 @@ typedef HashSet<uint64_t, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapsho
 typedef HSIterator<uint64_t, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free> value_set_iter;
 typedef HashSet<void *, uintptr_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free> loc_set_t;
 typedef HSIterator<void *, uintptr_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free> loc_set_iter;
+typedef HashSet<thread_id_t, int, 0> thrd_id_set_t;
+typedef HSIterator<thread_id_t, int, 0> thrd_id_set_iter;
 
 extern volatile int modellock;
 #endif
index c3e7eeb..8682da3 100644 (file)
@@ -5,6 +5,7 @@
 #include "funcinst.h"
 #include "common.h"
 #include "concretepredicate.h"
+#include "waitobj.h"
 
 #include "model.h"
 #include "execution.h"
@@ -23,6 +24,7 @@ ModelHistory::ModelHistory() :
        loc_wr_func_nodes_map = new HashTable<void *, SnapVector<FuncNode *> *, uintptr_t, 0>();
        loc_waiting_writes_map = new HashTable<void *, SnapVector<ConcretePredicate *> *, uintptr_t, 0>();
        thrd_waiting_write = new SnapVector<ConcretePredicate *>();
+       thrd_wait_obj = new SnapVector<WaitObj *>();
        func_inst_act_maps = new HashTable<uint32_t, SnapVector<inst_act_map_t *> *, int, 0>(128);
 }
 
@@ -290,6 +292,8 @@ void ModelHistory::remove_waiting_write(thread_id_t tid)
        void * location = concrete->get_location();
        SnapVector<ConcretePredicate *> * concrete_preds = loc_waiting_writes_map->get(location);
 
+       /* Linear search should be fine because presumably not many ConcretePredicates
+        * are at the same memory location */
        for (uint i = 0; i < concrete_preds->size(); i++) {
                ConcretePredicate * current = (*concrete_preds)[i];
                if (concrete == current) {
@@ -360,6 +364,20 @@ void ModelHistory::check_waiting_write(ModelAction * write_act)
        }
 }
 
+WaitObj * ModelHistory::getWaitObj(thread_id_t tid)
+{
+       int thread_id = id_to_int(tid);
+       int old_size = thrd_wait_obj->size();
+       if (old_size <= thread_id) {
+               thrd_wait_obj->resize(thread_id + 1);
+               for (int i = old_size; i < thread_id + 1; i++) {
+                       (*thrd_wait_obj)[i] = new WaitObj( int_to_id(i) );
+               }
+       }
+
+       return (*thrd_wait_obj)[thread_id];
+}
+
 SnapVector<inst_act_map_t *> * ModelHistory::getThrdInstActMap(uint32_t func_id)
 {
        ASSERT(func_id != 0);
@@ -438,3 +456,14 @@ void ModelHistory::print_func_node()
                }
        }
 }
+
+void ModelHistory::print_waiting_threads()
+{
+       ModelExecution * execution = model->get_execution();
+       for (unsigned int i = 0; i < execution->get_num_threads();i++) {
+               thread_id_t tid = int_to_id(i);
+               WaitObj * wait_obj = getWaitObj(tid);
+               wait_obj->print_waiting_for();
+               wait_obj->print_waited_by();
+       }
+}
index 2ce88f2..2cf93f8 100644 (file)
--- a/history.h
+++ b/history.h
@@ -1,7 +1,6 @@
 #ifndef __HISTORY_H__
 #define __HISTORY_H__
 
-#include "stl-model.h"
 #include "common.h"
 #include "classlist.h"
 #include "hashtable.h"
@@ -39,12 +38,15 @@ public:
        void remove_waiting_write(thread_id_t tid);
        void check_waiting_write(ModelAction * write_act);
        SnapVector<ConcretePredicate *> * getThrdWaitingWrite() { return thrd_waiting_write; }
+       thrd_id_set_t * getWaitingFor(thread_id_t tid);
+       WaitObj * getWaitObj(thread_id_t tid);
 
        SnapVector<inst_act_map_t *> * getThrdInstActMap(uint32_t func_id);
 
        void set_new_exec_flag();
        void dump_func_node_graph();
        void print_func_node();
+       void print_waiting_threads();
 
        MEMALLOC
 private:
@@ -68,9 +70,11 @@ private:
        HashTable<void *, SnapVector<FuncNode *> *, uintptr_t, 0> * loc_wr_func_nodes_map;
 
        HashTable<void *, SnapVector<ConcretePredicate *> *, uintptr_t, 0> * loc_waiting_writes_map;
+       /* The write values each paused thread is waiting for */
        SnapVector<ConcretePredicate *> * thrd_waiting_write;
+       SnapVector<WaitObj *> * thrd_wait_obj;
 
-       /* A run-time map from FuncInst to ModelAction per each FuncNode, per each thread.
+       /* A run-time map from FuncInst to ModelAction per each thread, per each FuncNode.
         * Manipulated by FuncNode, and needed by NewFuzzer */
        HashTable<uint32_t, SnapVector<inst_act_map_t *> *, int, 0> * func_inst_act_maps;
 
index b0874c8..490ce04 100644 (file)
@@ -6,6 +6,7 @@
 #include "funcinst.h"
 #include "predicate.h"
 #include "concretepredicate.h"
+#include "waitobj.h"
 
 #include "model.h"
 #include "schedule.h"
@@ -294,25 +295,41 @@ void NewFuzzer::find_threads(ModelAction * pending_read)
 {
        void * location = pending_read->get_location();
        thread_id_t self_id = pending_read->get_tid();
+       HashSet<thread_id_t, int, 0> waiting_for_threads(64);
 
        SnapVector<FuncNode *> * func_node_list = history->getWrFuncNodes(location);
        for (uint i = 0; i < func_node_list->size(); i++) {
                FuncNode * target_node = (*func_node_list)[i];
-               model_print("node %s may write to loc %p\n", target_node->get_func_name(), location);
-
                for (uint i = 1; i < execution->get_num_threads(); i++) {
                        thread_id_t tid = int_to_id(i);
                        if (tid == self_id)
                                continue;
 
                        FuncNode * node = history->get_curr_func_node(tid);
+                       /* It is possible that thread tid is not in any FuncNode */
                        if (node == NULL)
                                continue;
 
                        int distance = node->compute_distance(target_node);
-                       model_print("thread: %d; distance from node %d to node %d: %d\n", tid, node->get_func_id(), target_node->get_func_id(), distance);
+                       if (distance != -1) {
+                               waiting_for_threads.add(tid);
+                               model_print("thread: %d; distance from node %d to node %d: %d\n", tid, node->get_func_id(), target_node->get_func_id(), distance);
+
+                       }
+
                }
        }
+
+       /* Clear list first */
+       WaitObj * wait_obj = history->getWaitObj(self_id);
+       thrd_id_set_t * waiting_threads = wait_obj->getWaitingFor();
+       waiting_threads->reset();
+
+       HSIterator<thread_id_t, int, 0> * it = waiting_for_threads.iterator();
+       while (it->hasNext()) {
+               thread_id_t tid = it->next();
+               waiting_threads->add(tid);
+       }
 }
 
 bool NewFuzzer::shouldWait(const ModelAction * act)
diff --git a/waitobj.cc b/waitobj.cc
new file mode 100644 (file)
index 0000000..e9299f5
--- /dev/null
@@ -0,0 +1,47 @@
+#include "waitobj.h"
+
+WaitObj::WaitObj(thread_id_t tid) :
+       tid(tid),
+       waiting_for(32),
+       waited_by(32),
+       dist_table(32)
+{}
+
+int WaitObj::lookup_dist(thread_id_t other_id)
+{
+       if (dist_table.contains(other_id))
+               return dist_table.get(other_id);
+
+       return -1;
+}
+
+void WaitObj::print_waiting_for()
+{
+       if (waiting_for.getSize() == 0)
+               return;
+
+       model_print("thread %d is waiting for: ", tid);
+       thrd_id_set_iter * it = waiting_for.iterator();
+
+       while (it->hasNext()) {
+               thread_id_t thread_id = it->next();
+               model_print("%d ", thread_id);
+       }
+       model_print("\n");
+}
+
+void WaitObj::print_waited_by()
+{
+       if (waited_by.getSize() == 0)
+               return;
+
+       model_print("thread %d is waited by: ", tid);
+       thrd_id_set_iter * it = waited_by.iterator();
+
+       while (it->hasNext()) {
+               thread_id_t thread_id = it->next();
+               model_print("%d ", thread_id);
+       }
+       model_print("\n");
+
+}
diff --git a/waitobj.h b/waitobj.h
new file mode 100644 (file)
index 0000000..26f7f1c
--- /dev/null
+++ b/waitobj.h
@@ -0,0 +1,34 @@
+#ifndef __WAITOBJ_H__
+#define __WAITOBJ_H__
+
+#include "classlist.h"
+#include "modeltypes.h"
+
+class WaitObj {
+public:
+       WaitObj(thread_id_t);
+       ~WaitObj() {}
+
+       thread_id_t get_tid() { return tid; }
+
+       thrd_id_set_t * getWaitingFor() { return &waiting_for; }
+       thrd_id_set_t * getWaitingBy() { return &waited_by; }
+       int lookup_dist(thread_id_t other_tid);
+
+       void print_waiting_for();
+       void print_waited_by();
+
+       SNAPSHOTALLOC
+private:
+       thread_id_t tid;
+
+       /* The set of threads this thread (tid) is waiting for */
+       thrd_id_set_t waiting_for;
+
+       /* The set of threads waiting for this thread */
+       thrd_id_set_t waited_by;
+
+       HashTable<thread_id_t, int, int, 0> dist_table;
+};
+
+#endif