model: proactively build/prune is_enabled() set

[model-checker.git] / model.cc

diff --git a/model.cc b/model.cc
index 6a79ad4a90f80ff1ee3177511683cd96c67ebb54..feda416222de94f460291ee7f6a6ea15a21ddf22 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -154,9 +154,6 @@ void ModelChecker::reset_to_initial_state()
        DEBUG("+++ Resetting to initial state +++\n");
        node_stack->reset_execution();
 
-       /* Print all model-checker output before rollback */
-       fflush(model_out);
-
        /**
         * FIXME: if we utilize partial rollback, we will need to free only
         * those pending actions which were NOT pending before the rollback
@@ -755,6 +752,7 @@ void ModelChecker::set_backtracking(ModelAction *act)
 
        Node *node = prev->get_node()->get_parent();
 
+       /* See Dynamic Partial Order Reduction (addendum), POPL '05 */
        int low_tid, high_tid;
        if (node->enabled_status(t->get_id()) == THREAD_ENABLED) {
                low_tid = id_to_int(act->get_tid());
@@ -771,6 +769,7 @@ void ModelChecker::set_backtracking(ModelAction *act)
                if (i >= node->get_num_threads())
                        break;
 
+               /* See Dynamic Partial Order Reduction (addendum), POPL '05 */
                /* Don't backtrack into a point where the thread is disabled or sleeping. */
                if (node->enabled_status(tid) != THREAD_ENABLED)
                        continue;
@@ -1490,15 +1489,6 @@ ModelAction * ModelChecker::check_current_action(ModelAction *curr)
 {
        ASSERT(curr);
        bool second_part_of_rmw = curr->is_rmwc() || curr->is_rmw();
-
-       if (!check_action_enabled(curr)) {
-               /* Make the execution look like we chose to run this action
-                * much later, when a lock/join can succeed */
-               get_thread(curr)->set_pending(curr);
-               scheduler->sleep(get_thread(curr));
-               return NULL;
-       }
-
        bool newly_explored = initialize_curr_action(&curr);
 
        DBG();
@@ -3078,32 +3068,14 @@ Thread * ModelChecker::take_step(ModelAction *curr)
        Thread *curr_thrd = get_thread(curr);
        ASSERT(curr_thrd->get_state() == THREAD_READY);
 
+       ASSERT(check_action_enabled(curr)); /* May have side effects? */
        curr = check_current_action(curr);
-
-       /* Infeasible -> don't take any more steps */
-       if (is_infeasible())
-               return NULL;
-       else if (isfeasibleprefix() && have_bug_reports()) {
-               set_assert();
-               return NULL;
-       }
-
-       if (params.bound != 0 && priv->used_sequence_numbers > params.bound)
-               return NULL;
+       ASSERT(curr);
 
        if (curr_thrd->is_blocked() || curr_thrd->is_complete())
                scheduler->remove_thread(curr_thrd);
 
-       Thread *next_thrd = NULL;
-       if (curr)
-               next_thrd = action_select_next_thread(curr);
-       if (!next_thrd)
-               next_thrd = get_next_thread();
-
-       DEBUG("(%d, %d)\n", curr_thrd ? id_to_int(curr_thrd->get_id()) : -1,
-                       next_thrd ? id_to_int(next_thrd->get_id()) : -1);
-
-       return next_thrd;
+       return action_select_next_thread(curr);
 }
 
 /** Wrapper to run the user's main function, with appropriate arguments */
@@ -3112,6 +3084,21 @@ void user_main_wrapper(void *)
        user_main(model->params.argc, model->params.argv);
 }
 
+bool ModelChecker::should_terminate_execution()
+{
+       /* Infeasible -> don't take any more steps */
+       if (is_infeasible())
+               return true;
+       else if (isfeasibleprefix() && have_bug_reports()) {
+               set_assert();
+               return true;
+       }
+
+       if (params.bound != 0 && priv->used_sequence_numbers > params.bound)
+               return true;
+       return false;
+}
+
 /** @brief Run ModelChecker for the user program */
 void ModelChecker::run()
 {
@@ -3137,16 +3124,30 @@ void ModelChecker::run()
                                }
                        }
 
+                       /* Don't schedule threads which should be disabled */
+                       for (unsigned int i = 0; i < get_num_threads(); i++) {
+                               Thread *th = get_thread(int_to_id(i));
+                               ModelAction *act = th->get_pending();
+                               if (act && is_enabled(th) && !check_action_enabled(act)) {
+                                       scheduler->sleep(th);
+                               }
+                       }
+
                        /* Catch assertions from prior take_step or from
                         * between-ModelAction bugs (e.g., data races) */
                        if (has_asserted())
                                break;
 
+                       if (!t)
+                               t = get_next_thread();
+                       if (!t || t->is_model_thread())
+                               break;
+
                        /* Consume the next action for a Thread */
                        ModelAction *curr = t->get_pending();
                        t->set_pending(NULL);
                        t = take_step(curr);
-               } while (t && !t->is_model_thread());
+               } while (!should_terminate_execution());
 
                /*
                 * Launch end-of-execution release sequence fixups only when