X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=model.cc;h=7c9b4c07296bf05e57280c4eb4f33198f62dbe38;hb=8311cfbfaef6d71448cb04de647ef89cba3d3b98;hp=d19fdf9d12c1d809a7e72b4d6974b65f3be674a3;hpb=e0d4c19ffcaf877eaac3a2b7324daae6c1fa7a25;p=model-checker.git

diff --git a/model.cc b/model.cc
index d19fdf9..7c9b4c0 100644
--- a/model.cc
+++ b/model.cc
@@ -159,6 +159,14 @@ void ModelChecker::reset_to_initial_state()
 	/* 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
+	 * point
+	 */
+	for (unsigned int i = 0; i < get_num_threads(); i++)
+		delete get_thread(int_to_id(i))->get_pending();
+
 	snapshot_backtrack_before(0);
 }
 
@@ -203,11 +211,14 @@ Node * ModelChecker::get_curr_node() const
  * 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 this will return
- * NULL.
- * @param curr The current ModelAction. This action might guide the choice of
- * next thread.
- * @return The next thread to run. If the model-checker has no preference, NULL.
+ * when exploring a new execution ordering), in which case 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.
  */
 Thread * ModelChecker::get_next_thread(ModelAction *curr)
 {
@@ -216,14 +227,17 @@ Thread * ModelChecker::get_next_thread(ModelAction *curr)
 	if (curr != NULL) {
 		/* Do not split atomic actions. */
 		if (curr->is_rmwr())
-			return thread_current();
+			return get_thread(curr);
 		else if (curr->get_type() == THREAD_CREATE)
 			return curr->get_thread_operand();
 	}
 
-	/* Have we completed exploring the preselected path? */
+	/*
+	 * Have we completed exploring the preselected path? Then let the
+	 * scheduler decide
+	 */
 	if (diverge == NULL)
-		return NULL;
+		return scheduler->select_next_thread();
 
 	/* Else, we are trying to replay an execution */
 	ModelAction *next = node_stack->get_next()->get_action();
@@ -293,9 +307,7 @@ void ModelChecker::execute_sleep_set()
 	for (unsigned int i = 0; i < get_num_threads(); i++) {
 		thread_id_t tid = int_to_id(i);
 		Thread *thr = get_thread(tid);
-		if (scheduler->is_sleep_set(thr) && thr->get_pending() == NULL) {
-			scheduler->next_thread(thr);
-			Thread::swap(&system_context, thr);
+		if (scheduler->is_sleep_set(thr) && thr->get_pending()) {
 			thr->get_pending()->set_sleep_flag();
 		}
 	}
@@ -321,11 +333,22 @@ void ModelChecker::set_bad_synchronization()
 	priv->bad_synchronization = true;
 }
 
+/**
+ * Check whether the current trace has triggered an assertion which should halt
+ * its execution.
+ *
+ * @return True, if the execution should be aborted; false otherwise
+ */
 bool ModelChecker::has_asserted() const
 {
 	return priv->asserted;
 }
 
+/**
+ * Trigger a trace assertion which should cause this execution to be halted.
+ * This can be due to a detected bug or due to an infeasibility that should
+ * halt ASAP.
+ */
 void ModelChecker::set_assert()
 {
 	priv->asserted = true;
@@ -522,7 +545,7 @@ bool ModelChecker::next_execution()
 	return true;
 }
 
-ModelAction * ModelChecker::get_last_conflict(ModelAction *act)
+ModelAction * ModelChecker::get_last_conflict(ModelAction *act) const
 {
 	switch (act->get_type()) {
 	case ATOMIC_FENCE:
@@ -2650,6 +2673,19 @@ bool ModelChecker::is_enabled(thread_id_t tid) const
 	return scheduler->is_enabled(tid);
 }
 
+/**
+ * Switch from a model-checker context to a user-thread context. This is the
+ * complement of ModelChecker::switch_to_master and must be called from the
+ * model-checker context
+ *
+ * @param thread The user-thread to switch to
+ */
+void ModelChecker::switch_from_master(Thread *thread)
+{
+	scheduler->set_current_thread(thread);
+	Thread::swap(&system_context, thread);
+}
+
 /**
  * Switch from a user-context to the "master thread" context (a.k.a. system
  * context). This switch is made with the intention of exploring a particular
@@ -2665,6 +2701,7 @@ uint64_t ModelChecker::switch_to_master(ModelAction *act)
 {
 	DBG();
 	Thread *old = thread_current();
+	ASSERT(!old->get_pending());
 	old->set_pending(act);
 	if (Thread::swap(old, &system_context) < 0) {
 		perror("swap threads");
@@ -2681,9 +2718,6 @@ uint64_t ModelChecker::switch_to_master(ModelAction *act)
  */
 Thread * ModelChecker::take_step(ModelAction *curr)
 {
-	if (has_asserted())
-		return NULL;
-
 	Thread *curr_thrd = get_thread(curr);
 	ASSERT(curr_thrd->get_state() == THREAD_READY);
 
@@ -2704,35 +2738,10 @@ Thread * ModelChecker::take_step(ModelAction *curr)
 		scheduler->remove_thread(curr_thrd);
 
 	Thread *next_thrd = get_next_thread(curr);
-	next_thrd = scheduler->next_thread(next_thrd);
 
 	DEBUG("(%d, %d)\n", curr_thrd ? id_to_int(curr_thrd->get_id()) : -1,
 			next_thrd ? id_to_int(next_thrd->get_id()) : -1);
 
-	/*
-	 * Launch end-of-execution release sequence fixups only when there are:
-	 *
-	 * (1) no more user threads to run (or when execution replay chooses
-	 *     the 'model_thread')
-	 * (2) pending release sequences
-	 * (3) pending assertions (i.e., data races)
-	 * (4) no pending promises
-	 */
-	if (!pending_rel_seqs->empty() && (!next_thrd || next_thrd->is_model_thread()) &&
-			is_feasible_prefix_ignore_relseq() && !unrealizedraces.empty()) {
-		model_print("*** WARNING: release sequence fixup action (%zu pending release seuqences) ***\n",
-				pending_rel_seqs->size());
-		ModelAction *fixup = new ModelAction(MODEL_FIXUP_RELSEQ,
-				std::memory_order_seq_cst, NULL, VALUE_NONE,
-				model_thread);
-		model_thread->set_pending(fixup);
-		return model_thread;
-	}
-
-	/* next_thrd == NULL -> don't take any more steps */
-	if (!next_thrd)
-		return NULL;
-
 	return next_thrd;
 }
 
@@ -2751,16 +2760,53 @@ void ModelChecker::run()
 		add_thread(t);
 
 		do {
-			scheduler->next_thread(t);
-			Thread::swap(&system_context, t);
+			/*
+			 * Stash next pending action(s) for thread(s). There
+			 * should only need to stash one thread's action--the
+			 * thread which just took a step--plus the first step
+			 * for any newly-created thread
+			 */
+			for (unsigned int i = 0; i < get_num_threads(); i++) {
+				thread_id_t tid = int_to_id(i);
+				Thread *thr = get_thread(tid);
+				if (!thr->is_model_thread() && !thr->is_complete() && !thr->get_pending()) {
+					switch_from_master(thr);
+				}
+			}
+
+			/* Catch assertions from prior take_step or from
+			 * between-ModelAction bugs (e.g., data races) */
+			if (has_asserted())
+				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());
-		/** @TODO Re-write release sequence fixups here */
+
+		/*
+		 * Launch end-of-execution release sequence fixups only when
+		 * the execution is otherwise feasible AND there are:
+		 *
+		 * (1) pending release sequences
+		 * (2) pending assertions that could be invalidated by a change
+		 * in clock vectors (i.e., data races)
+		 * (3) no pending promises
+		 */
+		while (!pending_rel_seqs->empty() &&
+				is_feasible_prefix_ignore_relseq() &&
+				!unrealizedraces.empty()) {
+			model_print("*** WARNING: release sequence fixup action "
+					"(%zu pending release seuqence(s)) ***\n",
+					pending_rel_seqs->size());
+			ModelAction *fixup = new ModelAction(MODEL_FIXUP_RELSEQ,
+					std::memory_order_seq_cst, NULL, VALUE_NONE,
+					model_thread);
+			take_step(fixup);
+		};
 	} while (next_execution());
 
+	model_print("******* Model-checking complete: *******\n");
 	print_stats();
 }