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