X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=model.cc;h=cd20321bb8c76a4c76adb1b43c29d8c2c7e6b4b5;hb=60ac5360eee87e572b9dd445f8837280213b0382;hp=0e650a3c5b3c530d1fc398c4a07964e59b65dd64;hpb=71a4f2447c7f0a20120da4e751d78cdeb4495ddd;p=model-checker.git

diff --git a/model.cc b/model.cc
index 0e650a3..cd20321 100644
--- a/model.cc
+++ b/model.cc
@@ -172,7 +172,7 @@ unsigned int ModelChecker::get_num_threads() const
 }
 
 /** @return The currently executing Thread. */
-Thread * ModelChecker::get_current_thread()
+Thread * ModelChecker::get_current_thread() const
 {
 	return scheduler->get_current_thread();
 }
@@ -183,7 +183,8 @@ modelclock_t ModelChecker::get_next_seq_num()
 	return ++priv->used_sequence_numbers;
 }
 
-Node * ModelChecker::get_curr_node() {
+Node * ModelChecker::get_curr_node() const
+{
 	return node_stack->get_head();
 }
 
@@ -424,7 +425,7 @@ void ModelChecker::print_bugs() const
 void ModelChecker::record_stats()
 {
 	stats.num_total++;
-	if (!isfinalfeasible())
+	if (!isfeasibleprefix())
 		stats.num_infeasible++;
 	else if (have_bug_reports())
 		stats.num_buggy_executions++;
@@ -483,7 +484,7 @@ bool ModelChecker::next_execution()
 {
 	DBG();
 	/* Is this execution a feasible execution that's worth bug-checking? */
-	bool complete = isfinalfeasible() && (is_complete_execution() ||
+	bool complete = isfeasibleprefix() && (is_complete_execution() ||
 			have_bug_reports());
 
 	/* End-of-execution bug checks */
@@ -520,6 +521,7 @@ bool ModelChecker::next_execution()
 ModelAction * ModelChecker::get_last_conflict(ModelAction *act)
 {
 	switch (act->get_type()) {
+	case ATOMIC_FENCE:
 	case ATOMIC_READ:
 	case ATOMIC_WRITE:
 	case ATOMIC_RMW: {
@@ -1000,7 +1002,7 @@ bool ModelChecker::initialize_curr_action(ModelAction **curr)
 
 	(*curr)->set_seq_number(get_next_seq_num());
 
-	newcurr = node_stack->explore_action(*curr, scheduler->get_enabled());
+	newcurr = node_stack->explore_action(*curr, scheduler->get_enabled_array());
 	if (newcurr) {
 		/* First restore type and order in case of RMW operation */
 		if ((*curr)->is_rmwr())
@@ -1210,11 +1212,26 @@ bool ModelChecker::promises_expired() const
 	return false;
 }
 
-/** @return whether the current partial trace must be a prefix of a
- * feasible trace. */
+/**
+ * This is the strongest feasibility check available.
+ * @return whether the current trace (partial or complete) must be a prefix of
+ * a feasible trace.
+ */
 bool ModelChecker::isfeasibleprefix() const
 {
-	return promises->size() == 0 && pending_rel_seqs->size() == 0 && !is_infeasible();
+	return pending_rel_seqs->size() == 0 && is_feasible_prefix_ignore_relseq();
+}
+
+/**
+ * Returns whether the current completed trace is feasible, except for pending
+ * release sequences.
+ */
+bool ModelChecker::is_feasible_prefix_ignore_relseq() const
+{
+	if (DBG_ENABLED() && promises->size() != 0)
+		DEBUG("Infeasible: unrevolved promises\n");
+
+	return !is_infeasible() && promises->size() == 0;
 }
 
 /**
@@ -1258,15 +1275,6 @@ bool ModelChecker::is_infeasible_ignoreRMW() const
 		promises_expired();
 }
 
-/** Returns whether the current completed trace is feasible. */
-bool ModelChecker::isfinalfeasible() const
-{
-	if (DBG_ENABLED() && promises->size() != 0)
-		DEBUG("Infeasible: unrevolved promises\n");
-
-	return !is_infeasible() && promises->size() == 0;
-}
-
 /** Close out a RMWR by converting previous RMWR into a RMW or READ. */
 ModelAction * ModelChecker::process_rmw(ModelAction *act) {
 	ModelAction *lastread = get_last_action(act->get_tid());
@@ -1395,14 +1403,48 @@ bool ModelChecker::r_modification_order(ModelAction *curr, const ModelAction *rf
 	bool added = false;
 	ASSERT(curr->is_read());
 
+	/* Last SC fence in the current thread */
+	ModelAction *last_sc_fence_local = get_last_seq_cst_fence(curr->get_tid(), NULL);
+
 	/* Iterate over all threads */
 	for (i = 0; i < thrd_lists->size(); i++) {
+		/* Last SC fence in thread i */
+		ModelAction *last_sc_fence_thread_local = NULL;
+		if (int_to_id((int)i) != curr->get_tid())
+			last_sc_fence_thread_local = get_last_seq_cst_fence(int_to_id(i), NULL);
+
+		/* Last SC fence in thread i, before last SC fence in current thread */
+		ModelAction *last_sc_fence_thread_before = NULL;
+		if (last_sc_fence_local)
+			last_sc_fence_thread_before = get_last_seq_cst_fence(int_to_id(i), last_sc_fence_local);
+
 		/* Iterate over actions in thread, starting from most recent */
 		action_list_t *list = &(*thrd_lists)[i];
 		action_list_t::reverse_iterator rit;
 		for (rit = list->rbegin(); rit != list->rend(); rit++) {
 			ModelAction *act = *rit;
 
+			if (act->is_write() && act != rf && act != curr) {
+				/* C++, Section 29.3 statement 5 */
+				if (curr->is_seqcst() && last_sc_fence_thread_local &&
+						*act < *last_sc_fence_thread_local) {
+					mo_graph->addEdge(act, rf);
+					added = true;
+				}
+				/* C++, Section 29.3 statement 4 */
+				else if (act->is_seqcst() && last_sc_fence_local &&
+						*act < *last_sc_fence_local) {
+					mo_graph->addEdge(act, rf);
+					added = true;
+				}
+				/* C++, Section 29.3 statement 6 */
+				else if (last_sc_fence_thread_before &&
+						*act < *last_sc_fence_thread_before) {
+					mo_graph->addEdge(act, rf);
+					added = true;
+				}
+			}
+
 			/*
 			 * Include at most one act per-thread that "happens
 			 * before" curr. Don't consider reflexively.
@@ -1528,15 +1570,23 @@ bool ModelChecker::w_modification_order(ModelAction *curr)
 	if (curr->is_seqcst()) {
 		/* We have to at least see the last sequentially consistent write,
 			 so we are initialized. */
-		ModelAction *last_seq_cst = get_last_seq_cst(curr);
+		ModelAction *last_seq_cst = get_last_seq_cst_write(curr);
 		if (last_seq_cst != NULL) {
 			mo_graph->addEdge(last_seq_cst, curr);
 			added = true;
 		}
 	}
 
+	/* Last SC fence in the current thread */
+	ModelAction *last_sc_fence_local = get_last_seq_cst_fence(curr->get_tid(), NULL);
+
 	/* Iterate over all threads */
 	for (i = 0; i < thrd_lists->size(); i++) {
+		/* Last SC fence in thread i, before last SC fence in current thread */
+		ModelAction *last_sc_fence_thread_before = NULL;
+		if (last_sc_fence_local && int_to_id((int)i) != curr->get_tid())
+			last_sc_fence_thread_before = get_last_seq_cst_fence(int_to_id(i), last_sc_fence_local);
+
 		/* Iterate over actions in thread, starting from most recent */
 		action_list_t *list = &(*thrd_lists)[i];
 		action_list_t::reverse_iterator rit;
@@ -1563,6 +1613,13 @@ bool ModelChecker::w_modification_order(ModelAction *curr)
 					continue;
 			}
 
+			/* C++, Section 29.3 statement 7 */
+			if (last_sc_fence_thread_before && act->is_write() &&
+					*act < *last_sc_fence_thread_before) {
+				mo_graph->addEdge(act, curr);
+				added = true;
+			}
+
 			/*
 			 * Include at most one act per-thread that "happens
 			 * before" curr
@@ -1978,7 +2035,7 @@ ModelAction * ModelChecker::get_last_action(thread_id_t tid) const
  * check
  * @return The last seq_cst write
  */
-ModelAction * ModelChecker::get_last_seq_cst(ModelAction *curr) const
+ModelAction * ModelChecker::get_last_seq_cst_write(ModelAction *curr) const
 {
 	void *location = curr->get_location();
 	action_list_t *list = get_safe_ptr_action(obj_map, location);
@@ -1990,6 +2047,35 @@ ModelAction * ModelChecker::get_last_seq_cst(ModelAction *curr) const
 	return NULL;
 }
 
+/**
+ * Gets the last memory_order_seq_cst fence (in the total global sequence)
+ * performed in a particular thread, prior to a particular fence.
+ * @param tid The ID of the thread to check
+ * @param before_fence The fence from which to begin the search; if NULL, then
+ * search for the most recent fence in the thread.
+ * @return The last prior seq_cst fence in the thread, if exists; otherwise, NULL
+ */
+ModelAction * ModelChecker::get_last_seq_cst_fence(thread_id_t tid, const ModelAction *before_fence) const
+{
+	/* All fences should have NULL location */
+	action_list_t *list = get_safe_ptr_action(obj_map, NULL);
+	action_list_t::reverse_iterator rit = list->rbegin();
+
+	if (before_fence) {
+		for (; rit != list->rend(); rit++)
+			if (*rit == before_fence)
+				break;
+
+		ASSERT(*rit == before_fence);
+		rit++;
+	}
+
+	for (; rit != list->rend(); rit++)
+		if ((*rit)->is_fence() && (tid == (*rit)->get_tid()) && (*rit)->is_seqcst())
+			return *rit;
+	return NULL;
+}
+
 /**
  * Gets the last unlock operation performed on a particular mutex (i.e., memory
  * location). This function identifies the mutex according to the current
@@ -2010,7 +2096,7 @@ ModelAction * ModelChecker::get_last_unlock(ModelAction *curr) const
 	return NULL;
 }
 
-ModelAction * ModelChecker::get_parent_action(thread_id_t tid)
+ModelAction * ModelChecker::get_parent_action(thread_id_t tid) const
 {
 	ModelAction *parent = get_last_action(tid);
 	if (!parent)
@@ -2023,7 +2109,7 @@ ModelAction * ModelChecker::get_parent_action(thread_id_t tid)
  * @param tid The thread whose clock vector we want
  * @return Desired clock vector
  */
-ClockVector * ModelChecker::get_cv(thread_id_t tid)
+ClockVector * ModelChecker::get_cv(thread_id_t tid) const
 {
 	return get_parent_action(tid)->get_cv();
 }
@@ -2227,16 +2313,16 @@ void ModelChecker::build_reads_from_past(ModelAction *curr)
 	unsigned int i;
 	ASSERT(curr->is_read());
 
-	ModelAction *last_seq_cst = NULL;
+	ModelAction *last_sc_write = NULL;
 
 	/* Track whether this object has been initialized */
 	bool initialized = false;
 
 	if (curr->is_seqcst()) {
-		last_seq_cst = get_last_seq_cst(curr);
+		last_sc_write = get_last_seq_cst_write(curr);
 		/* We have to at least see the last sequentially consistent write,
 			 so we are initialized. */
-		if (last_seq_cst != NULL)
+		if (last_sc_write != NULL)
 			initialized = true;
 	}
 
@@ -2253,15 +2339,20 @@ void ModelChecker::build_reads_from_past(ModelAction *curr)
 				continue;
 
 			/* Don't consider more than one seq_cst write if we are a seq_cst read. */
-			if (!curr->is_seqcst() || (!act->is_seqcst() && (last_seq_cst == NULL || !act->happens_before(last_seq_cst))) || act == last_seq_cst) {
-				if (!curr->get_sleep_flag() || curr->is_seqcst() || sleep_can_read_from(curr, act)) {
-					DEBUG("Adding action to may_read_from:\n");
-					if (DBG_ENABLED()) {
-						act->print();
-						curr->print();
-					}
-					curr->get_node()->add_read_from(act);
+			bool allow_read = true;
+
+			if (curr->is_seqcst() && (act->is_seqcst() || (last_sc_write != NULL && act->happens_before(last_sc_write))) && act != last_sc_write)
+				allow_read = false;
+			else if (curr->get_sleep_flag() && !curr->is_seqcst() && !sleep_can_read_from(curr, act))
+				allow_read = false;
+
+			if (allow_read) {
+				DEBUG("Adding action to may_read_from:\n");
+				if (DBG_ENABLED()) {
+					act->print();
+					curr->print();
 				}
+				curr->get_node()->add_read_from(act);
 			}
 
 			/* Include at most one act per-thread that "happens before" curr */
@@ -2358,7 +2449,7 @@ void ModelChecker::print_summary() const
 	dumpGraph(buffername);
 #endif
 
-	if (!isfinalfeasible())
+	if (!isfeasibleprefix())
 		model_print("INFEASIBLE EXECUTION!\n");
 	print_list(action_trace, stats.num_total);
 	model_print("\n");
@@ -2495,7 +2586,7 @@ bool ModelChecker::take_step() {
 	 * (4) no pending promises
 	 */
 	if (!pending_rel_seqs->empty() && (!next || next->is_model_thread()) &&
-			isfinalfeasible() && !unrealizedraces.empty()) {
+			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,