/* The next node will read from a different value. */
tid = next->get_tid();
node_stack->pop_restofstack(2);
- } else if (nextnode->increment_future_value()) {
- /* The next node will try to read from a different future value. */
- tid = next->get_tid();
- node_stack->pop_restofstack(2);
} else if (nextnode->increment_relseq_break()) {
/* The next node will try to resolve a release sequence differently */
tid = next->get_tid();
stats.num_buggy_executions++;
else if (is_complete_execution())
stats.num_complete++;
- else
+ else if (scheduler->all_threads_sleeping())
stats.num_redundant++;
+ else
+ ASSERT(false);
}
/** @brief Print execution stats */
}
/**
- * Processes a read or rmw model action.
+ * Processes a read model action.
* @param curr is the read model action to process.
- * @param second_part_of_rmw is boolean that is true is this is the second action of a rmw.
* @return True if processing this read updates the mo_graph.
*/
-bool ModelChecker::process_read(ModelAction *curr, bool second_part_of_rmw)
+bool ModelChecker::process_read(ModelAction *curr)
{
+ Node *node = curr->get_node();
uint64_t value = VALUE_NONE;
bool updated = false;
while (true) {
- const ModelAction *reads_from = curr->get_node()->get_read_from();
- if (reads_from != NULL) {
- mo_graph->startChanges();
-
- value = reads_from->get_value();
- bool r_status = false;
+ switch (node->get_read_from_status()) {
+ case READ_FROM_PAST: {
+ const ModelAction *rf = node->get_read_from_past();
+ ASSERT(rf);
- if (!second_part_of_rmw) {
- check_recency(curr, reads_from);
- r_status = r_modification_order(curr, reads_from);
- }
+ mo_graph->startChanges();
+ value = rf->get_value();
+ check_recency(curr, rf);
+ bool r_status = r_modification_order(curr, rf);
- if (!second_part_of_rmw && is_infeasible() && (curr->get_node()->increment_read_from() || curr->get_node()->increment_future_value())) {
+ if (is_infeasible() && node->increment_read_from()) {
mo_graph->rollbackChanges();
priv->too_many_reads = false;
continue;
}
- read_from(curr, reads_from);
+ read_from(curr, rf);
mo_graph->commitChanges();
mo_check_promises(curr, true);
updated |= r_status;
- } else if (!second_part_of_rmw) {
+ break;
+ }
+ case READ_FROM_PROMISE: {
+ Promise *promise = curr->get_node()->get_read_from_promise();
+ promise->add_reader(curr);
+ value = promise->get_value();
+ curr->set_read_from_promise(promise);
+ mo_graph->startChanges();
+ updated = r_modification_order(curr, promise);
+ mo_graph->commitChanges();
+ break;
+ }
+ case READ_FROM_FUTURE: {
/* Read from future value */
- struct future_value fv = curr->get_node()->get_future_value();
+ struct future_value fv = node->get_future_value();
Promise *promise = new Promise(curr, fv);
value = fv.value;
curr->set_read_from_promise(promise);
mo_graph->startChanges();
updated = r_modification_order(curr, promise);
mo_graph->commitChanges();
+ break;
+ }
+ default:
+ ASSERT(false);
}
get_thread(curr)->set_return_value(value);
return updated;
{
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- ModelAction *reader = promise->get_action();
- if (reader->get_tid() != blocker->get_id())
- continue;
if (!promise->thread_is_available(waiting->get_id()))
continue;
- if (promise->eliminate_thread(waiting->get_id())) {
- /* Promise has failed */
- priv->failed_promise = true;
+ for (unsigned int j = 0; j < promise->get_num_readers(); j++) {
+ ModelAction *reader = promise->get_reader(j);
+ if (reader->get_tid() != blocker->get_id())
+ continue;
+ if (promise->eliminate_thread(waiting->get_id())) {
+ /* Promise has failed */
+ priv->failed_promise = true;
+ } else {
+ /* Only eliminate the 'waiting' thread once */
+ return;
+ }
}
}
}
if (process_thread_action(curr))
update_all = true;
- if (act->is_read() && process_read(act, second_part_of_rmw))
+ if (act->is_read() && !second_part_of_rmw && process_read(act))
update = true;
if (act->is_write() && process_write(act))
if ((parnode && !parnode->backtrack_empty()) ||
!currnode->misc_empty() ||
!currnode->read_from_empty() ||
- !currnode->future_value_empty() ||
!currnode->promise_empty() ||
!currnode->relseq_break_empty()) {
set_latest_backtrack(curr);
void ModelChecker::check_recency(ModelAction *curr, const ModelAction *rf)
{
if (params.maxreads != 0) {
- if (curr->get_node()->get_read_from_size() <= 1)
+ if (curr->get_node()->get_read_from_past_size() <= 1)
return;
//Must make sure that execution is currently feasible... We could
//accidentally clear by rolling back
if (act->get_reads_from() != rf)
return;
- if (act->get_node()->get_read_from_size() <= 1)
+ if (act->get_node()->get_read_from_past_size() <= 1)
return;
}
- for (int i = 0; i < curr->get_node()->get_read_from_size(); i++) {
+ for (int i = 0; i < curr->get_node()->get_read_from_past_size(); i++) {
/* Get write */
- const ModelAction *write = curr->get_node()->get_read_from_at(i);
+ const ModelAction *write = curr->get_node()->get_read_from_past(i);
/* Need a different write */
if (write == rf)
for (int loop = count; loop > 0; loop--, rit++) {
ModelAction *act = *rit;
bool foundvalue = false;
- for (int j = 0; j < act->get_node()->get_read_from_size(); j++) {
- if (act->get_node()->get_read_from_at(j) == write) {
+ for (int j = 0; j < act->get_node()->get_read_from_past_size(); j++) {
+ if (act->get_node()->get_read_from_past(j) == write) {
foundvalue = true;
break;
}
for (unsigned int i = 0, promise_index = 0; promise_index < promises->size(); i++) {
Promise *promise = (*promises)[promise_index];
if (write->get_node()->get_promise(i)) {
- ModelAction *read = promise->get_action();
- read_from(read, write);
+ for (unsigned int j = 0; j < promise->get_num_readers(); j++) {
+ ModelAction *read = promise->get_reader(j);
+ read_from(read, write);
+ actions_to_check.push_back(read);
+ }
//Make sure the promise's value matches the write's value
ASSERT(promise->is_compatible(write));
mo_graph->resolvePromise(promise, write, &mustResolve);
resolved.push_back(promise);
promises->erase(promises->begin() + promise_index);
- actions_to_check.push_back(read);
haveResolved = true;
} else
{
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- const ModelAction *act = promise->get_action();
- ASSERT(act->is_read());
- if (!act->happens_before(curr) &&
- !act->could_synchronize_with(curr) &&
- promise->is_compatible(curr) &&
- promise->get_value() == curr->get_value()) {
- curr->get_node()->set_promise(i, act->is_rmw());
+ if (!promise->is_compatible(curr) || promise->get_value() != curr->get_value())
+ continue;
+
+ bool satisfy = true;
+ for (unsigned int j = 0; j < promise->get_num_readers(); j++) {
+ const ModelAction *act = promise->get_reader(j);
+ if (act->happens_before(curr) ||
+ act->could_synchronize_with(curr)) {
+ satisfy = false;
+ break;
+ }
}
+ if (satisfy)
+ curr->get_node()->set_promise(i);
}
}
{
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- const ModelAction *act = promise->get_action();
- if ((old_cv == NULL || !old_cv->synchronized_since(act)) &&
- merge_cv->synchronized_since(act)) {
- if (promise->eliminate_thread(tid)) {
- //Promise has failed
- priv->failed_promise = true;
- return;
+ if (!promise->thread_is_available(tid))
+ continue;
+ for (unsigned int j = 0; j < promise->get_num_readers(); j++) {
+ const ModelAction *act = promise->get_reader(j);
+ if ((!old_cv || !old_cv->synchronized_since(act)) &&
+ merge_cv->synchronized_since(act)) {
+ if (promise->eliminate_thread(tid)) {
+ /* Promise has failed */
+ priv->failed_promise = true;
+ return;
+ }
}
}
}
for (unsigned int i = 0; i < promises->size(); i++) {
Promise *promise = (*promises)[i];
- const ModelAction *pread = promise->get_action();
// Is this promise on the same location?
- if (!pread->same_var(write))
+ if (promise->get_value() != write->get_value())
continue;
- if (pread->happens_before(act) && mo_graph->checkPromise(write, promise)) {
- priv->failed_promise = true;
- return;
+ for (unsigned int j = 0; j < promise->get_num_readers(); j++) {
+ const ModelAction *pread = promise->get_reader(j);
+ if (!pread->happens_before(act))
+ continue;
+ if (mo_graph->checkPromise(write, promise)) {
+ priv->failed_promise = true;
+ return;
+ }
+ break;
}
// Don't do any lookups twice for the same thread
mo_graph->startChanges();
r_modification_order(curr, act);
if (!is_infeasible())
- curr->get_node()->add_read_from(act);
+ curr->get_node()->add_read_from_past(act);
mo_graph->rollbackChanges();
}
/* Inherit existing, promised future values */
for (i = 0; i < promises->size(); i++) {
const Promise *promise = (*promises)[i];
- const ModelAction *promise_read = promise->get_action();
+ const ModelAction *promise_read = promise->get_reader(0);
if (promise_read->same_var(curr)) {
/* Only add feasible future-values */
mo_graph->startChanges();
r_modification_order(curr, promise);
- if (!is_infeasible()) {
- const struct future_value fv = promise->get_fv();
- curr->get_node()->add_future_value(fv);
- }
+ if (!is_infeasible())
+ curr->get_node()->add_read_from_promise(promise_read);
mo_graph->rollbackChanges();
}
}
/* We may find no valid may-read-from only if the execution is doomed */
- if (!curr->get_node()->get_read_from_size() && curr->get_node()->future_value_empty()) {
+ if (!curr->get_node()->read_from_size()) {
priv->no_valid_reads = true;
set_assert();
}
if (DBG_ENABLED()) {
model_print("Reached read action:\n");
curr->print();
- model_print("Printing may_read_from\n");
- curr->get_node()->print_may_read_from();
- model_print("End printing may_read_from\n");
+ model_print("Printing read_from_past\n");
+ curr->get_node()->print_read_from_past();
+ model_print("End printing read_from_past\n");
}
}
#endif
model_print("Execution %d:", stats.num_total);
- if (isfeasibleprefix())
+ if (isfeasibleprefix()) {
+ if (scheduler->all_threads_sleeping())
+ model_print(" SLEEP-SET REDUNDANT");
model_print("\n");
- else
+ } else
print_infeasibility(" INFEASIBLE");
print_list(action_trace);
model_print("\n");
return get_thread(act->get_tid());
}
+/**
+ * @brief Get a Promise's "promise number"
+ *
+ * A "promise number" is an index number that is unique to a promise, valid
+ * only for a specific snapshot of an execution trace. Promises may come and go
+ * as they are generated an resolved, so an index only retains meaning for the
+ * current snapshot.
+ *
+ * @param promise The Promise to check
+ * @return The promise index, if the promise still is valid; otherwise -1
+ */
+int ModelChecker::get_promise_number(const Promise *promise) const
+{
+ for (unsigned int i = 0; i < promises->size(); i++)
+ if ((*promises)[i] == promise)
+ return i;
+ /* Not found */
+ return -1;
+}
+
/**
* @brief Check if a Thread is currently enabled
* @param t The Thread to check
projects / model-checker.git / blobdiff