From 58cfad482a8c3ff22faee05a3f17bad26b8a5a0c Mon Sep 17 00:00:00 2001 From: Martin Quinson Date: Sun, 13 Feb 2022 22:19:46 +0100 Subject: [PATCH] Implement WaitAnyTransition --- src/kernel/activity/CommImpl.cpp | 4 +- src/kernel/actor/SimcallObserver.cpp | 129 ++++++++++++++++----------- src/kernel/actor/SimcallObserver.hpp | 29 +++--- src/mc/api/Transition.hpp | 2 +- src/mc/api/TransitionComm.cpp | 46 +++++++++- src/mc/api/TransitionComm.hpp | 9 ++ src/mc/checker/SafetyChecker.cpp | 1 + src/mc/mc_base.cpp | 2 +- 8 files changed, 148 insertions(+), 74 deletions(-) diff --git a/src/kernel/activity/CommImpl.cpp b/src/kernel/activity/CommImpl.cpp index 9a6579c12c..15b5cdf64c 100644 --- a/src/kernel/activity/CommImpl.cpp +++ b/src/kernel/activity/CommImpl.cpp @@ -417,8 +417,8 @@ void CommImpl::wait_for(actor::ActorImpl* issuer, double timeout) } else { /* If we reached this point, the wait simcall must have a timeout */ /* Otherwise it shouldn't be enabled and executed by the MC */ - if (timeout < 0.0) - THROW_IMPOSSIBLE; + xbt_assert(timeout >= 0.0, + "The checker asked me to raise a timeout on a communication that is not expecting any timeout"); set_state(issuer == src_actor_ ? State::SRC_TIMEOUT : State::DST_TIMEOUT); } finish(); diff --git a/src/kernel/actor/SimcallObserver.cpp b/src/kernel/actor/SimcallObserver.cpp index befdd70da6..fdb643d956 100644 --- a/src/kernel/actor/SimcallObserver.cpp +++ b/src/kernel/actor/SimcallObserver.cpp @@ -67,7 +67,7 @@ void RandomSimcall::prepare(int times_considered) XBT_DEBUG("MC_RANDOM(%d, %d) will return %d after %d times", min_, max_, next_value_, times_considered); } -int RandomSimcall::get_max_consider() const +int RandomSimcall::get_max_consider() { return max_ - min_ + 1; } @@ -83,12 +83,12 @@ std::string MutexLockSimcall::to_string(int times_considered) const return res; }*/ -bool MutexLockSimcall::is_enabled() const +bool MutexLockSimcall::is_enabled() { return not blocking_ || get_mutex()->get_owner() == nullptr || get_mutex()->get_owner() == get_issuer(); } -bool ConditionWaitSimcall::is_enabled() const +bool ConditionWaitSimcall::is_enabled() { static bool warned = false; if (not warned) { @@ -98,7 +98,7 @@ bool ConditionWaitSimcall::is_enabled() const return true; } -bool SemAcquireSimcall::is_enabled() const +bool SemAcquireSimcall::is_enabled() { static bool warned = false; if (not warned) { @@ -111,14 +111,15 @@ bool SemAcquireSimcall::is_enabled() const ActivityTestanySimcall::ActivityTestanySimcall(ActorImpl* actor, const std::vector& activities) : ResultingSimcall(actor, -1), activities_(activities) { +} + +int ActivityTestanySimcall::get_max_consider() +{ + indexes_.clear(); // list all the activities that are ready for (unsigned i = 0; i < activities_.size(); i++) if (activities_[i]->test(get_issuer())) indexes_.push_back(i); -} - -int ActivityTestanySimcall::get_max_consider() const -{ return indexes_.size() + 1; } @@ -129,10 +130,11 @@ void ActivityTestanySimcall::prepare(int times_considered) else next_value_ = -1; } -static void serialize_activity(const activity::ActivityImpl* act, std::stringstream& stream) +static void serialize_activity_test(const activity::ActivityImpl* act, std::stringstream& stream) { if (auto* comm = dynamic_cast(act)) { - stream << (short)mc::Transition::Type::COMM_TEST << ' '; + stream << " " << (short)mc::Transition::Type::COMM_TEST; + stream << ' ' << (void*)comm; stream << ' ' << (comm->src_actor_ != nullptr ? comm->src_actor_->get_pid() : -1); stream << ' ' << (comm->dst_actor_ != nullptr ? comm->dst_actor_->get_pid() : -1); stream << ' ' << comm->get_mailbox_id(); @@ -144,14 +146,21 @@ static void serialize_activity(const activity::ActivityImpl* act, std::stringstr void ActivityTestanySimcall::serialize(std::stringstream& stream) const { stream << (short)mc::Transition::Type::TESTANY << ' ' << activities_.size() << ' '; - for (auto const& act : activities_) - serialize_activity(act, stream); + for (auto const& act : activities_) { + serialize_activity_test(act, stream); + stream << ' '; + } } -void ActivityWaitSimcall::serialize(std::stringstream& stream) const +void ActivityTestSimcall::serialize(std::stringstream& stream) const +{ + serialize_activity_test(activity_, stream); +} +static void serialize_activity_wait(const activity::ActivityImpl* act, bool timeout, std::stringstream& stream) { - if (auto* comm = dynamic_cast(activity_)) { + if (auto* comm = dynamic_cast(act)) { stream << (short)mc::Transition::Type::COMM_WAIT << ' '; - stream << (timeout_ > 0) << ' ' << comm; + stream << timeout << ' ' << comm; + stream << ' ' << (comm->src_actor_ != nullptr ? comm->src_actor_->get_pid() : -1); stream << ' ' << (comm->dst_actor_ != nullptr ? comm->dst_actor_->get_pid() : -1); stream << ' ' << comm->get_mailbox_id(); @@ -160,57 +169,69 @@ void ActivityWaitSimcall::serialize(std::stringstream& stream) const stream << (short)mc::Transition::Type::UNKNOWN; } } -void ActivityTestSimcall::serialize(std::stringstream& stream) const + +void ActivityWaitSimcall::serialize(std::stringstream& stream) const +{ + serialize_activity_wait(activity_, timeout_ > 0, stream); +} +void ActivityWaitanySimcall::serialize(std::stringstream& stream) const +{ + stream << (short)mc::Transition::Type::WAITANY << ' ' << activities_.size() << ' '; + for (auto const& act : activities_) { + serialize_activity_wait(act, timeout_ > 0, stream); + stream << ' '; + } +} +ActivityWaitanySimcall::ActivityWaitanySimcall(ActorImpl* actor, const std::vector& activities, + double timeout) + : ResultingSimcall(actor, -1), activities_(activities), timeout_(timeout) { - serialize_activity(activity_, stream); } -bool ActivityWaitSimcall::is_enabled() const +bool ActivityWaitSimcall::is_enabled() { - /* FIXME: check also that src and dst processes are not suspended */ - const auto* comm = dynamic_cast(activity_); - if (comm == nullptr) - xbt_die("Only Comms are supported here for now"); + // FIXME: if _sg_mc_timeout == 1 and if we have either a sender or receiver timeout, the transition is enabled + // because even if the communication is not ready, it can timeout and won't block. - if (comm->src_timeout_ || comm->dst_timeout_) { - /* If it has a timeout it will be always be enabled (regardless of who declared the timeout), - * because even if the communication is not ready, it can timeout and won't block. */ - if (_sg_mc_timeout == 1) - return true; - } - /* On the other hand if it hasn't a timeout, check if the comm is ready.*/ - else if (comm->detached() && comm->src_actor_ == nullptr && comm->get_state() == activity::State::READY) - return (comm->dst_actor_ != nullptr); - return (comm->src_actor_ && comm->dst_actor_); -} - -bool ActivityWaitanySimcall::is_enabled() const -{ - // FIXME: deal with other kind of activities (Exec and I/Os) - // FIXME: Can be factored with ActivityWaitSimcall::is_enabled() - const auto* comm = dynamic_cast(activities_[next_value_]); - if (comm == nullptr) - xbt_die("Only Comms are supported here for now"); - if (comm->src_timeout_ || comm->dst_timeout_) { - /* If it has a timeout it will be always be enabled (regardless of who declared the timeout), - * because even if the communication is not ready, it can timeout and won't block. */ - if (_sg_mc_timeout == 1) - return true; - } - /* On the other hand if it hasn't a timeout, check if the comm is ready.*/ - else if (comm->detached() && comm->src_actor_ == nullptr && comm->get_state() == activity::State::READY) - return (comm->dst_actor_ != nullptr); - return (comm->src_actor_ && comm->dst_actor_); + return activity_->test(get_issuer()); } -int ActivityWaitanySimcall::get_max_consider() const +bool ActivityWaitanySimcall::is_enabled() { - return static_cast(activities_.size()); + // list all the activities that are ready + indexes_.clear(); + for (unsigned i = 0; i < activities_.size(); i++) + if (activities_[i]->test(get_issuer())) + indexes_.push_back(i); + + // if (_sg_mc_timeout && timeout_) FIXME: deal with the potential timeout of the WaitAny + + // FIXME: even if the WaitAny has no timeout, some of the activities may still have one. + // we should iterate over the vector searching for them + return not indexes_.empty(); +} + +int ActivityWaitanySimcall::get_max_consider() +{ + // list all the activities that are ready + indexes_.clear(); + for (unsigned i = 0; i < activities_.size(); i++) + if (activities_[i]->test(get_issuer())) + indexes_.push_back(i); + + int res = indexes_.size(); + // if (_sg_mc_timeout && timeout_) + // res++; + + return res; } void ActivityWaitanySimcall::prepare(int times_considered) { - next_value_ = times_considered; + if (times_considered < static_cast(indexes_.size())) + next_value_ = indexes_.at(times_considered); + else + next_value_ = -1; } void CommIsendSimcall::serialize(std::stringstream& stream) const diff --git a/src/kernel/actor/SimcallObserver.hpp b/src/kernel/actor/SimcallObserver.hpp index 924387616d..f75ae91321 100644 --- a/src/kernel/actor/SimcallObserver.hpp +++ b/src/kernel/actor/SimcallObserver.hpp @@ -27,7 +27,7 @@ public: * For example, a mutex_lock is not enabled when the mutex is not free. * A comm_receive is not enabled before the corresponding send has been issued. */ - virtual bool is_enabled() const { return true; } + virtual bool is_enabled() { return true; } /** Returns the amount of time that this transition can be used. * @@ -35,7 +35,7 @@ public: * If it's more than one (as with mc_random or waitany), we need to consider this transition several times to start * differing branches */ - virtual int get_max_consider() const { return 1; } + virtual int get_max_consider() { return 1; } /** Prepares the simcall to be used. * @@ -82,7 +82,7 @@ public: xbt_assert(min < max); } void serialize(std::stringstream& stream) const override; - int get_max_consider() const override; + int get_max_consider() override; void prepare(int times_considered) override; int get_value() const { return next_value_; } bool depends(SimcallObserver* other) override; @@ -109,7 +109,7 @@ public: : MutexSimcall(actor, mutex), blocking_(blocking) { } - bool is_enabled() const override; + bool is_enabled() override; }; class ConditionWaitSimcall : public ResultingSimcall { @@ -123,7 +123,7 @@ public: : ResultingSimcall(actor, false), cond_(cond), mutex_(mutex), timeout_(timeout) { } - bool is_enabled() const override; + bool is_enabled() override; bool is_visible() const override { return false; } activity::ConditionVariableImpl* get_cond() const { return cond_; } activity::MutexImpl* get_mutex() const { return mutex_; } @@ -139,7 +139,7 @@ public: : ResultingSimcall(actor, false), sem_(sem), timeout_(timeout) { } - bool is_enabled() const override; + bool is_enabled() override; bool is_visible() const override { return false; } activity::SemaphoreImpl* get_sem() const { return sem_; } double get_timeout() const { return timeout_; } @@ -166,9 +166,9 @@ class ActivityTestanySimcall : public ResultingSimcall { public: ActivityTestanySimcall(ActorImpl* actor, const std::vector& activities); bool is_visible() const override { return true; } - bool is_enabled() const override { return true; /* can return -1 if no activity is ready */ } + bool is_enabled() override { return true; /* can return -1 if no activity is ready */ } void serialize(std::stringstream& stream) const override; - int get_max_consider() const override; + int get_max_consider() override; void prepare(int times_considered) override; const std::vector& get_activities() const { return activities_; } int get_value() const { return next_value_; } @@ -185,7 +185,7 @@ public: } void serialize(std::stringstream& stream) const override; bool is_visible() const override { return true; } - bool is_enabled() const override; + bool is_enabled() override; activity::ActivityImpl* get_activity() const { return activity_; } void set_activity(activity::ActivityImpl* activity) { activity_ = activity; } double get_timeout() const { return timeout_; } @@ -193,18 +193,17 @@ public: class ActivityWaitanySimcall : public ResultingSimcall { const std::vector& activities_; + std::vector indexes_; // indexes in activities_ pointing to ready activities (=whose test() is positive) const double timeout_; int next_value_ = 0; public: - ActivityWaitanySimcall(ActorImpl* actor, const std::vector& activities, double timeout) - : ResultingSimcall(actor, -1), activities_(activities), timeout_(timeout) - { - } - bool is_enabled() const override; + ActivityWaitanySimcall(ActorImpl* actor, const std::vector& activities, double timeout); + bool is_enabled() override; + void serialize(std::stringstream& stream) const override; bool is_visible() const override { return true; } void prepare(int times_considered) override; - int get_max_consider() const override; + int get_max_consider() override; const std::vector& get_activities() const { return activities_; } double get_timeout() const { return timeout_; } int get_value() const { return next_value_; } diff --git a/src/mc/api/Transition.hpp b/src/mc/api/Transition.hpp index ed4dd7567a..3273f13c9e 100644 --- a/src/mc/api/Transition.hpp +++ b/src/mc/api/Transition.hpp @@ -32,7 +32,7 @@ class Transition { friend State; // FIXME remove this once we have a proper class to handle the statistics public: - XBT_DECLARE_ENUM_CLASS(Type, RANDOM, COMM_RECV, COMM_SEND, COMM_TEST, COMM_WAIT, TESTANY, + XBT_DECLARE_ENUM_CLASS(Type, RANDOM, COMM_RECV, COMM_SEND, COMM_TEST, COMM_WAIT, TESTANY, WAITANY, /* UNKNOWN must be last */ UNKNOWN); Type type_ = Type::UNKNOWN; diff --git a/src/mc/api/TransitionComm.cpp b/src/mc/api/TransitionComm.cpp index ff2b352597..35eadf01f2 100644 --- a/src/mc/api/TransitionComm.cpp +++ b/src/mc/api/TransitionComm.cpp @@ -46,6 +46,11 @@ bool CommWaitTransition::depends(const Transition* other) const if (dynamic_cast(other) != nullptr) return false; // Random is indep with any transition + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (auto* recv = dynamic_cast(other)) return recv->depends(this); @@ -93,6 +98,11 @@ bool CommTestTransition::depends(const Transition* other) const if (dynamic_cast(other) != nullptr) return false; // Test & Random are independent (Random is independent with anything) + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (auto* recv = dynamic_cast(other)) return recv->depends(this); // Recv < Test (alphabetical ordering) @@ -133,6 +143,10 @@ bool CommRecvTransition::depends(const Transition* other) const if (dynamic_cast(other) != nullptr) return false; // Random is indep with any transition + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (auto* any = dynamic_cast(other)) + return any->depends(this); if (const auto* recv = dynamic_cast(other)) return mbox_ == recv->mbox_; @@ -184,6 +198,7 @@ TestAnyTransition::TestAnyTransition(aid_t issuer, int times_considered, std::st for (int i = 0; i < size; i++) { Transition* t = deserialize_transition(issuer, 0, stream); + XBT_DEBUG("TestAny received a transition %s", t->to_string(true).c_str()); transitions_.push_back(t); } } @@ -197,7 +212,29 @@ std::string TestAnyTransition::to_string(bool verbose) const } bool TestAnyTransition::depends(const Transition* other) const { - return true; + return transitions_[times_considered_]->depends(other); +} +WaitAnyTransition::WaitAnyTransition(aid_t issuer, int times_considered, std::stringstream& stream) + : Transition(Type::WAITANY, issuer, times_considered) +{ + int size; + stream >> size; + for (int i = 0; i < size; i++) { + Transition* t = deserialize_transition(issuer, 0, stream); + transitions_.push_back(t); + } +} +std::string WaitAnyTransition::to_string(bool verbose) const +{ + auto res = xbt::string_printf("%ld: WaitAny{ ", aid_); + for (auto const* t : transitions_) + res += t->to_string(verbose); + res += "}"; + return res; +} +bool WaitAnyTransition::depends(const Transition* other) const +{ + return transitions_[times_considered_]->depends(other); } bool CommSendTransition::depends(const Transition* other) const @@ -208,6 +245,11 @@ bool CommSendTransition::depends(const Transition* other) const if (dynamic_cast(other) != nullptr) return false; // Random is indep with any transition + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (auto* any = dynamic_cast(other)) + return any->depends(this); + if (const auto* other_isend = dynamic_cast(other)) return mbox_ == other_isend->mbox_; @@ -257,6 +299,8 @@ Transition* deserialize_transition(aid_t issuer, int times_considered, std::stri case Transition::Type::TESTANY: return new TestAnyTransition(issuer, times_considered, stream); + case Transition::Type::WAITANY: + return new WaitAnyTransition(issuer, times_considered, stream); case Transition::Type::RANDOM: return new RandomTransition(issuer, times_considered, stream); diff --git a/src/mc/api/TransitionComm.hpp b/src/mc/api/TransitionComm.hpp index f643912d3a..6f8a7c9ed6 100644 --- a/src/mc/api/TransitionComm.hpp +++ b/src/mc/api/TransitionComm.hpp @@ -85,6 +85,15 @@ public: bool depends(const Transition* other) const override; }; +class WaitAnyTransition : public Transition { + std::vector transitions_; + +public: + WaitAnyTransition(aid_t issuer, int times_considered, std::stringstream& stream); + std::string to_string(bool verbose) const override; + bool depends(const Transition* other) const override; +}; + /** Make a new transition from serialized description */ Transition* deserialize_transition(aid_t issuer, int times_considered, std::stringstream& stream); diff --git a/src/mc/checker/SafetyChecker.cpp b/src/mc/checker/SafetyChecker.cpp index 6dc565e791..57e7049e2f 100644 --- a/src/mc/checker/SafetyChecker.cpp +++ b/src/mc/checker/SafetyChecker.cpp @@ -175,6 +175,7 @@ void SafetyChecker::run() void SafetyChecker::backtrack() { backtrack_count_++; + XBT_VERB("Backtracking from %s", get_record_trace().to_string().c_str()); stack_.pop_back(); api::get().mc_check_deadlock(); diff --git a/src/mc/mc_base.cpp b/src/mc/mc_base.cpp index 1388a231b4..236aab7468 100644 --- a/src/mc/mc_base.cpp +++ b/src/mc/mc_base.cpp @@ -58,7 +58,7 @@ void execute_actors() engine->reset_actor_dynar(); for (auto const& kv : engine->get_actor_list()) { auto actor = kv.second; - if (const auto* observer = actor->simcall_.observer_) + if (auto* observer = actor->simcall_.observer_) actor->simcall_.mc_max_consider_ = observer->get_max_consider(); engine->add_actor_to_dynar(actor); } -- 2.20.1