#include "src/mc/explo/odpor/ReversibleRaceCalculator.hpp"
#include "src/mc/explo/odpor/Execution.hpp"
+#include "src/mc/transition/Transition.hpp"
+#include "src/mc/transition/TransitionSynchro.hpp"
#include <functional>
#include <unordered_map>
#include <xbt/asserts.h>
#include <xbt/ex.h>
+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)
{
using Handler = std::function<bool(const Execution&, Execution::EventHandle, const Transition*)>;
using HandlerMap = std::unordered_map<Action, Handler>;
- 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 auto e2_action = E.get_transition_for_handle(e2);
+ 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()) {
return handler->second(E, e1, e2_action);
} else {
}
}
-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
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.
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.
const auto e1_action = E.get_transition_for_handle(e1)->type_;
- return e1_action != Transition::Type::COMM_ASYNC_SEND and e1_action != Transition::Type::COMM_ASYNC_RECV;
+ 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_;
- return e1_action != Transition::Type::MUTEX_ASYNC_LOCK and e1_action != Transition::Type::MUTEX_UNLOCK;
+ 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& E, Execution::EventHandle e1,
+ const Transition* /*e2*/)
{
- // TODO: Get the semantics correct here
- return false;
+ // 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)
+ return false;
+ return true;
}
-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`
return false;
}
-} // namespace simgrid::mc::odpor
\ No newline at end of file
+} // namespace simgrid::mc::odpor