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 <memory>
   9
  10 #include "base/basictypes.h"
  11 #include "base/file_path.h"
  12 #include "base/logging.h"
  13 #include "base/platform_file.h"
  14
  15 #ifndef NDEBUG
  16
  17 // A helper class to track down call sites that are not handling error cases.
  18 template<class T>
  19 class CheckReturnValue {
  20  public:
  21   // Not marked explicit on purpose.
  22   CheckReturnValue(T value) : value_(value), checked_(false) {  // NOLINT
  23   }
  24   CheckReturnValue(const CheckReturnValue& other)
  25       : value_(other.value_), checked_(other.checked_) {
  26     other.checked_ = true;
  27   }
  28
  29   CheckReturnValue& operator=(const CheckReturnValue& other) {
  30     if (this != &other) {
  31       DCHECK(checked_);
  32       value_ = other.value_;
  33       checked_ = other.checked_;
  34       other.checked_ = true;
  35     }
  36   }
  37
  38   ~CheckReturnValue() {
  39     DCHECK(checked_);
  40   }
  41
  42   operator const T&() const {
  43     checked_ = true;
  44     return value_;
  45   }
  46
  47  private:
  48   T value_;
  49   mutable bool checked_;
  50 };
  51 typedef CheckReturnValue<bool> CheckBool;
  52 #else
  53 typedef bool CheckBool;
  54 #endif
  55
  56 namespace courgette {
  57
  58 #ifdef OS_WIN
  59
  60 // Manages a temporary file.  The file is created in the %TEMP% folder and
  61 // is deleted when the file handle is closed.
  62 // NOTE: Since the file will be used as backing for a memory allocation,
  63 // it will never be so big that size_t cannot represent its size.
  64 class TempFile {
  65  public:
  66   TempFile();
  67   ~TempFile();
  68
  69   bool Create();
  70   void Close();
  71   bool SetSize(size_t size);
  72
  73   // Returns true iff the temp file is currently open.
  74   bool valid() const;
  75
  76   // Returns the handle of the temporary file or INVALID_HANDLE_VALUE if
  77   // a temp file has not been created.
  78   base::PlatformFile handle() const;
  79
  80  protected:
  81   base::PlatformFile file_;
  82 };
  83
  84 // Manages a read/write virtual mapping of a physical file.
  85 class FileMapping {
  86  public:
  87   FileMapping();
  88   ~FileMapping();
  89
  90   // Map a file from beginning to |size|.
  91   bool Create(HANDLE file, size_t size);
  92   void Close();
  93
  94   // Returns true iff a mapping has been created.
  95   bool valid() const;
  96
  97   // Returns a writable pointer to the beginning of the memory mapped file.
  98   // If Create has not been called successfully, return value is NULL.
  99   void* view() const;
 100
 101  protected:
 102   bool InitializeView(size_t size);
 103
 104   HANDLE mapping_;
 105   void* view_;
 106 };
 107
 108 // Manages a temporary file and a memory mapping of the temporary file.
 109 // The memory that this class manages holds a pointer back to the TempMapping
 110 // object itself, so that given a memory pointer allocated by this class,
 111 // you can get a pointer to the TempMapping instance that owns that memory.
 112 class TempMapping {
 113  public:
 114   TempMapping();
 115   ~TempMapping();
 116
 117   // Creates a temporary file of size |size| and maps it into the current
 118   // process's address space.
 119   bool Initialize(size_t size);
 120
 121   // Returns a writable pointer to the reserved memory.
 122   void* memory() const;
 123
 124   // Returns true if the mapping is valid and memory is available.
 125   bool valid() const;
 126
 127   // Returns a pointer to the TempMapping instance that allocated the |mem|
 128   // block of memory.  It's the callers responsibility to make sure that
 129   // the memory block was allocated by the TempMapping class.
 130   static TempMapping* GetMappingFromPtr(void* mem);
 131
 132  protected:
 133   TempFile file_;
 134   FileMapping mapping_;
 135 };
 136
 137 // A memory allocator class that allocates memory either from the heap or via a
 138 // temporary file.  The interface is STL inspired but the class does not throw
 139 // STL exceptions on allocation failure.  Instead it returns NULL.
 140 // A file allocation will be made if either the requested memory size exceeds
 141 // |kMaxHeapAllocationSize| or if a heap allocation fails.
 142 // Allocating the memory as a mapping of a temporary file solves the problem
 143 // that there might not be enough physical memory and pagefile to support the
 144 // allocation.  This can happen because these resources are too small, or
 145 // already committed to other processes.  Provided there is enough disk, the
 146 // temporary file acts like a pagefile that other processes can't access.
 147 template<class T>
 148 class MemoryAllocator {
 149  public:
 150   typedef T value_type;
 151   typedef value_type* pointer;
 152   typedef value_type& reference;
 153   typedef const value_type* const_pointer;
 154   typedef const value_type& const_reference;
 155   typedef size_t size_type;
 156   typedef ptrdiff_t difference_type;
 157
 158   // Each allocation is tagged with a single byte so that we know how to
 159   // deallocate it.
 160   enum AllocationType {
 161     HEAP_ALLOCATION,
 162     FILE_ALLOCATION,
 163   };
 164
 165   // 5MB is the maximum heap allocation size that we'll attempt.
 166   // When applying a patch for Chrome 10.X we found that at this
 167   // threshold there were 17 allocations higher than this threshold
 168   // (largest at 136MB) 10 allocations just below the threshold and 6362
 169   // smaller allocations.
 170   static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5;
 171
 172   template<class OtherT>
 173   struct rebind {
 174     // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
 175     typedef MemoryAllocator<OtherT> other;
 176   };
 177
 178   MemoryAllocator() _THROW0() {
 179   }
 180
 181   // We can't use an explicit constructor here, as dictated by our style guide.
 182   // The implementation of basic_string in Visual Studio 2010 prevents this.
 183   MemoryAllocator(const MemoryAllocator<T>& other) _THROW0() {  // NOLINT
 184   }
 185
 186   template<class OtherT>
 187   MemoryAllocator(const MemoryAllocator<OtherT>& other) _THROW0() {  // NOLINT
 188   }
 189
 190   ~MemoryAllocator() {
 191   }
 192
 193   void deallocate(pointer ptr, size_type size) {
 194     uint8* mem = reinterpret_cast<uint8*>(ptr);
 195     mem -= sizeof(T);
 196     if (mem[0] == HEAP_ALLOCATION) {
 197       delete [] mem;
 198     } else {
 199       DCHECK_EQ(static_cast<uint8>(FILE_ALLOCATION), mem[0]);
 200       TempMapping* mapping = TempMapping::GetMappingFromPtr(mem);
 201       delete mapping;
 202     }
 203   }
 204
 205   pointer allocate(size_type count) {
 206     // We use the first byte of each allocation to mark the allocation type.
 207     // However, so that the allocation is properly aligned, we allocate an
 208     // extra element and then use the first byte of the first element
 209     // to mark the allocation type.
 210     count++;
 211
 212     if (count > max_size())
 213       return NULL;
 214
 215     size_type bytes = count * sizeof(T);
 216     uint8* mem = NULL;
 217
 218     // First see if we can do this allocation on the heap.
 219     if (count < kMaxHeapAllocationSize)
 220       mem = new(std::nothrow) uint8[bytes];
 221     if (mem != NULL) {
 222       mem[0] = static_cast<uint8>(HEAP_ALLOCATION);
 223     } else {
 224       // If either the heap allocation failed or the request exceeds the
 225       // max heap allocation threshold, we back the allocation with a temp file.
 226       TempMapping* mapping = new(std::nothrow) TempMapping();
 227       if (mapping && mapping->Initialize(bytes)) {
 228         mem = reinterpret_cast<uint8*>(mapping->memory());
 229         mem[0] = static_cast<uint8>(FILE_ALLOCATION);
 230       }
 231     }
 232     return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : NULL;
 233   }
 234
 235   pointer allocate(size_type count, const void* hint) {
 236     return allocate(count);
 237   }
 238
 239   void construct(pointer ptr, const T& value) {
 240     ::new(ptr) T(value);
 241   }
 242
 243   void destroy(pointer ptr) {
 244     ptr->~T();
 245   }
 246
 247   size_type max_size() const _THROW0() {
 248     size_type count = static_cast<size_type>(-1) / sizeof(T);
 249     return (0 < count ? count : 1);
 250   }
 251 };
 252
 253 #else  // OS_WIN
 254
 255 // On Mac, Linux, we use a bare bones implementation that only does
 256 // heap allocations.
 257 template<class T>
 258 class MemoryAllocator {
 259  public:
 260   typedef T value_type;
 261   typedef value_type* pointer;
 262   typedef value_type& reference;
 263   typedef const value_type* const_pointer;
 264   typedef const value_type& const_reference;
 265   typedef size_t size_type;
 266   typedef ptrdiff_t difference_type;
 267
 268   template<class OtherT>
 269   struct rebind {
 270     // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
 271     typedef MemoryAllocator<OtherT> other;
 272   };
 273
 274   MemoryAllocator() {
 275   }
 276
 277   explicit MemoryAllocator(const MemoryAllocator<T>& other) {
 278   }
 279
 280   template<class OtherT>
 281   explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
 282   }
 283
 284   ~MemoryAllocator() {
 285   }
 286
 287   void deallocate(pointer ptr, size_type size) {
 288     delete [] ptr;
 289   }
 290
 291   pointer allocate(size_type count) {
 292     if (count > max_size())
 293       return NULL;
 294     return reinterpret_cast<pointer>(
 295         new(std::nothrow) uint8[count * sizeof(T)]);
 296   }
 297
 298   pointer allocate(size_type count, const void* hint) {
 299     return allocate(count);
 300   }
 301
 302   void construct(pointer ptr, const T& value) {
 303     ::new(ptr) T(value);
 304   }
 305
 306   void destroy(pointer ptr) {
 307     ptr->~T();
 308   }
 309
 310   size_type max_size() const {
 311     size_type count = static_cast<size_type>(-1) / sizeof(T);
 312     return (0 < count ? count : 1);
 313   }
 314 };
 315
 316 #endif  // OS_WIN
 317
 318 // Manages a growable buffer.  The buffer allocation is done by the
 319 // MemoryAllocator class.  This class will not throw exceptions so call sites
 320 // must be prepared to handle memory allocation failures.
 321 // The interface is STL inspired to avoid having to make too many changes
 322 // to code that previously was using STL.
 323 template<typename T, class Allocator = MemoryAllocator<T> >
 324 class NoThrowBuffer {
 325  public:
 326   typedef T value_type;
 327   static const size_t kAllocationFailure = 0xffffffff;
 328   static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T);
 329
 330   NoThrowBuffer() : buffer_(NULL), size_(0), alloc_size_(0) {
 331   }
 332
 333   ~NoThrowBuffer() {
 334     clear();
 335   }
 336
 337   void clear() {
 338     if (buffer_) {
 339       alloc_.deallocate(buffer_, alloc_size_);
 340       buffer_ = NULL;
 341       size_ = 0;
 342       alloc_size_ = 0;
 343     }
 344   }
 345
 346   bool empty() const {
 347     return size_ == 0;
 348   }
 349
 350   CheckBool reserve(size_t size) WARN_UNUSED_RESULT {
 351     if (failed())
 352       return false;
 353
 354     if (size <= alloc_size_)
 355       return true;
 356
 357     if (size < kStartSize)
 358       size = kStartSize;
 359
 360     T* new_buffer = alloc_.allocate(size);
 361     if (!new_buffer) {
 362       clear();
 363       alloc_size_ = kAllocationFailure;
 364     } else {
 365       if (buffer_) {
 366         memcpy(new_buffer, buffer_, size_ * sizeof(T));
 367         alloc_.deallocate(buffer_, alloc_size_);
 368       }
 369       buffer_ = new_buffer;
 370       alloc_size_ = size;
 371     }
 372
 373     return !failed();
 374   }
 375
 376   CheckBool append(const T* data, size_t size) WARN_UNUSED_RESULT {
 377     if (failed())
 378       return false;
 379
 380     if (size > alloc_.max_size() - size_)
 381       return false;
 382
 383     if (!size)
 384       return true;
 385
 386     if ((alloc_size_ - size_) < size) {
 387       const size_t max_size = alloc_.max_size();
 388       size_t new_size = alloc_size_ ? alloc_size_ : kStartSize;
 389       while (new_size < size_ + size) {
 390         if (new_size < max_size - new_size) {
 391           new_size *= 2;
 392         } else {
 393           new_size = max_size;
 394         }
 395       }
 396       if (!reserve(new_size))
 397         return false;
 398     }
 399
 400     memcpy(buffer_ + size_, data, size * sizeof(T));
 401     size_ += size;
 402
 403     return true;
 404   }
 405
 406   CheckBool resize(size_t size, const T& init_value) WARN_UNUSED_RESULT {
 407     if (size > size_) {
 408       if (!reserve(size))
 409         return false;
 410       for (size_t i = size_; i < size; ++i)
 411         buffer_[i] = init_value;
 412     } else if (size < size_) {
 413       // TODO(tommi): Should we allocate a new, smaller buffer?
 414       // It might be faster for us to simply change the size.
 415     }
 416
 417     size_ = size;
 418
 419     return true;
 420   }
 421
 422   CheckBool push_back(const T& item) WARN_UNUSED_RESULT {
 423     return append(&item, 1);
 424   }
 425
 426   const T& back() const {
 427     return buffer_[size_ - 1];
 428   }
 429
 430   T& back() {
 431     return buffer_[size_ - 1];
 432   }
 433
 434   const T* begin() const {
 435     if (!size_)
 436       return NULL;
 437     return &buffer_[0];
 438   }
 439
 440   T* begin() {
 441     if (!size_)
 442       return NULL;
 443     return &buffer_[0];
 444   }
 445
 446   const T* end() const {
 447     if (!size_)
 448       return NULL;
 449     return &buffer_[size_ - 1];
 450   }
 451
 452   T* end() {
 453     if (!size_)
 454       return NULL;
 455     return &buffer_[size_ - 1];
 456   }
 457
 458   const T& operator[](size_t index) const {
 459     DCHECK(index < size_);
 460     return buffer_[index];
 461   }
 462
 463   T& operator[](size_t index) {
 464     DCHECK(index < size_);
 465     return buffer_[index];
 466   }
 467
 468   size_t size() const {
 469     return size_;
 470   }
 471
 472   T* data() const {
 473     return buffer_;
 474   }
 475
 476   // Returns true if an allocation failure has ever occurred for this object.
 477   bool failed() const {
 478     return alloc_size_ == kAllocationFailure;
 479   }
 480
 481  protected:
 482   T* buffer_;
 483   size_t size_;  // how much of the buffer we're using.
 484   size_t alloc_size_;  // how much space we have allocated.
 485   Allocator alloc_;
 486 };
 487
 488 }  // namespace courgette
 489
 490 #endif  // COURGETTE_MEMORY_ALLOCATOR_H_