1 | // Copyright (c) 2009, Google Inc. |
2 | // All rights reserved. |
3 | // |
4 | // Redistribution and use in source and binary forms, with or without |
5 | // modification, are permitted provided that the following conditions are |
6 | // met: |
7 | // |
8 | // * Redistributions of source code must retain the above copyright |
9 | // notice, this list of conditions and the following disclaimer. |
10 | // * Redistributions in binary form must reproduce the above |
11 | // copyright notice, this list of conditions and the following disclaimer |
12 | // in the documentation and/or other materials provided with the |
13 | // distribution. |
14 | // * Neither the name of Google Inc. nor the names of its |
15 | // contributors may be used to endorse or promote products derived from |
16 | // this software without specific prior written permission. |
17 | // |
18 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
19 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
20 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
21 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
22 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
23 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
24 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
25 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
26 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
27 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
28 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
29 | |
30 | #ifndef GOOGLE_BREAKPAD_COMMON_MEMORY_ALLOCATOR_H_ |
31 | #define GOOGLE_BREAKPAD_COMMON_MEMORY_ALLOCATOR_H_ |
32 | |
33 | #include <stdint.h> |
34 | #include <stdlib.h> |
35 | #include <unistd.h> |
36 | #include <sys/mman.h> |
37 | |
38 | #include <memory> |
39 | #include <vector> |
40 | |
41 | #if defined(MEMORY_SANITIZER) |
42 | #include <sanitizer/msan_interface.h> |
43 | #endif |
44 | |
45 | #ifdef __APPLE__ |
46 | #define sys_mmap mmap |
47 | #define sys_munmap munmap |
48 | #define MAP_ANONYMOUS MAP_ANON |
49 | #else |
50 | #include "third_party/lss/linux_syscall_support.h" |
51 | #endif |
52 | |
53 | namespace google_breakpad { |
54 | |
55 | // This is very simple allocator which fetches pages from the kernel directly. |
56 | // Thus, it can be used even when the heap may be corrupted. |
57 | // |
58 | // There is no free operation. The pages are only freed when the object is |
59 | // destroyed. |
60 | class PageAllocator { |
61 | public: |
62 | PageAllocator() |
63 | : page_size_(getpagesize()), |
64 | last_(NULL), |
65 | current_page_(NULL), |
66 | page_offset_(0), |
67 | pages_allocated_(0) { |
68 | } |
69 | |
70 | ~PageAllocator() { |
71 | FreeAll(); |
72 | } |
73 | |
74 | void* Alloc(size_t bytes) { |
75 | if (!bytes) |
76 | return NULL; |
77 | |
78 | if (current_page_ && page_size_ - page_offset_ >= bytes) { |
79 | uint8_t* const ret = current_page_ + page_offset_; |
80 | page_offset_ += bytes; |
81 | if (page_offset_ == page_size_) { |
82 | page_offset_ = 0; |
83 | current_page_ = NULL; |
84 | } |
85 | |
86 | return ret; |
87 | } |
88 | |
89 | const size_t pages = |
90 | (bytes + sizeof(PageHeader) + page_size_ - 1) / page_size_; |
91 | uint8_t* const ret = GetNPages(pages); |
92 | if (!ret) |
93 | return NULL; |
94 | |
95 | page_offset_ = |
96 | (page_size_ - (page_size_ * pages - (bytes + sizeof(PageHeader)))) % |
97 | page_size_; |
98 | current_page_ = page_offset_ ? ret + page_size_ * (pages - 1) : NULL; |
99 | |
100 | return ret + sizeof(PageHeader); |
101 | } |
102 | |
103 | // Checks whether the page allocator owns the passed-in pointer. |
104 | // This method exists for testing pursposes only. |
105 | bool OwnsPointer(const void* p) { |
106 | for (PageHeader* = last_; header; header = header->next) { |
107 | const char* current = reinterpret_cast<char*>(header); |
108 | if ((p >= current) && (p < current + header->num_pages * page_size_)) |
109 | return true; |
110 | } |
111 | |
112 | return false; |
113 | } |
114 | |
115 | unsigned long pages_allocated() { return pages_allocated_; } |
116 | |
117 | private: |
118 | uint8_t* GetNPages(size_t num_pages) { |
119 | void* a = sys_mmap(NULL, page_size_ * num_pages, PROT_READ | PROT_WRITE, |
120 | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); |
121 | if (a == MAP_FAILED) |
122 | return NULL; |
123 | |
124 | #if defined(MEMORY_SANITIZER) |
125 | // We need to indicate to MSan that memory allocated through sys_mmap is |
126 | // initialized, since linux_syscall_support.h doesn't have MSan hooks. |
127 | __msan_unpoison(a, page_size_ * num_pages); |
128 | #endif |
129 | |
130 | struct PageHeader* = reinterpret_cast<PageHeader*>(a); |
131 | header->next = last_; |
132 | header->num_pages = num_pages; |
133 | last_ = header; |
134 | |
135 | pages_allocated_ += num_pages; |
136 | |
137 | return reinterpret_cast<uint8_t*>(a); |
138 | } |
139 | |
140 | void FreeAll() { |
141 | PageHeader* next; |
142 | |
143 | for (PageHeader* cur = last_; cur; cur = next) { |
144 | next = cur->next; |
145 | sys_munmap(cur, cur->num_pages * page_size_); |
146 | } |
147 | } |
148 | |
149 | struct { |
150 | PageHeader* ; // pointer to the start of the next set of pages. |
151 | size_t ; // the number of pages in this set. |
152 | }; |
153 | |
154 | const size_t page_size_; |
155 | PageHeader* last_; |
156 | uint8_t* current_page_; |
157 | size_t page_offset_; |
158 | unsigned long pages_allocated_; |
159 | }; |
160 | |
161 | // Wrapper to use with STL containers |
162 | template <typename T> |
163 | struct PageStdAllocator { |
164 | using AllocatorTraits = std::allocator_traits<std::allocator<T>>; |
165 | using value_type = typename AllocatorTraits::value_type; |
166 | using pointer = typename AllocatorTraits::pointer; |
167 | using difference_type = typename AllocatorTraits::difference_type; |
168 | using size_type = typename AllocatorTraits::size_type; |
169 | |
170 | explicit PageStdAllocator(PageAllocator& allocator) : allocator_(allocator), |
171 | stackdata_(NULL), |
172 | stackdata_size_(0) |
173 | {} |
174 | |
175 | template <class Other> PageStdAllocator(const PageStdAllocator<Other>& other) |
176 | : allocator_(other.allocator_), |
177 | stackdata_(nullptr), |
178 | stackdata_size_(0) |
179 | {} |
180 | |
181 | explicit PageStdAllocator(PageAllocator& allocator, |
182 | pointer stackdata, |
183 | size_type stackdata_size) : allocator_(allocator), |
184 | stackdata_(stackdata), |
185 | stackdata_size_(stackdata_size) |
186 | {} |
187 | |
188 | inline pointer allocate(size_type n, const void* = 0) { |
189 | const size_type size = sizeof(T) * n; |
190 | if (size <= stackdata_size_) { |
191 | return stackdata_; |
192 | } |
193 | return static_cast<pointer>(allocator_.Alloc(size)); |
194 | } |
195 | |
196 | inline void deallocate(pointer, size_type) { |
197 | // The PageAllocator doesn't free. |
198 | } |
199 | |
200 | template <typename U> struct rebind { |
201 | typedef PageStdAllocator<U> other; |
202 | }; |
203 | |
204 | private: |
205 | // Silly workaround for the gcc from Android's ndk (gcc 4.6), which will |
206 | // otherwise complain that `other.allocator_` is private in the constructor |
207 | // code. |
208 | template<typename Other> friend struct PageStdAllocator; |
209 | |
210 | PageAllocator& allocator_; |
211 | pointer stackdata_; |
212 | size_type stackdata_size_; |
213 | }; |
214 | |
215 | // A wasteful vector is a std::vector, except that it allocates memory from a |
216 | // PageAllocator. It's wasteful because, when resizing, it always allocates a |
217 | // whole new array since the PageAllocator doesn't support realloc. |
218 | template<class T> |
219 | class wasteful_vector : public std::vector<T, PageStdAllocator<T> > { |
220 | public: |
221 | wasteful_vector(PageAllocator* allocator, unsigned size_hint = 16) |
222 | : std::vector<T, PageStdAllocator<T> >(PageStdAllocator<T>(*allocator)) { |
223 | std::vector<T, PageStdAllocator<T> >::reserve(size_hint); |
224 | } |
225 | protected: |
226 | wasteful_vector(PageStdAllocator<T> allocator) |
227 | : std::vector<T, PageStdAllocator<T> >(allocator) {} |
228 | }; |
229 | |
230 | // auto_wasteful_vector allocates space on the stack for N entries to avoid |
231 | // using the PageAllocator for small data, while still allowing for larger data. |
232 | template<class T, unsigned int N> |
233 | class auto_wasteful_vector : public wasteful_vector<T> { |
234 | T stackdata_[N]; |
235 | public: |
236 | auto_wasteful_vector(PageAllocator* allocator) |
237 | : wasteful_vector<T>( |
238 | PageStdAllocator<T>(*allocator, |
239 | &stackdata_[0], |
240 | sizeof(stackdata_))) { |
241 | std::vector<T, PageStdAllocator<T> >::reserve(N); |
242 | } |
243 | }; |
244 | |
245 | } // namespace google_breakpad |
246 | |
247 | inline void* operator new(size_t nbytes, |
248 | google_breakpad::PageAllocator& allocator) { |
249 | return allocator.Alloc(nbytes); |
250 | } |
251 | |
252 | #endif // GOOGLE_BREAKPAD_COMMON_MEMORY_ALLOCATOR_H_ |
253 | |