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