/*
 * Copyright (C) 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef INCLUDE_PERFETTO_EXT_TRACE_PROCESSOR_IMPORTERS_MEMORY_TRACKER_GRAPH_PROCESSOR_H_
#define INCLUDE_PERFETTO_EXT_TRACE_PROCESSOR_IMPORTERS_MEMORY_TRACKER_GRAPH_PROCESSOR_H_

#include <sys/types.h>

#include <map>
#include <memory>
#include <set>
#include <string>

#include "perfetto/base/proc_utils.h"
#include "perfetto/ext/trace_processor/importers/memory_tracker/graph.h"
#include "perfetto/ext/trace_processor/importers/memory_tracker/raw_process_memory_node.h"

namespace perfetto {
namespace trace_processor {

class PERFETTO_EXPORT_COMPONENT GraphProcessor {
 public:
  // This map does not own the pointers inside.
  using RawMemoryNodeMap =
      std::map<base::PlatformProcessId, std::unique_ptr<RawProcessMemoryNode>>;

  static std::unique_ptr<GlobalNodeGraph> CreateMemoryGraph(
      const RawMemoryNodeMap& process_nodes);

  static void RemoveWeakNodesFromGraph(GlobalNodeGraph* global_graph);

  static void AddOverheadsAndPropagateEntries(GlobalNodeGraph* global_graph);

  static void CalculateSizesForGraph(GlobalNodeGraph* global_graph);

  static std::map<base::PlatformProcessId, uint64_t>
  ComputeSharedFootprintFromGraph(const GlobalNodeGraph& global_graph);

 private:
  friend class GraphProcessorTest;

  static void CollectAllocatorNodes(const RawProcessMemoryNode& source,
                                    GlobalNodeGraph* global_graph,
                                    GlobalNodeGraph::Process* process_graph);

  static void AddEdges(const RawProcessMemoryNode& source,
                       GlobalNodeGraph* global_graph);

  static void MarkImplicitWeakParentsRecursively(GlobalNodeGraph::Node* node);

  static void MarkWeakOwnersAndChildrenRecursively(
      GlobalNodeGraph::Node* node,
      std::set<const GlobalNodeGraph::Node*>* nodes);

  static void RemoveWeakNodesRecursively(GlobalNodeGraph::Node* parent);

  static void AssignTracingOverhead(const std::string& allocator,
                                    GlobalNodeGraph* global_graph,
                                    GlobalNodeGraph::Process* process);

  static GlobalNodeGraph::Node::Entry AggregateNumericWithNameForNode(
      GlobalNodeGraph::Node* node,
      const std::string& name);

  static void AggregateNumericsRecursively(GlobalNodeGraph::Node* node);

  static void PropagateNumericsAndDiagnosticsRecursively(
      GlobalNodeGraph::Node* node);

  static std::optional<uint64_t> AggregateSizeForDescendantNode(
      GlobalNodeGraph::Node* root,
      GlobalNodeGraph::Node* descendant);

  static void CalculateSizeForNode(GlobalNodeGraph::Node* node);

  /**
   * Calculate not-owned and not-owning sub-sizes of a memory allocator node
   * from its children's (sub-)sizes.
   *
   * Not-owned sub-size refers to the aggregated memory of all children which
   * is not owned by other MADs. Conversely, not-owning sub-size is the
   * aggregated memory of all children which do not own another MAD. The
   * diagram below illustrates these two concepts:
   *
   *     ROOT 1                         ROOT 2
   *     size: 4                        size: 5
   *     not-owned sub-size: 4          not-owned sub-size: 1 (!)
   *     not-owning sub-size: 0 (!)     not-owning sub-size: 5
   *
   *      ^                              ^
   *      |                              |
   *
   *     PARENT 1   ===== owns =====>   PARENT 2
   *     size: 4                        size: 5
   *     not-owned sub-size: 4          not-owned sub-size: 5
   *     not-owning sub-size: 4         not-owning sub-size: 5
   *
   *      ^                              ^
   *      |                              |
   *
   *     CHILD 1                        CHILD 2
   *     size [given]: 4                size [given]: 5
   *     not-owned sub-size: 4          not-owned sub-size: 5
   *     not-owning sub-size: 4         not-owning sub-size: 5
   *
   * This method assumes that (1) the size of the node, its children, and its
   * owners [see calculateSizes()] and (2) the not-owned and not-owning
   * sub-sizes of both the children and owners of the node have already been
   * calculated [depth-first post-order traversal].
   */
  static void CalculateNodeSubSizes(GlobalNodeGraph::Node* node);

  /**
   * Calculate owned and owning coefficients of a memory allocator node and
   * its owners.
   *
   * The owning coefficient refers to the proportion of a node's not-owning
   * sub-size which is attributed to the node (only relevant to owning MADs).
   * Conversely, the owned coefficient is the proportion of a node's
   * not-owned sub-size, which is attributed to it (only relevant to owned
   * MADs).
   *
   * The not-owned size of the owned node is split among its owners in the
   * order of the ownership importance as demonstrated by the following
   * example:
   *
   *                                          memory allocator nodes
   *                                   OWNED  OWNER1  OWNER2  OWNER3 OWNER4
   *       not-owned sub-size [given]     10       -       -       - -
   *      not-owning sub-size [given]      -       6       7       5 8
   *               importance [given]      -       2       2       1 0
   *    attributed not-owned sub-size      2       -       -       - -
   *   attributed not-owning sub-size      -       3       4       0 1
   *                owned coefficient   2/10       -       -       - -
   *               owning coefficient      -     3/6     4/7     0/5 1/8
   *
   * Explanation: Firstly, 6 bytes are split equally among OWNER1 and OWNER2
   * (highest importance). OWNER2 owns one more byte, so its attributed
   * not-owning sub-size is 6/2 + 1 = 4 bytes. OWNER3 is attributed no size
   * because it is smaller than the owners with higher priority. However,
   * OWNER4 is larger, so it's attributed the difference 8 - 7 = 1 byte.
   * Finally, 2 bytes remain unattributed and are hence kept in the OWNED
   * node as attributed not-owned sub-size. The coefficients are then
   * directly calculated as fractions of the sub-sizes and corresponding
   * attributed sub-sizes.
   *
   * Note that we always assume that all ownerships of a node overlap (e.g.
   * OWNER3 is subsumed by both OWNER1 and OWNER2). Hence, the table could
   * be alternatively represented as follows:
   *
   *                                 owned memory range
   *              0   1   2    3    4    5    6        7        8   9  10
   *   Priority 2 |  OWNER1 + OWNER2 (split)  | OWNER2 |
   *   Priority 1 | (already attributed) |
   *   Priority 0 | - - -  (already attributed)  - - - | OWNER4 |
   *    Remainder | - - - - - (already attributed) - - - - - -  | OWNED |
   *
   * This method assumes that (1) the size of the node [see calculateSizes()]
   * and (2) the not-owned size of the node and not-owning sub-sizes of its
   * owners [see the first step of calculateEffectiveSizes()] have already
   * been calculated. Note that the method doesn't make any assumptions about
   * the order in which nodes are visited.
   */
  static void CalculateNodeOwnershipCoefficient(GlobalNodeGraph::Node* node);

  /**
   * Calculate cumulative owned and owning coefficients of a memory allocator
   * node from its (non-cumulative) owned and owning coefficients and the
   * cumulative coefficients of its parent and/or owned node.
   *
   * The cumulative coefficients represent the total effect of all
   * (non-strict) ancestor ownerships on a memory allocator node. The
   * cumulative owned coefficient of a MAD can be calculated simply as:
   *
   *   cumulativeOwnedC(M) = ownedC(M) * cumulativeOwnedC(parent(M))
   *
   * This reflects the assumption that if a parent of a child MAD is
   * (partially) owned, then the parent's owner also indirectly owns (a part
   * of) the child MAD.
   *
   * The cumulative owning coefficient of a MAD depends on whether the MAD
   * owns another node:
   *
   *                           [if M doesn't own another MAD]
   *                         / cumulativeOwningC(parent(M))
   *   cumulativeOwningC(M) =
   *                         \ [if M owns another MAD]
   *                           owningC(M) * cumulativeOwningC(owned(M))
   *
   * The reasoning behind the first case is similar to the one for cumulative
   * owned coefficient above. The only difference is that we don't need to
   * include the node's (non-cumulative) owning coefficient because it is
   * implicitly 1.
   *
   * The formula for the second case is derived as follows: Since the MAD
   * owns another node, its memory is not included in its parent's not-owning
   * sub-size and hence shouldn't be affected by the parent's corresponding
   * cumulative coefficient. Instead, the MAD indirectly owns everything
   * owned by its owned node (and so it should be affected by the
   * corresponding coefficient).
   *
   * Note that undefined coefficients (and coefficients of non-existent
   * nodes) are implicitly assumed to be 1.
   *
   * This method assumes that (1) the size of the node [see calculateSizes()],
   * (2) the (non-cumulative) owned and owning coefficients of the node [see
   * the second step of calculateEffectiveSizes()], and (3) the cumulative
   * coefficients of the node's parent and owned MADs (if present)
   * [depth-first pre-order traversal] have already been calculated.
   */
  static void CalculateNodeCumulativeOwnershipCoefficient(
      GlobalNodeGraph::Node* node);

  /**
   * Calculate the effective size of a memory allocator node.
   *
   * In order to simplify the (already complex) calculation, we use the fact
   * that effective size is cumulative (unlike regular size), i.e. the
   * effective size of a non-leaf node is equal to the sum of effective sizes
   * of its children. The effective size of a leaf MAD is calculated as:
   *
   *   effectiveSize(M) = size(M) * cumulativeOwningC(M) * cumulativeOwnedC(M)
   *
   * This method assumes that (1) the size of the node and its children [see
   * calculateSizes()] and (2) the cumulative owning and owned coefficients
   * of the node (if it's a leaf node) [see the third step of
   * calculateEffectiveSizes()] or the effective sizes of its children (if
   * it's a non-leaf node) [depth-first post-order traversal] have already
   * been calculated.
   */
  static void CalculateNodeEffectiveSize(GlobalNodeGraph::Node* node);
};

}  // namespace trace_processor
}  // namespace perfetto

#endif  // INCLUDE_PERFETTO_EXT_TRACE_PROCESSOR_IMPORTERS_MEMORY_TRACKER_GRAPH_PROCESSOR_H_