}
/** @return The currently executing Thread. */
-Thread * ModelChecker::get_current_thread()
+Thread * ModelChecker::get_current_thread() const
{
return scheduler->get_current_thread();
}
return ++priv->used_sequence_numbers;
}
-Node * ModelChecker::get_curr_node() {
+Node * ModelChecker::get_curr_node() const
+{
return node_stack->get_head();
}
void ModelChecker::record_stats()
{
stats.num_total++;
- if (!isfinalfeasible())
+ if (!isfeasibleprefix())
stats.num_infeasible++;
else if (have_bug_reports())
stats.num_buggy_executions++;
{
DBG();
/* Is this execution a feasible execution that's worth bug-checking? */
- bool complete = isfinalfeasible() && (is_complete_execution() ||
+ bool complete = isfeasibleprefix() && (is_complete_execution() ||
have_bug_reports());
/* End-of-execution bug checks */
}
- if (!second_part_of_rmw&&!isfeasible()&&(curr->get_node()->increment_read_from()||curr->get_node()->increment_future_value())) {
+ 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;
continue;
(*curr)->set_seq_number(get_next_seq_num());
- newcurr = node_stack->explore_action(*curr, scheduler->get_enabled());
+ newcurr = node_stack->explore_action(*curr, scheduler->get_enabled_array());
if (newcurr) {
/* First restore type and order in case of RMW operation */
if ((*curr)->is_rmwr())
return false;
}
-/** @return whether the current partial trace must be a prefix of a
- * feasible trace. */
+/**
+ * This is the strongest feasibility check available.
+ * @return whether the current trace (partial or complete) must be a prefix of
+ * a feasible trace.
+ */
bool ModelChecker::isfeasibleprefix() const
{
- return promises->size() == 0 && pending_rel_seqs->size() == 0 && isfeasible();
+ return pending_rel_seqs->size() == 0 && is_feasible_prefix_ignore_relseq();
+}
+
+/**
+ * Returns whether the current completed trace is feasible, except for pending
+ * release sequences.
+ */
+bool ModelChecker::is_feasible_prefix_ignore_relseq() const
+{
+ if (DBG_ENABLED() && promises->size() != 0)
+ DEBUG("Infeasible: unrevolved promises\n");
+
+ return !is_infeasible() && promises->size() == 0;
}
-/** @return whether the current partial trace is feasible. */
-bool ModelChecker::isfeasible() const
+/**
+ * Check if the current partial trace is infeasible. Does not check any
+ * end-of-execution flags, which might rule out the execution. Thus, this is
+ * useful only for ruling an execution as infeasible.
+ * @return whether the current partial trace is infeasible.
+ */
+bool ModelChecker::is_infeasible() const
{
if (DBG_ENABLED() && mo_graph->checkForRMWViolation())
DEBUG("Infeasible: RMW violation\n");
- return !mo_graph->checkForRMWViolation() && isfeasibleotherthanRMW();
+ return mo_graph->checkForRMWViolation() || is_infeasible_ignoreRMW();
}
-/** @return whether the current partial trace is feasible other than
- * multiple RMW reading from the same store. */
-bool ModelChecker::isfeasibleotherthanRMW() const
+/**
+ * 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
{
if (DBG_ENABLED()) {
if (mo_graph->checkForCycles())
if (promises_expired())
DEBUG("Infeasible: promises expired\n");
}
- return !mo_graph->checkForCycles() && !priv->failed_promise && !priv->too_many_reads && !priv->bad_synchronization && !promises_expired();
-}
-
-/** Returns whether the current completed trace is feasible. */
-bool ModelChecker::isfinalfeasible() const
-{
- if (DBG_ENABLED() && promises->size() != 0)
- DEBUG("Infeasible: unrevolved promises\n");
-
- return isfeasible() && promises->size() == 0;
+ return mo_graph->checkForCycles() || priv->failed_promise ||
+ priv->too_many_reads || priv->bad_synchronization ||
+ promises_expired();
}
/** Close out a RMWR by converting previous RMWR into a RMW or READ. */
return;
//Must make sure that execution is currently feasible... We could
//accidentally clear by rolling back
- if (!isfeasible())
+ if (is_infeasible())
return;
std::vector<action_list_t> *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location());
int tid = id_to_int(curr->get_tid());
/* Test to see whether this is a feasible write to read from*/
mo_graph->startChanges();
r_modification_order(curr, write);
- bool feasiblereadfrom = isfeasible();
+ bool feasiblereadfrom = !is_infeasible();
mo_graph->rollbackChanges();
if (!feasiblereadfrom)
if (curr->is_seqcst()) {
/* We have to at least see the last sequentially consistent write,
so we are initialized. */
- ModelAction *last_seq_cst = get_last_seq_cst(curr);
+ ModelAction *last_seq_cst = get_last_seq_cst_write(curr);
if (last_seq_cst != NULL) {
mo_graph->addEdge(last_seq_cst, curr);
added = true;
*/
if (thin_air_constraint_may_allow(curr, act)) {
- if (isfeasible() ||
- (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() == act->get_reads_from() && isfeasibleotherthanRMW())) {
+ if (!is_infeasible() ||
+ (curr->is_rmw() && act->is_rmw() && curr->get_reads_from() == act->get_reads_from() && !is_infeasible_ignoreRMW())) {
struct PendingFutureValue pfv = {curr,act};
futurevalues->push_back(pfv);
}
* check
* @return The last seq_cst write
*/
-ModelAction * ModelChecker::get_last_seq_cst(ModelAction *curr) const
+ModelAction * ModelChecker::get_last_seq_cst_write(ModelAction *curr) const
{
void *location = curr->get_location();
action_list_t *list = get_safe_ptr_action(obj_map, location);
return NULL;
}
+/**
+ * Gets the last memory_order_seq_cst fence (in the total global sequence)
+ * performed in a particular thread, prior to a particular fence.
+ * @param tid The ID of the thread to check
+ * @param before_fence The fence from which to begin the search; if NULL, then
+ * search for the most recent fence in the thread.
+ * @return The last prior seq_cst fence in the thread, if exists; otherwise, NULL
+ */
+ModelAction * ModelChecker::get_last_seq_cst_fence(thread_id_t tid, const ModelAction *before_fence) const
+{
+ /* All fences should have NULL location */
+ action_list_t *list = get_safe_ptr_action(obj_map, NULL);
+ action_list_t::reverse_iterator rit = list->rbegin();
+
+ if (before_fence) {
+ for (; rit != list->rend(); rit++)
+ if (*rit == before_fence)
+ break;
+
+ ASSERT(*rit == before_fence);
+ rit++;
+ }
+
+ for (; rit != list->rend(); rit++)
+ if ((*rit)->is_fence() && (tid == (*rit)->get_tid()) && (*rit)->is_seqcst())
+ return *rit;
+ return NULL;
+}
+
/**
* Gets the last unlock operation performed on a particular mutex (i.e., memory
* location). This function identifies the mutex according to the current
return NULL;
}
-ModelAction * ModelChecker::get_parent_action(thread_id_t tid)
+ModelAction * ModelChecker::get_parent_action(thread_id_t tid) const
{
ModelAction *parent = get_last_action(tid);
if (!parent)
* @param tid The thread whose clock vector we want
* @return Desired clock vector
*/
-ClockVector * ModelChecker::get_cv(thread_id_t tid)
+ClockVector * ModelChecker::get_cv(thread_id_t tid) const
{
return get_parent_action(tid)->get_cv();
}
unsigned int i;
ASSERT(curr->is_read());
- ModelAction *last_seq_cst = NULL;
+ ModelAction *last_sc_write = NULL;
/* Track whether this object has been initialized */
bool initialized = false;
if (curr->is_seqcst()) {
- last_seq_cst = get_last_seq_cst(curr);
+ last_sc_write = get_last_seq_cst_write(curr);
/* We have to at least see the last sequentially consistent write,
so we are initialized. */
- if (last_seq_cst != NULL)
+ if (last_sc_write != NULL)
initialized = true;
}
continue;
/* Don't consider more than one seq_cst write if we are a seq_cst read. */
- if (!curr->is_seqcst() || (!act->is_seqcst() && (last_seq_cst == NULL || !act->happens_before(last_seq_cst))) || act == last_seq_cst) {
- if (!curr->get_sleep_flag() || curr->is_seqcst() || sleep_can_read_from(curr, act)) {
- DEBUG("Adding action to may_read_from:\n");
- if (DBG_ENABLED()) {
- act->print();
- curr->print();
- }
- curr->get_node()->add_read_from(act);
+ bool allow_read = true;
+
+ if (curr->is_seqcst() && (act->is_seqcst() || (last_sc_write != NULL && act->happens_before(last_sc_write))) && act != last_sc_write)
+ allow_read = false;
+ else if (curr->get_sleep_flag() && !curr->is_seqcst() && !sleep_can_read_from(curr, act))
+ allow_read = false;
+
+ if (allow_read) {
+ DEBUG("Adding action to may_read_from:\n");
+ if (DBG_ENABLED()) {
+ act->print();
+ curr->print();
}
+ curr->get_node()->add_read_from(act);
}
/* Include at most one act per-thread that "happens before" curr */
dumpGraph(buffername);
#endif
- if (!isfinalfeasible())
+ if (!isfeasibleprefix())
model_print("INFEASIBLE EXECUTION!\n");
print_list(action_trace, stats.num_total);
model_print("\n");
Thread *next = scheduler->next_thread(priv->nextThread);
/* Infeasible -> don't take any more steps */
- if (!isfeasible())
+ if (is_infeasible())
return false;
else if (isfeasibleprefix() && have_bug_reports()) {
set_assert();
* (4) no pending promises
*/
if (!pending_rel_seqs->empty() && (!next || next->is_model_thread()) &&
- isfinalfeasible() && !unrealizedraces.empty()) {
+ is_feasible_prefix_ignore_relseq() && !unrealizedraces.empty()) {
model_print("*** WARNING: release sequence fixup action (%zu pending release seuqences) ***\n",
pending_rel_seqs->size());
ModelAction *fixup = new ModelAction(MODEL_FIXUP_RELSEQ,