optimization - a given write can resolve at most one promise from a rmw

[model-checker.git] / nodestack.cc

diff --git a/nodestack.cc b/nodestack.cc
index 72c8d5cf5e46f7dca4241aa12f26958439ad15c3..22cc3784a1c75476b15c3e4378677158dc911e95 100644 (file)
--- a/nodestack.cc
+++ b/nodestack.cc
@@ -4,7 +4,7 @@
 #include "action.h"
 #include "common.h"
 #include "model.h"
-#include "threads.h"
+#include "threads-model.h"
 
 /**
  * @brief Node constructor
@@ -34,7 +34,9 @@ Node::Node(ModelAction *act, Node *par, int nthreads, Node *prevfairness)
        future_values(),
        future_index(-1),
        relseq_break_writes(),
-       relseq_break_index(0)
+       relseq_break_index(0),
+       misc_index(0),
+       misc_max(0)
 {
        if (act) {
                act->set_node(this);
@@ -49,7 +51,7 @@ Node::Node(ModelAction *act, Node *par, int nthreads, Node *prevfairness)
                                if (prevfi) {
                                        *fi=*prevfi;
                                }
-                               if (parent->enabled_array[i]==THREAD_ENABLED) {
+                               if (parent->is_enabled(int_to_id(i))) {
                                        fi->enabled_count++;
                                }
                                if (i==currtid) {
@@ -58,7 +60,7 @@ Node::Node(ModelAction *act, Node *par, int nthreads, Node *prevfairness)
                                }
                                //Do window processing
                                if (prevfairness != NULL) {
-                                       if (prevfairness -> parent->enabled_array[i] == THREAD_ENABLED)
+                                       if (prevfairness -> parent->is_enabled(int_to_id(i)))
                                                fi->enabled_count--;
                                        if (i==prevtid) {
                                                fi->turns--;
@@ -103,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;
+       }
 }
 
 /**
@@ -116,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);
 }
 
 /**
@@ -125,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_RMW|PROMISE_FULFILLED))
+                       rmw_count++;
+       }
+       
        for (unsigned int i = 0; i < promises.size(); i++) {
-               if (promises[i] == PROMISE_UNFULFILLED) {
-                       promises[i] = PROMISE_FULFILLED;
+               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;
@@ -145,12 +161,43 @@ 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)
+       unsigned int rmw_count=0;
+       for (unsigned int i = 0; i < promises.size(); i++) {
+               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 this isn't a feasible option, keep going
+                       if ((rmw_count > 0)&&(promises[i] & PROMISE_RMW))
+                               continue;
                        return false;
+               } else if (promises[i] == (PROMISE_RMW|PROMISE_FULFILLED)) {
+                       rmw_count--;
+               }
+       }
        return true;
 }
 
+
+void Node::set_misc_max(int i) {
+       misc_max=i;
+}
+
+int Node::get_misc() {
+       return misc_index;
+}
+
+bool Node::increment_misc() {
+       return (misc_index<misc_max)&&((++misc_index)<misc_max);
+}
+
+bool Node::misc_empty() {
+       return (misc_index+1)>=misc_max;
+}
+
+
 /**
  * Adds a value from a weakly ordered future write to backtrack to.
  * @param value is the value to backtrack to.
@@ -242,6 +289,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;
@@ -267,13 +315,21 @@ thread_id_t Node::get_next_backtrack()
 bool Node::is_enabled(Thread *t)
 {
        int thread_id=id_to_int(t->get_id());
-       return thread_id < num_threads && (enabled_array[thread_id] == THREAD_ENABLED);
+       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);
-       return thread_id < num_threads && (enabled_array[thread_id] == THREAD_ENABLED);
+       return thread_id < num_threads && (enabled_array[thread_id] != THREAD_DISABLED);
 }
 
 bool Node::has_priority(thread_id_t tid)
@@ -296,12 +352,12 @@ void Node::add_read_from(const ModelAction *act)
  * @return The first element in future_values
  */
 uint64_t Node::get_future_value() {
-       ASSERT(future_index<((int)future_values.size()));
+       ASSERT(future_index >= 0 && future_index<((int)future_values.size()));
        return future_values[future_index].value;
 }
 
 modelclock_t Node::get_future_value_expiration() {
-       ASSERT(future_index<((int)future_values.size()));
+       ASSERT(future_index >= 0 && future_index<((int)future_values.size()));
        return future_values[future_index].expiration;
 }
 
@@ -409,6 +465,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--;