+ return updated;
+}
+
+/**
+ * Performs various bookkeeping operations for the current ModelAction. For
+ * instance, adds action to the per-object, per-thread action vector and to the
+ * action trace list of all thread actions.
+ *
+ * @param act is the ModelAction to add.
+ */
+void ModelChecker::add_action_to_lists(ModelAction *act)
+{
+ int tid = id_to_int(act->get_tid());
+ action_trace->push_back(act);
+
+ obj_map->get_safe_ptr(act->get_location())->push_back(act);
+
+ std::vector<action_list_t> *vec = obj_thrd_map->get_safe_ptr(act->get_location());
+ if (tid >= (int)vec->size())
+ vec->resize(priv->next_thread_id);
+ (*vec)[tid].push_back(act);
+
+ if ((int)thrd_last_action->size() <= tid)
+ thrd_last_action->resize(get_num_threads());
+ (*thrd_last_action)[tid] = act;
+}
+
+ModelAction * ModelChecker::get_last_action(thread_id_t tid)
+{
+ int nthreads = get_num_threads();
+ if ((int)thrd_last_action->size() < nthreads)
+ thrd_last_action->resize(nthreads);
+ return (*thrd_last_action)[id_to_int(tid)];
+}
+
+/**
+ * Gets the last memory_order_seq_cst action (in the total global sequence)
+ * performed on a particular object (i.e., memory location).
+ * @param location The object location to check
+ * @return The last seq_cst action performed
+ */
+ModelAction * ModelChecker::get_last_seq_cst(const void *location)
+{
+ action_list_t *list = obj_map->get_safe_ptr(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 != list->rend(); rit++)
+ if ((*rit)->is_write() && (*rit)->is_seqcst())
+ return *rit;
+ return NULL;
+}
+
+ModelAction * ModelChecker::get_parent_action(thread_id_t tid)
+{
+ ModelAction *parent = get_last_action(tid);
+ if (!parent)
+ parent = get_thread(tid)->get_creation();
+ return parent;
+}
+
+/**
+ * Returns the clock vector for a given thread.
+ * @param tid The thread whose clock vector we want
+ * @return Desired clock vector
+ */
+ClockVector * ModelChecker::get_cv(thread_id_t tid)
+{
+ return get_parent_action(tid)->get_cv();
+}
+
+/**
+ * Resolve a set of Promises with a current write. The set is provided in the
+ * Node corresponding to @a write.
+ * @param write The ModelAction that is fulfilling Promises
+ * @return True if promises were resolved; false otherwise
+ */
+bool ModelChecker::resolve_promises(ModelAction *write)
+{
+ bool resolved = false;
+ 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->read_from(write);
+ r_modification_order(read, write);
+ post_r_modification_order(read, write);
+ promises->erase(promises->begin() + promise_index);
+ resolved = true;
+ } else
+ promise_index++;
+ }
+
+ return resolved;
+}
+
+/**
+ * Compute the set of promises that could potentially be satisfied by this
+ * action. Note that the set computation actually appears in the Node, not in
+ * ModelChecker.
+ * @param curr The ModelAction that may satisfy promises
+ */
+void ModelChecker::compute_promises(ModelAction *curr)
+{
+ for (unsigned int i = 0; i < promises->size(); i++) {
+ Promise *promise = (*promises)[i];
+ const ModelAction *act = promise->get_action();
+ if (!act->happens_before(curr) &&
+ act->is_read() &&
+ !act->is_synchronizing(curr) &&
+ !act->same_thread(curr) &&
+ promise->get_value() == curr->get_value()) {
+ curr->get_node()->set_promise(i);
+ }
+ }
+}
+
+/** Checks promises in response to change in ClockVector Threads. */
+void ModelChecker::check_promises(ClockVector *old_cv, ClockVector *merge_cv)
+{
+ 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)) {
+ //This thread is no longer able to send values back to satisfy the promise
+ int num_synchronized_threads = promise->increment_threads();
+ if (num_synchronized_threads == get_num_threads()) {
+ //Promise has failed
+ failed_promise = true;
+ return;
+ }
+ }
+ }
+}
+
+/**
+ * Build up an initial set of all past writes that this 'read' action may read
+ * from. This set is determined by the clock vector's "happens before"
+ * relationship.
+ * @param curr is the current ModelAction that we are exploring; it must be a
+ * 'read' operation.
+ */
+void ModelChecker::build_reads_from_past(ModelAction *curr)
+{
+ std::vector<action_list_t> *thrd_lists = obj_thrd_map->get_safe_ptr(curr->get_location());
+ unsigned int i;
+ ASSERT(curr->is_read());
+
+ ModelAction *last_seq_cst = NULL;
+
+ /* Track whether this object has been initialized */
+ bool initialized = false;
+
+ if (curr->is_seqcst()) {
+ last_seq_cst = get_last_seq_cst(curr->get_location());
+ /* We have to at least see the last sequentially consistent write,
+ so we are initialized. */
+ if (last_seq_cst != NULL)
+ initialized = true;
+ }
+
+ /* Iterate over all threads */
+ for (i = 0; i < thrd_lists->size(); i++) {
+ /* Iterate over actions in thread, starting from most recent */
+ action_list_t *list = &(*thrd_lists)[i];
+ action_list_t::reverse_iterator rit;
+ for (rit = list->rbegin(); rit != list->rend(); rit++) {
+ ModelAction *act = *rit;
+
+ /* Only consider 'write' actions */
+ if (!act->is_write())
+ continue;
+
+ /* Don't consider more than one seq_cst write if we are a seq_cst read. */
+ if (!act->is_seqcst() || !curr->is_seqcst() || act == last_seq_cst) {
+ 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 */
+ if (act->happens_before(curr)) {
+ initialized = true;
+ break;
+ }
+ }
+ }
+
+ if (!initialized) {
+ /** @todo Need a more informative way of reporting errors. */
+ printf("ERROR: may read from uninitialized atomic\n");
+ }
+
+ if (DBG_ENABLED() || !initialized) {
+ printf("Reached read action:\n");
+ curr->print();
+ printf("Printing may_read_from\n");
+ curr->get_node()->print_may_read_from();
+ printf("End printing may_read_from\n");
+ }
+
+ ASSERT(initialized);
+}
+
+static void print_list(action_list_t *list)
+{
+ action_list_t::iterator it;
+
+ printf("---------------------------------------------------------------------\n");
+ printf("Trace:\n");
+
+ for (it = list->begin(); it != list->end(); it++) {