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 #ifndef LIBMEMUNREACHABLE_HEAP_WALKER_H_ 18 #define LIBMEMUNREACHABLE_HEAP_WALKER_H_ 19 20 #include <signal.h> 21 22 #include "android-base/macros.h" 23 24 #include "Allocator.h" 25 #include "ScopedSignalHandler.h" 26 #include "Tarjan.h" 27 28 namespace android { 29 30 // A range [begin, end) 31 struct Range { 32 uintptr_t begin; 33 uintptr_t end; 34 35 size_t size() const { return end - begin; }; 36 bool operator==(const Range& other) const { 37 return this->begin == other.begin && this->end == other.end; 38 } 39 bool operator!=(const Range& other) const { return !(*this == other); } 40 }; 41 42 // Comparator for Ranges that returns equivalence for overlapping ranges 43 struct compare_range { 44 bool operator()(const Range& a, const Range& b) const { return a.end <= b.begin; } 45 }; 46 47 class HeapWalker { 48 public: 49 explicit HeapWalker(Allocator<HeapWalker> allocator) 50 : allocator_(allocator), 51 allocations_(allocator), 52 allocation_bytes_(0), 53 roots_(allocator), 54 root_vals_(allocator), 55 segv_handler_(allocator), 56 walking_ptr_(0) { 57 valid_allocations_range_.end = 0; 58 valid_allocations_range_.begin = ~valid_allocations_range_.end; 59 60 segv_handler_.install( 61 SIGSEGV, [=](ScopedSignalHandler& handler, int signal, siginfo_t* siginfo, void* uctx) { 62 this->HandleSegFault(handler, signal, siginfo, uctx); 63 }); 64 } 65 66 ~HeapWalker() {} 67 bool Allocation(uintptr_t begin, uintptr_t end); 68 void Root(uintptr_t begin, uintptr_t end); 69 void Root(const allocator::vector<uintptr_t>& vals); 70 71 bool DetectLeaks(); 72 73 bool Leaked(allocator::vector<Range>&, size_t limit, size_t* num_leaks, size_t* leak_bytes); 74 size_t Allocations(); 75 size_t AllocationBytes(); 76 77 template <class F> 78 void ForEachPtrInRange(const Range& range, F&& f); 79 80 template <class F> 81 void ForEachAllocation(F&& f); 82 83 struct AllocationInfo { 84 bool referenced_from_root; 85 }; 86 87 private: 88 void RecurseRoot(const Range& root); 89 bool WordContainsAllocationPtr(uintptr_t ptr, Range* range, AllocationInfo** info); 90 void HandleSegFault(ScopedSignalHandler&, int, siginfo_t*, void*); 91 92 DISALLOW_COPY_AND_ASSIGN(HeapWalker); 93 Allocator<HeapWalker> allocator_; 94 using AllocationMap = allocator::map<Range, AllocationInfo, compare_range>; 95 AllocationMap allocations_; 96 size_t allocation_bytes_; 97 Range valid_allocations_range_; 98 99 allocator::vector<Range> roots_; 100 allocator::vector<uintptr_t> root_vals_; 101 102 ScopedSignalHandler segv_handler_; 103 uintptr_t walking_ptr_; 104 }; 105 106 template <class F> 107 inline void HeapWalker::ForEachPtrInRange(const Range& range, F&& f) { 108 uintptr_t begin = (range.begin + (sizeof(uintptr_t) - 1)) & ~(sizeof(uintptr_t) - 1); 109 // TODO(ccross): we might need to consider a pointer to the end of a buffer 110 // to be inside the buffer, which means the common case of a pointer to the 111 // beginning of a buffer may keep two ranges live. 112 for (uintptr_t i = begin; i < range.end; i += sizeof(uintptr_t)) { 113 Range ref_range; 114 AllocationInfo* ref_info; 115 if (WordContainsAllocationPtr(i, &ref_range, &ref_info)) { 116 f(ref_range, ref_info); 117 } 118 } 119 } 120 121 template <class F> 122 inline void HeapWalker::ForEachAllocation(F&& f) { 123 for (auto& it : allocations_) { 124 const Range& range = it.first; 125 HeapWalker::AllocationInfo& allocation = it.second; 126 f(range, allocation); 127 } 128 } 129 130 } // namespace android 131 132 #endif 133