#include <stdio.h>
#include <algorithm>
+#include <mutex>
#include "model.h"
#include "action.h"
#include "cyclegraph.h"
#include "promise.h"
#include "datarace.h"
-#include "mutex.h"
-#include "threads.h"
+#include "threads-model.h"
#define INITIAL_THREAD_ID 0
thread_map(new HashTable<int, Thread *, int>()),
obj_map(new HashTable<const void *, action_list_t, uintptr_t, 4>()),
lock_waiters_map(new HashTable<const void *, action_list_t, uintptr_t, 4>()),
+ condvar_waiters_map(new HashTable<const void *, action_list_t, uintptr_t, 4>()),
obj_thrd_map(new HashTable<void *, std::vector<action_list_t>, uintptr_t, 4 >()),
promises(new std::vector< Promise *, SnapshotAlloc<Promise *> >()),
futurevalues(new std::vector< struct PendingFutureValue, SnapshotAlloc<struct PendingFutureValue> >()),
delete obj_thrd_map;
delete obj_map;
delete lock_waiters_map;
+ delete condvar_waiters_map;
delete action_trace;
for (unsigned int i = 0; i < promises->size(); i++)
return ++priv->used_sequence_numbers;
}
+Node * ModelChecker::get_curr_node() {
+ return node_stack->get_head();
+}
+
/**
* @brief Choose the next thread to execute.
*
scheduler->update_sleep_set(prevnode);
/* Reached divergence point */
- if (nextnode->increment_promise()) {
+ if (nextnode->increment_misc()) {
+ /* The next node will try to satisfy a different misc_index values. */
+ tid = next->get_tid();
+ node_stack->pop_restofstack(2);
+ } else if (nextnode->increment_promise()) {
/* The next node will try to satisfy a different set of promises. */
tid = next->get_tid();
node_stack->pop_restofstack(2);
DEBUG("Number of acquires waiting on pending release sequences: %zu\n",
pending_rel_seqs->size());
- if (isfinalfeasible() || DBG_ENABLED())
+
+ if (isfinalfeasible() || (params.bound != 0 && priv->used_sequence_numbers > params.bound ) || DBG_ENABLED() )
print_summary();
if ((diverge = get_next_backtrack()) == NULL)
}
break;
}
+ case ATOMIC_WAIT: {
+ /* linear search: from most recent to oldest */
+ action_list_t *list = obj_map->get_safe_ptr(act->get_location());
+ action_list_t::reverse_iterator rit;
+ for (rit = list->rbegin(); rit != list->rend(); rit++) {
+ ModelAction *prev = *rit;
+ if (!act->same_thread(prev)&&prev->is_failed_trylock())
+ return prev;
+ if (!act->same_thread(prev)&&prev->is_notify())
+ return prev;
+ }
+ break;
+ }
+
+ case ATOMIC_NOTIFY_ALL:
+ case ATOMIC_NOTIFY_ONE: {
+ /* linear search: from most recent to oldest */
+ action_list_t *list = obj_map->get_safe_ptr(act->get_location());
+ action_list_t::reverse_iterator rit;
+ for (rit = list->rbegin(); rit != list->rend(); rit++) {
+ ModelAction *prev = *rit;
+ if (!act->same_thread(prev)&&prev->is_wait())
+ return prev;
+ }
+ break;
+ }
default:
break;
}
* @return True if synchronization was updated; false otherwise
*/
bool ModelChecker::process_mutex(ModelAction *curr) {
- std::mutex *mutex = (std::mutex *)curr->get_location();
- struct std::mutex_state *state = mutex->get_state();
+ std::mutex *mutex=NULL;
+ struct std::mutex_state *state=NULL;
+
+ if (curr->is_trylock() || curr->is_lock() || curr->is_unlock()) {
+ mutex = (std::mutex *)curr->get_location();
+ state = mutex->get_state();
+ } else if(curr->is_wait()) {
+ mutex = (std::mutex *)curr->get_value();
+ state = mutex->get_state();
+ }
+
switch (curr->get_type()) {
case ATOMIC_TRYLOCK: {
bool success = !state->islocked;
waiters->clear();
break;
}
+ case ATOMIC_WAIT: {
+ //unlock the lock
+ state->islocked = false;
+ //wake up the other threads
+ action_list_t *waiters = lock_waiters_map->get_safe_ptr((void *) curr->get_value());
+ //activate all the waiting threads
+ for (action_list_t::iterator rit = waiters->begin(); rit != waiters->end(); rit++) {
+ scheduler->wake(get_thread(*rit));
+ }
+ waiters->clear();
+ //check whether we should go to sleep or not...simulate spurious failures
+ if (curr->get_node()->get_misc()==0) {
+ condvar_waiters_map->get_safe_ptr(curr->get_location())->push_back(curr);
+ //disable us
+ scheduler->sleep(get_current_thread());
+ }
+ break;
+ }
+ case ATOMIC_NOTIFY_ALL: {
+ action_list_t *waiters = condvar_waiters_map->get_safe_ptr(curr->get_location());
+ //activate all the waiting threads
+ for (action_list_t::iterator rit = waiters->begin(); rit != waiters->end(); rit++) {
+ scheduler->wake(get_thread(*rit));
+ }
+ waiters->clear();
+ break;
+ }
+ case ATOMIC_NOTIFY_ONE: {
+ action_list_t *waiters = condvar_waiters_map->get_safe_ptr(curr->get_location());
+ int wakeupthread=curr->get_node()->get_misc();
+ action_list_t::iterator it = waiters->begin();
+ advance(it, wakeupthread);
+ scheduler->wake(get_thread(*it));
+ waiters->erase(it);
+ break;
+ }
+
default:
ASSERT(0);
}
if (promises->size() == 0) {
for (unsigned int i = 0; i < futurevalues->size(); i++) {
struct PendingFutureValue pfv = (*futurevalues)[i];
- if (pfv.act->get_node()->add_future_value(pfv.value, pfv.expiration) &&
+ //Do more ambitious checks now that mo is more complete
+ if (mo_may_allow(pfv.writer, pfv.act)&&
+ pfv.act->get_node()->add_future_value(pfv.writer->get_value(), pfv.writer->get_seq_number()+params.maxfuturedelay) &&
(!priv->next_backtrack || *pfv.act > *priv->next_backtrack))
priv->next_backtrack = pfv.act;
}
break;
}
case THREAD_JOIN: {
- Thread *waiting, *blocking;
- waiting = get_thread(curr);
- blocking = (Thread *)curr->get_location();
- if (!blocking->is_complete()) {
- blocking->push_wait_list(curr);
- scheduler->sleep(waiting);
- } else {
- do_complete_join(curr);
- updated = true; /* trigger rel-seq checks */
- }
+ Thread *blocking = (Thread *)curr->get_location();
+ ModelAction *act = get_last_action(blocking->get_id());
+ curr->synchronize_with(act);
+ updated = true; /* trigger rel-seq checks */
break;
}
case THREAD_FINISH: {
Thread *th = get_thread(curr);
while (!th->wait_list_empty()) {
ModelAction *act = th->pop_wait_list();
- Thread *wake = get_thread(act);
- scheduler->wake(wake);
- do_complete_join(act);
- updated = true; /* trigger rel-seq checks */
+ scheduler->wake(get_thread(act));
}
th->complete();
updated = true; /* trigger rel-seq checks */
compute_promises(newcurr);
else if (newcurr->is_relseq_fixup())
compute_relseq_breakwrites(newcurr);
+ else if (newcurr->is_wait())
+ newcurr->get_node()->set_misc_max(2);
+ else if (newcurr->is_notify_one()) {
+ newcurr->get_node()->set_misc_max(condvar_waiters_map->get_safe_ptr(newcurr->get_location())->size());
+ }
}
return newcurr;
}
/**
- * This method checks whether a model action is enabled at the given point.
- * At this point, it checks whether a lock operation would be successful at this point.
- * If not, it puts the thread in a waiter list.
+ * @brief Check whether a model action is enabled.
+ *
+ * Checks whether a lock or join operation would be successful (i.e., is the
+ * lock already locked, or is the joined thread already complete). If not, put
+ * the action in a waiter list.
+ *
* @param curr is the ModelAction to check whether it is enabled.
* @return a bool that indicates whether the action is enabled.
*/
lock_waiters_map->get_safe_ptr(curr->get_location())->push_back(curr);
return false;
}
+ } else if (curr->get_type() == THREAD_JOIN) {
+ Thread *blocking = (Thread *)curr->get_location();
+ if (!blocking->is_complete()) {
+ blocking->push_wait_list(curr);
+ return false;
+ }
}
return true;
if (!check_action_enabled(curr)) {
/* Make the execution look like we chose to run this action
- * much later, when a lock is actually available to release */
+ * much later, when a lock/join can succeed */
get_current_thread()->set_pending(curr);
scheduler->sleep(get_current_thread());
return get_next_thread(NULL);
}
- wake_up_sleeping_actions(curr);
-
ModelAction *newcurr = initialize_curr_action(curr);
+ wake_up_sleeping_actions(curr);
/* Add the action to lists before any other model-checking tasks */
if (!second_part_of_rmw)
return get_next_thread(curr);
}
-/**
- * Complete a THREAD_JOIN operation, by synchronizing with the THREAD_FINISH
- * operation from the Thread it is joining with. Must be called after the
- * completion of the Thread in question.
- * @param join The THREAD_JOIN action
- */
-void ModelChecker::do_complete_join(ModelAction *join)
-{
- Thread *blocking = (Thread *)join->get_location();
- ModelAction *act = get_last_action(blocking->get_id());
- join->synchronize_with(act);
-}
-
void ModelChecker::check_curr_backtracking(ModelAction * curr) {
Node *currnode = curr->get_node();
Node *parnode = currnode->get_parent();
if ((!parnode->backtrack_empty() ||
+ !currnode->misc_empty() ||
!currnode->read_from_empty() ||
!currnode->future_value_empty() ||
!currnode->promise_empty() ||
(3) cannot synchronize with us
(4) is in a different thread
=>
- that read could potentially read from our write.
+ that read could potentially read from our write. Note that
+ these checks are overly conservative at this point, we'll
+ do more checks before actually removing the
+ pendingfuturevalue.
+
*/
if (thin_air_constraint_may_allow(curr, act)) {
if (isfeasible() ||
(curr->is_rmw() && act->is_rmw() && curr->get_reads_from() == act->get_reads_from() && isfeasibleotherthanRMW())) {
- struct PendingFutureValue pfv = {curr->get_value(),curr->get_seq_number()+params.maxfuturedelay,act};
+ struct PendingFutureValue pfv = {curr,act};
futurevalues->push_back(pfv);
}
}
return true;
}
+/** Arbitrary reads from the future are not allowed. Section 29.3
+ * part 9 places some constraints. This method checks one result of constraint
+ * constraint. Others require compiler support. */
+bool ModelChecker::mo_may_allow(const ModelAction * writer, const ModelAction *reader) {
+ std::vector<action_list_t> *thrd_lists = obj_thrd_map->get_safe_ptr(reader->get_location());
+
+ //Get write that follows reader action
+ action_list_t *list = &(*thrd_lists)[id_to_int(reader->get_tid())];
+ action_list_t::reverse_iterator rit;
+ ModelAction *first_write_after_read=NULL;
+
+ for (rit = list->rbegin(); rit != list->rend(); rit++) {
+ ModelAction *act = *rit;
+ if (act==reader)
+ break;
+ if (act->is_write())
+ first_write_after_read=act;
+ }
+
+ if (first_write_after_read==NULL)
+ return true;
+
+ return !mo_graph->checkReachable(first_write_after_read, writer);
+}
+
+
+
/**
* Finds the head(s) of the release sequence(s) containing a given ModelAction.
* The ModelAction under consideration is expected to be taking part in
continue;
}
- /* Only writes can break release sequences */
- if (!act->is_write())
+ /* Only non-RMW writes can break release sequences */
+ if (!act->is_write() || act->is_rmw())
continue;
/* Check modification order */
if ((int)thrd_last_action->size() <= tid)
thrd_last_action->resize(get_num_threads());
(*thrd_last_action)[tid] = 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);
+ (*vec)[tid].push_back(act);
+
+ if ((int)thrd_last_action->size() <= tid)
+ thrd_last_action->resize(get_num_threads());
+ (*thrd_last_action)[tid] = act;
+ }
}
/**
/* Find: max({i in dom(S) | isUnlock(t_i) && samevar(t_i, t)}) */
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++)
- if ((*rit)->is_unlock())
+ if ((*rit)->is_unlock() || (*rit)->is_wait())
return *rit;
return NULL;
}
act->is_read() &&
!act->could_synchronize_with(curr) &&
!act->same_thread(curr) &&
+ act->get_location() == curr->get_location() &&
promise->get_value() == curr->get_value()) {
curr->get_node()->set_promise(i);
}
//do we have a pwrite for the promise, if not, set it
if (promise->get_write() == NULL ) {
promise->set_write(write);
+ //The pwrite cannot happen before the promise
+ if (write->happens_before(act) && (write != act)) {
+ failed_promise = true;
+ return;
+ }
}
if (mo_graph->checkPromise(write, promise)) {
failed_promise = true;
curr->print();
}
- if (curr->get_sleep_flag()) {
+ if (curr->get_sleep_flag() && ! curr->is_seqcst()) {
if (sleep_can_read_from(curr, act))
curr->get_node()->add_read_from(act);
} else
if (!initialized) {
/** @todo Need a more informative way of reporting errors. */
printf("ERROR: may read from uninitialized atomic\n");
+ set_assert();
}
if (DBG_ENABLED() || !initialized) {
curr->get_node()->print_may_read_from();
printf("End printing may_read_from\n");
}
-
- ASSERT(initialized);
}
bool ModelChecker::sleep_can_read_from(ModelAction * curr, const ModelAction *write) {
bool thread_sleep=prevnode->get_enabled_array()[id_to_int(curr->get_tid())]==THREAD_SLEEP_SET;
if (write->is_release()&&thread_sleep)
return true;
- if (!write->is_rmw())
+ if (!write->is_rmw()) {
return false;
+ }
if (write->get_reads_from()==NULL)
return true;
write=write->get_reads_from();
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());
}
+ printf("HASH %u\n", hash);
printf("---------------------------------------------------------------------\n");
}
if (!isfeasible())
return false;
+ if (params.bound != 0) {
+ if (priv->used_sequence_numbers > params.bound) {
+ return false;
+ }
+ }
+
DEBUG("(%d, %d)\n", curr ? id_to_int(curr->get_id()) : -1,
next ? id_to_int(next->get_id()) : -1);
projects / model-checker.git / blobdiff