From 443de938403221d2b1aaddfdb561fb837745cf86 Mon Sep 17 00:00:00 2001 From: weiyu Date: Thu, 12 Dec 2019 15:44:07 -0800 Subject: [PATCH] Delete set iterator pointers to prevent memory leaks and enable updating of predicate weights at function exits --- funcnode.cc | 97 ++++++++++++++++++++++++++++++++++++++++++++++------ funcnode.h | 3 ++ history.cc | 7 ++++ newfuzzer.cc | 10 ++++-- predicate.cc | 7 ++++ waitobj.cc | 7 ++++ 6 files changed, 117 insertions(+), 14 deletions(-) diff --git a/funcnode.cc b/funcnode.cc index f8c4fb43..94ef8c93 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -20,6 +20,8 @@ FuncNode::FuncNode(ModelHistory * history) : loc_act_map(128), predicate_tree_position(), predicate_leaves(), + leaves_tmp_storage(), + weight_debug_vec(), edge_table(32), out_edges() { @@ -274,6 +276,9 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) inst_pred_map.reset(); inst_id_map.reset(); + // Clear the set of leaves encountered in this path + leaves_tmp_storage.clear(); + sllnode *it = act_list->begin(); Predicate * curr_pred = predicate_tree_entry; while (it != NULL) { @@ -305,6 +310,10 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) Predicate * old_pred = inst_pred_map.get(next_inst); Predicate * back_pred = old_pred->get_parent(); + // For updating weights + leaves_tmp_storage.push_back(curr_pred); + + // Add to the set of backedges curr_pred->add_backedge(back_pred); curr_pred = back_pred; continue; @@ -340,6 +349,7 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) curr_pred->set_exit(predicate_tree_exit); } + leaves_tmp_storage.push_back(curr_pred); update_predicate_tree_weight(); } @@ -411,6 +421,8 @@ ModelAction * next_act, Predicate ** unset_predicate) } } + delete pred_expr_it; + if (predicate_correct) { *curr_pred = branch; branch_found = true; @@ -449,6 +461,8 @@ SnapVector * half_pred_expressions) half_pred_expressions->push_back(expression); } } + + delete loc_it; } } else { // next_inst is not single location @@ -585,6 +599,8 @@ void FuncNode::add_to_val_loc_map(value_set_t * values, void * loc) uint64_t val = it->next(); add_to_val_loc_map(val, loc); } + + delete it; } void FuncNode::update_loc_may_equal_map(void * new_loc, loc_set_t * old_locations) @@ -613,6 +629,8 @@ void FuncNode::update_loc_may_equal_map(void * new_loc, loc_set_t * old_location } _neighbors->add(new_loc); } + + delete loc_it; } /* Every time a thread enters a function, set its position to the predicate tree entry */ @@ -744,7 +762,8 @@ int FuncNode::compute_distance(FuncNode * target, int max_step) } /* Implement quick sort to sort leaves before assigning base scores */ -static int partition(SnapVector * arr, int low, int high) +template +static int partition(ModelVector<_Tp *> * arr, int low, int high) { unsigned int pivot = (*arr)[high]->get_depth(); int i = low - 1; @@ -752,13 +771,13 @@ static int partition(SnapVector * arr, int low, int high) for (int j = low; j <= high - 1; j++) { if ( (*arr)[j]->get_depth() < pivot ) { i++; - Predicate *tmp = (*arr)[i]; + _Tp * tmp = (*arr)[i]; (*arr)[i] = (*arr)[j]; (*arr)[j] = tmp; } } - Predicate * tmp = (*arr)[i + 1]; + _Tp * tmp = (*arr)[i + 1]; (*arr)[i + 1] = (*arr)[high]; (*arr)[high] = tmp; @@ -766,7 +785,8 @@ static int partition(SnapVector * arr, int low, int high) } /* Implement quick sort to sort leaves before assigning base scores */ -static void quickSort(SnapVector * arr, int low, int high) +template +static void quickSort(ModelVector<_Tp *> * arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); @@ -779,20 +799,22 @@ static void quickSort(SnapVector * arr, int low, int high) void FuncNode::assign_initial_weight() { PredSetIter * it = predicate_leaves.iterator(); - SnapVector leaves; + leaves_tmp_storage.clear(); + while (it->hasNext()) { Predicate * pred = it->next(); double weight = 100.0 / sqrt(pred->get_expl_count() + 1); pred->set_weight(weight); - leaves.push_back(pred); + leaves_tmp_storage.push_back(pred); } + delete it; - quickSort(&leaves, 0, leaves.size() - 1); + quickSort(&leaves_tmp_storage, 0, leaves_tmp_storage.size() - 1); // assign scores for internal nodes; - while ( !leaves.empty() ) { - Predicate * leaf = leaves.back(); - leaves.pop_back(); + while ( !leaves_tmp_storage.empty() ) { + Predicate * leaf = leaves_tmp_storage.back(); + leaves_tmp_storage.pop_back(); Predicate * curr = leaf->get_parent(); while (curr != NULL) { @@ -834,8 +856,61 @@ void FuncNode::update_predicate_tree_weight() if (marker == 2) { // Predicate tree is initially built assign_initial_weight(); - } else { + return; + } + + weight_debug_vec.clear(); + + quickSort(&leaves_tmp_storage, 0, leaves_tmp_storage.size() - 1); + for (uint i = 0; i < leaves_tmp_storage.size(); i++) { + Predicate * pred = leaves_tmp_storage[i]; + double weight = 100.0 / sqrt(pred->get_expl_count() + 1); + pred->set_weight(weight); + } + + // Update weights in internal nodes + while ( !leaves_tmp_storage.empty() ) { + Predicate * leaf = leaves_tmp_storage.back(); + leaves_tmp_storage.pop_back(); + + Predicate * curr = leaf->get_parent(); + while (curr != NULL) { + ModelVector * children = curr->get_children(); + double weight_sum = 0; + bool has_unassigned_node = false; + + for (uint i = 0; i < children->size(); i++) { + Predicate * child = (*children)[i]; + + double weight = child->get_weight(); + if (weight != 0) + weight_sum += weight; + else if ( predicate_leaves.contains(child) ) { + // If this child is a leaf + double weight = 100.0 / sqrt(child->get_expl_count() + 1); + child->set_weight(weight); + weight_sum += weight; + } else { + has_unassigned_node = true; + weight_debug_vec.push_back(child); // For debugging purpose + break; + } + } + + if (!has_unassigned_node) { + double average_weight = (double) weight_sum / (double) children->size(); + double weight = average_weight * pow(0.9, curr->get_depth()); + curr->set_weight(weight); + } else + break; + + curr = curr->get_parent(); + } + } + for (uint i = 0; i < weight_debug_vec.size(); i++) { + Predicate * tmp = weight_debug_vec[i]; + ASSERT( tmp->get_weight() != 0 ); } } diff --git a/funcnode.h b/funcnode.h index f4db0e86..7aec0bd0 100644 --- a/funcnode.h +++ b/funcnode.h @@ -118,7 +118,10 @@ private: /* Run-time position in the predicate tree for each thread */ ModelVector predicate_tree_position; + PredSet predicate_leaves; + ModelVector leaves_tmp_storage; + ModelVector weight_debug_vec; /* Store the relation between this FuncNode and other FuncNodes */ HashTable edge_table; diff --git a/history.cc b/history.cc index 7e5166fd..e4394a5d 100644 --- a/history.cc +++ b/history.cc @@ -410,6 +410,7 @@ 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, @@ -503,7 +504,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) @@ -532,6 +537,8 @@ void ModelHistory::monitor_waiting_thread_counter(thread_id_t tid) } } } + + delete tid_iter; } /* Reallocate some snapshotted memories when new executions start */ diff --git a/newfuzzer.cc b/newfuzzer.cc index c9d3f177..b98d9a4b 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -68,6 +68,8 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set break; } } + + delete it; } prune_writes(tid, selected_branch, rf_set, inst_act_map); @@ -113,14 +115,15 @@ inst_act_map_t * inst_act_map, SnapVector * rf_set) PredExprSet * pred_expressions = branch->get_pred_expressions(); any_child_match = true; - /* Do not check unset predicates */ + branch->incr_total_checking_count(); + if (pred_expressions->isEmpty()) { + /* Do not check predicate expression of unset predicates */ available_branches_tmp_storage.push_back(branch); + branch->incr_store_visible_count(); continue; } - branch->incr_total_checking_count(); - /* Iterate over all write actions */ for (uint j = 0;j < rf_set->size();j++) { ModelAction * write_act = (*rf_set)[j]; @@ -417,6 +420,7 @@ inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate) break; } + delete pred_expr_it; return satisfy_predicate; } diff --git a/predicate.cc b/predicate.cc index 9ef02988..35bc032f 100644 --- a/predicate.cc +++ b/predicate.cc @@ -76,6 +76,8 @@ void Predicate::copy_predicate_expr(Predicate * other) struct pred_expr * copy = new pred_expr(ptr->token, ptr->func_inst, ptr->value); pred_expressions.add(copy); } + + delete it; } /* Follow the child if any child whose FuncInst matches with inst @@ -126,6 +128,7 @@ ConcretePredicate * Predicate::evaluate(inst_act_map_t * inst_act_map, thread_id concrete->add_expression(ptr->token, value, ptr->value); } + delete it; return concrete; } @@ -176,6 +179,8 @@ void Predicate::print_predicate() model_print("Total checks: %d, visible count: %d; prob: %f\n", total_checking_count, store_visible_count, prob); model_print("Exploration count: %d", exploration_count); model_print("\"];\n"); + + delete it; } void Predicate::print_pred_subtree() @@ -196,4 +201,6 @@ void Predicate::print_pred_subtree() if (exit) { model_print("\"%p\" -> \"%p\"[style=dashed, color=red]\n", this, exit); } + + delete it; } diff --git a/waitobj.cc b/waitobj.cc index 0d1853c8..dc422be7 100644 --- a/waitobj.cc +++ b/waitobj.cc @@ -168,6 +168,8 @@ void WaitObj::clear_waiting_for() target_nodes->reset(); } + delete iter; + waiting_for.reset(); /* waited_by relation should be kept */ } @@ -185,6 +187,7 @@ void WaitObj::print_waiting_for(bool verbose) model_print("%d ", waiting_for_id); } model_print("\n"); + delete it; if (verbose) { /* Print out the distances from each thread to target nodes */ @@ -204,6 +207,8 @@ void WaitObj::print_waiting_for(bool verbose) } model_print(") "); } + + delete node_iter; } model_print("\n"); } @@ -222,4 +227,6 @@ void WaitObj::print_waited_by() model_print("%d ", thread_id); } model_print("\n"); + + delete it; } -- 2.34.1