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

courgette/memory_allocator.h

Index: courgette/memory_allocator.h
===================================================================
--- courgette/memory_allocator.h	(revision 80344)
+++ courgette/memory_allocator.h	(working copy)
@@ -56,7 +56,17 @@
 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,
@@ -66,9 +76,10 @@
   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;
@@ -82,7 +93,9 @@
   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_;
@@ -95,7 +108,8 @@
   ~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.
@@ -106,7 +120,8 @@
   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_;
@@ -123,11 +138,15 @@
 
   // 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.
@@ -147,7 +166,7 @@
 // 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;
@@ -174,8 +193,8 @@
 
   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() {
@@ -183,11 +202,13 @@
 
   // 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() {
@@ -212,8 +233,11 @@
     // 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;
@@ -226,12 +250,16 @@
     } 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) {
@@ -262,6 +290,166 @@
 
 #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_