src/mc/api/State.hpp

   1 /* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #ifndef SIMGRID_MC_STATE_HPP
   7 #define SIMGRID_MC_STATE_HPP
   8
   9 #include "src/mc/api/ActorState.hpp"
  10 #include "src/mc/api/ClockVector.hpp"
  11 #include "src/mc/api/RemoteApp.hpp"
  12 #include "src/mc/api/strategy/Strategy.hpp"
  13 #include "src/mc/explo/odpor/WakeupTree.hpp"
  14 #include "src/mc/transition/Transition.hpp"
  15
  16 #if SIMGRID_HAVE_STATEFUL_MC
  17 #include "src/mc/sosp/Snapshot.hpp"
  18 #endif
  19
  20 namespace simgrid::mc {
  21
  22 /* A node in the exploration graph (kind-of) */
  23 class XBT_PRIVATE State : public xbt::Extendable<State> {
  24   static long expended_states_; /* Count total amount of states, for stats */
  25
  26   /** @brief The outgoing transition is the last transition that we took to leave this state.  */
  27   std::shared_ptr<Transition> outgoing_transition_ = nullptr;
  28
  29   /** @brief The incoming transition is what led to this state, coming from its parent  */
  30   std::shared_ptr<Transition> incoming_transition_ = nullptr;
  31
  32   /** Sequential state ID (used for debugging) */
  33   long num_ = 0;
  34
  35   /** Snapshot of system state (if needed) */
  36   std::shared_ptr<Snapshot> system_state_;
  37
  38   /** Unique parent of this state. Required both for sleep set computation
  39       and for guided model-checking */
  40   std::shared_ptr<State> parent_state_ = nullptr;
  41
  42   std::shared_ptr<Strategy> strategy_;
  43
  44   /* Sleep sets are composed of the actor and the corresponding transition that made it being added to the sleep
  45    * set. With this information, it is check whether it should be removed from it or not when exploring a new
  46    * transition */
  47   std::map<aid_t, std::shared_ptr<Transition>> sleep_set_;
  48
  49   /**
  50    * The wakeup tree with respect to the execution represented
  51    * by the totality of all states before and including this one
  52    * and with respect to this state's sleep set
  53    */
  54   odpor::WakeupTree wakeup_tree_;
  55   bool has_initialized_wakeup_tree = false;
  56
  57 public:
  58   explicit State(RemoteApp& remote_app);
  59   explicit State(RemoteApp& remote_app, std::shared_ptr<State> parent_state);
  60   /* Returns a positive number if there is another transition to pick, or -1 if not */
  61   aid_t next_transition() const; // this function should disapear as it is redundant with the next one
  62
  63   /* Same as next_transition(), but choice is now guided, and an integer corresponding to the
  64    internal cost of the transition is returned */
  65   std::pair<aid_t, int> next_transition_guided() const;
  66
  67   /**
  68    * Same as next_transition(), but the choice is not based off the ODPOR
  69    * wakeup tree associated with this state
  70    */
  71   aid_t next_odpor_transition() const;
  72
  73   /**
  74    * @brief Explore a new path on the remote app; the parameter 'next' must be the result of a previous call to
  75    * next_transition()
  76    */
  77   std::shared_ptr<Transition> execute_next(aid_t next, RemoteApp& app);
  78
  79   long get_num() const { return num_; }
  80   std::size_t count_todo() const;
  81   std::size_t count_todo_multiples() const;
  82
  83   /* Marking as TODO some actor in this state:
  84    *  + consider_one mark aid actor (and assert it is possible)
  85    *  + consider_best ensure one actor is marked by eventually marking the best regarding its guiding method
  86    *  + consider_all mark all enabled actor that are not done yet */
  87   void consider_one(aid_t aid) const { strategy_->consider_one(aid); }
  88   void consider_best() const { strategy_->consider_best(); }
  89   unsigned long consider_all() const { return strategy_->consider_all(); }
  90
  91   bool is_actor_done(aid_t actor) const { return strategy_->actors_to_run_.at(actor).is_done(); }
  92   std::shared_ptr<Transition> get_transition_out() const { return outgoing_transition_; }
  93   std::shared_ptr<Transition> get_transition_in() const { return incoming_transition_; }
  94   std::shared_ptr<State> get_parent_state() const { return parent_state_; }
  95
  96   std::map<aid_t, ActorState> const& get_actors_list() const { return strategy_->actors_to_run_; }
  97
  98   unsigned long get_actor_count() const { return strategy_->actors_to_run_.size(); }
  99   bool is_actor_enabled(aid_t actor) const { return strategy_->actors_to_run_.at(actor).is_enabled(); }
 100
 101   Snapshot* get_system_state() const { return system_state_.get(); }
 102   void set_system_state(std::shared_ptr<Snapshot> state) { system_state_ = std::move(state); }
 103
 104   /**
 105    * @brief Computes the backtrack set for this state
 106    * according to its definition in SimGrid.
 107    *
 108    * The backtrack set as it appears in DPOR, SDPOR, and ODPOR
 109    * in SimGrid consists of those actors marked as `todo`
 110    * (i.e. those that have yet to be explored) as well as those
 111    * marked `done` (i.e. those that have already been explored)
 112    * since the pseudocode in none of the above algorithms explicitly
 113    * removes elements from the backtrack set. DPOR makes use
 114    * explicitly of the `done` set, but we again note that the
 115    * backtrack set still contains processes added to the done set.
 116    */
 117   std::unordered_set<aid_t> get_backtrack_set() const;
 118   std::unordered_set<aid_t> get_sleeping_actors() const;
 119   std::unordered_set<aid_t> get_enabled_actors() const;
 120   std::map<aid_t, std::shared_ptr<Transition>> const& get_sleep_set() const { return sleep_set_; }
 121   void add_sleep_set(std::shared_ptr<Transition> t) { sleep_set_.insert_or_assign(t->aid_, std::move(t)); }
 122   bool is_actor_sleeping(aid_t actor) const
 123   {
 124     return std::find_if(sleep_set_.begin(), sleep_set_.end(), [=](const auto& pair) { return pair.first == actor; }) !=
 125            sleep_set_.end();
 126   }
 127
 128   /**
 129    * @brief Inserts an arbitrary enabled actor into the wakeup tree
 130    * associated with this state, if such an actor exists and if
 131    * the wakeup tree is already not empty
 132    *
 133    * @param prior The sequence of steps leading up to this state
 134    * with respec to which the tree associated with this state should be
 135    * a wakeup tree (wakeup trees are defined relative to an execution)
 136    *
 137    * @invariant: You should not manipulate a wakeup tree with respect
 138    * to more than one execution; doing so will almost certainly lead to
 139    * unexpected results as wakeup trees are defined relative to a single
 140    * execution
 141    */
 142   void seed_wakeup_tree_if_needed(const odpor::Execution& prior);
 143
 144   /**
 145    * @brief Initializes the wakeup_tree_ instance by taking the subtree rooted at the
 146    * single-process node `N` running actor `p := "actor taken by parent to form this state"`
 147    * of the *parent's* wakeup tree
 148    */
 149   void sprout_tree_from_parent_state();
 150
 151   /**
 152    * @brief Removes the subtree rooted at the single-process node
 153    * `N` running actor `p` of this state's wakeup tree
 154    */
 155   void remove_subtree_using_current_out_transition();
 156   bool has_empty_tree() const { return this->wakeup_tree_.empty(); }
 157
 158   /**
 159    * @brief
 160    */
 161   odpor::WakeupTree::InsertionResult insert_into_wakeup_tree(const odpor::PartialExecution&, const odpor::Execution&);
 162
 163   /** @brief Prepares the state for re-exploration following
 164    * another after having followed ODPOR from this state with
 165    * the current out transition
 166    *
 167    * After ODPOR has completed searching a maximal trace, it
 168    * finds the first point in the execution with a nonempty wakeup
 169    * tree. This method corresponds to lines 20 and 21 in the ODPOR
 170    * pseudocode
 171    */
 172   void do_odpor_unwind();
 173
 174   /* Returns the total amount of states created so far (for statistics) */
 175   static long get_expanded_states() { return expended_states_; }
 176 };
 177 } // namespace simgrid::mc
 178
 179 #endif