src/mc/api/ActorState.hpp

   1 /* Copyright (c) 2007-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_PATTERN_H
   7 #define SIMGRID_MC_PATTERN_H
   8
   9 #include "src/kernel/activity/CommImpl.hpp"
  10 #include "src/mc/remote/RemotePtr.hpp"
  11
  12 #include <algorithm>
  13 #include <exception>
  14 #include <vector>
  15
  16 namespace simgrid::mc {
  17
  18 /* On every state, each actor has an entry of the following type.
  19  * This usually represents both the actor and its transition because
  20  * most of the time an actor cannot have more than one enabled transition
  21  * at a given time. However, certain transitions have multiple "paths"
  22  * that can be followed, which means that a given actor may be able
  23  * to do more than one thing at a time.
  24  *
  25  * Formally, at this state multiple transitions would exist all of
  26  * which happened to be executed by the same actor. This distinction
  27  * is important in cases
  28  */
  29 class ActorState {
  30   /**
  31    * @brief The transitions that the actor is allowed to execute from this
  32    * state, viz. those that are enabled for this actor
  33    *
  34    * Most actors can take only a single action from any given state.
  35    * However, when an actor executes a transition with multiple
  36    * possible variations (e.g. an MC_Random() [see class: RandomTransition]
  37    * for more details]), multiple enabled actions are defined
  38    *
  39    * @invariant The transitions are arranged such that an actor
  40    * with multiple possible paths of execution will contain all
  41    * such transitions such that `pending_transitions_[i]` represents
  42    * the variation of the transition with `times_considered = i`.
  43    *
  44    * @note: If only a subset of transitions of an actor that can
  45    * take multiple transitions in some state are truly enabled,
  46    * we would instead need to map `times_considered` to a transition,
  47    * as the map is currently implicit in the ordering of the transitions
  48    * in the vector
  49    *
  50    * TODO: If a single transition is taken at a time in a concurrent system,
  51    * then nearly all of the transitions from in a state `s'` after taking
  52    * an action `t` from state `s`  (i.e. s -- t --> s') are the same
  53    * sans for the new transition of the actor which just executed t.
  54    * This means there may be a way to store the list once and apply differences
  55    * rather than repeating elements frequently.
  56    */
  57   std::vector<std::shared_ptr<Transition>> pending_transitions_;
  58
  59   /* Possible exploration status of an actor transition in a state.
  60    * Either the checker did not consider the transition, or it was considered and still to do, or considered and
  61    * done.
  62    */
  63   enum class InterleavingType {
  64     /** This actor transition is not considered by the checker (yet?) */
  65     disabled = 0,
  66     /** The checker algorithm decided that this actor transitions should be done at some point */
  67     todo,
  68     /** The checker algorithm decided that this should be done, but it was done in the meanwhile */
  69     done,
  70   };
  71
  72   /** Exploration control information */
  73   InterleavingType state_ = InterleavingType::disabled;
  74
  75   /** The ID of that actor */
  76   const aid_t aid_;
  77
  78   /** Number of times that the actor was considered to be executed in previous explorations of the state space */
  79   unsigned int times_considered_ = 0;
  80   /** Maximal amount of times that the actor can be considered for execution in this state.
  81    * If times_considered==max_consider, we fully explored that part of the state space */
  82   unsigned int max_consider_ = 0;
  83
  84   /** Whether that actor is initially enabled in this state */
  85   bool enabled_;
  86
  87 public:
  88   ActorState(aid_t aid, bool enabled, unsigned int max_consider) : ActorState(aid, enabled, max_consider, {}) {}
  89
  90   ActorState(aid_t aid, bool enabled, unsigned int max_consider, std::vector<std::shared_ptr<Transition>> transitions)
  91       : pending_transitions_(std::move(transitions)), aid_(aid), max_consider_(max_consider), enabled_(enabled)
  92   {
  93   }
  94
  95   unsigned int do_consider()
  96   {
  97     if (max_consider_ <= times_considered_ + 1)
  98       mark_done();
  99     return times_considered_++;
 100   }
 101   unsigned int get_max_considered() const { return max_consider_; }
 102   unsigned int get_times_considered() const { return times_considered_; }
 103   unsigned int get_times_not_considered() const { return max_consider_ - times_considered_; }
 104   bool has_more_to_consider() const { return get_times_not_considered() > 0; }
 105   aid_t get_aid() const { return aid_; }
 106
 107   /* returns whether the actor is marked as enabled in the application side */
 108   bool is_enabled() const { return enabled_; }
 109   /* returns whether the actor is marked as disabled by the exploration algorithm */
 110   bool is_disabled() const { return this->state_ == InterleavingType::disabled; }
 111   bool is_done() const { return this->state_ == InterleavingType::done; }
 112   bool is_todo() const { return this->state_ == InterleavingType::todo; }
 113   /** Mark that we should try executing this process at some point in the future of the checker algorithm */
 114   void mark_todo()
 115   {
 116     this->state_            = InterleavingType::todo;
 117     this->times_considered_ = 0;
 118   }
 119   void mark_done() { this->state_ = InterleavingType::done; }
 120
 121   /**
 122    * @brief Retrieves the transition that we should consider for execution by
 123    * this actor from the State instance with respect to which this ActorState object
 124    * is considered
 125    */
 126   std::shared_ptr<Transition> get_transition() const
 127   {
 128     // The rationale for this selection is as follows:
 129     //
 130     // 1. For transitions with only one possibility of execution,
 131     // we always wish to select action `0` even if we've
 132     // marked the transition already as considered (which
 133     // we'll do if we explore a trace following that transition).
 134     //
 135     // 2. For transitions that can be considered multiple
 136     // times, we want to be sure to select the most up-to-date
 137     // action. In general, this means selecting that which is
 138     // now being considered at this state. If, however, we've
 139     // executed the
 140     //
 141     // The formula satisfies both of the above conditions:
 142     //
 143     // > std::clamp(times_considered_, 0u, max_consider_ - 1)
 144     return get_transition(std::clamp(times_considered_, 0u, max_consider_ - 1));
 145   }
 146
 147   std::shared_ptr<Transition> get_transition(unsigned times_considered) const
 148   {
 149     xbt_assert(times_considered < this->pending_transitions_.size(),
 150                "Actor %ld does not have a state available transition with `times_considered = %u`,\n"
 151                "yet one was asked for",
 152                aid_, times_considered);
 153     return this->pending_transitions_[times_considered];
 154   }
 155
 156   void set_transition(std::shared_ptr<Transition> t, unsigned times_considered)
 157   {
 158     xbt_assert(times_considered < this->pending_transitions_.size(),
 159                "Actor %ld does not have a state available transition with `times_considered = %u`, "
 160                "yet one was attempted to be set",
 161                aid_, times_considered);
 162     this->pending_transitions_[times_considered] = std::move(t);
 163   }
 164
 165   const std::vector<std::shared_ptr<Transition>>& get_enabled_transitions() const
 166   {
 167     return this->pending_transitions_;
 168   };
 169 };
 170
 171 } // namespace simgrid::mc
 172
 173 #endif