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.
28void 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
57void 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
72bool 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
113bool 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