X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=nodestack.cc;h=b4f75e0336a3afdc3978b7ecb086e459423df455;hb=ac80452d8a9b319e38869c8ff1434ddebfc025a5;hp=06259b91c54964ba4c094af50347c11a23d9cb41;hpb=fe7b400edb33255770fb47ad520afbd05d13a231;p=model-checker.git

diff --git a/nodestack.cc b/nodestack.cc
index 06259b9..b4f75e0 100644
--- a/nodestack.cc
+++ b/nodestack.cc
@@ -105,11 +105,14 @@ void Node::print_may_read_from()
  * Sets a promise to explore meeting with the given node.
  * @param i is the promise index.
  */
-void Node::set_promise(unsigned int i) {
+void Node::set_promise(unsigned int i, bool is_rmw) {
 	if (i >= promises.size())
 		promises.resize(i + 1, PROMISE_IGNORE);
-	if (promises[i] == PROMISE_IGNORE)
+	if (promises[i] == PROMISE_IGNORE) {
 		promises[i] = PROMISE_UNFULFILLED;
+		if (is_rmw)
+			promises[i] |= PROMISE_RMW;
+	}
 }
 
 /**
@@ -118,7 +121,7 @@ void Node::set_promise(unsigned int i) {
  * @return true if the promise should be satisfied by the given model action.
  */
 bool Node::get_promise(unsigned int i) {
-	return (i < promises.size()) && (promises[i] == PROMISE_FULFILLED);
+	return (i < promises.size()) && ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED);
 }
 
 /**
@@ -127,16 +130,27 @@ bool Node::get_promise(unsigned int i) {
  */
 bool Node::increment_promise() {
 	DBG();
-
+	unsigned int rmw_count=0;
 	for (unsigned int i = 0; i < promises.size(); i++) {
-		if (promises[i] == PROMISE_UNFULFILLED) {
-			promises[i] = PROMISE_FULFILLED;
+		if (promises[i]==(PROMISE_RMW|PROMISE_FULFILLED))
+			rmw_count++;
+	}
+	
+	for (unsigned int i = 0; i < promises.size(); i++) {
+		if ((promises[i] & PROMISE_MASK) == PROMISE_UNFULFILLED) {
+			if ((rmw_count > 0) && (promises[i] & PROMISE_RMW)) {
+				//sending our value to two rmws... not going to work..try next combination
+				continue;
+			}
+			promises[i] = (promises[i] & PROMISE_RMW) |PROMISE_FULFILLED;
 			while (i > 0) {
 				i--;
-				if (promises[i] == PROMISE_FULFILLED)
-					promises[i] = PROMISE_UNFULFILLED;
+				if ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED)
+					promises[i] = (promises[i] & PROMISE_RMW) | PROMISE_UNFULFILLED;
 			}
 			return true;
+		} else if (promises[i] == (PROMISE_RMW|PROMISE_FULFILLED)) {
+			rmw_count--;
 		}
 	}
 	return false;
@@ -147,9 +161,15 @@ bool Node::increment_promise() {
  * @return true if we have explored all promise combinations.
  */
 bool Node::promise_empty() {
-	for (unsigned int i = 0; i < promises.size();i++)
-		if (promises[i] == PROMISE_UNFULFILLED)
+	bool fulfilledrmw=false;
+	for (int i = promises.size()-1 ; i>=0; i--) {
+		if (promises[i]==PROMISE_UNFULFILLED)
 			return false;
+		if (!fulfilledrmw && ((promises[i]&PROMISE_MASK)==PROMISE_UNFULFILLED))
+			return false;
+		if (promises[i]==(PROMISE_FULFILLED|PROMISE_RMW))
+			fulfilledrmw=true;
+	}
 	return true;
 }
 
@@ -172,26 +192,39 @@ bool Node::misc_empty() {
 
 
 /**
- * Adds a value from a weakly ordered future write to backtrack to.
+ * Adds a value from a weakly ordered future write to backtrack to. This
+ * operation may "fail" if the future value has already been run (within some
+ * sloppiness window of this expiration), or if the futurevalues set has
+ * reached its maximum.
+ * @see model_params.maxfuturevalues
+ *
  * @param value is the value to backtrack to.
+ * @return True if the future value was successully added; false otherwise
  */
 bool Node::add_future_value(uint64_t value, modelclock_t expiration) {
-	int suitableindex=-1;
+	int idx = -1; /* Highest index where value is found */
 	for (unsigned int i = 0; i < future_values.size(); i++) {
 		if (future_values[i].value == value) {
-			if (future_values[i].expiration>=expiration)
+			if (expiration <= future_values[i].expiration)
 				return false;
-			if (future_index < ((int) i)) {
-				suitableindex=i;
-			}
+			idx = i;
 		}
 	}
-
-	if (suitableindex!=-1) {
-		future_values[suitableindex].expiration=expiration;
+	if (idx > future_index) {
+		/* Future value hasn't been explored; update expiration */
+		future_values[idx].expiration = expiration;
 		return true;
+	} else if (idx >= 0 && expiration <= future_values[idx].expiration + model->params.expireslop) {
+		/* Future value has been explored and is within the "sloppy" window */
+		return false;
 	}
-	struct future_value newfv={value, expiration};
+
+	/* Limit the size of the future-values set */
+	if (model->params.maxfuturevalues > 0 &&
+			(int)future_values.size() >= model->params.maxfuturevalues)
+		return false;
+
+	struct future_value newfv = {value, expiration};
 	future_values.push_back(newfv);
 	return true;
 }
@@ -262,6 +295,7 @@ void Node::explore_child(ModelAction *act, enabled_type_t * is_enabled)
 bool Node::set_backtrack(thread_id_t id)
 {
 	int i = id_to_int(id);
+	ASSERT(i<((int)backtrack.size()));
 	if (backtrack[i])
 		return false;
 	backtrack[i] = true;
@@ -290,6 +324,14 @@ bool Node::is_enabled(Thread *t)
 	return thread_id < num_threads && (enabled_array[thread_id] != THREAD_DISABLED);
 }
 
+enabled_type_t Node::enabled_status(thread_id_t tid) {
+	int thread_id=id_to_int(tid);
+	if (thread_id < num_threads)
+		return enabled_array[thread_id];
+	else
+		return THREAD_DISABLED;
+}
+
 bool Node::is_enabled(thread_id_t tid)
 {
 	int thread_id=id_to_int(tid);
@@ -429,6 +471,7 @@ bool Node::relseq_break_empty() {
 void Node::explore(thread_id_t tid)
 {
 	int i = id_to_int(tid);
+	ASSERT(i<((int)backtrack.size()));
 	if (backtrack[i]) {
 		backtrack[i] = false;
 		numBacktracks--;