1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #ifndef COURGETTE_MEMORY_ALLOCATOR_H_
6 #define COURGETTE_MEMORY_ALLOCATOR_H_
12 #include "base/compiler_specific.h"
13 #include "base/files/file.h"
14 #include "base/files/file_path.h"
15 #include "base/logging.h"
16 #include "base/process/memory.h"
20 // A helper class to track down call sites that are not handling error cases.
22 class CheckReturnValue {
24 // Not marked explicit on purpose.
25 CheckReturnValue(T value) : value_(value), checked_(false) { // NOLINT
27 CheckReturnValue(const CheckReturnValue& other)
28 : value_(other.value_), checked_(other.checked_) {
29 other.checked_ = true;
32 CheckReturnValue& operator=(const CheckReturnValue& other) {
35 value_ = other.value_;
36 checked_ = other.checked_;
37 other.checked_ = true;
46 operator const T&() const {
53 mutable bool checked_;
55 typedef CheckReturnValue<bool> CheckBool;
57 typedef bool CheckBool;
62 // Allocates memory for an instance of type T, instantiates an object in that
63 // memory with arguments |args| (of type ArgTypes), and returns the constructed
64 // instance. Returns null if allocation fails.
65 template <class T, class... ArgTypes>
66 T* UncheckedNew(ArgTypes... args) {
68 return base::UncheckedMalloc(sizeof(T), &ram) ? new (ram) T(args...)
72 // Complement of UncheckedNew(): destructs |object| and releases its memory.
74 void UncheckedDelete(T* object) {
81 // A deleter for std::unique_ptr that will delete the object via
84 struct UncheckedDeleter {
85 inline void operator()(T* ptr) const { UncheckedDelete(ptr); }
90 // Manages a read/write virtual mapping of a physical file.
96 // Map a file from beginning to |size|.
97 bool Create(HANDLE file, size_t size);
100 // Returns true iff a mapping has been created.
103 // Returns a writable pointer to the beginning of the memory mapped file.
104 // If Create has not been called successfully, return value is NULL.
108 bool InitializeView(size_t size);
114 // Manages a temporary file and a memory mapping of the temporary file.
115 // The memory that this class manages holds a pointer back to the TempMapping
116 // object itself, so that given a memory pointer allocated by this class,
117 // you can get a pointer to the TempMapping instance that owns that memory.
123 // Creates a temporary file of size |size| and maps it into the current
124 // process's address space.
125 bool Initialize(size_t size);
127 // Returns a writable pointer to the reserved memory.
128 void* memory() const;
130 // Returns true if the mapping is valid and memory is available.
133 // Returns a pointer to the TempMapping instance that allocated the |mem|
134 // block of memory. It's the callers responsibility to make sure that
135 // the memory block was allocated by the TempMapping class.
136 static TempMapping* GetMappingFromPtr(void* mem);
140 FileMapping mapping_;
143 // A memory allocator class that allocates memory either from the heap or via a
144 // temporary file. The interface is STL inspired but the class does not throw
145 // STL exceptions on allocation failure. Instead it returns NULL.
146 // A file allocation will be made if either the requested memory size exceeds
147 // |kMaxHeapAllocationSize| or if a heap allocation fails.
148 // Allocating the memory as a mapping of a temporary file solves the problem
149 // that there might not be enough physical memory and pagefile to support the
150 // allocation. This can happen because these resources are too small, or
151 // already committed to other processes. Provided there is enough disk, the
152 // temporary file acts like a pagefile that other processes can't access.
154 class MemoryAllocator {
156 typedef T value_type;
157 typedef value_type* pointer;
158 typedef value_type& reference;
159 typedef const value_type* const_pointer;
160 typedef const value_type& const_reference;
161 typedef size_t size_type;
162 typedef ptrdiff_t difference_type;
164 // Each allocation is tagged with a single byte so that we know how to
166 enum AllocationType : uint8_t {
167 HEAP_ALLOCATION = 0xF0, // Non-trivial constants to detect corruption.
168 FILE_ALLOCATION = 0x0F,
171 // 5MB is the maximum heap allocation size that we'll attempt.
172 // When applying a patch for Chrome 10.X we found that at this
173 // threshold there were 17 allocations higher than this threshold
174 // (largest at 136MB) 10 allocations just below the threshold and 6362
175 // smaller allocations.
176 static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5;
178 template<class OtherT>
180 // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
181 typedef MemoryAllocator<OtherT> other;
186 // We can't use an explicit constructor here, as dictated by our style guide.
187 // The implementation of basic_string in Visual Studio 2010 prevents this.
188 MemoryAllocator(const MemoryAllocator<T>& other) { // NOLINT
191 template <class OtherT>
192 MemoryAllocator(const MemoryAllocator<OtherT>& other) { // NOLINT
198 void deallocate(pointer ptr, size_type size) {
199 uint8_t* mem = reinterpret_cast<uint8_t*>(ptr);
201 if (mem[0] == HEAP_ALLOCATION)
203 else if (mem[0] == FILE_ALLOCATION)
204 UncheckedDelete(TempMapping::GetMappingFromPtr(mem));
209 pointer allocate(size_type count) {
210 // We use the first byte of each allocation to mark the allocation type.
211 // However, so that the allocation is properly aligned, we allocate an
212 // extra element and then use the first byte of the first element
213 // to mark the allocation type.
216 if (count > max_size())
219 size_type bytes = count * sizeof(T);
222 // First see if we can do this allocation on the heap.
223 if (count < kMaxHeapAllocationSize &&
224 base::UncheckedMalloc(bytes, reinterpret_cast<void**>(&mem))) {
225 mem[0] = static_cast<uint8_t>(HEAP_ALLOCATION);
227 // Back the allocation with a temp file if either the request exceeds the
228 // max heap allocation threshold or the heap allocation failed.
229 TempMapping* mapping = UncheckedNew<TempMapping>();
231 if (mapping->Initialize(bytes)) {
232 mem = reinterpret_cast<uint8_t*>(mapping->memory());
233 mem[0] = static_cast<uint8_t>(FILE_ALLOCATION);
235 UncheckedDelete(mapping);
239 // If the above fails (e.g. because we are in a sandbox), just try the heap.
240 if (!mem && base::UncheckedMalloc(bytes, reinterpret_cast<void**>(&mem))) {
241 mem[0] = static_cast<uint8_t>(HEAP_ALLOCATION);
243 return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : NULL;
246 pointer allocate(size_type count, const void* hint) {
247 return allocate(count);
250 void construct(pointer ptr, const T& value) {
254 void destroy(pointer ptr) {
258 size_type max_size() const {
259 size_type count = static_cast<size_type>(-1) / sizeof(T);
260 return (0 < count ? count : 1);
266 // On Mac, Linux, we use a bare bones implementation that only does
269 class MemoryAllocator {
271 typedef T value_type;
272 typedef value_type* pointer;
273 typedef value_type& reference;
274 typedef const value_type* const_pointer;
275 typedef const value_type& const_reference;
276 typedef size_t size_type;
277 typedef ptrdiff_t difference_type;
279 template<class OtherT>
281 // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
282 typedef MemoryAllocator<OtherT> other;
288 explicit MemoryAllocator(const MemoryAllocator<T>& other) {
291 template<class OtherT>
292 explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
298 void deallocate(pointer ptr, size_type size) { free(ptr); }
300 pointer allocate(size_type count) {
301 if (count > max_size())
303 pointer result = nullptr;
304 return base::UncheckedMalloc(count * sizeof(T),
305 reinterpret_cast<void**>(&result))
310 pointer allocate(size_type count, const void* hint) {
311 return allocate(count);
314 void construct(pointer ptr, const T& value) {
318 void destroy(pointer ptr) {
322 size_type max_size() const {
323 size_type count = static_cast<size_type>(-1) / sizeof(T);
324 return (0 < count ? count : 1);
330 // Manages a growable buffer. The buffer allocation is done by the
331 // MemoryAllocator class. This class will not throw exceptions so call sites
332 // must be prepared to handle memory allocation failures.
333 // The interface is STL inspired to avoid having to make too many changes
334 // to code that previously was using STL.
335 template<typename T, class Allocator = MemoryAllocator<T> >
336 class NoThrowBuffer {
338 typedef T value_type;
339 static const size_t kAllocationFailure = 0xffffffff;
340 static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T);
342 NoThrowBuffer() : buffer_(NULL), size_(0), alloc_size_(0) {
351 alloc_.deallocate(buffer_, alloc_size_);
362 CheckBool reserve(size_t size) WARN_UNUSED_RESULT {
366 if (size <= alloc_size_)
369 if (size < kStartSize)
372 T* new_buffer = alloc_.allocate(size);
375 alloc_size_ = kAllocationFailure;
378 memcpy(new_buffer, buffer_, size_ * sizeof(T));
379 alloc_.deallocate(buffer_, alloc_size_);
381 buffer_ = new_buffer;
388 CheckBool append(const T* data, size_t size) WARN_UNUSED_RESULT {
392 if (size > alloc_.max_size() - size_)
398 // Disallow source range from overlapping with buffer_, since in this case
399 // reallocation would cause use-after-free.
400 DCHECK(data + size <= buffer_ || data >= buffer_ + alloc_size_);
402 if ((alloc_size_ - size_) < size) {
403 const size_t max_size = alloc_.max_size();
404 size_t new_size = alloc_size_ ? alloc_size_ : kStartSize;
405 while (new_size < size_ + size) {
406 if (new_size < max_size - new_size) {
412 if (!reserve(new_size))
416 memcpy(buffer_ + size_, data, size * sizeof(T));
422 CheckBool resize(size_t size, const T& init_value) WARN_UNUSED_RESULT {
426 for (size_t i = size_; i < size; ++i)
427 buffer_[i] = init_value;
428 } else if (size < size_) {
429 // TODO(tommi): Should we allocate a new, smaller buffer?
430 // It might be faster for us to simply change the size.
438 CheckBool push_back(const T& item) WARN_UNUSED_RESULT {
439 return append(&item, 1);
442 const T& back() const {
443 return buffer_[size_ - 1];
447 return buffer_[size_ - 1];
450 const T* begin() const {
462 const T* end() const {
465 return buffer_ + size_;
471 return buffer_ + size_;
474 const T& operator[](size_t index) const {
475 DCHECK(index < size_);
476 return buffer_[index];
479 T& operator[](size_t index) {
480 DCHECK(index < size_);
481 return buffer_[index];
484 size_t size() const {
488 size_t capacity() const {
496 // Returns true if an allocation failure has ever occurred for this object.
497 bool failed() const {
498 return alloc_size_ == kAllocationFailure;
503 size_t size_; // how much of the buffer we're using.
504 size_t alloc_size_; // how much space we have allocated.
508 } // namespace courgette
510 #endif // COURGETTE_MEMORY_ALLOCATOR_H_