X-Git-Url: http://plrg.eecs.uci.edu/git/?p=c11tester.git;a=blobdiff_plain;f=model.cc;h=8267377faa791a2cfbc85f9027949c7338186635;hp=e7ab3bbed4298fb943e9704095ba3e0b58f109ab;hb=9b894e117ad1090ad6f54753cde7fd9b6ea60ab7;hpb=56ed2751a8f9fe48129271a5d6ba574d8a078166 diff --git a/model.cc b/model.cc index e7ab3bbe..8267377f 100644 --- a/model.cc +++ b/model.cc @@ -12,6 +12,7 @@ #include "promise.h" #include "datarace.h" #include "mutex.h" +#include "threads.h" #define INITIAL_THREAD_ID 0 @@ -25,6 +26,7 @@ ModelChecker::ModelChecker(struct model_params params) : num_executions(0), num_feasible_executions(0), diverge(NULL), + earliest_diverge(NULL), action_trace(new action_list_t()), thread_map(new HashTable()), obj_map(new HashTable()), @@ -32,24 +34,29 @@ ModelChecker::ModelChecker(struct model_params params) : obj_thrd_map(new HashTable, uintptr_t, 4 >()), promises(new std::vector()), futurevalues(new std::vector()), - pending_acq_rel_seq(new std::vector()), + pending_rel_seqs(new std::vector()), thrd_last_action(new std::vector(1)), node_stack(new NodeStack()), mo_graph(new CycleGraph()), failed_promise(false), too_many_reads(false), - asserted(false) + asserted(false), + bad_synchronization(false) { /* Allocate this "size" on the snapshotting heap */ priv = (struct model_snapshot_members *)calloc(1, sizeof(*priv)); /* First thread created will have id INITIAL_THREAD_ID */ priv->next_thread_id = INITIAL_THREAD_ID; + + /* 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); } /** @brief Destructor */ ModelChecker::~ModelChecker() { - for (int i = 0; i < get_num_threads(); i++) + for (unsigned int i = 0; i < get_num_threads(); i++) delete thread_map->get(i); delete thread_map; @@ -62,7 +69,7 @@ ModelChecker::~ModelChecker() delete (*promises)[i]; delete promises; - delete pending_acq_rel_seq; + delete pending_rel_seqs; delete thrd_last_action; delete node_stack; @@ -80,6 +87,7 @@ void ModelChecker::reset_to_initial_state() node_stack->reset_execution(); failed_promise = false; too_many_reads = false; + bad_synchronization = false; reset_asserted(); snapshotObject->backTrackBeforeStep(0); } @@ -91,11 +99,17 @@ thread_id_t ModelChecker::get_next_id() } /** @return the number of user threads created during this execution */ -int ModelChecker::get_num_threads() +unsigned int ModelChecker::get_num_threads() { return priv->next_thread_id; } +/** @return The currently executing Thread. */ +Thread * ModelChecker::get_current_thread() +{ + return scheduler->get_current_thread(); +} + /** @return a sequence number for a new ModelAction */ modelclock_t ModelChecker::get_next_seq_num() { @@ -136,6 +150,9 @@ Thread * ModelChecker::get_next_thread(ModelAction *curr) ModelAction *next = node_stack->get_next()->get_action(); if (next == diverge) { + if (earliest_diverge == NULL || *diverge < *earliest_diverge) + earliest_diverge=diverge; + Node *nextnode = next->get_node(); /* Reached divergence point */ if (nextnode->increment_promise()) { @@ -150,18 +167,26 @@ Thread * ModelChecker::get_next_thread(ModelAction *curr) /* 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(); + node_stack->pop_restofstack(2); } else { /* Make a different thread execute for next step */ Node *node = nextnode->get_parent(); tid = node->get_next_backtrack(); node_stack->pop_restofstack(1); + if (diverge==earliest_diverge) { + earliest_diverge=node->get_action(); + } } DEBUG("*** Divergence point ***\n"); + diverge = NULL; } else { tid = next->get_tid(); } - DEBUG("*** ModelChecker chose next thread = %d ***\n", tid); + DEBUG("*** ModelChecker chose next thread = %d ***\n", id_to_int(tid)); ASSERT(tid != THREAD_ID_T_NONE); return thread_map->get(id_to_int(tid)); } @@ -178,8 +203,20 @@ bool ModelChecker::next_execution() DBG(); num_executions++; - if (isfinalfeasible()) + + if (isfinalfeasible()) { + printf("Earliest divergence point since last feasible execution:\n"); + if (earliest_diverge) + earliest_diverge->print(); + else + printf("(Not set)\n"); + + earliest_diverge = NULL; num_feasible_executions++; + } + + DEBUG("Number of acquires waiting on pending release sequences: %zu\n", + pending_rel_seqs->size()); if (isfinalfeasible() || DBG_ENABLED()) print_summary(); @@ -207,7 +244,7 @@ ModelAction * ModelChecker::get_last_conflict(ModelAction *act) action_list_t::reverse_iterator rit; for (rit = list->rbegin(); rit != list->rend(); rit++) { ModelAction *prev = *rit; - if (act->is_synchronizing(prev)) + if (prev->could_synchronize_with(act)) return prev; } break; @@ -295,7 +332,8 @@ void ModelChecker::set_backtracking(ModelAction *act) if (!node->set_backtrack(tid)) continue; DEBUG("Setting backtrack: conflict = %d, instead tid = %d\n", - prev->get_tid(), t->get_id()); + id_to_int(prev->get_tid()), + id_to_int(t->get_id())); if (DBG_ENABLED()) { prev->print(); act->print(); @@ -334,7 +372,7 @@ bool ModelChecker::process_read(ModelAction *curr, bool second_part_of_rmw) bool r_status = false; if (!second_part_of_rmw) { - check_recency(curr); + check_recency(curr, reads_from); r_status = r_modification_order(curr, reads_from); } @@ -347,6 +385,8 @@ bool ModelChecker::process_read(ModelAction *curr, bool second_part_of_rmw) curr->read_from(reads_from); mo_graph->commitChanges(); + mo_check_promises(curr->get_tid(), reads_from); + updated |= r_status; } else if (!second_part_of_rmw) { /* Read from future value */ @@ -374,8 +414,10 @@ bool ModelChecker::process_read(ModelAction *curr, bool second_part_of_rmw) * * The unlock operation has to re-enable all of the threads that are * waiting on the lock. + * + * @return True if synchronization was updated; false otherwise */ -void ModelChecker::process_mutex(ModelAction *curr) { +bool ModelChecker::process_mutex(ModelAction *curr) { std::mutex *mutex = (std::mutex *)curr->get_location(); struct std::mutex_state *state = mutex->get_state(); switch (curr->get_type()) { @@ -397,8 +439,10 @@ void ModelChecker::process_mutex(ModelAction *curr) { state->islocked = true; ModelAction *unlock = get_last_unlock(curr); //synchronize with the previous unlock statement - if (unlock != NULL) + if (unlock != NULL) { curr->synchronize_with(unlock); + return true; + } break; } case ATOMIC_UNLOCK: { @@ -408,7 +452,7 @@ void ModelChecker::process_mutex(ModelAction *curr) { action_list_t *waiters = lock_waiters_map->get_safe_ptr(curr->get_location()); //activate all the waiting threads for (action_list_t::iterator rit = waiters->begin(); rit != waiters->end(); rit++) { - scheduler->add_thread(get_thread((*rit)->get_tid())); + scheduler->wake(get_thread(*rit)); } waiters->clear(); break; @@ -416,6 +460,7 @@ void ModelChecker::process_mutex(ModelAction *curr) { default: ASSERT(0); } + return false; } /** @@ -439,6 +484,8 @@ bool ModelChecker::process_write(ModelAction *curr) } mo_graph->commitChanges(); + mo_check_promises(curr->get_tid(), curr); + get_thread(curr)->set_return_value(VALUE_NONE); return updated_mod_order || updated_promises; } @@ -452,11 +499,11 @@ bool ModelChecker::process_write(ModelAction *curr) * (e.g., ATOMIC_{READ,WRITE,RMW,LOCK}, etc.) * * @param curr The current action - * @return True if synchronization was updated + * @return True if synchronization was updated or a thread completed */ bool ModelChecker::process_thread_action(ModelAction *curr) { - bool synchronized = false; + bool updated = false; switch (curr->get_type()) { case THREAD_CREATE: { @@ -473,7 +520,7 @@ bool ModelChecker::process_thread_action(ModelAction *curr) scheduler->sleep(waiting); } else { do_complete_join(curr); - synchronized = true; + updated = true; /* trigger rel-seq checks */ } break; } @@ -484,20 +531,91 @@ bool ModelChecker::process_thread_action(ModelAction *curr) Thread *wake = get_thread(act); scheduler->wake(wake); do_complete_join(act); - synchronized = true; + updated = true; /* trigger rel-seq checks */ } th->complete(); + updated = true; /* trigger rel-seq checks */ break; } case THREAD_START: { - check_promises(NULL, curr->get_cv()); + check_promises(curr->get_tid(), NULL, curr->get_cv()); break; } default: break; } - return synchronized; + return updated; +} + +/** + * @brief Process the current action for release sequence fixup activity + * + * Performs model-checker release sequence fixups for the current action, + * forcing a single pending release sequence to break (with a given, potential + * "loose" write) or to complete (i.e., synchronize). If a pending release + * sequence forms a complete release sequence, then we must perform the fixup + * synchronization, mo_graph additions, etc. + * + * @param curr The current action; must be a release sequence fixup action + * @param work_queue The work queue to which to add work items as they are + * generated + */ +void ModelChecker::process_relseq_fixup(ModelAction *curr, work_queue_t *work_queue) +{ + const ModelAction *write = curr->get_node()->get_relseq_break(); + struct release_seq *sequence = pending_rel_seqs->back(); + pending_rel_seqs->pop_back(); + ASSERT(sequence); + ModelAction *acquire = sequence->acquire; + const ModelAction *rf = sequence->rf; + const ModelAction *release = sequence->release; + ASSERT(acquire); + ASSERT(release); + ASSERT(rf); + ASSERT(release->same_thread(rf)); + + if (write == NULL) { + /** + * @todo Forcing a synchronization requires that we set + * modification order constraints. For instance, we can't allow + * a fixup sequence in which two separate read-acquire + * operations read from the same sequence, where the first one + * synchronizes and the other doesn't. Essentially, we can't + * allow any writes to insert themselves between 'release' and + * 'rf' + */ + + /* Must synchronize */ + if (!acquire->synchronize_with(release)) { + set_bad_synchronization(); + 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)) { + propagate->synchronize_with(acquire); + /* Re-check 'propagate' for mo_graph edges */ + work_queue->push_back(MOEdgeWorkEntry(propagate)); + } + } + } else { + /* Break release sequence with new edges: + * release --mo--> write --mo--> rf */ + mo_graph->addEdge(release, write); + mo_graph->addEdge(write, rf); + } + + /* See if we have realized a data race */ + if (checkDataRaces()) + set_assert(); } /** @@ -518,10 +636,14 @@ ModelAction * ModelChecker::initialize_curr_action(ModelAction *curr) if (curr->is_rmwc() || curr->is_rmw()) { newcurr = process_rmw(curr); delete curr; - compute_promises(newcurr); + + if (newcurr->is_rmw()) + compute_promises(newcurr); return newcurr; } + curr->set_seq_number(get_next_seq_num()); + newcurr = node_stack->explore_action(curr, scheduler->get_enabled()); if (newcurr) { /* First restore type and order in case of RMW operation */ @@ -534,18 +656,21 @@ ModelAction * ModelChecker::initialize_curr_action(ModelAction *curr) /* Discard duplicate ModelAction; use action from NodeStack */ delete curr; - /* If we have diverged, we need to reset the clock vector. */ - if (diverge == NULL) - newcurr->create_cv(get_parent_action(newcurr->get_tid())); + /* Always compute new clock vector */ + newcurr->create_cv(get_parent_action(newcurr->get_tid())); } else { newcurr = curr; + + /* Always compute new clock vector */ + newcurr->create_cv(get_parent_action(newcurr->get_tid())); /* * Perform one-time actions when pushing new ModelAction onto * NodeStack */ - curr->create_cv(get_parent_action(curr->get_tid())); - if (curr->is_write()) - compute_promises(curr); + if (newcurr->is_write()) + compute_promises(newcurr); + else if (newcurr->is_relseq_fixup()) + compute_relseq_breakwrites(newcurr); } return newcurr; } @@ -593,7 +718,7 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) /* Make the execution look like we chose to run this action * much later, when a lock is actually available to release */ get_current_thread()->set_pending(curr); - remove_thread(get_current_thread()); + scheduler->sleep(get_current_thread()); return get_next_thread(NULL); } @@ -608,6 +733,7 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) build_reads_from_past(curr); curr = newcurr; + /* Initialize work_queue with the "current action" work */ work_queue_t work_queue(1, CheckCurrWorkEntry(curr)); while (!work_queue.empty()) { @@ -618,8 +744,10 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) case WORK_CHECK_CURR_ACTION: { ModelAction *act = work.action; bool update = false; /* update this location's release seq's */ + bool update_all = false; /* update all release seq's */ - process_thread_action(curr); + if (process_thread_action(curr)) + update_all = true; if (act->is_read() && process_read(act, second_part_of_rmw)) update = true; @@ -627,10 +755,15 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) if (act->is_write() && process_write(act)) update = true; - if (act->is_mutex_op()) - process_mutex(act); + if (act->is_mutex_op() && process_mutex(act)) + update_all = true; + + if (act->is_relseq_fixup()) + process_relseq_fixup(curr, &work_queue); - if (update) + if (update_all) + work_queue.push_back(CheckRelSeqWorkEntry(NULL)); + else if (update) work_queue.push_back(CheckRelSeqWorkEntry(act->get_location())); break; } @@ -643,13 +776,15 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) bool updated = false; if (act->is_read()) { - if (r_modification_order(act, act->get_reads_from())) + const ModelAction *rf = act->get_reads_from(); + if (rf != NULL && r_modification_order(act, rf)) updated = true; } if (act->is_write()) { if (w_modification_order(act)) updated = true; } + mo_graph->commitChanges(); if (updated) work_queue.push_back(CheckRelSeqWorkEntry(act->get_location())); @@ -688,7 +823,8 @@ void ModelChecker::check_curr_backtracking(ModelAction * curr) { if ((!parnode->backtrack_empty() || !currnode->read_from_empty() || !currnode->future_value_empty() || - !currnode->promise_empty()) + !currnode->promise_empty() || + !currnode->relseq_break_empty()) && (!priv->next_backtrack || *curr > *priv->next_backtrack)) { priv->next_backtrack = curr; @@ -708,11 +844,14 @@ bool ModelChecker::promises_expired() { /** @return whether the current partial trace must be a prefix of a * feasible trace. */ bool ModelChecker::isfeasibleprefix() { - return promises->size() == 0 && pending_acq_rel_seq->size() == 0; + return promises->size() == 0 && pending_rel_seqs->size() == 0; } /** @return whether the current partial trace is feasible. */ bool ModelChecker::isfeasible() { + if (DBG_ENABLED() && mo_graph->checkForRMWViolation()) + DEBUG("Infeasible: RMW violation\n"); + return !mo_graph->checkForRMWViolation() && isfeasibleotherthanRMW(); } @@ -726,10 +865,12 @@ bool ModelChecker::isfeasibleotherthanRMW() { DEBUG("Infeasible: failed promise\n"); if (too_many_reads) DEBUG("Infeasible: too many reads\n"); + if (bad_synchronization) + DEBUG("Infeasible: bad synchronization ordering\n"); if (promises_expired()) DEBUG("Infeasible: promises expired\n"); } - return !mo_graph->checkForCycles() && !failed_promise && !too_many_reads && !promises_expired(); + return !mo_graph->checkForCycles() && !failed_promise && !too_many_reads && !bad_synchronization && !promises_expired(); } /** Returns whether the current completed trace is feasible. */ @@ -742,8 +883,7 @@ bool ModelChecker::isfinalfeasible() { /** Close out a RMWR by converting previous RMWR into a RMW or READ. */ ModelAction * ModelChecker::process_rmw(ModelAction *act) { - int tid = id_to_int(act->get_tid()); - ModelAction *lastread = get_last_action(tid); + ModelAction *lastread = get_last_action(act->get_tid()); lastread->process_rmw(act); if (act->is_rmw() && lastread->get_reads_from()!=NULL) { mo_graph->addRMWEdge(lastread->get_reads_from(), lastread); @@ -763,23 +903,21 @@ ModelAction * ModelChecker::process_rmw(ModelAction *act) { * * If so, we decide that the execution is no longer feasible. */ -void ModelChecker::check_recency(ModelAction *curr) { +void ModelChecker::check_recency(ModelAction *curr, const ModelAction *rf) { if (params.maxreads != 0) { + if (curr->get_node()->get_read_from_size() <= 1) return; - //Must make sure that execution is currently feasible... We could //accidentally clear by rolling back if (!isfeasible()) return; - std::vector *thrd_lists = obj_thrd_map->get_safe_ptr(curr->get_location()); int tid = id_to_int(curr->get_tid()); /* Skip checks */ if ((int)thrd_lists->size() <= tid) return; - action_list_t *list = &(*thrd_lists)[tid]; action_list_t::reverse_iterator rit = list->rbegin(); @@ -798,17 +936,18 @@ void ModelChecker::check_recency(ModelAction *curr) { ModelAction *act = *rit; if (!act->is_read()) return; - if (act->get_reads_from() != curr->get_reads_from()) + + if (act->get_reads_from() != rf) return; if (act->get_node()->get_read_from_size() <= 1) return; } - for (int i = 0; iget_node()->get_read_from_size(); i++) { //Get write const ModelAction * write = curr->get_node()->get_read_from_at(i); + //Need a different write - if (write==curr->get_reads_from()) + if (write==rf) continue; /* Test to see whether this is a feasible write to read from*/ @@ -890,7 +1029,11 @@ bool ModelChecker::r_modification_order(ModelAction *curr, const ModelAction *rf } } else { const ModelAction *prevreadfrom = act->get_reads_from(); - if (prevreadfrom != NULL && rf != prevreadfrom) { + //if the previous read is unresolved, keep going... + if (prevreadfrom == NULL) + continue; + + if (rf != prevreadfrom) { mo_graph->addEdge(prevreadfrom, rf); added = true; } @@ -931,10 +1074,10 @@ void ModelChecker::post_r_modification_order(ModelAction *curr, const ModelActio action_list_t::reverse_iterator rit; ModelAction *lastact = NULL; - /* Find last action that happens after curr */ + /* Find last action that happens after curr that is either not curr or a rmw */ for (rit = list->rbegin(); rit != list->rend(); rit++) { ModelAction *act = *rit; - if (curr->happens_before(act)) { + if (curr->happens_before(act) && (curr != act || curr->is_rmw())) { lastact = act; } else break; @@ -942,12 +1085,25 @@ void ModelChecker::post_r_modification_order(ModelAction *curr, const ModelActio /* Include at most one act per-thread that "happens before" curr */ if (lastact != NULL) { - if (lastact->is_read()) { + if (lastact==curr) { + //Case 1: The resolved read is a RMW, and we need to make sure + //that the write portion of the RMW mod order after rf + + mo_graph->addEdge(rf, lastact); + } else if (lastact->is_read()) { + //Case 2: The resolved read is a normal read and the next + //operation is a read, and we need to make sure the value read + //is mod ordered after rf + const ModelAction *postreadfrom = lastact->get_reads_from(); if (postreadfrom != NULL&&rf != postreadfrom) mo_graph->addEdge(rf, postreadfrom); - } else if (rf != lastact) { - mo_graph->addEdge(rf, lastact); + } else { + //Case 3: The resolved read is a normal read and the next + //operation is a write, and we need to make sure that the + //write is mod ordered after rf + if (lastact!=rf) + mo_graph->addEdge(rf, lastact); } break; } @@ -1002,14 +1158,22 @@ bool ModelChecker::w_modification_order(ModelAction *curr) ModelAction *act = *rit; if (act == curr) { /* - * If RMW, we already have all relevant edges, - * so just skip to next thread. - * If normal write, we need to look at earlier - * actions, so continue processing list. + * 1) If RMW and it actually read from something, then we + * already have all relevant edges, so just skip to next + * thread. + * + * 2) If RMW and it didn't read from anything, we should + * whatever edge we can get to speed up convergence. + * + * 3) If normal write, we need to look at earlier actions, so + * continue processing list. */ - if (curr->is_rmw()) - break; - else + if (curr->is_rmw()) { + if (curr->get_reads_from()!=NULL) + break; + else + continue; + } else continue; } @@ -1026,11 +1190,15 @@ bool ModelChecker::w_modification_order(ModelAction *curr) */ if (act->is_write()) mo_graph->addEdge(act, curr); - else if (act->is_read() && act->get_reads_from() != NULL) + else if (act->is_read()) { + //if previous read accessed a null, just keep going + if (act->get_reads_from() == NULL) + continue; mo_graph->addEdge(act->get_reads_from(), curr); + } added = true; break; - } else if (act->is_read() && !act->is_synchronizing(curr) && + } else if (act->is_read() && !act->could_synchronize_with(curr) && !act->same_thread(curr)) { /* We have an action that: (1) did not happen before us @@ -1090,14 +1258,24 @@ bool ModelChecker::thin_air_constraint_may_allow(const ModelAction * writer, con * @todo Finish lazy updating, when promises are fulfilled in the future * @param rf The action that might be part of a release sequence. Must be a * write. - * @param release_heads A pass-by-reference style return parameter. After + * @param release_heads A pass-by-reference style return parameter. After * execution of this function, release_heads will contain the heads of all the - * relevant release sequences, if any exists + * relevant release sequences, if any exists with certainty + * @param pending A pass-by-reference style return parameter which is only used + * when returning false (i.e., uncertain). Returns most information regarding + * an uncertain release sequence, including any write operations that might + * break the sequence. * @return true, if the ModelChecker is certain that release_heads is complete; * false otherwise */ -bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *release_heads) const +bool ModelChecker::release_seq_heads(const ModelAction *rf, + rel_heads_list_t *release_heads, + struct release_seq *pending) const { + /* Only check for release sequences if there are no cycles */ + if (mo_graph->checkForCycles()) + return false; + while (rf) { ASSERT(rf->is_write()); @@ -1121,6 +1299,7 @@ bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *rel }; if (!rf) { /* read from future: need to settle this later */ + pending->rf = NULL; return false; /* incomplete */ } @@ -1150,6 +1329,8 @@ bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *rel ASSERT(rf->same_thread(release)); + pending->writes.clear(); + bool certain = true; for (unsigned int i = 0; i < thrd_lists->size(); i++) { if (id_to_int(rf->get_tid()) == (int)i) @@ -1161,10 +1342,14 @@ bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *rel bool future_ordered = false; ModelAction *last = get_last_action(int_to_id(i)); - if (last && (rf->happens_before(last) || - last->get_type() == THREAD_FINISH)) + Thread *th = get_thread(int_to_id(i)); + if ((last && rf->happens_before(last)) || + !scheduler->is_enabled(th) || + th->is_complete()) future_ordered = true; + ASSERT(!th->is_model_thread() || future_ordered); + for (rit = list->rbegin(); rit != list->rend(); rit++) { const ModelAction *act = *rit; /* Reach synchronization -> this thread is complete */ @@ -1193,14 +1378,21 @@ bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *rel /* release --mo-> act --mo--> rf */ return true; /* complete */ } + /* act may break release sequence */ + pending->writes.push_back(act); certain = false; } if (!future_ordered) - return false; /* This thread is uncertain */ + certain = false; /* This thread is uncertain */ } - if (certain) + if (certain) { release_heads->push_back(release); + pending->writes.clear(); + } else { + pending->release = release; + pending->rf = rf; + } return certain; } @@ -1214,16 +1406,19 @@ bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *rel * @param act The 'acquire' action that may read from a release sequence * @param release_heads A pass-by-reference return parameter. Will be filled * with the head(s) of the release sequence(s), if they exists with certainty. - * @see ModelChecker::release_seq_head + * @see ModelChecker::release_seq_heads */ void ModelChecker::get_release_seq_heads(ModelAction *act, rel_heads_list_t *release_heads) { const ModelAction *rf = act->get_reads_from(); - bool complete; - complete = release_seq_head(rf, release_heads); - if (!complete) { + struct release_seq *sequence = (struct release_seq *)snapshot_calloc(1, sizeof(struct release_seq)); + sequence->acquire = act; + + if (!release_seq_heads(rf, release_heads, sequence)) { /* add act to 'lazy checking' list */ - pending_acq_rel_seq->push_back(act); + pending_rel_seqs->push_back(sequence); + } else { + snapshot_free(sequence); } } @@ -1243,9 +1438,10 @@ void ModelChecker::get_release_seq_heads(ModelAction *act, rel_heads_list_t *rel bool ModelChecker::resolve_release_sequences(void *location, work_queue_t *work_queue) { bool updated = false; - std::vector::iterator it = pending_acq_rel_seq->begin(); - while (it != pending_acq_rel_seq->end()) { - ModelAction *act = *it; + std::vector::iterator it = pending_rel_seqs->begin(); + while (it != pending_rel_seqs->end()) { + struct release_seq *pending = *it; + ModelAction *act = pending->acquire; /* Only resolve sequences on the given location, if provided */ if (location && act->get_location() != location) { @@ -1256,22 +1452,26 @@ bool ModelChecker::resolve_release_sequences(void *location, work_queue_t *work_ const ModelAction *rf = act->get_reads_from(); rel_heads_list_t release_heads; bool complete; - complete = release_seq_head(rf, &release_heads); + complete = release_seq_heads(rf, &release_heads, pending); for (unsigned int i = 0; i < release_heads.size(); i++) { if (!act->has_synchronized_with(release_heads[i])) { - updated = true; - act->synchronize_with(release_heads[i]); + if (act->synchronize_with(release_heads[i])) + updated = true; + else + set_bad_synchronization(); } } if (updated) { + /* Re-check all pending release sequences */ + work_queue->push_back(CheckRelSeqWorkEntry(NULL)); /* Re-check act for mo_graph edges */ work_queue->push_back(MOEdgeWorkEntry(act)); /* propagate synchronization to later actions */ - action_list_t::reverse_iterator it = action_trace->rbegin(); - for (; (*it) != act; it++) { - ModelAction *propagate = *it; + action_list_t::reverse_iterator rit = action_trace->rbegin(); + for (; (*rit) != act; rit++) { + ModelAction *propagate = *rit; if (act->happens_before(propagate)) { propagate->synchronize_with(act); /* Re-check 'propagate' for mo_graph edges */ @@ -1279,10 +1479,12 @@ bool ModelChecker::resolve_release_sequences(void *location, work_queue_t *work_ } } } - if (complete) - it = pending_acq_rel_seq->erase(it); - else + if (complete) { + it = pending_rel_seqs->erase(it); + snapshot_free(pending); + } else { it++; + } } // If we resolved promises or data races, see if we have realized a data race. @@ -1398,26 +1600,40 @@ ClockVector * ModelChecker::get_cv(thread_id_t tid) bool ModelChecker::resolve_promises(ModelAction *write) { bool resolved = false; + std::vector threads_to_check; 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); if (read->is_rmw()) { mo_graph->addRMWEdge(write, read); } + read->read_from(write); //First fix up the modification order for actions that happened //before the read r_modification_order(read, write); //Next fix up the modification order for actions that happened //after the read. 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); + promises->erase(promises->begin() + promise_index); + threads_to_check.push_back(read->get_tid()); + resolved = true; } else promise_index++; } + + //Check whether reading these writes has made threads unable to + //resolve promises + + for(unsigned int i=0;iget_action(); if (!act->happens_before(curr) && act->is_read() && - !act->is_synchronizing(curr) && + !act->could_synchronize_with(curr) && !act->same_thread(curr) && promise->get_value() == curr->get_value()) { curr->get_node()->set_promise(i); @@ -1443,16 +1659,14 @@ void ModelChecker::compute_promises(ModelAction *curr) } /** Checks promises in response to change in ClockVector Threads. */ -void ModelChecker::check_promises(ClockVector *old_cv, ClockVector *merge_cv) +void ModelChecker::check_promises(thread_id_t tid, 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()) { + if (promise->increment_threads(tid)) { //Promise has failed failed_promise = true; return; @@ -1461,6 +1675,92 @@ void ModelChecker::check_promises(ClockVector *old_cv, ClockVector *merge_cv) } } +/** 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.. + * + * 1. If tid=pthread, then we check what other threads are reachable + * through the mode order starting with pwrite. Those threads cannot + * perform a write that will resolve the promise due to modification + * order constraints. + * + * 2. If the tid is not pthread, we check whether pwrite can reach the + * action write through the modification order. If so, that thread + * cannot perform a future write that will resolve the promise due to + * modificatin order constraints. + * + * @parem tid The thread that either read from the model action + * write, or actually did the model action write. + * + * @parem write The ModelAction representing the relevant write. + */ + +void ModelChecker::mo_check_promises(thread_id_t tid, const ModelAction *write) { + void * location = write->get_location(); + for (unsigned int i = 0; i < promises->size(); i++) { + Promise *promise = (*promises)[i]; + const ModelAction *act = promise->get_action(); + + //Is this promise on the same location? + if ( act->get_location() != location ) + continue; + + //same thread as the promise + if ( act->get_tid()==tid ) { + + //do we have a pwrite for the promise, if not, set it + if (promise->get_write() == NULL ) { + promise->set_write(write); + } + if (mo_graph->checkPromise(write, promise)) { + failed_promise = true; + return; + } + } + + //Don't do any lookups twice for the same thread + if (promise->has_sync_thread(tid)) + continue; + + if (mo_graph->checkReachable(promise->get_write(), write)) { + if (promise->increment_threads(tid)) { + failed_promise = true; + return; + } + } + } +} + +/** + * Compute the set of writes that may break the current pending release + * sequence. This information is extracted from previou release sequence + * calculations. + * + * @param curr The current ModelAction. Must be a release sequence fixup + * action. + */ +void ModelChecker::compute_relseq_breakwrites(ModelAction *curr) +{ + if (pending_rel_seqs->empty()) + return; + + struct release_seq *pending = pending_rel_seqs->back(); + for (unsigned int i = 0; i < pending->writes.size(); i++) { + const ModelAction *write = pending->writes[i]; + curr->get_node()->add_relseq_break(write); + } + + /* NULL means don't break the sequence; just synchronize */ + curr->get_node()->add_relseq_break(NULL); +} + /** * 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" @@ -1546,6 +1846,34 @@ static void print_list(action_list_t *list) printf("---------------------------------------------------------------------\n"); } +#if SUPPORT_MOD_ORDER_DUMP +void ModelChecker::dumpGraph(char *filename) { + char buffer[200]; + sprintf(buffer, "%s.dot",filename); + FILE *file=fopen(buffer, "w"); + fprintf(file, "digraph %s {\n",filename); + 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++) { + ModelAction *action=*it; + if (action->is_read()) { + fprintf(file, "N%u [label=\"%u, T%u\"];\n", action->get_seq_number(),action->get_seq_number(), action->get_tid()); + if (action->get_reads_from()!=NULL) + fprintf(file, "N%u -> N%u[label=\"rf\", color=red];\n", action->get_seq_number(), action->get_reads_from()->get_seq_number()); + } + if (thread_array[action->get_tid()] != NULL) { + fprintf(file, "N%u -> N%u[label=\"sb\", color=blue];\n", thread_array[action->get_tid()]->get_seq_number(), action->get_seq_number()); + } + + thread_array[action->get_tid()]=action; + } + fprintf(file,"}\n"); + model_free(thread_array); + fclose(file); +} +#endif + void ModelChecker::print_summary() { printf("\n"); @@ -1558,6 +1886,8 @@ void ModelChecker::print_summary() char buffername[100]; sprintf(buffername, "exec%04u", num_executions); mo_graph->dumpGraphToFile(buffername); + sprintf(buffername, "graph%04u", num_executions); + dumpGraph(buffername); #endif if (!isfinalfeasible()) @@ -1586,12 +1916,35 @@ void ModelChecker::remove_thread(Thread *t) scheduler->remove_thread(t); } +/** + * @brief Get a Thread reference by its ID + * @param tid The Thread's ID + * @return A Thread reference + */ +Thread * ModelChecker::get_thread(thread_id_t tid) const +{ + return thread_map->get(id_to_int(tid)); +} + +/** + * @brief Get a reference to the Thread in which a ModelAction was executed + * @param act The ModelAction + * @return A Thread reference + */ +Thread * ModelChecker::get_thread(ModelAction *act) const +{ + return get_thread(act->get_tid()); +} + /** * Switch from a user-context to the "master thread" context (a.k.a. system * context). This switch is made with the intention of exploring a particular * model-checking action (described by a ModelAction object). Must be called * from a user-thread context. - * @param act The current action that will be explored. Must not be NULL. + * + * @param act The current action that will be explored. May be NULL only if + * trace is exiting via an assertion (see ModelChecker::set_assert and + * ModelChecker::has_asserted). * @return Return status from the 'swap' call (i.e., success/fail, 0/-1) */ int ModelChecker::switch_to_master(ModelAction *act) @@ -1611,35 +1964,57 @@ bool ModelChecker::take_step() { if (has_asserted()) return false; - Thread * curr = thread_current(); + Thread *curr = priv->current_action ? get_thread(priv->current_action) : NULL; if (curr) { if (curr->get_state() == THREAD_READY) { ASSERT(priv->current_action); priv->nextThread = check_current_action(priv->current_action); priv->current_action = NULL; + if (curr->is_blocked() || curr->is_complete()) scheduler->remove_thread(curr); } else { ASSERT(false); } } - Thread * next = scheduler->next_thread(priv->nextThread); + Thread *next = scheduler->next_thread(priv->nextThread); /* Infeasible -> don't take any more steps */ if (!isfeasible()) return false; - if (next) - next->set_state(THREAD_RUNNING); - DEBUG("(%d, %d)\n", curr ? curr->get_id() : -1, next ? next->get_id() : -1); + DEBUG("(%d, %d)\n", curr ? id_to_int(curr->get_id()) : -1, + next ? id_to_int(next->get_id()) : -1); + + /* + * Launch end-of-execution release sequence fixups only when there are: + * + * (1) no more user threads to run (or when execution replay chooses + * the 'model_thread') + * (2) pending release sequences + * (3) pending assertions (i.e., data races) + * (4) no pending promises + */ + if (!pending_rel_seqs->empty() && (!next || next->is_model_thread()) && + isfinalfeasible() && !unrealizedraces.empty()) { + printf("*** WARNING: release sequence fixup action (%zu pending release seuqences) ***\n", + pending_rel_seqs->size()); + ModelAction *fixup = new ModelAction(MODEL_FIXUP_RELSEQ, + std::memory_order_seq_cst, NULL, VALUE_NONE, + model_thread); + set_current_action(fixup); + return true; + } /* next == NULL -> don't take any more steps */ if (!next) return false; - if ( next->get_pending() != NULL ) { - //restart a pending action + next->set_state(THREAD_RUNNING); + + if (next->get_pending() != NULL) { + /* restart a pending action */ set_current_action(next->get_pending()); next->set_pending(NULL); next->set_state(THREAD_READY);