Switch out use of std::string and std::vector for large allocations for a buffer class that doesn...

courgette/memory_allocator.h

 // 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"
@@ skipping 38 matching lines @@
   mutable bool checked_;
 };
 typedef CheckReturnValue<bool> CheckBool;
 #else
 typedef bool CheckBool;
 #endif
 
 namespace courgette {
 
 #ifdef OS_WIN
+// Prototype for the allocation handler function.
+// See ThrowExceptionOnAllocationFailure below.
+typedef void (__stdcall* AllocationFailureHandler)(uint32 err);
+
+// A helper function to help diagnose failures we've seen in the field.
+// The function constructs a string containing the error and throws a runtime
+// exception.  The calling convention is set to stdcall to force argument
+// passing via the stack.
+__declspec(noinline)
+void __stdcall ThrowExceptionOnAllocationFailure(uint32 err);
 
 // 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();
 
-  __declspec(noinline) void Create();
+  __declspec(noinline) bool Create(AllocationFailureHandler failure_handler);
   void Close();
-  __declspec(noinline) void SetSize(size_t size);
+  __declspec(noinline) bool SetSize(size_t size,
+                                    AllocationFailureHandler failure_handler);
 
   // 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;
 
   // Returns the size of the temp file.  If the temp file doesn't exist,
   // the return value is 0.
   size_t size() const;
 
  protected:
-  __declspec(noinline) FilePath PrepareTempFile();
+  __declspec(noinline)
+  bool PrepareTempFile(FilePath* path,

[grt (UTC plus 2), 2011/04/05 17:10:08]

move |path| after |failure_handler|: out params come after in params.

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+                       AllocationFailureHandler failure_handler);
 
   base::PlatformFile file_;
   size_t size_;
 };
 
 // Manages a read/write virtual mapping of a physical file.
 class FileMapping {
  public:
   FileMapping();
   ~FileMapping();
 
   // Map a file from beginning to |size|.
-  __declspec(noinline) void Create(HANDLE file, size_t size);
+  __declspec(noinline) bool Create(HANDLE file, size_t size,
+                                   AllocationFailureHandler failure_handler);
   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:
-  __declspec(noinline) void InitializeView(size_t size);
+  __declspec(noinline)
+  bool InitializeView(size_t size, AllocationFailureHandler failure_handler);
 
   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' address space.
-  __declspec(noinline) void Initialize(size_t size);
+  __declspec(noinline) bool Initialize(size_t size,
+      AllocationFailureHandler failure_handler);
 
   // 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_;
 };
 
 // An STL compatible memory allocator class that allocates memory either

[grt (UTC plus 2), 2011/04/05 17:10:08]

Since the allocate() method now returns NULL on error, this class template no
longer satisfies the requirements on allocator types specified in the standard. 
Please revise the comment accordingly and consider changing the name to
something like "NonThrowingAllocator" so that this is even more obvious.

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

 // from the heap or via a temporary file.  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>
+template<class T, AllocationFailureHandler mem_failures_handler>

[grt (UTC plus 2), 2011/04/05 17:10:08]

If you make this template<class T, AllocationFailureHandler mem_failures_handler
= NULL>, can you get rid of the #ifdef at the bottom of NoThrowBuffer?

Also, I don't see any users of MemoryAllocator that specify a non-NULL
mem_failures_handler.  Could you remove this entirely?

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Yes, but afaik the style guide doesn't allow that, right?
Hmm... that's a good point.  My plan was to retain the option of easily going
back to the STL containers if we had problems.  However, I'm a bit uneasy with
this function pointer ugliness, so yes, I'll just get rid of it and accept the
fact that this is not STL anymore :)

 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 an MemoryAllocator<T> to a MemoryAllocator<OtherT>
-    typedef MemoryAllocator<OtherT> other;
+    // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
+    typedef MemoryAllocator<OtherT, mem_failures_handler> 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() {
+  MemoryAllocator(  // NOLINT
+      const MemoryAllocator<T, mem_failures_handler>& other) _THROW0() {
   }
 
   template<class OtherT>
-  explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) _THROW0() {
+  MemoryAllocator(  // NOLINT
+      const MemoryAllocator<OtherT, mem_failures_handler>& other) _THROW0() {
   }
 
   ~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())
