model: add check_recency()

[cdsspec-compiler.git] / model.cc

diff --git a/model.cc b/model.cc
index 36b7b4490ffe5bb3c012e3baf3e439f719da2932..cbabe7145c94c8853f41c9aa243469bf6629dbd8 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -33,6 +33,7 @@ ModelChecker::ModelChecker(struct model_params params) :
        node_stack(new NodeStack()),
        mo_graph(new CycleGraph()),
        failed_promise(false),
+       too_many_reads(false),
        asserted(false)
 {
        /* Allocate this "size" on the snapshotting heap */
@@ -75,6 +76,7 @@ void ModelChecker::reset_to_initial_state()
        DEBUG("+++ Resetting to initial state +++\n");
        node_stack->reset_execution();
        failed_promise = false;
+       too_many_reads = false;
        reset_asserted();
        snapshotObject->backTrackBeforeStep(0);
 }
@@ -327,6 +329,8 @@ Thread * ModelChecker::check_current_action(ModelAction *curr)
                        value = reads_from->get_value();
                        /* Assign reads_from, perform release/acquire synchronization */
                        curr->read_from(reads_from);
+                       check_recency(curr, already_added);
+
                        if (r_modification_order(curr,reads_from))
                                updated = true;
                } else {
@@ -380,7 +384,7 @@ bool ModelChecker::isfeasibleprefix() {
 
 /** @returns whether the current partial trace is feasible. */
 bool ModelChecker::isfeasible() {
-       return !mo_graph->checkForCycles() && !failed_promise;
+       return !mo_graph->checkForCycles() && !failed_promise && !too_many_reads;
 }
 
 /** Returns whether the current completed trace is feasible. */
@@ -398,6 +402,56 @@ ModelAction * ModelChecker::process_rmw(ModelAction *act) {
        return lastread;
 }
 
+/**
+ * Checks whether a thread has read from the same write for too many times.
+ * @todo This may be more subtle than this code segment addresses at this
+ * point...  Potential problems to ponder and fix:
+ * (1) What if the reads_from set keeps changing such that there is no common
+ * write?
+ * (2) What if the problem is that the other writes would break modification
+ * order.
+ */
+void ModelChecker::check_recency(ModelAction *curr, bool already_added) {
+       if (params.maxreads != 0) {
+               if (curr->get_node()->get_read_from_size() <= 1)
+                       return;
+
+               std::vector<action_list_t> *thrd_lists = obj_thrd_map->get_safe_ptr(curr->get_location());
+               int tid = id_to_int(curr->get_tid());
+
+               /* Skip checks */
+               if ((int)thrd_lists->size() <= tid)
+                       return;
+
+               action_list_t *list = &(*thrd_lists)[tid];
+
+               action_list_t::reverse_iterator rit = list->rbegin();
+               /* Skip past curr */
+               if (!already_added) {
+                       for (; (*rit) != curr; rit++)
+                               ;
+                       /* go past curr now */
+                       rit++;
+               }
+
+               int count=0;
+               for (; rit != list->rend(); rit++) {
+                       ModelAction *act = *rit;
+                       if (!act->is_read())
+                               return;
+                       if (act->get_reads_from() != curr->get_reads_from())
+                               return;
+                       if (act->get_node()->get_read_from_size() <= 1)
+                               return;
+                       count++;
+                       if (count >= params.maxreads) {
+                               /* We've read from the same write for too many times */
+                               too_many_reads = true;
+                       }
+               }
+       }
+}
+
 /**
  * Updates the mo_graph with the constraints imposed from the current read.
  * @param curr The current action. Must be a read.
@@ -566,7 +620,11 @@ bool ModelChecker::release_seq_head(const ModelAction *rf,
        if (rf->is_release())
                release_heads->push_back(rf);
        if (rf->is_rmw()) {
-               if (rf->is_acquire())
+               /* We need a RMW action that is both an acquire and release to stop */
+               /** @todo Need to be smarter here...  In the linux lock
+                * example, this will run to the beginning of the program for
+                * every acquire. */
+               if (rf->is_acquire() && rf->is_release())
                        return true; /* complete */
                return release_seq_head(rf->get_reads_from(), release_heads);
        }