From: bdemsky Date: Tue, 26 Nov 2019 06:01:17 +0000 (-0800) Subject: Run tabbing pass X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=commitdiff_plain;h=fcc90758629b11f123081c80bb3c37e7ca2a4608 Run tabbing pass --- diff --git a/concretepredicate.h b/concretepredicate.h index c3b81bd9..1440763a 100644 --- a/concretepredicate.h +++ b/concretepredicate.h @@ -24,4 +24,4 @@ private: SnapVector expressions; }; -#endif /* __CONCRETE_PREDICATE_H */ +#endif /* __CONCRETE_PREDICATE_H */ diff --git a/funcinst.cc b/funcinst.cc index df91edc8..95e93fc2 100644 --- a/funcinst.cc +++ b/funcinst.cc @@ -67,7 +67,7 @@ FuncInst * FuncInst::search_in_collision(ModelAction *act) action_type type = act->get_type(); mllnode * it; - for (it = collisions.begin(); it != NULL; it = it->getNext()) { + for (it = collisions.begin();it != NULL;it = it->getNext()) { FuncInst * inst = it->getVal(); if (inst->get_type() == type) return inst; diff --git a/funcinst.h b/funcinst.h index e96eb190..79ec01ad 100644 --- a/funcinst.h +++ b/funcinst.h @@ -49,7 +49,7 @@ private: const char * position; /* Atomic operations with the same source line number may act at different - * memory locations, such as the next field of the head pointer in ms-queue. + * memory locations, such as the next field of the head pointer in ms-queue. * location only stores the memory location when this FuncInst was constructed. */ void * location; diff --git a/funcnode.cc b/funcnode.cc index 909d4a8d..2a25bfb9 100644 --- a/funcnode.cc +++ b/funcnode.cc @@ -133,7 +133,7 @@ FuncInst * FuncNode::get_inst(ModelAction *act) } /* RMWRCAS actions are converted to RMW or READ actions */ else if (inst_type == ATOMIC_RMWRCAS && - (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) { + (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) { return inst; } /* Return the FuncInst in the collision list */ @@ -149,7 +149,7 @@ void FuncNode::add_entry_inst(FuncInst * inst) return; mllnode * it; - for (it = entry_insts.begin(); it != NULL; it = it->getNext()) { + for (it = entry_insts.begin();it != NULL;it = it->getNext()) { if (inst == it->getVal()) return; } @@ -158,7 +158,7 @@ void FuncNode::add_entry_inst(FuncInst * inst) } /** - * @brief Convert ModelAdtion list to FuncInst list + * @brief Convert ModelAdtion list to FuncInst list * @param act_list A list of ModelActions */ void FuncNode::update_tree(action_list_t * act_list) @@ -172,7 +172,7 @@ void FuncNode::update_tree(action_list_t * act_list) func_inst_list_t inst_list; action_list_t rw_act_list; - for (sllnode * it = act_list->begin(); it != NULL; it = it->getNext()) { + for (sllnode * it = act_list->begin();it != NULL;it = it->getNext()) { ModelAction * act = it->getVal(); FuncInst * func_inst = get_inst(act); void * loc = act->get_location(); @@ -221,7 +221,7 @@ void FuncNode::update_tree(action_list_t * act_list) // print_predicate_tree(); } -/** +/** * @brief Link FuncInsts in inst_list - add one FuncInst to another's predecessors and successors * @param inst_list A list of FuncInsts */ @@ -338,16 +338,16 @@ void FuncNode::update_predicate_tree(action_list_t * act_list) } /* Given curr_pred and next_inst, find the branch following curr_pred that - * contains next_inst and the correct predicate. + * contains next_inst and the correct predicate. * @return true if branch found, false otherwise. */ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, - ModelAction * next_act, SnapVector * unset_predicates) + ModelAction * next_act, SnapVector * unset_predicates) { /* Check if a branch with func_inst and corresponding predicate exists */ bool branch_found = false; ModelVector * branches = (*curr_pred)->get_children(); - for (uint i = 0; i < branches->size(); i++) { + for (uint i = 0;i < branches->size();i++) { Predicate * branch = (*branches)[i]; if (branch->get_func_inst() != next_inst) continue; @@ -369,33 +369,33 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, bool equality; switch(pred_expression->token) { - case NOPREDICATE: - predicate_correct = true; - break; - case EQUALITY: - FuncInst * to_be_compared; - ModelAction * last_act; - - to_be_compared = pred_expression->func_inst; - last_act = to_be_compared->get_associated_act(marker); - - last_read = last_act->get_reads_from_value(); - next_read = next_act->get_reads_from_value(); - equality = (last_read == next_read); - if (equality != pred_expression->value) - predicate_correct = false; - - break; - case NULLITY: - next_read = next_act->get_reads_from_value(); - equality = ((void*)next_read == NULL); - if (equality != pred_expression->value) - predicate_correct = false; - break; - default: + case NOPREDICATE: + predicate_correct = true; + break; + case EQUALITY: + FuncInst * to_be_compared; + ModelAction * last_act; + + to_be_compared = pred_expression->func_inst; + last_act = to_be_compared->get_associated_act(marker); + + last_read = last_act->get_reads_from_value(); + next_read = next_act->get_reads_from_value(); + equality = (last_read == next_read); + if (equality != pred_expression->value) + predicate_correct = false; + + break; + case NULLITY: + next_read = next_act->get_reads_from_value(); + equality = ((void*)next_read == NULL); + if (equality != pred_expression->value) predicate_correct = false; - model_print("unkown predicate token\n"); - break; + break; + default: + predicate_correct = false; + model_print("unkown predicate token\n"); + break; } } @@ -411,8 +411,8 @@ bool FuncNode::follow_branch(Predicate ** curr_pred, FuncInst * next_inst, /* Infer predicate expressions, which are generated in FuncNode::generate_predicates */ void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, - HashTable * loc_act_map, - SnapVector * half_pred_expressions) + HashTable * loc_act_map, + SnapVector * half_pred_expressions) { void * loc = next_act->get_location(); @@ -423,7 +423,7 @@ void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, FuncInst * last_inst = get_inst(last_act); struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst); half_pred_expressions->push_back(expression); - } else if ( next_inst->is_single_location() ){ + } else if ( next_inst->is_single_location() ) { loc_set_t * loc_may_equal = loc_may_equal_map->get(loc); if (loc_may_equal != NULL) { @@ -457,7 +457,7 @@ void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, /* Able to generate complex predicates when there are multiple predciate expressions */ void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst, - SnapVector * half_pred_expressions) + SnapVector * half_pred_expressions) { if (half_pred_expressions->size() == 0) { Predicate * new_pred = new Predicate(next_inst); @@ -485,11 +485,11 @@ void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst, predicates[0]->add_predicate_expr(half_expr->token, half_expr->func_inst, true); predicates[1]->add_predicate_expr(half_expr->token, half_expr->func_inst, false); - for (uint i = 1; i < half_pred_expressions->size(); i++) { + for (uint i = 1;i < half_pred_expressions->size();i++) { half_expr = (*half_pred_expressions)[i]; uint old_size = predicates.size(); - for (uint j = 0; j < old_size; j++) { + for (uint j = 0;j < old_size;j++) { Predicate * pred = predicates[j]; Predicate * new_pred = new Predicate(next_inst); new_pred->copy_predicate_expr(pred); @@ -501,14 +501,14 @@ void FuncNode::generate_predicates(Predicate ** curr_pred, FuncInst * next_inst, } } - for (uint i = 0; i < predicates.size(); i++) { + for (uint i = 0;i < predicates.size();i++) { Predicate * pred= predicates[i]; (*curr_pred)->add_child(pred); pred->set_parent(*curr_pred); } /* Free memories allocated by infer_predicate */ - for (uint i = 0; i < half_pred_expressions->size(); i++) { + for (uint i = 0;i < half_pred_expressions->size();i++) { struct half_pred_expr * tmp = (*half_pred_expressions)[i]; snapshot_free(tmp); } @@ -625,7 +625,7 @@ void FuncNode::init_inst_act_map(thread_id_t tid) uint new_size = thread_id + 1; thrd_inst_act_map->resize(new_size); - for (uint i = old_size; i < new_size; i++) + for (uint i = old_size;i < new_size;i++) (*thrd_inst_act_map)[i] = new inst_act_map_t(128); } } @@ -701,7 +701,7 @@ int FuncNode::compute_distance(FuncNode * target, int max_step) ModelList * outEdges = curr->get_out_edges(); mllnode * it; - for (it = outEdges->begin(); it != NULL; it = it->getNext()) { + for (it = outEdges->begin();it != NULL;it = it->getNext()) { FuncNode * out_node = it->getVal(); /* This node has not been visited before */ @@ -730,18 +730,18 @@ void FuncNode::print_predicate_tree() void FuncNode::print_val_loc_map() { /* - value_set_iter * val_it = values_may_read_from->iterator(); - while (val_it->hasNext()) { - uint64_t value = val_it->next(); - model_print("val %llx: ", value); - - loc_set_t * locations = val_loc_map->get(value); - loc_set_iter * loc_it = locations->iterator(); - while (loc_it->hasNext()) { - void * location = loc_it->next(); - model_print("%p ", location); - } - model_print("\n"); - } -*/ + value_set_iter * val_it = values_may_read_from->iterator(); + while (val_it->hasNext()) { + uint64_t value = val_it->next(); + model_print("val %llx: ", value); + + loc_set_t * locations = val_loc_map->get(value); + loc_set_iter * loc_it = locations->iterator(); + while (loc_it->hasNext()) { + void * location = loc_it->next(); + model_print("%p ", location); + } + model_print("\n"); + } + */ } diff --git a/funcnode.h b/funcnode.h index ea591a2e..9e3bc69d 100644 --- a/funcnode.h +++ b/funcnode.h @@ -120,4 +120,4 @@ private: ModelList out_edges; }; -#endif /* __FUNCNODE_H__ */ +#endif /* __FUNCNODE_H__ */ diff --git a/hashfunction.cc b/hashfunction.cc index b41dc032..8cb1b6c9 100644 --- a/hashfunction.cc +++ b/hashfunction.cc @@ -1,13 +1,13 @@ #include "hashfunction.h" -/** +/** * Hash function for 64-bit integers * https://gist.github.com/badboy/6267743#64-bit-to-32-bit-hash-functions */ unsigned int int64_hash(uint64_t key) { - key = (~key) + (key << 18); // key = (key << 18) - key - 1; + key = (~key) + (key << 18); // key = (key << 18) - key - 1; key = key ^ (key >> 31); - key = key * 21; // key = (key + (key << 2)) + (key << 4); + key = key * 21; // key = (key + (key << 2)) + (key << 4); key = key ^ (key >> 11); key = key + (key << 6); key = key ^ (key >> 22); diff --git a/history.cc b/history.cc index afd1f1d1..e48f1c8d 100644 --- a/history.cc +++ b/history.cc @@ -31,7 +31,7 @@ ModelHistory::ModelHistory() : 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]; } @@ -51,7 +51,7 @@ void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid) 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); @@ -104,7 +104,7 @@ void ModelHistory::exit_function(const uint32_t func_id, thread_id_t 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 + /* 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(); @@ -136,7 +136,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); @@ -169,7 +169,7 @@ 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); } @@ -305,7 +305,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 +334,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) { @@ -374,7 +374,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 +383,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); @@ -411,7 +411,7 @@ void ModelHistory::remove_waiting_thread(thread_id_t tid) } 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); @@ -473,10 +473,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) { @@ -535,7 +535,7 @@ void ModelHistory::monitor_waiting_thread_counter(thread_id_t tid) /* 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 +544,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 +561,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(); diff --git a/include/predicatetypes.h b/include/predicatetypes.h index 5b03829a..737a0996 100644 --- a/include/predicatetypes.h +++ b/include/predicatetypes.h @@ -60,5 +60,5 @@ struct concrete_pred_expr { SNAPSHOTALLOC }; -#endif /* __PREDICATE_TYPES_H__ */ +#endif /* __PREDICATE_TYPES_H__ */ diff --git a/newfuzzer.cc b/newfuzzer.cc index e76d8961..c7d70ac6 100644 --- a/newfuzzer.cc +++ b/newfuzzer.cc @@ -68,7 +68,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set //model_print("the %d read action of thread %d at %p is unsuccessful\n", read->get_seq_number(), read_thread->get_id(), read->get_location()); SnapVector * pruned_writes = thrd_pruned_writes[thread_id]; - for (uint i = 0; i < pruned_writes->size(); i++) { + for (uint i = 0;i < pruned_writes->size();i++) { rf_set->push_back( (*pruned_writes)[i] ); } @@ -91,7 +91,7 @@ int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set } void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_inst, - inst_act_map_t * inst_act_map, SnapVector * rf_set) + inst_act_map_t * inst_act_map, SnapVector * rf_set) { ASSERT(!rf_set->empty()); if (curr_pred == NULL || read_inst == NULL) @@ -100,7 +100,7 @@ void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_in ModelVector * children = curr_pred->get_children(); /* Iterate over all predicate children */ - for (uint i = 0; i < children->size(); i++) { + for (uint i = 0;i < children->size();i++) { Predicate * branch = (*children)[i]; /* The children predicates may have different FuncInsts */ @@ -114,7 +114,7 @@ void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_in branch->incr_total_checking_count(); /* Iterate over all write actions */ - for (uint j = 0; j < rf_set->size(); j++) { + for (uint j = 0;j < rf_set->size();j++) { ModelAction * write_act = (*rf_set)[j]; uint64_t write_val = write_act->get_write_value(); bool dummy = true; @@ -132,7 +132,7 @@ void NewFuzzer::check_store_visibility(Predicate * curr_pred, FuncInst * read_in } -/* Select a random branch from the children of curr_pred +/* Select a random branch from the children of curr_pred * @return The selected branch */ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst) @@ -149,7 +149,7 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func ModelVector * children = curr_pred->get_children(); SnapVector branches; - for (uint i = 0; i < children->size(); i++) { + for (uint i = 0;i < children->size();i++) { Predicate * child = (*children)[i]; if (child->get_func_inst() == read_inst && !failed_predicates.contains(child)) { branches.push_back(child); @@ -186,39 +186,39 @@ Predicate * NewFuzzer::selectBranch(thread_id_t tid, Predicate * curr_pred, Func * * Note: (1) c_i + 1 is used because counts may be 0. * (2) The numerator of f_i is chosen to reduce the effect of underflow - * + * * @param numerator is M defined above */ int NewFuzzer::choose_index(SnapVector * branches, uint32_t numerator) { return random() % branches->size(); /*-- - if (branches->size() == 1) - return 0; - - double total_factor = 0; - SnapVector factors = SnapVector( branches->size() + 1 ); - for (uint i = 0; i < branches->size(); i++) { - Predicate * branch = (*branches)[i]; - double factor = (double) numerator / (branch->get_expl_count() + 5 * branch->get_fail_count() + 1); - total_factor += factor; - factors.push_back(factor); - } - - double prob = (double) random() / RAND_MAX; - double prob_sum = 0; - int index = 0; - - for (uint i = 0; i < factors.size(); i++) { - index = i; - prob_sum += (double) (factors[i] / total_factor); - if (prob_sum > prob) { - break; - } - } - - return index; -*/ + if (branches->size() == 1) + return 0; + + double total_factor = 0; + SnapVector factors = SnapVector( branches->size() + 1 ); + for (uint i = 0; i < branches->size(); i++) { + Predicate * branch = (*branches)[i]; + double factor = (double) numerator / (branch->get_expl_count() + 5 * branch->get_fail_count() + 1); + total_factor += factor; + factors.push_back(factor); + } + + double prob = (double) random() / RAND_MAX; + double prob_sum = 0; + int index = 0; + + for (uint i = 0; i < factors.size(); i++) { + index = i; + prob_sum += (double) (factors[i] / total_factor); + if (prob_sum > prob) { + break; + } + } + + return index; + */ } Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid) @@ -230,13 +230,13 @@ Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid) return thrd_selected_child_branch[thread_id]; } -/* Remove writes from the rf_set that do not satisfie the selected predicate, +/* Remove writes from the rf_set that do not satisfie the selected predicate, * and store them in thrd_pruned_writes * * @return true if rf_set is pruned */ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, - SnapVector * rf_set, inst_act_map_t * inst_act_map) + SnapVector * rf_set, inst_act_map_t * inst_act_map) { if (pred == NULL) return false; @@ -250,7 +250,7 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, if (thrd_pruned_writes.size() <= (uint) thread_id) { uint new_size = thread_id + 1; thrd_pruned_writes.resize(new_size); - for (uint i = old_size; i < new_size; i++) + for (uint i = old_size;i < new_size;i++) thrd_pruned_writes[i] = new SnapVector(); } SnapVector * pruned_writes = thrd_pruned_writes[thread_id]; @@ -281,7 +281,7 @@ bool NewFuzzer::prune_writes(thread_id_t tid, Predicate * pred, return pruned; } -/* @brief Put a thread to sleep because no writes in rf_set satisfies the selected predicate. +/* @brief Put a thread to sleep because no writes in rf_set satisfies the selected predicate. * * @param thread A thread whose last action is a read */ @@ -318,15 +318,15 @@ bool NewFuzzer::should_conditional_sleep(Predicate * predicate) { return false; /* - int sleep_score = predicate->get_sleep_score(); - int random_num = random() % 100; + int sleep_score = predicate->get_sleep_score(); + int random_num = random() % 100; - // should sleep if random_num falls within [0, sleep_score) - if (random_num < sleep_score) - return true; + // should sleep if random_num falls within [0, sleep_score) + if (random_num < sleep_score) + return true; - return false; - */ + return false; + */ } bool NewFuzzer::has_paused_threads() @@ -370,9 +370,9 @@ void NewFuzzer::wake_up_paused_threads(int * threadlist, int * numthreads) (*numthreads)++; /*-- - Predicate * selected_branch = get_selected_child_branch(tid); - update_predicate_score(selected_branch, SLEEP_FAIL_TYPE3); -*/ + Predicate * selected_branch = get_selected_child_branch(tid); + update_predicate_score(selected_branch, SLEEP_FAIL_TYPE3); + */ model_print("thread %d is woken up\n", tid); } @@ -396,9 +396,9 @@ void NewFuzzer::notify_paused_thread(Thread * thread) history->remove_waiting_thread(tid); /*-- - Predicate * selected_branch = get_selected_child_branch(tid); - update_predicate_score(selected_branch, SLEEP_SUCCESS); -*/ + Predicate * selected_branch = get_selected_child_branch(tid); + update_predicate_score(selected_branch, SLEEP_SUCCESS); + */ model_print("** thread %d is woken up\n", tid); } @@ -417,9 +417,9 @@ bool NewFuzzer::find_threads(ModelAction * pending_read) bool finds_waiting_for = false; SnapVector * func_node_list = history->getWrFuncNodes(location); - for (uint i = 0; i < func_node_list->size(); i++) { + for (uint i = 0;i < func_node_list->size();i++) { FuncNode * target_node = (*func_node_list)[i]; - for (uint i = 1; i < execution->get_num_threads(); i++) { + for (uint i = 1;i < execution->get_num_threads();i++) { thread_id_t tid = int_to_id(i); if (tid == self_id) continue; @@ -452,36 +452,36 @@ bool NewFuzzer::find_threads(ModelAction * pending_read) */ /*-- -void NewFuzzer::update_predicate_score(Predicate * predicate, sleep_result_t type) -{ - switch (type) { - case SLEEP_FAIL_TYPE1: - predicate->incr_fail_count(); - - // Do not choose this predicate when reselecting a new branch - failed_predicates.put(predicate, true); - break; - case SLEEP_FAIL_TYPE2: - predicate->incr_fail_count(); - predicate->incr_sleep_score(1); - failed_predicates.put(predicate, true); - break; - case SLEEP_FAIL_TYPE3: - predicate->incr_fail_count(); - predicate->decr_sleep_score(10); - break; - case SLEEP_SUCCESS: - predicate->incr_sleep_score(10); - break; - default: - model_print("unknown predicate result type.\n"); - break; - } -} -*/ + void NewFuzzer::update_predicate_score(Predicate * predicate, sleep_result_t type) + { + switch (type) { + case SLEEP_FAIL_TYPE1: + predicate->incr_fail_count(); + + // Do not choose this predicate when reselecting a new branch + failed_predicates.put(predicate, true); + break; + case SLEEP_FAIL_TYPE2: + predicate->incr_fail_count(); + predicate->incr_sleep_score(1); + failed_predicates.put(predicate, true); + break; + case SLEEP_FAIL_TYPE3: + predicate->incr_fail_count(); + predicate->decr_sleep_score(10); + break; + case SLEEP_SUCCESS: + predicate->incr_sleep_score(10); + break; + default: + model_print("unknown predicate result type.\n"); + break; + } + } + */ bool NewFuzzer::check_predicate_expressions(PredExprSet * pred_expressions, - inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate) + inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate) { bool satisfy_predicate = true; @@ -491,30 +491,30 @@ bool NewFuzzer::check_predicate_expressions(PredExprSet * pred_expressions, bool equality; switch (expression->token) { - case NOPREDICATE: - *no_predicate = true; - break; - case EQUALITY: - FuncInst * to_be_compared; - ModelAction * last_act; - uint64_t last_read; - - to_be_compared = expression->func_inst; - last_act = inst_act_map->get(to_be_compared); - last_read = last_act->get_reads_from_value(); - - equality = (write_val == last_read); - if (equality != expression->value) - satisfy_predicate = false; - break; - case NULLITY: - equality = ((void*)write_val == NULL); - if (equality != expression->value) - satisfy_predicate = false; - break; - default: - model_print("unknown predicate token\n"); - break; + case NOPREDICATE: + *no_predicate = true; + break; + case EQUALITY: + FuncInst * to_be_compared; + ModelAction * last_act; + uint64_t last_read; + + to_be_compared = expression->func_inst; + last_act = inst_act_map->get(to_be_compared); + last_read = last_act->get_reads_from_value(); + + equality = (write_val == last_read); + if (equality != expression->value) + satisfy_predicate = false; + break; + case NULLITY: + equality = ((void*)write_val == NULL); + if (equality != expression->value) + satisfy_predicate = false; + break; + default: + model_print("unknown predicate token\n"); + break; } if (!satisfy_predicate) diff --git a/newfuzzer.h b/newfuzzer.h index 63d88de7..76f13ce6 100644 --- a/newfuzzer.h +++ b/newfuzzer.h @@ -8,7 +8,7 @@ #include "predicate.h" struct node_dist_info { - node_dist_info(thread_id_t tid, FuncNode * node, int distance) : + node_dist_info(thread_id_t tid, FuncNode * node, int distance) : tid(tid), target(node), dist(distance) @@ -71,4 +71,4 @@ private: bool check_predicate_expressions(PredExprSet * pred_expressions, inst_act_map_t * inst_act_map, uint64_t write_val, bool * no_predicate); }; -#endif /* end of __NEWFUZZER_H__ */ +#endif /* end of __NEWFUZZER_H__ */ diff --git a/pipe.cc b/pipe.cc index b915c792..95a9a439 100644 --- a/pipe.cc +++ b/pipe.cc @@ -8,18 +8,18 @@ static int (*pipe_init_p)(int filep[2]) = NULL; int pipe(int fildes[2]) { - if (!model) { - snapshot_system_init(10000, 1024, 1024, 40000); - model = new ModelChecker(); - model->startChecker(); - } - if (!pipe_init_p) { - pipe_init_p = (int (*)(int fildes[2])) dlsym(RTLD_NEXT, "pipe"); - char *error = dlerror(); - if (error != NULL) { - fputs(error, stderr); - exit(EXIT_FAILURE); - } - } - return pipe_init_p(fildes); + if (!model) { + snapshot_system_init(10000, 1024, 1024, 40000); + model = new ModelChecker(); + model->startChecker(); + } + if (!pipe_init_p) { + pipe_init_p = (int (*)(int fildes[2]))dlsym(RTLD_NEXT, "pipe"); + char *error = dlerror(); + if (error != NULL) { + fputs(error, stderr); + exit(EXIT_FAILURE); + } + } + return pipe_init_p(fildes); } diff --git a/predicate.cc b/predicate.cc index 51b216dd..1fd1d949 100644 --- a/predicate.cc +++ b/predicate.cc @@ -27,7 +27,7 @@ Predicate::~Predicate() unsigned int pred_expr_hash(struct pred_expr * expr) { - return (unsigned int)((uintptr_t)expr); + return (unsigned int)((uintptr_t)expr); } bool pred_expr_equal(struct pred_expr * p1, struct pred_expr * p2) @@ -76,20 +76,20 @@ ConcretePredicate * Predicate::evaluate(inst_act_map_t * inst_act_map, thread_id uint64_t value = 0; switch(ptr->token) { - case NOPREDICATE: - break; - case EQUALITY: - FuncInst * to_be_compared; - ModelAction * last_act; - - to_be_compared = ptr->func_inst; - last_act = inst_act_map->get(to_be_compared); - value = last_act->get_reads_from_value(); - break; - case NULLITY: - break; - default: - break; + case NOPREDICATE: + break; + case EQUALITY: + FuncInst * to_be_compared; + ModelAction * last_act; + + to_be_compared = ptr->func_inst; + last_act = inst_act_map->get(to_be_compared); + value = last_act->get_reads_from_value(); + break; + case NULLITY: + break; + default: + break; } concrete->add_expression(ptr->token, value, ptr->value); @@ -121,17 +121,17 @@ void Predicate::print_predicate() struct pred_expr * expr = it->next(); FuncInst * inst = expr->func_inst; switch (expr->token) { - case NOPREDICATE: - break; - case EQUALITY: - model_print("predicate token: equality, position: %s, value: %d\n", inst->get_position(), expr->value); - break; - case NULLITY: - model_print("predicate token: nullity, value: %d\n", expr->value); - break; - default: - model_print("unknown predicate token\n"); - break; + case NOPREDICATE: + break; + case EQUALITY: + model_print("predicate token: equality, position: %s, value: %d\n", inst->get_position(), expr->value); + break; + case NULLITY: + model_print("predicate token: nullity, value: %d\n", expr->value); + break; + default: + model_print("unknown predicate token\n"); + break; } } @@ -148,7 +148,7 @@ void Predicate::print_predicate() void Predicate::print_pred_subtree() { print_predicate(); - for (uint i = 0; i < children.size(); i++) { + for (uint i = 0;i < children.size();i++) { Predicate * child = children[i]; child->print_pred_subtree(); model_print("\"%p\" -> \"%p\"\n", this, child); diff --git a/predicate.h b/predicate.h index 3e1867fd..2fdd6c59 100644 --- a/predicate.h +++ b/predicate.h @@ -73,4 +73,4 @@ private: PredSet backedges; }; -#endif /* __PREDICATE_H__ */ +#endif /* __PREDICATE_H__ */ diff --git a/pthread.cc b/pthread.cc index 4b5e3d37..b5fb7ce9 100644 --- a/pthread.cc +++ b/pthread.cc @@ -15,7 +15,7 @@ #include int pthread_create(pthread_t *t, const pthread_attr_t * attr, - pthread_start_t start_routine, void * arg) { + pthread_start_t start_routine, void * arg) { if (!model) { snapshot_system_init(10000, 1024, 1024, 40000); model = new ModelChecker(); @@ -133,7 +133,7 @@ int pthread_mutex_unlock(pthread_mutex_t *p_mutex) { } int pthread_mutex_timedlock (pthread_mutex_t *__restrict p_mutex, - const struct timespec *__restrict abstime) { + const struct timespec *__restrict abstime) { // timedlock just gives the option of giving up the lock, so return and let the scheduler decide which thread goes next if (!model) { @@ -194,7 +194,7 @@ int pthread_cond_wait(pthread_cond_t *p_cond, pthread_mutex_t *p_mutex) { } int pthread_cond_timedwait(pthread_cond_t *p_cond, - pthread_mutex_t *p_mutex, const struct timespec *abstime) { + pthread_mutex_t *p_mutex, const struct timespec *abstime) { ModelExecution *execution = model->get_execution(); if ( !execution->getCondMap()->contains(p_cond) ) diff --git a/schedule.cc b/schedule.cc index f68786a8..31db9c8f 100644 --- a/schedule.cc +++ b/schedule.cc @@ -206,7 +206,7 @@ Thread * Scheduler::select_next_thread() int thread_list[enabled_len], sleep_list[enabled_len]; Thread * thread; - for (int i = 0; i < enabled_len; i++) { + for (int i = 0;i < enabled_len;i++) { if (enabled[i] == THREAD_ENABLED) thread_list[avail_threads++] = i; else if (enabled[i] == THREAD_SLEEP_SET) diff --git a/sleeps.cc b/sleeps.cc index becc98c8..789a1019 100644 --- a/sleeps.cc +++ b/sleeps.cc @@ -13,13 +13,13 @@ unsigned int sleep(unsigned int seconds) { /* https://code.woboq.org/userspace/glibc/sysdeps/posix/sleep.c.html */ const unsigned int max - = (unsigned int) (((unsigned long int) (~((time_t) 0))) >> 1); + = (unsigned int) (((unsigned long int) (~((time_t) 0))) >> 1); struct timespec ts = { 0, 0 }; do { if (sizeof (ts.tv_sec) <= sizeof (seconds)) { /* Since SECONDS is unsigned assigning the value to .tv_sec can - overflow it. In this case we have to wait in steps. */ + overflow it. In this case we have to wait in steps. */ ts.tv_sec += MIN (seconds, max); seconds -= (unsigned int) ts.tv_sec; } else { diff --git a/waitobj.cc b/waitobj.cc index 39b47afc..0d1853c8 100644 --- a/waitobj.cc +++ b/waitobj.cc @@ -15,10 +15,10 @@ WaitObj::WaitObj(thread_id_t tid) : WaitObj::~WaitObj() { - for (uint i = 0; i < thrd_dist_maps.size(); i++) + 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++) + for (uint i = 0;i < thrd_target_nodes.size();i++) delete thrd_target_nodes[i]; } @@ -107,7 +107,7 @@ dist_map_t * WaitObj::getDistMap(thread_id_t tid) if (old_size <= thread_id) { thrd_dist_maps.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_dist_maps[i] = new dist_map_t(16); } } @@ -122,7 +122,7 @@ node_set_t * WaitObj::getTargetNodes(thread_id_t tid) if (old_size <= thread_id) { thrd_target_nodes.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_target_nodes[i] = new node_set_t(16); } } @@ -189,7 +189,7 @@ void WaitObj::print_waiting_for(bool verbose) if (verbose) { /* Print out the distances from each thread to target nodes */ model_print("\t"); - for (uint i = 0; i < thrd_target_nodes.size(); i++) { + for (uint i = 0;i < thrd_target_nodes.size();i++) { dist_map_t * dist_map = getDistMap(i); node_set_t * node_set = getTargetNodes(i); node_set_iter * node_iter = node_set->iterator(); @@ -197,7 +197,7 @@ void WaitObj::print_waiting_for(bool verbose) if (!node_set->isEmpty()) { model_print("[thread %d](", int_to_id(i)); - while (node_iter->hasNext()){ + while (node_iter->hasNext()) { FuncNode * node = node_iter->next(); int dist = dist_map->get(node); model_print("node %d: %d, ", node->get_func_id(), dist);