X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/3f756b051175054c62c4741fdab2a6b934828262..ff4bc56d5d0d4b1bf3e5c83e5af51ac3cc119789:/src/mc/explo/odpor/ReversibleRaceCalculator.cpp diff --git a/src/mc/explo/odpor/ReversibleRaceCalculator.cpp b/src/mc/explo/odpor/ReversibleRaceCalculator.cpp index f2db6b6b9a..f6007c27ff 100644 --- a/src/mc/explo/odpor/ReversibleRaceCalculator.cpp +++ b/src/mc/explo/odpor/ReversibleRaceCalculator.cpp @@ -11,8 +11,18 @@ #include #include +XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_odpor_reversible_race, mc_dfs, "ODPOR exploration algorithm of the model-checker"); + namespace simgrid::mc::odpor { +/** + The reversible race detector should only be used if we already have the assumption + e1 <* e2 (see Source set: a foundation for ODPOR). In particular this means that : + - e1 -->_E e2 + - proc(e1) != proc(e2) + - there is no event e3 s.t. e1 --> e3 --> e2 +*/ + bool ReversibleRaceCalculator::is_race_reversible(const Execution& E, Execution::EventHandle e1, Execution::EventHandle e2) { @@ -20,26 +30,26 @@ bool ReversibleRaceCalculator::is_race_reversible(const Execution& E, Execution: using Handler = std::function; using HandlerMap = std::unordered_map; - const static HandlerMap handlers = - HandlerMap{{Action::ACTOR_JOIN, &ReversibleRaceCalculator::is_race_reversible_ActorJoin}, - {Action::BARRIER_ASYNC_LOCK, &ReversibleRaceCalculator::is_race_reversible_BarrierAsyncLock}, - {Action::BARRIER_WAIT, &ReversibleRaceCalculator::is_race_reversible_BarrierWait}, - {Action::COMM_ASYNC_SEND, &ReversibleRaceCalculator::is_race_reversible_CommSend}, - {Action::COMM_ASYNC_RECV, &ReversibleRaceCalculator::is_race_reversible_CommRecv}, - {Action::COMM_TEST, &ReversibleRaceCalculator::is_race_reversible_CommTest}, - {Action::COMM_WAIT, &ReversibleRaceCalculator::is_race_reversible_CommWait}, - {Action::MUTEX_ASYNC_LOCK, &ReversibleRaceCalculator::is_race_reversible_MutexAsyncLock}, - {Action::MUTEX_TEST, &ReversibleRaceCalculator::is_race_reversible_MutexTest}, - {Action::MUTEX_TRYLOCK, &ReversibleRaceCalculator::is_race_reversible_MutexTrylock}, - {Action::MUTEX_UNLOCK, &ReversibleRaceCalculator::is_race_reversible_MutexUnlock}, - {Action::MUTEX_WAIT, &ReversibleRaceCalculator::is_race_reversible_MutexWait}, - {Action::OBJECT_ACCESS, &ReversibleRaceCalculator::is_race_reversible_ObjectAccess}, - {Action::RANDOM, &ReversibleRaceCalculator::is_race_reversible_Random}, - {Action::SEM_ASYNC_LOCK, &ReversibleRaceCalculator::is_race_reversible_SemAsyncLock}, - {Action::SEM_UNLOCK, &ReversibleRaceCalculator::is_race_reversible_SemUnlock}, - {Action::SEM_WAIT, &ReversibleRaceCalculator::is_race_reversible_SemWait}, - {Action::TESTANY, &ReversibleRaceCalculator::is_race_reversible_TestAny}, - {Action::WAITANY, &ReversibleRaceCalculator::is_race_reversible_WaitAny}}; + const static HandlerMap handlers = { + {Action::ACTOR_JOIN, &ReversibleRaceCalculator::is_race_reversible_ActorJoin}, + {Action::BARRIER_ASYNC_LOCK, &ReversibleRaceCalculator::is_race_reversible_BarrierAsyncLock}, + {Action::BARRIER_WAIT, &ReversibleRaceCalculator::is_race_reversible_BarrierWait}, + {Action::COMM_ASYNC_SEND, &ReversibleRaceCalculator::is_race_reversible_CommSend}, + {Action::COMM_ASYNC_RECV, &ReversibleRaceCalculator::is_race_reversible_CommRecv}, + {Action::COMM_TEST, &ReversibleRaceCalculator::is_race_reversible_CommTest}, + {Action::COMM_WAIT, &ReversibleRaceCalculator::is_race_reversible_CommWait}, + {Action::MUTEX_ASYNC_LOCK, &ReversibleRaceCalculator::is_race_reversible_MutexAsyncLock}, + {Action::MUTEX_TEST, &ReversibleRaceCalculator::is_race_reversible_MutexTest}, + {Action::MUTEX_TRYLOCK, &ReversibleRaceCalculator::is_race_reversible_MutexTrylock}, + {Action::MUTEX_UNLOCK, &ReversibleRaceCalculator::is_race_reversible_MutexUnlock}, + {Action::MUTEX_WAIT, &ReversibleRaceCalculator::is_race_reversible_MutexWait}, + {Action::OBJECT_ACCESS, &ReversibleRaceCalculator::is_race_reversible_ObjectAccess}, + {Action::RANDOM, &ReversibleRaceCalculator::is_race_reversible_Random}, + {Action::SEM_ASYNC_LOCK, &ReversibleRaceCalculator::is_race_reversible_SemAsyncLock}, + {Action::SEM_UNLOCK, &ReversibleRaceCalculator::is_race_reversible_SemUnlock}, + {Action::SEM_WAIT, &ReversibleRaceCalculator::is_race_reversible_SemWait}, + {Action::TESTANY, &ReversibleRaceCalculator::is_race_reversible_TestAny}, + {Action::WAITANY, &ReversibleRaceCalculator::is_race_reversible_WaitAny}}; const auto* e2_action = E.get_transition_for_handle(e2); if (const auto handler = handlers.find(e2_action->type_); handler != handlers.end()) { @@ -55,8 +65,8 @@ bool ReversibleRaceCalculator::is_race_reversible(const Execution& E, Execution: } } -bool ReversibleRaceCalculator::is_race_reversible_ActorJoin(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_ActorJoin(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // ActorJoin races with another event iff its target `T` is the same as // the actor executing the other transition. Clearly, then, we could not join @@ -64,15 +74,15 @@ bool ReversibleRaceCalculator::is_race_reversible_ActorJoin(const Execution&, Ex return false; } -bool ReversibleRaceCalculator::is_race_reversible_BarrierAsyncLock(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_BarrierAsyncLock(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // BarrierAsyncLock is always enabled return true; } bool ReversibleRaceCalculator::is_race_reversible_BarrierWait(const Execution& E, Execution::EventHandle e1, - const Transition* e2) + const Transition* /*e2*/) { // If the other event is a barrier lock event, then we // are not reversible; otherwise we are reversible. @@ -80,22 +90,22 @@ bool ReversibleRaceCalculator::is_race_reversible_BarrierWait(const Execution& E return e1_action != Transition::Type::BARRIER_ASYNC_LOCK; } -bool ReversibleRaceCalculator::is_race_reversible_CommRecv(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_CommRecv(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // CommRecv is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_CommSend(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_CommSend(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // CommSend is always enabled return true; } bool ReversibleRaceCalculator::is_race_reversible_CommWait(const Execution& E, Execution::EventHandle e1, - const Transition* e2) + const Transition* /*e2*/) { // If the other event is a communication event, then we // are not reversible; otherwise we are reversible. @@ -103,93 +113,101 @@ bool ReversibleRaceCalculator::is_race_reversible_CommWait(const Execution& E, E return e1_action != Transition::Type::COMM_ASYNC_SEND && e1_action != Transition::Type::COMM_ASYNC_RECV; } -bool ReversibleRaceCalculator::is_race_reversible_CommTest(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_CommTest(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // CommTest is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_MutexAsyncLock(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_MutexAsyncLock(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // MutexAsyncLock is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_MutexTest(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_MutexTest(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // MutexTest is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_MutexTrylock(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_MutexTrylock(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // MutexTrylock is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_MutexUnlock(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_MutexUnlock(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // MutexUnlock is always enabled return true; } bool ReversibleRaceCalculator::is_race_reversible_MutexWait(const Execution& E, Execution::EventHandle e1, - const Transition* e2) + const Transition* /*e2*/) { - // TODO: Get the semantics correct here + // The only possibilities for e1 to satisfy the pre-condition are : + // - MUTEX_ASYNC_LOCK + + 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; } -bool ReversibleRaceCalculator::is_race_reversible_SemAsyncLock(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_SemAsyncLock(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // SemAsyncLock is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_SemUnlock(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_SemUnlock(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // SemUnlock is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_SemWait(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_SemWait(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // TODO: Get the semantics correct here + // Certainement qu'il suffit de considérer les SemUnlock. ⋀ a priori, + // il doit même suffir de considérer le cas où leur capacity après execution est <=1 + // ces cas disent qu'avant éxecution la capacity était de 0. Donc aucune chance de pouvoir + // wait avant le unlock. return false; } -bool ReversibleRaceCalculator::is_race_reversible_ObjectAccess(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_ObjectAccess(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // Object access is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_Random(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_Random(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // Random is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_TestAny(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_TestAny(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // TestAny is always enabled return true; } -bool ReversibleRaceCalculator::is_race_reversible_WaitAny(const Execution&, Execution::EventHandle e1, - const Transition* e2) +bool ReversibleRaceCalculator::is_race_reversible_WaitAny(const Execution&, Execution::EventHandle /*e1*/, + const Transition* /*e2*/) { // TODO: We need to check if any of the transitions // waited on occurred before `e1`