1 /*
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 namespace android {
26
27 // Converts possibly cyclic graph of leaks to a DAG by combining
28 // strongly-connected components into a object, stored in the scc pointer
29 // of each node in the component.
ComputeDAG()30 void LeakFolding::ComputeDAG() {
31 SCCList<LeakInfo> scc_list{allocator_};
32 Tarjan(leak_graph_, scc_list);
33
34 Allocator<SCCInfo> scc_allocator = allocator_;
35
36 for (auto& scc_nodes : scc_list) {
37 Allocator<SCCInfo>::unique_ptr leak_scc;
38 leak_scc = scc_allocator.make_unique(scc_allocator);
39
40 for (auto& node : scc_nodes) {
41 node->ptr->scc = leak_scc.get();
42 leak_scc->count++;
43 leak_scc->size += node->ptr->range.size();
44 }
45
46 leak_scc_.emplace_back(std::move(leak_scc));
47 }
48
49 for (auto& it : leak_map_) {
50 LeakInfo& leak = it.second;
51 for (auto& ref : leak.node.references_out) {
52 if (leak.scc != ref->ptr->scc) {
53 leak.scc->node.Edge(&ref->ptr->scc->node);
54 }
55 }
56 }
57 }
58
AccumulateLeaks(SCCInfo * dominator)59 void LeakFolding::AccumulateLeaks(SCCInfo* dominator) {
60 std::function<void(SCCInfo*)> walk([&](SCCInfo* scc) {
61 if (scc->accumulator != dominator) {
62 scc->accumulator = dominator;
63 dominator->cuumulative_size += scc->size;
64 dominator->cuumulative_count += scc->count;
65 scc->node.Foreach([&](SCCInfo* ref) { walk(ref); });
66 }
67 });
68 walk(dominator);
69 }
70
FoldLeaks()71 bool LeakFolding::FoldLeaks() {
72 Allocator<LeakInfo> leak_allocator = allocator_;
73
74 // Find all leaked allocations insert them into leak_map_ and leak_graph_
75 heap_walker_.ForEachAllocation([&](const Range& range, HeapWalker::AllocationInfo& allocation) {
76 if (!allocation.referenced_from_root) {
77 auto it = leak_map_.emplace(std::piecewise_construct, std::forward_as_tuple(range),
78 std::forward_as_tuple(range, allocator_));
79 LeakInfo& leak = it.first->second;
80 leak_graph_.push_back(&leak.node);
81 }
82 });
83
84 // Find references between leaked allocations and connect them in leak_graph_
85 for (auto& it : leak_map_) {
86 LeakInfo& leak = it.second;
87 heap_walker_.ForEachPtrInRange(leak.range,
88 [&](Range& ptr_range, HeapWalker::AllocationInfo* ptr_info) {
89 if (!ptr_info->referenced_from_root) {
90 LeakInfo* ptr_leak = &leak_map_.at(ptr_range);
91 leak.node.Edge(&ptr_leak->node);
92 }
93 });
94 }
95
96 // Convert the cyclic graph to a DAG by grouping strongly connected components
97 ComputeDAG();
98
99 // Compute dominators and cuumulative sizes
100 for (auto& scc : leak_scc_) {
101 if (scc->node.references_in.size() == 0) {
102 scc->dominator = true;
103 AccumulateLeaks(scc.get());
104 }
105 }
106
107 return true;
108 }
109
Leaked(allocator::vector<LeakFolding::Leak> & leaked,size_t * num_leaks_out,size_t * leak_bytes_out)110 bool LeakFolding::Leaked(allocator::vector<LeakFolding::Leak>& leaked, size_t* num_leaks_out,
111 size_t* leak_bytes_out) {
112 size_t num_leaks = 0;
113 size_t leak_bytes = 0;
114 for (auto& it : leak_map_) {
115 const LeakInfo& leak = it.second;
116 num_leaks++;
117 leak_bytes += leak.range.size();
118 }
119
120 for (auto& it : leak_map_) {
121 const LeakInfo& leak = it.second;
122 if (leak.scc->dominator) {
123 leaked.emplace_back(Leak{leak.range, leak.scc->cuumulative_count - 1,
124 leak.scc->cuumulative_size - leak.range.size()});
125 }
126 }
127
128 if (num_leaks_out) {
129 *num_leaks_out = num_leaks;
130 }
131 if (leak_bytes_out) {
132 *leak_bytes_out = leak_bytes;
133 }
134
135 return true;
136 }
137
138 } // namespace android
139