X-Git-Url: http://plrg.eecs.uci.edu/git/?p=model-checker.git;a=blobdiff_plain;f=model.cc;h=2c27567954f3618c9a94e3e5640955d5b08b1475;hp=73d212d0166d2ac3d2fc7368f25afac0333ac491;hb=59eb730e1d19a0825008c40eb521bfc5c29df5f9;hpb=12b1a10eeff58161619bafcfd8e288b3e2c76621 diff --git a/model.cc b/model.cc index 73d212d..2c27567 100644 --- a/model.cc +++ b/model.cc @@ -34,7 +34,7 @@ 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()), @@ -52,7 +52,7 @@ ModelChecker::ModelChecker(struct model_params params) : /** @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; @@ -65,7 +65,7 @@ ModelChecker::~ModelChecker() delete (*promises)[i]; delete promises; - delete pending_acq_rel_seq; + delete pending_rel_seqs; delete thrd_last_action; delete node_stack; @@ -95,7 +95,7 @@ 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; } @@ -150,6 +150,9 @@ Thread * ModelChecker::get_next_thread(ModelAction *curr) earliest_diverge=diverge; Node *nextnode = next->get_node(); + Node *prevnode = nextnode->get_parent(); + scheduler->update_sleep_set(prevnode); + /* Reached divergence point */ if (nextnode->increment_promise()) { /* The next node will try to satisfy a different set of promises. */ @@ -165,24 +168,63 @@ Thread * ModelChecker::get_next_thread(ModelAction *curr) node_stack->pop_restofstack(2); } else { /* Make a different thread execute for next step */ - Node *node = nextnode->get_parent(); - tid = node->get_next_backtrack(); + scheduler->add_sleep(thread_map->get(id_to_int(next->get_tid()))); + tid = prevnode->get_next_backtrack(); + /* Make sure the backtracked thread isn't sleeping. */ + scheduler->remove_sleep(thread_map->get(id_to_int(tid))); node_stack->pop_restofstack(1); if (diverge==earliest_diverge) { - earliest_diverge=node->get_action(); + earliest_diverge=prevnode->get_action(); } } + /* The correct sleep set is in the parent node. */ + execute_sleep_set(); + 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)); } +/** + * We need to know what the next actions of all threads in the sleep + * set will be. This method computes them and stores the actions at + * the corresponding thread object's pending action. + */ + +void ModelChecker::execute_sleep_set() { + for(unsigned int i=0;iget_enabled(thr) == THREAD_SLEEP_SET ) { + thr->set_state(THREAD_RUNNING); + scheduler->next_thread(thr); + Thread::swap(&system_context, thr); + thr->set_pending(priv->current_action); + } + } + priv->current_action = NULL; +} + +void ModelChecker::wake_up_sleeping_actions(ModelAction * curr) { + for(unsigned int i=0;iget_enabled(thr) == THREAD_SLEEP_SET ) { + ModelAction *pending_act=thr->get_pending(); + if (pending_act->could_synchronize_with(curr)) { + //Remove this thread from sleep set + scheduler->remove_sleep(thr); + } + } + } +} + /** * Queries the model-checker for more executions to explore and, if one * exists, resets the model-checker state to execute a new execution. @@ -199,7 +241,7 @@ bool ModelChecker::next_execution() if (isfinalfeasible()) { printf("Earliest divergence point since last feasible execution:\n"); if (earliest_diverge) - earliest_diverge->print(false); + earliest_diverge->print(); else printf("(Not set)\n"); @@ -208,7 +250,7 @@ bool ModelChecker::next_execution() } DEBUG("Number of acquires waiting on pending release sequences: %lu\n", - pending_acq_rel_seq->size()); + pending_rel_seqs->size()); if (isfinalfeasible() || DBG_ENABLED()) print_summary(); @@ -236,7 +278,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; @@ -270,7 +312,7 @@ ModelAction * ModelChecker::get_last_conflict(ModelAction *act) return NULL; } -/** This method find backtracking points where we should try to +/** This method finds backtracking points where we should try to * reorder the parameter ModelAction against. * * @param the ModelAction to find backtracking points for. @@ -295,9 +337,10 @@ void ModelChecker::set_backtracking(ModelAction *act) for(int i = low_tid; i < high_tid; i++) { thread_id_t tid = int_to_id(i); + if (!node->is_enabled(tid)) continue; - + /* Check if this has been explored already */ if (node->has_been_explored(tid)) continue; @@ -315,7 +358,6 @@ void ModelChecker::set_backtracking(ModelAction *act) if (unfair) continue; } - /* Cache the latest backtracking point */ if (!priv->next_backtrack || *prev > *priv->next_backtrack) priv->next_backtrack = prev; @@ -324,7 +366,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(); @@ -376,6 +419,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 */ @@ -473,6 +518,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; } @@ -525,7 +572,7 @@ bool ModelChecker::process_thread_action(ModelAction *curr) break; } case THREAD_START: { - check_promises(NULL, curr->get_cv()); + check_promises(curr->get_tid(), NULL, curr->get_cv()); break; } default: @@ -626,7 +673,6 @@ bool ModelChecker::check_action_enabled(ModelAction *curr) { Thread * ModelChecker::check_current_action(ModelAction *curr) { ASSERT(curr); - bool second_part_of_rmw = curr->is_rmwc() || curr->is_rmw(); if (!check_action_enabled(curr)) { @@ -637,8 +683,11 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) return get_next_thread(NULL); } + wake_up_sleeping_actions(curr); + ModelAction *newcurr = initialize_curr_action(curr); + /* Add the action to lists before any other model-checking tasks */ if (!second_part_of_rmw) add_action_to_lists(newcurr); @@ -650,7 +699,6 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) /* Initialize work_queue with the "current action" work */ work_queue_t work_queue(1, CheckCurrWorkEntry(curr)); - while (!work_queue.empty()) { WorkQueueEntry work = work_queue.front(); work_queue.pop_front(); @@ -709,9 +757,7 @@ Thread * ModelChecker::check_current_action(ModelAction *curr) } check_curr_backtracking(curr); - set_backtracking(curr); - return get_next_thread(curr); } @@ -755,7 +801,7 @@ 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. */ @@ -794,8 +840,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); @@ -941,7 +986,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; } @@ -1066,14 +1115,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; } @@ -1090,11 +1147,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 @@ -1154,13 +1215,19 @@ 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()) @@ -1189,6 +1256,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 */ } @@ -1218,6 +1286,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) @@ -1230,7 +1300,7 @@ bool ModelChecker::release_seq_head(const ModelAction *rf, rel_heads_list_t *rel ModelAction *last = get_last_action(int_to_id(i)); if (last && (rf->happens_before(last) || - last->get_type() == THREAD_FINISH)) + get_thread(int_to_id(i))->is_complete())) future_ordered = true; for (rit = list->rbegin(); rit != list->rend(); rit++) { @@ -1261,14 +1331,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; } @@ -1282,16 +1359,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); } } @@ -1311,9 +1391,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) { @@ -1324,7 +1405,7 @@ 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])) { if (act->synchronize_with(release_heads[i])) @@ -1351,10 +1432,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. @@ -1470,6 +1553,7 @@ 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]; @@ -1487,13 +1571,22 @@ bool ModelChecker::resolve_promises(ModelAction *write) 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); @@ -1519,16 +1612,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; @@ -1537,6 +1628,69 @@ 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; + } + } + } +} + /** * 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" @@ -1635,7 +1789,8 @@ void ModelChecker::dumpGraph(char *filename) { 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()); - fprintf(file, "N%u -> N%u[label=\"rf\", color=red];\n", action->get_seq_number(), action->get_reads_from()->get_seq_number()); + 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()); @@ -1696,7 +1851,7 @@ void ModelChecker::remove_thread(Thread *t) * @param tid The Thread's ID * @return A Thread reference */ -Thread * ModelChecker::get_thread(thread_id_t tid) +Thread * ModelChecker::get_thread(thread_id_t tid) const { return thread_map->get(id_to_int(tid)); } @@ -1706,7 +1861,7 @@ Thread * ModelChecker::get_thread(thread_id_t tid) * @param act The ModelAction * @return A Thread reference */ -Thread * ModelChecker::get_thread(ModelAction *act) +Thread * ModelChecker::get_thread(ModelAction *act) const { return get_thread(act->get_tid()); } @@ -1739,7 +1894,7 @@ bool ModelChecker::take_step() { if (has_asserted()) return false; - Thread * curr = thread_current(); + Thread *curr = thread_current(); if (curr) { if (curr->get_state() == THREAD_READY) { ASSERT(priv->current_action); @@ -1753,22 +1908,23 @@ bool ModelChecker::take_step() { 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); /* 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);