Home | History | Annotate | Download | only in libmemunreachable 
      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(std::allocator_arg, allocator_, [&](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