1 /* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved. */
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. */
6 #ifndef SIMGRID_MC_STATE_HPP
7 #define SIMGRID_MC_STATE_HPP
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"
16 #if SIMGRID_HAVE_STATEFUL_MC
17 #include "src/mc/sosp/Snapshot.hpp"
20 namespace simgrid::mc {
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 */
26 /** @brief The outgoing transition is the last transition that we took to leave this state. */
27 std::shared_ptr<Transition> outgoing_transition_ = nullptr;
29 /** @brief The incoming transition is what led to this state, coming from its parent */
30 std::shared_ptr<Transition> incoming_transition_ = nullptr;
32 /** Sequential state ID (used for debugging) */
35 /** Snapshot of system state (if needed) */
36 std::shared_ptr<Snapshot> system_state_;
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;
42 std::shared_ptr<Strategy> strategy_;
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
47 std::map<aid_t, Transition> sleep_set_;
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
54 odpor::WakeupTree wakeup_tree_;
55 bool has_initialized_wakeup_tree = false;
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
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;
68 * Same as next_transition(), but the choice is not based off the ODPOR
69 * wakeup tree associated with this state
71 aid_t next_odpor_transition() const;
74 * @brief Explore a new path on the remote app; the parameter 'next' must be the result of a previous call to
77 std::shared_ptr<Transition> execute_next(aid_t next, RemoteApp& app);
79 long get_num() const { return num_; }
80 std::size_t count_todo() const;
81 std::size_t count_todo_multiples() const;
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(); }
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_; }
96 std::map<aid_t, ActorState> const& get_actors_list() const { return strategy_->actors_to_run_; }
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(); }
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); }
105 * @brief Computes the backtrack set for this state
106 * according to its definition in Simgrid.
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.
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, Transition> const& get_sleep_set() const { return sleep_set_; }
121 void add_sleep_set(std::shared_ptr<Transition> t)
123 sleep_set_.insert_or_assign(t->aid_, Transition(t->type_, t->aid_, t->times_considered_));
125 bool is_actor_sleeping(aid_t actor) const
127 return std::find_if(sleep_set_.begin(), sleep_set_.end(), [=](const auto& pair) { return pair.first == actor; }) !=
132 * @brief Inserts an arbitrary enabled actor into the wakeup tree
133 * associated with this state, if such an actor exists and if
134 * the wakeup tree is already not empty
136 * @param prior The sequence of steps leading up to this state
137 * with respec to which the tree associated with this state should be
138 * a wakeup tree (wakeup trees are defined relative to an execution)
140 * @invariant: You should not manipulate a wakeup tree with respect
141 * to more than one execution; doing so will almost certainly lead to
142 * unexpected results as wakeup trees are defined relative to a single
145 void seed_wakeup_tree_if_needed(const odpor::Execution& prior);
148 * @brief Initializes the wakeup_tree_ instance by taking the subtree rooted at the
149 * single-process node `N` running actor `p := "actor taken by parent to form this state"`
150 * of the *parent's* wakeup tree
152 void sprout_tree_from_parent_state();
155 * @brief Removes the subtree rooted at the single-process node
156 * `N` running actor `p` of this state's wakeup tree
158 void remove_subtree_using_current_out_transition();
159 bool has_empty_tree() const { return this->wakeup_tree_.empty(); }
164 void mark_path_interesting_for_odpor(const odpor::PartialExecution&, const odpor::Execution&);
167 void do_odpor_backtrack_cleanup();
169 /* Returns the total amount of states created so far (for statistics) */
170 static long get_expanded_states() { return expended_states_; }
172 } // namespace simgrid::mc