wakeup_tree_.remove_min_single_process_subtree();
}
+ void State::remove_subtree_at_aid(const aid_t proc) {
+ wakeup_tree_.remove_subtree_at_aid(proc);
+
+ }
+
odpor::WakeupTree::InsertionResult State::insert_into_wakeup_tree(const odpor::PartialExecution& pe,
const odpor::Execution& E)
{
* `N` running actor `p` of this state's wakeup tree
*/
void remove_subtree_using_current_out_transition();
+ void remove_subtree_at_aid(aid_t proc);
bool has_empty_tree() const { return this->wakeup_tree_.empty(); }
std::string string_of_wut() const { return this->wakeup_tree_.string_of_whole_tree(); }
const aid_t next = reduction_mode_ == ReductionMode::odpor ? state->next_odpor_transition()
: std::get<0>(state->next_transition_guided());
- if (next < 0 || not state->is_actor_enabled(next)) {
- // If there is no more transition in the current state (or if ODPOR picked an actor that is not enabled --
- // ReversibleRace is an overapproximation), backtrace
+ if (next < 0) {
+ // If there is no more transition in the current state ), backtrace
+ XBT_VERB("%lu actors remain, but none of them need to be interleaved (depth %zu).", state->get_actor_count(),
+ stack_.size() + 1);
+
+ if (state->get_actor_count() == 0) {
+ get_remote_app().finalize_app();
+ XBT_VERB("Execution came to an end at %s (state: %ld, depth: %zu)", get_record_trace().to_string().c_str(),
+ state->get_num(), stack_.size());
+ }
+
+ this->backtrack();
+ continue;
+ }
+ if (not state->is_actor_enabled(next)) {
+ // if ODPOR picked an actor that is not enabled -- ReversibleRace is an overapproximation
+ xbt_assert(reduction_mode_ == ReductionMode::odpor,
+ "Only ODPOR should be fool enough to try to execute a disabled transition");
+ XBT_VERB("Preventing ODPOR exploration from executing a disabled transition. The reversibility of the race "
+ "must have been overapproximated");
+
+ state->remove_subtree_at_aid(next);
+ state->add_sleep_set(state->get_actors_list().at(next).get_transition());
XBT_VERB("%lu actors remain, but none of them need to be interleaved (depth %zu).", state->get_actor_count(),
stack_.size() + 1);
XBT_DEBUG("\tPerformed ODPOR 'clean-up'. Sleep set has:");
for (const auto& [aid, transition] : state->get_sleep_set())
XBT_DEBUG("\t <%ld,%s>", aid, transition->to_string().c_str());
- if (not state->has_empty_tree()) {
- XBT_DEBUG("\t found the following non-empty WuT:\n"
- "%s", state->string_of_wut().c_str());
- return state;
- }
}
return nullptr;
}
* ("eventually looks like C", viz. the `~_E` relation)
*/
for (auto e_prime = static_cast<odpor::Execution::EventHandle>(0); e_prime <= last_event.value(); ++e_prime) {
- XBT_DEBUG("ODPOR: Now considering all possible race with `%u`", e_prime);
- for (const auto e : execution_seq_.get_reversible_races_of(e_prime)) {
+ XBT_DEBUG("ODPOR: Now considering all possible race with `%u`", e_prime);
+ for (const auto e : execution_seq_.get_reversible_races_of(e_prime)) {
XBT_DEBUG("ODPOR: Reversible race detected between events `%u` and `%u`", e, e_prime);
State& prev_state = *stack_[e];
if (const auto v = execution_seq_.get_odpor_extension_from(e, e_prime, prev_state); v.has_value()) {
bool ReversibleRaceCalculator::is_race_reversible_MutexWait(const Execution& E, Execution::EventHandle e1,
const Transition* /*e2*/)
{
- // The only possibilities for e1 to satisfy the pre-condition are :
- // - MUTEX_ASYNC_LOCK
+ // TODO: for now we over approximate the reversibility
-
- const auto e1_action = E.get_transition_for_handle(e1)->type_;
- xbt_assert(e1_action == Transition::Type::MUTEX_UNLOCK);
- return e1_action != Transition::Type::MUTEX_ASYNC_LOCK && e1_action != Transition::Type::MUTEX_UNLOCK;
+ return true;
}
bool ReversibleRaceCalculator::is_race_reversible_SemAsyncLock(const Execution&, Execution::EventHandle /*e1*/,
bool ReversibleRaceCalculator::is_race_reversible_SemWait(const Execution& E, Execution::EventHandle e1,
const Transition* /*e2*/)
{
- // Reversible with everynbody but unlock which creates a free token
+
const auto e1_transition = E.get_transition_for_handle(e1);
if (e1_transition->type_ == Transition::Type::SEM_UNLOCK &&
- static_cast<const SemaphoreTransition*>(e1_transition)->get_capacity() <= 1)
+ static_cast<const SemaphoreTransition*>(e1_transition)->get_capacity() <= 1) {
return false;
+ }
+ xbt_assert(false, "SEM_WAIT that is dependent with a SEM_UNLOCK should not be reversible. FixMe");
return true;
}
XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_wut, mc, "Logging specific to ODPOR WakeupTrees");
-
namespace simgrid::mc::odpor {
void WakeupTreeNode::add_child(WakeupTreeNode* node)
std::string tabulations = "";
for (int i = 0; i < indentation_level; i++)
tabulations += " ";
- std::string final_string = action_ == nullptr ? "<>\n" :
- tabulations + "Actor " + std::to_string(action_->aid_) + ": " + action_->to_string(true) + "\n";
+ std::string final_string = action_ == nullptr ? "<>\n"
+ : tabulations + "Actor " + std::to_string(action_->aid_) + ": " +
+ action_->to_string(true) + "\n";
for (auto node : children_)
final_string += node->string_of_whole_tree(indentation_level + 1);
return final_string;
}
}
+void WakeupTree::remove_subtree_at_aid(aid_t proc)
+{
+ for (const auto& child : root_->get_ordered_children())
+ if (child->get_actor() == proc) {
+ this->remove_subtree_rooted_at(child);
+ break;
+ }
+}
+
void WakeupTree::remove_min_single_process_subtree()
{
if (const auto node = get_min_single_process_node(); node.has_value()) {
*/
void remove_min_single_process_subtree();
+ void remove_subtree_at_aid(aid_t proc);
+
/**
* @brief Whether or not this tree is considered empty
*
std::string SemaphoreTransition::to_string(bool verbose) const
{
if (type_ == Type::SEM_ASYNC_LOCK || type_ == Type::SEM_UNLOCK)
- return xbt::string_printf("%s(semaphore: %u, capacity: %u)", Transition::to_c_str(type_), capacity_, sem_);
+ return xbt::string_printf("%s(semaphore: %u, capacity: %u)", Transition::to_c_str(type_), sem_, capacity_);
if (type_ == Type::SEM_WAIT)
- return xbt::string_printf("%s(semaphore: %u, capacity: %u, granted: %s)", Transition::to_c_str(type_), capacity_,
- sem_, granted_ ? "yes" : "no");
+ return xbt::string_printf("%s(semaphore: %u, capacity: %u, granted: %s)", Transition::to_c_str(type_), sem_,
+ capacity_,
+ granted_ ? "yes" : "no");
THROW_IMPOSSIBLE;
}
SemaphoreTransition::SemaphoreTransition(aid_t issuer, int times_considered, Type type, std::stringstream& stream)
if (type_ == Type::SEM_UNLOCK && other->type_ == Type::SEM_UNLOCK)
return false;
+ // UNLCOK indep with a WAIT if the semaphore had enought capacity anyway
+ if (type_ == Type::SEM_UNLOCK && capacity_ > 1 && other->type_ == Type::SEM_WAIT )
+ return false;
+
// WAIT indep WAIT:
// if both enabled (may happen in the initial value is sufficient), the ordering has no impact on the result.
// If only one enabled, the other won't be enabled by the first one.
if (type_ == Type::SEM_WAIT && other->type_ == Type::SEM_WAIT)
return false;
+
return true; // Other semaphore cases are dependent
}
