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_H_
31#define GOOGLE_BREAKPAD_COMMON_MEMORY_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_mmap2 mmap
48#define sys_munmap munmap
49#define MAP_ANONYMOUS MAP_ANON
50#else
51#include "third_party/lss/linux_syscall_support.h"
52#endif
53
54namespace google_breakpad {
55
56// This is very simple allocator which fetches pages from the kernel directly.
57// Thus, it can be used even when the heap may be corrupted.
58//
59// There is no free operation. The pages are only freed when the object is
60// destroyed.
61class PageAllocator {
62 public:
63  PageAllocator()
64      : page_size_(getpagesize()),
65        last_(NULL),
66        current_page_(NULL),
67        page_offset_(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 private:
116  uint8_t *GetNPages(size_t num_pages) {
117#if defined(__x86_64__) || defined(__aarch64__)
118    void *a = sys_mmap(NULL, page_size_ * num_pages, PROT_READ | PROT_WRITE,
119                       MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
120#else
121    void *a = sys_mmap2(NULL, page_size_ * num_pages, PROT_READ | PROT_WRITE,
122                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
123#endif
124    if (a == MAP_FAILED)
125      return NULL;
126
127#if defined(MEMORY_SANITIZER)
128    // We need to indicate to MSan that memory allocated through sys_mmap is
129    // initialized, since linux_syscall_support.h doesn't have MSan hooks.
130    __msan_unpoison(a, page_size_ * num_pages);
131#endif
132
133    struct PageHeader *header = reinterpret_cast<PageHeader*>(a);
134    header->next = last_;
135    header->num_pages = num_pages;
136    last_ = header;
137
138    return reinterpret_cast<uint8_t*>(a);
139  }
140
141  void FreeAll() {
142    PageHeader *next;
143
144    for (PageHeader *cur = last_; cur; cur = next) {
145      next = cur->next;
146      sys_munmap(cur, cur->num_pages * page_size_);
147    }
148  }
149
150  struct PageHeader {
151    PageHeader *next;  // pointer to the start of the next set of pages.
152    size_t num_pages;  // the number of pages in this set.
153  };
154
155  const size_t page_size_;
156  PageHeader *last_;
157  uint8_t *current_page_;
158  size_t page_offset_;
159};
160
161// Wrapper to use with STL containers
162template <typename T>
163struct PageStdAllocator : public std::allocator<T> {
164  typedef typename std::allocator<T>::pointer pointer;
165  typedef typename std::allocator<T>::size_type size_type;
166
167  explicit PageStdAllocator(PageAllocator& allocator): allocator_(allocator) {}
168  template <class Other> PageStdAllocator(const PageStdAllocator<Other>& other)
169      : allocator_(other.allocator_) {}
170
171  inline pointer allocate(size_type n, const void* = 0) {
172    return static_cast<pointer>(allocator_.Alloc(sizeof(T) * n));
173  }
174
175  inline void deallocate(pointer, size_type) {
176    // The PageAllocator doesn't free.
177  }
178
179  template <typename U> struct rebind {
180    typedef PageStdAllocator<U> other;
181  };
182
183 private:
184  // Silly workaround for the gcc from Android's ndk (gcc 4.6), which will
185  // otherwise complain that `other.allocator_` is private in the constructor
186  // code.
187  template<typename Other> friend struct PageStdAllocator;
188
189  PageAllocator& allocator_;
190};
191
192// A wasteful vector is a std::vector, except that it allocates memory from a
193// PageAllocator. It's wasteful because, when resizing, it always allocates a
194// whole new array since the PageAllocator doesn't support realloc.
195template<class T>
196class wasteful_vector : public std::vector<T, PageStdAllocator<T> > {
197 public:
198  wasteful_vector(PageAllocator* allocator, unsigned size_hint = 16)
199      : std::vector<T, PageStdAllocator<T> >(PageStdAllocator<T>(*allocator)) {
200    std::vector<T, PageStdAllocator<T> >::reserve(size_hint);
201  }
202};
203
204}  // namespace google_breakpad
205
206inline void* operator new(size_t nbytes,
207                          google_breakpad::PageAllocator& allocator) {
208  return allocator.Alloc(nbytes);
209}
210
211#endif  // GOOGLE_BREAKPAD_COMMON_MEMORY_H_
212