r_status = r_modification_order(curr, reads_from);
}
-
if (!second_part_of_rmw && is_infeasible() && (curr->get_node()->increment_read_from() || curr->get_node()->increment_future_value())) {
mo_graph->rollbackChanges();
priv->too_many_reads = false;
} else if (!second_part_of_rmw) {
/* Read from future value */
struct future_value fv = curr->get_node()->get_future_value();
+ Promise *promise = new Promise(curr, fv);
value = fv.value;
- curr->set_read_from(NULL);
- Promise *valuepromise = new Promise(curr, value, fv.expiration);
- promises->push_back(valuepromise);
+ curr->set_read_from_promise(promise);
+ promises->push_back(promise);
}
get_thread(curr)->set_return_value(value);
return updated;
void ModelChecker::add_future_value(const ModelAction *writer, ModelAction *reader)
{
/* Do more ambitious checks now that mo is more complete */
- if (mo_may_allow(writer, reader) &&
- reader->get_node()->add_future_value(writer->get_value(),
- writer->get_seq_number() + params.maxfuturedelay))
- set_latest_backtrack(reader);
+ if (mo_may_allow(writer, reader)) {
+ Node *node = reader->get_node();
+
+ /* Find an ancestor thread which exists at the time of the reader */
+ Thread *write_thread = get_thread(writer);
+ while (id_to_int(write_thread->get_id()) >= node->get_num_threads())
+ write_thread = write_thread->get_parent();
+
+ struct future_value fv = {
+ writer->get_value(),
+ writer->get_seq_number() + params.maxfuturedelay,
+ write_thread->get_id(),
+ };
+ if (node->add_future_value(fv))
+ set_latest_backtrack(reader);
+ }
}
/**
case THREAD_CREATE: {
Thread *th = curr->get_thread_operand();
th->set_creation(curr);
+ /* Promises can be satisfied by children */
+ for (unsigned int i = 0; i < promises->size(); i++) {
+ Promise *promise = (*promises)[i];
+ if (promise->thread_is_available(curr->get_tid()))
+ promise->add_thread(th->get_id());
+ }
break;
}
case THREAD_JOIN: {
scheduler->wake(get_thread(act));
}
th->complete();
+ /* Completed thread can't satisfy promises */
+ for (unsigned int i = 0; i < promises->size(); i++) {
+ Promise *promise = (*promises)[i];
+ if (promise->thread_is_available(th->get_id()))
+ if (promise->eliminate_thread(th->get_id()))
+ priv->failed_promise = true;
+ }
updated = true; /* trigger rel-seq checks */
break;
}
{
char buf[100];
char *ptr = buf;
- if (mo_graph->checkForRMWViolation())
- ptr += sprintf(ptr, "[RMW atomicity]");
if (mo_graph->checkForCycles())
ptr += sprintf(ptr, "[mo cycle]");
if (priv->failed_promise)
*/
bool ModelChecker::is_infeasible() const
{
- return mo_graph->checkForRMWViolation() || is_infeasible_ignoreRMW();
-}
-
-/**
- * Check If the current partial trace is infeasible, while ignoring
- * infeasibility related to 2 RMW's reading from the same store. It does not
- * check end-of-execution feasibility.
- * @see ModelChecker::is_infeasible
- * @return whether the current partial trace is infeasible, ignoring multiple
- * RMWs reading from the same store.
- * */
-bool ModelChecker::is_infeasible_ignoreRMW() const
-{
- return mo_graph->checkForCycles() || priv->failed_promise ||
- priv->too_many_reads || priv->bad_synchronization ||
+ return mo_graph->checkForCycles() ||
+ priv->failed_promise ||
+ priv->too_many_reads ||
+ priv->bad_synchronization ||
promises_expired();
}
* read.
*
* Basic idea is the following: Go through each other thread and find
- * the lastest action that happened before our read. Two cases:
+ * the last action that happened before our read. Two cases:
*
* (1) The action is a write => that write must either occur before
* the write we read from or be the write we read from.
* must occur before the write we read from or be the same write.
*
* @param curr The current action. Must be a read.
- * @param rf The action that curr reads from. Must be a write.
+ * @param rf The ModelAction or Promise that curr reads from. Must be a write.
* @return True if modification order edges were added; false otherwise
*/
-bool ModelChecker::r_modification_order(ModelAction *curr, const ModelAction *rf)
+template <typename rf_type>
+bool ModelChecker::r_modification_order(ModelAction *curr, const rf_type *rf)
{
std::vector<action_list_t> *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location());
unsigned int i;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *act = *rit;
- if (act->is_write() && act != rf && act != curr) {
+ if (act->is_write() && !act->equals(rf) && act != curr) {
/* C++, Section 29.3 statement 5 */
if (curr->is_seqcst() && last_sc_fence_thread_local &&
*act < *last_sc_fence_thread_local) {
*/
if (act->happens_before(curr) && act != curr) {
if (act->is_write()) {
- if (rf != act) {
+ if (!act->equals(rf)) {
mo_graph->addEdge(act, rf);
added = true;
}
if (prevreadfrom == NULL)
continue;
- if (rf != prevreadfrom) {
+ if (!prevreadfrom->equals(rf)) {
mo_graph->addEdge(prevreadfrom, rf);
added = true;
}
*/
if (thin_air_constraint_may_allow(curr, act)) {
- if (!is_infeasible() ||
- (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() == act->get_reads_from() && !is_infeasible_ignoreRMW())) {
+ if (!is_infeasible())
futurevalues->push_back(PendingFutureValue(curr, act));
- }
+ else if (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() && curr->get_reads_from() == act->get_reads_from())
+ add_future_value(curr, act);
}
}
}
post_r_modification_order(read, write);
//Make sure the promise's value matches the write's value
ASSERT(promise->get_value() == write->get_value());
- delete(promise);
+ delete promise;
promises->erase(promises->begin() + promise_index);
actions_to_check.push_back(read);
const ModelAction *act = promise->get_action();
if ((old_cv == NULL || !old_cv->synchronized_since(act)) &&
merge_cv->synchronized_since(act)) {
- if (promise->increment_threads(tid)) {
+ if (promise->eliminate_thread(tid)) {
//Promise has failed
priv->failed_promise = true;
return;
}
}
-void ModelChecker::check_promises_thread_disabled() {
+void ModelChecker::check_promises_thread_disabled()
+{
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- if (promise->check_promise()) {
+ if (promise->has_failed()) {
priv->failed_promise = true;
return;
}
}
}
-/** Checks promises in response to addition to modification order for threads.
+/**
+ * @brief Checks promises in response to addition to modification order for
+ * threads.
+ *
* Definitions:
+ *
* pthread is the thread that performed the read that created the promise
*
* pread is the read that created the promise
*
* pwrite is either the first write to same location as pread by
- * pthread that is sequenced after pread or the value read by the
- * first read to the same lcoation as pread by pthread that is
- * sequenced after pread..
+ * pthread that is sequenced after pread or the write read by the
+ * first read to the same location as pread by pthread that is
+ * sequenced after pread.
*
- * 1. If tid=pthread, then we check what other threads are reachable
- * through the mode order starting with pwrite. Those threads cannot
+ * 1. If tid=pthread, then we check what other threads are reachable
+ * through the mod order starting with pwrite. Those threads cannot
* perform a write that will resolve the promise due to modification
* order constraints.
*
* cannot perform a future write that will resolve the promise due to
* modificatin order constraints.
*
- * @param tid The thread that either read from the model action
- * write, or actually did the model action write.
+ * @param tid The thread that either read from the model action write, or
+ * actually did the model action write.
*
- * @param write The ModelAction representing the relevant write.
- * @param read The ModelAction that reads a promised write, or NULL otherwise.
+ * @param write The ModelAction representing the relevant write.
+ * @param read The ModelAction that reads a promised write, or NULL otherwise.
*/
void ModelChecker::mo_check_promises(thread_id_t tid, const ModelAction *write, const ModelAction *read)
{
Promise *promise = (*promises)[i];
const ModelAction *act = promise->get_action();
- //Is this promise on the same location?
+ // Is this promise on the same location?
if (act->get_location() != location)
continue;
- //same thread as the promise
+ // same thread as the promise
if (act->get_tid() == tid) {
- //make sure that the reader of this write happens after the promise
- if (( read == NULL ) || ( promise->get_action() -> happens_before(read))) {
- //do we have a pwrite for the promise, if not, set it
+ // make sure that the reader of this write happens after the promise
+ if ((read == NULL) || (promise->get_action()->happens_before(read))) {
+ // do we have a pwrite for the promise, if not, set it
if (promise->get_write() == NULL) {
promise->set_write(write);
- //The pwrite cannot happen before the promise
+ // The pwrite cannot happen before the promise
if (write->happens_before(act) && (write != act)) {
priv->failed_promise = true;
return;
}
}
-
+
if (mo_graph->checkPromise(write, promise)) {
priv->failed_promise = true;
return;
}
}
- //Don't do any lookups twice for the same thread
- if (promise->has_sync_thread(tid))
+ // Don't do any lookups twice for the same thread
+ if (!promise->thread_is_available(tid))
continue;
if (promise->get_write() && mo_graph->checkReachable(promise->get_write(), write)) {
- if (promise->increment_threads(tid)) {
+ if (promise->eliminate_thread(tid)) {
priv->failed_promise = true;
return;
}
void ModelChecker::print_summary() const
{
#if SUPPORT_MOD_ORDER_DUMP
- scheduler->print();
char buffername[100];
sprintf(buffername, "exec%04u", stats.num_total);
mo_graph->dumpGraphToFile(buffername);
* @param act The ModelAction
* @return A Thread reference
*/
-Thread * ModelChecker::get_thread(ModelAction *act) const
+Thread * ModelChecker::get_thread(const ModelAction *act) const
{
return get_thread(act->get_tid());
}