From 6b01d1c06ef2c3f9313196bd9fa7e905bfbdfde1 Mon Sep 17 00:00:00 2001 From: weiyu Date: Tue, 8 Dec 2020 11:50:48 -0800 Subject: [PATCH] remove unused code --- Makefile | 4 +- cmodelint.cc | 43 -- concretepredicate.cc | 11 - concretepredicate.h | 27 -- config.h | 4 +- execution.cc | 12 - funcinst.cc | 128 ------ funcinst.h | 82 ---- funcnode.cc | 894 --------------------------------------- funcnode.h | 146 ------- history.cc | 531 ----------------------- history.h | 95 ----- include/predicatetypes.h | 64 --- model.cc | 5 +- model.h | 2 - newfuzzer.cc | 446 ------------------- newfuzzer.h | 69 --- predicate.cc | 192 --------- predicate.h | 91 ---- waitobj.cc | 232 ---------- waitobj.h | 57 --- 21 files changed, 7 insertions(+), 3128 deletions(-) delete mode 100644 concretepredicate.cc delete mode 100644 concretepredicate.h delete mode 100644 funcinst.cc delete mode 100644 funcinst.h delete mode 100644 funcnode.cc delete mode 100644 funcnode.h delete mode 100644 history.cc delete mode 100644 history.h delete mode 100644 include/predicatetypes.h delete mode 100644 newfuzzer.cc delete mode 100644 newfuzzer.h delete mode 100644 predicate.cc delete mode 100644 predicate.h delete mode 100644 waitobj.cc delete mode 100644 waitobj.h diff --git a/Makefile b/Makefile index 1fdbf702..dfa836a5 100644 --- a/Makefile +++ b/Makefile @@ -5,8 +5,8 @@ OBJECTS := libthreads.o schedule.o model.o threads.o librace.o action.o \ datarace.o impatomic.o cmodelint.o \ snapshot.o malloc.o mymemory.o common.o mutex.o conditionvariable.o \ context.o execution.o libannotate.o plugins.o pthread.o futex.o fuzzer.o \ - sleeps.o history.o funcnode.o funcinst.o predicate.o printf.o newfuzzer.o \ - concretepredicate.o waitobj.o hashfunction.o pipe.o epoll.o actionlist.o + sleeps.o printf.o \ + hashfunction.o pipe.o epoll.o actionlist.o CPPFLAGS += -Iinclude -I. LDFLAGS := -ldl -lrt -rdynamic -lpthread diff --git a/cmodelint.cc b/cmodelint.cc index 205ef507..9f1c9c06 100644 --- a/cmodelint.cc +++ b/cmodelint.cc @@ -4,7 +4,6 @@ #include "model.h" #include "execution.h" #include "action.h" -#include "history.h" #include "cmodelint.h" #include "snapshot-interface.h" #include "threads-model.h" @@ -283,49 +282,7 @@ void cds_atomic_thread_fence(int atomic_index, const char * position) { */ void cds_func_entry(const char * funcName) { -#ifdef NEWFUZZER - createModelIfNotExist(); - thread_id_t tid = thread_current_id(); - uint32_t func_id; - - ModelHistory *history = model->get_history(); - if ( !history->getFuncMap()->contains(funcName) ) { - // add func id to func map - func_id = history->get_func_counter(); - history->incr_func_counter(); - history->getFuncMap()->put(funcName, func_id); - - // add func id to reverse func map - ModelVector * func_map_rev = history->getFuncMapRev(); - if ( func_map_rev->size() <= func_id ) - func_map_rev->resize( func_id + 1 ); - - func_map_rev->at(func_id) = funcName; - } else { - func_id = history->getFuncMap()->get(funcName); - } - - history->enter_function(func_id, tid); -#endif } void cds_func_exit(const char * funcName) { -#ifdef NEWFUZZER - createModelIfNotExist(); - thread_id_t tid = thread_current_id(); - uint32_t func_id; - - ModelHistory *history = model->get_history(); - func_id = history->getFuncMap()->get(funcName); -/* - * func_id not found; this could happen in the case where a function calls cds_func_entry - * when the model has been defined yet, but then an atomic inside the function initializes - * the model. And then cds_func_exit is called upon the function exiting. - * - */ - if (func_id == 0) - return; - - history->exit_function(func_id, tid); -#endif } diff --git a/concretepredicate.cc b/concretepredicate.cc deleted file mode 100644 index 79643bee..00000000 --- a/concretepredicate.cc +++ /dev/null @@ -1,11 +0,0 @@ -#include "concretepredicate.h" - -ConcretePredicate::ConcretePredicate(thread_id_t tid) : - tid(tid), - expressions() -{} - -void ConcretePredicate::add_expression(token_t token, uint64_t value, bool equality) -{ - expressions.push_back(concrete_pred_expr(token, value, equality)); -} diff --git a/concretepredicate.h b/concretepredicate.h deleted file mode 100644 index 1440763a..00000000 --- a/concretepredicate.h +++ /dev/null @@ -1,27 +0,0 @@ -#ifndef __CONCRETE_PREDICATE_H__ -#define __CONCRETE_PREDICATE_H__ - -#include -#include "modeltypes.h" -#include "classlist.h" -#include "predicatetypes.h" - -class ConcretePredicate { -public: - ConcretePredicate(thread_id_t tid); - ~ConcretePredicate() {} - - void add_expression(token_t token, uint64_t value, bool equality); - SnapVector * getExpressions() { return &expressions; } - void set_location(void * loc) { location = loc; } - void * get_location() { return location; } - thread_id_t get_tid() { return tid; } - - SNAPSHOTALLOC -private: - thread_id_t tid; - void * location; - SnapVector expressions; -}; - -#endif /* __CONCRETE_PREDICATE_H */ diff --git a/config.h b/config.h index 1d0f59f6..8eaca874 100644 --- a/config.h +++ b/config.h @@ -48,7 +48,7 @@ #define SHADOWBASETABLES 4 /** Enable debugging assertions (via ASSERT()) */ -#define CONFIG_ASSERT +//#define CONFIG_ASSERT /** Enable mitigations against fork handlers that call into locks... */ #define FORK_HANDLER_HACK @@ -66,4 +66,6 @@ //#define COLLECT_STAT #define REPORT_DATA_RACES +//#define PRINT_TRACE + #endif diff --git a/execution.cc b/execution.cc index d2efaba7..9ef07120 100644 --- a/execution.cc +++ b/execution.cc @@ -14,9 +14,7 @@ #include "datarace.h" #include "threads-model.h" #include "bugmessage.h" -#include "history.h" #include "fuzzer.h" -#include "newfuzzer.h" #ifdef COLLECT_STAT static unsigned int atomic_load_count = 0; @@ -79,11 +77,7 @@ ModelExecution::ModelExecution(ModelChecker *m, Scheduler *scheduler) : thrd_last_fence_release(), priv(new struct model_snapshot_members ()), mo_graph(new CycleGraph()), -#ifdef NEWFUZZER - fuzzer(new NewFuzzer()), -#else fuzzer(new Fuzzer()), -#endif isfinished(false) { /* Initialize a model-checker thread, for special ModelActions */ @@ -384,9 +378,6 @@ ModelAction * ModelExecution::convertNonAtomicStore(void * location) { add_normal_write_to_lists(act); add_write_to_lists(act); w_modification_order(act); -#ifdef NEWFUZZER - model->get_history()->process_action(act, act->get_tid()); -#endif return act; } @@ -1750,9 +1741,6 @@ Thread * ModelExecution::take_step(ModelAction *curr) ASSERT(curr); /* Process this action in ModelHistory for records */ -#ifdef NEWFUZZER - model->get_history()->process_action( curr, curr->get_tid() ); -#endif if (curr_thrd->is_blocked() || curr_thrd->is_complete()) scheduler->remove_thread(curr_thrd); diff --git a/funcinst.cc b/funcinst.cc deleted file mode 100644 index 037f5f4b..00000000 --- a/funcinst.cc +++ /dev/null @@ -1,128 +0,0 @@ -#include "funcinst.h" -#include "model.h" - -FuncInst::FuncInst(ModelAction *act, FuncNode *func_node) : - single_location(true), - execution_number(0), - associated_reads(), - thrd_markers() -{ - ASSERT(act); - ASSERT(func_node); - this->position = act->get_position(); - this->location = act->get_location(); - this->type = act->get_type(); - this->order = act->get_mo(); - this->func_node = func_node; -} - -/* @param other Preceding FuncInst in the same execution trace - * Add other to predecessors if it has been added - * - * @return false: other is already in predecessors - * true : other is added to precedessors - */ -bool FuncInst::add_pred(FuncInst * other) -{ - mllnode * it; - for (it = predecessors.begin();it != NULL;it=it->getNext()) { - FuncInst * inst = it->getVal(); - if (inst == other) - return false; - } - - predecessors.push_back(other); - return true; -} - -bool FuncInst::add_succ(FuncInst * other) -{ - mllnode* it; - for (it = successors.begin();it != NULL;it=it->getNext()) { - FuncInst * inst = it->getVal(); - if ( inst == other ) - return false; - } - - successors.push_back(other); - return true; -} - -void FuncInst::set_associated_read(thread_id_t tid, int index, uint32_t marker, uint64_t read_val) -{ - int thread_id = id_to_int(tid); - - if (associated_reads.size() < (uint) thread_id + 1) { - int old_size = associated_reads.size(); - int new_size = thread_id + 1; - - associated_reads.resize(new_size); - thrd_markers.resize(new_size); - - for (int i = old_size;i < new_size;i++ ) { - associated_reads[i] = new ModelVector(); - thrd_markers[i] = new ModelVector(); - } - } - - ModelVector * read_values = associated_reads[thread_id]; - ModelVector * markers = thrd_markers[thread_id]; - if (read_values->size() < (uint) index + 1) { - int old_size = read_values->size(); - - for (int i = old_size;i < index + 1;i++) { - read_values->push_back(VALUE_NONE); - markers->push_back(0); - } - } - - (*read_values)[index] = read_val; - (*markers)[index] = marker; -} - -uint64_t FuncInst::get_associated_read(thread_id_t tid, int index, uint32_t marker) -{ - int thread_id = id_to_int(tid); - - if ( (*thrd_markers[thread_id])[index] == marker) - return (*associated_reads[thread_id])[index]; - else - return VALUE_NONE; -} - -/* Search the FuncInst that has the same type as act in the collision list */ -FuncInst * FuncInst::search_in_collision(ModelAction *act) -{ - action_type type = act->get_type(); - - mllnode * it; - for (it = collisions.begin();it != NULL;it = it->getNext()) { - FuncInst * inst = it->getVal(); - if (inst->get_type() == type) - return inst; - } - return NULL; -} - -void FuncInst::add_to_collision(FuncInst * inst) -{ - collisions.push_back(inst); -} - -/* Note: is_read() is equivalent to ModelAction::is_read() */ -bool FuncInst::is_read() const -{ - return type == ATOMIC_READ || type == ATOMIC_RMWR || type == ATOMIC_RMWRCAS || type == ATOMIC_RMW; -} - -/* Note: because of action type conversion in ModelExecution - * is_write() <==> pure writes (excluding rmw) */ -bool FuncInst::is_write() const -{ - return type == ATOMIC_WRITE || type == ATOMIC_RMW || type == ATOMIC_INIT || type == NONATOMIC_WRITE; -} - -void FuncInst::print() -{ - model_print("func inst - pos: %s, loc: %p, type: %d,\n", position, location, type); -} diff --git a/funcinst.h b/funcinst.h deleted file mode 100644 index c4d41eec..00000000 --- a/funcinst.h +++ /dev/null @@ -1,82 +0,0 @@ -#ifndef __FUNCINST_H__ -#define __FUNCINST_H__ - -#include "action.h" -#include "classlist.h" -#include "hashtable.h" -#include "threads-model.h" - -typedef ModelList func_inst_list_mt; - -class FuncInst { -public: - FuncInst(ModelAction *act, FuncNode *func_node); - ~FuncInst(); - - const char * get_position() const { return position; } - - void * get_location() const { return location; } - void set_location(void * loc) { location = loc; } - - action_type get_type() const { return type; } - memory_order get_mo() const { return order; } - FuncNode * get_func_node() const { return func_node; } - - bool add_pred(FuncInst * other); - bool add_succ(FuncInst * other); - - FuncInst * search_in_collision(ModelAction *act); - void add_to_collision(FuncInst * inst); - - func_inst_list_mt * get_preds() { return &predecessors; } - func_inst_list_mt * get_succs() { return &successors; } - - bool is_read() const; - bool is_write() const; - bool is_single_location() { return single_location; } - void not_single_location() { single_location = false; } - - void set_execution_number(int new_number) { execution_number = new_number; } - int get_execution_number() { return execution_number; } - - void set_associated_read(thread_id_t tid, int index, uint32_t marker, uint64_t read_val); - uint64_t get_associated_read(thread_id_t tid, int index, uint32_t marker); - - void print(); - - MEMALLOC -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. - * location only stores the memory location when this FuncInst was constructed. - */ - void * location; - - /* NOTE: for rmw actions, func_inst and act may have different - * action types because of action type conversion in ModelExecution */ - action_type type; - - memory_order order; - FuncNode * func_node; - - bool single_location; - int execution_number; - - ModelVector< ModelVector * > associated_reads; - ModelVector< ModelVector * > thrd_markers; - - /** - * Collisions store a list of FuncInsts with the same position - * but different action types. For example, - * volatile int x; x++; produces read and write - * actions with the same position. - */ - func_inst_list_mt collisions; - - func_inst_list_mt predecessors; - func_inst_list_mt successors; -}; - -#endif /* __FUNCINST_H__ */ diff --git a/funcnode.cc b/funcnode.cc deleted file mode 100644 index 55785fa8..00000000 --- a/funcnode.cc +++ /dev/null @@ -1,894 +0,0 @@ -#include "action.h" -#include "history.h" -#include "funcnode.h" -#include "funcinst.h" -#include "predicate.h" -#include "concretepredicate.h" - -#include "model.h" -#include "execution.h" -#include "newfuzzer.h" -#include - -FuncNode::FuncNode(ModelHistory * history) : - func_id(0), - func_name(NULL), - history(history), - inst_counter(1), - marker(1), - exit_count(0), - thrd_markers(), - thrd_recursion_depth(), - func_inst_map(), - inst_list(), - entry_insts(), - thrd_inst_pred_maps(), - thrd_inst_id_maps(), - thrd_loc_inst_maps(), - likely_null_set(), - thrd_predicate_tree_position(), - thrd_predicate_trace(), - edge_table(32), - out_edges() -{ - predicate_tree_entry = new Predicate(NULL, true); - predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true); - - predicate_tree_exit = new Predicate(NULL, false, true); - predicate_tree_exit->set_depth(MAX_DEPTH); - - /* Snapshot data structures below */ - read_locations = new loc_set_t(); - write_locations = new loc_set_t(); - val_loc_map = new HashTable(); - loc_may_equal_map = new HashTable(); - - //values_may_read_from = new value_set_t(); -} - -/* Reallocate snapshotted memories when new executions start */ -void FuncNode::set_new_exec_flag() -{ - read_locations = new loc_set_t(); - write_locations = new loc_set_t(); - val_loc_map = new HashTable(); - loc_may_equal_map = new HashTable(); - - //values_may_read_from = new value_set_t(); -} - -/* Check whether FuncInst with the same type, position, and location - * as act has been added to func_inst_map or not. If not, add it. - */ -void FuncNode::add_inst(ModelAction *act) -{ - ASSERT(act); - const char * position = act->get_position(); - - /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK - * actions are not tagged with their source line numbers - */ - if (position == NULL) - return; - - FuncInst * func_inst = func_inst_map.get(position); - - /* This position has not been inserted into hashtable before */ - if (func_inst == NULL) { - func_inst = create_new_inst(act); - func_inst_map.put(position, func_inst); - return; - } - - /* Volatile variables that use ++ or -- syntax may result in read and write actions with the same position */ - if (func_inst->get_type() != act->get_type()) { - FuncInst * collision_inst = func_inst->search_in_collision(act); - - if (collision_inst == NULL) { - collision_inst = create_new_inst(act); - func_inst->add_to_collision(collision_inst); - return; - } else { - func_inst = collision_inst; - } - } - - ASSERT(func_inst->get_type() == act->get_type()); - int curr_execution_number = model->get_execution_number(); - - /* Reset locations when new executions start */ - if (func_inst->get_execution_number() != curr_execution_number) { - func_inst->set_location(act->get_location()); - func_inst->set_execution_number(curr_execution_number); - } - - /* Mark the memory location of such inst as not unique */ - if (func_inst->get_location() != act->get_location()) - func_inst->not_single_location(); -} - -FuncInst * FuncNode::create_new_inst(ModelAction * act) -{ - FuncInst * func_inst = new FuncInst(act, this); - int exec_num = model->get_execution_number(); - func_inst->set_execution_number(exec_num); - - inst_list.push_back(func_inst); - - return func_inst; -} - - -/* Get the FuncInst with the same type, position, and location - * as act - * - * @return FuncInst with the same type, position, and location as act */ -FuncInst * FuncNode::get_inst(ModelAction *act) -{ - ASSERT(act); - const char * position = act->get_position(); - - /* THREAD* actions, ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK - * actions are not tagged with their source line numbers - */ - if (position == NULL) - return NULL; - - FuncInst * inst = func_inst_map.get(position); - if (inst == NULL) - return NULL; - - action_type inst_type = inst->get_type(); - action_type act_type = act->get_type(); - - if (inst_type == act_type) { - return inst; - } - /* RMWRCAS actions are converted to RMW or READ actions */ - else if (inst_type == ATOMIC_RMWRCAS && - (act_type == ATOMIC_RMW || act_type == ATOMIC_READ)) { - return inst; - } - /* Return the FuncInst in the collision list */ - else { - return inst->search_in_collision(act); - } -} - -void FuncNode::add_entry_inst(FuncInst * inst) -{ - if (inst == NULL) - return; - - mllnode * it; - for (it = entry_insts.begin();it != NULL;it = it->getNext()) { - if (inst == it->getVal()) - return; - } - - entry_insts.push_back(inst); -} - -void FuncNode::function_entry_handler(thread_id_t tid) -{ - init_marker(tid); - init_local_maps(tid); - init_predicate_tree_data_structure(tid); -} - -void FuncNode::function_exit_handler(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - - reset_local_maps(tid); - - thrd_recursion_depth[thread_id]--; - thrd_markers[thread_id]->pop_back(); - - Predicate * exit_pred = get_predicate_tree_position(tid); - if (exit_pred->get_exit() == NULL) { - // Exit predicate is unset yet - exit_pred->set_exit(predicate_tree_exit); - } - - update_predicate_tree_weight(tid); - reset_predicate_tree_data_structure(tid); - - exit_count++; - //model_print("exit count: %d\n", exit_count); - -// print_predicate_tree(); -} - -/** - * @brief Convert ModelAdtion list to FuncInst list - * @param act_list A list of ModelActions - */ -void FuncNode::update_tree(ModelAction * act) -{ - bool should_process = act->is_read() || act->is_write(); - if (!should_process) - return; - - HashTable * write_history = history->getWriteHistory(); - - /* build inst_list from act_list for later processing */ -// func_inst_list_t inst_list; - - FuncInst * func_inst = get_inst(act); - void * loc = act->get_location(); - - if (func_inst == NULL) - return; - -// inst_list.push_back(func_inst); - - if (act->is_write()) { - if (!write_locations->contains(loc)) { - write_locations->add(loc); - history->update_loc_wr_func_nodes_map(loc, this); - } - } - - if (act->is_read()) { - /* If func_inst may only read_from a single location, then: - * - * The first time an action reads from some location, - * import all the values that have been written to this - * location from ModelHistory and notify ModelHistory - * that this FuncNode may read from this location. - */ - if (!read_locations->contains(loc) && func_inst->is_single_location()) { - read_locations->add(loc); - value_set_t * write_values = write_history->get(loc); - add_to_val_loc_map(write_values, loc); - history->update_loc_rd_func_nodes_map(loc, this); - } - - // Keep a has-been-zero-set record - if ( likely_reads_from_null(act) ) - likely_null_set.put(func_inst, true); - } - -// update_inst_tree(&inst_list); TODO - - update_predicate_tree(act); -} - -/** - * @brief Link FuncInsts in inst_list - add one FuncInst to another's predecessors and successors - * @param inst_list A list of FuncInsts - */ -void FuncNode::update_inst_tree(func_inst_list_t * inst_list) -{ - if (inst_list == NULL) - return; - else if (inst_list->size() == 0) - return; - - /* start linking */ - sllnode* it = inst_list->begin(); - sllnode* prev; - - /* add the first instruction to the list of entry insts */ - FuncInst * entry_inst = it->getVal(); - add_entry_inst(entry_inst); - - it = it->getNext(); - while (it != NULL) { - prev = it->getPrev(); - - FuncInst * prev_inst = prev->getVal(); - FuncInst * curr_inst = it->getVal(); - - prev_inst->add_succ(curr_inst); - curr_inst->add_pred(prev_inst); - - it = it->getNext(); - } -} - -void FuncNode::update_predicate_tree(ModelAction * next_act) -{ - thread_id_t tid = next_act->get_tid(); - int thread_id = id_to_int(tid); - uint32_t this_marker = thrd_markers[thread_id]->back(); - int recursion_depth = thrd_recursion_depth[thread_id]; - - loc_inst_map_t * loc_inst_map = thrd_loc_inst_maps[thread_id]->back(); - inst_pred_map_t * inst_pred_map = thrd_inst_pred_maps[thread_id]->back(); - inst_id_map_t * inst_id_map = thrd_inst_id_maps[thread_id]->back(); - - Predicate * curr_pred = get_predicate_tree_position(tid); - NewFuzzer * fuzzer = (NewFuzzer *)model->get_execution()->getFuzzer(); - Predicate * selected_branch = fuzzer->get_selected_child_branch(tid); - - bool amended; - while (true) { - FuncInst * next_inst = get_inst(next_act); - - Predicate * unset_predicate = NULL; - bool branch_found = follow_branch(&curr_pred, next_inst, next_act, &unset_predicate); - - // A branch with unset predicate expression is detected - if (!branch_found && unset_predicate != NULL) { - amended = amend_predicate_expr(curr_pred, next_inst, next_act); - if (amended) - continue; - else { - curr_pred = unset_predicate; - branch_found = true; - } - } - - // Detect loops - if (!branch_found && inst_id_map->contains(next_inst)) { - FuncInst * curr_inst = curr_pred->get_func_inst(); - uint32_t curr_id = inst_id_map->get(curr_inst); - uint32_t next_id = inst_id_map->get(next_inst); - - if (curr_id >= next_id) { - Predicate * old_pred = inst_pred_map->get(next_inst); - Predicate * back_pred = old_pred->get_parent(); - - // Add to the set of backedges - curr_pred->add_backedge(back_pred); - curr_pred = back_pred; - - continue; - } - } - - // Generate new branches - if (!branch_found) { - SnapVector half_pred_expressions; - infer_predicates(next_inst, next_act, &half_pred_expressions); - generate_predicates(curr_pred, next_inst, &half_pred_expressions); - continue; - } - - if (next_act->is_write()) { - curr_pred->set_write(true); - } - - if (next_act->is_read()) { - /* Only need to store the locations of read actions */ - loc_inst_map->put(next_act->get_location(), next_inst); - } - - inst_pred_map->put(next_inst, curr_pred); - set_predicate_tree_position(tid, curr_pred); - - if (!inst_id_map->contains(next_inst)) - inst_id_map->put(next_inst, inst_counter++); - - curr_pred->incr_expl_count(); - add_predicate_to_trace(tid, curr_pred); - if (next_act->is_read()) - next_inst->set_associated_read(tid, recursion_depth, this_marker, next_act->get_reads_from_value()); - - break; - } - - // A check - if (next_act->is_read()) { -// if (selected_branch != NULL && !amended) -// ASSERT(selected_branch == curr_pred); - } -} - -/* Given curr_pred and next_inst, find the branch following curr_pred that - * 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, Predicate ** unset_predicate) -{ - /* Check if a branch with func_inst and corresponding predicate exists */ - bool branch_found = false; - thread_id_t tid = next_act->get_tid(); - - ModelVector * branches = (*curr_pred)->get_children(); - for (uint i = 0;i < branches->size();i++) { - Predicate * branch = (*branches)[i]; - if (branch->get_func_inst() != next_inst) - continue; - - /* Check against predicate expressions */ - bool predicate_correct = true; - PredExprSet * pred_expressions = branch->get_pred_expressions(); - - /* Only read and rmw actions my have unset predicate expressions */ - if (pred_expressions->getSize() == 0) { - predicate_correct = false; - - if (*unset_predicate == NULL) - *unset_predicate = branch; - else - ASSERT(false); - - continue; - } - - PredExprSetIter * pred_expr_it = pred_expressions->iterator(); - while (pred_expr_it->hasNext()) { - pred_expr * pred_expression = pred_expr_it->next(); - uint64_t last_read, next_read; - bool equality; - - switch(pred_expression->token) { - case NOPREDICATE: - predicate_correct = true; - break; - case EQUALITY: - FuncInst * to_be_compared; - to_be_compared = pred_expression->func_inst; - - last_read = get_associated_read(tid, to_be_compared); - if (last_read == VALUE_NONE) - predicate_correct = false; - // ASSERT(last_read != VALUE_NONE); - - next_read = next_act->get_reads_from_value(); - equality = (last_read == next_read); - if (equality != pred_expression->value) - predicate_correct = false; - - break; - case NULLITY: - // TODO: implement likely to be null - equality = likely_reads_from_null(next_act); - if (equality != pred_expression->value) - predicate_correct = false; - break; - default: - predicate_correct = false; - model_print("unkown predicate token\n"); - break; - } - } - - delete pred_expr_it; - - if (predicate_correct) { - *curr_pred = branch; - branch_found = true; - break; - } - } - - return branch_found; -} - -/* Infer predicate expressions, which are generated in FuncNode::generate_predicates */ -void FuncNode::infer_predicates(FuncInst * next_inst, ModelAction * next_act, - SnapVector * half_pred_expressions) -{ - void * loc = next_act->get_location(); - int thread_id = id_to_int(next_act->get_tid()); - loc_inst_map_t * loc_inst_map = thrd_loc_inst_maps[thread_id]->back(); - - if (next_inst->is_read()) { - /* read + rmw */ - if ( loc_inst_map->contains(loc) ) { - FuncInst * last_inst = loc_inst_map->get(loc); - 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() ) { - loc_set_t * loc_may_equal = loc_may_equal_map->get(loc); - - if (loc_may_equal != NULL) { - loc_set_iter * loc_it = loc_may_equal->iterator(); - while (loc_it->hasNext()) { - void * neighbor = loc_it->next(); - if (loc_inst_map->contains(neighbor)) { - FuncInst * last_inst = loc_inst_map->get(neighbor); - - struct half_pred_expr * expression = new half_pred_expr(EQUALITY, last_inst); - half_pred_expressions->push_back(expression); - } - } - - delete loc_it; - } - } - - // next_inst is not single location and has been null - bool likely_null = likely_null_set.contains(next_inst); - if ( !next_inst->is_single_location() && likely_null ) { - struct half_pred_expr * expression = new half_pred_expr(NULLITY, NULL); - half_pred_expressions->push_back(expression); - } - } else { - /* Pure writes */ - // TODO: do anything here? - } -} - -/* 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) -{ - if (half_pred_expressions->size() == 0) { - Predicate * new_pred = new Predicate(next_inst); - curr_pred->add_child(new_pred); - new_pred->set_parent(curr_pred); - - /* entry predicates and predicates containing pure write actions - * have no predicate expressions */ - if ( curr_pred->is_entry_predicate() ) - new_pred->add_predicate_expr(NOPREDICATE, NULL, true); - else if (next_inst->is_write()) { - /* next_inst->is_write() <==> pure writes */ - new_pred->add_predicate_expr(NOPREDICATE, NULL, true); - } - - return; - } - - SnapVector predicates; - - struct half_pred_expr * half_expr = (*half_pred_expressions)[0]; - predicates.push_back(new Predicate(next_inst)); - predicates.push_back(new Predicate(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++) { - half_expr = (*half_pred_expressions)[i]; - - uint old_size = predicates.size(); - 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); - - pred->add_predicate_expr(half_expr->token, half_expr->func_inst, true); - new_pred->add_predicate_expr(half_expr->token, half_expr->func_inst, false); - - predicates.push_back(new_pred); - } - } - - 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++) { - struct half_pred_expr * tmp = (*half_pred_expressions)[i]; - snapshot_free(tmp); - } -} - -/* Amend predicates that contain no predicate expressions. Currenlty only amend with NULLITY predicates */ -bool FuncNode::amend_predicate_expr(Predicate * curr_pred, FuncInst * next_inst, ModelAction * next_act) -{ - ModelVector * children = curr_pred->get_children(); - - Predicate * unset_pred = NULL; - for (uint i = 0;i < children->size();i++) { - Predicate * child = (*children)[i]; - if (child->get_func_inst() == next_inst) { - unset_pred = child; - break; - } - } - - bool likely_null = likely_null_set.contains(next_inst); - - // only generate NULLITY predicate when it is actually NULL. - if ( !next_inst->is_single_location() && likely_null ) { - Predicate * new_pred = new Predicate(next_inst); - - curr_pred->add_child(new_pred); - new_pred->set_parent(curr_pred); - - unset_pred->add_predicate_expr(NULLITY, NULL, false); - new_pred->add_predicate_expr(NULLITY, NULL, true); - - return true; - } - - return false; -} - -void FuncNode::add_to_val_loc_map(uint64_t val, void * loc) -{ - loc_set_t * locations = val_loc_map->get(val); - - if (locations == NULL) { - locations = new loc_set_t(); - val_loc_map->put(val, locations); - } - - update_loc_may_equal_map(loc, locations); - locations->add(loc); - // values_may_read_from->add(val); -} - -void FuncNode::add_to_val_loc_map(value_set_t * values, void * loc) -{ - if (values == NULL) - return; - - value_set_iter * it = values->iterator(); - while (it->hasNext()) { - 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) -{ - if ( old_locations->contains(new_loc) ) - return; - - loc_set_t * neighbors = loc_may_equal_map->get(new_loc); - - if (neighbors == NULL) { - neighbors = new loc_set_t(); - loc_may_equal_map->put(new_loc, neighbors); - } - - loc_set_iter * loc_it = old_locations->iterator(); - while (loc_it->hasNext()) { - // new_loc: { old_locations, ... } - void * member = loc_it->next(); - neighbors->add(member); - - // for each i in old_locations, i : { new_loc, ... } - loc_set_t * _neighbors = loc_may_equal_map->get(member); - if (_neighbors == NULL) { - _neighbors = new loc_set_t(); - loc_may_equal_map->put(member, _neighbors); - } - _neighbors->add(new_loc); - } - - delete loc_it; -} - -bool FuncNode::likely_reads_from_null(ModelAction * read) -{ - uint64_t read_val = read->get_reads_from_value(); - if ( (void *)(read_val && 0xffffffff) == NULL ) - return true; - - return false; -} - -void FuncNode::set_predicate_tree_position(thread_id_t tid, Predicate * pred) -{ - int thread_id = id_to_int(tid); - ModelVector * stack = thrd_predicate_tree_position[thread_id]; - (*stack)[stack->size() - 1] = pred; -} - -/* @return The position of a thread in a predicate tree */ -Predicate * FuncNode::get_predicate_tree_position(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - return thrd_predicate_tree_position[thread_id]->back(); -} - -void FuncNode::add_predicate_to_trace(thread_id_t tid, Predicate * pred) -{ - int thread_id = id_to_int(tid); - thrd_predicate_trace[thread_id]->back()->push_back(pred); -} - -void FuncNode::init_marker(thread_id_t tid) -{ - marker++; - - int thread_id = id_to_int(tid); - int old_size = thrd_markers.size(); - - if (old_size < thread_id + 1) { - thrd_markers.resize(thread_id + 1); - - for (int i = old_size;i < thread_id + 1;i++) { - thrd_markers[i] = new ModelVector(); - thrd_recursion_depth.push_back(-1); - } - } - - thrd_markers[thread_id]->push_back(marker); - thrd_recursion_depth[thread_id]++; -} - -uint64_t FuncNode::get_associated_read(thread_id_t tid, FuncInst * inst) -{ - int thread_id = id_to_int(tid); - int recursion_depth = thrd_recursion_depth[thread_id]; - uint marker = thrd_markers[thread_id]->back(); - - return inst->get_associated_read(tid, recursion_depth, marker); -} - -/* Make sure elements of maps are initialized properly when threads enter functions */ -void FuncNode::init_local_maps(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - int old_size = thrd_loc_inst_maps.size(); - - if (old_size < thread_id + 1) { - int new_size = thread_id + 1; - - thrd_loc_inst_maps.resize(new_size); - thrd_inst_id_maps.resize(new_size); - thrd_inst_pred_maps.resize(new_size); - - for (int i = old_size;i < new_size;i++) { - thrd_loc_inst_maps[i] = new ModelVector; - thrd_inst_id_maps[i] = new ModelVector; - thrd_inst_pred_maps[i] = new ModelVector; - } - } - - ModelVector * map = thrd_loc_inst_maps[thread_id]; - int index = thrd_recursion_depth[thread_id]; - - // If there are recursive calls, push more hashtables into the vector. - if (map->size() < (uint) index + 1) { - thrd_loc_inst_maps[thread_id]->push_back(new loc_inst_map_t(64)); - thrd_inst_id_maps[thread_id]->push_back(new inst_id_map_t(64)); - thrd_inst_pred_maps[thread_id]->push_back(new inst_pred_map_t(64)); - } - - ASSERT(map->size() == (uint) index + 1); -} - -/* Reset elements of maps when threads exit functions */ -void FuncNode::reset_local_maps(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - int index = thrd_recursion_depth[thread_id]; - - // When recursive call ends, keep only one hashtable in the vector - if (index > 0) { - delete thrd_loc_inst_maps[thread_id]->back(); - delete thrd_inst_id_maps[thread_id]->back(); - delete thrd_inst_pred_maps[thread_id]->back(); - - thrd_loc_inst_maps[thread_id]->pop_back(); - thrd_inst_id_maps[thread_id]->pop_back(); - thrd_inst_pred_maps[thread_id]->pop_back(); - } else { - thrd_loc_inst_maps[thread_id]->back()->reset(); - thrd_inst_id_maps[thread_id]->back()->reset(); - thrd_inst_pred_maps[thread_id]->back()->reset(); - } -} - -void FuncNode::init_predicate_tree_data_structure(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - int old_size = thrd_predicate_tree_position.size(); - - if (old_size < thread_id + 1) { - thrd_predicate_tree_position.resize(thread_id + 1); - thrd_predicate_trace.resize(thread_id + 1); - - for (int i = old_size;i < thread_id + 1;i++) { - thrd_predicate_tree_position[i] = new ModelVector(); - thrd_predicate_trace[i] = new ModelVector(); - } - } - - thrd_predicate_tree_position[thread_id]->push_back(predicate_tree_entry); - thrd_predicate_trace[thread_id]->push_back(new predicate_trace_t()); -} - -void FuncNode::reset_predicate_tree_data_structure(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - thrd_predicate_tree_position[thread_id]->pop_back(); - - // Free memories allocated in init_predicate_tree_data_structure - delete thrd_predicate_trace[thread_id]->back(); - thrd_predicate_trace[thread_id]->pop_back(); -} - -/* Add FuncNodes that this node may follow */ -void FuncNode::add_out_edge(FuncNode * other) -{ - if ( !edge_table.contains(other) ) { - edge_table.put(other, OUT_EDGE); - out_edges.push_back(other); - return; - } - - edge_type_t edge = edge_table.get(other); - if (edge == IN_EDGE) { - edge_table.put(other, BI_EDGE); - out_edges.push_back(other); - } -} - -/* Compute the distance between this FuncNode and the target node. - * Return -1 if the target node is unreachable or the actual distance - * is greater than max_step. - */ -int FuncNode::compute_distance(FuncNode * target, int max_step) -{ - if (target == NULL) - return -1; - else if (target == this) - return 0; - - // Be careful with memory - SnapList queue; - HashTable distances(128); - - queue.push_back(this); - distances.put(this, 0); - - while (!queue.empty()) { - FuncNode * curr = queue.front(); - queue.pop_front(); - int dist = distances.get(curr); - - if (max_step <= dist) - return -1; - - ModelList * outEdges = curr->get_out_edges(); - mllnode * it; - for (it = outEdges->begin();it != NULL;it = it->getNext()) { - FuncNode * out_node = it->getVal(); - - /* This node has not been visited before */ - if ( !distances.contains(out_node) ) { - if (out_node == target) - return dist + 1; - - queue.push_back(out_node); - distances.put(out_node, dist + 1); - } - } - } - - /* Target node is unreachable */ - return -1; -} - -void FuncNode::update_predicate_tree_weight(thread_id_t tid) -{ - predicate_trace_t * trace = thrd_predicate_trace[id_to_int(tid)]->back(); - - // Update predicate weights based on prediate trace - for (int i = trace->size() - 1;i >= 0;i--) { - Predicate * node = (*trace)[i]; - ModelVector * children = node->get_children(); - - if (children->size() == 0) { - double weight = 100.0 / sqrt(node->get_expl_count() + node->get_fail_count() + 1); - node->set_weight(weight); - } else { - double weight_sum = 0.0; - for (uint i = 0;i < children->size();i++) { - Predicate * child = (*children)[i]; - double weight = child->get_weight(); - weight_sum += weight; - } - - double average_weight = (double) weight_sum / (double) children->size(); - double weight = average_weight * pow(0.9, node->get_depth()); - node->set_weight(weight); - } - } -} - -void FuncNode::print_predicate_tree() -{ - model_print("digraph function_%s {\n", func_name); - predicate_tree_entry->print_pred_subtree(); - predicate_tree_exit->print_predicate(); - model_print("}\n"); // end of graph -} diff --git a/funcnode.h b/funcnode.h deleted file mode 100644 index 35f1969d..00000000 --- a/funcnode.h +++ /dev/null @@ -1,146 +0,0 @@ -#ifndef __FUNCNODE_H__ -#define __FUNCNODE_H__ - -#include "hashset.h" -#include "hashfunction.h" -#include "classlist.h" -#include "threads-model.h" - -#define MAX_DIST 10 - -typedef ModelList func_inst_list_mt; -typedef ModelVector predicate_trace_t; - -typedef HashTable loc_inst_map_t; -typedef HashTable inst_id_map_t; -typedef HashTable inst_pred_map_t; - -typedef enum edge_type { - IN_EDGE, OUT_EDGE, BI_EDGE -} edge_type_t; - -class FuncNode { -public: - FuncNode(ModelHistory * history); - ~FuncNode(); - - uint32_t get_func_id() { return func_id; } - const char * get_func_name() { return func_name; } - void set_func_id(uint32_t id) { func_id = id; } - void set_func_name(const char * name) { func_name = name; } - void set_new_exec_flag(); - - void add_inst(ModelAction *act); - FuncInst * create_new_inst(ModelAction *act); - FuncInst * get_inst(ModelAction *act); - - func_inst_list_mt * get_inst_list() { return &inst_list; } - func_inst_list_mt * get_entry_insts() { return &entry_insts; } - void add_entry_inst(FuncInst * inst); - - void function_entry_handler(thread_id_t tid); - void function_exit_handler(thread_id_t tid); - - void update_tree(ModelAction * act); - - void add_to_val_loc_map(uint64_t val, void * loc); - void add_to_val_loc_map(value_set_t * values, void * loc); - void update_loc_may_equal_map(void * new_loc, loc_set_t * old_locations); - - Predicate * get_predicate_tree_position(thread_id_t tid); - - void add_predicate_to_trace(thread_id_t tid, Predicate *pred); - - uint64_t get_associated_read(thread_id_t tid, FuncInst * inst); - - void add_out_edge(FuncNode * other); - ModelList * get_out_edges() { return &out_edges; } - int compute_distance(FuncNode * target, int max_step = MAX_DIST); - - void print_predicate_tree(); - - MEMALLOC -private: - uint32_t func_id; - const char * func_name; - ModelHistory * history; - Predicate * predicate_tree_entry; // A dummy node whose children are the real entries - Predicate * predicate_tree_exit; // A dummy node - - uint32_t inst_counter; - uint32_t marker; - uint32_t exit_count; - ModelVector< ModelVector *> thrd_markers; - ModelVector thrd_recursion_depth; // Recursion depth starts from 0 to match with vector indexes. - - void init_marker(thread_id_t tid); - - /* Use source line number as the key of hashtable, to check if - * atomic operation with this line number has been added or not - */ - HashTable func_inst_map; - - /* List of all atomic actions in this function */ - func_inst_list_mt inst_list; - - /* Possible entry atomic actions in this function */ - func_inst_list_mt entry_insts; - - /* Map a FuncInst to the its predicate when updating predicate trees */ - ModelVector< ModelVector * > thrd_inst_pred_maps; - - /* Number FuncInsts to detect loops when updating predicate trees */ - ModelVector< ModelVector *> thrd_inst_id_maps; - - /* Detect read actions at the same locations when updating predicate trees */ - ModelVector< ModelVector *> thrd_loc_inst_maps; - - void init_local_maps(thread_id_t tid); - void reset_local_maps(thread_id_t tid); - - void update_inst_tree(func_inst_list_t * inst_list); - void update_predicate_tree(ModelAction * act); - bool follow_branch(Predicate ** curr_pred, FuncInst * next_inst, ModelAction * next_act, Predicate ** unset_predicate); - - void infer_predicates(FuncInst * next_inst, ModelAction * next_act, SnapVector * half_pred_expressions); - void generate_predicates(Predicate * curr_pred, FuncInst * next_inst, SnapVector * half_pred_expressions); - bool amend_predicate_expr(Predicate * curr_pred, FuncInst * next_inst, ModelAction * next_act); - - /* Set of locations read by this FuncNode */ - loc_set_t * read_locations; - - /* Set of locations written to by this FuncNode */ - loc_set_t * write_locations; - - /* Keeps track of locations that have the same values written to */ - HashTable * val_loc_map; - - /* Keeps track of locations that may share the same value as key, deduced from val_loc_map */ - HashTable * loc_may_equal_map; - - HashTable likely_null_set; - - bool likely_reads_from_null(ModelAction * read); - // value_set_t * values_may_read_from; - - /* Run-time position in the predicate tree for each thread - * The inner vector is used to deal with recursive functions. */ - ModelVector< ModelVector * > thrd_predicate_tree_position; - - ModelVector< ModelVector * > thrd_predicate_trace; - - void set_predicate_tree_position(thread_id_t tid, Predicate * pred); - - void init_predicate_tree_data_structure(thread_id_t tid); - void reset_predicate_tree_data_structure(thread_id_t tid); - - /* Store the relation between this FuncNode and other FuncNodes */ - HashTable edge_table; - - /* FuncNodes that follow this node */ - ModelList out_edges; - - void update_predicate_tree_weight(thread_id_t tid); -}; - -#endif /* __FUNCNODE_H__ */ diff --git a/history.cc b/history.cc deleted file mode 100644 index f84af3f0..00000000 --- a/history.cc +++ /dev/null @@ -1,531 +0,0 @@ -#include -#include "history.h" -#include "action.h" -#include "funcnode.h" -#include "funcinst.h" -#include "common.h" -#include "concretepredicate.h" -#include "waitobj.h" - -#include "model.h" -#include "execution.h" -#include "newfuzzer.h" - -/** @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() -{ - /* 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_func_list = new SnapVector(); - thrd_last_entered_func = new SnapVector(); - thrd_waiting_write = new SnapVector(); - thrd_wait_obj = new SnapVector(); -} - -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); - uint id = id_to_int(tid); - - if ( thrd_func_list->size() <= id ) { - uint oldsize = thrd_func_list->size(); - thrd_func_list->resize( id + 1 ); - - 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_last_entered_func->push_back(0); - } - } - - 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 ) - resize_func_nodes( func_id + 1 ); - - FuncNode * func_node = func_nodes[func_id]; - func_node->function_entry_handler(tid); - - /* Add edges between FuncNodes */ - if (last_entered_func_id != 0) { - 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) -{ - uint32_t id = id_to_int(tid); - 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->function_exit_handler(tid); - - (*thrd_func_list)[id].pop_back(); - } else { - ASSERT(false); - } - //model_print("thread %d exiting func %d\n", tid, func_id); -} - -void ModelHistory::resize_func_nodes(uint32_t new_size) -{ - uint32_t old_size = func_nodes.size(); - - if ( old_size < new_size ) - func_nodes.resize(new_size); - - 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); - func_node->set_func_name(func_name); - func_nodes[id] = func_node; - } -} - -void ModelHistory::process_action(ModelAction *act, thread_id_t tid) -{ - 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); - - /* 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); - - /* 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); - } - - 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; - - if (skip_action(act)) - return; - - FuncNode * func_node = func_nodes[func_id]; - func_node->add_inst(act); - - func_node->update_tree(act); - last_seq_number = act->get_seq_number(); -} - -/* Return the FuncNode given its func_id */ -FuncNode * ModelHistory::get_func_node(uint32_t func_id) -{ - 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]; -} - -/* Return the current FuncNode when given a thread id */ -FuncNode * ModelHistory::get_curr_func_node(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - uint32_t func_id = (*thrd_func_list)[thread_id].back(); - - 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); - - if (write_set == NULL) { - write_set = new value_set_t(); - write_history->put(location, write_set); - } - - write_set->add(write_val); -} - -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) -{ - SnapVector * func_node_list = loc_rd_func_nodes_map->get(location); - if (func_node_list == NULL) { - func_node_list = new SnapVector(); - loc_rd_func_nodes_map->put(location, func_node_list); - } - - return func_node_list; -} - -SnapVector * ModelHistory::getWrFuncNodes(void * location) -{ - SnapVector * func_node_list = loc_wr_func_nodes_map->get(location); - if (func_node_list == NULL) { - func_node_list = new SnapVector(); - loc_wr_func_nodes_map->put(location, func_node_list); - } - - 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); - if (waiting_conditions == NULL) { - waiting_conditions = new SnapVector(); - 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()); - if (thrd_waiting_write->size() <= (uint) thread_id) { - thrd_waiting_write->resize(thread_id + 1); - } - - (*thrd_waiting_write)[thread_id] = concrete; -} - -void ModelHistory::remove_waiting_write(thread_id_t tid) -{ - ConcretePredicate * concrete = (*thrd_waiting_write)[ id_to_int(tid) ]; - void * location = concrete->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) { - (*concrete_preds)[i] = concrete_preds->back(); - concrete_preds->pop_back(); - break; - } - } - - int thread_id = id_to_int( concrete->get_tid() ); - (*thrd_waiting_write)[thread_id] = NULL; - delete concrete; -} - -/* 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); - if (concrete_preds == NULL) - return; - - uint index = 0; - while (index < concrete_preds->size()) { - ConcretePredicate * concrete_pred = (*concrete_preds)[index]; - 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++) { - 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; - } - - if (equality != concrete.equality) { - satisfy_predicate = false; - break; - } - } - - if (satisfy_predicate) { - /* Wake up threads */ - thread_id_t tid = concrete_pred->get_tid(); - Thread * thread = model->get_thread(tid); - - //model_print("** thread %d is woken up\n", thread->get_id()); - ((NewFuzzer *)model->get_execution()->getFuzzer())->notify_paused_thread(thread); - } - - index++; - } -} - -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(); - delete iter; -} - -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); - ((NewFuzzer *)execution->getFuzzer())->notify_paused_thread(thread); - } - } -} - -bool ModelHistory::skip_action(ModelAction * act) -{ - 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 (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) - 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); - } - } - - delete node_iter; - } - - delete tid_iter; -} - -void ModelHistory::monitor_waiting_thread_counter(thread_id_t tid) -{ - WaitObj * wait_obj = getWaitObj(tid); - thrd_id_set_t * waited_by = wait_obj->getWaitedBy(); - - // 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) { -// model_print("thread %d stops waiting for thread %d\n", waited_by_id, tid); - 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); - ((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++) { - FuncNode * func_node = func_nodes[i]; - func_node->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++) { - 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()) { - FuncNode * other = it->getVal(); - model_print("\"%p\" -> \"%p\"\n", node, other); - } - } - model_print("}\n"); -} - -void ModelHistory::print_func_node() -{ - /* function id starts with 1 */ - 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()); - } - */ - } -} - -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(); - } -} diff --git a/history.h b/history.h deleted file mode 100644 index 431f978e..00000000 --- a/history.h +++ /dev/null @@ -1,95 +0,0 @@ -#ifndef __HISTORY_H__ -#define __HISTORY_H__ - -#include "common.h" -#include "classlist.h" -#include "hashtable.h" -#include "threads-model.h" - -#define INIT_SEQ_NUMBER 0xffffffff - -class ModelHistory { -public: - ModelHistory(); - ~ModelHistory(); - - void enter_function(const uint32_t func_id, thread_id_t tid); - void exit_function(const uint32_t func_id, thread_id_t tid); - - uint32_t get_func_counter() { return func_counter; } - void incr_func_counter() { func_counter++; } - - void resize_func_nodes(uint32_t max_func_id); - void process_action(ModelAction *act, thread_id_t tid); - - HashTable * getFuncMap() { return &func_map; } - ModelVector * getFuncMapRev() { return &func_map_rev; } - - ModelVector * getFuncNodes() { return &func_nodes; } - FuncNode * get_func_node(uint32_t func_id); - FuncNode * get_curr_func_node(thread_id_t tid); - - void update_write_history(void * location, uint64_t write_val); - HashTable * getWriteHistory() { return write_history; } - void update_loc_rd_func_nodes_map(void * location, FuncNode * node); - void update_loc_wr_func_nodes_map(void * location, FuncNode * node); - SnapVector * getRdFuncNodes(void * location); - SnapVector * getWrFuncNodes(void * location); - - void add_waiting_write(ConcretePredicate * concrete); - void remove_waiting_write(thread_id_t tid); - void check_waiting_write(ModelAction * write_act); - SnapVector * getThrdWaitingWrite() { return thrd_waiting_write; } - - WaitObj * getWaitObj(thread_id_t tid); - void add_waiting_thread(thread_id_t self_id, thread_id_t waiting_for_id, FuncNode * target_node, int dist); - void remove_waiting_thread(thread_id_t tid); - void stop_waiting_for_node(thread_id_t self_id, thread_id_t waiting_for_id, FuncNode * target_node); - - void set_new_exec_flag(); - void dump_func_node_graph(); - void print_func_node(); - void print_waiting_threads(); - - MEMALLOC -private: - uint32_t func_counter; - modelclock_t last_seq_number; - - /* Map function names to integer ids */ - HashTable func_map; - - /* Map integer ids to function names */ - ModelVector func_map_rev; - - ModelVector func_nodes; - - /* Map a location to a set of values that have been written to it */ - HashTable * write_history; - - /* Map a location to FuncNodes that may read from it */ - HashTable *, uintptr_t, 0> * loc_rd_func_nodes_map; - - /* Map a location to FuncNodes that may write to it */ - HashTable *, uintptr_t, 0> * loc_wr_func_nodes_map; - - HashTable *, uintptr_t, 0> * loc_waiting_writes_map; - - /* thrd_func_list stores a list of function ids for each thread. - * Each element in thrd_func_list stores the functions that - * thread i has entered and yet to exit from - */ - SnapVector * thrd_func_list; - SnapVector * thrd_last_entered_func; - - /* The write values each paused thread is waiting for */ - SnapVector * thrd_waiting_write; - SnapVector * thrd_wait_obj; - - bool skip_action(ModelAction * act); - void monitor_waiting_thread(uint32_t func_id, thread_id_t tid); - void monitor_waiting_thread_counter(thread_id_t tid); - -}; - -#endif /* __HISTORY_H__ */ diff --git a/include/predicatetypes.h b/include/predicatetypes.h deleted file mode 100644 index 737a0996..00000000 --- a/include/predicatetypes.h +++ /dev/null @@ -1,64 +0,0 @@ -/** - * @file predicatetypes.h - * @brief Define common predicate expression types - */ - -#ifndef __PREDICATE_TYPES_H__ -#define __PREDICATE_TYPES_H__ - -typedef enum predicate_token { - NOPREDICATE, EQUALITY, NULLITY -} token_t; - -typedef enum predicate_sleep_result { - SLEEP_FAIL_TYPE1, SLEEP_FAIL_TYPE2, SLEEP_FAIL_TYPE3, - SLEEP_SUCCESS -} sleep_result_t; - -/* If token is EQUALITY, then the predicate asserts whether - * this load should read the same value as the last value - * read at memory location specified in predicate_expr. - */ -struct pred_expr { - pred_expr(token_t token, FuncInst * inst, bool value) : - token(token), - func_inst(inst), - value(value) - {} - - token_t token; - FuncInst * func_inst; - bool value; - - MEMALLOC -}; - -/* Used by FuncNode to generate Predicates */ -struct half_pred_expr { - half_pred_expr(token_t token, FuncInst * inst) : - token(token), - func_inst(inst) - {} - - token_t token; - FuncInst * func_inst; - - SNAPSHOTALLOC -}; - -struct concrete_pred_expr { - concrete_pred_expr(token_t token, uint64_t value, bool equality) : - token(token), - value(value), - equality(equality) - {} - - token_t token; - uint64_t value; - bool equality; - - SNAPSHOTALLOC -}; - -#endif /* __PREDICATE_TYPES_H__ */ - diff --git a/model.cc b/model.cc index f7337706..3f811d7d 100644 --- a/model.cc +++ b/model.cc @@ -15,7 +15,6 @@ #include "output.h" #include "traceanalysis.h" #include "execution.h" -#include "history.h" #include "bugmessage.h" #include "params.h" #include "plugins.h" @@ -72,7 +71,6 @@ ModelChecker::ModelChecker() : /* Initialize default scheduler */ params(), scheduler(new Scheduler()), - history(new ModelHistory()), execution(new ModelExecution(this, scheduler)), execution_number(1), curr_thread_num(MAIN_THREAD_ID), @@ -280,7 +278,9 @@ void ModelChecker::print_execution(bool printbugs) const } model_print("\n"); +#ifdef PRINT_TRACE execution->print_summary(); +#endif } /** @@ -313,7 +313,6 @@ void ModelChecker::finish_execution(bool more_executions) clear_program_output(); execution_number ++; - history->set_new_exec_flag(); if (more_executions) reset_to_initial_state(); diff --git a/model.h b/model.h index 9e52f537..d71ad8f6 100644 --- a/model.h +++ b/model.h @@ -41,7 +41,6 @@ public: void exit_model_checker(); ModelExecution * get_execution() const { return execution; } - ModelHistory * get_history() const { return history; } int get_execution_number() const { return execution_number; } @@ -70,7 +69,6 @@ private: /** The scheduler to use: tracks the running/ready Threads */ Scheduler * const scheduler; - ModelHistory * history; ModelExecution *execution; Thread * init_thread; diff --git a/newfuzzer.cc b/newfuzzer.cc deleted file mode 100644 index 76f4e4ce..00000000 --- a/newfuzzer.cc +++ /dev/null @@ -1,446 +0,0 @@ -#include "newfuzzer.h" -#include "threads-model.h" -#include "action.h" -#include "history.h" -#include "funcnode.h" -#include "funcinst.h" -#include "concretepredicate.h" -#include "waitobj.h" - -#include "model.h" -#include "schedule.h" -#include "execution.h" - -NewFuzzer::NewFuzzer() : - thrd_last_read_act(), - thrd_last_func_inst(), - available_branches_tmp_storage(), - thrd_selected_child_branch(), - thrd_pruned_writes(), - paused_thread_list(), - paused_thread_table(128), - dist_info_vec() -{} - -/** - * @brief Register the ModelHistory and ModelExecution engine - */ -void NewFuzzer::register_engine(ModelChecker *_model, ModelExecution *execution) -{ - this->history = _model->get_history(); - this->execution = execution; -} - -int NewFuzzer::selectWrite(ModelAction *read, SnapVector * rf_set) -{ - return random() % rf_set->size(); - - thread_id_t tid = read->get_tid(); - int thread_id = id_to_int(tid); - - if (thrd_last_read_act.size() <= (uint) thread_id) { - thrd_last_read_act.resize(thread_id + 1); - thrd_last_func_inst.resize(thread_id + 1); - } - - // A new read action is encountered, select a random child branch of current predicate - if (read != thrd_last_read_act[thread_id]) { - FuncNode * func_node = history->get_curr_func_node(tid); - Predicate * curr_pred = func_node->get_predicate_tree_position(tid); - FuncInst * read_inst = func_node->get_inst(read); - - if (curr_pred != NULL) { - Predicate * selected_branch = NULL; - - if (check_branch_inst(curr_pred, read_inst, rf_set)) - selected_branch = selectBranch(tid, curr_pred, read_inst); - else { - // no child of curr_pred matches read_inst, check back edges - PredSet * back_edges = curr_pred->get_backedges(); - PredSetIter * it = back_edges->iterator(); - - while (it->hasNext()) { - curr_pred = it->next(); - if (check_branch_inst(curr_pred, read_inst, rf_set)) { - selected_branch = selectBranch(tid, curr_pred, read_inst); - break; - } - } - - delete it; - } - - thrd_selected_child_branch[thread_id] = selected_branch; - prune_writes(tid, selected_branch, rf_set); - } - - thrd_last_read_act[thread_id] = read; - thrd_last_func_inst[thread_id] = read_inst; - } - - // The chosen branch fails, reselect new branches - while ( rf_set->size() == 0 ) { - Predicate * selected_branch = get_selected_child_branch(tid); - FuncNode * func_node = history->get_curr_func_node(tid); - - // Increment failure count - selected_branch->incr_fail_count(); - func_node->add_predicate_to_trace(tid, selected_branch); // For updating predicate weight - - //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++) { - rf_set->push_back( (*pruned_writes)[i] ); - } - - // Reselect a predicate and prune writes - Predicate * curr_pred = selected_branch->get_parent(); - FuncInst * read_inst = thrd_last_func_inst[thread_id]; - selected_branch = selectBranch(tid, curr_pred, read_inst); - thrd_selected_child_branch[thread_id] = selected_branch; - - prune_writes(tid, selected_branch, rf_set); - - ASSERT(selected_branch); - } - - int random_index = random() % rf_set->size(); - - return random_index; -} - -/* Check if children of curr_pred match read_inst. - * @return False if no child matches read_inst - */ -bool NewFuzzer::check_branch_inst(Predicate * curr_pred, FuncInst * read_inst, - SnapVector * rf_set) -{ - available_branches_tmp_storage.clear(); - - ASSERT(!rf_set->empty()); - if (curr_pred == NULL || read_inst == NULL) - return false; - - ModelVector * children = curr_pred->get_children(); - bool any_child_match = false; - - /* Iterate over all predicate children */ - for (uint i = 0;i < children->size();i++) { - Predicate * branch = (*children)[i]; - - /* The children predicates may have different FuncInsts */ - if (branch->get_func_inst() == read_inst) { - any_child_match = true; - branch->incr_total_checking_count(); - available_branches_tmp_storage.push_back(branch); - } - } - - return any_child_match; -} - -/* 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) -{ - int thread_id = id_to_int(tid); - if ( thrd_selected_child_branch.size() <= (uint) thread_id) - thrd_selected_child_branch.resize(thread_id + 1); - - if (curr_pred == NULL || read_inst == NULL) { - thrd_selected_child_branch[thread_id] = NULL; - return NULL; - } - - // predicate children have not been generated - if (available_branches_tmp_storage.size() == 0) { - thrd_selected_child_branch[thread_id] = NULL; - return NULL; - } - - int index = choose_branch_index(&available_branches_tmp_storage); - Predicate * selected_branch = available_branches_tmp_storage[ index ]; - - /* Remove the chosen branch from vec in case that this - * branch fails and need to choose another one */ - available_branches_tmp_storage[index] = available_branches_tmp_storage.back(); - available_branches_tmp_storage.pop_back(); - - return selected_branch; -} - -/** - * @brief Select a branch from the given predicate branch - */ -int NewFuzzer::choose_branch_index(SnapVector * branches) -{ - if (branches->size() == 1) - return 0; - - double total_weight = 0; - SnapVector weights; - for (uint i = 0;i < branches->size();i++) { - Predicate * branch = (*branches)[i]; - double weight = branch->get_weight(); - total_weight += weight; - weights.push_back(weight); - } - - double prob = (double) random() / RAND_MAX; - double prob_sum = 0; - int index = 0; - - for (uint i = 0;i < weights.size();i++) { - index = i; - prob_sum += (double) (weights[i] / total_weight); - if (prob_sum > prob) { - break; - } - } - - return index; -// return random() % branches->size(); -} - -Predicate * NewFuzzer::get_selected_child_branch(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - if (thrd_selected_child_branch.size() <= (uint) thread_id) - return NULL; - - return thrd_selected_child_branch[thread_id]; -} - -/* 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) -{ - if (pred == NULL) - return false; - - PredExprSet * pred_expressions = pred->get_pred_expressions(); - if (pred_expressions->getSize() == 0) // unset predicates - return false; - - int thread_id = id_to_int(tid); - uint old_size = thrd_pruned_writes.size(); - 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++) - thrd_pruned_writes[i] = new SnapVector(); - } - SnapVector * pruned_writes = thrd_pruned_writes[thread_id]; - pruned_writes->clear(); // clear the old pruned_writes set - - bool pruned = false; - uint rf_index = 0; - - while ( rf_index < rf_set->size() ) { - ModelAction * write_act = (*rf_set)[rf_index]; - uint64_t write_val = write_act->get_write_value(); - bool no_predicate = false; - bool satisfy_predicate = true; - - // Check if the write value satisfies the predicates - PredExprSetIter * pred_expr_it = pred_expressions->iterator(); - while (pred_expr_it->hasNext()) { - struct pred_expr * expression = pred_expr_it->next(); - bool equality; - - switch (expression->token) { - case NOPREDICATE: - no_predicate = true; - break; - case EQUALITY: - FuncInst * to_be_compared; - FuncNode * func_node; - uint64_t last_read; - - to_be_compared = expression->func_inst; - func_node = history->get_curr_func_node(tid); - last_read = func_node->get_associated_read(tid, to_be_compared); - ASSERT(last_read != VALUE_NONE); - - equality = (write_val == last_read); - if (equality != expression->value) - satisfy_predicate = false; - break; - case NULLITY: - // TODO: implement likely to be null - equality = ((void*) (write_val & 0xffffffff) == NULL); - if (equality != expression->value) - satisfy_predicate = false; - break; - default: - model_print("unknown predicate token\n"); - break; - } - - if (!satisfy_predicate) - break; - } - delete pred_expr_it; - - if (no_predicate) - return false; - - if (!satisfy_predicate) { - ASSERT(rf_set != NULL); - (*rf_set)[rf_index] = rf_set->back(); - rf_set->pop_back(); - pruned_writes->push_back(write_act); - pruned = true; - } else - rf_index++; - } - - return pruned; -} - -/* @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 - */ -void NewFuzzer::conditional_sleep(Thread * thread) -{ -/* - int index = paused_thread_list.size(); - - model->getScheduler()->add_sleep(thread); - paused_thread_list.push_back(thread); - paused_thread_table.put(thread, index); // Update table - - // Add the waiting condition to ModelHistory - ModelAction * read = thread->get_pending(); - thread_id_t tid = thread->get_id(); - FuncNode * func_node = history->get_curr_func_node(tid); - // inst_act_map_t * inst_act_map = func_node->get_inst_act_map(tid); - - Predicate * selected_branch = get_selected_child_branch(tid); - // ConcretePredicate * concrete = selected_branch->evaluate(inst_act_map, tid); - concrete->set_location(read->get_location()); - - ASSERT(false); - - // history->add_waiting_write(concrete); - // history->add_waiting_thread is already called in find_threads - */ -} - -bool NewFuzzer::has_paused_threads() -{ - return paused_thread_list.size() != 0; -} - -Thread * NewFuzzer::selectThread(int * threadlist, int numthreads) -{ - if (numthreads == 0 && has_paused_threads()) { - wake_up_paused_threads(threadlist, &numthreads); - //model_print("list size: %d, active t id: %d\n", numthreads, threadlist[0]); - } - int random_index = random() % numthreads; - int thread = threadlist[random_index]; - thread_id_t curr_tid = int_to_id(thread); - return execution->get_thread(curr_tid); -} - -/* Force waking up one of threads paused by Fuzzer, because otherwise - * the Fuzzer is not making progress - */ -void NewFuzzer::wake_up_paused_threads(int * threadlist, int * numthreads) -{ - int random_index = random() % paused_thread_list.size(); - Thread * thread = paused_thread_list[random_index]; - model->getScheduler()->remove_sleep(thread); - - Thread * last_thread = paused_thread_list.back(); - paused_thread_list[random_index] = last_thread; - paused_thread_list.pop_back(); - paused_thread_table.put(last_thread, random_index); // Update table - paused_thread_table.remove(thread); - - thread_id_t tid = thread->get_id(); - history->remove_waiting_write(tid); - history->remove_waiting_thread(tid); - - threadlist[*numthreads] = tid; - (*numthreads)++; - -/*-- - 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); -} - -/* Wake up conditional sleeping threads if the desired write is available */ -void NewFuzzer::notify_paused_thread(Thread * thread) -{ - ASSERT(paused_thread_table.contains(thread)); - - int index = paused_thread_table.get(thread); - model->getScheduler()->remove_sleep(thread); - - Thread * last_thread = paused_thread_list.back(); - paused_thread_list[index] = last_thread; - paused_thread_list.pop_back(); - paused_thread_table.put(last_thread, index); // Update table - paused_thread_table.remove(thread); - - thread_id_t tid = thread->get_id(); - history->remove_waiting_write(tid); - history->remove_waiting_thread(tid); - -/*-- - Predicate * selected_branch = get_selected_child_branch(tid); - update_predicate_score(selected_branch, SLEEP_SUCCESS); - */ - - model_print("** thread %d is woken up\n", tid); -} - -/* Find threads that may write values that the pending read action is waiting for. - * Side effect: waiting thread related info are stored in dist_info_vec - * - * @return True if any thread is found - */ -bool NewFuzzer::find_threads(ModelAction * pending_read) -{ - ASSERT(pending_read->is_read()); - - void * location = pending_read->get_location(); - thread_id_t self_id = pending_read->get_tid(); - bool finds_waiting_for = false; - - SnapVector * func_node_list = history->getWrFuncNodes(location); - 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++) { - thread_id_t tid = int_to_id(i); - if (tid == self_id) - continue; - - FuncNode * node = history->get_curr_func_node(tid); - /* It is possible that thread tid is not in any FuncNode */ - if (node == NULL) - continue; - - int distance = node->compute_distance(target_node); - if (distance != -1) { - finds_waiting_for = true; - //model_print("thread: %d; distance from node %d to node %d: %d\n", tid, node->get_func_id(), target_node->get_func_id(), distance); - - dist_info_vec.push_back(node_dist_info(tid, target_node, distance)); - } - } - } - - return finds_waiting_for; -} diff --git a/newfuzzer.h b/newfuzzer.h deleted file mode 100644 index 67454ffc..00000000 --- a/newfuzzer.h +++ /dev/null @@ -1,69 +0,0 @@ -#ifndef __NEWFUZZER_H__ -#define __NEWFUZZER_H__ - -#include "fuzzer.h" -#include "classlist.h" -#include "mymemory.h" -#include "stl-model.h" -#include "predicate.h" - -struct node_dist_info { - node_dist_info(thread_id_t tid, FuncNode * node, int distance) : - tid(tid), - target(node), - dist(distance) - {} - - thread_id_t tid; - FuncNode * target; - int dist; - - SNAPSHOTALLOC -}; - -class NewFuzzer : public Fuzzer { -public: - NewFuzzer(); - int selectWrite(ModelAction *read, SnapVector* rf_set); - bool has_paused_threads(); - void notify_paused_thread(Thread * thread); - - Thread * selectThread(int * threadlist, int numthreads); - Thread * selectNotify(simple_action_list_t * waiters); - bool shouldSleep(const ModelAction * sleep); - bool shouldWake(const ModelAction * sleep); - - void register_engine(ModelChecker * model, ModelExecution * execution); - Predicate * get_selected_child_branch(thread_id_t tid); - - SNAPSHOTALLOC -private: - ModelHistory * history; - ModelExecution * execution; - - SnapVector thrd_last_read_act; - SnapVector thrd_last_func_inst; - - SnapVector available_branches_tmp_storage; - SnapVector thrd_selected_child_branch; - SnapVector< SnapVector *> thrd_pruned_writes; - - bool check_branch_inst(Predicate * curr_pred, FuncInst * read_inst, SnapVector * rf_set); - Predicate * selectBranch(thread_id_t tid, Predicate * curr_pred, FuncInst * read_inst); - bool prune_writes(thread_id_t tid, Predicate * pred, SnapVector * rf_set); - int choose_branch_index(SnapVector * branches); - - /* The set of Threads put to sleep by NewFuzzer because no writes in rf_set satisfies the selected predicate. Only used by selectWrite. - */ - SnapVector paused_thread_list; //-- (not in use) - HashTable paused_thread_table; //-- - - SnapVector dist_info_vec; //-- - - void conditional_sleep(Thread * thread); //-- - void wake_up_paused_threads(int * threadlist, int * numthreads); //-- - - bool find_threads(ModelAction * pending_read); //-- -}; - -#endif /* end of __NEWFUZZER_H__ */ diff --git a/predicate.cc b/predicate.cc deleted file mode 100644 index 9b8060aa..00000000 --- a/predicate.cc +++ /dev/null @@ -1,192 +0,0 @@ -#include "funcinst.h" -#include "predicate.h" -#include "concretepredicate.h" - -Predicate::Predicate(FuncInst * func_inst, bool is_entry, bool is_exit) : - func_inst(func_inst), - entry_predicate(is_entry), - exit_predicate(is_exit), - does_write(false), - depth(0), - weight(100), - exploration_count(0), - store_visible_count(0), - total_checking_count(0), - pred_expressions(16), - children(), - parent(NULL), - exit(NULL), - backedges(16) -{} - -Predicate::~Predicate() -{ - // parent and func_inst should not be deleted - pred_expressions.reset(); - backedges.reset(); - children.clear(); -} - -unsigned int pred_expr_hash(struct pred_expr * expr) -{ - return (unsigned int)((uintptr_t)expr); -} - -bool pred_expr_equal(struct pred_expr * p1, struct pred_expr * p2) -{ - if (p1->token != p2->token) - return false; - if (p1->token == EQUALITY && p1->func_inst != p2->func_inst) - return false; - if (p1->value != p2->value) - return false; - return true; -} - -void Predicate::add_predicate_expr(token_t token, FuncInst * func_inst, bool value) -{ - struct pred_expr *ptr = new pred_expr(token, func_inst, value); - pred_expressions.add(ptr); -} - -void Predicate::add_child(Predicate * child) -{ - /* check duplication? */ - children.push_back(child); -} - -void Predicate::set_parent(Predicate * parent_pred) -{ - parent = parent_pred; - depth = parent_pred->get_depth() + 1; -} - -void Predicate::set_exit(Predicate * exit_pred) -{ - exit = exit_pred; -} - -void Predicate::copy_predicate_expr(Predicate * other) -{ - PredExprSet * other_pred_expressions = other->get_pred_expressions(); - PredExprSetIter * it = other_pred_expressions->iterator(); - - while (it->hasNext()) { - struct pred_expr * ptr = it->next(); - struct pred_expr * copy = new pred_expr(ptr->token, ptr->func_inst, ptr->value); - pred_expressions.add(copy); - } - - delete it; -} - -/* Evaluate predicate expressions against the given inst_act_map */ -ConcretePredicate * Predicate::evaluate(thread_id_t tid) -{ - /* - ConcretePredicate * concrete = new ConcretePredicate(tid); - PredExprSetIter * it = pred_expressions.iterator(); - - while (it->hasNext()) { - struct pred_expr * ptr = it->next(); - 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; - } - - concrete->add_expression(ptr->token, value, ptr->value); - } - - delete it; - return concrete; - */ - - return NULL; -} - -void Predicate::print_predicate() -{ - model_print("\"%p\" [shape=box, label=\"", this); - if (entry_predicate) { - model_print("entry node\"];\n"); - return; - } - - if (exit_predicate) { - model_print("exit node\"];\n"); - return; - } - - model_print("depth: %u; weight: %g\n", depth, weight); - - func_inst->print(); - - if (pred_expressions.getSize() == 0) - model_print("predicate unset\n"); - - PredExprSetIter * it = pred_expressions.iterator(); - while (it->hasNext()) { - 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; - } - } - - if (does_write) { - model_print("Does write\n"); - } - - double prob = (double) store_visible_count / total_checking_count; - model_print("Total checks: %d, visible count: %d; prob: %f\n", total_checking_count, store_visible_count, prob); - model_print("Exploration count: %d, failure count: %d", exploration_count, failure_count); - model_print("\"];\n"); - - delete it; -} - -void Predicate::print_pred_subtree() -{ - print_predicate(); - for (uint i = 0;i < children.size();i++) { - Predicate * child = children[i]; - child->print_pred_subtree(); - model_print("\"%p\" -> \"%p\"\n", this, child); - } - - PredSetIter * it = backedges.iterator(); - while (it->hasNext()) { - Predicate * backedge = it->next(); - model_print("\"%p\" -> \"%p\"[style=dashed, color=grey]\n", this, backedge); - } - - if (exit) { - model_print("\"%p\" -> \"%p\"[style=dashed, color=red]\n", this, exit); - } - - delete it; -} diff --git a/predicate.h b/predicate.h deleted file mode 100644 index cc9f714d..00000000 --- a/predicate.h +++ /dev/null @@ -1,91 +0,0 @@ -#ifndef __PREDICATE_H__ -#define __PREDICATE_H__ - -#include "hashset.h" -#include "predicatetypes.h" -#include "classlist.h" - -#define MAX_DEPTH 0x7fffffff - -unsigned int pred_expr_hash (struct pred_expr *); -bool pred_expr_equal(struct pred_expr *, struct pred_expr *); -typedef HashSet PredExprSet; -typedef HSIterator PredExprSetIter; - -class Predicate { -public: - Predicate(FuncInst * func_inst, bool is_entry = false, bool is_exit = false); - ~Predicate(); - - FuncInst * get_func_inst() { return func_inst; } - PredExprSet * get_pred_expressions() { return &pred_expressions; } - - void add_predicate_expr(token_t token, FuncInst * func_inst, bool value); - void add_child(Predicate * child); - void set_parent(Predicate * parent_pred); - void set_exit(Predicate * exit_pred); - void add_backedge(Predicate * back_pred) { backedges.add(back_pred); } - void set_weight(double weight_) { weight = weight_; } - void copy_predicate_expr(Predicate * other); - - Predicate * follow_write_child(FuncInst * inst); - ModelVector * get_children() { return &children; } - Predicate * get_parent() { return parent; } - Predicate * get_exit() { return exit; } - PredSet * get_backedges() { return &backedges; } - double get_weight() { return weight; } - - bool is_entry_predicate() { return entry_predicate; } - void set_entry_predicate() { entry_predicate = true; } - - /* Whether func_inst does write or not */ - bool is_write() { return does_write; } - void set_write(bool is_write) { does_write = is_write; } - - ConcretePredicate * evaluate(thread_id_t tid); - - uint32_t get_expl_count() { return exploration_count; } - uint32_t get_fail_count() { return failure_count; } - uint32_t get_store_visible_count() { return store_visible_count; } - uint32_t get_total_checking_count() { return total_checking_count; } - - void incr_expl_count() { exploration_count++; } - void incr_fail_count() { failure_count++; } - void incr_store_visible_count() { store_visible_count++; } - void incr_total_checking_count() { total_checking_count++; } - - uint32_t get_depth() { return depth; } - void set_depth(uint32_t depth_) { depth = depth_; } - - void print_predicate(); - void print_pred_subtree(); - - MEMALLOC -private: - FuncInst * func_inst; - bool entry_predicate; - bool exit_predicate; - bool does_write; - - /* Height of this predicate node in the predicate tree */ - uint32_t depth; - double weight; - - uint32_t exploration_count; - uint32_t failure_count; - uint32_t store_visible_count; - uint32_t total_checking_count; /* The number of times the store visibility is checked */ - - /* May have multiple predicate expressions */ - PredExprSet pred_expressions; - ModelVector children; - - /* Only a single parent may exist */ - Predicate * parent; - Predicate * exit; - - /* May have multiple back edges, e.g. nested loops */ - PredSet backedges; -}; - -#endif /* __PREDICATE_H__ */ diff --git a/waitobj.cc b/waitobj.cc deleted file mode 100644 index dc422be7..00000000 --- a/waitobj.cc +++ /dev/null @@ -1,232 +0,0 @@ -#include "waitobj.h" -#include "threads-model.h" -#include "funcnode.h" - -#define COUNTER_THRESHOLD 1000 - -WaitObj::WaitObj(thread_id_t tid) : - tid(tid), - waiting_for(32), - waited_by(32), - thrd_dist_maps(), - thrd_target_nodes(), - thrd_action_counters() -{} - -WaitObj::~WaitObj() -{ - 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++) - delete thrd_target_nodes[i]; -} - -void WaitObj::add_waiting_for(thread_id_t other, FuncNode * node, int dist) -{ - waiting_for.add(other); - - dist_map_t * dist_map = getDistMap(other); - dist_map->put(node, dist); - - node_set_t * target_nodes = getTargetNodes(other); - target_nodes->add(node); -} - -void WaitObj::add_waited_by(thread_id_t other) -{ - waited_by.add(other); -} - -/** - * Stop waiting for the thread to reach the target node - * - * @param other The thread to be removed - * @param node The target node - * @return true if "other" is removed from waiting_for set - * false if only a target node of "other" is removed - */ -bool WaitObj::remove_waiting_for_node(thread_id_t other, FuncNode * node) -{ - dist_map_t * dist_map = getDistMap(other); - dist_map->remove(node); - - node_set_t * target_nodes = getTargetNodes(other); - target_nodes->remove(node); - - /* The thread has no nodes to reach */ - if (target_nodes->isEmpty()) { - int index = id_to_int(other); - thrd_action_counters[index] = 0; - waiting_for.remove(other); - - return true; - } - - return false; -} - -/* Stop waiting for the thread */ -void WaitObj::remove_waiting_for(thread_id_t other) -{ - waiting_for.remove(other); - - // TODO: clear dist_map or not? - /* dist_map_t * dist_map = getDistMap(other); - dist_map->reset(); */ - - node_set_t * target_nodes = getTargetNodes(other); - target_nodes->reset(); - - int index = id_to_int(other); - thrd_action_counters[index] = 0; -} - -void WaitObj::remove_waited_by(thread_id_t other) -{ - waited_by.remove(other); -} - -int WaitObj::lookup_dist(thread_id_t tid, FuncNode * target) -{ - dist_map_t * map = getDistMap(tid); - node_set_t * node_set = getTargetNodes(tid); - - /* thrd_dist_maps is not reset when clear_waiting_for is called, - * so node_set should be checked */ - if (node_set->contains(target) && map->contains(target)) - return map->get(target); - - return -1; -} - -dist_map_t * WaitObj::getDistMap(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - int old_size = thrd_dist_maps.size(); - - if (old_size <= thread_id) { - thrd_dist_maps.resize(thread_id + 1); - for (int i = old_size;i < thread_id + 1;i++) { - thrd_dist_maps[i] = new dist_map_t(16); - } - } - - return thrd_dist_maps[thread_id]; -} - -node_set_t * WaitObj::getTargetNodes(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - int old_size = thrd_target_nodes.size(); - - if (old_size <= thread_id) { - thrd_target_nodes.resize(thread_id + 1); - for (int i = old_size;i < thread_id + 1;i++) { - thrd_target_nodes[i] = new node_set_t(16); - } - } - - return thrd_target_nodes[thread_id]; -} - -/** - * Increment action counter for thread tid - * @return true if the counter for tid expires - */ -bool WaitObj::incr_counter(thread_id_t tid) -{ - int thread_id = id_to_int(tid); - - /* thrd_action_counters.resize does not work here */ - while (thrd_action_counters.size() <= (uint) thread_id) { - thrd_action_counters.push_back(0); - } - - thrd_action_counters[thread_id]++; - if (thrd_action_counters[thread_id] > COUNTER_THRESHOLD) { - thrd_action_counters[thread_id] = 0; - return true; - } - - return false; -} - -void WaitObj::clear_waiting_for() -{ - thrd_id_set_iter * iter = waiting_for.iterator(); - while (iter->hasNext()) { - thread_id_t tid = iter->next(); - int index = id_to_int(tid); - thrd_action_counters[index] = 0; - - /* thrd_dist_maps are not reset because distances - * will be overwritten when node targets are added - * thrd_dist_maps[index]->reset(); */ - - node_set_t * target_nodes = getTargetNodes(tid); - target_nodes->reset(); - } - - delete iter; - - waiting_for.reset(); - /* waited_by relation should be kept */ -} - -void WaitObj::print_waiting_for(bool verbose) -{ - if (waiting_for.getSize() == 0) - return; - - model_print("thread %d is waiting for: ", tid); - thrd_id_set_iter * it = waiting_for.iterator(); - - while (it->hasNext()) { - thread_id_t waiting_for_id = it->next(); - model_print("%d ", waiting_for_id); - } - model_print("\n"); - delete it; - - 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++) { - dist_map_t * dist_map = getDistMap(i); - node_set_t * node_set = getTargetNodes(i); - node_set_iter * node_iter = node_set->iterator(); - - if (!node_set->isEmpty()) { - model_print("[thread %d](", int_to_id(i)); - - 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); - } - model_print(") "); - } - - delete node_iter; - } - model_print("\n"); - } -} - -void WaitObj::print_waited_by() -{ - if (waited_by.getSize() == 0) - return; - - model_print("thread %d is waited by: ", tid); - thrd_id_set_iter * it = waited_by.iterator(); - - while (it->hasNext()) { - thread_id_t thread_id = it->next(); - model_print("%d ", thread_id); - } - model_print("\n"); - - delete it; -} diff --git a/waitobj.h b/waitobj.h deleted file mode 100644 index 36d95796..00000000 --- a/waitobj.h +++ /dev/null @@ -1,57 +0,0 @@ -#ifndef __WAITOBJ_H__ -#define __WAITOBJ_H__ - -#include "classlist.h" -#include "modeltypes.h" - -typedef HashTable dist_map_t; -typedef HashSet node_set_t; -typedef HSIterator node_set_iter; - -class WaitObj { -public: - WaitObj(thread_id_t); - ~WaitObj(); - - thread_id_t get_tid() { return tid; } - - void add_waiting_for(thread_id_t other, FuncNode * node, int dist); - void add_waited_by(thread_id_t other); - bool remove_waiting_for_node(thread_id_t other, FuncNode * node); - void remove_waiting_for(thread_id_t other); - void remove_waited_by(thread_id_t other); - - thrd_id_set_t * getWaitingFor() { return &waiting_for; } - thrd_id_set_t * getWaitedBy() { return &waited_by; } - - node_set_t * getTargetNodes(thread_id_t tid); - int lookup_dist(thread_id_t tid, FuncNode * target); - - bool incr_counter(thread_id_t tid); - - void clear_waiting_for(); - - void print_waiting_for(bool verbose = false); - void print_waited_by(); - - SNAPSHOTALLOC -private: - thread_id_t tid; - - /* The set of threads this thread (tid) is waiting for */ - thrd_id_set_t waiting_for; - - /* The set of threads waiting for this thread */ - thrd_id_set_t waited_by; - - SnapVector thrd_dist_maps; - SnapVector thrd_target_nodes; - - /* Count the number of actions for threads that - * this thread is waiting for */ - SnapVector thrd_action_counters; - - dist_map_t * getDistMap(thread_id_t tid); -}; - -#endif -- 2.34.1