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.
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 
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 
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 
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