src/mc/api/ClockVector.hpp

   1 /* Copyright (c) 2016-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 #ifndef SIMGRID_MC_CLOCK_VECTOR_HPP
   7 #define SIMGRID_MC_CLOCK_VECTOR_HPP
   8
   9 #include "simgrid/forward.h"
  10
  11 #include <cstdint>
  12 #include <initializer_list>
  13 #include <optional>
  14 #include <unordered_map>
  15
  16 namespace simgrid::mc {
  17
  18 /**
  19  * @brief A multi-dimensional vector used to keep track of
  20  * happens-before relation between dependent events in an
  21  * execution of DPOR, SDPOR, or ODPOR
  22  *
  23  * Clock vectors permit actors in a distributed system
  24  * to determine whether two events occurred one after the other
  25  * but they may not have); i.e. they permit actors to keep track of "time".
  26  * A clever observation made in the original DPOR paper is that a
  27  * transition-based "happens-before" relation can be computed for
  28  * any particular trace `S` using clock vectors, effectively
  29  * treating dependency like the passing of a message (the context
  30  * in which vector clocks are typically used).
  31  *
  32  * Support, however, needs to be added to clock vectors since
  33  * SimGrid permits the *creation* of new actors during execution.
  34  * Since we don't know this size before-hand, we have to allow
  35  * clock vectors to behave as if they were "infinitely" large. To
  36  * do so, all newly mapped elements, if not assigned a value, are
  37  * defaulted to `0`. This corresponds to the value this actor would
  38  * have had regardless had its creation been known to have evnetually
  39  * occurred: no actions taken by that actor had occurred prior, so
  40  * there's no way the clock vector would have been updated. In other
  41  * words, when comparing clock vectors of different sizes, it's equivalent
  42  * to imagine both of the same size with elements absent in one or
  43  * the other implicitly mapped to zero.
  44  */
  45 struct ClockVector final {
  46 private:
  47   std::unordered_map<aid_t, uint32_t> contents;
  48
  49 public:
  50   ClockVector()                              = default;
  51   ClockVector(const ClockVector&)            = default;
  52   ClockVector& operator=(ClockVector const&) = default;
  53   ClockVector(ClockVector&&)                 = default;
  54   ClockVector(std::initializer_list<std::pair<const aid_t, uint32_t>> init) : contents(std::move(init)) {}
  55
  56   /**
  57    * @brief The number of components in this
  58    * clock vector
  59    *
  60    * A `ClockVector` implicitly maps the id of an actor
  61    * it does not contain to a default value of `0`.
  62    * Thus, a `ClockVector` is "lazy" in the sense
  63    * that new actors are "automatically" mapped
  64    * without needing to be explicitly added the clock
  65    * vector when the actor is created. This means that
  66    * comparison between clock vectors is possible
  67    * even as actors become enabled and disabled
  68    *
  69    * @return uint32_t the number of elements in
  70    * the clock vector
  71    */
  72   size_t size() const { return this->contents.size(); }
  73
  74   uint32_t& operator[](aid_t aid)
  75   {
  76     // NOTE: The `operator[]` overload of
  77     // unordered_map will create a new key-value
  78     // pair if `tid` does not exist and will use
  79     // a _default_ value for the value (0 in this case)
  80     // which is precisely what we want here
  81     return this->contents[aid];
  82   }
  83
  84   /**
  85    * @brief Retrieves the value mapped to the given
  86    * actor if it is contained in this clock vector
  87    */
  88   std::optional<uint32_t> get(aid_t aid) const
  89   {
  90     if (const auto iter = this->contents.find(aid); iter != this->contents.end())
  91       return std::optional<uint32_t>{iter->second};
  92     return std::nullopt;
  93   }
  94
  95   /**
  96    * @brief Computes a clock vector whose components
  97    * are larger than the components of both of
  98    * the given clock vectors
  99    *
 100    * The maximum of two clock vectors is definied to
 101    * be the clock vector whose components are the maxmimum
 102    * of the corresponding components of the arguments.
 103    * Since the `ClockVector` class is "lazy", the two
 104    * clock vectors given as arguments may not be of the same size.
 105    * The resultant clock vector has components as follows:
 106    *
 107    * 1. For each actor that each clock vector maps, the
 108    * resulting clock vector maps that thread to the maxmimum
 109    * of the values mapped for the actor in each clock vector
 110    *
 111    * 2. For each actor that only a single clock vector maps,
 112    * the resulting clock vector maps that thread to the
 113    * value mapped by the lone clock vector
 114    *
 115    * The scheme is equivalent to assuming that an unmapped
 116    * thread by any one clock vector is implicitly mapped to zero
 117    *
 118    * @param cv1 the first clock vector
 119    * @param cv2  the second clock vector
 120    * @return a clock vector whose components are at
 121    * least as large as the corresponding components of each clock
 122    * vector and whose size is large enough to contain the union
 123    * of components of each clock vector
 124    */
 125   static ClockVector max(const ClockVector& cv1, const ClockVector& cv2);
 126 };
 127
 128 } // namespace simgrid::mc
 129
 130 #endif