model: rename check_deadlock() to is_circular_wait()

[model-checker.git] / model.cc

diff --git a/model.cc b/model.cc
index 38d08d988e198e37a5f136a1b44988892ee4c3d7..c713d1e1761b308cc5433dfa05345a8c23d5024a 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -400,6 +400,22 @@ bool ModelChecker::is_deadlocked() const
        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
@@ -853,7 +869,6 @@ ModelAction * ModelChecker::get_next_backtrack()
 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()) {
@@ -874,7 +889,6 @@ bool ModelChecker::process_read(ModelAction *curr)
                        }
 
                        updated = r_modification_order(curr, rf);
-                       value = rf->get_value();
                        read_from(curr, rf);
                        mo_graph->commitChanges();
                        mo_check_promises(curr, true);
@@ -884,7 +898,6 @@ bool ModelChecker::process_read(ModelAction *curr)
                        Promise *promise = curr->get_node()->get_read_from_promise();
                        if (promise->add_reader(curr))
                                priv->failed_promise = true;
-                       value = promise->get_value();
                        curr->set_read_from_promise(promise);
                        mo_graph->startChanges();
                        if (!check_recency(curr, promise))
@@ -897,7 +910,6 @@ bool ModelChecker::process_read(ModelAction *curr)
                        /* 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();
@@ -908,7 +920,7 @@ bool ModelChecker::process_read(ModelAction *curr)
                default:
                        ASSERT(false);
                }
-               get_thread(curr)->set_return_value(value);
+               get_thread(curr)->set_return_value(curr->get_return_value());
                return updated;
        }
 }
@@ -931,20 +943,15 @@ bool ModelChecker::process_read(ModelAction *curr)
  */
 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);
@@ -956,7 +963,7 @@ bool ModelChecker::process_mutex(ModelAction *curr)
        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) {
@@ -967,7 +974,7 @@ bool ModelChecker::process_mutex(ModelAction *curr)
        }
        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
@@ -979,7 +986,7 @@ bool ModelChecker::process_mutex(ModelAction *curr)
        }
        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
@@ -1411,7 +1418,7 @@ bool ModelChecker::check_action_enabled(ModelAction *curr) {
        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;
@@ -3045,6 +3052,8 @@ void ModelChecker::run()
                                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");
                                }
                        }