1 /* Copyright (c) 2008-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/odpor/Execution.hpp"
7 #include "src/mc/api/State.hpp"
8 #include "xbt/asserts.h"
9 #include "xbt/string.hpp"
14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_odpor_execution, mc_dfs, "ODPOR exploration algorithm of the model-checker");
16 namespace simgrid::mc::odpor {
18 std::vector<std::string> get_textual_trace(const PartialExecution& w)
20 std::vector<std::string> trace;
21 for (const auto& t : w) {
22 auto a = xbt::string_printf("Actor %ld: %s", t->aid_, t->to_string(true).c_str());
23 trace.emplace_back(std::move(a));
28 Execution::Execution(const PartialExecution& w)
30 push_partial_execution(w);
33 void Execution::push_transition(std::shared_ptr<Transition> t)
36 throw std::invalid_argument("Unexpectedly received `nullptr`");
38 ClockVector max_clock_vector;
39 for (const Event& e : this->contents_) {
40 if (e.get_transition()->depends(t.get())) {
41 max_clock_vector = ClockVector::max(max_clock_vector, e.get_clock_vector());
44 max_clock_vector[t->aid_] = this->size();
45 contents_.push_back(Event({std::move(t), max_clock_vector}));
48 void Execution::push_partial_execution(const PartialExecution& w)
50 for (const auto& t : w) {
55 std::vector<std::string> Execution::get_textual_trace() const
57 std::vector<std::string> trace;
58 for (const auto& t : this->contents_) {
59 auto a = xbt::string_printf("Actor %ld: %s", t.get_transition()->aid_, t.get_transition()->to_string(true).c_str());
60 trace.emplace_back(std::move(a));
65 std::unordered_set<Execution::EventHandle> Execution::get_racing_events_of(Execution::EventHandle target) const
67 std::unordered_set<Execution::EventHandle> racing_events;
68 // This keep tracks of events that happens-before the target
69 std::unordered_set<Execution::EventHandle> disqualified_events;
71 // For each event of the execution
72 for (auto e_i = target; e_i != std::numeric_limits<Execution::EventHandle>::max(); e_i--) {
73 // We need `e_i -->_E target` as a necessary condition
74 if (not happens_before(e_i, target)) {
75 XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` discarded because `%u` --\\-->_E `%u`", target, e_i, e_i, target);
79 // Further, `proc(e_i) != proc(target)`
80 if (get_actor_with_handle(e_i) == get_actor_with_handle(target)) {
81 disqualified_events.insert(e_i);
82 XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` disqualified because proc(`%u`)=proc(`%u`)", target, e_i, e_i,
87 // There could an event that "happens-between" the two events which would discount `e_i` as a race
88 for (auto e_j = e_i; e_j < target; e_j++) {
90 // 1. e_i --->_E e_j; and
91 // 2. disqualified_events.count(e_j) > 0
92 // then e_i --->_E target indirectly (either through
93 // e_j directly, or transitively through e_j)
94 if (disqualified_events.count(e_j) > 0 && happens_before(e_i, e_j)) {
95 XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` disqualified because `%u` happens-between `%u`-->`%u`-->`%u`)",
96 target, e_i, e_j, e_i, e_j, target);
97 disqualified_events.insert(e_i);
102 // If `e_i` wasn't disqualified in the last round,
103 // it's in a race with `target`. After marking it
104 // as such, we ensure no other event `e` can happen-before
105 // it (since this would transitively make it the event
106 // which "happens-between" `target` and `e`)
107 if (disqualified_events.count(e_i) == 0) {
108 XBT_DEBUG("ODPOR_RACING_EVENTS with `%u` : `%u` is a valid racing event", target, e_i);
109 racing_events.insert(e_i);
110 disqualified_events.insert(e_i);
114 return racing_events;
117 std::unordered_set<Execution::EventHandle> Execution::get_reversible_races_of(EventHandle handle) const
119 std::unordered_set<EventHandle> reversible_races;
120 const auto* this_transition = get_transition_for_handle(handle);
121 for (EventHandle race : get_racing_events_of(handle)) {
122 const auto* other_transition = get_transition_for_handle(race);
124 if (this_transition->reversible_race(other_transition)) {
125 reversible_races.insert(race);
128 return reversible_races;
131 Execution Execution::get_prefix_before(Execution::EventHandle handle) const
133 return Execution(std::vector<Event>{contents_.begin(), contents_.begin() + handle});
136 std::unordered_set<aid_t>
137 Execution::get_missing_source_set_actors_from(EventHandle e, const std::unordered_set<aid_t>& backtrack_set) const
139 // If this execution is empty, there are no initials
140 // relative to the last transition added to the execution
141 // since such a transition does not exist
143 return std::unordered_set<aid_t>{};
146 // To actually compute `I_[E'](v) ∩ backtrack(E')`, we must
147 // first compute `E'` and "move" in the direction of `v`.
148 // We perform a scan over `E` (this execution) and make
149 // note of any events which occur after `e` but don't
150 // "happen-after" `e` by pushing them onto `E'`. Note that
151 // correctness is still preserved in computing `v` "on-the-fly"
152 // to determine if an event `e` by actor `q` is an initial for `E'`
153 // after `v`: only those events that "occur-before" `e` in `v` could
154 // "happen-before" `ve for any valid "happens-before" relation
155 // (see property 1 in the ODPOR paper, viz. "is included in <_E")
157 // First, grab `E' := pre(e, E)` and determine what actor `p` is
158 const auto next_E_p = get_latest_event_handle().value();
159 xbt_assert(e != next_E_p,
160 "This method assumes that the event `e` (%u) and `next_[E](p)` (%u)"
161 "are in a reversible race, yet we claim to have such a race between the"
162 "same event. This indicates the the SDPOR pseudocode implementation is broken "
163 "as it supplies these values.",
165 Execution E_prime_v = get_prefix_before(e);
166 std::vector<sdpor::Execution::EventHandle> v;
167 std::unordered_set<aid_t> I_E_prime_v;
168 std::unordered_set<aid_t> disqualified_actors;
170 // Note `e + 1` here: `notdep(e, E)` is defined as the
171 // set of events that *occur-after* but don't *happen-after* `e`
172 for (auto e_prime = e + 1; e_prime <= next_E_p; ++e_prime) {
173 // Any event `e*` which occurs after `e` but which does not
174 // happen after `e` is a member of `v`. In addition to marking
175 // the event in `v`, we also "simulate" running the action `v`
177 if (not happens_before(e, e_prime) || e_prime == next_E_p) {
178 // First, push the transition onto the hypothetical execution
179 E_prime_v.push_transition(get_event_with_handle(e_prime).get_transition());
180 const EventHandle e_prime_in_E_prime_v = E_prime_v.get_latest_event_handle().value();
182 // When checking whether any event in `dom_[E'](v)` happens before
183 // `next_[E'](q)` below for thread `q`, we must consider that the
184 // events relative to `E` (this execution) are different than those
185 // relative to `E'.v`. Thus e.g. event `7` in `E` may be event `4`
186 // in `E'.v`. Since we are asking about "happens-before"
187 // `-->_[E'.v]` about `E'.v`, we must build `v` relative to `E'`.
189 // Note that we add `q` to v regardless of whether `q` itself has been
190 // disqualified since we've determined that `e_prime` "occurs-after" but
191 // does not "happen-after" `e`
192 v.push_back(e_prime_in_E_prime_v);
194 const aid_t q = E_prime_v.get_actor_with_handle(e_prime_in_E_prime_v);
195 if (disqualified_actors.count(q) > 0) { // Did we already note that `q` is not an initial?
198 const bool is_initial = std::none_of(v.begin(), v.end(), [&](const auto& e_star) {
199 return E_prime_v.happens_before(e_star, e_prime_in_E_prime_v);
202 // If the backtrack set already contains `q`, we're done:
203 // they've made note to search for (or have already searched for)
205 if (backtrack_set.count(q) > 0) {
206 return std::unordered_set<aid_t>{};
208 I_E_prime_v.insert(q);
211 // If `q` is disqualified as a candidate, clearly
212 // no event occurring after `e_prime` in `E` executed
213 // by actor `q` will qualify since any (valid) happens-before
214 // relation orders actions taken by each actor
215 disqualified_actors.insert(q);
219 xbt_assert(not I_E_prime_v.empty(),
220 "For any non-empty execution, we know that "
221 "at minimum one actor is an initial since "
222 "some execution is possible with respect to a "
223 "prefix before event `%u`, yet we didn't find anyone. "
224 "This implies the implementation of this function is broken.",
229 std::optional<PartialExecution> Execution::get_odpor_extension_from(EventHandle e, EventHandle e_prime,
230 const State& state_at_e) const
232 // `e` is assumed to be in a reversible race with `e_prime`.
233 // If `e > e_prime`, then `e` occurs-after `e_prime` which means
234 // `e` could not race with if
236 throw std::invalid_argument("ODPOR extensions can only be computed for "
237 "events in a reversible race, which is claimed, "
238 "yet the racing event 'occurs-after' the target");
246 std::vector<Execution::EventHandle> v_handles;
247 std::unordered_set<aid_t> WI_E_prime_v;
248 std::unordered_set<aid_t> disqualified_actors;
249 Execution E_prime_v = get_prefix_before(e);
250 const std::unordered_set<aid_t> sleep_E_prime = state_at_e.get_sleeping_actors();
252 // Note `e + 1` here: `notdep(e, E)` is defined as the
253 // set of events that *occur-after* but don't *happen-after* `e`
255 // SUBTLE NOTE: ODPOR requires us to compute `notdep(e, E)` EVEN THOUGH
256 // the race is between `e` and `e'`; that is, events occurring in `E`
257 // that "occur-after" `e'` may end up in the partial execution `v`.
259 // Observe that `notdep(e, E).proc(e')` will contain all transitions
260 // that don't happen-after `e` in the order they appear FOLLOWED BY
261 // THE **TRANSITION** ASSOCIATED WITH **`e'`**!!
263 // SUBTLE NOTE: Observe that any event that "happens-after" `e'`
264 // must necessarily "happen-after" `e` as well, since `e` and
265 // `e'` are presumed to be in a reversible race. Hence, we know that
266 // all events `e_star` such that `e` "happens-before" `e_star` cannot affect
267 // the enabledness of `e'`; furthermore, `e'` cannot affect the enabledness
268 // of any event independent with `e` that "occurs-after" `e'`
269 for (auto e_star = e + 1; e_star <= get_latest_event_handle().value(); ++e_star) {
270 // Any event `e*` which occurs after `e` but which does not
271 // happen after `e` is a member of `v`. In addition to marking
272 // the event in `v`, we also "simulate" running the action `v` from E'
273 // to be able to compute `--->[E'.v]`
274 if (not happens_before(e, e_star)) {
275 xbt_assert(e_star != e_prime,
276 "Invariant Violation: We claimed events %u and %u were in a reversible race, yet we also "
277 "claim that they do not happen-before one another. This is impossible: "
278 "are you sure that the two events are in a reversible race?",
280 E_prime_v.push_transition(get_event_with_handle(e_star).get_transition());
281 v.push_back(get_event_with_handle(e_star).get_transition());
283 XBT_DEBUG("Added Event `%u` (%ld:%s) to the construction of v", e_star, get_actor_with_handle(e_star),
284 get_event_with_handle(e_star).get_transition()->to_string().c_str());
286 const EventHandle e_star_in_E_prime_v = E_prime_v.get_latest_event_handle().value();
288 // When checking whether any event in `dom_[E'](v)` happens before
289 // `next_[E'](q)` below for thread `q`, we must consider that the
290 // events relative to `E` (this execution) are different than those
291 // relative to `E'.v`. Thus e.g. event `7` in `E` may be event `4`
292 // in `E'.v`. Since we are asking about "happens-before"
293 // `-->_[E'.v]` about `E'.v`, we must build `v` relative to `E'`
294 v_handles.push_back(e_star_in_E_prime_v);
296 // Note that we add `q` to v regardless of whether `q` itself has been
297 // disqualified since `q` may itself disqualify other actors
298 // (i.e. even if `q` is disqualified from being an initial, it
299 // is still contained in the sequence `v`)
300 const aid_t q = E_prime_v.get_actor_with_handle(e_star_in_E_prime_v);
301 if (disqualified_actors.count(q) > 0) { // Did we already note that `q` is not an initial?
304 const bool is_initial = std::none_of(v_handles.begin(), v_handles.end(), [&](const auto& handle) {
305 return E_prime_v.happens_before(handle, e_star_in_E_prime_v);
308 // If the sleep set already contains `q`, we're done:
309 // we've found an initial contained in the sleep set and
310 // so the intersection is non-empty
311 if (sleep_E_prime.count(q) > 0) {
314 WI_E_prime_v.insert(q);
317 // If `q` is disqualified as a candidate, clearly
318 // no event occurring after `e_prime` in `E` executed
319 // by actor `q` will qualify since any (valid) happens-before
320 // relation orders actions taken by each actor
321 disqualified_actors.insert(q);
324 XBT_DEBUG("Event `%u` (%ld:%s) dismissed from the construction of v", e_star, get_actor_with_handle(e_star),
325 get_event_with_handle(e_star).get_transition()->to_string().c_str());
329 // Now we add `e_prime := <q, i>` to `E'.v` and repeat the same work
330 // It's possible `proc(e_prime)` is an initial
332 // Note the form of `v` in the pseudocode:
333 // `v := notdep(e, E).e'^
334 E_prime_v.push_transition(get_event_with_handle(e_prime).get_transition());
335 v.push_back(get_event_with_handle(e_prime).get_transition());
337 const EventHandle e_prime_in_E_prime_v = E_prime_v.get_latest_event_handle().value();
338 v_handles.push_back(e_prime_in_E_prime_v);
340 const bool is_initial = std::none_of(v_handles.begin(), v_handles.end(), [&](const auto& handle) {
341 return E_prime_v.happens_before(handle, e_prime_in_E_prime_v);
344 if (const aid_t q = E_prime_v.get_actor_with_handle(e_prime_in_E_prime_v); sleep_E_prime.count(q) > 0) {
347 WI_E_prime_v.insert(q);
351 const Execution pre_E_e = get_prefix_before(e);
352 const auto sleeping_actors = state_at_e.get_sleeping_actors();
354 // Check if any enabled actor that is independent with
355 // this execution after `v` is contained in the sleep set
356 for (const auto& [aid, astate] : state_at_e.get_actors_list()) {
357 const bool is_in_WI_E =
358 astate.is_enabled() and pre_E_e.is_independent_with_execution_of(v, astate.get_transition());
359 const bool is_in_sleep_set = sleeping_actors.count(aid) > 0;
361 // `action(aid)` is in `WI_[E](v)` but also is contained in the sleep set.
362 // This implies that the intersection between the two is non-empty
363 if (is_in_WI_E && is_in_sleep_set)
370 bool Execution::is_initial_after_execution_of(const PartialExecution& w, aid_t p) const
373 std::vector<EventHandle> w_handles;
374 for (const auto& w_i : w) {
375 // Take one step in the direction of `w`
376 E_w.push_transition(w_i);
378 // If that step happened to be executed by `p`,
379 // great: we know that `p` is contained in `w`.
380 // We now need to verify that it doens't "happen-after"
381 // any events which occur before it
382 if (w_i->aid_ == p) {
383 const auto p_handle = E_w.get_latest_event_handle().value();
384 return std::none_of(w_handles.begin(), w_handles.end(),
385 [&](const auto handle) { return E_w.happens_before(handle, p_handle); });
387 w_handles.push_back(E_w.get_latest_event_handle().value());
393 bool Execution::is_independent_with_execution_of(const PartialExecution& w, std::shared_ptr<Transition> next_E_p) const
395 // INVARIANT: Here, we assume that for any process `p_i` of `w`,
396 // the events of this execution followed by the execution of all
397 // actors occurring before `p_i` in `v` (`p_j`, `0 <= j < i`)
398 // are sufficient to enable `p_i`. This is fortunately the case
399 // with what ODPOR requires of us, viz. to ask the question about
400 // `v := notdep(e, E)` for some execution `E` and event `e` of
403 E_p_w.push_transition(std::move(next_E_p));
404 const auto p_handle = E_p_w.get_latest_event_handle().value();
406 // As we add events to `w`, verify that none
407 // of them "happen-after" the event associated with
408 // the step `next_E_p` (viz. p_handle)
409 for (const auto& w_i : w) {
410 E_p_w.push_transition(w_i);
411 const auto w_i_handle = E_p_w.get_latest_event_handle().value();
412 if (E_p_w.happens_before(p_handle, w_i_handle)) {
419 std::optional<PartialExecution> Execution::get_shortest_odpor_sq_subset_insertion(const PartialExecution& v,
420 const PartialExecution& w) const
422 // See section 4 of Abdulla. et al.'s 2017 ODPOR paper for details (specifically
423 // where the [iterative] computation of `v ~_[E] w` is described)
427 for (const auto& next_E_p : v) {
428 // Is `p in `I_[E](w)`?
429 if (const aid_t p = next_E_p->aid_; E_v.is_initial_after_execution_of(w_now, p)) {
430 // Remove `p` from w and continue
432 // INVARIANT: If `p` occurs in `w`, it had better refer to the same
433 // transition referenced by `v`. Unfortunately, we have two
434 // sources of truth here which can be manipulated at the same
435 // time as arguments to the function. If ODPOR works correctly,
436 // they should always refer to the same value; but as a sanity check,
437 // we have an assert that tests that at least the types are the same.
438 const auto action_by_p_in_w =
439 std::find_if(w_now.begin(), w_now.end(), [=](const auto& action) { return action->aid_ == p; });
440 xbt_assert(action_by_p_in_w != w_now.end(), "Invariant violated: actor `p` "
441 "is claimed to be an initial after `w` but is "
442 "not actually contained in `w`. This indicates that there "
443 "is a bug computing initials");
444 const auto& w_action = *action_by_p_in_w;
445 xbt_assert(w_action->type_ == next_E_p->type_,
446 "Invariant violated: `v` claims that actor `%ld` executes '%s' while "
447 "`w` claims that it executes '%s'. These two partial executions both "
448 "refer to `next_[E](p)`, which should be the same",
449 p, next_E_p->to_string(false).c_str(), w_action->to_string(false).c_str());
450 w_now.erase(action_by_p_in_w);
453 else if (E_v.is_independent_with_execution_of(w_now, next_E_p)) {
454 // INVARIANT: Note that it is impossible for `p` to be
455 // excluded from the set `I_[E](w)` BUT ALSO be contained in
456 // `w` itself if `E ⊢ p ◇ w` (intuitively, the fact that `E ⊢ p ◇ w`
457 // means that are able to move `p` anywhere in `w` IF it occurred, so
458 // if it really does occur we know it must then be an initial).
459 // We assert this is the case here
460 const auto action_by_p_in_w =
461 std::find_if(w_now.begin(), w_now.end(), [=](const auto& action) { return action->aid_ == p; });
462 xbt_assert(action_by_p_in_w == w_now.end(),
463 "Invariant violated: We claimed that actor `%ld` is not an initial "
464 "after `w`, yet it's independent with all actions of `w` AND occurs in `w`."
465 "This indicates that there is a bug computing initials",
468 // Neither of the two above conditions hold, so the relation fails
472 // Move one step forward in the direction of `v` and repeat
473 E_v.push_transition(next_E_p);
475 return std::optional<PartialExecution>{std::move(w_now)};
478 bool Execution::happens_before(Execution::EventHandle e1_handle, Execution::EventHandle e2_handle) const
480 // 1. "happens-before" (-->_E) is a subset of "occurs before" (<_E)
481 // and is an irreflexive relation
482 if (e1_handle >= e2_handle) {
486 // Each execution maintains a stack of clock vectors which are updated
487 // according to the procedure outlined in section 4 of the original DPOR paper
488 const Event& e2 = get_event_with_handle(e2_handle);
489 const aid_t proc_e1 = get_actor_with_handle(e1_handle);
491 if (const auto e1_in_e2_clock = e2.get_clock_vector().get(proc_e1); e1_in_e2_clock.has_value()) {
492 return e1_handle <= e1_in_e2_clock.value();
494 // If `e1` does not appear in e2's clock vector, this implies
495 // not only that the transitions associated with `e1` and `e2
496 // are independent, but further that there are no transitive
497 // dependencies between e1 and e2
501 } // namespace simgrid::mc::odpor