X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=model.cc;h=d9ff365e6808494c4c667272f7dd9b7c4f9d5a5f;hb=bee1e27429b9a66e414eb83cf14e2089dd40a79e;hp=0122922d376ca03a742f03729585f3c48db7b09a;hpb=b2f34d7f1d030f414786ea0b1a5709dcac604c7b;p=model-checker.git diff --git a/model.cc b/model.cc index 0122922..d9ff365 100644 --- a/model.cc +++ b/model.cc @@ -61,7 +61,7 @@ struct model_snapshot_members { unsigned int next_thread_id; modelclock_t used_sequence_numbers; ModelAction *next_backtrack; - std::vector< bug_message *, SnapshotAlloc > bugs; + SnapVector bugs; struct execution_stats stats; bool failed_promise; bool too_many_reads; @@ -85,12 +85,12 @@ ModelChecker::ModelChecker(struct model_params params) : obj_map(new HashTable()), lock_waiters_map(new HashTable()), condvar_waiters_map(new HashTable()), - obj_thrd_map(new HashTable *, uintptr_t, 4 >()), - promises(new std::vector< Promise *, SnapshotAlloc >()), - futurevalues(new std::vector< struct PendingFutureValue, SnapshotAlloc >()), - pending_rel_seqs(new std::vector< struct release_seq *, SnapshotAlloc >()), - thrd_last_action(new std::vector< ModelAction *, SnapshotAlloc >(1)), - thrd_last_fence_release(new std::vector< ModelAction *, SnapshotAlloc >()), + obj_thrd_map(new HashTable *, uintptr_t, 4 >()), + promises(new SnapVector()), + futurevalues(new SnapVector()), + pending_rel_seqs(new SnapVector()), + thrd_last_action(new SnapVector(1)), + thrd_last_fence_release(new SnapVector()), node_stack(new NodeStack()), priv(new struct model_snapshot_members()), mo_graph(new CycleGraph()) @@ -137,11 +137,11 @@ static action_list_t * get_safe_ptr_action(HashTable * get_safe_ptr_vect_action(HashTable *, uintptr_t, 4> * hash, void * ptr) +static SnapVector * get_safe_ptr_vect_action(HashTable *, uintptr_t, 4> * hash, void * ptr) { - std::vector *tmp = hash->get(ptr); + SnapVector *tmp = hash->get(ptr); if (tmp == NULL) { - tmp = new std::vector(); + tmp = new SnapVector(); hash->put(ptr, tmp); } return tmp; @@ -642,8 +642,8 @@ ModelAction * ModelChecker::get_last_fence_conflict(ModelAction *act) const * load-acquire * or * load --sb-> fence-acquire */ - std::vector< ModelAction *, ModelAlloc > acquire_fences(get_num_threads(), NULL); - std::vector< ModelAction *, ModelAlloc > prior_loads(get_num_threads(), NULL); + ModelVector acquire_fences(get_num_threads(), NULL); + ModelVector prior_loads(get_num_threads(), NULL); bool found_acquire_fences = false; for ( ; rit != list->rend(); rit++) { ModelAction *prev = *rit; @@ -1080,7 +1080,7 @@ void ModelChecker::add_future_value(const ModelAction *writer, ModelAction *read bool ModelChecker::process_write(ModelAction *curr) { /* Readers to which we may send our future value */ - std::vector< ModelAction *, ModelAlloc > send_fv; + ModelVector send_fv; bool updated_mod_order = w_modification_order(curr, &send_fv); int promise_idx = get_promise_to_resolve(curr); @@ -1704,7 +1704,7 @@ bool ModelChecker::should_read_instead(const ModelAction *curr, const T *rf, con if (!mo_graph->checkReachable(rf, other_rf)) return false; - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); action_list_t *list = &(*thrd_lists)[id_to_int(curr->get_tid())]; action_list_t::reverse_iterator rit = list->rbegin(); ASSERT((*rit) == curr); @@ -1747,7 +1747,7 @@ bool ModelChecker::check_recency(ModelAction *curr, const T *rf) const curr->get_node()->get_read_from_promise_size() <= 1) return true; - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); int tid = id_to_int(curr->get_tid()); ASSERT(tid < (int)thrd_lists->size()); action_list_t *list = &(*thrd_lists)[tid]; @@ -1805,13 +1805,16 @@ bool ModelChecker::check_recency(ModelAction *curr, const T *rf) const template bool ModelChecker::r_modification_order(ModelAction *curr, const rf_type *rf) { - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); unsigned int i; bool added = false; ASSERT(curr->is_read()); /* Last SC fence in the current thread */ ModelAction *last_sc_fence_local = get_last_seq_cst_fence(curr->get_tid(), NULL); + ModelAction *last_sc_write = NULL; + if (curr->is_seqcst()) + last_sc_write = get_last_seq_cst_write(curr); /* Iterate over all threads */ for (i = 0; i < thrd_lists->size(); i++) { @@ -1831,7 +1834,18 @@ bool ModelChecker::r_modification_order(ModelAction *curr, const rf_type *rf) for (rit = list->rbegin(); rit != list->rend(); rit++) { ModelAction *act = *rit; - if (act->is_write() && !act->equals(rf) && act != curr) { + /* Skip curr */ + if (act == curr) + continue; + /* Don't want to add reflexive edges on 'rf' */ + if (act->equals(rf)) { + if (act->happens_before(curr)) + break; + else + continue; + } + + if (act->is_write()) { /* C++, Section 29.3 statement 5 */ if (curr->is_seqcst() && last_sc_fence_thread_local && *act < *last_sc_fence_thread_local) { @@ -1852,15 +1866,19 @@ bool ModelChecker::r_modification_order(ModelAction *curr, const rf_type *rf) } } + /* C++, Section 29.3 statement 3 (second subpoint) */ + if (curr->is_seqcst() && last_sc_write && act == last_sc_write) { + added = mo_graph->addEdge(act, rf) || added; + break; + } + /* * Include at most one act per-thread that "happens - * before" curr. Don't consider reflexively. + * before" curr */ - if (act->happens_before(curr) && act != curr) { + if (act->happens_before(curr)) { if (act->is_write()) { - if (!act->equals(rf)) { - added = mo_graph->addEdge(act, rf) || added; - } + added = mo_graph->addEdge(act, rf) || added; } else { const ModelAction *prevrf = act->get_reads_from(); const Promise *prevrf_promise = act->get_reads_from_promise(); @@ -1911,9 +1929,9 @@ bool ModelChecker::r_modification_order(ModelAction *curr, const rf_type *rf) * value. If NULL, then don't record any future values. * @return True if modification order edges were added; false otherwise */ -bool ModelChecker::w_modification_order(ModelAction *curr, std::vector< ModelAction *, ModelAlloc > *send_fv) +bool ModelChecker::w_modification_order(ModelAction *curr, ModelVector *send_fv) { - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); unsigned int i; bool added = false; ASSERT(curr->is_write()); @@ -2057,7 +2075,7 @@ bool ModelChecker::thin_air_constraint_may_allow(const ModelAction *writer, cons */ bool ModelChecker::mo_may_allow(const ModelAction *writer, const ModelAction *reader) { - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, reader->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, reader->get_location()); unsigned int i; /* Iterate over all threads */ for (i = 0; i < thrd_lists->size(); i++) { @@ -2158,7 +2176,7 @@ bool ModelChecker::release_seq_heads(const ModelAction *rf, release_heads->push_back(fence_release); int tid = id_to_int(rf->get_tid()); - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, rf->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, rf->get_location()); action_list_t *list = &(*thrd_lists)[tid]; action_list_t::const_reverse_iterator rit; @@ -2301,7 +2319,7 @@ void ModelChecker::get_release_seq_heads(ModelAction *acquire, bool ModelChecker::resolve_release_sequences(void *location, work_queue_t *work_queue) { bool updated = false; - std::vector< struct release_seq *, SnapshotAlloc >::iterator it = pending_rel_seqs->begin(); + SnapVector::iterator it = pending_rel_seqs->begin(); while (it != pending_rel_seqs->end()) { struct release_seq *pending = *it; ModelAction *acquire = pending->acquire; @@ -2382,7 +2400,7 @@ void ModelChecker::add_action_to_lists(ModelAction *act) if (uninit) action_trace->push_front(uninit); - std::vector *vec = get_safe_ptr_vect_action(obj_thrd_map, act->get_location()); + SnapVector *vec = get_safe_ptr_vect_action(obj_thrd_map, act->get_location()); if (tid >= (int)vec->size()) vec->resize(priv->next_thread_id); (*vec)[tid].push_back(act); @@ -2405,7 +2423,7 @@ void ModelChecker::add_action_to_lists(ModelAction *act) void *mutex_loc = (void *) act->get_value(); get_safe_ptr_action(obj_map, mutex_loc)->push_back(act); - std::vector *vec = get_safe_ptr_vect_action(obj_thrd_map, mutex_loc); + SnapVector *vec = get_safe_ptr_vect_action(obj_thrd_map, mutex_loc); if (tid >= (int)vec->size()) vec->resize(priv->next_thread_id); (*vec)[tid].push_back(act); @@ -2454,8 +2472,11 @@ ModelAction * ModelChecker::get_last_seq_cst_write(ModelAction *curr) const action_list_t *list = get_safe_ptr_action(obj_map, 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() && (*rit) != curr) + for (rit = list->rbegin(); (*rit) != curr; rit++) + ; + rit++; /* Skip past curr */ + for ( ; rit != list->rend(); rit++) + if ((*rit)->is_write() && (*rit)->is_seqcst()) return *rit; return NULL; } @@ -2549,7 +2570,7 @@ int ModelChecker::get_promise_to_resolve(const ModelAction *curr) const */ bool ModelChecker::resolve_promise(ModelAction *write, unsigned int promise_idx) { - std::vector< ModelAction *, ModelAlloc > actions_to_check; + ModelVector actions_to_check; Promise *promise = (*promises)[promise_idx]; for (unsigned int i = 0; i < promise->get_num_readers(); i++) { @@ -2724,7 +2745,7 @@ void ModelChecker::compute_relseq_breakwrites(ModelAction *curr) */ void ModelChecker::build_may_read_from(ModelAction *curr) { - std::vector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); + SnapVector *thrd_lists = get_safe_ptr_vect_action(obj_thrd_map, curr->get_location()); unsigned int i; ASSERT(curr->is_read()); @@ -2933,15 +2954,6 @@ void ModelChecker::add_thread(Thread *t) scheduler->add_thread(t); } -/** - * Removes a thread from the scheduler. - * @param the thread to remove. - */ -void ModelChecker::remove_thread(Thread *t) -{ - scheduler->remove_thread(t); -} - /** * @brief Get a Thread reference by its ID * @param tid The Thread's ID @@ -3030,6 +3042,7 @@ uint64_t ModelChecker::switch_to_master(ModelAction *act) { DBG(); Thread *old = thread_current(); + scheduler->set_current_thread(NULL); ASSERT(!old->get_pending()); old->set_pending(act); if (Thread::swap(old, &system_context) < 0) {