boosting_vote_aggregator.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407
  1. // Copyright 2019 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_PERFORMANCE_MANAGER_EXECUTION_CONTEXT_PRIORITY_BOOSTING_VOTE_AGGREGATOR_H_
  5. #define COMPONENTS_PERFORMANCE_MANAGER_EXECUTION_CONTEXT_PRIORITY_BOOSTING_VOTE_AGGREGATOR_H_
  6. #include <map>
  7. #include <set>
  8. #include "base/memory/raw_ptr.h"
  9. #include "base/task/task_traits.h"
  10. #include "components/performance_manager/public/execution_context_priority/execution_context_priority.h"
  11. #include "third_party/abseil-cpp/absl/types/optional.h"
  12. namespace performance_manager {
  13. namespace execution_context_priority {
  14. class BoostingVoteAggregator;
  15. // A BoostingVote is a special kind of relative vote that allows a voter to
  16. // express that "execution context X should have the same or greater priority
  17. // than execution context Y". It allows implementing priority boost semantics to
  18. // avoid priority inversions for access to shared resources. BoostingVotes must
  19. // be registered with a BoostingVoteAggregator. Similar to a VoteReceipt, they
  20. // are a move-only type and their vote will be removed with their destruction.
  21. //
  22. // A BoostingVote is considered "active" if it is associated with an aggregator
  23. // (the result of calling "aggregator()" is non-null).
  24. //
  25. // See comments in the implementation for details on how the algorithm works.
  26. class BoostingVote {
  27. public:
  28. // Registers a relative vote with the provided |aggregator|, that ensures that
  29. // the priority of |output_execution_context| will be at least as high as that
  30. // of |input_execution_context|.
  31. BoostingVote(BoostingVoteAggregator* aggregator,
  32. const ExecutionContext* input_execution_context,
  33. const ExecutionContext* output_execution_context,
  34. const char* reason);
  35. BoostingVote(const BoostingVote& rhs) = delete;
  36. BoostingVote(BoostingVote&& rhs);
  37. BoostingVote& operator=(const BoostingVote& rhs) = delete;
  38. BoostingVote& operator=(BoostingVote&& rhs);
  39. ~BoostingVote();
  40. BoostingVoteAggregator* aggregator() const { return aggregator_; }
  41. const ExecutionContext* input_execution_context() const {
  42. return input_execution_context_;
  43. }
  44. const ExecutionContext* output_execution_context() const {
  45. return output_execution_context_;
  46. }
  47. const char* reason() const { return reason_; }
  48. // Detaches this BoostingVote from its aggregator. After calling this
  49. // |aggregator_| will be nullptr and the vote will no longer be active.
  50. void Reset();
  51. private:
  52. raw_ptr<BoostingVoteAggregator> aggregator_ = nullptr;
  53. raw_ptr<const ExecutionContext> input_execution_context_ = nullptr;
  54. raw_ptr<const ExecutionContext> output_execution_context_ = nullptr;
  55. const char* reason_ = nullptr;
  56. };
  57. // The BoostingVoteAggregator allows for incoming votes to be modified via a
  58. // collection of registered "relative boosting votes" that express relationships
  59. // such as "execution context X should have the same or greater priority than
  60. // execution context Y". It is intended to serve as the root of a tree of voters
  61. // and aggregators, allowing priority boost semantics to be implemented. This
  62. // class must outlive all boosting votes registered with it.
  63. class BoostingVoteAggregator : public VoteObserver {
  64. public:
  65. BoostingVoteAggregator();
  66. BoostingVoteAggregator(const BoostingVoteAggregator&) = delete;
  67. BoostingVoteAggregator& operator=(const BoostingVoteAggregator&) = delete;
  68. ~BoostingVoteAggregator() override;
  69. // Both of these must be called in order for the aggregator to be setup
  70. // ("IsSetup" will return true). Both of these should be called exactly once.
  71. VotingChannel GetVotingChannel();
  72. void SetUpstreamVotingChannel(VotingChannel channel);
  73. bool IsSetup() const;
  74. protected:
  75. friend class BoostingVote;
  76. // We currently require that base::TaskPriority be zero-based, and
  77. // consecutive. These static asserts ensure that we revisit this code if the
  78. // base::TaskPriority enum ever changes.
  79. static_assert(static_cast<int>(base::TaskPriority::LOWEST) == 0,
  80. "expect 0-based priorities");
  81. static_assert(static_cast<int>(base::TaskPriority::HIGHEST) == 2,
  82. "expect 3 priority levels");
  83. using NodePriorityMap = std::map<const ExecutionContext*, base::TaskPriority>;
  84. // Small helper class used to endow both edges and nodes with "active" bits
  85. // for each priority layer.
  86. class ActiveLayers {
  87. public:
  88. // Returns true if any layer is active.
  89. bool IsActiveInAnyLayer() const { return active_layers_ != 0; }
  90. // Returns the "active" state of this node for the given |layer_bit|.
  91. bool IsActive(uint32_t layer_bit) const;
  92. // Sets the active state for this node in the given |layer_bit|.
  93. void SetActive(uint32_t layer_bit);
  94. void SetInactive(uint32_t layer_bit);
  95. private:
  96. // A bit-set corresponding to the priority layers in which this object is
  97. // active.
  98. uint32_t active_layers_ = 0;
  99. };
  100. // This is move-only because all of its members are move-only.
  101. // An instance of this will exist for any node that is referenced, either by a
  102. // direct Vote for that node, or as an input or output of a BoostedVote.
  103. class NodeData : public ActiveLayers {
  104. public:
  105. NodeData();
  106. NodeData(const NodeData& rhs) = delete;
  107. NodeData(NodeData&& rhs);
  108. NodeData& operator=(const NodeData& rhs) = delete;
  109. NodeData& operator=(NodeData&& rhs) = default;
  110. ~NodeData();
  111. const Vote& incoming_vote() const { return incoming_vote_.value(); }
  112. // Sets/Cancels the incoming vote.
  113. void SetIncomingVote(const Vote& incoming_vote) {
  114. DCHECK(!incoming_vote_.has_value());
  115. incoming_vote_ = incoming_vote;
  116. }
  117. void RemoveIncomingVote() {
  118. DCHECK(incoming_vote_.has_value());
  119. incoming_vote_ = absl::nullopt;
  120. }
  121. // Updates the incoming vote.
  122. void UpdateIncomingVote(const Vote& incoming_vote) {
  123. DCHECK(incoming_vote_.has_value());
  124. incoming_vote_ = incoming_vote;
  125. }
  126. // Sets/Cancels the outgoing vote.
  127. void SetOutgoingVote(const Vote& outgoing_vote) {
  128. DCHECK(!outgoing_vote_.has_value());
  129. outgoing_vote_ = outgoing_vote;
  130. }
  131. void CancelOutgoingVote() {
  132. DCHECK(outgoing_vote_.has_value());
  133. outgoing_vote_ = absl::nullopt;
  134. }
  135. // Updates the outgoing vote. Returns true if it changed.
  136. bool UpdateOutgoingVote(const Vote& outgoing_vote) {
  137. DCHECK(outgoing_vote_.has_value());
  138. if (outgoing_vote == outgoing_vote_.value())
  139. return false;
  140. outgoing_vote_ = outgoing_vote;
  141. return true;
  142. }
  143. // Returns true if this node has an active |incoming| vote. If false that
  144. // means this node exists only because it is referenced by a BoostedVote.
  145. // Same as |incoming_vote_.has_value()|, but more readable.
  146. bool HasIncomingVote() const { return incoming_vote_.has_value(); }
  147. // Returns true if this node has an active outgoing vote.
  148. bool HasOutgoingVote() const { return outgoing_vote_.has_value(); }
  149. // Returns true if this node is involved in any edges.
  150. bool HasEdges() const { return edge_count_ > 0; }
  151. // Returns the effective priority of this node based on the highest of the
  152. // values in |supporting_node_count_|.
  153. base::TaskPriority GetEffectivePriorityLevel() const;
  154. // For keeping track of the number of edges in which this node is involved.
  155. void IncrementEdgeCount();
  156. void DecrementEdgeCount();
  157. size_t edge_count_for_testing() const { return edge_count_; }
  158. private:
  159. // Counts the number of edges involving this node, both input and output.
  160. // When this goes to zero the node no longer needs an explicit
  161. // representation.
  162. size_t edge_count_ = 0;
  163. // The input vote we've received, if any.
  164. absl::optional<Vote> incoming_vote_;
  165. // The output vote we're emitted, if any.
  166. absl::optional<Vote> outgoing_vote_;
  167. };
  168. // NOTE: It is important that NodeDataMap preserve pointers to NodeData
  169. // through insertions and deletions in the map, as we take raw pointers to
  170. // objects in the map.
  171. using NodeDataMap = std::map<const ExecutionContext*, NodeData>;
  172. using NodeDataPtrSet = std::set<NodeDataMap::value_type*>;
  173. // For any given edge, this maintains the metadata associated with that
  174. // particular edge.
  175. class EdgeData : public ActiveLayers {
  176. public:
  177. EdgeData();
  178. EdgeData(const EdgeData&) = delete;
  179. EdgeData(EdgeData&&);
  180. EdgeData& operator=(const EdgeData&) = delete;
  181. EdgeData& operator=(EdgeData&&);
  182. ~EdgeData();
  183. // Adds a reason to the set of reasons associated with this edge.
  184. void AddReason(const char* reason);
  185. // Removes a reason from this edge. Returns true if this was the active
  186. // selected reason that had been forwarded, indicating that a new reason
  187. // needs to be chosen.
  188. bool RemoveReason(const char* reason);
  189. // Returns the active reason for this edge.
  190. const char* GetActiveReason() const;
  191. // Returns the total number of reasons associated with this edge. This is
  192. // effectively the multiplicity of the edge in the dependency graph.
  193. size_t GetReasonCount() const { return reasons_.size(); }
  194. private:
  195. // The reasons associated with this particular edge (one contribution per
  196. // BoostingVote). We really don't expect many multiple edges so a vector is
  197. // used to reduce allocations. This is semantically a multi-set.
  198. std::vector<const char*> reasons_;
  199. };
  200. // A helper for storing edges with different sort orders. Templated so that it
  201. // is strongly typed.
  202. template <bool kForward>
  203. class Edge {
  204. public:
  205. Edge(const ExecutionContext* src, const ExecutionContext* dst)
  206. : src_(src), dst_(dst) {}
  207. explicit Edge(const BoostingVote* boosting_vote)
  208. : src_(boosting_vote->input_execution_context()),
  209. dst_(boosting_vote->output_execution_context()) {}
  210. Edge(const Edge&) = default;
  211. ~Edge() {}
  212. Edge& operator=(const Edge&) = default;
  213. Edge& operator=(Edge&&) = delete;
  214. bool operator==(const Edge& rhs) const {
  215. return std::tie(src_, dst_) == std::tie(rhs.src_, rhs.dst_);
  216. }
  217. bool operator!=(const Edge& rhs) const { return !(*this == rhs); }
  218. // Forward edges sort by (src, dst), while reverse edges sort by (dst, src).
  219. bool operator<(const Edge& rhs) const {
  220. if (kForward)
  221. return std::tie(src_, dst_) < std::tie(rhs.src_, rhs.dst_);
  222. return std::tie(dst_, src_) < std::tie(rhs.dst_, rhs.src_);
  223. }
  224. const ExecutionContext* src() const { return src_; }
  225. const ExecutionContext* dst() const { return dst_; }
  226. private:
  227. // TODO(crbug.com/1298696): Breaks component_unittests.
  228. raw_ptr<const ExecutionContext, DegradeToNoOpWhenMTE> src_ = nullptr;
  229. raw_ptr<const ExecutionContext, DegradeToNoOpWhenMTE> dst_ = nullptr;
  230. };
  231. using ForwardEdge = Edge<true>;
  232. using ReverseEdge = Edge<false>;
  233. // EdgeData is stored in the forward map, and a pointer to that data is
  234. // included in the reverse edge map.
  235. using ForwardEdges = std::map<ForwardEdge, EdgeData>;
  236. using ReverseEdges = std::map<ReverseEdge, EdgeData*>;
  237. // To be called by BoostingVote.
  238. void SubmitBoostingVote(const BoostingVote* boosting_vote);
  239. void CancelBoostingVote(const BoostingVote* boosting_vote);
  240. // VoteObserver implementation:
  241. void OnVoteSubmitted(VoterId voter_id,
  242. const ExecutionContext* execution_context,
  243. const Vote& vote) override;
  244. void OnVoteChanged(VoterId voter_id,
  245. const ExecutionContext* execution_context,
  246. const Vote& new_vote) override;
  247. void OnVoteInvalidated(VoterId voter_id,
  248. const ExecutionContext* execution_context) override;
  249. // Helper functions for enumerating over incoming and outgoing edges.
  250. // |function| should accept a single input parameter that is a
  251. // ForwardEdge::iterator or ReverseEdge::iterator, as appropriate, and which
  252. // returns a bool. Returning true indicates the iteration should continue,
  253. // returning false indicates it should terminate.
  254. template <typename Function>
  255. void ForEachIncomingEdge(const ExecutionContext* node, Function&& function);
  256. template <typename Function>
  257. void ForEachOutgoingEdge(const ExecutionContext* node, Function&& function);
  258. // Finds or creates the node data associated with the given node.
  259. NodeDataMap::iterator FindOrCreateNodeData(const ExecutionContext* node);
  260. NodeDataMap::iterator FindNodeData(const ExecutionContext* node);
  261. // Returns the vote reason that should be associated with the given
  262. // node. This will preferentially select the reason that comes with a direct
  263. // vote if any is present; otherwise, it will select the active reason of the
  264. // active edge that causes the node itself to be active. Complexity is
  265. // O(|inbound edge count| + lg |total edge count|). This can return nullptr if
  266. // no non-null reasons have been provided.
  267. const char* GetVoteReason(const NodeDataMap::value_type* node_data_value);
  268. // Upstreams the vote for this |node| via its associated NodeData.
  269. void UpstreamVoteIfNeeded(NodeDataMap::value_type* node_data_value);
  270. // Upstreams changes that have been made to the provided set of nodes. This
  271. // takes care of deleted nodes if they no longer need to be represented in
  272. // the priority flow graph.
  273. void UpstreamChanges(const NodeDataPtrSet& changes);
  274. // Helper for removing a node from the NodeDataMap.
  275. void MaybeRemoveNode(NodeDataMap::iterator node_data_it);
  276. // Marks sub-tree rooted at |node| as inactive, and returns the nodes that
  277. // were deactivated in the provided output set.
  278. void MarkSubtreeInactive(uint32_t layer_bit,
  279. NodeDataMap::value_type* node,
  280. NodeDataPtrSet* deactivated);
  281. // Determines if the given node has an inbound active edge, returning an
  282. // iterator to it if there is one.
  283. ReverseEdges::iterator GetActiveInboundEdge(
  284. uint32_t layer_bit,
  285. const NodeDataMap::value_type* node);
  286. // Gets the nearest active ancestor of a given deactivated node. Returns
  287. // nullptr if there is none.
  288. NodeDataMap::value_type* GetNearestActiveAncestor(
  289. uint32_t layer_bit,
  290. const NodeDataMap::value_type* deactivated_node);
  291. // Given a set of inactive nodes, returns a search front corresponding to
  292. // all of their nearest active ancestors.
  293. void GetNearestActiveAncestors(uint32_t layer_bit,
  294. const NodeDataPtrSet& deactivated,
  295. NodeDataPtrSet* active_ancestors);
  296. // Given a search front of active nodes, explores outwards from those nodes
  297. // in order to generate a reachability spanning tree. Empties the
  298. // |active_search_front| as the search progresses, and populates |changes|
  299. // with the set of nodes that were made active as a result of the search.
  300. void MarkNodesActiveFromSearchFront(uint32_t layer_bit,
  301. NodeDataPtrSet* active_search_front,
  302. NodeDataPtrSet* activated);
  303. // Reprocesses the subtree rooted at the provided |node|. This is used to
  304. // repair the reachability spanning tree when the active edge inbound to
  305. // |node| is deleted. The set of nodes that have seen an active state toggle
  306. // or a change in vote reason are stored in |changes|, for use with
  307. // "UpstreamChanges".
  308. void ReprocessSubtree(uint32_t layer_bit,
  309. NodeDataMap::value_type* node,
  310. NodeDataPtrSet* changes);
  311. // Used by SubmitVote/ChangeVote and VoteInvalidated.
  312. void OnVoteAdded(uint32_t layer_bit,
  313. NodeDataMap::value_type* node,
  314. NodeDataPtrSet* changes);
  315. void OnVoteRemoved(uint32_t layer_bit,
  316. NodeDataMap::value_type* node,
  317. NodeDataPtrSet* changes);
  318. // Our input voter. We'll only accept votes from this voter otherwise we'll
  319. // DCHECK.
  320. voting::VoterId<Vote> input_voter_id_;
  321. // Our channel for upstreaming our votes.
  322. VotingChannel channel_;
  323. // Provides a VotingChannel to our input voter.
  324. VotingChannelFactory voting_channel_factory_{this};
  325. // Nodes and associated metadata in the "priority flow graph". An entry exists
  326. // in this map for any node that has an active non-default vote, or for any
  327. // node that is referenced by the "priority flow graph".
  328. NodeDataMap nodes_;
  329. // The collection of know BoostingVotes, describing the edges in the
  330. // "priority flow graph" as adjacency lists. Nodes are stored as instances of
  331. // NodeData.
  332. ForwardEdges forward_edges_;
  333. ReverseEdges reverse_edges_;
  334. };
  335. } // namespace execution_context_priority
  336. } // namespace performance_manager
  337. #endif // COMPONENTS_PERFORMANCE_MANAGER_EXECUTION_CONTEXT_PRIORITY_BOOSTING_VOTE_AGGREGATOR_H_