// Copyright (c) 2011 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef COURGETTE_MEMORY_ALLOCATOR_H_ #define COURGETTE_MEMORY_ALLOCATOR_H_ #include <memory> #include "base/basictypes.h" #include "base/files/file_path.h" #include "base/logging.h" #include "base/platform_file.h" #ifndef NDEBUG // A helper class to track down call sites that are not handling error cases. template<class T> class CheckReturnValue { public: // Not marked explicit on purpose. CheckReturnValue(T value) : value_(value), checked_(false) { // NOLINT } CheckReturnValue(const CheckReturnValue& other) : value_(other.value_), checked_(other.checked_) { other.checked_ = true; } CheckReturnValue& operator=(const CheckReturnValue& other) { if (this != &other) { DCHECK(checked_); value_ = other.value_; checked_ = other.checked_; other.checked_ = true; } } ~CheckReturnValue() { DCHECK(checked_); } operator const T&() const { checked_ = true; return value_; } private: T value_; mutable bool checked_; }; typedef CheckReturnValue<bool> CheckBool; #else typedef bool CheckBool; #endif namespace courgette { #if defined(OS_WIN) // Manages a temporary file. The file is created in the %TEMP% folder and // is deleted when the file handle is closed. // NOTE: Since the file will be used as backing for a memory allocation, // it will never be so big that size_t cannot represent its size. class TempFile { public: TempFile(); ~TempFile(); bool Create(); void Close(); bool SetSize(size_t size); // Returns true iff the temp file is currently open. bool valid() const; // Returns the handle of the temporary file or INVALID_HANDLE_VALUE if // a temp file has not been created. base::PlatformFile handle() const; protected: base::PlatformFile file_; }; // Manages a read/write virtual mapping of a physical file. class FileMapping { public: FileMapping(); ~FileMapping(); // Map a file from beginning to |size|. bool Create(HANDLE file, size_t size); void Close(); // Returns true iff a mapping has been created. bool valid() const; // Returns a writable pointer to the beginning of the memory mapped file. // If Create has not been called successfully, return value is NULL. void* view() const; protected: bool InitializeView(size_t size); HANDLE mapping_; void* view_; }; // Manages a temporary file and a memory mapping of the temporary file. // The memory that this class manages holds a pointer back to the TempMapping // object itself, so that given a memory pointer allocated by this class, // you can get a pointer to the TempMapping instance that owns that memory. class TempMapping { public: TempMapping(); ~TempMapping(); // Creates a temporary file of size |size| and maps it into the current // process's address space. bool Initialize(size_t size); // Returns a writable pointer to the reserved memory. void* memory() const; // Returns true if the mapping is valid and memory is available. bool valid() const; // Returns a pointer to the TempMapping instance that allocated the |mem| // block of memory. It's the callers responsibility to make sure that // the memory block was allocated by the TempMapping class. static TempMapping* GetMappingFromPtr(void* mem); protected: TempFile file_; FileMapping mapping_; }; // A memory allocator class that allocates memory either from the heap or via a // temporary file. The interface is STL inspired but the class does not throw // STL exceptions on allocation failure. Instead it returns NULL. // A file allocation will be made if either the requested memory size exceeds // |kMaxHeapAllocationSize| or if a heap allocation fails. // Allocating the memory as a mapping of a temporary file solves the problem // that there might not be enough physical memory and pagefile to support the // allocation. This can happen because these resources are too small, or // already committed to other processes. Provided there is enough disk, the // temporary file acts like a pagefile that other processes can't access. template<class T> class MemoryAllocator { public: typedef T value_type; typedef value_type* pointer; typedef value_type& reference; typedef const value_type* const_pointer; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; // Each allocation is tagged with a single byte so that we know how to // deallocate it. enum AllocationType { HEAP_ALLOCATION, FILE_ALLOCATION, }; // 5MB is the maximum heap allocation size that we'll attempt. // When applying a patch for Chrome 10.X we found that at this // threshold there were 17 allocations higher than this threshold // (largest at 136MB) 10 allocations just below the threshold and 6362 // smaller allocations. static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5; template<class OtherT> struct rebind { // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT> typedef MemoryAllocator<OtherT> other; }; MemoryAllocator() _THROW0() { } // We can't use an explicit constructor here, as dictated by our style guide. // The implementation of basic_string in Visual Studio 2010 prevents this. MemoryAllocator(const MemoryAllocator<T>& other) _THROW0() { // NOLINT } template<class OtherT> MemoryAllocator(const MemoryAllocator<OtherT>& other) _THROW0() { // NOLINT } ~MemoryAllocator() { } void deallocate(pointer ptr, size_type size) { uint8* mem = reinterpret_cast<uint8*>(ptr); mem -= sizeof(T); if (mem[0] == HEAP_ALLOCATION) { delete [] mem; } else { DCHECK_EQ(static_cast<uint8>(FILE_ALLOCATION), mem[0]); TempMapping* mapping = TempMapping::GetMappingFromPtr(mem); delete mapping; } } pointer allocate(size_type count) { // We use the first byte of each allocation to mark the allocation type. // However, so that the allocation is properly aligned, we allocate an // extra element and then use the first byte of the first element // to mark the allocation type. count++; if (count > max_size()) return NULL; size_type bytes = count * sizeof(T); uint8* mem = NULL; // First see if we can do this allocation on the heap. if (count < kMaxHeapAllocationSize) mem = new(std::nothrow) uint8[bytes]; if (mem != NULL) { mem[0] = static_cast<uint8>(HEAP_ALLOCATION); } else { // If either the heap allocation failed or the request exceeds the // max heap allocation threshold, we back the allocation with a temp file. TempMapping* mapping = new(std::nothrow) TempMapping(); if (mapping && mapping->Initialize(bytes)) { mem = reinterpret_cast<uint8*>(mapping->memory()); mem[0] = static_cast<uint8>(FILE_ALLOCATION); } } return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : NULL; } pointer allocate(size_type count, const void* hint) { return allocate(count); } void construct(pointer ptr, const T& value) { ::new(ptr) T(value); } void destroy(pointer ptr) { ptr->~T(); } size_type max_size() const _THROW0() { size_type count = static_cast<size_type>(-1) / sizeof(T); return (0 < count ? count : 1); } }; #else // OS_WIN // On Mac, Linux, we use a bare bones implementation that only does // heap allocations. template<class T> class MemoryAllocator { public: typedef T value_type; typedef value_type* pointer; typedef value_type& reference; typedef const value_type* const_pointer; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; template<class OtherT> struct rebind { // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT> typedef MemoryAllocator<OtherT> other; }; MemoryAllocator() { } explicit MemoryAllocator(const MemoryAllocator<T>& other) { } template<class OtherT> explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) { } ~MemoryAllocator() { } void deallocate(pointer ptr, size_type size) { delete [] ptr; } pointer allocate(size_type count) { if (count > max_size()) return NULL; return reinterpret_cast<pointer>( new(std::nothrow) uint8[count * sizeof(T)]); } pointer allocate(size_type count, const void* hint) { return allocate(count); } void construct(pointer ptr, const T& value) { ::new(ptr) T(value); } void destroy(pointer ptr) { ptr->~T(); } size_type max_size() const { size_type count = static_cast<size_type>(-1) / sizeof(T); return (0 < count ? count : 1); } }; #endif // OS_WIN // Manages a growable buffer. The buffer allocation is done by the // MemoryAllocator class. This class will not throw exceptions so call sites // must be prepared to handle memory allocation failures. // The interface is STL inspired to avoid having to make too many changes // to code that previously was using STL. template<typename T, class Allocator = MemoryAllocator<T> > class NoThrowBuffer { public: typedef T value_type; static const size_t kAllocationFailure = 0xffffffff; static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T); NoThrowBuffer() : buffer_(NULL), size_(0), alloc_size_(0) { } ~NoThrowBuffer() { clear(); } void clear() { if (buffer_) { alloc_.deallocate(buffer_, alloc_size_); buffer_ = NULL; size_ = 0; alloc_size_ = 0; } } bool empty() const { return size_ == 0; } CheckBool reserve(size_t size) WARN_UNUSED_RESULT { if (failed()) return false; if (size <= alloc_size_) return true; if (size < kStartSize) size = kStartSize; T* new_buffer = alloc_.allocate(size); if (!new_buffer) { clear(); alloc_size_ = kAllocationFailure; } else { if (buffer_) { memcpy(new_buffer, buffer_, size_ * sizeof(T)); alloc_.deallocate(buffer_, alloc_size_); } buffer_ = new_buffer; alloc_size_ = size; } return !failed(); } CheckBool append(const T* data, size_t size) WARN_UNUSED_RESULT { if (failed()) return false; if (size > alloc_.max_size() - size_) return false; if (!size) return true; if ((alloc_size_ - size_) < size) { const size_t max_size = alloc_.max_size(); size_t new_size = alloc_size_ ? alloc_size_ : kStartSize; while (new_size < size_ + size) { if (new_size < max_size - new_size) { new_size *= 2; } else { new_size = max_size; } } if (!reserve(new_size)) return false; } memcpy(buffer_ + size_, data, size * sizeof(T)); size_ += size; return true; } CheckBool resize(size_t size, const T& init_value) WARN_UNUSED_RESULT { if (size > size_) { if (!reserve(size)) return false; for (size_t i = size_; i < size; ++i) buffer_[i] = init_value; } else if (size < size_) { // TODO(tommi): Should we allocate a new, smaller buffer? // It might be faster for us to simply change the size. } size_ = size; return true; } CheckBool push_back(const T& item) WARN_UNUSED_RESULT { return append(&item, 1); } const T& back() const { return buffer_[size_ - 1]; } T& back() { return buffer_[size_ - 1]; } const T* begin() const { if (!size_) return NULL; return &buffer_[0]; } T* begin() { if (!size_) return NULL; return &buffer_[0]; } const T* end() const { if (!size_) return NULL; return &buffer_[size_ - 1]; } T* end() { if (!size_) return NULL; return &buffer_[size_ - 1]; } const T& operator[](size_t index) const { DCHECK(index < size_); return buffer_[index]; } T& operator[](size_t index) { DCHECK(index < size_); return buffer_[index]; } size_t size() const { return size_; } T* data() const { return buffer_; } // Returns true if an allocation failure has ever occurred for this object. bool failed() const { return alloc_size_ == kAllocationFailure; } protected: T* buffer_; size_t size_; // how much of the buffer we're using. size_t alloc_size_; // how much space we have allocated. Allocator alloc_; }; } // namespace courgette #endif // COURGETTE_MEMORY_ALLOCATOR_H_