Delete set iterator pointers to prevent memory leaks and enable updating of predicate...
authorweiyu <weiyuluo1232@gmail.com>
Thu, 12 Dec 2019 23:44:07 +0000 (15:44 -0800)
committerweiyu <weiyuluo1232@gmail.com>
Thu, 12 Dec 2019 23:44:07 +0000 (15:44 -0800)
funcnode.cc
funcnode.h
history.cc
newfuzzer.cc
predicate.cc
waitobj.cc

index f8c4fb4..94ef8c9 100644 (file)
@@ -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<ModelAction *> *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<struct half_pred_expr *> * 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<Predicate *> * arr, int low, int high)
+template<typename _Tp>
+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<Predicate *> * 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<Predicate *> * arr, int low, int high)
 }
 
 /* Implement quick sort to sort leaves before assigning base scores */
-static void quickSort(SnapVector<Predicate *> * arr, int low, int high)
+template<typename _Tp>
+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<Predicate *> * arr, int low, int high)
 void FuncNode::assign_initial_weight()
 {
        PredSetIter * it = predicate_leaves.iterator();
-       SnapVector<Predicate *> 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<Predicate *> * 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 );
        }
 }
 
index f4db0e8..7aec0bd 100644 (file)
@@ -118,7 +118,10 @@ private:
 
        /* Run-time position in the predicate tree for each thread */
        ModelVector<Predicate *> predicate_tree_position;
+
        PredSet predicate_leaves;
+       ModelVector<Predicate *> leaves_tmp_storage;
+       ModelVector<Predicate *> weight_debug_vec;
 
        /* Store the relation between this FuncNode and other FuncNodes */
        HashTable<FuncNode *, edge_type_t, uintptr_t, 0, model_malloc, model_calloc, model_free> edge_table;
index 7e5166f..e4394a5 100644 (file)
@@ -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 */
index c9d3f17..b98d9a4 100644 (file)
@@ -68,6 +68,8 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector<ModelAction *> * 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<ModelAction *> * 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;
 }
 
index 9ef0298..35bc032 100644 (file)
@@ -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;
 }
index 0d1853c..dc422be 100644 (file)
@@ -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;
 }