-      throw std::length_error("overflow");
+    if (count > max_size()) {
+      if (mem_failures_handler)
+        mem_failures_handler(ERROR_INVALID_PARAMETER);
+      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 TempMapping();
-      mapping->Initialize(bytes);
-      mem = reinterpret_cast<uint8*>(mapping->memory());
-      mem[0] = static_cast<uint8>(FILE_ALLOCATION);
+      TempMapping* mapping = new(std::nothrow) TempMapping();
+      if (!mapping && mem_failures_handler)
+        mem_failures_handler(ERROR_OUTOFMEMORY);
+
+      if (mapping && mapping->Initialize(bytes, mem_failures_handler)) {
+        mem = reinterpret_cast<uint8*>(mapping->memory());
+        mem[0] = static_cast<uint8>(FILE_ALLOCATION);
+      }
     }
-    return reinterpret_cast<pointer>(mem + sizeof(T));
+    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_t 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 just use the default STL allocator.
 template<class T>
 class MemoryAllocator : public std::allocator<T> {

[grt (UTC plus 2), 2011/04/05 17:10:08]

This class template has different semantics than the OS_WIN version.  You
minimally need to override allocate() so that it returns NULL instead of
throwing std::bad_alloc.

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

That's intentional.  The problem I'm addressing is for Windows installations
specifically but retaining the previous functionality on other platforms.

  public:
 };
 
 #endif  // OS_WIN
 

[grt (UTC plus 2), 2011/04/05 17:10:08]

Add some documentation for this class and for its methods.

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+template<typename T>

[grt (UTC plus 2), 2011/04/05 17:10:08]

Consider:
template<typename T, class Allocator = MemoryAllocator<T> >

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+class NoThrowBuffer {
+ public:
+  typedef T value_type;
+  const static size_t kAllocationFailure = 0xffffffff;

[grt (UTC plus 2), 2011/04/05 17:10:08]

"static const" here and on the next line.

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+  const static size_t kStartSize = sizeof(T) > 0xff ? 1 : 0xff / sizeof(T);

[grt (UTC plus 2), 2011/04/05 17:10:08]

Why 0xff rather than 0x100?

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Cause it's closer to fffffuuuuuuuu... :) no real reason, I'll change it to
0x100.

+
+  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) {

[grt (UTC plus 2), 2011/04/05 17:10:08]

Use WARN_UNUSED_RESULT (from base/compiler_specific.h) here and everywhere you
use CheckBool.  It doesn't do anything for MSVC at the moment, but it could be
made to do so in the future, in which case you'd have compile-time enforcement
of what CheckBool is doing.

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+    if (failed())
+      return false;
+
+    if (size <= alloc_size_)
+      return true;
+
+    if (size < kStartSize) {

[grt (UTC plus 2), 2011/04/05 17:10:08]

nit: remove braces

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+      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) {
+    if (failed())
+      return false;
+

[grt (UTC plus 2), 2011/04/05 17:10:08]

if (size > alloc_.max_size() - size_)
  return false;

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+    if (!size)
+      return true;
+
+    if ((alloc_size_ - size_) < size) {

[grt (UTC plus 2), 2011/04/05 17:10:08]

this code has a few problems with overflow.  the following is probably a bit
more verbose than needed, but i think covers the cases:
  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;
  }

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+      size_t new_size = alloc_size_ ? (alloc_size_ * 2) : kStartSize;
+      while (new_size < size)
+        new_size *= 2;
+      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) {
+    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 simply be faster for us to don't reallocate but only

[grt (UTC plus 2), 2011/04/05 17:10:08]

nit: "It might be faster for us to simply change the size."

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+      // change the size.
+    }
+
+    size_ = size;
+
+    return true;
+  }
+
+  CheckBool push_back(const T& item) {
+    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 {
+    return buffer_[index];

[grt (UTC plus 2), 2011/04/05 17:10:08]

DCHECK(index < size_)?

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+  }
+
+  T& operator[](size_t index) {
+    return buffer_[index];

[grt (UTC plus 2), 2011/04/05 17:10:08]

DCHECK(index < size_)?

[tommi (sloooow) - chröme, 2011/04/05 19:06:53]

Done.

+  }
+
+  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.
+#ifdef OS_WIN
+  MemoryAllocator<T, NULL> alloc_;
+#else
+  MemoryAllocator<T> alloc_;
+#endif
+};
+
 }  // namespace courgette
 
 #endif  // COURGETTE_MEMORY_ALLOCATOR_H_