src/trace_processor/importers/proto/heap_graph_walker.cc - platform/external/perfetto - Git at Google

 /*
  * Copyright (C) 2019 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.
  */

 #include "src/trace_processor/importers/proto/heap_graph_walker.h"
 #include "perfetto/base/logging.h"

 namespace perfetto {
 namespace trace_processor {
 namespace {

 void AddChild(std::map<int64_t, int64_t>* component_to_node,
               uint64_t count,
               int64_t child_component_id,
               int64_t last_node_row) {
   if (count > 1) {
     // We have multiple edges from this component to the target component.
     // This cannot possibly be uniquely retained by one node in this
     // component.
     (*component_to_node)[child_component_id] = -1;
   } else {
     // Check if the node that owns grand_component via child_component_id
     // is the same as the node that owns it through all other
     // child_component_ids.
     auto it = component_to_node->find(child_component_id);
     if (it == component_to_node->end())
       (*component_to_node)[child_component_id] = last_node_row;
     else if (it->second != last_node_row)
       it->second = -1;
   }
 }

 bool IsUniqueOwner(const std::map<int64_t, int64_t>& component_to_node,
                    uint64_t count,
                    int64_t child_component_id,
                    int64_t last_node_row) {
   if (count > 1)
     return false;

   auto it = component_to_node.find(child_component_id);
   return it == component_to_node.end() || it->second == last_node_row;
 }

 }  // namespace

 HeapGraphWalker::Delegate::~Delegate() = default;

 void HeapGraphWalker::AddNode(int64_t row, uint64_t size) {
   if (static_cast<size_t>(row) >= nodes_.size())
     nodes_.resize(static_cast<size_t>(row) + 1);
   Node& node = GetNode(row);
   node.self_size = size;
   node.row = row;
 }

 void HeapGraphWalker::AddEdge(int64_t owner_row, int64_t owned_row) {
   GetNode(owner_row).children.emplace(&GetNode(owned_row));
   GetNode(owned_row).parents.emplace(&GetNode(owner_row));
 }

 void HeapGraphWalker::MarkRoot(int64_t row) {
   Node& n = GetNode(row);
   n.root = true;
   ReachableNode(&n);
 }

 void HeapGraphWalker::CalculateRetained() {
   for (Node& n : nodes_) {
     if (n.reachable && n.node_index == 0)
       FindSCC(&n);
   }

   // Sanity check that we have processed all edges.
   for (const auto& c : components_)
     PERFETTO_CHECK(c.incoming_edges == 0);
 }

 void HeapGraphWalker::ReachableNode(Node* node) {
   if (node->reachable)
     return;
   delegate_->MarkReachable(node->row);
   node->reachable = true;
   for (Node* child : node->children)
     ReachableNode(child);
 }

 int64_t HeapGraphWalker::RetainedSize(const Component& component) {
   int64_t retained_size =
       static_cast<int64_t>(component.unique_retained_size) +
       static_cast<int64_t>(component.unique_retained_root_size);
   for (const int64_t child_component_id : component.children_components) {
     const Component& child_component =
         components_[static_cast<size_t>(child_component_id)];
     retained_size += child_component.unique_retained_size;
   }
   return retained_size;
 }

 void HeapGraphWalker::FoundSCC(Node* node) {
   // We have discovered a new connected component.
   int64_t component_id = static_cast<int64_t>(components_.size());
   components_.emplace_back();
   Component& component = components_.back();
   component.lowlink = node->lowlink;

   std::vector<Node*> component_nodes;

   // A struct representing all direct children from this component.
   struct DirectChild {
     // Number of edges from current component_id to this component.
     size_t edges_from_current_component = 0;
     // If edges_from_current_component == 1, this is the row of the node that
     // has an outgoing edge to it.
     int64_t last_node_row = 0;
   };
   std::map<int64_t, DirectChild> direct_children_rows;

   Node* stack_elem;
   do {
     stack_elem = node_stack_.back();
     component_nodes.emplace_back(stack_elem);
     node_stack_.pop_back();
     for (Node* child : stack_elem->children) {
       if (!child->on_stack) {
         // If the node is not on the stack, but is a child of a node on the
         // stack, it must have already been explored (and assigned a
         // component).
         PERFETTO_CHECK(child->component != -1);
         if (child->component != component_id) {
           DirectChild& dc = direct_children_rows[child->component];
           dc.edges_from_current_component++;
           dc.last_node_row = stack_elem->row;
         }
       }
       // If the node is on the stack, it must be part of this SCC and will be
       // handled by the loop.
       // This node being on the stack means there exist a path from it to the
       // current node. If it also is a child of this node, there is a loop.
     }
     stack_elem->on_stack = false;
     // A node can never be part of two components.
     PERFETTO_CHECK(stack_elem->component == -1);
     stack_elem->component = component_id;
     if (stack_elem->root)
       component.root = true;
   } while (stack_elem != node);

   for (Node* elem : component_nodes) {
     component.unique_retained_size += elem->self_size;
     for (Node* parent : elem->parents) {
       // We do not count intra-component edges.
       if (parent->reachable && parent->component != component_id)
         component.incoming_edges++;
     }
     component.orig_incoming_edges = component.incoming_edges;
     component.pending_nodes = component.orig_incoming_edges;
   }

   std::map<int64_t, int64_t> unique_retained_by_node;
   // Map from child component to node in this component that uniquely owns it,
   // or -1 if non-unique.
   std::map<int64_t, int64_t> component_to_node;
   for (const auto& p : direct_children_rows) {
     int64_t child_component_id = p.first;
     const DirectChild& dc = p.second;
     size_t count = dc.edges_from_current_component;
     PERFETTO_CHECK(child_component_id != component_id);

     AddChild(&component_to_node, count, child_component_id, dc.last_node_row);

     Component& child_component =
         components_[static_cast<size_t>(child_component_id)];

     for (int64_t grand_component_id : child_component.children_components) {
       AddChild(&component_to_node, count, grand_component_id, dc.last_node_row);
       Component& grand_component =
           components_[static_cast<size_t>(grand_component_id)];
       grand_component.pending_nodes -= count;
       if (grand_component.pending_nodes == 0) {
         component.unique_retained_root_size +=
             grand_component.unique_retained_root_size;
         if (grand_component.root) {
           component.unique_retained_root_size +=
               grand_component.unique_retained_size;
         } else {
           component.unique_retained_size +=
               grand_component.unique_retained_size;

           if (IsUniqueOwner(component_to_node, count, grand_component_id,
                             dc.last_node_row)) {
             unique_retained_by_node[dc.last_node_row] +=
                 grand_component.unique_retained_size;
           }
         }
         grand_component.children_components.clear();
         component.children_components.erase(grand_component_id);
       } else {
         component.children_components.emplace(grand_component_id);
       }
     }

     child_component.incoming_edges -= count;
     child_component.pending_nodes -= count;

     if (child_component.pending_nodes == 0) {
       PERFETTO_CHECK(child_component.incoming_edges == 0);

       component.unique_retained_root_size +=
           child_component.unique_retained_root_size;
       if (child_component.root) {
         component.unique_retained_root_size +=
             child_component.unique_retained_size;
       } else {
         component.unique_retained_size += child_component.unique_retained_size;

         if (IsUniqueOwner(component_to_node, count, child_component_id,
                           dc.last_node_row)) {
           unique_retained_by_node[dc.last_node_row] +=
               child_component.unique_retained_size;
         }
       }
       component.children_components.erase(child_component_id);
     } else {
       component.children_components.emplace(child_component_id);
     }

     if (child_component.incoming_edges == 0)
       child_component.children_components.clear();
   }

   size_t parents = component.orig_incoming_edges;
   // If this has no parents, but does not retain a node, we know that no other
   // node can uniquely retain this node. Add 1 to poison that node.
   // If this is a root, but it does not retain a node, we also know that no
   // node can uniquely retain that node.
   if (parents == 0 || component.root)
     parents += 1;
   for (const int64_t child_component_id : component.children_components) {
     Component& child_component =
         components_[static_cast<size_t>(child_component_id)];
     PERFETTO_CHECK(child_component.pending_nodes > 0);
     child_component.pending_nodes += parents;
   }

   int64_t retained_size = RetainedSize(component);
   for (Node* n : component_nodes) {
     int64_t unique_retained_size = 0;
     auto it = unique_retained_by_node.find(n->row);
     if (it != unique_retained_by_node.end())
       unique_retained_size = it->second;

     delegate_->SetRetained(
         n->row, static_cast<int64_t>(retained_size),
         static_cast<int64_t>(n->self_size) + unique_retained_size);
   }
 }

 void HeapGraphWalker::FindSCC(Node* node) {
   node->node_index = node->lowlink = next_node_index_++;
   node_stack_.push_back(node);
   node->on_stack = true;
   for (Node* child : node->children) {
     PERFETTO_CHECK(child->reachable);
     if (child->node_index == 0) {
       FindSCC(child);
       if (child->lowlink < node->lowlink)
         node->lowlink = child->lowlink;
     } else if (child->on_stack) {
       if (child->node_index < node->lowlink)
         node->lowlink = child->node_index;
     }
   }

   if (node->lowlink == node->node_index)
     FoundSCC(node);
 }

 }  // namespace trace_processor
 }  // namespace perfetto
	/*
	* Copyright (C) 2019 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.
	*/

	#include "src/trace_processor/importers/proto/heap_graph_walker.h"
	#include "perfetto/base/logging.h"

	namespace perfetto {
	namespace trace_processor {
	namespace {

	void AddChild(std::map<int64_t, int64_t>* component_to_node,
	uint64_t count,
	int64_t child_component_id,
	int64_t last_node_row) {
	if (count > 1) {
	// We have multiple edges from this component to the target component.
	// This cannot possibly be uniquely retained by one node in this
	// component.
	(*component_to_node)[child_component_id] = -1;
	} else {
	// Check if the node that owns grand_component via child_component_id
	// is the same as the node that owns it through all other
	// child_component_ids.
	auto it = component_to_node->find(child_component_id);
	if (it == component_to_node->end())
	(*component_to_node)[child_component_id] = last_node_row;
	else if (it->second != last_node_row)
	it->second = -1;
	}
	}

	bool IsUniqueOwner(const std::map<int64_t, int64_t>& component_to_node,
	uint64_t count,
	int64_t child_component_id,
	int64_t last_node_row) {
	if (count > 1)
	return false;

	auto it = component_to_node.find(child_component_id);
	return it == component_to_node.end() \|\| it->second == last_node_row;
	}

	} // namespace

	HeapGraphWalker::Delegate::~Delegate() = default;

	void HeapGraphWalker::AddNode(int64_t row, uint64_t size) {
	if (static_cast<size_t>(row) >= nodes_.size())
	nodes_.resize(static_cast<size_t>(row) + 1);
	Node& node = GetNode(row);
	node.self_size = size;
	node.row = row;
	}

	void HeapGraphWalker::AddEdge(int64_t owner_row, int64_t owned_row) {
	GetNode(owner_row).children.emplace(&GetNode(owned_row));
	GetNode(owned_row).parents.emplace(&GetNode(owner_row));
	}

	void HeapGraphWalker::MarkRoot(int64_t row) {
	Node& n = GetNode(row);
	n.root = true;
	ReachableNode(&n);
	}

	void HeapGraphWalker::CalculateRetained() {
	for (Node& n : nodes_) {
	if (n.reachable && n.node_index == 0)
	FindSCC(&n);
	}

	// Sanity check that we have processed all edges.
	for (const auto& c : components_)
	PERFETTO_CHECK(c.incoming_edges == 0);
	}

	void HeapGraphWalker::ReachableNode(Node* node) {
	if (node->reachable)
	return;
	delegate_->MarkReachable(node->row);
	node->reachable = true;
	for (Node* child : node->children)
	ReachableNode(child);
	}

	int64_t HeapGraphWalker::RetainedSize(const Component& component) {
	int64_t retained_size =
	static_cast<int64_t>(component.unique_retained_size) +
	static_cast<int64_t>(component.unique_retained_root_size);
	for (const int64_t child_component_id : component.children_components) {
	const Component& child_component =
	components_[static_cast<size_t>(child_component_id)];
	retained_size += child_component.unique_retained_size;
	}
	return retained_size;
	}

	void HeapGraphWalker::FoundSCC(Node* node) {
	// We have discovered a new connected component.
	int64_t component_id = static_cast<int64_t>(components_.size());
	components_.emplace_back();
	Component& component = components_.back();
	component.lowlink = node->lowlink;

	std::vector<Node*> component_nodes;

	// A struct representing all direct children from this component.
	struct DirectChild {
	// Number of edges from current component_id to this component.
	size_t edges_from_current_component = 0;
	// If edges_from_current_component == 1, this is the row of the node that
	// has an outgoing edge to it.
	int64_t last_node_row = 0;
	};
	std::map<int64_t, DirectChild> direct_children_rows;

	Node* stack_elem;
	do {
	stack_elem = node_stack_.back();
	component_nodes.emplace_back(stack_elem);
	node_stack_.pop_back();
	for (Node* child : stack_elem->children) {
	if (!child->on_stack) {
	// If the node is not on the stack, but is a child of a node on the
	// stack, it must have already been explored (and assigned a
	// component).
	PERFETTO_CHECK(child->component != -1);
	if (child->component != component_id) {
	DirectChild& dc = direct_children_rows[child->component];
	dc.edges_from_current_component++;
	dc.last_node_row = stack_elem->row;
	}
	}
	// If the node is on the stack, it must be part of this SCC and will be
	// handled by the loop.
	// This node being on the stack means there exist a path from it to the
	// current node. If it also is a child of this node, there is a loop.
	}
	stack_elem->on_stack = false;
	// A node can never be part of two components.
	PERFETTO_CHECK(stack_elem->component == -1);
	stack_elem->component = component_id;
	if (stack_elem->root)
	component.root = true;
	} while (stack_elem != node);

	for (Node* elem : component_nodes) {
	component.unique_retained_size += elem->self_size;
	for (Node* parent : elem->parents) {
	// We do not count intra-component edges.
	if (parent->reachable && parent->component != component_id)
	component.incoming_edges++;
	}
	component.orig_incoming_edges = component.incoming_edges;
	component.pending_nodes = component.orig_incoming_edges;
	}

	std::map<int64_t, int64_t> unique_retained_by_node;
	// Map from child component to node in this component that uniquely owns it,
	// or -1 if non-unique.
	std::map<int64_t, int64_t> component_to_node;
	for (const auto& p : direct_children_rows) {
	int64_t child_component_id = p.first;
	const DirectChild& dc = p.second;
	size_t count = dc.edges_from_current_component;
	PERFETTO_CHECK(child_component_id != component_id);

	AddChild(&component_to_node, count, child_component_id, dc.last_node_row);

	Component& child_component =
	components_[static_cast<size_t>(child_component_id)];

	for (int64_t grand_component_id : child_component.children_components) {
	AddChild(&component_to_node, count, grand_component_id, dc.last_node_row);
	Component& grand_component =
	components_[static_cast<size_t>(grand_component_id)];
	grand_component.pending_nodes -= count;
	if (grand_component.pending_nodes == 0) {
	component.unique_retained_root_size +=
	grand_component.unique_retained_root_size;
	if (grand_component.root) {
	component.unique_retained_root_size +=
	grand_component.unique_retained_size;
	} else {
	component.unique_retained_size +=
	grand_component.unique_retained_size;

	if (IsUniqueOwner(component_to_node, count, grand_component_id,
	dc.last_node_row)) {
	unique_retained_by_node[dc.last_node_row] +=
	grand_component.unique_retained_size;
	}
	}
	grand_component.children_components.clear();
	component.children_components.erase(grand_component_id);
	} else {
	component.children_components.emplace(grand_component_id);
	}
	}

	child_component.incoming_edges -= count;
	child_component.pending_nodes -= count;

	if (child_component.pending_nodes == 0) {
	PERFETTO_CHECK(child_component.incoming_edges == 0);

	component.unique_retained_root_size +=
	child_component.unique_retained_root_size;
	if (child_component.root) {
	component.unique_retained_root_size +=
	child_component.unique_retained_size;
	} else {
	component.unique_retained_size += child_component.unique_retained_size;

	if (IsUniqueOwner(component_to_node, count, child_component_id,
	dc.last_node_row)) {
	unique_retained_by_node[dc.last_node_row] +=
	child_component.unique_retained_size;
	}
	}
	component.children_components.erase(child_component_id);
	} else {
	component.children_components.emplace(child_component_id);
	}

	if (child_component.incoming_edges == 0)
	child_component.children_components.clear();
	}

	size_t parents = component.orig_incoming_edges;
	// If this has no parents, but does not retain a node, we know that no other
	// node can uniquely retain this node. Add 1 to poison that node.
	// If this is a root, but it does not retain a node, we also know that no
	// node can uniquely retain that node.
	if (parents == 0 \|\| component.root)
	parents += 1;
	for (const int64_t child_component_id : component.children_components) {
	Component& child_component =
	components_[static_cast<size_t>(child_component_id)];
	PERFETTO_CHECK(child_component.pending_nodes > 0);
	child_component.pending_nodes += parents;
	}

	int64_t retained_size = RetainedSize(component);
	for (Node* n : component_nodes) {
	int64_t unique_retained_size = 0;
	auto it = unique_retained_by_node.find(n->row);
	if (it != unique_retained_by_node.end())
	unique_retained_size = it->second;

	delegate_->SetRetained(
	n->row, static_cast<int64_t>(retained_size),
	static_cast<int64_t>(n->self_size) + unique_retained_size);
	}
	}

	void HeapGraphWalker::FindSCC(Node* node) {
	node->node_index = node->lowlink = next_node_index_++;
	node_stack_.push_back(node);
	node->on_stack = true;
	for (Node* child : node->children) {
	PERFETTO_CHECK(child->reachable);
	if (child->node_index == 0) {
	FindSCC(child);
	if (child->lowlink < node->lowlink)
	node->lowlink = child->lowlink;
	} else if (child->on_stack) {
	if (child->node_index < node->lowlink)
	node->lowlink = child->node_index;
	}
	}

	if (node->lowlink == node->node_index)
	FoundSCC(node);
	}

	} // namespace trace_processor
	} // namespace perfetto