Toward implementing the counter approach to monitor threads

diff --git a/history.cc b/history.cc
index 1e746045f7ab4e0c3a9e1d1fece5abdb3759db8f..9969c016a35927531ea03647fffa885ca659fc0d 100644 (file)
--- a/history.cc
+++ b/history.cc
@@ -81,6 +81,7 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
                last_func_node->add_out_edge(func_node);
        }
 
+       /* Monitor the statuses of threads waiting for tid */
        monitor_waiting_thread(func_id, tid);
 }
 
@@ -147,20 +148,22 @@ void ModelHistory::resize_func_nodes(uint32_t new_size)
 void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
 {
        ModelExecution * execution = model->get_execution();
-       /* Return if thread i has not entered any function or has exited
-          from all functions */
        SnapVector<func_id_list_t> * thrd_func_list = execution->get_thrd_func_list();
        SnapVector< SnapList<action_list_t *> *> *
                thrd_func_act_lists = execution->get_thrd_func_act_lists();
 
-       uint32_t id = id_to_int(tid);
-       if ( thrd_func_list->size() <= id )
+       uint32_t thread_id = id_to_int(tid);
+       uint32_t func_id = (*thrd_func_list)[thread_id].back();
+
+       /* Return if thread tid has not entered any function that contains atomics */
+       if ( thrd_func_list->size() <= thread_id )
                return;
 
-       /* Get the function id that thread i is currently in */
-       uint32_t func_id = (*thrd_func_list)[id].back();
-       SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[id];
+       /* Monitor the statuses of threads waiting for tid */
+       monitor_waiting_thread_counter(tid);
 
+       /* Every write action should be processed, including
+        * nonatomic writes (which have no position) */
        if (act->is_write()) {
                void * location = act->get_location();
                uint64_t value = act->get_write_value();
@@ -176,10 +179,13 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid)
                check_waiting_write(act);
        }
 
-       /* The following does not care about actions without a position */
+       /* The following does not care about actions that are not inside
+        * any function that contains atomics or actions without a position */
        if (func_id == 0 || act->get_position() == NULL)
                return;
 
+       SnapList<action_list_t *> * func_act_lists = (*thrd_func_act_lists)[thread_id];
+       /* The list of actions that thread tid has taken in its current function */
        action_list_t * curr_act_list = func_act_lists->back();
        ASSERT(curr_act_list != NULL);
 
@@ -416,11 +422,11 @@ void ModelHistory::remove_waiting_thread(thread_id_t tid)
        self_wait_obj->clear_waiting_for();
 }
 
-void ModelHistory::stop_waiting_for(thread_id_t self_id,
+void ModelHistory::stop_waiting_for_node(thread_id_t self_id,
        thread_id_t waiting_for_id, FuncNode * target_node)
 {
        WaitObj * self_wait_obj = getWaitObj(self_id);
-       bool thread_removed = self_wait_obj->remove_waiting_for(waiting_for_id, target_node);
+       bool thread_removed = self_wait_obj->remove_waiting_for_node(waiting_for_id, target_node);
 
        // model_print("\t%d gives up %d on node %d\n", self_id, waiting_for_id, target_node->get_func_id());
 
@@ -502,12 +508,32 @@ void ModelHistory::monitor_waiting_thread(uint32_t func_id, thread_id_t tid)
                        int new_dist = curr_node->compute_distance(target, old_dist);
 
                        if (new_dist == -1) {
-                               stop_waiting_for(waited_by_id, tid, target);
+                               stop_waiting_for_node(waited_by_id, tid, target);
                        }
                }
        }
 }
 
+void monitor_waiting_thread_counter(thread_id_t tid)
+{
+       WaitObj * wait_obj = getWaitObj(tid);
+       thrd_id_set_t * waited_by = wait_obj->getWaitedBy();
+       SnapVector<thread_id_t> expire_threads;
+
+       // Thread tid has taken an action, update the counter for threads waiting for tid
+       thrd_id_set_iter * tid_iter = waited_by->iterator();
+       while (tid_iter->hasNext()) {
+               thread_id_t waited_by_id = tid_iter->next();
+               WaitObj * other_wait_obj = getWaitObj(waited_by_id);
+
+               bool expire = other_wait_obj->incr_counter(tid);
+               if (expire) {
+                       // TODO: complete
+                       expire_threads.push_back(tid);
+               }
+       }
+}
+
 /* Reallocate some snapshotted memories when new executions start */
 void ModelHistory::set_new_exec_flag()
 {

diff --git a/history.h b/history.h
index 7513524f2da80e83ddedee973c51e38332ea6fc6..f8d866367c7e7e573067a0014f160e49b502a00f 100644 (file)
--- a/history.h
+++ b/history.h
@@ -42,7 +42,7 @@ public:
        WaitObj * getWaitObj(thread_id_t tid);
        void add_waiting_thread(thread_id_t self_id, thread_id_t waiting_for_id, FuncNode * target_node, int dist);
        void remove_waiting_thread(thread_id_t tid);
-       void stop_waiting_for(thread_id_t self_id, thread_id_t waiting_for_id, FuncNode * target_node);
+       void stop_waiting_for_node(thread_id_t self_id, thread_id_t waiting_for_id, FuncNode * target_node);
 
        SnapVector<inst_act_map_t *> * getThrdInstActMap(uint32_t func_id);
 
@@ -83,6 +83,7 @@ private:
 
        bool skip_action(ModelAction * act, SnapList<ModelAction *> * curr_act_list);
        void monitor_waiting_thread(uint32_t func_id, thread_id_t tid);
+       void monitor_waiting_thread_counter(thread_id_t tid);
 };
 
 #endif /* __HISTORY_H__ */

