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         sigsegv_handler_(allocator),
56         sigbus_handler_(allocator),
57         walking_ptr_(0),
58         walking_range_{0, 0},
59         segv_logged_(false),
60         segv_page_count_(0) {
61     valid_allocations_range_.end = 0;
62     valid_allocations_range_.begin = ~valid_allocations_range_.end;
63     valid_mappings_range_.end = 0;
64     valid_mappings_range_.begin = ~valid_allocations_range_.end;
65 
66     sigsegv_handler_.install(
67         SIGSEGV, [=](ScopedSignalHandler& handler, int signal, siginfo_t* siginfo, void* uctx) {
68           this->HandleSegFault(handler, signal, siginfo, uctx);
69         });
70     sigbus_handler_.install(
71         SIGBUS, [=](ScopedSignalHandler& handler, int signal, siginfo_t* siginfo, void* uctx) {
72           this->HandleSegFault(handler, signal, siginfo, uctx);
73         });
74   }
75 
76   ~HeapWalker() {}
77   bool Allocation(uintptr_t begin, uintptr_t end);
78   void Mapping(uintptr_t begin, uintptr_t end);
79   void Root(uintptr_t begin, uintptr_t end);
80   void Root(const allocator::vector<uintptr_t>& vals);
81 
82   bool DetectLeaks();
83 
84   bool Leaked(allocator::vector<Range>&, size_t limit, size_t* num_leaks, size_t* leak_bytes);
85   size_t Allocations();
86   size_t AllocationBytes();
87 
88   template <class F>
89   void ForEachPtrInRange(const Range& range, F&& f);
90 
91   template <class F>
92   void ForEachAllocation(F&& f);
93 
94   struct AllocationInfo {
95     bool referenced_from_root;
96   };
97 
98  private:
99   void RecurseRoot(const Range& root);
100   bool WordContainsAllocationPtr(uintptr_t ptr, Range* range, AllocationInfo** info);
101   void HandleSegFault(ScopedSignalHandler&, int, siginfo_t*, void*);
102 
103   DISALLOW_COPY_AND_ASSIGN(HeapWalker);
104   Allocator<HeapWalker> allocator_;
105   using AllocationMap = allocator::map<Range, AllocationInfo, compare_range>;
106   AllocationMap allocations_;
107   size_t allocation_bytes_;
108   Range valid_allocations_range_;
109   Range valid_mappings_range_;
110 
111   allocator::vector<Range> roots_;
112   allocator::vector<uintptr_t> root_vals_;
113 
114   ScopedSignalHandler sigsegv_handler_;
115   ScopedSignalHandler sigbus_handler_;
116   volatile uintptr_t walking_ptr_;
117   Range walking_range_;
118   bool segv_logged_;
119   size_t segv_page_count_;
120 };
121 
122 template <class F>
123 inline void HeapWalker::ForEachPtrInRange(const Range& range, F&& f) {
124   uintptr_t begin = (range.begin + (sizeof(uintptr_t) - 1)) & ~(sizeof(uintptr_t) - 1);
125   // TODO(ccross): we might need to consider a pointer to the end of a buffer
126   // to be inside the buffer, which means the common case of a pointer to the
127   // beginning of a buffer may keep two ranges live.
128   for (uintptr_t i = begin; i < range.end; i += sizeof(uintptr_t)) {
129     Range ref_range;
130     AllocationInfo* ref_info;
131     if (WordContainsAllocationPtr(i, &ref_range, &ref_info)) {
132       f(ref_range, ref_info);
133     }
134   }
135 }
136 
137 template <class F>
138 inline void HeapWalker::ForEachAllocation(F&& f) {
139   for (auto& it : allocations_) {
140     const Range& range = it.first;
141     HeapWalker::AllocationInfo& allocation = it.second;
142     f(range, allocation);
143   }
144 }
145 
146 }  // namespace android
147 
148 #endif
149