documentation update

[model-checker.git] / model.cc

diff --git a/model.cc b/model.cc
index 0a5cda59df858e8d4f35e74e7eb76929032bbefa..55d5d0d43cfab46bac7a4d8e51987231526f6c33 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -204,34 +204,43 @@ Node * ModelChecker::get_curr_node() const
        return node_stack->get_head();
 }
 
+/**
+ * @brief Select the next thread to execute based on the curren action
+ *
+ * RMW actions occur in two parts, and we cannot split them. And THREAD_CREATE
+ * actions should be followed by the execution of their child thread. In either
+ * case, the current action should determine the next thread schedule.
+ *
+ * @param curr The current action
+ * @return The next thread to run, if the current action will determine this
+ * selection; otherwise NULL
+ */
+Thread * ModelChecker::action_select_next_thread(const ModelAction *curr) const
+{
+       /* Do not split atomic RMW */
+       if (curr->is_rmwr())
+               return get_thread(curr);
+       /* Follow CREATE with the created thread */
+       if (curr->get_type() == THREAD_CREATE)
+               return curr->get_thread_operand();
+       return NULL;
+}
+
 /**
  * @brief Choose the next thread to execute.
  *
- * This function chooses the next thread that should execute. It can force the
- * adjacency of read/write portions of a RMW action, force THREAD_CREATE to be
- * followed by a THREAD_START, or it can enforce execution replay/backtracking.
- * The model-checker may have no preference regarding the next thread (i.e.,
- * when exploring a new execution ordering), in which case we defer to the
- * scheduler.
+ * This function chooses the next thread that should execute. It can enforce
+ * execution replay/backtracking or, if the model-checker has no preference
+ * regarding the next thread (i.e., when exploring a new execution ordering),
+ * we defer to the scheduler.
  *
- * @param curr Optional: The current ModelAction. Only used if non-NULL and it
- * might guide the choice of next thread (i.e., THREAD_CREATE should be
- * followed by THREAD_START, or ATOMIC_RMWR followed by ATOMIC_{RMW,RMWC})
- * @return The next chosen thread to run, if any exist. Or else if no threads
- * remain to be executed, return NULL.
+ * @return The next chosen thread to run, if any exist. Or else if the current
+ * execution should terminate, return NULL.
  */
-Thread * ModelChecker::get_next_thread(ModelAction *curr)
+Thread * ModelChecker::get_next_thread()
 {
        thread_id_t tid;
 
-       if (curr != NULL) {
-               /* Do not split atomic actions. */
-               if (curr->is_rmwr())
-                       return get_thread(curr);
-               else if (curr->get_type() == THREAD_CREATE)
-                       return curr->get_thread_operand();
-       }
-
        /*
         * Have we completed exploring the preselected path? Then let the
         * scheduler decide
@@ -813,6 +822,21 @@ void ModelChecker::set_backtracking(ModelAction *act)
                        if (unfair)
                                continue;
                }
+
+               /* See if CHESS-like yield fairness allows */
+               if (model->params.yieldon) {
+                       bool unfair = false;
+                       for (int t = 0; t < node->get_num_threads(); t++) {
+                               thread_id_t tother = int_to_id(t);
+                               if (node->is_enabled(tother) && node->has_priority_over(tid, tother)) {
+                                       unfair = true;
+                                       break;
+                               }
+                       }
+                       if (unfair)
+                               continue;
+               }
+               
                /* Cache the latest backtracking point */
                set_latest_backtrack(prev);
 
@@ -1467,6 +1491,11 @@ ModelAction * ModelChecker::check_current_action(ModelAction *curr)
 
        wake_up_sleeping_actions(curr);
 
+       /* Compute fairness information for CHESS yield algorithm */
+       if (model->params.yieldon) {
+               curr->get_node()->update_yield(scheduler);
+       }
+
        /* Add the action to lists before any other model-checking tasks */
        if (!second_part_of_rmw)
                add_action_to_lists(curr);
@@ -2805,7 +2834,9 @@ static void print_list(action_list_t *list)
        unsigned int hash = 0;
 
        for (it = list->begin(); it != list->end(); it++) {
-               (*it)->print();
+               const ModelAction *act = *it;
+               if (act->get_seq_number() > 0)
+                       act->print();
                hash = hash^(hash<<3)^((*it)->hash());
        }
        model_print("HASH %u\n", hash);
@@ -3026,7 +3057,11 @@ Thread * ModelChecker::take_step(ModelAction *curr)
        if (curr_thrd->is_blocked() || curr_thrd->is_complete())
                scheduler->remove_thread(curr_thrd);
 
-       Thread *next_thrd = get_next_thread(curr);
+       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);