X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=history.cc;h=2ad4c1a90c53b33f959d8830213b81019b5e685e;hb=bf2121ac2a964022f09c30ebb904bef7ceb2df8d;hp=243501810e43ff7f4c3d56ae09f3e56a03ddf154;hpb=51ee3f71895aafae7e7292174862b3ad42c801a6;p=c11tester.git diff --git a/history.cc b/history.cc index 24350181..2ad4c1a9 100644 --- a/history.cc +++ b/history.cc @@ -5,6 +5,7 @@ #include "funcinst.h" #include "common.h" #include "concretepredicate.h" +#include "waitobj.h" #include "model.h" #include "execution.h" @@ -15,22 +16,35 @@ ModelHistory::ModelHistory() : func_counter(1), /* function id starts with 1 */ func_map(), func_map_rev(), - func_nodes(), - write_history(), // snapshot data structure - loc_func_nodes_map(), // shapshot 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 -{} + func_nodes() +{ + /* The following are snapshot data structures */ + write_history = new HashTable(); + loc_rd_func_nodes_map = new HashTable *, uintptr_t, 0>(); + loc_wr_func_nodes_map = new HashTable *, uintptr_t, 0>(); + loc_waiting_writes_map = new HashTable *, uintptr_t, 0>(); + thrd_waiting_write = new SnapVector(); + thrd_wait_obj = new SnapVector(); + func_inst_act_maps = new HashTable *, int, 0>(128); +} + +ModelHistory::~ModelHistory() +{ + // TODO: complete deconstructor; maybe not needed + for (uint i = 0; i < thrd_wait_obj->size(); i++) + 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 = model->get_execution()->get_thrd_func_list(); + + SnapVector * thrd_func_list = execution->get_thrd_func_list(); SnapVector< SnapList *> * - thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists(); + thrd_func_act_lists = execution->get_thrd_func_act_lists(); + SnapVector * thrd_last_entered_func = execution->get_thrd_last_entered_func(); if ( thrd_func_list->size() <= id ) { uint oldsize = thrd_func_list->size(); @@ -38,23 +52,20 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) thrd_func_act_lists->resize( id + 1 ); for (uint i = oldsize; i < id + 1; i++) { - new (&(*thrd_func_list)[i]) func_id_list_t(); // push 0 as a dummy function id to a void seg fault + new (&(*thrd_func_list)[i]) func_id_list_t(); (*thrd_func_list)[i].push_back(0); (*thrd_func_act_lists)[i] = new SnapList(); + thrd_last_entered_func->push_back(0); } } - while ( thrd_last_entered_func.size() <= id ) { - thrd_last_entered_func.push_back(0); // 0 is a dummy function id - } - SnapList * func_act_lists = (*thrd_func_act_lists)[id]; func_act_lists->push_back( new action_list_t() ); - uint32_t last_entered_func_id = thrd_last_entered_func[id]; - thrd_last_entered_func[id] = func_id; + uint32_t last_entered_func_id = (*thrd_last_entered_func)[id]; + (*thrd_last_entered_func)[id] = func_id; (*thrd_func_list)[id].push_back(func_id); if ( func_nodes.size() <= func_id ) @@ -69,15 +80,19 @@ 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 the statuses of threads waiting for tid */ + monitor_waiting_thread(func_id, tid); } /* @param func_id a non-zero value */ void ModelHistory::exit_function(const uint32_t func_id, thread_id_t tid) { + ModelExecution * execution = model->get_execution(); uint32_t id = id_to_int(tid); - SnapVector * thrd_func_list = model->get_execution()->get_thrd_func_list(); + SnapVector * thrd_func_list = execution->get_thrd_func_list(); SnapVector< SnapList *> * - thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists(); + thrd_func_act_lists = execution->get_thrd_func_act_lists(); SnapList * func_act_lists = (*thrd_func_act_lists)[id]; uint32_t last_func_id = (*thrd_func_list)[id].back(); @@ -132,70 +147,62 @@ void ModelHistory::resize_func_nodes(uint32_t new_size) void ModelHistory::process_action(ModelAction *act, thread_id_t tid) { - /* return if thread i has not entered any function or has exited - from all functions */ - SnapVector * thrd_func_list = model->get_execution()->get_thrd_func_list(); + ModelExecution * execution = model->get_execution(); + SnapVector * thrd_func_list = execution->get_thrd_func_list(); SnapVector< SnapList *> * - thrd_func_act_lists = model->get_execution()->get_thrd_func_act_lists(); + 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); + /* 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(); update_write_history(location, value); - /* Update FuncNodes that may read from this location */ - SnapList * func_nodes = loc_func_nodes_map.get(location); - if (func_nodes != NULL) { - sllnode * it = func_nodes->begin(); - for (; it != NULL; it = it->getNext()) { - FuncNode * func_node = it->getVal(); - func_node->add_to_val_loc_map(value, 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]; + func_node->add_to_val_loc_map(value, location); } check_waiting_write(act); } - /* the following does not care about actions without a position */ + uint32_t func_id = (*thrd_func_list)[thread_id].back(); + + /* 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; - bool second_part_of_rmw = act->is_rmwc() || act->is_rmw(); + 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); - modelclock_t curr_seq_number = act->get_seq_number(); - /* Skip actions that are second part of a read modify write or actions with the same sequence number */ - if (curr_act_list->size() != 0) { - ModelAction * last_act = curr_act_list->back(); - if (second_part_of_rmw || last_act->get_seq_number() == curr_seq_number) - return; - } - - /* skip actions that are paused by fuzzer (sequence number is 0) */ - if (curr_seq_number == 0) + if (skip_action(act, curr_act_list)) return; - FuncNode * func_node = func_nodes[func_id]; - - /* add to curr_inst_list */ + /* Add to curr_inst_list */ curr_act_list->push_back(act); + + FuncNode * func_node = func_nodes[func_id]; func_node->add_inst(act); if (act->is_read()) { func_node->update_inst_act_map(tid, act); // Update predicate tree position - Fuzzer * fuzzer = model->get_execution()->getFuzzer(); + Fuzzer * fuzzer = execution->getFuzzer(); Predicate * selected_branch = fuzzer->get_selected_child_branch(tid); func_node->set_predicate_tree_position(tid, selected_branch); } @@ -204,7 +211,11 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) /* 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 + if (func_id == 0) + return NULL; + + // This node has not been added to func_nodes + if (func_nodes.size() <= func_id) return NULL; return func_nodes[func_id]; @@ -216,75 +227,89 @@ FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid) int thread_id = id_to_int(tid); SnapVector * 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; + if (func_id != 0) { + return func_nodes[func_id]; + } + + return NULL; } void ModelHistory::update_write_history(void * location, uint64_t write_val) { - value_set_t * write_set = write_history.get(location); + value_set_t * write_set = write_history->get(location); if (write_set == NULL) { write_set = new value_set_t(); - write_history.put(location, write_set); + write_history->put(location, write_set); } write_set->add(write_val); } -void ModelHistory::update_loc_func_nodes_map(void * location, FuncNode * node) +void ModelHistory::update_loc_rd_func_nodes_map(void * location, FuncNode * node) +{ + SnapVector * func_node_list = getRdFuncNodes(location); + func_node_list->push_back(node); +} + +void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node) +{ + SnapVector * func_node_list = getWrFuncNodes(location); + func_node_list->push_back(node); +} + +SnapVector * ModelHistory::getRdFuncNodes(void * location) { - SnapList * func_node_list = loc_func_nodes_map.get(location); + SnapVector * func_node_list = loc_rd_func_nodes_map->get(location); if (func_node_list == NULL) { - func_node_list = new SnapList(); - loc_func_nodes_map.put(location, func_node_list); + func_node_list = new SnapVector(); + loc_rd_func_nodes_map->put(location, func_node_list); } - func_node_list->push_back(node); + return func_node_list; } -void ModelHistory::update_loc_wr_func_nodes_map(void * location, FuncNode * node) +SnapVector * ModelHistory::getWrFuncNodes(void * location) { - SnapList * func_node_list = loc_wr_func_nodes_map.get(location); + SnapVector * func_node_list = loc_wr_func_nodes_map->get(location); if (func_node_list == NULL) { - func_node_list = new SnapList(); - loc_func_nodes_map.put(location, func_node_list); + func_node_list = new SnapVector(); + loc_wr_func_nodes_map->put(location, func_node_list); } - func_node_list->push_back(node); + return func_node_list; } /* 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 * waiting_conditions = loc_waiting_writes_map.get(location); + SnapVector * waiting_conditions = loc_waiting_writes_map->get(location); if (waiting_conditions == NULL) { waiting_conditions = new SnapVector(); - loc_waiting_writes_map.put(location, waiting_conditions); + 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); + if (thrd_waiting_write->size() <= (uint) thread_id) { + thrd_waiting_write->resize(thread_id + 1); } - thrd_waiting_write[thread_id] = concrete; + (*thrd_waiting_write)[thread_id] = concrete; } void ModelHistory::remove_waiting_write(thread_id_t tid) { - ConcretePredicate * concrete = thrd_waiting_write[ id_to_int(tid) ]; + ConcretePredicate * concrete = (*thrd_waiting_write)[ id_to_int(tid) ]; void * location = concrete->get_location(); - SnapVector * concrete_preds = loc_waiting_writes_map.get(location); + SnapVector * 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) { @@ -295,16 +320,16 @@ void ModelHistory::remove_waiting_write(thread_id_t tid) } int thread_id = id_to_int( concrete->get_tid() ); - thrd_waiting_write[thread_id] = NULL; + (*thrd_waiting_write)[thread_id] = NULL; delete concrete; } -/* Check if any other thread is waiting for this write action. If so, wake them up */ +/* Check if any other thread is waiting for this write action. If so, "notify" them */ void ModelHistory::check_waiting_write(ModelAction * write_act) { void * location = write_act->get_location(); uint64_t value = write_act->get_write_value(); - SnapVector * concrete_preds = loc_waiting_writes_map.get(location); + SnapVector * concrete_preds = loc_waiting_writes_map->get(location); SnapVector to_remove = SnapVector(); if (concrete_preds == NULL) return; @@ -355,6 +380,170 @@ 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]; +} + +void ModelHistory::add_waiting_thread(thread_id_t self_id, + 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, target_node, dist); + + /* Update waited-by relation */ + WaitObj * other_wait_obj = getWaitObj(waiting_for_id); + other_wait_obj->add_waited_by(self_id); +} + +/* Thread tid is woken up (or notified), so it is not waiting for others anymore */ +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(); + WaitObj * other_wait_obj = getWaitObj(other_id); + other_wait_obj->remove_waited_by(tid); + } + + self_wait_obj->clear_waiting_for(); +} + +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_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()); + + /* If thread self_id is not waiting for waiting_for_id anymore */ + if (thread_removed) { + WaitObj * other_wait_obj = getWaitObj(waiting_for_id); + other_wait_obj->remove_waited_by(self_id); + + thrd_id_set_t * self_waiting_for = self_wait_obj->getWaitingFor(); + if ( self_waiting_for->isEmpty() ) { + // model_print("\tthread %d waits for nobody, wake up\n", self_id); + ModelExecution * execution = model->get_execution(); + Thread * thread = execution->get_thread(self_id); + execution->getFuzzer()->notify_paused_thread(thread); + } + } +} + +SnapVector * ModelHistory::getThrdInstActMap(uint32_t func_id) +{ + ASSERT(func_id != 0); + + SnapVector * maps = func_inst_act_maps->get(func_id); + if (maps == NULL) { + maps = new SnapVector(); + func_inst_act_maps->put(func_id, maps); + } + + return maps; +} + +bool ModelHistory::skip_action(ModelAction * act, SnapList * curr_act_list) +{ + ASSERT(curr_act_list != NULL); + + bool second_part_of_rmw = act->is_rmwc() || act->is_rmw(); + modelclock_t curr_seq_number = act->get_seq_number(); + + /* Skip actions that are second part of a read modify write */ + if (second_part_of_rmw) + return true; + + /* Skip actions with the same sequence number */ + if (curr_act_list->size() != 0) { + ModelAction * last_act = curr_act_list->back(); + if (last_act->get_seq_number() == curr_seq_number) + return true; + } + + /* Skip actions that are paused by fuzzer (sequence number is 0) */ + if (curr_seq_number == 0) + return true; + + 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(); + FuncNode * curr_node = func_nodes[func_id]; + + /* For each thread 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); + + node_set_t * target_nodes = other_wait_obj->getTargetNodes(tid); + node_set_iter * node_iter = target_nodes->iterator(); + while (node_iter->hasNext()) { + FuncNode * target = node_iter->next(); + int old_dist = other_wait_obj->lookup_dist(tid, target); + int new_dist = curr_node->compute_distance(target, old_dist); + + if (new_dist == -1) { + stop_waiting_for_node(waited_by_id, tid, target); + } + } + } +} + +void ModelHistory::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) { + wait_obj->remove_waited_by(waited_by_id); + other_wait_obj->remove_waiting_for(tid); + + thrd_id_set_t * other_waiting_for = other_wait_obj->getWaitingFor(); + if ( other_waiting_for->isEmpty() ) { + // model_print("\tthread %d waits for nobody, wake up\n", self_id); + ModelExecution * execution = model->get_execution(); + Thread * thread = execution->get_thread(waited_by_id); + execution->getFuzzer()->notify_paused_thread(thread); + } + } + } +} + /* Reallocate some snapshotted memories when new executions start */ void ModelHistory::set_new_exec_flag() { @@ -397,3 +586,19 @@ 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(); + } + + 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_waited_by(); + } +}