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
53namespace 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.
60class 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* header = 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* header = 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 PageHeader {
150 PageHeader* next; // pointer to the start of the next set of pages.
151 size_t num_pages; // 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
162template <typename T>
163struct 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.
218template<class T>
219class 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.
232template<class T, unsigned int N>
233class 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
247inline 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