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   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);
  24   }
  25   REQUIRE(num_nodes_traversed == tree.get_num_nodes());
  26 }
  27
  28 TEST_CASE("simgrid::mc::odpor::WakeupTree: Constructing Trees")
  29 {
  30   SECTION("Constructing empty trees")
  31   {
  32     WakeupTree tree;
  33     REQUIRE(tree.empty());
  34     REQUIRE(tree.get_num_entries() == 0);
  35     REQUIRE(tree.get_num_nodes() == 1);
  36     test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
  37   }
  38
  39   SECTION("Testing Subtree Rooting")
  40   {
  41     // Here, we make everything dependent. This will ensure that each unique sequence
  42     // inserted into the tree never "eventually looks like"
  43     const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
  44     const auto a1 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
  45     const auto a2 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
  46     const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 4);
  47     const auto a4 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 5);
  48     const auto a5 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 6);
  49
  50     Execution execution;
  51     execution.push_transition(a0);
  52     execution.push_transition(a1);
  53     execution.push_transition(a2);
  54     execution.push_transition(a3);
  55     execution.push_transition(a4);
  56     execution.push_transition(a5);
  57
  58     // The tree is as follows:
  59     //                  {}
  60     //               /     /
  61     //             a1       a4
  62     //           /    /       /
  63     //          a2    a3       a1
  64     //         /     /   /      /
  65     //        a3    a2   a5     a2
  66     //       /     /             /
  67     //      a4    a4             a3
  68     //
  69     // Recall that new nodes (in this case the one with
  70     // action `a2`) are added such that they are "greater than" (under
  71     // the tree's `<` relation) all those that exist under the given parent
  72     WakeupTree tree;
  73     tree.insert(Execution(), {a1, a2, a3, a4});
  74     tree.insert(Execution(), {a1, a3, a2, a4});
  75     tree.insert(Execution(), {a1, a3, a2, a4, a5});
  76     tree.insert(Execution(), {a1, a3, a5});
  77     tree.insert(Execution(), {a4, a2, a1, a3});
  78     REQUIRE(tree.get_num_nodes() == 13);
  79
  80     SECTION("Cloning a tree from the root produces the same tree")
  81     {
  82       // The root node is the last node
  83       auto tree_root = tree.begin();
  84       std::advance(tree_root, tree.get_num_nodes() - 1);
  85
  86       WakeupTree clone = WakeupTree::make_subtree_rooted_at(*tree_root);
  87       REQUIRE(clone.empty() == tree.empty());
  88       REQUIRE(clone.get_num_entries() == tree.get_num_entries());
  89       REQUIRE(clone.get_num_nodes() == tree.get_num_nodes());
  90
  91       auto tree_iter = tree.begin();
  92       for (auto clone_iter = clone.begin(); clone_iter != clone.end(); ++clone_iter, ++tree_iter) {
  93         REQUIRE(tree_iter != tree.end());
  94         REQUIRE((*tree_iter)->get_sequence() == (*clone_iter)->get_sequence());
  95       }
  96     }
  97
  98     SECTION("Cloning a subtree from a leaf gives an empty tree")
  99     {
 100       // Let's pick the first leaf
 101       WakeupTree clone = WakeupTree::make_subtree_rooted_at(*tree.begin());
 102       REQUIRE(clone.empty());
 103       REQUIRE(clone.get_num_entries() == 0);
 104       REQUIRE(clone.get_num_nodes() == 1);
 105     }
 106
 107     SECTION("Cloning a subtree from an interior node gives the subtree underneath")
 108     {
 109       // Here, we pick the second-to-last node in the
 110       // series, which is the right-most child of the root
 111       auto right_most = tree.begin();
 112       std::advance(right_most, tree.get_num_nodes() - 2);
 113
 114       WakeupTree clone = WakeupTree::make_subtree_rooted_at(*right_most);
 115       REQUIRE_FALSE(clone.empty());
 116       REQUIRE(clone.get_num_entries() == 3);
 117       REQUIRE(clone.get_num_nodes() == 4);
 118       // Importantly, note that action `a4` is not included in
 119       // any of the executions; for in the subtree `clone` `a4`
 120       // is now the root.
 121       test_tree_iterator(clone, std::vector<PartialExecution>{PartialExecution{a2, a1, a3}, PartialExecution{a2, a1},
 122                                                               PartialExecution{a2}, PartialExecution{}});
 123     }
 124   }
 125 }
 126
 127 TEST_CASE("simgrid::mc::odpor::WakeupTree: Testing Insertion for Empty Executions")
 128 {
 129   SECTION("Following an execution")
 130   {
 131     // We imagine the following completed execution `E`
 132     // consisting of executing actions a0-a3. Execution
 133     // `E` is the first such maximal execution explored
 134     // by ODPOR, which implies that a) all sleep sets are
 135     // empty and b) all wakeup trees (i.e. for each prefix) consist of the root
 136     // node with a single leaf containing the action
 137     // taken, save for the wakeup tree of the execution itself
 138     // which is empty.
 139
 140     // We first notice that there's a reversible race between
 141     // events 0 and 3.
 142
 143     const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 3);
 144     const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
 145     const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 1);
 146     const auto a3 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
 147
 148     Execution execution;
 149     execution.push_transition(a0);
 150     execution.push_transition(a1);
 151     execution.push_transition(a2);
 152     execution.push_transition(a3);
 153
 154     REQUIRE(execution.get_racing_events_of(2) == std::unordered_set<Execution::EventHandle>{0});
 155     REQUIRE(execution.get_racing_events_of(3) == std::unordered_set<Execution::EventHandle>{0});
 156
 157     WakeupTree tree;
 158
 159     SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
 160     {
 161       tree.insert(Execution(), {});
 162       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
 163     }
 164
 165     // First, we initialize the tree to how it looked prior
 166     // to the insertion of the race.
 167     tree.insert(Execution(), {a0});
 168
 169     // Then, after insertion, we ensure that the node was
 170     // indeed added to the tree.
 171     tree.insert(Execution(), {a1, a3});
 172     test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
 173                                                            PartialExecution{a1}, PartialExecution{}});
 174
 175     SECTION("Attempting to re-insert the same EXACT sequence should have no effect")
 176     {
 177       tree.insert(Execution(), {a1, a3});
 178       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
 179                                                              PartialExecution{a1}, PartialExecution{}});
 180     }
 181
 182     SECTION("Attempting to re-insert an equivalent sequence should have no effect")
 183     {
 184       // a3 and a1 are interchangeable since `a1` is independent with everything.
 185       // Since we found an equivalent sequence that is a leaf, nothing should result..
 186       tree.insert(Execution(), {a3, a1});
 187       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
 188                                                              PartialExecution{a1}, PartialExecution{}});
 189     }
 190
 191     SECTION("Attempting to insert the empty sequence should have no effect")
 192     {
 193       tree.insert(Execution(), {});
 194       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
 195                                                              PartialExecution{a1}, PartialExecution{}});
 196     }
 197
 198     SECTION("Inserting an extension should create a branch point")
 199     {
 200       // `a1.a2` shares the same `a1` prefix as `a1.a3`. Thus, the tree
 201       // should now look as follows:
 202       //
 203       //                 {}
 204       //               /    /
 205       //             a0     a1
 206       //                   /   /
 207       //                  a3   a2
 208       //
 209       // Recall that new nodes (in this case the one with
 210       // action `a2`) are added such that they are "greater than" (under
 211       // the tree's `<` relation) all those that exist under the given parent.
 212       tree.insert(Execution(), {a1, a2});
 213       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a1, a3},
 214                                                              PartialExecution{a1, a2}, PartialExecution{a1},
 215                                                              PartialExecution{}});
 216     }
 217   }
 218
 219   SECTION("Performing Arbitrary Insertions")
 220   {
 221     const auto a0 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 2);
 222     const auto a1 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 4);
 223     const auto a2 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 3);
 224     const auto a3 = std::make_shared<DependentAction>(Transition::Type::UNKNOWN, 1);
 225     const auto a4 = std::make_shared<IndependentAction>(Transition::Type::UNKNOWN, 2);
 226     const auto a5 = std::make_shared<ConditionallyDependentAction>(Transition::Type::UNKNOWN, 4);
 227
 228     Execution execution;
 229     execution.push_transition(a0);
 230     execution.push_transition(a1);
 231     execution.push_transition(a2);
 232     execution.push_transition(a3);
 233     execution.push_transition(a4);
 234     execution.push_transition(a5);
 235
 236     WakeupTree tree;
 237
 238     SECTION("Attempting to insert the empty sequence into an empty tree should have no effect")
 239     {
 240       tree.insert(Execution(), {});
 241       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{}});
 242     }
 243
 244     SECTION("Attempting to re-insert the same sequence multiple times should have no extra effect")
 245     {
 246       tree.insert(Execution(), {a4});
 247       tree.insert(Execution(), {a4});
 248       tree.insert(Execution(), {a4});
 249       REQUIRE(tree.get_num_nodes() == 2);
 250       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4}, PartialExecution{}});
 251     }
 252
 253     SECTION("Attempting to insert an independent sequence same should have no extra effect")
 254     {
 255       // a4 and a1 are independent actions. Intuitively, then, we need only
 256       // search one ordering of the two actions. The wakeup tree handles
 257       // this by computing the `~` relation. The relation itself determines
 258       // whether the `a1` is an initial of `a3`, which it is not. It then
 259       // checks whether `a1` is independent with everything in the sequence
 260       // (in this case, consisting only of `a1`) which IS true. Since `a4`
 261       // is already a leaf node of the tree, it suffices to only have `a4`
 262       // in this tree to guide ODPOR.
 263       tree.insert(Execution(), {a4});
 264       tree.insert(Execution(), {a1});
 265       REQUIRE(tree.get_num_nodes() == 2);
 266       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a4}, PartialExecution{}});
 267     }
 268
 269     SECTION(
 270         "Attempting to insert a progression of executions should have no extra effect when the first process is a leaf")
 271     {
 272       // All progressions starting with `a0` are effectively already accounted
 273       // for by inserting `a0` since we `a0` "can always be made to look like"
 274       // (viz. the `~` relation) `a0.*` where `*` is some sequence of actions
 275       tree.insert(Execution(), {a0});
 276       tree.insert(Execution(), {a0, a3});
 277       tree.insert(Execution(), {a0, a3, a2});
 278       tree.insert(Execution(), {a0, a3, a2, a4});
 279       tree.insert(Execution(), {a0, a3, a2, a4});
 280       REQUIRE(tree.get_num_nodes() == 2);
 281       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{}});
 282     }
 283
 284     SECTION("Stress test with multiple branch points: `~_E` with different looking sequences")
 285     {
 286       // After the insertions below, the tree looks like the following:
 287       //                {}
 288       //              /    /
 289       //            a0     a2
 290       //                 /  |   /
 291       //               a0  a3   a5
 292       tree.insert(Execution(), {a0});
 293       tree.insert(Execution(), {a2, a0});
 294       tree.insert(Execution(), {a2, a3});
 295       tree.insert(Execution(), {a2, a5});
 296       REQUIRE(tree.get_num_nodes() == 6);
 297       test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
 298                                                              PartialExecution{a2, a3}, PartialExecution{a2, a5},
 299                                                              PartialExecution{a2}, PartialExecution{}});
 300       SECTION("Adding more stress")
 301       {
 302         // In this case, `a2` and `a1` can be interchanged with each other.
 303         // Thus `a2.a1 == a1.a2`. Since there is already an interior node
 304         // containing `a2`, we attempt to add the what remains (viz. `a1`) to the
 305         // series. HOWEVER: we notice that `a2.a5` is "eventually equivalent to"
 306         // (that is `~` with) `a1.a2` since `a2` is an initial of the latter and
 307         // `a1` and `a5` are independent of each other.
 308         tree.insert(Execution(), {a1, a2});
 309         REQUIRE(tree.get_num_nodes() == 6);
 310         test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
 311                                                                PartialExecution{a2, a3}, PartialExecution{a2, a5},
 312                                                                PartialExecution{a2}, PartialExecution{}});
 313
 314         // With a3.a0, we notice that starting a sequence with `a3` is
 315         // always different than starting one with either `a0` or
 316         //
 317         // After the insertion, the tree looks like the following:
 318         //                     {}
 319         //              /     /        /
 320         //            a0     a2        a3
 321         //                 /  |  /     |
 322         //               a0  a3  a5    a0
 323         tree.insert(Execution(), {a3, a0});
 324         REQUIRE(tree.get_num_nodes() == 8);
 325         test_tree_iterator(tree, std::vector<PartialExecution>{PartialExecution{a0}, PartialExecution{a2, a0},
 326                                                                PartialExecution{a2, a3}, PartialExecution{a2, a5},
 327                                                                PartialExecution{a2}, PartialExecution{a3, a0},
 328                                                                PartialExecution{a3}, PartialExecution{}});
 329       }
 330     }
 331   }
 332 }