src/mc/explo/odpor/WakeupTree_test.cpp

   1 /* Copyright (c) 2017-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 #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"
  11
  12 using namespace simgrid::mc;
  13 using namespace simgrid::mc::odpor;
  14 using namespace simgrid::mc::udpor;
  15
  16 static void test_tree_iterator(const WakeupTree& tree, const std::vector<PartialExecution>& expected)
  17 {
  18   auto tree_iter = tree.begin();
  19   for (auto expected_iter = expected.begin(); expected_iter != expected.end(); ++expected_iter, ++tree_iter) {
  20     REQUIRE(tree_iter != tree.end());
  21     REQUIRE((*tree_iter)->get_sequence() == *expected_iter);
  22   }
  23 }
  24
  25 TEST_CASE("simgrid::mc::odpor::WakeupTree: Testing Insertion for Empty Executions")
  26 {
  27   SECTION("Following an execution")
  28   {
  29     // We imagine the following completed execution `E`
  30     // consisting of executing actions a0-a3. Execution
  31     // `E` cis the first such maximal execution explored
  32     // by ODPOR, which implies that a) all sleep sets are
  33     // empty and b) all wakeup trees (i.e. for each prefix) consist of the root
  34     // node with a single leaf containing the action
  35     // taken, save for the wakeup tree of the execution itself
  36     // which is empty
  37
  38     // We first notice that there's a reversible race between
  39     // events 0 and 3.
  40
  41     const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
  42     const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
  43     const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
  44     const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
  45
  46     Execution execution;
  47     execution.push_transition(a0);
  48     execution.push_transition(a1);
  49     execution.push_transition(a2);
  50     execution.push_transition(a3);
  51
  52     REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
  53     REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
  54
  55     WakeupTree tree;
  56
  57     SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
  58     {
  59       tree.insert(Execution(), {});
  60       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
  61     }
  62
  63     // First, we initialize the tree to how it looked prior
  64     // to the insertion of the race
  65     tree.insert(Execution(), {a0});
  66
  67     // Then, after insertion, we ensure that the node was
  68     // indeed added to the tree
  69     tree.insert(Execution(), {a1, a3});
  70     test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
  71                                                            PartialExecution{a1}, PartialExecution{}});
  72
  73     SECTION("Attempting to re-insert the same EXACT sequence should have no effect")
  74     {
  75       tree.insert(Execution(), {a1, a3});
  76       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
  77                                                              PartialExecution{a1}, PartialExecution{}});
  78     }
  79
  80     SECTION("Attempting to re-insert an equivalent sequence should have no effect")
  81     {
  82       // a3 and a1 are interchangeable since `a1` is independent with everything.
  83       // Since we found an equivalent sequence that is a leaf, nothing should result
  84       tree.insert(Execution(), {a3, a1});
  85       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
  86                                                              PartialExecution{a1}, PartialExecution{}});
  87     }
  88
  89     SECTION("Attempting to insert the empty sequence should have no effect")
  90     {
  91       tree.insert(Execution(), {});
  92       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
  93                                                              PartialExecution{a1}, PartialExecution{}});
  94     }
  95
  96     SECTION("Inserting an extension should create a branch point")
  97     {
  98       // `a1.a2` shares the same `a1` prefix as `a1.a3`. Thus, the tree
  99       // should now look as follows:
 100       //
 101       //                 {}
 102       //               /    /
 103       //             a0     a1
 104       //                   /   /
 105       //                  a3   a2
 106       //
 107       // Recall that new nodes (in this case the one with
 108       // action `a2`) are added such that they are "greater than" (under
 109       // the tree's `<` relation) all those that exist under the given parent
 110       tree.insert(Execution(), {a1, a2});
 111       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
 112                                                              PartialExecution{a1, a2}, PartialExecution{a1},
 113                                                              PartialExecution{}});
 114     }
 115   }
 116
 117   SECTION("Performing Arbitrary Insertions")
 118   {
 119     const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
 120     const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
 121     const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 3);
 122     const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
 123     const auto a4 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
 124     const auto a5 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
 125
 126     Execution execution;
 127     execution.push_transition(a0);
 128     execution.push_transition(a1);
 129     execution.push_transition(a2);
 130     execution.push_transition(a3);
 131     execution.push_transition(a4);
 132     execution.push_transition(a5);
 133
 134     WakeupTree tree;
 135
 136     SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
 137     {
 138       tree.insert(Execution(), {});
 139       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
 140     }
 141
 142     SECTION("Attempting to re-insert the same sequence multiple times should have no extra effect")
 143     {
 144       tree.insert(Execution(), {a4});
 145       tree.insert(Execution(), {a4});
 146       tree.insert(Execution(), {a4});
 147       REQUIRE(tree.get_num_nodes() == 2);
 148       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4}, PartialExecution{}});
 149     }
 150
 151     SECTION("Attempting to insert an independent sequence same should have no extra effect")
 152     {
 153       // a4 and a1 are independent actions. Intuitively, then, we need only
 154       // search one ordering of the two actions. The wakeup tree handles
 155       // this by computing the `~` relation. The relation itself determines
 156       // whether the `a1` is an initial of `a3`, which it is not. It then
 157       // checks whether `a1` is independent with everything in the sequence
 158       // (in this case, consisting only of `a1`) which IS true. Since `a4`
 159       // is already a leaf node of the tree, it suffices to only have `a4`
 160       // in this tree to guide ODPOR
 161       tree.insert(Execution(), {a4});
 162       tree.insert(Execution(), {a1});
 163       REQUIRE(tree.get_num_nodes() == 2);
 164       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4}, PartialExecution{}});
 165     }
 166
 167     SECTION(
 168         "Attempting to insert a progression of executions should have no extra effect when the first process is a leaf")
 169     {
 170       // All progressions starting with `a0` are effectively already accounted
 171       // for by inserting `a0` since we `a0` "can always be made to look like"
 172       // (viz. the `~` relation) `a0.*` where `*` is some sequence of actions
 173       tree.insert(Execution(), {a0});
 174       tree.insert(Execution(), {a0, a3});
 175       tree.insert(Execution(), {a0, a3, a2});
 176       tree.insert(Execution(), {a0, a3, a2, a4});
 177       tree.insert(Execution(), {a0, a3, a2, a4});
 178       REQUIRE(tree.get_num_nodes() == 2);
 179       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{}});
 180     }
 181
 182     SECTION("Stress test with multiple branch points")
 183     {
 184       tree.insert(Execution(), {a0});
 185       tree.insert(Execution(), {a2, a0});
 186       tree.insert(Execution(), {a2, a3});
 187       tree.insert(Execution(), {a2, a5});
 188       REQUIRE(tree.get_num_nodes() == 6);
 189       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
 190                                                              PartialExecution{a2, a3}, PartialExecution{a2, a5},
 191                                                              PartialExecution{a2}, PartialExecution{}});
 192     }
 193   }
 194 }
 195
 196 TEST_CASE("simgrid::mc::odpor::WakeupTree: Testing Subtree Rooting")
 197 {
 198   const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
 199   const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
 200   const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
 201   const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
 202   const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
 203   const auto a5 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
 204
 205   Execution execution;
 206   execution.push_transition(a0);
 207   execution.push_transition(a1);
 208   execution.push_transition(a2);
 209   execution.push_transition(a3);
 210
 211   REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
 212   REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
 213
 214   // The wakeup tree should
 215
 216   WakeupTree tree;
 217 }