boosting_vote_aggregator.cc | Explore in Territory

// Copyright 2019 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/performance_manager/execution_context_priority/boosting_vote_aggregator.h"

#include <algorithm>
#include <deque>
#include <tuple>
#include <utility>

#include "base/not_fatal_until.h"
#include "components/performance_manager/public/execution_context/execution_context.h"

// This voter allows expressing "priority boosts" which are used to resolve
// priority inversions. These priority inversions are a result of resource
// contention. For example, consider execution contexts ec0 and ec1, where ec0
// holds a WebLock and ec1 is waiting to acquire that WebLock. If the priority
// of ec0 is below that of execution context ec1 then its priority needs to be
// boosted in order to prevent a priority inversion.
//
// We represent this resource contention relationship with a directed edge from
// ec1 -> ec0, which expresses the fact that ec1 is waiting on a resource held
// by ec0. We instrument APIs that provide shared access to resources (WebLocks,
// IndexedDB, etc) and they serve as factories of edges, expressing their "wait
// lists" to the BoostingVoteAggregator. This graph will in general be quite
// sparse and consist of directed acyclic components (one per shared resource),
// but in theory it may be fully connected and cyclic. (A cycle in the graph
// effectively indicates web content that has expressed a dead lock, so while
// possible it is unlikely.)
//
// Nodes in the graph represent execution contexts, which themselves have
// baseline priorities that are calculated based on a variety of factors
// (visibility, type of content, ...). These priorities flow along edges if the
// next node has a lower priority, "boosting" the priority of the destination
// node in order to resolve priority inversions. Since the graph is finite and
// the flow is in one direction only this process is guaranteed to converge for
// any given graph and set of baseline priorities. We call this graph the
// "priority flow graph".
//
// We break this down into a separate graph problem per priority level. We
// define a virtual "source" node, and create directed edges from that source
// node to each node that has received an explicit vote. Finding the set of all
// nodes that are supported at that priority level then becomes one of
// reachability from a single source node, which is trivially O(|edges|) using
// a depth-first search.
//
// We wish to maintain this graph in the face of edge additions and removals
// (both direct priority votes and priority boosts are expressed as edges in
// this representation). To make this simpler we actually maintain a
// reachability spanning tree. That is, every reachable node has exactly one
// "active" (part of the spanning tree) incoming edge. The tree can be
// maintained as follows:
//
// Adding an edge:
//
// - Add the edge to the graph and mark it as inactive.
// - If the destination node is already active, we're done.
// - If the source node is inactive (and so is the destination node at this
//   point), then there is no possible path to the node, thus we're done.
// - At this point the source node is active, and the destination is inactive.
//   We mark the edge and the destination node as active, and recursively
//   investigate outbound edges to see if other nodes are now reachable. Since
//   edges are only ever marked active if they are from an active node to an
//   inactive node, this can occur once per node, thus each active node has
//   exactly one incoming edge, and the entire set of active edges and nodes
//   forms a directed tree.
//
// Removing an edge:
//
// - If the edge is inactive, simply remove it and return.
// - If the edge is active, then recurse on the subtree hanging off the
//   destination node, marking all of the associated edges and nodes as
//   inactive, while simultaneously maintaining a set of the nodes that have
//   been marked as inactive.
//   - For each node that was just marked inactive, traverse inactive back-edges
//     and find an active ancestor node if possible. Collect these active
//     ancestors as part of a search front.
//   - Launch a search from the search front, extending the tree of active nodes
//     by traversing inactive edges and marking them and the destination node as
//     active.
// - The 2-pass approach of first marking the subtree as inactive and *then*
//   extending the tree is necessary. If these 2 steps were mingled, then when
//   traversing the subtree and inspecting a node it would be possible to
//   identify an inactive edge from an ancestor that is actually a descendant
//   of the current node. The first pass serves to effectively split the tree
//   into ancestors and descendants so that future edge activations can maintain
//   the tree relationship rather than creating simple cycles.

