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 printf.o
+ sleeps.o history.o funcnode.o printf.o
CPPFLAGS += -Iinclude -I.
LDFLAGS := -ldl -lrt -rdynamic
#ifndef CLASSLIST_H
#define CLASSLIST_H
+#include <inttypes.h>
#include "stl-model.h"
class ClockVector;
class Thread;
class TraceAnalysis;
class Fuzzer;
+class FuncNode;
+class FuncInst;
struct model_snapshot_members;
struct bug_message;
typedef SnapList<ModelAction *> action_list_t;
+typedef SnapList<uint32_t> func_id_list_t;
extern volatile int forklock;
#endif
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<const char *> * 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);
}
#include "datarace.h"
#include "threads-model.h"
#include "bugmessage.h"
+#include "history.h"
#include "fuzzer.h"
#define INITIAL_THREAD_ID 0
thrd_last_action(1),
thrd_last_fence_release(),
priv(new struct model_snapshot_members ()),
- mo_graph(new CycleGraph()),
- fuzzer(new Fuzzer())
+ mo_graph(new CycleGraph()),
+ fuzzer(new Fuzzer()),
+ thrd_func_list(),
+ thrd_func_inst_lists()
{
/* Initialize a model-checker thread, for special ModelActions */
model_thread = new Thread(get_next_id());
}
//otherwise fall into the lock case
case ATOMIC_LOCK: {
- if (curr->get_cv()->getClock(state->alloc_tid) <= state->alloc_clock)
- assert_bug("Lock access before initialization");
+ //TODO: FIND SOME BETTER WAY TO CHECK LOCK INITIALIZED OR NOT
+ //if (curr->get_cv()->getClock(state->alloc_tid) <= state->alloc_clock)
+ // assert_bug("Lock access before initialization");
state->locked = get_thread(curr);
ModelAction *unlock = get_last_unlock(curr);
//synchronize with the previous unlock statement
*/
void ModelExecution::process_write(ModelAction *curr)
{
-
w_modification_order(curr);
-
-
get_thread(curr)->set_return_value(VALUE_NONE);
}
curr = check_current_action(curr);
ASSERT(curr);
+ // model_print("poitner loc: %p, thread: %d, type: %d, order: %d, position: %s\n", curr, curr->get_tid(), curr->get_type(), curr->get_mo(), curr->get_position() );
+ model->get_history()->add_func_atomic( curr, curr_thrd->get_id() );
+
if (curr_thrd->is_blocked() || curr_thrd->is_complete())
scheduler->remove_thread(curr_thrd);
HashTable<pthread_mutex_t *, cdsc::snapmutex *, uintptr_t, 4> * getMutexMap() {return &mutex_map;}
ModelAction * check_current_action(ModelAction *curr);
+ SnapVector<func_id_list_t *> * get_thrd_func_list() { return &thrd_func_list; }
+ SnapVector< SnapList<func_inst_list_t *> *> * get_thrd_func_inst_lists() { return &thrd_func_inst_lists; }
+
SNAPSHOTALLOC
private:
int get_execution_number() const;
Fuzzer * fuzzer;
Thread * action_select_next_thread(const ModelAction *curr) const;
+
+ /* 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
+ *
+ * This data structure is handled by ModelHistory
+ */
+ SnapVector< func_id_list_t * > thrd_func_list;
+
+ /* Keeps track of atomic actions that thread i has performed in some
+ * function. Index of SnapVector is thread id. SnapList simulates
+ * the call stack.
+ *
+ * This data structure is handled by ModelHistory
+ */
+ SnapVector< SnapList< func_inst_list_t *> *> thrd_func_inst_lists;
};
#endif /* __EXECUTION_H__ */
--- /dev/null
+#include "funcinst.h"
+
+FuncInst::FuncInst(ModelAction *act) :
+ collisions()
+{
+ ASSERT(act);
+ this->position = act->get_position();
+ this->location = act->get_location();
+ this->type = act->get_type();
+}
+
+bool FuncInst::add_pred(FuncInst * other) {
+ func_inst_list_mt::iterator it;
+ for (it = predecessors.begin(); it != predecessors.end(); it++) {
+ FuncInst * inst = *it;
+ if (inst == other)
+ return false;
+ }
+
+ predecessors.push_back(other);
+ return true;
+}
+
+bool FuncInst::add_succ(FuncInst * other) {
+ func_inst_list_mt::iterator it;
+ for (it = successors.begin(); it != successors.end(); it++) {
+ FuncInst * inst = *it;
+ if ( inst == other )
+ return false;
+ }
+
+ successors.push_back(other);
+ return true;
+}
+
+FuncInst * FuncInst::search_in_collision(ModelAction *act) {
+ action_type type = act->get_type();
+
+ func_inst_list_mt::iterator it;
+ for (it = collisions.begin(); it != collisions.end(); it++) {
+ FuncInst * inst = *it;
+ if ( inst->get_type() == type )
+ return inst;
+ }
+ return NULL;
+}
--- /dev/null
+#include "action.h"
+#include "hashtable.h"
+
+class ModelAction;
+
+typedef ModelList<FuncInst *> func_inst_list_mt;
+
+class FuncInst {
+public:
+ FuncInst(ModelAction *act);
+ ~FuncInst();
+
+ //ModelAction * get_action() const { return action; }
+ const char * get_position() const { return position; }
+ void * get_location() const { return location; }
+ action_type get_type() const { return type; }
+
+ bool add_pred(FuncInst * other);
+ bool add_succ(FuncInst * other);
+
+ FuncInst * search_in_collision(ModelAction *act);
+
+ func_inst_list_mt * get_collisions() { return &collisions; }
+ func_inst_list_mt * get_preds() { return &predecessors; }
+ func_inst_list_mt * get_succs() { return &successors; }
+
+ MEMALLOC
+private:
+ //ModelAction * const action;
+ const char * position;
+ void *location;
+ action_type type;
+
+ func_inst_list_mt collisions;
+ func_inst_list_mt predecessors;
+ func_inst_list_mt successors;
+};
--- /dev/null
+#include "funcnode.h"
+
+FuncNode::FuncNode() :
+ func_insts(),
+ inst_list(),
+ entry_insts()
+{}
+
+FuncInst * FuncNode::get_or_add_action(ModelAction *act)
+{
+ ASSERT(act);
+
+ const char * position = act->get_position();
+
+ /* Actions THREAD_CREATE, THREAD_START, THREAD_YIELD, THREAD_JOIN,
+ * THREAD_FINISH, PTHREAD_CREATE, PTHREAD_JOIN,
+ * ATOMIC_LOCK, ATOMIC_TRYLOCK, and ATOMIC_UNLOCK are not tagged with their
+ * source line numbers
+ */
+ if (position == NULL) {
+ return NULL;
+ }
+
+ if ( func_insts.contains(position) ) {
+ FuncInst * inst = func_insts.get(position);
+
+ if (inst->get_type() != act->get_type() ) {
+ // model_print("action with a different type occurs at line number %s\n", position);
+ FuncInst * func_inst = inst->search_in_collision(act);
+
+ if (func_inst != NULL) {
+ // return the FuncInst found in the collision list
+ return func_inst;
+ }
+
+ func_inst = new FuncInst(act);
+ inst->get_collisions()->push_back(func_inst);
+ inst_list.push_back(func_inst); // delete?
+ // model_print("collision added\n");
+
+ return func_inst;
+ }
+
+ return inst;
+ }
+
+ FuncInst * func_inst = new FuncInst(act);
+ func_insts.put(position, func_inst);
+
+ inst_list.push_back(func_inst);
+ return func_inst;
+}
--- /dev/null
+#include "action.h"
+#include "funcinst.h"
+#include "hashtable.h"
+
+class ModelAction;
+
+typedef ModelList<FuncInst *> func_inst_list_mt;
+
+class FuncNode {
+public:
+ FuncNode();
+ ~FuncNode();
+
+ FuncInst * get_or_add_action(ModelAction *act);
+
+ HashTable<const char *, FuncInst *, uintptr_t, 4, model_malloc, model_calloc, model_free> * getFuncInsts() { return &func_insts; }
+ func_inst_list_mt * get_inst_list() { return &inst_list; }
+
+ 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; }
+
+ MEMALLOC
+private:
+ uint32_t func_id;
+ const char * func_name;
+
+ /* Use source line number as the key of hashtable, to check if
+ * atomic operation with this line number has been added or not
+ *
+ * To do: cds_atomic_compare_exchange contains three atomic operations
+ * that are feeded with the same source line number by llvm pass
+ */
+ HashTable<const char *, FuncInst *, uintptr_t, 4, model_malloc, model_calloc, model_free> func_insts;
+
+ /* list of all atomic instructions in this function */
+ func_inst_list_mt inst_list;
+
+ /* possible entry (atomic) instructions in this function */
+ func_inst_list_mt entry_insts;
+};
#include <inttypes.h>
#include "history.h"
#include "action.h"
+#include "funcnode.h"
+#include "common.h"
+#include "model.h"
+#include "execution.h"
+
+
+/** @brief Constructor */
ModelHistory::ModelHistory() :
- func_id(1), /* function id starts with 1 */
+ func_counter(0), /* function id starts with 0 */
func_map(),
- func_history(),
- work_list()
+ func_map_rev(),
+ func_atomics()
{}
void ModelHistory::enter_function(const uint32_t func_id, thread_id_t tid)
{
- if ( !work_list.contains(tid) ) {
- // This thread has not been pushed to work_list
- SnapList<uint32_t> * func_list = new SnapList<uint32_t>();
- func_list->push_back(func_id);
- work_list.put(tid, func_list);
- } else {
- SnapList<uint32_t> * func_list = work_list.get(tid);
- func_list->push_back(func_id);
+ //model_print("thread %d entering func %d\n", tid, func_id);
+ uint32_t id = id_to_int(tid);
+ SnapVector<func_id_list_t *> * thrd_func_list = model->get_execution()->get_thrd_func_list();
+ SnapVector< SnapList<func_inst_list_t *> *> *
+ thrd_func_inst_lists = model->get_execution()->get_thrd_func_inst_lists();
+
+ if ( thrd_func_list->size() <= id ) {
+ thrd_func_list->resize( id + 1 );
+ thrd_func_inst_lists->resize( id + 1 );
}
+
+ func_id_list_t * func_list = thrd_func_list->at(id);
+ SnapList<func_inst_list_t *> * func_inst_lists = thrd_func_inst_lists->at(id);
+
+ if (func_list == NULL) {
+ func_list = new func_id_list_t();
+ thrd_func_list->at(id) = func_list;
+ }
+
+ if (func_inst_lists == NULL) {
+ func_inst_lists = new SnapList< func_inst_list_t *>();
+ thrd_func_inst_lists->at(id) = func_inst_lists;
+ }
+
+ func_list->push_back(func_id);
+ func_inst_lists->push_back( new func_inst_list_t() );
}
void ModelHistory::exit_function(const uint32_t func_id, thread_id_t tid)
{
- SnapList<uint32_t> * func_list = work_list.get(tid);
+ uint32_t id = id_to_int(tid);
+ SnapVector<func_id_list_t *> * thrd_func_list = model->get_execution()->get_thrd_func_list();
+ SnapVector< SnapList<func_inst_list_t *> *> *
+ thrd_func_inst_lists = model->get_execution()->get_thrd_func_inst_lists();
+
+ func_id_list_t * func_list = thrd_func_list->at(id);
+ SnapList<func_inst_list_t *> * func_inst_lists = thrd_func_inst_lists->at(id);
+
uint32_t last_func_id = func_list->back();
if (last_func_id == func_id) {
func_list->pop_back();
+
+ func_inst_list_t * curr_inst_list = func_inst_lists->back();
+ link_insts(curr_inst_list);
+
+ func_inst_lists->pop_back();
} else {
model_print("trying to exit with a wrong function id\n");
model_print("--- last_func: %d, func_id: %d\n", last_func_id, func_id);
}
+ //model_print("thread %d exiting func %d\n", tid, func_id);
+}
+
+void ModelHistory::add_func_atomic(ModelAction *act, thread_id_t tid)
+{
+ /* return if thread i has not entered any function or has exited
+ from all functions */
+ SnapVector<func_id_list_t *> * thrd_func_list = model->get_execution()->get_thrd_func_list();
+ SnapVector< SnapList<func_inst_list_t *> *> *
+ thrd_func_inst_lists = model->get_execution()->get_thrd_func_inst_lists();
+
+ uint32_t id = id_to_int(tid);
+ if ( thrd_func_list->size() <= id )
+ return;
+ else if (thrd_func_list->at(id) == NULL)
+ return;
+
+ /* get the function id that thread i is currently in */
+ func_id_list_t * func_list = thrd_func_list->at(id);
+ SnapList<func_inst_list_t *> * func_inst_lists = thrd_func_inst_lists->at(id);
+
+ uint32_t func_id = func_list->back();
+
+ if ( func_atomics.size() <= func_id )
+ func_atomics.resize( func_id + 1 );
+
+ FuncNode * func_node = func_atomics[func_id];
+ if (func_node == NULL) {
+ const char * func_name = func_map_rev[func_id];
+ func_node = new FuncNode();
+ func_node->set_func_id(func_id);
+ func_node->set_func_name(func_name);
+
+ func_atomics[func_id] = func_node;
+ }
+
+ FuncInst * inst = func_node->get_or_add_action(act);
+ if (inst != NULL) {
+ func_inst_list_t * curr_inst_list = func_inst_lists->back();
+
+ ASSERT(curr_inst_list != NULL);
+ curr_inst_list->push_back(inst);
+ }
+}
+
+/* Link FuncInsts in a list - add one FuncInst to another's predecessors and successors */
+void ModelHistory::link_insts(func_inst_list_t * inst_list)
+{
+ if (inst_list == NULL)
+ return;
+
+ func_inst_list_t::iterator it = inst_list->begin();
+ func_inst_list_t::iterator prev = inst_list->end();
+ it++;
+
+ while (it != inst_list->end()) {
+ prev = it;
+ prev--;
+
+ FuncInst * prev_inst = *prev;
+ FuncInst * curr_inst = *it;
+
+ prev_inst->add_succ(curr_inst);
+ curr_inst->add_pred(prev_inst);
+
+ it++;
+ }
+}
+
+void ModelHistory::print()
+{
+ for (uint32_t i = 0; i < func_atomics.size(); i++ ) {
+ FuncNode * funcNode = func_atomics[i];
+ func_inst_list_mt * inst_list = funcNode->get_inst_list();
+
+ if (funcNode == NULL)
+ continue;
+
+ model_print("function %s has following actions\n", funcNode->get_func_name());
+ func_inst_list_mt::iterator it;
+ for (it = inst_list->begin(); it != inst_list->end(); it++) {
+ FuncInst *inst = *it;
+ model_print("type: %d, at: %s\n", inst->get_type(), inst->get_position());
+ }
+ }
}
#include "stl-model.h"
#include "common.h"
#include "hashtable.h"
-#include "modeltypes.h"
-
-/* forward declaration */
-class ModelAction;
-
-typedef ModelList<ModelAction *> action_mlist_t;
+#include "threads-model.h"
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_id; }
- void incr_func_counter() { func_id++; }
+ uint32_t get_func_counter() { return func_counter; }
+ void incr_func_counter() { func_counter++; }
+
+ void add_func_atomic(ModelAction *act, thread_id_t tid);
- HashTable<const char *, uint32_t, uintptr_t, 4> * getFuncMap() { return &func_map; }
- HashTable<uint32_t, action_mlist_t *, uintptr_t, 4> * getFuncHistory() { return &func_history; }
+ HashTable<const char *, uint32_t, uintptr_t, 4, model_malloc, model_calloc, model_free> * getFuncMap() { return &func_map; }
+ ModelVector<const char *> * getFuncMapRev() { return &func_map_rev; }
+ ModelVector<FuncNode *> * getFuncAtomics() { return &func_atomics; }
+
+ void link_insts(func_inst_list_t * inst_list);
void print();
+
MEMALLOC
private:
- uint32_t func_id;
-
- /* map function names to integer ids */
- HashTable<const char *, uint32_t, uintptr_t, 4> func_map;
+ uint32_t func_counter;
- HashTable<uint32_t, action_mlist_t *, uintptr_t, 4> func_history;
+ /* map function names to integer ids */
+ HashTable<const char *, uint32_t, uintptr_t, 4, model_malloc, model_calloc, model_free> func_map;
+ /* map integer ids to function names */
+ ModelVector<const char *> func_map_rev;
- /* work_list stores a list of function ids for each thread
- * SnapList<uint32_t> is intended to be used as a stack storing
- * the functions that thread i has entered and yet to exit from
- */
- HashTable<thread_id_t, SnapList<uint32_t> *, uintptr_t, 4> work_list;
+ ModelVector<FuncNode *> func_atomics;
};
projects / c11tester.git / commitdiff