Merge "Do not count roots as unique_retained." am: 51516f0763 am: 1dfacee66b Change-Id: Ib78072ff9a5ccbbdff0dbbb6f14d040a7327bbd3
diff --git a/src/trace_processor/importers/proto/heap_graph_walker.cc b/src/trace_processor/importers/proto/heap_graph_walker.cc index 5805b77..8655d85 100644 --- a/src/trace_processor/importers/proto/heap_graph_walker.cc +++ b/src/trace_processor/importers/proto/heap_graph_walker.cc
@@ -72,6 +72,7 @@ void HeapGraphWalker::MarkRoot(int64_t row) { Node& n = GetNode(row); + n.root = true; ReachableNode(&n); } @@ -96,7 +97,9 @@ } int64_t HeapGraphWalker::RetainedSize(const Component& component) { - int64_t retained_size = static_cast<int64_t>(component.unique_retained_size); + 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)]; @@ -150,6 +153,8 @@ // 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) { @@ -184,11 +189,20 @@ components_[static_cast<size_t>(grand_component_id)]; grand_component.pending_nodes -= count; if (grand_component.pending_nodes == 0) { - 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] += + 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); @@ -200,22 +214,22 @@ child_component.incoming_edges -= count; child_component.pending_nodes -= count; - if (child_component.orig_incoming_edges == count) { + if (child_component.pending_nodes == 0) { PERFETTO_CHECK(child_component.incoming_edges == 0); - PERFETTO_CHECK(child_component.pending_nodes == 0); - component.unique_retained_size += child_component.unique_retained_size; - if (count == 1) { - unique_retained_by_node[dc.last_node_row] += + 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 if (child_component.pending_nodes == 0) { - PERFETTO_CHECK(child_component.incoming_edges == 0); - 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; + } 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 { @@ -228,9 +242,11 @@ 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 retain this node. Add 1 to poison that node. - if (parents == 0) - parents = 1; + // 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)]; @@ -256,6 +272,7 @@ 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)
diff --git a/src/trace_processor/importers/proto/heap_graph_walker.h b/src/trace_processor/importers/proto/heap_graph_walker.h index 57d4550..b23f2a3 100644 --- a/src/trace_processor/importers/proto/heap_graph_walker.h +++ b/src/trace_processor/importers/proto/heap_graph_walker.h
@@ -135,15 +135,20 @@ bool reachable = false; bool on_stack = false; + bool root = false; }; struct Component { + uint64_t self_size = 0; uint64_t unique_retained_size = 0; + uint64_t unique_retained_root_size = 0; size_t incoming_edges = 0; size_t orig_incoming_edges = 0; size_t pending_nodes = 0; std::set<int64_t> children_components; uint64_t lowlink = 0; + + bool root = false; }; Node& GetNode(int64_t id) { return nodes_[static_cast<size_t>(id)]; }
diff --git a/src/trace_processor/importers/proto/heap_graph_walker_unittest.cc b/src/trace_processor/importers/proto/heap_graph_walker_unittest.cc index 29b2a3f..763af52 100644 --- a/src/trace_processor/importers/proto/heap_graph_walker_unittest.cc +++ b/src/trace_processor/importers/proto/heap_graph_walker_unittest.cc
@@ -23,6 +23,9 @@ namespace trace_processor { namespace { +using ::testing::UnorderedElementsAre; +using ::testing::UnorderedElementsAreArray; + class HeapGraphWalkerTestDelegate : public HeapGraphWalker::Delegate { public: ~HeapGraphWalkerTestDelegate() override = default; @@ -68,7 +71,7 @@ // 2 3 | // ^ ^ | // \ / | -// 4 | +// 4R | TEST(HeapGraphWalkerTest, Diamond) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -96,10 +99,10 @@ EXPECT_EQ(delegate.UniqueRetained(4), 10); } -// 1 2 | -// ^ ^ | -// \ / | -// 3<->4 | +// 1 2 | +// ^ ^ | +// \ / | +// 3R<->4 | TEST(HeapGraphWalkerTest, Loop) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -127,7 +130,7 @@ EXPECT_EQ(delegate.UniqueRetained(4), 6); } -// 1 | +// 1R | // ^\ | // / v | // 3<-2 | @@ -157,10 +160,10 @@ // 1 | // ^ | // | | -// 2 4 | -// ^ ^ | -// | | | -// 3 5 | +// 2 4 | +// ^ ^ | +// | | | +// 3R 5 | TEST(HeapGraphWalkerTest, Disconnected) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -201,7 +204,7 @@ // 4 5 | // ^ ^ | // \ / | -// 6 | +// 6R | TEST(HeapGraphWalkerTest, Complex) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -244,7 +247,7 @@ // 2<-> 3 | // ^ | // | | -// 4 | +// 4R | TEST(HeapGraphWalkerTest, SharedInComponent) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -268,6 +271,7 @@ EXPECT_EQ(delegate.Retained(4), 10); EXPECT_EQ(delegate.UniqueRetained(1), 1); + // TODO(fmayer): this should be 6, as it breaks away the component. EXPECT_EQ(delegate.UniqueRetained(2), 2); EXPECT_EQ(delegate.UniqueRetained(3), 3); EXPECT_EQ(delegate.UniqueRetained(4), 10); @@ -276,7 +280,7 @@ // 1 <- 2 | // ^ ^ | // | | | -// 3<-> 4 | +// 3<-> 4R | TEST(HeapGraphWalkerTest, TwoPaths) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -308,7 +312,7 @@ // 1 | // ^^ | // / \ | -// 2 3 | +// 2R 3R | TEST(HeapGraphWalkerTest, Diverge) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -335,7 +339,7 @@ // 1 | // ^^ | // / \ | -// 2 3 (dead) | +// 2R 3 (dead) | TEST(HeapGraphWalkerTest, Dead) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); @@ -356,16 +360,11 @@ EXPECT_EQ(delegate.UniqueRetained(2), 3); } -// We defined unique_retained as follows: -// the number of bytes that are only retained through this object. -// if this object were destroyed, this many bytes would be freed up. -// The following test-case is a counter-example for the current -// implementation. // 2<->3 | // ^ | // | | -// 1 | -TEST(HeapGraphWalkerTest, DISABLED_UnreachableComponent) { +// 1R | +TEST(HeapGraphWalkerTest, Component) { HeapGraphWalkerTestDelegate delegate; HeapGraphWalker walker(&delegate); walker.AddNode(1, 1); @@ -384,9 +383,204 @@ EXPECT_EQ(delegate.Retained(3), 5); EXPECT_EQ(delegate.UniqueRetained(1), 6); - EXPECT_EQ(delegate.UniqueRetained(2), 5); + // TODO(fmayer): this should be 5, as this breaks away the component. + EXPECT_EQ(delegate.UniqueRetained(2), 2); EXPECT_EQ(delegate.UniqueRetained(3), 3); } + +// 2<->3R | +// ^ | +// | | +// 1R | +TEST(HeapGraphWalkerTest, ComponentWithRoot) { + HeapGraphWalkerTestDelegate delegate; + HeapGraphWalker walker(&delegate); + walker.AddNode(1, 1); + walker.AddNode(2, 2); + walker.AddNode(3, 3); + + walker.AddEdge(1, 2); + walker.AddEdge(2, 3); + walker.AddEdge(3, 2); + + walker.MarkRoot(1); + walker.MarkRoot(3); + walker.CalculateRetained(); + + EXPECT_EQ(delegate.Retained(1), 6); + EXPECT_EQ(delegate.Retained(2), 5); + EXPECT_EQ(delegate.Retained(3), 5); + + EXPECT_EQ(delegate.UniqueRetained(1), 1); + EXPECT_EQ(delegate.UniqueRetained(2), 2); + EXPECT_EQ(delegate.UniqueRetained(3), 3); +} + +// R +// 2 <- 3 | +// ^ ^ | +// \ / | +// 1R | +TEST(HeapGraphWalkerTest, TwoRoots) { + HeapGraphWalkerTestDelegate delegate; + HeapGraphWalker walker(&delegate); + walker.AddNode(1, 1); + walker.AddNode(2, 2); + walker.AddNode(3, 3); + + walker.AddEdge(1, 2); + walker.AddEdge(1, 3); + walker.AddEdge(3, 2); + + walker.MarkRoot(1); + walker.MarkRoot(2); + walker.CalculateRetained(); + + EXPECT_EQ(delegate.Retained(1), 6); + EXPECT_EQ(delegate.Retained(2), 2); + EXPECT_EQ(delegate.Retained(3), 5); + + EXPECT_EQ(delegate.UniqueRetained(1), 4); + EXPECT_EQ(delegate.UniqueRetained(2), 2); + EXPECT_EQ(delegate.UniqueRetained(3), 3); +} + +// Call a function for every set in the powerset or the cartesian product +// of v with itself. +// TODO(fmayer): Find a smarter way to generate all graphs. +template <typename F> +void SquarePowerSet(const std::vector<int64_t>& v, F fn) { + for (uint64_t subset = 0; subset < pow(2, pow(v.size(), 2)); ++subset) { + std::vector<std::pair<int64_t, int64_t>> ps; + uint64_t node = 0; + for (int64_t n1 : v) { + for (int64_t n2 : v) { + if ((1 << node++) & subset) + ps.emplace_back(n1, n2); + } + } + fn(ps); + } +} + +// Call a function for every set in the powerset. +template <typename F> +void PowerSet(const std::vector<int64_t>& v, F fn) { + for (uint64_t subset = 0; subset < pow(2, v.size()); ++subset) { + std::vector<int64_t> ps; + uint64_t node = 0; + for (int64_t n : v) { + if ((1 << node++) & subset) + ps.emplace_back(n); + } + fn(ps); + } +} + +TEST(PowerSetTest, Simple) { + std::vector<int64_t> s = {0, 1, 2}; + std::vector<std::vector<int64_t>> ps; + PowerSet(s, [&ps](const std::vector<int64_t>& x) { ps.emplace_back(x); }); + EXPECT_THAT(ps, UnorderedElementsAre(std::vector<int64_t>{}, // + std::vector<int64_t>{0}, // + std::vector<int64_t>{1}, // + std::vector<int64_t>{2}, // + std::vector<int64_t>{0, 1}, // + std::vector<int64_t>{0, 2}, // + std::vector<int64_t>{1, 2}, // + std::vector<int64_t>{0, 1, 2})); +} + +TEST(SquarePowerSetTest, Simple) { + std::vector<int64_t> s = {0, 1}; + std::vector<std::vector<std::pair<int64_t, int64_t>>> ps; + SquarePowerSet(s, [&ps](const std::vector<std::pair<int64_t, int64_t>>& x) { + ps.emplace_back(x); + }); + + std::vector<std::pair<int64_t, int64_t>> expected[] = { + {}, // + {{0, 0}}, // + {{0, 1}}, // + {{1, 0}}, // + {{1, 1}}, // + {{0, 0}, {0, 1}}, // + {{0, 0}, {1, 0}}, // + {{0, 0}, {1, 1}}, // + {{0, 1}, {1, 0}}, // + {{0, 1}, {1, 1}}, // + {{1, 0}, {1, 1}}, // + {{0, 0}, {0, 1}, {1, 0}}, // + {{0, 0}, {0, 1}, {1, 1}}, // + {{0, 0}, {1, 0}, {1, 1}}, // + {{0, 1}, {1, 0}, {1, 1}}, // + {{0, 0}, {0, 1}, {1, 0}, {1, 1}}}; + EXPECT_THAT(ps, UnorderedElementsAreArray(expected)); +} + +// Generate all graphs with 4 nodes, and assert that deleting one node frees +// up more memory than that node's unique retained. +TEST(HeapGraphWalkerTest, AllGraphs) { + std::vector<int64_t> nodes{1, 2, 3, 4}; + std::vector<uint64_t> sizes{0, 1, 2, 3, 4}; + PowerSet(nodes, [&nodes, &sizes](const std::vector<int64_t>& roots) { + SquarePowerSet( + nodes, [&nodes, &sizes, + &roots](const std::vector<std::pair<int64_t, int64_t>>& edges) { + HeapGraphWalkerTestDelegate delegate; + HeapGraphWalker walker(&delegate); + + HeapGraphWalkerTestDelegate delegate2; + HeapGraphWalker walker2(&delegate2); + + for (int64_t node : nodes) { + walker.AddNode(node, sizes[static_cast<size_t>(node)]); + // walker2 leaves out node 1. + if (node != 1) + walker2.AddNode(node, sizes[static_cast<size_t>(node)]); + } + + for (const auto& p : edges) { + walker.AddEdge(p.first, p.second); + // walker2 leaves out node 1. + if (p.first != 1 && p.second != 1) + walker2.AddEdge(p.first, p.second); + } + + for (int64_t r : roots) { + walker.MarkRoot(r); + // walker2 leaves out node 1. + if (r != 1) + walker2.MarkRoot(r); + } + + walker.CalculateRetained(); + // We do not need to CalculateRetained on walker2, because we only + // get the reachable nodes. + + int64_t reachable = 0; + int64_t reachable2 = 0; + + ASSERT_FALSE(delegate2.Reachable(1)); + for (int64_t n : nodes) { + if (delegate.Reachable(n)) + reachable += sizes[static_cast<size_t>(n)]; + if (delegate2.Reachable(n)) + reachable2 += sizes[static_cast<size_t>(n)]; + } + EXPECT_LE(reachable2, reachable); + if (delegate.Reachable(1)) { + // TODO(fmayer): This should be EXPECT_EQ, but we do currently + // undercount the unique retained, because we do not include the + // memory that could get freed by the component being broken apart. + EXPECT_LE(delegate.UniqueRetained(1), reachable - reachable2) + << "roots: " << testing::PrintToString(roots) + << ", edges: " << testing::PrintToString(edges); + } + }); + }); +} + } // namespace } // namespace trace_processor } // namespace perfetto