X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/ee3aa92a3bb4209e12bb7f8b628cb47e68cae081..0f0aacb167ddc9427ea1da1c8f1b66ef2d6f532e:/src/mc/explo/odpor/ReversibleRaceCalculator.cpp

diff --git a/src/mc/explo/odpor/ReversibleRaceCalculator.cpp b/src/mc/explo/odpor/ReversibleRaceCalculator.cpp
index 650ce1ceff..a7de9b92ec 100644
--- a/src/mc/explo/odpor/ReversibleRaceCalculator.cpp
+++ b/src/mc/explo/odpor/ReversibleRaceCalculator.cpp
@@ -5,14 +5,26 @@
 
 #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)
 {
@@ -55,8 +67,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 +76,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 +92,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,97 +115,103 @@ 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
-  const auto e1_action = E.get_transition_for_handle(e1)->type_;
-  return e1_action != Transition::Type::MUTEX_ASYNC_LOCK && e1_action != Transition::Type::MUTEX_UNLOCK;
+  // TODO: for now we over approximate the reversibility
+
+  return true;
 }
 
-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;
+
+  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;
+  }
+  xbt_assert(false, "SEM_WAIT that is dependent with a SEM_UNLOCK should not be reversible. FixMe");
+  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;
+  return true; // Let's overapproximate to not miss branches
 }
 
 } // namespace simgrid::mc::odpor