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