courgette/memory_allocator.h

   1 // Copyright 2011 The Chromium Authors
   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 #include <string.h>
  12
  13 #include "base/files/file.h"
  14 #include "base/logging.h"
  15 #include "base/memory/raw_ptr.h"
  16 #include "base/process/memory.h"
  17 #include "build/build_config.h"
  18
  19 #ifndef NDEBUG
  20
  21 // A helper class to track down call sites that are not handling error cases.
  22 template<class T>
  23 class CheckReturnValue {
  24  public:
  25   // Not marked explicit on purpose.
  26   CheckReturnValue(T value) : value_(value), checked_(false) {  // NOLINT
  27   }
  28   CheckReturnValue(const CheckReturnValue& other)
  29       : value_(other.value_), checked_(other.checked_) {
  30     other.checked_ = true;
  31   }
  32
  33   CheckReturnValue& operator=(const CheckReturnValue& other) {
  34     if (this != &other) {
  35       DCHECK(checked_);
  36       value_ = other.value_;
  37       checked_ = other.checked_;
  38       other.checked_ = true;
  39     }
  40     return *this;
  41   }
  42
  43   ~CheckReturnValue() {
  44     DCHECK(checked_);
  45   }
  46
  47   operator const T&() const {
  48     checked_ = true;
  49     return value_;
  50   }
  51
  52  private:
  53   T value_;
  54   mutable bool checked_;
  55 };
  56 typedef CheckReturnValue<bool> CheckBool;
  57 #else
  58 typedef bool CheckBool;
  59 #endif
  60
  61 namespace courgette {
  62
  63 // Allocates memory for an instance of type T, instantiates an object in that
  64 // memory with arguments |args| (of type ArgTypes), and returns the constructed
  65 // instance. Returns null if allocation fails.
  66 template <class T, class... ArgTypes>
  67 T* UncheckedNew(ArgTypes... args) {
  68   void* ram = nullptr;
  69   return base::UncheckedMalloc(sizeof(T), &ram) ? new (ram) T(args...)
  70                                                 : nullptr;
  71 }
  72
  73 // Complement of UncheckedNew(): destructs |object| and releases its memory.
  74 template <class T>
  75 void UncheckedDelete(T* object) {
  76   if (object) {
  77     object->T::~T();
  78     free(object);
  79   }
  80 }
  81
  82 // A deleter for std::unique_ptr that will delete the object via
  83 // UncheckedDelete().
  84 template <class T>
  85 struct UncheckedDeleter {
  86   inline void operator()(T* ptr) const { UncheckedDelete(ptr); }
  87 };
  88
  89 #if BUILDFLAG(IS_WIN)
  90
  91 // Manages a read/write virtual mapping of a physical file.
  92 class FileMapping {
  93  public:
  94   FileMapping();
  95   ~FileMapping();
  96
  97   // Map a file from beginning to |size|.
  98   bool Create(HANDLE file, size_t size);
  99   void Close();
 100
 101   // Returns true iff a mapping has been created.
 102   bool valid() const;
 103
 104   // Returns a writable pointer to the beginning of the memory mapped file.
 105   // If Create has not been called successfully, return value is nullptr.
 106   void* view() const;
 107
 108  protected:
 109   bool InitializeView(size_t size);
 110
 111   HANDLE mapping_;
 112   raw_ptr<void> view_;
 113 };
 114
 115 // Manages a temporary file and a memory mapping of the temporary file.
 116 // The memory that this class manages holds a pointer back to the TempMapping
 117 // object itself, so that given a memory pointer allocated by this class,
 118 // you can get a pointer to the TempMapping instance that owns that memory.
 119 class TempMapping {
 120  public:
 121   TempMapping();
 122   ~TempMapping();
 123
 124   // Creates a temporary file of size |size| and maps it into the current
 125   // process's address space.
 126   bool Initialize(size_t size);
 127
 128   // Returns a writable pointer to the reserved memory.
 129   void* memory() const;
 130
 131   // Returns true if the mapping is valid and memory is available.
 132   bool valid() const;
 133
 134   // Returns a pointer to the TempMapping instance that allocated the |mem|
 135   // block of memory.  It's the callers responsibility to make sure that
 136   // the memory block was allocated by the TempMapping class.
 137   static TempMapping* GetMappingFromPtr(void* mem);
 138
 139  protected:
 140   base::File file_;
 141   FileMapping mapping_;
 142 };
 143
 144 // A memory allocator class that allocates memory either from the heap or via a
 145 // temporary file.  The interface is STL inspired but the class does not throw
 146 // STL exceptions on allocation failure.  Instead it returns nullptr.
 147 // A file allocation will be made if either the requested memory size exceeds
 148 // |kMaxHeapAllocationSize| or if a heap allocation fails.
 149 // Allocating the memory as a mapping of a temporary file solves the problem
 150 // that there might not be enough physical memory and pagefile to support the
 151 // allocation.  This can happen because these resources are too small, or
 152 // already committed to other processes.  Provided there is enough disk, the
 153 // temporary file acts like a pagefile that other processes can't access.
 154 template<class T>
 155 class MemoryAllocator {
 156  public:
 157   typedef T value_type;
 158   typedef value_type* pointer;
 159   typedef value_type& reference;
 160   typedef const value_type* const_pointer;
 161   typedef const value_type& const_reference;
 162   typedef size_t size_type;
 163   typedef ptrdiff_t difference_type;
 164
 165   // Each allocation is tagged with a single byte so that we know how to
 166   // deallocate it.
 167   enum AllocationType : uint8_t {
 168     HEAP_ALLOCATION = 0xF0,  // Non-trivial constants to detect corruption.
 169     FILE_ALLOCATION = 0x0F,
 170   };
 171
 172   // 5MB is the maximum heap allocation size that we'll attempt.
 173   // When applying a patch for Chrome 10.X we found that at this
 174   // threshold there were 17 allocations higher than this threshold
 175   // (largest at 136MB) 10 allocations just below the threshold and 6362
 176   // smaller allocations.
 177   static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5;
 178
 179   template<class OtherT>
 180   struct rebind {
 181     // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
 182     typedef MemoryAllocator<OtherT> other;
 183   };
 184
 185   MemoryAllocator() {}
 186
 187   // We can't use an explicit constructor here, as dictated by our style guide.
 188   // The implementation of basic_string in Visual Studio 2010 prevents this.
 189   MemoryAllocator(const MemoryAllocator<T>& other) {  // NOLINT
 190   }
 191
 192   template <class OtherT>
 193   MemoryAllocator(const MemoryAllocator<OtherT>& other) {  // NOLINT
 194   }
 195
 196   ~MemoryAllocator() {
 197   }
 198
 199   void deallocate(pointer ptr, size_type size) {
 200     uint8_t* mem = reinterpret_cast<uint8_t*>(ptr);
 201     mem -= sizeof(T);
 202     if (mem[0] == HEAP_ALLOCATION)
 203       free(mem);
 204     else if (mem[0] == FILE_ALLOCATION)
 205       UncheckedDelete(TempMapping::GetMappingFromPtr(mem));
 206     else
 207       LOG(FATAL);
 208   }
 209
 210   pointer allocate(size_type count) {
 211     // We use the first byte of each allocation to mark the allocation type.
 212     // However, so that the allocation is properly aligned, we allocate an
 213     // extra element and then use the first byte of the first element
 214     // to mark the allocation type.
 215     count++;
 216
 217     if (count > max_size())
 218       return nullptr;
 219
 220     size_type bytes = count * sizeof(T);
 221     uint8_t* mem = nullptr;
 222
 223     // First see if we can do this allocation on the heap.
 224     if (count < kMaxHeapAllocationSize &&
 225         base::UncheckedMalloc(bytes, reinterpret_cast<void**>(&mem))) {
 226       mem[0] = static_cast<uint8_t>(HEAP_ALLOCATION);
 227     } else {
 228       // Back the allocation with a temp file if either the request exceeds the
 229       // max heap allocation threshold or the heap allocation failed.
 230       TempMapping* mapping = UncheckedNew<TempMapping>();
 231       if (mapping) {
 232         if (mapping->Initialize(bytes)) {
 233           mem = reinterpret_cast<uint8_t*>(mapping->memory());
 234           mem[0] = static_cast<uint8_t>(FILE_ALLOCATION);
 235         } else {
 236           UncheckedDelete(mapping);
 237         }
 238       }
 239     }
 240     // If the above fails (e.g. because we are in a sandbox), just try the heap.
 241     if (!mem && base::UncheckedMalloc(bytes, reinterpret_cast<void**>(&mem))) {
 242       mem[0] = static_cast<uint8_t>(HEAP_ALLOCATION);
 243     }
 244     return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : nullptr;
 245   }
 246
 247   pointer allocate(size_type count, const void* hint) {
 248     return allocate(count);
 249   }
 250
 251   void construct(pointer ptr, const T& value) {
 252     ::new(ptr) T(value);
 253   }
 254
 255   void destroy(pointer ptr) {
 256     ptr->~T();
 257   }
 258
 259   size_type max_size() const {
 260     size_type count = static_cast<size_type>(-1) / sizeof(T);
 261     return (0 < count ? count : 1);
 262   }
 263 };
 264
 265 #else  // BUILDFLAG(IS_WIN)
 266
 267 // On Mac, Linux, we use a bare bones implementation that only does
 268 // heap allocations.
 269 template<class T>
 270 class MemoryAllocator {
 271  public:
 272   typedef T value_type;
 273   typedef value_type* pointer;
 274   typedef value_type& reference;
 275   typedef const value_type* const_pointer;
 276   typedef const value_type& const_reference;
 277   typedef size_t size_type;
 278   typedef ptrdiff_t difference_type;
 279
 280   template<class OtherT>
 281   struct rebind {
 282     // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
 283     typedef MemoryAllocator<OtherT> other;
 284   };
 285
 286   MemoryAllocator() {
 287   }
 288
 289   explicit MemoryAllocator(const MemoryAllocator<T>& other) {
 290   }
 291
 292   template<class OtherT>
 293   explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
 294   }
 295
 296   ~MemoryAllocator() {
 297   }
 298
 299   void deallocate(pointer ptr, size_type size) { free(ptr); }
 300
 301   pointer allocate(size_type count) {
 302     if (count > max_size())
 303       return nullptr;
 304     pointer result = nullptr;
 305     return base::UncheckedMalloc(count * sizeof(T),
 306                                  reinterpret_cast<void**>(&result))
 307                ? result
 308                : nullptr;
 309   }
 310
 311   pointer allocate(size_type count, const void* hint) {
 312     return allocate(count);
 313   }
 314
 315   void construct(pointer ptr, const T& value) {
 316     ::new(ptr) T(value);
 317   }
 318
 319   void destroy(pointer ptr) {
 320     ptr->~T();
 321   }
 322
 323   size_type max_size() const {
 324     size_type count = static_cast<size_type>(-1) / sizeof(T);
 325     return (0 < count ? count : 1);
 326   }
 327 };
 328
 329 #endif  // BUILDFLAG(IS_WIN)
 330
 331 // Manages a growable buffer.  The buffer allocation is done by the
 332 // MemoryAllocator class.  This class will not throw exceptions so call sites
 333 // must be prepared to handle memory allocation failures.
 334 // The interface is STL inspired to avoid having to make too many changes
 335 // to code that previously was using STL.
 336 template<typename T, class Allocator = MemoryAllocator<T> >
 337 class NoThrowBuffer {
 338  public:
 339   typedef T value_type;
 340   static const size_t kAllocationFailure = 0xffffffff;
 341   static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T);
 342
 343   NoThrowBuffer() : buffer_(nullptr), size_(0), alloc_size_(0) {}
 344
 345   ~NoThrowBuffer() {
 346     clear();
 347   }
 348
 349   void clear() {
 350     if (buffer_) {
 351       alloc_.deallocate(buffer_, alloc_size_);
 352       buffer_ = nullptr;
 353       size_ = 0;
 354       alloc_size_ = 0;
 355     }
 356   }
 357
 358   bool empty() const {
 359     return size_ == 0;
 360   }
 361
 362   [[nodiscard]] CheckBool reserve(size_t size) {
 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   [[nodiscard]] CheckBool append(const T* data, size_t size) {
 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   [[nodiscard]] CheckBool resize(size_t size, const T& init_value) {
 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   [[nodiscard]] CheckBool push_back(const T& item) { return append(&item, 1); }
 439
 440   const T& back() const {
 441     return buffer_[size_ - 1];
 442   }
 443
 444   T& back() {
 445     return buffer_[size_ - 1];
 446   }
 447
 448   const T* begin() const {
 449     if (!size_)
 450       return nullptr;
 451     return buffer_;
 452   }
 453
 454   T* begin() {
 455     if (!size_)
 456       return nullptr;
 457     return buffer_;
 458   }
 459
 460   const T* end() const {
 461     if (!size_)
 462       return nullptr;
 463     return buffer_ + size_;
 464   }
 465
 466   T* end() {
 467     if (!size_)
 468       return nullptr;
 469     return buffer_ + size_;
 470   }
 471
 472   const T& operator[](size_t index) const {
 473     DCHECK(index < size_);
 474     return buffer_[index];
 475   }
 476
 477   T& operator[](size_t index) {
 478     DCHECK(index < size_);
 479     return buffer_[index];
 480   }
 481
 482   size_t size() const {
 483     return size_;
 484   }
 485
 486   size_t capacity() const {
 487     return alloc_size_;
 488   }
 489
 490   T* data() const {
 491     return buffer_;
 492   }
 493
 494   // Returns true if an allocation failure has ever occurred for this object.
 495   bool failed() const {
 496     return alloc_size_ == kAllocationFailure;
 497   }
 498
 499  protected:
 500   raw_ptr<T> buffer_;
 501   size_t size_;  // how much of the buffer we're using.
 502   size_t alloc_size_;  // how much space we have allocated.
 503   Allocator alloc_;
 504 };
 505
 506 }  // namespace courgette
 507
 508 #endif  // COURGETTE_MEMORY_ALLOCATOR_H_