projects
/
model-checker.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
nodestack: implement expiration sloppiness parameter
[model-checker.git]
/
model.cc
diff --git
a/model.cc
b/model.cc
index 775b796f167d68ee8394a0e828b0791e122a4937..b29df05cafe86fadefa27b85c535e30eb94fd43e 100644
(file)
--- a/
model.cc
+++ b/
model.cc
@@
-208,7
+208,7
@@
Thread * ModelChecker::get_next_thread(ModelAction *curr)
return thread_map->get(id_to_int(tid));
}
return thread_map->get(id_to_int(tid));
}
-/**
+/**
* We need to know what the next actions of all threads in the sleep
* set will be. This method computes them and stores the actions at
* the corresponding thread object's pending action.
* We need to know what the next actions of all threads in the sleep
* set will be. This method computes them and stores the actions at
* the corresponding thread object's pending action.
@@
-218,7
+218,8
@@
void ModelChecker::execute_sleep_set() {
for(unsigned int i=0;i<get_num_threads();i++) {
thread_id_t tid=int_to_id(i);
Thread *thr=get_thread(tid);
for(unsigned int i=0;i<get_num_threads();i++) {
thread_id_t tid=int_to_id(i);
Thread *thr=get_thread(tid);
- if ( scheduler->get_enabled(thr) == THREAD_SLEEP_SET ) {
+ if ( scheduler->get_enabled(thr) == THREAD_SLEEP_SET &&
+ thr->get_pending() == NULL ) {
thr->set_state(THREAD_RUNNING);
scheduler->next_thread(thr);
Thread::swap(&system_context, thr);
thr->set_state(THREAD_RUNNING);
scheduler->next_thread(thr);
Thread::swap(&system_context, thr);
@@
-240,7
+241,7
@@
void ModelChecker::wake_up_sleeping_actions(ModelAction * curr) {
scheduler->remove_sleep(thr);
}
}
scheduler->remove_sleep(thr);
}
}
- }
+ }
}
/**
}
/**
@@
-271,8
+272,10
@@
bool ModelChecker::next_execution()
pending_rel_seqs->size());
pending_rel_seqs->size());
- if (isfinalfeasible() || (params.bound != 0 && priv->used_sequence_numbers > params.bound ) || DBG_ENABLED() )
+ if (isfinalfeasible() || (params.bound != 0 && priv->used_sequence_numbers > params.bound ) || DBG_ENABLED() ) {
+ checkDataRaces();
print_summary();
print_summary();
+ }
if ((diverge = get_next_backtrack()) == NULL)
return false;
if ((diverge = get_next_backtrack()) == NULL)
return false;
@@
-383,10
+386,14
@@
void ModelChecker::set_backtracking(ModelAction *act)
for(int i = low_tid; i < high_tid; i++) {
thread_id_t tid = int_to_id(i);
for(int i = low_tid; i < high_tid; i++) {
thread_id_t tid = int_to_id(i);
+ /* Make sure this thread can be enabled here. */
+ if (i >= node->get_num_threads())
+ break;
+
/* Don't backtrack into a point where the thread is disabled or sleeping. */
/* Don't backtrack into a point where the thread is disabled or sleeping. */
- if (node->
get_enabled_array()[i]
!=THREAD_ENABLED)
+ if (node->
enabled_status(tid)
!=THREAD_ENABLED)
continue;
continue;
-
+
/* Check if this has been explored already */
if (node->has_been_explored(tid))
continue;
/* Check if this has been explored already */
if (node->has_been_explored(tid))
continue;
@@
-744,41
+751,46
@@
void ModelChecker::process_relseq_fixup(ModelAction *curr, work_queue_t *work_qu
* initializing clock vectors, and computing the promises to fulfill.
*
* @param curr The current action, as passed from the user context; may be
* initializing clock vectors, and computing the promises to fulfill.
*
* @param curr The current action, as passed from the user context; may be
- * freed/invalidated after the execution of this function
- *
@return The current action, as processed by the ModelChecker. Is only the
- *
same as the parameter @a curr if this is a newly-explored action.
+ * freed/invalidated after the execution of this function
, with a different
+ *
action "returned" its place (pass-by-reference)
+ *
@return True if curr is a newly-explored action; false otherwise
*/
*/
-
ModelAction * ModelChecker::initialize_curr_action(ModelAction
*curr)
+
bool ModelChecker::initialize_curr_action(ModelAction *
*curr)
{
ModelAction *newcurr;
{
ModelAction *newcurr;
- if (
curr->is_rmwc() || curr
->is_rmw()) {
- newcurr = process_rmw(curr);
- delete curr;
+ if (
(*curr)->is_rmwc() || (*curr)
->is_rmw()) {
+ newcurr = process_rmw(
*
curr);
+ delete
*
curr;
if (newcurr->is_rmw())
compute_promises(newcurr);
if (newcurr->is_rmw())
compute_promises(newcurr);
- return newcurr;
+
+ *curr = newcurr;
+ return false;
}
}
-
curr
->set_seq_number(get_next_seq_num());
+
(*curr)
->set_seq_number(get_next_seq_num());
- newcurr = node_stack->explore_action(curr, scheduler->get_enabled());
+ newcurr = node_stack->explore_action(
*
curr, scheduler->get_enabled());
if (newcurr) {
/* First restore type and order in case of RMW operation */
if (newcurr) {
/* First restore type and order in case of RMW operation */
- if (
curr
->is_rmwr())
- newcurr->copy_typeandorder(curr);
+ if (
(*curr)
->is_rmwr())
+ newcurr->copy_typeandorder(
*
curr);
- ASSERT(
curr
->get_location() == newcurr->get_location());
- newcurr->copy_from_new(curr);
+ ASSERT(
(*curr)
->get_location() == newcurr->get_location());
+ newcurr->copy_from_new(
*
curr);
/* Discard duplicate ModelAction; use action from NodeStack */
/* Discard duplicate ModelAction; use action from NodeStack */
- delete curr;
+ delete
*
curr;
/* Always compute new clock vector */
newcurr->create_cv(get_parent_action(newcurr->get_tid()));
/* Always compute new clock vector */
newcurr->create_cv(get_parent_action(newcurr->get_tid()));
+
+ *curr = newcurr;
+ return false; /* Action was explored previously */
} else {
} else {
- newcurr = curr;
+ newcurr =
*
curr;
/* Always compute new clock vector */
newcurr->create_cv(get_parent_action(newcurr->get_tid()));
/* Always compute new clock vector */
newcurr->create_cv(get_parent_action(newcurr->get_tid()));
@@
-795,8
+807,8
@@
ModelAction * ModelChecker::initialize_curr_action(ModelAction *curr)
else if (newcurr->is_notify_one()) {
newcurr->get_node()->set_misc_max(condvar_waiters_map->get_safe_ptr(newcurr->get_location())->size());
}
else if (newcurr->is_notify_one()) {
newcurr->get_node()->set_misc_max(condvar_waiters_map->get_safe_ptr(newcurr->get_location())->size());
}
+ return true; /* This was a new ModelAction */
}
}
- return newcurr;
}
/**
}
/**
@@
-854,18
+866,17
@@
Thread * ModelChecker::check_current_action(ModelAction *curr)
return get_next_thread(NULL);
}
return get_next_thread(NULL);
}
-
ModelAction *newcurr = initialize_curr_action(
curr);
+
bool newly_explored = initialize_curr_action(&
curr);
- wake_up_sleeping_actions(
new
curr);
+ wake_up_sleeping_actions(curr);
/* Add the action to lists before any other model-checking tasks */
if (!second_part_of_rmw)
/* Add the action to lists before any other model-checking tasks */
if (!second_part_of_rmw)
- add_action_to_lists(
new
curr);
+ add_action_to_lists(curr);
/* Build may_read_from set for newly-created actions */
/* Build may_read_from set for newly-created actions */
- if (
curr == newcurr
&& curr->is_read())
+ if (
newly_explored
&& curr->is_read())
build_reads_from_past(curr);
build_reads_from_past(curr);
- curr = newcurr;
/* Initialize work_queue with the "current action" work */
work_queue_t work_queue(1, CheckCurrWorkEntry(curr));
/* Initialize work_queue with the "current action" work */
work_queue_t work_queue(1, CheckCurrWorkEntry(curr));
@@
-963,7
+974,7
@@
bool ModelChecker::promises_expired() {
/** @return whether the current partial trace must be a prefix of a
* feasible trace. */
bool ModelChecker::isfeasibleprefix() {
/** @return whether the current partial trace must be a prefix of a
* feasible trace. */
bool ModelChecker::isfeasibleprefix() {
- return promises->size() == 0 && pending_rel_seqs->size() == 0;
+ return promises->size() == 0 && pending_rel_seqs->size() == 0
&& isfeasible()
;
}
/** @return whether the current partial trace is feasible. */
}
/** @return whether the current partial trace is feasible. */
@@
-1055,7
+1066,7
@@
void ModelChecker::check_recency(ModelAction *curr, const ModelAction *rf) {
ModelAction *act = *rit;
if (!act->is_read())
return;
ModelAction *act = *rit;
if (!act->is_read())
return;
-
+
if (act->get_reads_from() != rf)
return;
if (act->get_node()->get_read_from_size() <= 1)
if (act->get_reads_from() != rf)
return;
if (act->get_node()->get_read_from_size() <= 1)
@@
-1086,7
+1097,7
@@
void ModelChecker::check_recency(ModelAction *curr, const ModelAction *rf) {
ModelAction *act=*rit;
bool foundvalue = false;
for (int j = 0; j<act->get_node()->get_read_from_size(); j++) {
ModelAction *act=*rit;
bool foundvalue = false;
for (int j = 0; j<act->get_node()->get_read_from_size(); j++) {
- if (act->get_node()->get_read_from_at(
i
)==write) {
+ if (act->get_node()->get_read_from_at(
j
)==write) {
foundvalue = true;
break;
}
foundvalue = true;
break;
}
@@
-1280,7
+1291,7
@@
bool ModelChecker::w_modification_order(ModelAction *curr)
* 1) If RMW and it actually read from something, then we
* already have all relevant edges, so just skip to next
* thread.
* 1) If RMW and it actually read from something, then we
* already have all relevant edges, so just skip to next
* thread.
- *
+ *
* 2) If RMW and it didn't read from anything, we should
* whatever edge we can get to speed up convergence.
*
* 2) If RMW and it didn't read from anything, we should
* whatever edge we can get to speed up convergence.
*
@@
-1290,7
+1301,7
@@
bool ModelChecker::w_modification_order(ModelAction *curr)
if (curr->is_rmw()) {
if (curr->get_reads_from()!=NULL)
break;
if (curr->is_rmw()) {
if (curr->get_reads_from()!=NULL)
break;
- else
+ else
continue;
} else
continue;
continue;
} else
continue;
@@
-1309,7
+1320,7
@@
bool ModelChecker::w_modification_order(ModelAction *curr)
*/
if (act->is_write())
mo_graph->addEdge(act, curr);
*/
if (act->is_write())
mo_graph->addEdge(act, curr);
- else if (act->is_read()) {
+ else if (act->is_read()) {
//if previous read accessed a null, just keep going
if (act->get_reads_from() == NULL)
continue;
//if previous read accessed a null, just keep going
if (act->get_reads_from() == NULL)
continue;
@@
-1377,10
+1388,9
@@
bool ModelChecker::mo_may_allow(const ModelAction *writer, const ModelAction *re
{
std::vector<action_list_t> *thrd_lists = obj_thrd_map->get_safe_ptr(reader->get_location());
unsigned int i;
{
std::vector<action_list_t> *thrd_lists = obj_thrd_map->get_safe_ptr(reader->get_location());
unsigned int i;
-
/* Iterate over all threads */
for (i = 0; i < thrd_lists->size(); i++) {
/* Iterate over all threads */
for (i = 0; i < thrd_lists->size(); i++) {
- ModelAction *write_after_read = NULL;
+
const
ModelAction *write_after_read = NULL;
/* Iterate over actions in thread, starting from most recent */
action_list_t *list = &(*thrd_lists)[i];
/* Iterate over actions in thread, starting from most recent */
action_list_t *list = &(*thrd_lists)[i];
@@
-1392,12
+1402,14
@@
bool ModelChecker::mo_may_allow(const ModelAction *writer, const ModelAction *re
break;
else if (act->is_write())
write_after_read = act;
break;
else if (act->is_write())
write_after_read = act;
+ else if (act->is_read() && act->get_reads_from() != NULL && act != reader) {
+ write_after_read = act->get_reads_from();
+ }
}
}
- if (write_after_read && mo_graph->checkReachable(write_after_read, writer))
+ if (write_after_read &&
write_after_read!=writer &&
mo_graph->checkReachable(write_after_read, writer))
return false;
}
return false;
}
-
return true;
}
return true;
}
@@
-1678,7
+1690,7
@@
void ModelChecker::add_action_to_lists(ModelAction *act)
if (act->is_wait()) {
void *mutex_loc=(void *) act->get_value();
obj_map->get_safe_ptr(mutex_loc)->push_back(act);
if (act->is_wait()) {
void *mutex_loc=(void *) act->get_value();
obj_map->get_safe_ptr(mutex_loc)->push_back(act);
-
+
std::vector<action_list_t> *vec = obj_thrd_map->get_safe_ptr(mutex_loc);
if (tid >= (int)vec->size())
vec->resize(priv->next_thread_id);
std::vector<action_list_t> *vec = obj_thrd_map->get_safe_ptr(mutex_loc);
if (tid >= (int)vec->size())
vec->resize(priv->next_thread_id);
@@
-1790,7
+1802,7
@@
bool ModelChecker::resolve_promises(ModelAction *write)
//Make sure the promise's value matches the write's value
ASSERT(promise->get_value() == write->get_value());
delete(promise);
//Make sure the promise's value matches the write's value
ASSERT(promise->get_value() == write->get_value());
delete(promise);
-
+
promises->erase(promises->begin() + promise_index);
threads_to_check.push_back(read->get_tid());
promises->erase(promises->begin() + promise_index);
threads_to_check.push_back(read->get_tid());
@@
-1825,7
+1837,7
@@
void ModelChecker::compute_promises(ModelAction *curr)
!act->same_thread(curr) &&
act->get_location() == curr->get_location() &&
promise->get_value() == curr->get_value()) {
!act->same_thread(curr) &&
act->get_location() == curr->get_location() &&
promise->get_value() == curr->get_value()) {
- curr->get_node()->set_promise(i);
+ curr->get_node()->set_promise(i
, act->is_rmw()
);
}
}
}
}
}
}
@@
-1847,10
+1859,20
@@
void ModelChecker::check_promises(thread_id_t tid, ClockVector *old_cv, ClockVec
}
}
}
}
+void ModelChecker::check_promises_thread_disabled() {
+ for (unsigned int i = 0; i < promises->size(); i++) {
+ Promise *promise = (*promises)[i];
+ if (promise->check_promise()) {
+ failed_promise = true;
+ return;
+ }
+ }
+}
+
/** Checks promises in response to addition to modification order for threads.
* Definitions:
* pthread is the thread that performed the read that created the promise
/** Checks promises in response to addition to modification order for threads.
* Definitions:
* pthread is the thread that performed the read that created the promise
- *
+ *
* pread is the read that created the promise
*
* pwrite is either the first write to same location as pread by
* pread is the read that created the promise
*
* pwrite is either the first write to same location as pread by
@@
-1879,7
+1901,7
@@
void ModelChecker::mo_check_promises(thread_id_t tid, const ModelAction *write)
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
const ModelAction *act = promise->get_action();
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
const ModelAction *act = promise->get_action();
-
+
//Is this promise on the same location?
if ( act->get_location() != location )
continue;
//Is this promise on the same location?
if ( act->get_location() != location )
continue;
@@
-1901,12
+1923,12
@@
void ModelChecker::mo_check_promises(thread_id_t tid, const ModelAction *write)
return;
}
}
return;
}
}
-
+
//Don't do any lookups twice for the same thread
if (promise->has_sync_thread(tid))
continue;
//Don't do any lookups twice for the same thread
if (promise->has_sync_thread(tid))
continue;
-
- if (mo_graph->checkReachable(promise->get_write(), write)) {
+
+ if (
promise->get_write()&&
mo_graph->checkReachable(promise->get_write(), write)) {
if (promise->increment_threads(tid)) {
failed_promise = true;
return;
if (promise->increment_threads(tid)) {
failed_promise = true;
return;
@@
-1978,17
+2000,14
@@
void ModelChecker::build_reads_from_past(ModelAction *curr)
/* Don't consider more than one seq_cst write if we are a seq_cst read. */
if (!curr->is_seqcst() || (!act->is_seqcst() && (last_seq_cst == NULL || !act->happens_before(last_seq_cst))) || act == last_seq_cst) {
/* Don't consider more than one seq_cst write if we are a seq_cst read. */
if (!curr->is_seqcst() || (!act->is_seqcst() && (last_seq_cst == NULL || !act->happens_before(last_seq_cst))) || act == last_seq_cst) {
- DEBUG("Adding action to may_read_from:\n");
- if (DBG_ENABLED()) {
- act->print();
- curr->print();
- }
-
- if (curr->get_sleep_flag() && ! curr->is_seqcst()) {
- if (sleep_can_read_from(curr, act))
- curr->get_node()->add_read_from(act);
- } else
+ if (!curr->get_sleep_flag() || curr->is_seqcst() || sleep_can_read_from(curr, act)) {
+ DEBUG("Adding action to may_read_from:\n");
+ if (DBG_ENABLED()) {
+ act->print();
+ curr->print();
+ }
curr->get_node()->add_read_from(act);
curr->get_node()->add_read_from(act);
+ }
}
/* Include at most one act per-thread that "happens before" curr */
}
/* Include at most one act per-thread that "happens before" curr */
@@
-2017,7
+2036,8
@@
void ModelChecker::build_reads_from_past(ModelAction *curr)
bool ModelChecker::sleep_can_read_from(ModelAction * curr, const ModelAction *write) {
while(true) {
Node *prevnode=write->get_node()->get_parent();
bool ModelChecker::sleep_can_read_from(ModelAction * curr, const ModelAction *write) {
while(true) {
Node *prevnode=write->get_node()->get_parent();
- bool thread_sleep=prevnode->get_enabled_array()[id_to_int(curr->get_tid())]==THREAD_SLEEP_SET;
+
+ bool thread_sleep=prevnode->enabled_status(curr->get_tid())==THREAD_SLEEP_SET;
if (write->is_release()&&thread_sleep)
return true;
if (!write->is_rmw()) {
if (write->is_release()&&thread_sleep)
return true;
if (!write->is_rmw()) {
@@
-2036,7
+2056,7
@@
static void print_list(action_list_t *list)
printf("---------------------------------------------------------------------\n");
printf("Trace:\n");
unsigned int hash=0;
printf("---------------------------------------------------------------------\n");
printf("Trace:\n");
unsigned int hash=0;
-
+
for (it = list->begin(); it != list->end(); it++) {
(*it)->print();
hash=hash^(hash<<3)^((*it)->hash());
for (it = list->begin(); it != list->end(); it++) {
(*it)->print();
hash=hash^(hash<<3)^((*it)->hash());
@@
-2048,12
+2068,12
@@
static void print_list(action_list_t *list)
#if SUPPORT_MOD_ORDER_DUMP
void ModelChecker::dumpGraph(char *filename) {
char buffer[200];
#if SUPPORT_MOD_ORDER_DUMP
void ModelChecker::dumpGraph(char *filename) {
char buffer[200];
- sprintf(buffer, "%s.dot",filename);
- FILE *file=fopen(buffer, "w");
- fprintf(file, "digraph %s {\n",filename);
+
sprintf(buffer, "%s.dot",filename);
+
FILE *file=fopen(buffer, "w");
+
fprintf(file, "digraph %s {\n",filename);
mo_graph->dumpNodes(file);
ModelAction ** thread_array=(ModelAction **)model_calloc(1, sizeof(ModelAction *)*get_num_threads());
mo_graph->dumpNodes(file);
ModelAction ** thread_array=(ModelAction **)model_calloc(1, sizeof(ModelAction *)*get_num_threads());
-
+
for (action_list_t::iterator it = action_trace->begin(); it != action_trace->end(); it++) {
ModelAction *action=*it;
if (action->is_read()) {
for (action_list_t::iterator it = action_trace->begin(); it != action_trace->end(); it++) {
ModelAction *action=*it;
if (action->is_read()) {
@@
-2064,12
+2084,12
@@
void ModelChecker::dumpGraph(char *filename) {
if (thread_array[action->get_tid()] != NULL) {
fprintf(file, "N%u -> N%u[label=\"sb\", color=blue];\n", thread_array[action->get_tid()]->get_seq_number(), action->get_seq_number());
}
if (thread_array[action->get_tid()] != NULL) {
fprintf(file, "N%u -> N%u[label=\"sb\", color=blue];\n", thread_array[action->get_tid()]->get_seq_number(), action->get_seq_number());
}
-
+
thread_array[action->get_tid()]=action;
}
thread_array[action->get_tid()]=action;
}
- fprintf(file,"}\n");
+
fprintf(file,"}\n");
model_free(thread_array);
model_free(thread_array);
- fclose(file);
+ fclose(file);
}
#endif
}
#endif
@@
-2086,7
+2106,7
@@
void ModelChecker::print_summary()
sprintf(buffername, "exec%04u", num_executions);
mo_graph->dumpGraphToFile(buffername);
sprintf(buffername, "graph%04u", num_executions);
sprintf(buffername, "exec%04u", num_executions);
mo_graph->dumpGraphToFile(buffername);
sprintf(buffername, "graph%04u", num_executions);
- dumpGraph(buffername);
+
dumpGraph(buffername);
#endif
if (!isfinalfeasible())
#endif
if (!isfinalfeasible())
@@
-2107,7
+2127,7
@@
void ModelChecker::add_thread(Thread *t)
}
/**
}
/**
- * Removes a thread from the scheduler.
+ * Removes a thread from the scheduler.
* @param the thread to remove.
*/
void ModelChecker::remove_thread(Thread *t)
* @param the thread to remove.
*/
void ModelChecker::remove_thread(Thread *t)