blob: 2dff6728f08eb6c4056d108fac343873de9ebafd [file] [log] [blame]
Colin Cross8e8f34c2016-03-02 17:53:39 -08001/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <inttypes.h>
18
19#include "Allocator.h"
20#include "HeapWalker.h"
21#include "LeakFolding.h"
22#include "Tarjan.h"
23#include "log.h"
24
25// Converts possibly cyclic graph of leaks to a DAG by combining
26// strongly-connected components into a object, stored in the scc pointer
27// of each node in the component.
28void LeakFolding::ComputeDAG() {
29 SCCList<LeakInfo> scc_list{allocator_};
30 Tarjan(leak_graph_, scc_list);
31
32 Allocator<SCCInfo> scc_allocator = allocator_;
33
Colin Crossa83881e2017-06-22 10:50:05 -070034 for (auto& scc_nodes : scc_list) {
Colin Cross8e8f34c2016-03-02 17:53:39 -080035 Allocator<SCCInfo>::unique_ptr leak_scc;
36 leak_scc = scc_allocator.make_unique(scc_allocator);
37
Colin Crossa83881e2017-06-22 10:50:05 -070038 for (auto& node : scc_nodes) {
Colin Cross8e8f34c2016-03-02 17:53:39 -080039 node->ptr->scc = leak_scc.get();
40 leak_scc->count++;
41 leak_scc->size += node->ptr->range.size();
42 }
43
44 leak_scc_.emplace_back(std::move(leak_scc));
45 }
46
47 for (auto& it : leak_map_) {
48 LeakInfo& leak = it.second;
Colin Crossa83881e2017-06-22 10:50:05 -070049 for (auto& ref : leak.node.references_out) {
Colin Cross8e8f34c2016-03-02 17:53:39 -080050 if (leak.scc != ref->ptr->scc) {
51 leak.scc->node.Edge(&ref->ptr->scc->node);
52 }
53 }
54 }
55}
56
57void LeakFolding::AccumulateLeaks(SCCInfo* dominator) {
Colin Crossa83881e2017-06-22 10:50:05 -070058 std::function<void(SCCInfo*)> walk(std::allocator_arg, allocator_, [&](SCCInfo* scc) {
59 if (scc->accumulator != dominator) {
60 scc->accumulator = dominator;
61 dominator->cuumulative_size += scc->size;
62 dominator->cuumulative_count += scc->count;
63 scc->node.Foreach([&](SCCInfo* ref) { walk(ref); });
64 }
65 });
Colin Cross8e8f34c2016-03-02 17:53:39 -080066 walk(dominator);
67}
68
69bool LeakFolding::FoldLeaks() {
70 Allocator<LeakInfo> leak_allocator = allocator_;
71
72 // Find all leaked allocations insert them into leak_map_ and leak_graph_
Colin Crossa83881e2017-06-22 10:50:05 -070073 heap_walker_.ForEachAllocation([&](const Range& range, HeapWalker::AllocationInfo& allocation) {
74 if (!allocation.referenced_from_root) {
75 auto it = leak_map_.emplace(std::piecewise_construct, std::forward_as_tuple(range),
76 std::forward_as_tuple(range, allocator_));
77 LeakInfo& leak = it.first->second;
78 leak_graph_.push_back(&leak.node);
79 }
80 });
Colin Cross8e8f34c2016-03-02 17:53:39 -080081
82 // Find references between leaked allocations and connect them in leak_graph_
83 for (auto& it : leak_map_) {
84 LeakInfo& leak = it.second;
85 heap_walker_.ForEachPtrInRange(leak.range,
Colin Crossa83881e2017-06-22 10:50:05 -070086 [&](Range& ptr_range, HeapWalker::AllocationInfo* ptr_info) {
87 if (!ptr_info->referenced_from_root) {
88 LeakInfo* ptr_leak = &leak_map_.at(ptr_range);
89 leak.node.Edge(&ptr_leak->node);
90 }
91 });
Colin Cross8e8f34c2016-03-02 17:53:39 -080092 }
93
94 // Convert the cyclic graph to a DAG by grouping strongly connected components
95 ComputeDAG();
96
97 // Compute dominators and cuumulative sizes
98 for (auto& scc : leak_scc_) {
99 if (scc->node.references_in.size() == 0) {
100 scc->dominator = true;
101 AccumulateLeaks(scc.get());
102 }
103 }
104
105 return true;
106}
107
Colin Crossa83881e2017-06-22 10:50:05 -0700108bool LeakFolding::Leaked(allocator::vector<LeakFolding::Leak>& leaked, size_t* num_leaks_out,
109 size_t* leak_bytes_out) {
Colin Cross8e8f34c2016-03-02 17:53:39 -0800110 size_t num_leaks = 0;
111 size_t leak_bytes = 0;
112 for (auto& it : leak_map_) {
113 const LeakInfo& leak = it.second;
114 num_leaks++;
115 leak_bytes += leak.range.size();
116 }
117
Colin Cross8e8f34c2016-03-02 17:53:39 -0800118 for (auto& it : leak_map_) {
119 const LeakInfo& leak = it.second;
120 if (leak.scc->dominator) {
Colin Crossa83881e2017-06-22 10:50:05 -0700121 leaked.emplace_back(Leak{leak.range, leak.scc->cuumulative_count - 1,
122 leak.scc->cuumulative_size - leak.range.size()});
Colin Cross8e8f34c2016-03-02 17:53:39 -0800123 }
124 }
125
126 if (num_leaks_out) {
127 *num_leaks_out = num_leaks;
128 }
129 if (leak_bytes_out) {
130 *leak_bytes_out = leak_bytes;
131 }
132
133 return true;
134}