From: weiyu Date: Wed, 9 Oct 2019 02:00:15 +0000 (-0700) Subject: Toward implementing the counter approach to monitor threads X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=commitdiff_plain;h=f54c2d871c2482fd271ffb6969106e37eb6a9263 Toward implementing the counter approach to monitor threads --- diff --git a/history.cc b/history.cc index 1e746045..9969c016 100644 --- 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 * thrd_func_list = execution->get_thrd_func_list(); SnapVector< SnapList *> * 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 * 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 * 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 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 7513524f..f8d86636 100644 --- 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 * getThrdInstActMap(uint32_t func_id); @@ -83,6 +83,7 @@ private: bool skip_action(ModelAction * act, SnapList * 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 42870b5c..5a1bc12f 100644 --- 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 WaitObj::incr_waiting_for_counter() +{ + SnapVector 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 34c17428..c15fb21f 100644 --- 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 incr_waiting_for_counter(); + void clear_waiting_for(); void print_waiting_for(bool verbose = false); @@ -44,6 +47,10 @@ private: SnapVector thrd_dist_maps; SnapVector thrd_target_nodes; + /* Count the number of actions for threads that + * this thread is waiting for */ + SnapVector thrd_action_counters; + dist_map_t * getDistMap(thread_id_t tid); };