next_backtrack(NULL),
bugs(),
failed_promise(false),
+ hard_failed_promise(false),
too_many_reads(false),
no_valid_reads(false),
bad_synchronization(false),
ModelAction *next_backtrack;
SnapVector<bug_message *> bugs;
bool failed_promise;
+ bool hard_failed_promise;
bool too_many_reads;
bool no_valid_reads;
/** @brief Incorrectly-ordered synchronization was made */
/**
* @brief Check if the current pending promises allow a future value to be sent
*
- * If one of the following is true:
- * (a) there are no pending promises
- * (b) the reader and writer do not cross any promises
- * Then, it is safe to pass a future value back now.
+ * It is unsafe to pass a future value back if there exists a pending promise Pr
+ * such that:
*
- * Otherwise, we must save the pending future value until (a) or (b) is true
+ * reader --exec-> Pr --exec-> writer
+ *
+ * If such Pr exists, we must save the pending future value until Pr is
+ * resolved.
*
* @param writer The operation which sends the future value. Must be a write.
* @param reader The operation which will observe the value. Must be a read.
bool ModelExecution::promises_may_allow(const ModelAction *writer,
const ModelAction *reader) const
{
- if (promises.empty())
- return true;
for (int i = promises.size() - 1; i >= 0; i--) {
ModelAction *pr = promises[i]->get_reader(0);
//reader is after promise...doesn't cross any promise
char *ptr = buf;
if (mo_graph->checkForCycles())
ptr += sprintf(ptr, "[mo cycle]");
- if (priv->failed_promise)
+ if (priv->failed_promise || priv->hard_failed_promise)
ptr += sprintf(ptr, "[failed promise]");
if (priv->too_many_reads)
ptr += sprintf(ptr, "[too many reads]");
if (promises.size() != 0)
ptr += sprintf(ptr, "[unresolved promise]");
if (ptr != buf)
- model_print("%s: %s\n", prefix ? prefix : "Infeasible", buf);
+ model_print("%s: %s", prefix ? prefix : "Infeasible", buf);
}
/**
*/
bool ModelExecution::is_feasible_prefix_ignore_relseq() const
{
- return !is_infeasible() && promises.size() == 0;
+ return !is_infeasible() && promises.size() == 0 && ! priv->failed_promise;
+
}
/**
{
return mo_graph->checkForCycles() ||
priv->no_valid_reads ||
- priv->failed_promise ||
priv->too_many_reads ||
priv->bad_synchronization ||
+ priv->hard_failed_promise ||
promises_expired();
}
pendingfuturevalue.
*/
- if (send_fv && thin_air_constraint_may_allow(curr, act)) {
+
+ if (send_fv && thin_air_constraint_may_allow(curr, act) && check_coherence_promise(curr, act)) {
if (!is_infeasible())
send_fv->push_back(act);
else if (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() && curr->get_reads_from() == act->get_reads_from())
return added;
}
+//This procedure uses cohere to prune future values that are
+//guaranteed to generate a coherence violation.
+//
+//need to see if there is (1) a promise for thread write, (2)
+//the promise is sb before write, (3) the promise can only be
+//resolved by the thread read, and (4) the promise has same
+//location as read/write
+
+bool ModelExecution::check_coherence_promise(const ModelAction * write, const ModelAction *read) {
+ thread_id_t write_tid=write->get_tid();
+ for(unsigned int i = promises.size(); i>0; i--) {
+ Promise *pr=promises[i-1];
+ if (!pr->same_location(write))
+ continue;
+ //the reading thread is the only thread that can resolve the promise
+ if (pr->get_num_was_available_threads()==1 && pr->thread_was_available(read->get_tid())) {
+ for(unsigned int j=0;j<pr->get_num_readers();j++) {
+ ModelAction *prreader=pr->get_reader(j);
+ //the writing thread reads from the promise before the write
+ if (prreader->get_tid()==write_tid &&
+ (*prreader)<(*write)) {
+ if ((*read)>(*prreader)) {
+ //check that we don't have a read between the read and promise
+ //from the same thread as read
+ bool okay=false;
+ for(const ModelAction *tmp=read;tmp!=prreader;) {
+ tmp=tmp->get_node()->get_parent()->get_action();
+ if (tmp->is_read() && tmp->same_thread(read)) {
+ okay=true;
+ break;
+ }
+ }
+ if (okay)
+ continue;
+ }
+ return false;
+ }
+ }
+ }
+ }
+ return true;
+}
+
+
/** Arbitrary reads from the future are not allowed. Section 29.3
* part 9 places some constraints. This method checks one result of constraint
* constraint. Others require compiler support. */
* require compiler support):
*
* If X --hb-> Y --mo-> Z, then X should not read from Z.
+ * If X --hb-> Y, A --rf-> Y, and A --mo-> Z, then X should not read from Z.
*/
bool ModelExecution::mo_may_allow(const ModelAction *writer, const ModelAction *reader)
{
/* Make sure the promise's value matches the write's value */
ASSERT(promise->is_compatible(write) && promise->same_value(write));
if (!mo_graph->resolvePromise(promise, write))
- priv->failed_promise = true;
+ priv->hard_failed_promise = true;
/**
* @todo It is possible to end up in an inconsistent state, where a
if (!pread->happens_before(act))
continue;
if (mo_graph->checkPromise(write, promise)) {
- priv->failed_promise = true;
+ priv->hard_failed_promise = true;
return;
}
break;
if (mo_graph->checkReachable(promise, write)) {
if (mo_graph->checkPromise(write, promise)) {
- priv->failed_promise = true;
+ priv->hard_failed_promise = true;
return;
}
}
dumpGraph(buffername);
#endif
- model_print("Execution %d:", get_execution_number());
+ model_print("Execution trace %d:", get_execution_number());
if (isfeasibleprefix()) {
if (is_yieldblocked())
model_print(" YIELD BLOCKED");
if (scheduler->all_threads_sleeping())
model_print(" SLEEP-SET REDUNDANT");
- model_print("\n");
+ if (have_bug_reports())
+ model_print(" DETECTED BUG(S)");
} else
print_infeasibility(" INFEASIBLE");
+ model_print("\n");
+
print_list(&action_trace);
model_print("\n");
+
if (!promises.empty()) {
model_print("Pending promises:\n");
for (unsigned int i = 0; i < promises.size(); i++) {
projects / model-checker.git / blobdiff