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