courgette/memory_allocator.h

   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.
   4
   5 #ifndef COURGETTE_MEMORY_ALLOCATOR_H_
   6 #define COURGETTE_MEMORY_ALLOCATOR_H_
   7
   8 #include <stddef.h>
   9 #include <stdint.h>
  10 #include <stdlib.h>
  11
  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"
  17
  18 #ifndef NDEBUG
  19
  20 // A helper class to track down call sites that are not handling error cases.
  21 template<class T>
  22 class CheckReturnValue {
  23  public:
  24   // Not marked explicit on purpose.
  25   CheckReturnValue(T value) : value_(value), checked_(false) {  // NOLINT
  26   }
  27   CheckReturnValue(const CheckReturnValue& other)
  28       : value_(other.value_), checked_(other.checked_) {
  29     other.checked_ = true;
  30   }
  31
  32   CheckReturnValue& operator=(const CheckReturnValue& other) {
  33     if (this != &other) {
  34       DCHECK(checked_);
  35       value_ = other.value_;
  36       checked_ = other.checked_;
  37       other.checked_ = true;
  38     }
  39     return *this;
  40   }
  41
  42   ~CheckReturnValue() {
  43     DCHECK(checked_);
  44   }
  45
  46   operator const T&() const {
  47     checked_ = true;
  48     return value_;
  49   }
  50
  51  private:
  52   T value_;
  53   mutable bool checked_;
  54 };
  55 typedef CheckReturnValue<bool> CheckBool;
  56 #else
  57 typedef bool CheckBool;
  58 #endif
  59
  60 namespace courgette {
  61
  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) {
  67   void* ram = nullptr;
  68   return base::UncheckedMalloc(sizeof(T), &ram) ? new (ram) T(args...)
  69                                                 : nullptr;
  70 }
  71
  72 // Complement of UncheckedNew(): destructs |object| and releases its memory.
  73 template <class T>
  74 void UncheckedDelete(T* object) {
  75   if (object) {
  76     object->T::~T();
  77     free(object);
  78   }
  79 }
  80
  81 // A deleter for std::unique_ptr that will delete the object via
  82 // UncheckedDelete().
  83 template <class T>
  84 struct UncheckedDeleter {
  85   inline void operator()(T* ptr) const { UncheckedDelete(ptr); }
  86 };
  87
  88 #if defined(OS_WIN)
  89
  90 // Manages a read/write virtual mapping of a physical file.
  91 class FileMapping {
  92  public:
  93   FileMapping();
  94   ~FileMapping();
  95
  96   // Map a file from beginning to |size|.
  97   bool Create(HANDLE file, size_t size);
  98   void Close();
  99
 100   // Returns true iff a mapping has been created.
 101   bool valid() const;
 102
 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.
 105   void* view() const;
 106
 107  protected:
 108   bool InitializeView(size_t size);
 109
 110   HANDLE mapping_;
 111   void* view_;
 112 };
 113
 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.
 118 class TempMapping {
 119  public:
 120   TempMapping();
 121   ~TempMapping();
 122
 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);
 126
 127   // Returns a writable pointer to the reserved memory.
 128   void* memory() const;
 129
 130   // Returns true if the mapping is valid and memory is available.
 131   bool valid() const;
 132
 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);
 137
 138  protected:
 139   base::File file_;
 140   FileMapping mapping_;
 141 };
 142
 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.
 153 template<class T>
 154 class MemoryAllocator {
 155  public:
 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;
 163
 164   // Each allocation is tagged with a single byte so that we know how to
 165   // deallocate it.
 166   enum AllocationType : uint8_t {
 167     HEAP_ALLOCATION = 0xF0,  // Non-trivial constants to detect corruption.
 168     FILE_ALLOCATION = 0x0F,
 169   };
 170
 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;
 177
 178   template<class OtherT>
 179   struct rebind {
 180     // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
 181     typedef MemoryAllocator<OtherT> other;
 182   };
 183
 184   MemoryAllocator() {}
 185
 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
 189   }
 190
 191   template <class OtherT>
 192   MemoryAllocator(const MemoryAllocator<OtherT>& other) {  // NOLINT
 193   }
 194
 195   ~MemoryAllocator() {
 196   }
 197
 198   void deallocate(pointer ptr, size_type size) {
 199     uint8_t* mem = reinterpret_cast<uint8_t*>(ptr);
 200     mem -= sizeof(T);
 201     if (mem[0] == HEAP_ALLOCATION)
 202       free(mem);
 203     else if (mem[0] == FILE_ALLOCATION)
 204       UncheckedDelete(TempMapping::GetMappingFromPtr(mem));
 205     else
 206       LOG(FATAL);
 207   }
 208
 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.
 214     count++;
 215
 216     if (count > max_size())
 217       return NULL;
 218
 219     size_type bytes = count * sizeof(T);
 220     uint8_t* mem = NULL;
 221
 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);
 226     } else {
 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>();
 230       if (mapping) {
 231         if (mapping->Initialize(bytes)) {
 232           mem = reinterpret_cast<uint8_t*>(mapping->memory());
 233           mem[0] = static_cast<uint8_t>(FILE_ALLOCATION);
 234         } else {
 235           UncheckedDelete(mapping);
 236         }
 237       }
 238     }
 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);
 242     }
 243     return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : NULL;
 244   }
 245
 246   pointer allocate(size_type count, const void* hint) {
 247     return allocate(count);
 248   }
 249
 250   void construct(pointer ptr, const T& value) {
 251     ::new(ptr) T(value);
 252   }
 253
 254   void destroy(pointer ptr) {
 255     ptr->~T();
 256   }
 257
 258   size_type max_size() const {
 259     size_type count = static_cast<size_type>(-1) / sizeof(T);
 260     return (0 < count ? count : 1);
 261   }
 262 };
 263
 264 #else  // OS_WIN
 265
 266 // On Mac, Linux, we use a bare bones implementation that only does
 267 // heap allocations.
 268 template<class T>
 269 class MemoryAllocator {
 270  public:
 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;
 278
 279   template<class OtherT>
 280   struct rebind {
 281     // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
 282     typedef MemoryAllocator<OtherT> other;
 283   };
 284
 285   MemoryAllocator() {
 286   }
 287
 288   explicit MemoryAllocator(const MemoryAllocator<T>& other) {
 289   }
 290
 291   template<class OtherT>
 292   explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
 293   }
 294
 295   ~MemoryAllocator() {
 296   }
 297
 298   void deallocate(pointer ptr, size_type size) { free(ptr); }
 299
 300   pointer allocate(size_type count) {
 301     if (count > max_size())
 302       return NULL;
 303     pointer result = nullptr;
 304     return base::UncheckedMalloc(count * sizeof(T),
 305                                  reinterpret_cast<void**>(&result))
 306                ? result
 307                : nullptr;
 308   }
 309
 310   pointer allocate(size_type count, const void* hint) {
 311     return allocate(count);
 312   }
 313
 314   void construct(pointer ptr, const T& value) {
 315     ::new(ptr) T(value);
 316   }
 317
 318   void destroy(pointer ptr) {
 319     ptr->~T();
 320   }
 321
 322   size_type max_size() const {
 323     size_type count = static_cast<size_type>(-1) / sizeof(T);
 324     return (0 < count ? count : 1);
 325   }
 326 };
 327
 328 #endif  // OS_WIN
 329
 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 {
 337  public:
 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);
 341
 342   NoThrowBuffer() : buffer_(NULL), size_(0), alloc_size_(0) {
 343   }
 344
 345   ~NoThrowBuffer() {
 346     clear();
 347   }
 348
 349   void clear() {
 350     if (buffer_) {
 351       alloc_.deallocate(buffer_, alloc_size_);
 352       buffer_ = NULL;
 353       size_ = 0;
 354       alloc_size_ = 0;
 355     }
 356   }
 357
 358   bool empty() const {
 359     return size_ == 0;
 360   }
 361
 362   CheckBool reserve(size_t size) WARN_UNUSED_RESULT {
 363     if (failed())
 364       return false;
 365
 366     if (size <= alloc_size_)
 367       return true;
 368
 369     if (size < kStartSize)
 370       size = kStartSize;
 371
 372     T* new_buffer = alloc_.allocate(size);
 373     if (!new_buffer) {
 374       clear();
 375       alloc_size_ = kAllocationFailure;
 376     } else {
 377       if (buffer_) {
 378         memcpy(new_buffer, buffer_, size_ * sizeof(T));
 379         alloc_.deallocate(buffer_, alloc_size_);
 380       }
 381       buffer_ = new_buffer;
 382       alloc_size_ = size;
 383     }
 384
 385     return !failed();
 386   }
 387
 388   CheckBool append(const T* data, size_t size) WARN_UNUSED_RESULT {
 389     if (failed())
 390       return false;
 391
 392     if (size > alloc_.max_size() - size_)
 393       return false;
 394
 395     if (!size)
 396       return true;
 397
 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_);
 401
 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) {
 407           new_size *= 2;
 408         } else {
 409           new_size = max_size;
 410         }
 411       }
 412       if (!reserve(new_size))
 413         return false;
 414     }
 415
 416     memcpy(buffer_ + size_, data, size * sizeof(T));
 417     size_ += size;
 418
 419     return true;
 420   }
 421
 422   CheckBool resize(size_t size, const T& init_value) WARN_UNUSED_RESULT {
 423     if (size > size_) {
 424       if (!reserve(size))
 425         return false;
 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.
 431     }
 432
 433     size_ = size;
 434
 435     return true;
 436   }
 437
 438   CheckBool push_back(const T& item) WARN_UNUSED_RESULT {
 439     return append(&item, 1);
 440   }
 441
 442   const T& back() const {
 443     return buffer_[size_ - 1];
 444   }
 445
 446   T& back() {
 447     return buffer_[size_ - 1];
 448   }
 449
 450   const T* begin() const {
 451     if (!size_)
 452       return NULL;
 453     return buffer_;
 454   }
 455
 456   T* begin() {
 457     if (!size_)
 458       return NULL;
 459     return buffer_;
 460   }
 461
 462   const T* end() const {
 463     if (!size_)
 464       return NULL;
 465     return buffer_ + size_;
 466   }
 467
 468   T* end() {
 469     if (!size_)
 470       return NULL;
 471     return buffer_ + size_;
 472   }
 473
 474   const T& operator[](size_t index) const {
 475     DCHECK(index < size_);
 476     return buffer_[index];
 477   }
 478
 479   T& operator[](size_t index) {
 480     DCHECK(index < size_);
 481     return buffer_[index];
 482   }
 483
 484   size_t size() const {
 485     return size_;
 486   }
 487
 488   size_t capacity() const {
 489     return alloc_size_;
 490   }
 491
 492   T* data() const {
 493     return buffer_;
 494   }
 495
 496   // Returns true if an allocation failure has ever occurred for this object.
 497   bool failed() const {
 498     return alloc_size_ == kAllocationFailure;
 499   }
 500
 501  protected:
 502   T* buffer_;
 503   size_t size_;  // how much of the buffer we're using.
 504   size_t alloc_size_;  // how much space we have allocated.
 505   Allocator alloc_;
 506 };
 507
 508 }  // namespace courgette
 509
 510 #endif  // COURGETTE_MEMORY_ALLOCATOR_H_