From: weiyu Date: Tue, 8 Oct 2019 01:28:20 +0000 (-0700) Subject: Every time a thread enters a function, check whether other threads should still wait... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=commitdiff_plain;h=f6903f05c59c2f59ae9d22f177985aba6cf35e03 Every time a thread enters a function, check whether other threads should still wait for this thread or not. --- diff --git a/funcnode.cc b/funcnode.cc index 18d7771b..70cc4472 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -646,6 +646,9 @@ void FuncNode::add_out_edge(FuncNode * other) */ int FuncNode::compute_distance(FuncNode * target, int max_step) { + if (target == NULL) + return -1; + SnapList queue; HashTable distances; diff --git a/history.cc b/history.cc index 3f098a60..d184fc62 100644 --- a/history.cc +++ b/history.cc @@ -28,11 +28,19 @@ ModelHistory::ModelHistory() : func_inst_act_maps = new HashTable *, int, 0>(128); } +ModelHistory::~ModelHistory() +{ + // TODO: complete deconstructor + for (uint i = 0; i < thrd_wait_obj->size(); ) + delete (*thrd_wait_obj)[i]; +} + void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) { //model_print("thread %d entering func %d\n", tid, func_id); ModelExecution * execution = model->get_execution(); uint id = id_to_int(tid); + SnapVector * thrd_func_list = execution->get_thrd_func_list(); SnapVector< SnapList *> * thrd_func_act_lists = execution->get_thrd_func_act_lists(); @@ -72,6 +80,8 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) FuncNode * last_func_node = func_nodes[last_entered_func_id]; last_func_node->add_out_edge(func_node); } + + monitor_waiting_thread(func_id, tid); } /* @param func_id a non-zero value */ @@ -156,7 +166,7 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) uint64_t value = act->get_write_value(); update_write_history(location, value); - /* Update FuncNodes that may read from this location */ + /* Notify FuncNodes that may read from this location */ SnapVector * func_node_list = getRdFuncNodes(location); for (uint i = 0; i < func_node_list->size(); i++) { FuncNode * func_node = (*func_node_list)[i]; @@ -379,10 +389,10 @@ WaitObj * ModelHistory::getWaitObj(thread_id_t tid) } void ModelHistory::add_waiting_thread(thread_id_t self_id, - thread_id_t waiting_for_id, int dist) + thread_id_t waiting_for_id, FuncNode * target_node, int dist) { WaitObj * self_wait_obj = getWaitObj(self_id); - self_wait_obj->add_waiting_for(waiting_for_id, dist); + self_wait_obj->add_waiting_for(waiting_for_id, target_node, dist); /* Update waited-by relation */ WaitObj * other_wait_obj = getWaitObj(waiting_for_id); @@ -394,6 +404,7 @@ void ModelHistory::remove_waiting_thread(thread_id_t tid) WaitObj * self_wait_obj = getWaitObj(tid); thrd_id_set_t * waiting_for = self_wait_obj->getWaitingFor(); + /* Remove tid from waited_by's */ thrd_id_set_iter * iter = waiting_for->iterator(); while (iter->hasNext()) { thread_id_t other_id = iter->next(); @@ -440,6 +451,36 @@ bool ModelHistory::skip_action(ModelAction * act, SnapList * curr return false; } +/* Monitor thread tid and decide whether other threads (that are waiting for tid) + * should keep waiting for this thread or not. Shall only be called when a thread + * enters a function. + * + * Heuristics: If the distance from the current FuncNode to some target node + * ever increases, stop waiting for this thread on this target node. + */ +void ModelHistory::monitor_waiting_thread(uint32_t func_id, thread_id_t tid) +{ + WaitObj * wait_obj = getWaitObj(tid); + thrd_id_set_t * waited_by = wait_obj->getWaitedBy(); + + /* For each thread waiting for tid */ + thrd_id_set_iter * iter = waited_by->iterator(); + + while (iter->hasNext()) { + thread_id_t other_id = iter->next(); + WaitObj * other_wait_obj = getWaitObj(other_id); + + node_set_t * target_nodes = other_wait_obj->getTargetNodes(tid); + node_set_iter * iter = target_nodes->iterator(); + while (iter->hasNext()) { + FuncNode * target = iter->next(); + int old_dist = other_wait_obj->lookup_dist(tid, target); + } + // TODO: Recompute distance from tmp to 'target' nodes + // FuncNode * tmp = func_nodes[func_id]; + } +} + /* Reallocate some snapshotted memories when new executions start */ void ModelHistory::set_new_exec_flag() { diff --git a/history.h b/history.h index a7185106..82a1a010 100644 --- a/history.h +++ b/history.h @@ -40,7 +40,7 @@ public: SnapVector * getThrdWaitingWrite() { return thrd_waiting_write; } WaitObj * getWaitObj(thread_id_t tid); - void add_waiting_thread(thread_id_t self_id, thread_id_t waiting_for_id, int dist); + 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); SnapVector * getThrdInstActMap(uint32_t func_id); @@ -76,11 +76,12 @@ private: SnapVector * thrd_waiting_write; SnapVector * thrd_wait_obj; - /* A run-time map from FuncInst to ModelAction per each thread, per each FuncNode. + /* A run-time map from FuncInst to ModelAction per thread, per FuncNode. * Manipulated by FuncNode, and needed by NewFuzzer */ HashTable *, int, 0> * func_inst_act_maps; bool skip_action(ModelAction * act, SnapList * curr_act_list); + void monitor_waiting_thread(uint32_t func_id, thread_id_t tid); }; #endif /* __HISTORY_H__ */ diff --git a/newfuzzer.cc b/newfuzzer.cc index b5f1cd8e..6810d022 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -17,7 +17,7 @@ NewFuzzer::NewFuzzer() : thrd_curr_pred(), thrd_selected_child_branch(), thrd_pruned_writes(), - paused_thread_set(), + paused_thread_list(), paused_thread_table(128) {} @@ -210,10 +210,10 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, */ void NewFuzzer::conditional_sleep(Thread * thread) { - int index = paused_thread_set.size(); + int index = paused_thread_list.size(); model->getScheduler()->add_sleep(thread); - paused_thread_set.push_back(thread); + paused_thread_list.push_back(thread); paused_thread_table.put(thread, index); // Update table /* Add the waiting condition to ModelHistory */ @@ -234,7 +234,7 @@ void NewFuzzer::conditional_sleep(Thread * thread) bool NewFuzzer::has_paused_threads() { - return paused_thread_set.size() != 0; + return paused_thread_list.size() != 0; } Thread * NewFuzzer::selectThread(int * threadlist, int numthreads) @@ -255,13 +255,13 @@ Thread * NewFuzzer::selectThread(int * threadlist, int numthreads) */ 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]; + int random_index = random() % paused_thread_list.size(); + Thread * thread = paused_thread_list[random_index]; model->getScheduler()->remove_sleep(thread); - Thread * last_thread = paused_thread_set.back(); - paused_thread_set[random_index] = last_thread; - paused_thread_set.pop_back(); + Thread * last_thread = paused_thread_list.back(); + paused_thread_list[random_index] = last_thread; + paused_thread_list.pop_back(); paused_thread_table.put(last_thread, random_index); // Update table paused_thread_table.remove(thread); @@ -282,9 +282,9 @@ void NewFuzzer::notify_paused_thread(Thread * 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(); + Thread * last_thread = paused_thread_list.back(); + paused_thread_list[index] = last_thread; + paused_thread_list.pop_back(); paused_thread_table.put(last_thread, index); // Update table paused_thread_table.remove(thread); @@ -316,7 +316,7 @@ void NewFuzzer::find_threads(ModelAction * pending_read) int distance = node->compute_distance(target_node); if (distance != -1) { - history->add_waiting_thread(self_id, tid, distance); + history->add_waiting_thread(self_id, tid, target_node, distance); model_print("thread: %d; distance from node %d to node %d: %d\n", tid, node->get_func_id(), target_node->get_func_id(), distance); } diff --git a/newfuzzer.h b/newfuzzer.h index 0e5d483b..6ce1e7f4 100644 --- a/newfuzzer.h +++ b/newfuzzer.h @@ -37,7 +37,7 @@ private: /* The set of Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. Only used by selectWrite. */ - SnapVector paused_thread_set; + SnapVector paused_thread_list; HashTable paused_thread_table; void conditional_sleep(Thread * thread); diff --git a/waitobj.cc b/waitobj.cc index 3aaa632e..64def5a0 100644 --- a/waitobj.cc +++ b/waitobj.cc @@ -1,16 +1,32 @@ #include "waitobj.h" +#include "threads-model.h" WaitObj::WaitObj(thread_id_t tid) : tid(tid), waiting_for(32), waited_by(32), - dist_table(32) + thrd_dist_maps(), + thrd_target_nodes() {} -void WaitObj::add_waiting_for(thread_id_t other, int dist) +WaitObj::~WaitObj() +{ + for (uint i = 0; i < thrd_dist_maps.size(); i++) + delete thrd_dist_maps[i]; + + for (uint i = 0; i < thrd_target_nodes.size(); i++) + delete thrd_target_nodes[i]; +} + +void WaitObj::add_waiting_for(thread_id_t other, FuncNode * node, int dist) { waiting_for.add(other); - dist_table.put(other, dist); + + dist_map_t * dist_map = getDistMap(other); + dist_map->put(node, dist); + + node_set_t * target_nodes = getTargetNodes(other); + target_nodes->add(node); } void WaitObj::add_waited_by(thread_id_t other) @@ -18,10 +34,28 @@ void WaitObj::add_waited_by(thread_id_t other) waited_by.add(other); } -void WaitObj::remove_waiting_for(thread_id_t other) +/** + * Stop waiting for the thread to reach the target node + * + * @param other The thread to be removed + * @param node The target node + * @return true if "other" is removed from waiting_for set + */ +bool WaitObj::remove_waiting_for(thread_id_t other, FuncNode * node) { - waiting_for.remove(other); - dist_table.remove(other); + dist_map_t * dist_map = getDistMap(other); + dist_map->remove(node); + + node_set_t * target_nodes = getTargetNodes(other); + target_nodes->remove(node); + + /* The thread has not nodes to reach */ + if (target_nodes->isEmpty()) { + waiting_for.remove(other); + return true; + } + + return false; } void WaitObj::remove_waited_by(thread_id_t other) @@ -29,19 +63,58 @@ void WaitObj::remove_waited_by(thread_id_t other) waited_by.remove(other); } -int WaitObj::lookup_dist(thread_id_t other_id) +int WaitObj::lookup_dist(thread_id_t tid, FuncNode * target) { - if (dist_table.contains(other_id)) - return dist_table.get(other_id); + dist_map_t * map = getDistMap(tid); + if (map->contains(target)) + return map->get(target); return -1; } +dist_map_t * WaitObj::getDistMap(thread_id_t tid) +{ + int thread_id = id_to_int(tid); + int old_size = thrd_dist_maps.size(); + + if (old_size <= thread_id) { + thrd_dist_maps.resize(thread_id + 1); + for (int i = old_size; i < thread_id + 1; i++) { + thrd_dist_maps[i] = new dist_map_t(16); + } + } + + return thrd_dist_maps[thread_id]; +} + +node_set_t * WaitObj::getTargetNodes(thread_id_t tid) +{ + int thread_id = id_to_int(tid); + int old_size = thrd_target_nodes.size(); + + if (old_size <= thread_id) { + thrd_target_nodes.resize(thread_id + 1); + for (int i = old_size; i < thread_id + 1; i++) { + thrd_target_nodes[i] = new node_set_t(16); + } + } + + return thrd_target_nodes[thread_id]; +} + void WaitObj::reset() { + thrd_id_set_iter * iter = waiting_for.iterator(); + while (iter->hasNext()) { + thread_id_t tid = iter->next(); + int index = id_to_int(tid); + thrd_target_nodes[index]->reset(); + /* thrd_dist_maps are not reset because distances + * will be overwritten */ + } + waiting_for.reset(); waited_by.reset(); - dist_table.reset(); } void WaitObj::print_waiting_for() diff --git a/waitobj.h b/waitobj.h index ae7a5fe5..9b4aead2 100644 --- a/waitobj.h +++ b/waitobj.h @@ -4,22 +4,28 @@ #include "classlist.h" #include "modeltypes.h" +typedef HashTable dist_map_t; +typedef HashSet node_set_t; +typedef HSIterator node_set_iter; + class WaitObj { public: WaitObj(thread_id_t); - ~WaitObj() {} + ~WaitObj(); thread_id_t get_tid() { return tid; } - void add_waiting_for(thread_id_t other, int dist); + void add_waiting_for(thread_id_t other, FuncNode * node, int dist); void add_waited_by(thread_id_t other); - void remove_waiting_for(thread_id_t other); + bool remove_waiting_for(thread_id_t other, FuncNode * node); void remove_waited_by(thread_id_t other); thrd_id_set_t * getWaitingFor() { return &waiting_for; } - thrd_id_set_t * getWaitingBy() { return &waited_by; } - int lookup_dist(thread_id_t other_tid); + thrd_id_set_t * getWaitedBy() { return &waited_by; } + 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); void reset(); void print_waiting_for(); @@ -35,7 +41,10 @@ private: /* The set of threads waiting for this thread */ thrd_id_set_t waited_by; - HashTable dist_table; + SnapVector thrd_dist_maps; + SnapVector thrd_target_nodes; + + dist_map_t * getDistMap(thread_id_t tid); }; #endif