namespace performance_manager {
namespace execution_context_priority {

namespace {

// Converts a non-default priority level to a zero-based index.
constexpr size_t PriorityToIndex(base::TaskPriority priority) { … }

// Converts a priority level to a bit in an |active_layers| variable.
constexpr uint32_t PriorityToBit(base::TaskPriority priority) { … }

static constexpr uint32_t kFirstLayerBit = …;
static constexpr uint32_t kLastLayerBit = …;
static_assert …;

static const ExecutionContext* kMaxExecutionContext = …;

}  // namespace

BoostingVote::BoostingVote(BoostingVoteAggregator* aggregator,
                           const ExecutionContext* input_execution_context,
                           const ExecutionContext* output_execution_context,
                           const char* reason)
    : … { … }

BoostingVote::BoostingVote(BoostingVote&& rhs) { … }

BoostingVote& BoostingVote::operator=(BoostingVote&& rhs) { … }

BoostingVote::~BoostingVote() { … }

void BoostingVote::Reset() { … }

bool BoostingVoteAggregator::ActiveLayers::IsActive(uint32_t layer_bit) const { … }

void BoostingVoteAggregator::ActiveLayers::SetActive(uint32_t layer_bit) { … }

void BoostingVoteAggregator::ActiveLayers::SetInactive(uint32_t layer_bit) { … }

BoostingVoteAggregator::NodeData::NodeData() = default;
BoostingVoteAggregator::NodeData::NodeData(NodeData&& rhs) = default;
BoostingVoteAggregator::NodeData::~NodeData() = default;

base::TaskPriority BoostingVoteAggregator::NodeData::GetEffectivePriorityLevel()
    const { … }

void BoostingVoteAggregator::NodeData::IncrementEdgeCount() { … }

void BoostingVoteAggregator::NodeData::DecrementEdgeCount() { … }

BoostingVoteAggregator::EdgeData::EdgeData() = default;

BoostingVoteAggregator::EdgeData::EdgeData(EdgeData&&) = default;

BoostingVoteAggregator::EdgeData& BoostingVoteAggregator::EdgeData::operator=(
    EdgeData&&) = default;

BoostingVoteAggregator::EdgeData::~EdgeData() = default;

void BoostingVoteAggregator::EdgeData::AddReason(const char* reason) { … }

bool BoostingVoteAggregator::EdgeData::RemoveReason(const char* reason) { … }

const char* BoostingVoteAggregator::EdgeData::GetActiveReason() const { … }

BoostingVoteAggregator::BoostingVoteAggregator() = default;

BoostingVoteAggregator::~BoostingVoteAggregator() { … }

VotingChannel BoostingVoteAggregator::GetVotingChannel() { … }

void BoostingVoteAggregator::SetUpstreamVotingChannel(VotingChannel channel) { … }

bool BoostingVoteAggregator::IsSetup() const { … }

void BoostingVoteAggregator::SubmitBoostingVote(
    const BoostingVote* boosting_vote) { … }

void BoostingVoteAggregator::CancelBoostingVote(
    const BoostingVote* boosting_vote) { … }

void BoostingVoteAggregator::OnVoteSubmitted(
    VoterId voter_id,
    const ExecutionContext* execution_context,
    const Vote& vote) { … }

void BoostingVoteAggregator::OnVoteChanged(
    VoterId voter_id,
    const ExecutionContext* execution_context,
    const Vote& new_vote) { … }

void BoostingVoteAggregator::OnVoteInvalidated(
    VoterId voter_id,
    const ExecutionContext* execution_context) { … }

template <typename Function>
void BoostingVoteAggregator::ForEachIncomingEdge(const ExecutionContext* node,
                                                 Function&& function) { … }

template <typename Function>
void BoostingVoteAggregator::ForEachOutgoingEdge(const ExecutionContext* node,
                                                 Function&& function) { … }

BoostingVoteAggregator::NodeDataMap::iterator
BoostingVoteAggregator::FindOrCreateNodeData(const ExecutionContext* node) { … }

BoostingVoteAggregator::NodeDataMap::iterator
BoostingVoteAggregator::FindNodeData(const ExecutionContext* node) { … }

const char* BoostingVoteAggregator::GetVoteReason(
    const NodeDataMap::value_type* node) { … }

void BoostingVoteAggregator::UpstreamVoteIfNeeded(
    NodeDataMap::value_type* node) { … }

void BoostingVoteAggregator::UpstreamChanges(const NodeDataPtrSet& changes) { … }

void BoostingVoteAggregator::MaybeRemoveNode(
    NodeDataMap::iterator node_data_it) { … }

void BoostingVoteAggregator::MarkSubtreeInactive(uint32_t layer_bit,
                                                 NodeDataMap::value_type* node,
                                                 NodeDataPtrSet* deactivated) { … }

BoostingVoteAggregator::ReverseEdges::iterator
BoostingVoteAggregator::GetActiveInboundEdge(
    uint32_t layer_bit,
    const NodeDataMap::value_type* node) { … }

BoostingVoteAggregator::NodeDataMap::value_type*
BoostingVoteAggregator::GetNearestActiveAncestor(
    uint32_t layer_bit,
    const NodeDataMap::value_type* deactivated_node) { … }

void BoostingVoteAggregator::GetNearestActiveAncestors(
    uint32_t layer_bit,
    const NodeDataPtrSet& deactivated,
    NodeDataPtrSet* active_ancestors) { … }

void BoostingVoteAggregator::MarkNodesActiveFromSearchFront(
    uint32_t layer_bit,
    NodeDataPtrSet* active_search_front,
    NodeDataPtrSet* activated) { … }

void BoostingVoteAggregator::ReprocessSubtree(uint32_t layer_bit,
                                              NodeDataMap::value_type* node,
                                              NodeDataPtrSet* changes) { … }

void BoostingVoteAggregator::OnVoteAdded(uint32_t layer_bit,
                                         NodeDataMap::value_type* node,
                                         NodeDataPtrSet* changes) { … }

void BoostingVoteAggregator::OnVoteRemoved(uint32_t layer_bit,
                                           NodeDataMap::value_type* node,
                                           NodeDataPtrSet* changes) { … }

}  // namespace execution_context_priority
}  // namespace performance_manager
chromium/components/performance_manager/execution_context_priority/boosting_vote_aggregator.cc
