1 /* Copyright (c) 2017-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/3rd-party/catch.hpp"
7 #include "src/mc/explo/odpor/Execution.hpp"
8 #include "src/mc/explo/odpor/WakeupTree.hpp"
9 #include "src/mc/explo/udpor/udpor_tests_private.hpp"
10 #include "src/xbt/utils/iter/LazyPowerset.hpp"
12 using namespace simgrid::mc;
13 using namespace simgrid::mc::odpor;
14 using namespace simgrid::mc::udpor;
16 static void test_tree_iterator(const WakeupTree& tree, const std::vector<PartialExecution>& expected)
18 uint64_t num_nodes_traversed = 0;
19 auto tree_iter = tree.begin();
20 for (auto expected_iter = expected.begin(); expected_iter != expected.end();
21 ++expected_iter, ++tree_iter, ++num_nodes_traversed) {
22 REQUIRE(tree_iter != tree.end());
23 REQUIRE((*tree_iter)->get_sequence() == *expected_iter);
25 REQUIRE(num_nodes_traversed == tree.get_num_nodes());
28 TEST_CASE("simgrid::mc::odpor::WakeupTree: Constructing Trees")
30 SECTION("Constructing empty trees")
33 REQUIRE(tree.empty());
34 REQUIRE(tree.get_num_entries() == 0);
35 REQUIRE(tree.get_num_nodes() == 1);
36 REQUIRE_FALSE(tree.get_min_single_process_node().has_value());
37 REQUIRE_FALSE(tree.get_min_single_process_actor().has_value());
38 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
41 SECTION("Testing subtree creation and manipulation")
43 // Here, we make everything dependent. This will ensure that each unique sequence
44 // inserted into the tree never "eventually looks like"
45 const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
46 const auto a1 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
47 const auto a2 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
48 const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 4);
49 const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 5);
50 const auto a5 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 6);
53 execution.push_transition(a0);
54 execution.push_transition(a1);
55 execution.push_transition(a2);
56 execution.push_transition(a3);
57 execution.push_transition(a4);
58 execution.push_transition(a5);
60 // The tree is as follows:
71 // Recall that new nodes (in this case the one with
72 // action `a2`) are added such that they are "greater than" (under
73 // the tree's `<` relation) all those that exist under the given parent
75 tree.insert(Execution(), {a1, a2, a3, a4});
76 tree.insert(Execution(), {a1, a3, a2, a4});
77 tree.insert(Execution(), {a1, a3, a2, a4, a5});
78 tree.insert(Execution(), {a1, a3, a5});
79 tree.insert(Execution(), {a4, a2, a1, a3});
80 REQUIRE(tree.get_num_nodes() == 13);
81 test_tree_iterator(tree, std::vector<PartialExecution>{
82 PartialExecution{a1, a2, a3, a4}, PartialExecution{a1, a2, a3},
83 PartialExecution{a1, a2}, PartialExecution{a1, a3, a2, a4},
84 PartialExecution{a1, a3, a2}, PartialExecution{a1, a3, a5}, PartialExecution{a1, a3},
85 PartialExecution{a1}, PartialExecution{a4, a2, a1, a3}, PartialExecution{a4, a2, a1},
86 PartialExecution{a4, a2}, PartialExecution{a4}, PartialExecution{}});
88 SECTION("Cloning a tree from the root produces the same tree")
90 // The root node is the last node
91 auto tree_root = tree.begin();
92 std::advance(tree_root, tree.get_num_nodes() - 1);
94 WakeupTree clone = WakeupTree::make_subtree_rooted_at(*tree_root);
95 REQUIRE(clone.empty() == tree.empty());
96 REQUIRE(clone.get_num_entries() == tree.get_num_entries());
97 REQUIRE(clone.get_num_nodes() == tree.get_num_nodes());
99 auto tree_iter = tree.begin();
100 for (auto clone_iter = clone.begin(); clone_iter != clone.end(); ++clone_iter, ++tree_iter) {
101 REQUIRE(tree_iter != tree.end());
102 REQUIRE((*tree_iter)->get_sequence() == (*clone_iter)->get_sequence());
106 SECTION("Cloning a subtree from a leaf gives an empty tree")
108 // Let's pick the first leaf
109 WakeupTree clone = WakeupTree::make_subtree_rooted_at(*tree.begin());
110 REQUIRE(clone.empty());
111 REQUIRE(clone.get_num_entries() == 0);
112 REQUIRE(clone.get_num_nodes() == 1);
115 SECTION("Cloning a subtree from an interior node gives the subtree underneath")
117 // Here, we pick the second-to-last node in the
118 // series, which is the right-most child of the root
119 auto right_most = tree.begin();
120 std::advance(right_most, tree.get_num_nodes() - 2);
122 WakeupTree clone = WakeupTree::make_subtree_rooted_at(*right_most);
123 REQUIRE_FALSE(clone.empty());
124 REQUIRE(clone.get_num_entries() == 3);
125 REQUIRE(clone.get_num_nodes() == 4);
126 // Importantly, note that action `a4` is not included in
127 // any of the executions; for in the subtree `clone` `a4`
129 test_tree_iterator(clone, std::vector<PartialExecution>{PartialExecution{a2, a1, a3}, PartialExecution{a2, a1},
130 PartialExecution{a2}, PartialExecution{}});
133 SECTION("Removing the first single-process subtree")
135 // Prior to removal, the first `a1` was the first single-process node
136 REQUIRE(tree.get_min_single_process_node().has_value());
137 REQUIRE(tree.get_min_single_process_actor().has_value());
138 REQUIRE(tree.get_min_single_process_actor().value() == a1->aid_);
140 tree.remove_min_single_process_subtree();
142 // Now the first `a4` is
143 REQUIRE(tree.get_min_single_process_node().has_value());
144 REQUIRE(tree.get_min_single_process_actor().has_value());
145 REQUIRE(tree.get_min_single_process_actor().value() == a4->aid_);
147 REQUIRE(tree.get_num_nodes() == 5);
148 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4, a2, a1, a3},
149 PartialExecution{a4, a2, a1}, PartialExecution{a4, a2},
150 PartialExecution{a4}, PartialExecution{}});
151 tree.remove_min_single_process_subtree();
153 // At this point, we've removed each single-process subtree, so
154 // the tree should be empty
155 REQUIRE(tree.empty());
160 TEST_CASE("simgrid::mc::odpor::WakeupTree: Testing Insertion for Empty Executions")
162 SECTION("Following an execution")
164 // We imagine the following completed execution `E`
165 // consisting of executing actions a0-a3. Execution
166 // `E` is the first such maximal execution explored
167 // by ODPOR, which implies that a) all sleep sets are
168 // empty and b) all wakeup trees (i.e. for each prefix) consist of the root
169 // node with a single leaf containing the action
170 // taken, save for the wakeup tree of the execution itself
173 // We first notice that there's a reversible race between
176 const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
177 const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
178 const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
179 const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
182 execution.push_transition(a0);
183 execution.push_transition(a1);
184 execution.push_transition(a2);
185 execution.push_transition(a3);
187 REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
188 REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
192 SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
194 tree.insert(Execution(), {});
195 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
198 // First, we initialize the tree to how it looked prior
199 // to the insertion of the race.
200 tree.insert(Execution(), {a0});
202 // Then, after insertion, we ensure that the node was
203 // indeed added to the tree.
204 tree.insert(Execution(), {a1, a3});
205 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
206 PartialExecution{a1}, PartialExecution{}});
208 SECTION("Attempting to re-insert the same EXACT sequence should have no effect")
210 tree.insert(Execution(), {a1, a3});
211 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
212 PartialExecution{a1}, PartialExecution{}});
215 SECTION("Attempting to re-insert an equivalent sequence should have no effect")
217 // a3 and a1 are interchangeable since `a1` is independent with everything.
218 // Since we found an equivalent sequence that is a leaf, nothing should result..
219 tree.insert(Execution(), {a3, a1});
220 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
221 PartialExecution{a1}, PartialExecution{}});
224 SECTION("Attempting to insert the empty sequence should have no effect")
226 tree.insert(Execution(), {});
227 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
228 PartialExecution{a1}, PartialExecution{}});
231 SECTION("Inserting an extension should create a branch point")
233 // `a1.a2` shares the same `a1` prefix as `a1.a3`. Thus, the tree
234 // should now look as follows:
242 // Recall that new nodes (in this case the one with
243 // action `a2`) are added such that they are "greater than" (under
244 // the tree's `<` relation) all those that exist under the given parent.
245 tree.insert(Execution(), {a1, a2});
246 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
247 PartialExecution{a1, a2}, PartialExecution{a1},
248 PartialExecution{}});
252 SECTION("Performing Arbitrary Insertions")
254 const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
255 const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
256 const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 3);
257 const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
258 const auto a4 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
259 const auto a5 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
262 SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
264 tree.insert(Execution(), {});
265 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
268 SECTION("Attempting to re-insert the same sequence multiple times should have no extra effect")
270 tree.insert(Execution(), {a4});
271 tree.insert(Execution(), {a4});
272 tree.insert(Execution(), {a4});
273 REQUIRE(tree.get_num_nodes() == 2);
274 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4}, PartialExecution{}});
277 SECTION("Attempting to insert an independent sequence same should have no extra effect")
279 // a4 and a1 are independent actions. Intuitively, then, we need only
280 // search one ordering of the two actions. The wakeup tree handles
281 // this by computing the `~` relation. The relation itself determines
282 // whether the `a1` is an initial of `a3`, which it is not. It then
283 // checks whether `a1` is independent with everything in the sequence
284 // (in this case, consisting only of `a1`) which IS true. Since `a4`
285 // is already a leaf node of the tree, it suffices to only have `a4`
286 // in this tree to guide ODPOR.
287 tree.insert(Execution(), {a4});
288 tree.insert(Execution(), {a1});
289 REQUIRE(tree.get_num_nodes() == 2);
290 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4}, PartialExecution{}});
294 "Attempting to insert a progression of executions should have no extra effect when the first process is a leaf")
296 // All progressions starting with `a0` are effectively already accounted
297 // for by inserting `a0` since we `a0` "can always be made to look like"
298 // (viz. the `~` relation) `a0.*` where `*` is some sequence of actions
299 tree.insert(Execution(), {a0});
300 tree.insert(Execution(), {a0, a3});
301 tree.insert(Execution(), {a0, a3, a2});
302 tree.insert(Execution(), {a0, a3, a2, a4});
303 tree.insert(Execution(), {a0, a3, a2, a4});
304 REQUIRE(tree.get_num_nodes() == 2);
305 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{}});
308 SECTION("Stress test with multiple branch points: `~_E` with different looking sequences")
310 // After the insertions below, the tree looks like the following:
316 tree.insert(Execution(), {a0});
317 tree.insert(Execution(), {a2, a0});
318 tree.insert(Execution(), {a2, a3});
319 tree.insert(Execution(), {a2, a5});
320 REQUIRE(tree.get_num_nodes() == 6);
321 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
322 PartialExecution{a2, a3}, PartialExecution{a2, a5},
323 PartialExecution{a2}, PartialExecution{}});
324 SECTION("Adding more stress")
326 // In this case, `a2` and `a1` can be interchanged with each other.
327 // Thus `a2.a1 == a1.a2`. Since there is already an interior node
328 // containing `a2`, we attempt to add the what remains (viz. `a1`) to the
329 // series. HOWEVER: we notice that `a2.a5` is "eventually equivalent to"
330 // (that is `~` with) `a1.a2` since `a2` is an initial of the latter and
331 // `a1` and `a5` are independent of each other.
332 tree.insert(Execution(), {a1, a2});
333 REQUIRE(tree.get_num_nodes() == 6);
334 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
335 PartialExecution{a2, a3}, PartialExecution{a2, a5},
336 PartialExecution{a2}, PartialExecution{}});
338 // With a3.a0, we notice that starting a sequence with `a3` is
339 // always different than starting one with either `a0` or
341 // After the insertion, the tree looks like the following:
347 tree.insert(Execution(), {a3, a0});
348 REQUIRE(tree.get_num_nodes() == 8);
349 test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
350 PartialExecution{a2, a3}, PartialExecution{a2, a5},
351 PartialExecution{a2}, PartialExecution{a3, a0},
352 PartialExecution{a3}, PartialExecution{}});