diff --git a/waitobj.cc b/waitobj.cc
index 42870b5c7d1cb65edee8924fd2967a4bfd2db298..5a1bc12f1f3c68f0bda956fd2557c85a69e47fe9 100644 (file)
--- a/waitobj.cc
+++ b/waitobj.cc
@@ -7,7 +7,8 @@ WaitObj::WaitObj(thread_id_t tid) :
        waiting_for(32),
        waited_by(32),
        thrd_dist_maps(),
-       thrd_target_nodes()
+       thrd_target_nodes(),
+       thrd_action_counters()
 {}
 
 WaitObj::~WaitObj()
@@ -43,7 +44,7 @@ void WaitObj::add_waited_by(thread_id_t other)
  * @return true if "other" is removed from waiting_for set
  *         false if only a target node of "other" is removed
  */
-bool WaitObj::remove_waiting_for(thread_id_t other, FuncNode * node)
+bool WaitObj::remove_waiting_for_node(thread_id_t other, FuncNode * node)
 {
        dist_map_t * dist_map = getDistMap(other);
        dist_map->remove(node);
@@ -60,6 +61,16 @@ bool WaitObj::remove_waiting_for(thread_id_t other, FuncNode * node)
        return false;
 }
 
+/* Stop waiting for the thread */
+void WaitObj::remove_waiting_for(thread_id_t other)
+{
+       // TODO: clear dist_map or not?
+       waiting_for.remove(other);
+
+       node_set_t * target_nodes = getTargetNodes(other);
+       target_nodes->reset();
+}
+
 void WaitObj::remove_waited_by(thread_id_t other)
 {
        waited_by.remove(other);
@@ -68,7 +79,11 @@ void WaitObj::remove_waited_by(thread_id_t other)
 int WaitObj::lookup_dist(thread_id_t tid, FuncNode * target)
 {
        dist_map_t * map = getDistMap(tid);
-       if (map->contains(target))
+       node_set_t * node_set = getTargetNodes(tid);
+
+       /* thrd_dist_maps is not reset when clear_waiting_for is called,
+        * so node_set should be checked */
+       if (node_set->contains(target) && map->contains(target))
                return map->get(target);
 
        return -1;
@@ -104,6 +119,45 @@ node_set_t * WaitObj::getTargetNodes(thread_id_t tid)
        return thrd_target_nodes[thread_id];
 }
 
+/*
+SnapVector<thread_id_t> WaitObj::incr_waiting_for_counter()
+{
+       SnapVector<thread_id_t> expire_thrds;
+
+       thrd_id_set_iter * iter = waiting_for.iterator();
+       while (iter->hasNext()) {
+               thread_id_t waiting_for_id = iter->next();
+               bool expire = incr_counter(waiting_for_id);
+
+               if (expire) {
+                       expire_thrds.push_back(waiting_for_id);
+               }
+       }
+
+       return expire_thrds;
+}*/
+
+/**
+ * Increment action counter for thread tid
+ * @return true if the counter for tid expires
+ */
+bool WaitObj::incr_counter(thread_id_t tid)
+{
+       int thread_id = id_to_int(tid);
+
+       /* thrd_action_counters.resize does not work here */
+       while (thrd_action_counters.size() <= (uint) thread_id) {
+               thrd_action_counters.push_back(0);
+       }
+
+       thrd_action_counters[thread_id]++;
+
+       if (thrd_action_counters[thread_id] > 1000)
+               return true;
+
+       return false;
+}
+
 void WaitObj::clear_waiting_for()
 {
        thrd_id_set_iter * iter = waiting_for.iterator();
@@ -169,5 +223,4 @@ void WaitObj::print_waited_by()
                model_print("%d ", thread_id);
        }
        model_print("\n");
-
 }

diff --git a/waitobj.h b/waitobj.h
index 34c174289731368c0f9233c2bf275ee4288c3ab4..c15fb21f4ad0f17cb968d35a682f57f0e66c1b4e 100644 (file)
--- a/waitobj.h
+++ b/waitobj.h
@@ -17,7 +17,7 @@ public:
 
        void add_waiting_for(thread_id_t other, FuncNode * node, int dist);
        void add_waited_by(thread_id_t other);
-       bool remove_waiting_for(thread_id_t other, FuncNode * node);
+       bool remove_waiting_for_node(thread_id_t other, FuncNode * node);
        void remove_waited_by(thread_id_t other);
 
        thrd_id_set_t * getWaitingFor() { return &waiting_for; }
@@ -25,7 +25,10 @@ public:
 
        node_set_t * getTargetNodes(thread_id_t tid);
        int lookup_dist(thread_id_t tid, FuncNode * target);
-       int lookup_dist(thread_id_t other_tid);
+
+       bool incr_counter(thread_id_t tid);
+       // SnapVector<thread_id_t> incr_waiting_for_counter();
+
        void clear_waiting_for();
 
        void print_waiting_for(bool verbose = false);
@@ -44,6 +47,10 @@ private:
        SnapVector<dist_map_t *> thrd_dist_maps;
        SnapVector<node_set_t *> thrd_target_nodes;
 
+       /* Count the number of actions for threads that
+        * this thread is waiting for */
+       SnapVector<uint32_t> thrd_action_counters;
+
        dist_map_t * getDistMap(thread_id_t tid);
 };