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 Constructor */
ModelExecution::ModelExecution(ModelChecker *m,
- struct model_params *params,
+ const struct model_params *params,
Scheduler *scheduler,
NodeStack *node_stack) :
model(m),
params(params),
scheduler(scheduler),
action_trace(),
- thread_map(),
- obj_map(new HashTable<const void *, action_list_t *, uintptr_t, 4>()),
+ thread_map(2), /* We'll always need at least 2 threads */
+ obj_map(),
condvar_waiters_map(),
obj_thrd_map(),
promises(),
{
/* Initialize a model-checker thread, for special ModelActions */
model_thread = new Thread(get_next_id());
- thread_map.put(id_to_int(model_thread->get_id()), model_thread);
+ add_thread(model_thread);
scheduler->register_engine(this);
+ node_stack->register_engine(this);
}
/** @brief Destructor */
ModelExecution::~ModelExecution()
{
for (unsigned int i = 0; i < get_num_threads(); i++)
- delete thread_map.get(i);
-
- delete obj_map;
+ delete get_thread(int_to_id(i));
for (unsigned int i = 0; i < promises.size(); i++)
delete promises[i];
return blocking_threads;
}
+/**
+ * @brief Check if we are yield-blocked
+ *
+ * A program can be "yield-blocked" if all threads are ready to execute a
+ * yield.
+ *
+ * @return True if the program is yield-blocked; false otherwise
+ */
+bool ModelExecution::is_yieldblocked() const
+{
+ if (!params->yieldblock)
+ return false;
+
+ for (unsigned int i = 0; i < get_num_threads(); i++) {
+ thread_id_t tid = int_to_id(i);
+ Thread *t = get_thread(tid);
+ if (t->get_pending() && t->get_pending()->is_yield())
+ return true;
+ }
+ return false;
+}
+
/**
* Check if this is a complete execution. That is, have all thread completed
* execution (rather than exiting because sleep sets have forced a redundant
*/
bool ModelExecution::is_complete_execution() const
{
+ if (is_yieldblocked())
+ return false;
for (unsigned int i = 0; i < get_num_threads(); i++)
if (is_enabled(int_to_id(i)))
return false;
ModelAction * ModelExecution::get_last_conflict(ModelAction *act) const
{
switch (act->get_type()) {
- /* case ATOMIC_FENCE: fences don't directly cause backtracking */
+ case ATOMIC_FENCE:
+ /* Only seq-cst fences can (directly) cause backtracking */
+ if (!act->is_seqcst())
+ break;
case ATOMIC_READ:
case ATOMIC_WRITE:
case ATOMIC_RMW: {
ModelAction *ret = NULL;
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
+ if (prev == act)
+ continue;
if (prev->could_synchronize_with(act)) {
ret = prev;
break;
case ATOMIC_LOCK:
case ATOMIC_TRYLOCK: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
}
case ATOMIC_UNLOCK: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
}
case ATOMIC_WAIT: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
case ATOMIC_NOTIFY_ALL:
case ATOMIC_NOTIFY_ONE: {
/* linear search: from most recent to oldest */
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = obj_map.get(act->get_location());
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++) {
ModelAction *prev = *rit;
/**
* @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
/**
* Process a write ModelAction
* @param curr The ModelAction to process
+ * @param work The work queue, for adding fixup work
* @return True if the mo_graph was updated or promises were resolved
*/
-bool ModelExecution::process_write(ModelAction *curr)
+bool ModelExecution::process_write(ModelAction *curr, work_queue_t *work)
{
/* Readers to which we may send our future value */
ModelVector<ModelAction *> send_fv;
if (promise) {
earliest_promise_reader = promise->get_reader(0);
- updated_promises = resolve_promise(curr, promise);
+ updated_promises = resolve_promise(curr, promise, work);
} else
earliest_promise_reader = NULL;
/* Must synchronize */
if (!synchronize(release, acquire))
return;
- /* Re-check all pending release sequences */
- work_queue->push_back(CheckRelSeqWorkEntry(NULL));
- /* Re-check act for mo_graph edges */
- work_queue->push_back(MOEdgeWorkEntry(acquire));
-
- /* propagate synchronization to later actions */
- action_list_t::reverse_iterator rit = action_trace.rbegin();
- for (; (*rit) != acquire; rit++) {
- ModelAction *propagate = *rit;
- if (acquire->happens_before(propagate)) {
- synchronize(acquire, propagate);
- /* Re-check 'propagate' for mo_graph edges */
- work_queue->push_back(MOEdgeWorkEntry(propagate));
- }
- }
+
+ /* Propagate the changed clock vector */
+ propagate_clockvector(acquire, work_queue);
} else {
/* Break release sequence with new edges:
* release --mo--> write --mo--> rf */
/**
* @brief Check whether a model action is enabled.
*
- * Checks whether a lock or join operation would be successful (i.e., is the
- * lock already locked, or is the joined thread already complete). If not, put
- * the action in a waiter list.
+ * Checks whether an operation would be successful (i.e., is a lock already
+ * locked, or is the joined thread already complete).
+ *
+ * For yield-blocking, yields are never enabled.
*
* @param curr is the ModelAction to check whether it is enabled.
* @return a bool that indicates whether the action is enabled.
thread_blocking_check_promises(blocking, get_thread(curr));
return false;
}
+ } else if (params->yieldblock && curr->is_yield()) {
+ return false;
}
return true;
*
* @param curr The current action to process
* @return The ModelAction that is actually executed; may be different than
- * curr; may be NULL, if the current action is not enabled to run
+ * curr
*/
ModelAction * ModelExecution::check_current_action(ModelAction *curr)
{
if (act->is_read() && !second_part_of_rmw && process_read(act))
update = true;
- if (act->is_write() && process_write(act))
+ if (act->is_write() && process_write(act, &work_queue))
update = true;
if (act->is_fence() && process_fence(act))
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)
{
}
}
+/**
+ * @brief Propagate a modified clock vector to actions later in the execution
+ * order
+ *
+ * After an acquire operation lazily completes a release-sequence
+ * synchronization, we must update all clock vectors for operations later than
+ * the acquire in the execution order.
+ *
+ * @param acquire The ModelAction whose clock vector must be propagated
+ * @param work The work queue to which we can add work items, if this
+ * propagation triggers more updates (e.g., to the modification order)
+ */
+void ModelExecution::propagate_clockvector(ModelAction *acquire, work_queue_t *work)
+{
+ /* Re-check all pending release sequences */
+ work->push_back(CheckRelSeqWorkEntry(NULL));
+ /* Re-check read-acquire for mo_graph edges */
+ work->push_back(MOEdgeWorkEntry(acquire));
+
+ /* propagate synchronization to later actions */
+ action_list_t::reverse_iterator rit = action_trace.rbegin();
+ for (; (*rit) != acquire; rit++) {
+ ModelAction *propagate = *rit;
+ if (acquire->happens_before(propagate)) {
+ synchronize(acquire, propagate);
+ /* Re-check 'propagate' for mo_graph edges */
+ work->push_back(MOEdgeWorkEntry(propagate));
+ }
+ }
+}
+
/**
* Attempt to resolve all stashed operations that might synchronize with a
* release sequence for a given location. This implements the "lazy" portion of
updated = true;
if (updated) {
- /* Re-check all pending release sequences */
- work_queue->push_back(CheckRelSeqWorkEntry(NULL));
- /* Re-check read-acquire for mo_graph edges */
- if (acquire->is_read())
- work_queue->push_back(MOEdgeWorkEntry(acquire));
-
- /* propagate synchronization to later actions */
- action_list_t::reverse_iterator rit = action_trace.rbegin();
- for (; (*rit) != acquire; rit++) {
- ModelAction *propagate = *rit;
- if (acquire->happens_before(propagate)) {
- synchronize(acquire, propagate);
- /* Re-check 'propagate' for mo_graph edges */
- work_queue->push_back(MOEdgeWorkEntry(propagate));
- }
- }
+ /* Propagate the changed clock vector */
+ propagate_clockvector(acquire, work_queue);
}
if (complete) {
it = pending_rel_seqs.erase(it);
int tid = id_to_int(act->get_tid());
ModelAction *uninit = NULL;
int uninit_id = -1;
- action_list_t *list = get_safe_ptr_action(obj_map, act->get_location());
+ action_list_t *list = get_safe_ptr_action(&obj_map, act->get_location());
if (list->empty() && act->is_atomic_var()) {
uninit = get_uninitialized_action(act);
uninit_id = id_to_int(uninit->get_tid());
if (act->is_wait()) {
void *mutex_loc = (void *) act->get_value();
- get_safe_ptr_action(obj_map, mutex_loc)->push_back(act);
+ get_safe_ptr_action(&obj_map, mutex_loc)->push_back(act);
SnapVector<action_list_t> *vec = get_safe_ptr_vect_action(&obj_thrd_map, mutex_loc);
if (tid >= (int)vec->size())
ModelAction * ModelExecution::get_last_seq_cst_write(ModelAction *curr) const
{
void *location = curr->get_location();
- action_list_t *list = get_safe_ptr_action(obj_map, location);
+ action_list_t *list = obj_map.get(location);
/* Find: max({i in dom(S) | seq_cst(t_i) && isWrite(t_i) && samevar(t_i, t)}) */
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); (*rit) != curr; rit++)
*/
ModelAction * ModelExecution::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);
+ /* All fences should have location FENCE_LOCATION */
+ action_list_t *list = obj_map.get(FENCE_LOCATION);
+
+ if (!list)
+ return NULL;
+
action_list_t::reverse_iterator rit = list->rbegin();
if (before_fence) {
ModelAction * ModelExecution::get_last_unlock(ModelAction *curr) const
{
void *location = curr->get_location();
- action_list_t *list = get_safe_ptr_action(obj_map, location);
+ action_list_t *list = obj_map.get(location);
/* Find: max({i in dom(S) | isUnlock(t_i) && samevar(t_i, t)}) */
action_list_t::reverse_iterator rit;
for (rit = list->rbegin(); rit != list->rend(); rit++)
* Resolve a Promise with a current write.
* @param write The ModelAction that is fulfilling Promises
* @param promise The Promise to resolve
+ * @param work The work queue, for adding new fixup work
* @return True if the Promise was successfully resolved; false otherwise
*/
-bool ModelExecution::resolve_promise(ModelAction *write, Promise *promise)
+bool ModelExecution::resolve_promise(ModelAction *write, Promise *promise,
+ work_queue_t *work)
{
ModelVector<ModelAction *> actions_to_check;
for (unsigned int i = 0; i < promise->get_num_readers(); i++) {
ModelAction *read = promise->get_reader(i);
- read_from(read, write);
+ if (read_from(read, write)) {
+ /* Propagate the changed clock vector */
+ propagate_clockvector(read, work);
+ }
actions_to_check.push_back(read);
}
/* 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;
}
}
{
action_list_t::const_iterator it;
- model_print("---------------------------------------------------------------------\n");
+ model_print("------------------------------------------------------------------------------------\n");
+ model_print("# t Action type MO Location Value Rf CV\n");
+ model_print("------------------------------------------------------------------------------------\n");
unsigned int hash = 0;
hash = hash^(hash<<3)^((*it)->hash());
}
model_print("HASH %u\n", hash);
- model_print("---------------------------------------------------------------------\n");
+ model_print("------------------------------------------------------------------------------------\n");
}
#if SUPPORT_MOD_ORDER_DUMP
mo_graph->dumpNodes(file);
ModelAction **thread_array = (ModelAction **)model_calloc(1, sizeof(ModelAction *) * get_num_threads());
- for (action_list_t::iterator it = action_trace.begin(); it != action_trace.end(); it++) {
+ for (action_list_t::const_iterator it = action_trace.begin(); it != action_trace.end(); it++) {
ModelAction *act = *it;
if (act->is_read()) {
mo_graph->dot_print_node(file, act);
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++) {
*/
void ModelExecution::add_thread(Thread *t)
{
- thread_map.put(id_to_int(t->get_id()), t);
+ unsigned int i = id_to_int(t->get_id());
+ if (i >= thread_map.size())
+ thread_map.resize(i + 1);
+ thread_map[i] = t;
if (!t->is_model_thread())
scheduler->add_thread(t);
}
*/
Thread * ModelExecution::get_thread(thread_id_t tid) const
{
- return thread_map.get(id_to_int(tid));
+ unsigned int i = id_to_int(tid);
+ if (i < thread_map.size())
+ return thread_map[i];
+ return NULL;
}
/**
{
while (!pending_rel_seqs.empty() &&
is_feasible_prefix_ignore_relseq() &&
- !unrealizedraces.empty()) {
+ haveUnrealizedRaces()) {
model_print("*** WARNING: release sequence fixup action "
"(%zu pending release seuqence(s)) ***\n",
pending_rel_seqs.size());
projects / model-checker.git / blobdiff