1 /* Copyright (c) 2016-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 #include "src/mc/explo/UdporChecker.hpp"
7 #include "src/mc/api/State.hpp"
8 #include "src/mc/explo/udpor/Comb.hpp"
9 #include "src/mc/explo/udpor/ExtensionSetCalculator.hpp"
10 #include "src/mc/explo/udpor/History.hpp"
11 #include "src/mc/explo/udpor/maximal_subsets_iterator.hpp"
14 #include <xbt/asserts.h>
16 #include <xbt/string.hpp>
18 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_udpor, mc, "Logging specific to verification using UDPOR");
20 namespace simgrid::mc::udpor {
22 UdporChecker::UdporChecker(const std::vector<char*>& args) : Exploration(args, true) {}
24 void UdporChecker::run()
26 XBT_INFO("Starting a UDPOR exploration");
28 state_stack.push_back(get_current_state());
29 explore(Configuration(), EventSet(), EventSet(), EventSet());
30 XBT_INFO("UDPOR exploration terminated -- model checking completed");
33 void UdporChecker::explore(const Configuration& C, EventSet D, EventSet A, EventSet prev_exC)
35 auto& stateC = *state_stack.back();
36 auto exC = compute_exC(C, stateC, prev_exC);
37 const auto enC = compute_enC(C, exC);
38 XBT_DEBUG("explore(C, D, A) with:\n"
44 C.to_string().c_str(), D.to_string().c_str(), A.to_string().c_str(), exC.to_string().c_str(),
45 enC.to_string().c_str());
46 XBT_DEBUG("ex(C) has %zu elements, of which %zu are in en(C)", exC.size(), enC.size());
48 // If enC is a subset of D, intuitively
49 // there aren't any enabled transitions
50 // which are "worth" exploring since their
51 // exploration would lead to a so-called
52 // "sleep-set blocked" trace.
53 if (enC.is_subset_of(D)) {
54 XBT_DEBUG("en(C) is a subset of the sleep set D (size %zu); if we "
55 "kept exploring, we'd hit a sleep-set blocked trace",
57 XBT_DEBUG("The current configuration has %zu elements", C.get_events().size());
59 // When `en(C)` is empty, intuitively this means that there
60 // are no enabled transitions that can be executed from the
61 // state reached by `C` (denoted `state(C)`), i.e. by some
62 // execution of the transitions in C obeying the causality
63 // relation. Here, then, we may be in a deadlock (the other
64 // possibility is that we've finished running everything, and
65 // we wouldn't be in deadlock then)
67 XBT_VERB("Maximal configuration detected. Checking for deadlock...");
68 get_remote_app().check_deadlock();
73 UnfoldingEvent* e = select_next_unfolding_event(A, enC);
74 xbt_assert(e != nullptr, "\n\n****** INVARIANT VIOLATION ******\n"
75 "UDPOR guarantees that an event will be chosen at each point in\n"
76 "the search, yet no events were actually chosen\n"
77 "*********************************\n\n");
78 XBT_DEBUG("Selected event `%s` (%zu dependencies) to extend the configuration", e->to_string().c_str(),
79 e->get_immediate_causes().size());
88 // Explore(C + {e}, D, A \ {e})
90 // Move the application into stateCe (i.e. `state(C + {e})`) and make note of that state
91 move_to_stateCe(&stateC, e);
92 state_stack.push_back(record_current_state());
94 explore(Ce, D, std::move(A), std::move(exC));
96 // Prepare to move the application back one state.
97 // We need only remove the state from the stack here: if we perform
98 // another `Explore()` after computing an alternative, at that
99 // point we'll actually create a fresh RemoteProcess
100 state_stack.pop_back();
105 XBT_DEBUG("Checking for the existence of an alternative...");
106 if (auto J = C.compute_alternative_to(D, this->unfolding); J.has_value()) {
107 // Before searching the "right half", we need to make
108 // sure the program actually reflects the fact
109 // that we are searching again from `state(C)`. While the
110 // stack of states is properly adjusted to represent
111 // `state(C)` all together, the RemoteApp is currently sitting
112 // at some *future* state with resepct to `state(C)` since the
113 // recursive calls have moved it there.
114 restore_program_state_with_current_stack();
116 // Explore(C, D + {e}, J \ C)
117 auto J_minus_C = J.value().get_events().subtracting(C.get_events());
119 XBT_DEBUG("Alternative detected! The alternative is:\n"
122 "UDPOR is going to explore it...",
123 J.value().to_string().c_str(), J_minus_C.to_string().c_str());
124 explore(C, D, std::move(J_minus_C), std::move(prev_exC));
126 XBT_DEBUG("No alternative detected with:\n"
130 C.to_string().c_str(), D.to_string().c_str(), A.to_string().c_str());
137 clean_up_explore(e, C, D);
140 EventSet UdporChecker::compute_exC(const Configuration& C, const State& stateC, const EventSet& prev_exC)
142 // See eqs. 5.7 of section 5.2 of [3]
143 // C = C' + {e_cur}, i.e. C' = C - {e_cur}
147 // ex(C) = ex(C' + {e_cur}) = ex(C') / {e_cur} +
148 // U{<a, K> : K is maximal, `a` depends on all of K, `a` enabled at config(K) }
149 const UnfoldingEvent* e_cur = C.get_latest_event();
150 EventSet exC = prev_exC;
153 // IMPORTANT NOTE: In order to have deterministic results, we need to process
154 // the actors in a deterministic manner so that events are discovered by
155 // UDPOR in a deterministic order. The processing done here always processes
156 // actors in a consistent order since `std::map` is by-default ordered using
157 // `std::less<Key>` (see the return type of `State::get_actors_list()`)
158 for (const auto& [aid, actor_state] : stateC.get_actors_list()) {
159 for (const auto& transition : actor_state.get_enabled_transitions()) {
160 XBT_DEBUG("\t Considering partial extension for %s", transition->to_string().c_str());
161 EventSet extension = ExtensionSetCalculator::partially_extend(C, &unfolding, transition);
162 exC.form_union(extension);
168 EventSet UdporChecker::compute_enC(const Configuration& C, const EventSet& exC) const
171 for (const auto* e : exC) {
172 if (C.is_compatible_with(e)) {
179 void UdporChecker::move_to_stateCe(State* state, UnfoldingEvent* e)
181 const aid_t next_actor = e->get_transition()->aid_;
183 // TODO: Add the trace if possible for reporting a bug
184 xbt_assert(next_actor >= 0, "\n\n****** INVARIANT VIOLATION ******\n"
185 "In reaching this execution path, UDPOR ensures that at least one\n"
186 "one transition of the state of an visited event is enabled, yet no\n"
187 "state was actually enabled. Please report this as a bug.\n"
188 "*********************************\n\n");
189 auto latest_transition_by_next_actor = state->execute_next(next_actor, get_remote_app());
191 // The transition that is associated with the event was just
192 // executed, so it's possible that the new version of the transition
193 // (i.e. the one after execution) has *more* information than
194 // that which existed *prior* to execution.
197 // ------- !!!!! UDPOR INVARIANT !!!!! -------
199 // At this point, we are leveraging the fact that
200 // UDPOR will not contain more than one copy of any
201 // transition executed by any actor for any
202 // particular step taken by that actor. That is,
203 // if transition `i` of the `j`th actor is contained in the
204 // configuration `C` currently under consideration
205 // by UDPOR, then only one and only one copy exists in `C`
207 // This means that we can referesh the transitions associated
208 // with each event lazily, i.e. only after we have chosen the
209 // event to continue our execution.
210 e->set_transition(std::move(latest_transition_by_next_actor));
213 void UdporChecker::restore_program_state_with_current_stack()
215 XBT_DEBUG("Restoring state using the current stack");
216 get_remote_app().restore_initial_state();
218 /* Traverse the stack from the state at position start and re-execute the transitions */
219 for (const std::unique_ptr<State>& state : state_stack) {
220 if (state == state_stack.back()) /* If we are arrived on the target state, don't replay the outgoing transition */
222 state->get_transition_out()->replay(get_remote_app());
226 std::unique_ptr<State> UdporChecker::record_current_state()
228 auto next_state = this->get_current_state();
230 // In UDPOR, we care about all enabled transitions in a given state
231 next_state->consider_all();
236 UnfoldingEvent* UdporChecker::select_next_unfolding_event(const EventSet& A, const EventSet& enC)
239 throw std::invalid_argument("There are no unfolding events to select. "
240 "Are you sure that you checked that en(C) was not "
241 "empty before attempting to select an event from it?");
244 // UDPOR's exploration is non-deterministic (as is DPOR's)
245 // in the sense that at any given point there may
246 // be multiple paths that can be followed. The correctness and optimality
247 // of the algorithm remains unaffected by the route taken by UDPOR when
248 // given multiple choices; but to ensure that SimGrid itself has deterministic
249 // behavior on all platforms, we always pick events with lower id's
250 // to ensure we explore the unfolding deterministically.
252 const auto min_event = std::min_element(enC.begin(), enC.end(),
253 [](const auto e1, const auto e2) { return e1->get_id() < e2->get_id(); });
254 return const_cast<UnfoldingEvent*>(*min_event);
256 const auto intersection = A.make_intersection(enC);
257 const auto min_event = std::min_element(intersection.begin(), intersection.end(),
258 [](const auto e1, const auto e2) { return e1->get_id() < e2->get_id(); });
259 return const_cast<UnfoldingEvent*>(*min_event);
263 void UdporChecker::clean_up_explore(const UnfoldingEvent* e, const Configuration& C, const EventSet& D)
265 // The "clean-up set" conceptually represents
266 // those events which will no longer be considered
267 // by UDPOR during its exploration. The concept is
268 // introduced to avoid modification during iteration
269 // over the current unfolding to determine who needs to
270 // be removed. Since sets are unordered, it's quite possible
271 // that e.g. two events `e` and `e'` such that `e < e'`
272 // which are determined eligible for removal are removed
273 // in the order `e` and then `e'`. Determining that `e'`
274 // needs to be removed requires that its history be in
275 // tact to e.g. compute the conflicts with the event.
277 // Thus, we compute the set and remove all of the events
278 // at once in lieu of removing events while iterating over them.
279 // We can hypothesize that processing the events in reverse
280 // topological order would prevent any issues concerning
281 // the order in which are processed
282 EventSet clean_up_set;
284 // Q_(C, D, U) = C u D u U (complicated expression)
285 // See page 9 of "Unfolding-based Partial Order Reduction"
288 const EventSet C_union_D = C.get_events().make_union(D);
290 // "U (complicated expression)" portion
291 const EventSet conflict_union = std::accumulate(
292 C_union_D.begin(), C_union_D.end(), EventSet(), [&](const EventSet acc, const UnfoldingEvent* e_prime) {
293 return acc.make_union(unfolding.get_immediate_conflicts_of(e_prime));
296 const EventSet Q_CDU = C_union_D.make_union(conflict_union.get_local_config());
298 XBT_DEBUG("Computed Q_CDU as '%s'", Q_CDU.to_string().c_str());
300 // Move {e} \ Q_CDU from U to G
301 if (not Q_CDU.contains(e)) {
302 XBT_DEBUG("Moving %s from U to G...", e->to_string().c_str());
303 clean_up_set.insert(e);
306 // foreach ê in #ⁱ_U(e)
307 for (const auto* e_hat : this->unfolding.get_immediate_conflicts_of(e)) {
308 // Move [ê] \ Q_CDU from U to G
309 const EventSet to_remove = e_hat->get_local_config().subtracting(Q_CDU);
310 XBT_DEBUG("Moving {%s} from U to G...", to_remove.to_string().c_str());
311 clean_up_set.form_union(to_remove);
314 // TODO: We still perhaps need to
315 // figure out how to deal with the fact that the previous
316 // extension sets computed for past configurations
317 // contain events that may be removed from `U`. Perhaps
318 // it would be best to keep them around forever (they
319 // are moved to `G` after all and can be discarded at will,
320 // which means they may never have to be removed at all).
322 // Of course, the benefit of moving them into the set `G`
323 // is that the computation for immediate conflicts becomes
324 // more efficient (we have to search all of `U` for such conflicts,
325 // and there would be no reason to search those events
326 // that UDPOR has marked as no longer being important)
327 // For now, there appear to be no "obvious" issues (although
328 // UDPOR's behavior is often far from obvious...)
329 this->unfolding.mark_finished(clean_up_set);
332 RecordTrace UdporChecker::get_record_trace()
335 for (auto const& state : state_stack)
336 res.push_back(state->get_transition_out().get());
340 } // namespace simgrid::mc::udpor
342 namespace simgrid::mc {
344 Exploration* create_udpor_checker(const std::vector<char*>& args)
346 return new simgrid::mc::udpor::UdporChecker(args);
349 } // namespace simgrid::mc