X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=history.cc;h=f84af3f0f4cd024e954fdf7c9e642b2510adb5ae;hp=afd1f1d1752d9d4a0fde35ccef3d91c99ae572f2;hb=7cab9e695d0cfd0e935a6ef100a914aa6f661cc4;hpb=bbc0bd0561362e1cb93c04fddc165b49d83c24ed diff --git a/history.cc b/history.cc index afd1f1d1..f84af3f0 100644 --- a/history.cc +++ b/history.cc @@ -14,6 +14,7 @@ /** @brief Constructor */ ModelHistory::ModelHistory() : func_counter(1), /* function id starts with 1 */ + last_seq_number(INIT_SEQ_NUMBER), func_map(), func_map_rev(), func_nodes() @@ -23,47 +24,36 @@ ModelHistory::ModelHistory() : 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_func_list = new SnapVector(); + thrd_last_entered_func = new SnapVector(); 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++) + 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 = execution->get_thrd_func_list(); - SnapVector< SnapList *> * - 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(); thrd_func_list->resize( id + 1 ); - thrd_func_act_lists->resize( id + 1 ); - for (uint i = oldsize; i < id + 1; i++) { + for (uint i = oldsize;i < id + 1;i++) { // 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); } } - 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; (*thrd_func_list)[id].push_back(func_id); @@ -72,8 +62,7 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) resize_func_nodes( func_id + 1 ); FuncNode * func_node = func_nodes[func_id]; - func_node->init_predicate_tree_position(tid); - func_node->init_inst_act_map(tid); + func_node->function_entry_handler(tid); /* Add edges between FuncNodes */ if (last_entered_func_id != 0) { @@ -82,49 +71,22 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) } /* Monitor the statuses of threads waiting for tid */ - monitor_waiting_thread(func_id, 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 = execution->get_thrd_func_list(); - SnapVector< SnapList *> * - 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(); if (last_func_id == func_id) { FuncNode * func_node = func_nodes[func_id]; - func_node->set_predicate_tree_position(tid, NULL); - func_node->reset_inst_act_map(tid); - - action_list_t * curr_act_list = func_act_lists->back(); - - /* defer the processing of curr_act_list until the function has exits a few times - * (currently twice) so that more information can be gathered to infer nullity predicates. - */ - func_node->incr_exit_count(); - if (func_node->get_exit_count() >= 2) { - SnapList * action_list_buffer = func_node->get_action_list_buffer(); - while (action_list_buffer->size() > 0) { - action_list_t * act_list = action_list_buffer->back(); - action_list_buffer->pop_back(); - func_node->update_tree(act_list); - } - - func_node->update_tree(curr_act_list); - } else - func_node->get_action_list_buffer()->push_front(curr_act_list); + func_node->function_exit_handler(tid); (*thrd_func_list)[id].pop_back(); - func_act_lists->pop_back(); } else { - model_print("trying to exit with a wrong function id\n"); - model_print("--- last_func: %d, func_id: %d\n", last_func_id, func_id); + ASSERT(false); } //model_print("thread %d exiting func %d\n", tid, func_id); } @@ -136,7 +98,7 @@ void ModelHistory::resize_func_nodes(uint32_t new_size) if ( old_size < new_size ) func_nodes.resize(new_size); - for (uint32_t id = old_size; id < new_size; id++) { + for (uint32_t id = old_size;id < new_size;id++) { const char * func_name = func_map_rev[id]; FuncNode * func_node = new FuncNode(this); func_node->set_func_id(id); @@ -147,18 +109,13 @@ void ModelHistory::resize_func_nodes(uint32_t new_size) void ModelHistory::process_action(ModelAction *act, thread_id_t tid) { - ModelExecution * execution = model->get_execution(); - SnapVector * thrd_func_list = execution->get_thrd_func_list(); - SnapVector< SnapList *> * - thrd_func_act_lists = execution->get_thrd_func_act_lists(); - 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; /* Monitor the statuses of threads waiting for tid */ - monitor_waiting_thread_counter(tid); + // monitor_waiting_thread_counter(tid); /* Every write action should be processed, including * nonatomic writes (which have no position) */ @@ -169,12 +126,12 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) /* Notify FuncNodes that may read from this location */ SnapVector * func_node_list = getRdFuncNodes(location); - for (uint i = 0; i < func_node_list->size(); i++) { + 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); + // check_waiting_write(act); } uint32_t func_id = (*thrd_func_list)[thread_id].back(); @@ -184,23 +141,14 @@ void ModelHistory::process_action(ModelAction *act, thread_id_t tid) 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(); - - if (skip_action(act, curr_act_list)) + if (skip_action(act)) return; - /* 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); - } + func_node->update_tree(act); + last_seq_number = act->get_seq_number(); } /* Return the FuncNode given its func_id */ @@ -220,7 +168,6 @@ FuncNode * ModelHistory::get_func_node(uint32_t func_id) 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(); if (func_id != 0) { @@ -305,7 +252,7 @@ void ModelHistory::remove_waiting_write(thread_id_t tid) /* 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++) { + for (uint i = 0;i < concrete_preds->size();i++) { ConcretePredicate * current = (*concrete_preds)[i]; if (concrete == current) { (*concrete_preds)[i] = concrete_preds->back(); @@ -334,19 +281,19 @@ void ModelHistory::check_waiting_write(ModelAction * write_act) SnapVector * concrete_exprs = concrete_pred->getExpressions(); bool satisfy_predicate = true; /* Check if the written value satisfies every predicate expression */ - for (uint i = 0; i < concrete_exprs->size(); i++) { + for (uint i = 0;i < concrete_exprs->size();i++) { struct concrete_pred_expr concrete = (*concrete_exprs)[i]; bool equality = false; switch (concrete.token) { - case EQUALITY: - equality = (value == concrete.value); - break; - case NULLITY: - equality = ((void*)value == NULL); - break; - default: - model_print("unknown predicate token"); - break; + case EQUALITY: + equality = (value == concrete.value); + break; + case NULLITY: + equality = ((void*)value == NULL); + break; + default: + model_print("unknown predicate token"); + break; } if (equality != concrete.equality) { @@ -361,7 +308,7 @@ void ModelHistory::check_waiting_write(ModelAction * write_act) Thread * thread = model->get_thread(tid); //model_print("** thread %d is woken up\n", thread->get_id()); - model->get_execution()->getFuzzer()->notify_paused_thread(thread); + ((NewFuzzer *)model->get_execution()->getFuzzer())->notify_paused_thread(thread); } index++; @@ -374,7 +321,7 @@ WaitObj * ModelHistory::getWaitObj(thread_id_t 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++) { + for (int i = old_size;i < thread_id + 1;i++) { (*thrd_wait_obj)[i] = new WaitObj( int_to_id(i) ); } } @@ -383,7 +330,7 @@ WaitObj * ModelHistory::getWaitObj(thread_id_t tid) } void ModelHistory::add_waiting_thread(thread_id_t self_id, - thread_id_t waiting_for_id, FuncNode * target_node, 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, target_node, dist); @@ -408,10 +355,11 @@ void ModelHistory::remove_waiting_thread(thread_id_t tid) } self_wait_obj->clear_waiting_for(); + delete iter; } void ModelHistory::stop_waiting_for_node(thread_id_t self_id, - thread_id_t waiting_for_id, FuncNode * target_node) + 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); @@ -428,28 +376,13 @@ void ModelHistory::stop_waiting_for_node(thread_id_t self_id, // 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); + ((NewFuzzer *)execution->getFuzzer())->notify_paused_thread(thread); } } } -SnapVector * ModelHistory::getThrdInstActMap(uint32_t func_id) +bool ModelHistory::skip_action(ModelAction * act) { - 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(); @@ -458,11 +391,8 @@ bool ModelHistory::skip_action(ModelAction * act, SnapList * curr 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; - } + if (last_seq_number != INIT_SEQ_NUMBER && last_seq_number == curr_seq_number) + return true; /* Skip actions that are paused by fuzzer (sequence number is 0) */ if (curr_seq_number == 0) @@ -473,10 +403,10 @@ bool ModelHistory::skip_action(ModelAction * act, SnapList * curr /* 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. + * 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. + * ever increases, stop waiting for this thread on this target node. */ void ModelHistory::monitor_waiting_thread(uint32_t func_id, thread_id_t tid) { @@ -501,7 +431,11 @@ void ModelHistory::monitor_waiting_thread(uint32_t func_id, thread_id_t tid) stop_waiting_for_node(waited_by_id, tid, target); } } + + delete node_iter; } + + delete tid_iter; } void ModelHistory::monitor_waiting_thread_counter(thread_id_t tid) @@ -526,16 +460,18 @@ void ModelHistory::monitor_waiting_thread_counter(thread_id_t tid) // 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); + ((NewFuzzer *)execution->getFuzzer())->notify_paused_thread(thread); } } } + + delete tid_iter; } /* Reallocate some snapshotted memories when new executions start */ void ModelHistory::set_new_exec_flag() { - for (uint i = 1; i < func_nodes.size(); i++) { + for (uint i = 1;i < func_nodes.size();i++) { FuncNode * func_node = func_nodes[i]; func_node->set_new_exec_flag(); } @@ -544,13 +480,13 @@ void ModelHistory::set_new_exec_flag() void ModelHistory::dump_func_node_graph() { model_print("digraph func_node_graph {\n"); - for (uint i = 1; i < func_nodes.size(); i++) { + for (uint i = 1;i < func_nodes.size();i++) { FuncNode * node = func_nodes[i]; ModelList * out_edges = node->get_out_edges(); model_print("\"%p\" [label=\"%s\"]\n", node, node->get_func_name()); mllnode * it; - for (it = out_edges->begin(); it != NULL; it = it->getNext()) { + for (it = out_edges->begin();it != NULL;it = it->getNext()) { FuncNode * other = it->getVal(); model_print("\"%p\" -> \"%p\"\n", node, other); } @@ -561,33 +497,33 @@ void ModelHistory::dump_func_node_graph() void ModelHistory::print_func_node() { /* function id starts with 1 */ - for (uint32_t i = 1; i < func_nodes.size(); i++) { + for (uint32_t i = 1;i < func_nodes.size();i++) { FuncNode * func_node = func_nodes[i]; - func_node->print_predicate_tree(); -/* - func_inst_list_mt * entry_insts = func_node->get_entry_insts(); - model_print("function %s has entry actions\n", func_node->get_func_name()); - mllnode* it; - for (it = entry_insts->begin();it != NULL;it=it->getNext()) { - FuncInst *inst = it->getVal(); - model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position()); - } - */ +/* + func_inst_list_mt * entry_insts = func_node->get_entry_insts(); + model_print("function %s has entry actions\n", func_node->get_func_name()); + + mllnode* it; + for (it = entry_insts->begin();it != NULL;it=it->getNext()) { + FuncInst *inst = it->getVal(); + model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position()); + } + */ } } void ModelHistory::print_waiting_threads() { ModelExecution * execution = model->get_execution(); - for (unsigned int i = 0; i < execution->get_num_threads();i++) { + 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++) { + 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();