return blocking_threads;
}
+/**
+ * Check if a Thread has entered a circular wait deadlock situation. This will
+ * not check other threads for potential deadlock situations, and may miss
+ * deadlocks involving WAIT.
+ *
+ * @param t The thread which may have entered a deadlock
+ * @return True if this Thread entered a deadlock; false otherwise
+ */
+bool ModelChecker::is_circular_wait(const Thread *t) const
+{
+ for (Thread *waiting = t->waiting_on() ; waiting != NULL; waiting = waiting->waiting_on())
+ if (waiting == t)
+ return true;
+ return false;
+}
+
/**
* Check if this is a complete execution. That is, have all thread completed
* execution (rather than exiting because sleep sets have forced a redundant
bool ModelChecker::process_read(ModelAction *curr)
{
Node *node = curr->get_node();
- uint64_t value = VALUE_NONE;
while (true) {
bool updated = false;
switch (node->get_read_from_status()) {
}
updated = r_modification_order(curr, rf);
- value = rf->get_value();
read_from(curr, rf);
mo_graph->commitChanges();
mo_check_promises(curr, true);
}
case READ_FROM_PROMISE: {
Promise *promise = curr->get_node()->get_read_from_promise();
- promise->add_reader(curr);
- value = promise->get_value();
+ if (promise->add_reader(curr))
+ priv->failed_promise = true;
curr->set_read_from_promise(promise);
mo_graph->startChanges();
if (!check_recency(curr, promise))
/* Read from future value */
struct future_value fv = node->get_future_value();
Promise *promise = new Promise(curr, fv);
- value = fv.value;
curr->set_read_from_promise(promise);
promises->push_back(promise);
mo_graph->startChanges();
default:
ASSERT(false);
}
- get_thread(curr)->set_return_value(value);
+ get_thread(curr)->set_return_value(curr->get_return_value());
return updated;
}
}
*/
bool ModelChecker::process_mutex(ModelAction *curr)
{
- std::mutex *mutex = NULL;
+ std::mutex *mutex = curr->get_mutex();
struct std::mutex_state *state = NULL;
- if (curr->is_trylock() || curr->is_lock() || curr->is_unlock()) {
- mutex = (std::mutex *)curr->get_location();
+ if (mutex)
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;
+ bool success = !state->locked;
curr->set_try_lock(success);
if (!success) {
get_thread(curr)->set_return_value(0);
case ATOMIC_LOCK: {
if (curr->get_cv()->getClock(state->alloc_tid) <= state->alloc_clock)
assert_bug("Lock access before initialization");
- state->islocked = true;
+ state->locked = get_thread(curr);
ModelAction *unlock = get_last_unlock(curr);
//synchronize with the previous unlock statement
if (unlock != NULL) {
}
case ATOMIC_UNLOCK: {
//unlock the lock
- state->islocked = false;
+ state->locked = NULL;
//wake up the other threads
action_list_t *waiters = get_safe_ptr_action(lock_waiters_map, curr->get_location());
//activate all the waiting threads
}
case ATOMIC_WAIT: {
//unlock the lock
- state->islocked = false;
+ state->locked = NULL;
//wake up the other threads
action_list_t *waiters = get_safe_ptr_action(lock_waiters_map, (void *) curr->get_value());
//activate all the waiting threads
if (curr->is_lock()) {
std::mutex *lock = (std::mutex *)curr->get_location();
struct std::mutex_state *state = lock->get_state();
- if (state->islocked) {
+ if (state->locked) {
//Stick the action in the appropriate waiting queue
get_safe_ptr_action(lock_waiters_map, curr->get_location())->push_back(curr);
return false;
bool ModelChecker::resolve_promise(ModelAction *write, unsigned int promise_idx)
{
std::vector< ModelAction *, ModelAlloc<ModelAction *> > actions_to_check;
- promise_list_t mustResolve;
Promise *promise = (*promises)[promise_idx];
for (unsigned int i = 0; i < promise->get_num_readers(); i++) {
}
/* Make sure the promise's value matches the write's value */
ASSERT(promise->is_compatible(write) && promise->same_value(write));
- mo_graph->resolvePromise(promise, write, &mustResolve);
+ if (!mo_graph->resolvePromise(promise, write))
+ priv->failed_promise = true;
promises->erase(promises->begin() + promise_idx);
-
- /** @todo simplify the 'mustResolve' stuff */
- ASSERT(mustResolve.size() <= 1);
-
- if (!mustResolve.empty() && mustResolve[0] != promise)
- priv->failed_promise = true;
- delete promise;
+ /**
+ * @todo It is possible to end up in an inconsistent state, where a
+ * "resolved" promise may still be referenced if
+ * CycleGraph::resolvePromise() failed, so don't delete 'promise'.
+ *
+ * Note that the inconsistency only matters when dumping mo_graph to
+ * file.
+ *
+ * delete promise;
+ */
//Check whether reading these writes has made threads unable to
//resolve promises
-
for (unsigned int i = 0; i < actions_to_check.size(); i++) {
ModelAction *read = actions_to_check[i];
mo_check_promises(read, true);
Thread *thr = get_thread(tid);
if (!thr->is_model_thread() && !thr->is_complete() && !thr->get_pending()) {
switch_from_master(thr);
+ if (is_circular_wait(thr))
+ assert_bug("Deadlock detected");
}
}
projects / model-checker.git / blobdiff