Implementation of an STL compatible allocator for Courgette on Windows.

This is to better handle low memory situations when applying a differential
patch to a large Chrome setup.

For reading input files, I'm also switching to using memory mapped files
instead of ReadFileToString to reduce the load on the heap.

TEST=courgette.exe should succeed in applying a patch between two
  chrome 10.x archives on an XP machine with 180MB of physical memory and
  no page file.
BUG=72459,73209

Review URL: http://codereview.chromium.org/6597038

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@76320 0039d316-1c4b-4281-b951-d872f2087c98

10 files changed, 439 insertions, 64 deletions

diff --git a/courgette/adjustment_method.cc b/courgette/adjustment_method.cc
index 4f16944..5e9e6d2 100644
--- a/courgette/adjustment_method.cc
+++ b/courgette/adjustment_method.cc
@@ -595,7 +595,7 @@ class GraphAdjuster : public AdjustmentMethod {
 
   void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
                      bool is_model) {
-    const std::vector<Instruction*>& instructions = program->instructions();
+    const InstructionVector& instructions = program->instructions();
     for (size_t i = 0;  i < instructions.size();  ++i) {
       Instruction* instruction = instructions.at(i);
       if (Label* label = program->InstructionAbs32Label(instruction))
diff --git a/courgette/adjustment_method_2.cc b/courgette/adjustment_method_2.cc
index cacf33e..e3ca315 100644
--- a/courgette/adjustment_method_2.cc
+++ b/courgette/adjustment_method_2.cc
@@ -1252,7 +1252,7 @@ class Adjuster : public AdjustmentMethod {
   void CollectTraces(const AssemblyProgram* program, Trace* abs32, Trace* rel32,
                      bool is_model) {
     label_info_maker_.ResetDebugLabel();
-    const std::vector<Instruction*>& instructions = program->instructions();
+    const InstructionVector& instructions = program->instructions();
     for (size_t i = 0;  i < instructions.size();  ++i) {
       Instruction* instruction = instructions.at(i);
       if (Label* label = program->InstructionAbs32Label(instruction))
diff --git a/courgette/assembly_program.h b/courgette/assembly_program.h
index e726f81..f7429201 100644
--- a/courgette/assembly_program.h
+++ b/courgette/assembly_program.h
@@ -12,12 +12,16 @@
 #include "base/basictypes.h"
 
 #include "courgette/image_info.h"
+#include "courgette/memory_allocator.h"
 
 namespace courgette {
 
 class EncodedProgram;
 class Instruction;
 
+typedef std::vector<Instruction*, MemoryAllocator<Instruction*> >
+    InstructionVector;
+
 // A Label is a symbolic reference to an address.  Unlike a conventional
 // assembly language, we always know the address.  The address will later be
 // stored in a table and the Label will be replaced with the index into the
@@ -89,7 +93,7 @@ class AssemblyProgram {
   EncodedProgram* Encode() const;
 
   // Accessor for instruction list.
-  const std::vector<Instruction*>& instructions() const {
+  const InstructionVector& instructions() const {
     return instructions_;
   }
 
@@ -101,7 +105,6 @@ class AssemblyProgram {
   // otherwise returns NULL.
   Label* InstructionRel32Label(const Instruction* instruction) const;
 
-
  private:
   void Emit(Instruction* instruction) { instructions_.push_back(instruction); }
 
@@ -118,7 +121,7 @@ class AssemblyProgram {
 
   uint64 image_base_;  // Desired or mandated base address of image.
 
-  std::vector<Instruction*> instructions_;  // All the instructions in program.
+  InstructionVector instructions_;  // All the instructions in program.
 
   // These are lookup maps to find the label associated with a given address.
   // We have separate label spaces for addresses referenced by rel32 labels and
diff --git a/courgette/courgette.gyp b/courgette/courgette.gyp
index 795b538..55a19dd 100644
--- a/courgette/courgette.gyp
+++ b/courgette/courgette.gyp
@@ -30,6 +30,8 @@
       'ensemble_create.cc',
       'image_info.cc',
       'image_info.h',
+      'memory_allocator.cc',
+      'memory_allocator.h',
       'region.h',
       'simple_delta.cc',
       'simple_delta.h',
diff --git a/courgette/encoded_program.cc b/courgette/encoded_program.cc
index f09a350..8439d31 100644
--- a/courgette/encoded_program.cc
+++ b/courgette/encoded_program.cc
@@ -39,18 +39,19 @@ EncodedProgram::EncodedProgram() : image_base_(0) {}
 EncodedProgram::~EncodedProgram() {}
 
 // Serializes a vector of integral values using Varint32 coding.
-template<typename T>
-void WriteVector(const std::vector<T>& items, SinkStream* buffer) {
+template<typename T, typename A>
+void WriteVector(const std::vector<T, A>& items, SinkStream* buffer) {
   size_t count = items.size();
   buffer->WriteSizeVarint32(count);
   for (size_t i = 0;  i < count;  ++i) {
-    COMPILE_ASSERT(sizeof(T) <= sizeof(uint32), T_must_fit_in_uint32);
+    COMPILE_ASSERT(sizeof(T) <= sizeof(uint32),  // NOLINT
+                   T_must_fit_in_uint32);
     buffer->WriteSizeVarint32(items[i]);
   }
 }
 
-template<typename T>
-bool ReadVector(std::vector<T>* items, SourceStream* buffer) {
+template<typename T, typename A>
+bool ReadVector(std::vector<T, A>* items, SourceStream* buffer) {
   uint32 count;
   if (!buffer->ReadVarint32(&count))
     return false;
@@ -68,7 +69,8 @@ bool ReadVector(std::vector<T>* items, SourceStream* buffer) {
 }
 
 // Serializes a vector, using delta coding followed by Varint32 coding.
-void WriteU32Delta(const std::vector<uint32>& set, SinkStream* buffer) {
+template<typename A>
+void WriteU32Delta(const std::vector<uint32, A>& set, SinkStream* buffer) {
   size_t count = set.size();
   buffer->WriteSizeVarint32(count);
   uint32 prev = 0;
@@ -80,7 +82,8 @@ void WriteU32Delta(const std::vector<uint32>& set, SinkStream* buffer) {
   }
 }
 
-static bool ReadU32Delta(std::vector<uint32>* set, SourceStream* buffer) {
+template <typename A>
+static bool ReadU32Delta(std::vector<uint32, A>* set, SourceStream* buffer) {
   uint32 count;
 
   if (!buffer->ReadVarint32(&count))
@@ -109,8 +112,8 @@ static bool ReadU32Delta(std::vector<uint32>* set, SourceStream* buffer) {
 // the possibility of a greater size for experiments comparing Varint32 encoding
 // of a vector of larger integrals vs a plain form.)
 //
-template<typename T>
-void WriteVectorU8(const std::vector<T>& items, SinkStream* buffer) {
+template<typename T, typename A>
+void WriteVectorU8(const std::vector<T, A>& items, SinkStream* buffer) {
   size_t count = items.size();
   buffer->WriteSizeVarint32(count);
   if (count != 0) {
@@ -119,8 +122,8 @@ void WriteVectorU8(const std::vector<T>& items, SinkStream* buffer) {
   }
 }
 
-template<typename T>
-bool ReadVectorU8(std::vector<T>* items, SourceStream* buffer) {
+template<typename T, typename A>
+bool ReadVectorU8(std::vector<T, A>* items, SourceStream* buffer) {
   uint32 count;
   if (!buffer->ReadVarint32(&count))
     return false;
@@ -146,7 +149,7 @@ void EncodedProgram::DefineAbs32Label(int index, RVA value) {
 
 static const RVA kUnassignedRVA = static_cast<RVA>(-1);
 
-void EncodedProgram::DefineLabelCommon(std::vector<RVA>* rvas,
+void EncodedProgram::DefineLabelCommon(RvaVector* rvas,
                                        int index,
                                        RVA rva) {
   if (static_cast<int>(rvas->size()) <= index) {
@@ -163,7 +166,7 @@ void EncodedProgram::EndLabels() {
   FinishLabelsCommon(&rel32_rva_);
 }
 
-void EncodedProgram::FinishLabelsCommon(std::vector<RVA>* rvas) {
+void EncodedProgram::FinishLabelsCommon(RvaVector* rvas) {
   // Replace all unassigned slots with the value at the previous index so they
   // delta-encode to zero.  (There might be better values than zero.  The way to
   // get that is have the higher level assembly program assign the unassigned
@@ -183,7 +186,7 @@ void EncodedProgram::AddOrigin(RVA origin) {
   origins_.push_back(origin);
 }
 
-void EncodedProgram::AddCopy(int count, const void* bytes) {
+void EncodedProgram::AddCopy(uint32 count, const void* bytes) {
   const uint8* source = static_cast<const uint8*>(bytes);
 
   // Fold adjacent COPY instructions into one.  This nearly halves the size of
@@ -199,7 +202,7 @@ void EncodedProgram::AddCopy(int count, const void* bytes) {
     }
     if (ops_.back() == COPY) {
       copy_counts_.back() += count;
-      for (int i = 0;  i < count;  ++i) {
+      for (uint32 i = 0;  i < count;  ++i) {
         copy_bytes_.push_back(source[i]);
       }
       return;
@@ -212,7 +215,7 @@ void EncodedProgram::AddCopy(int count, const void* bytes) {
   } else {
     ops_.push_back(COPY);
     copy_counts_.push_back(count);
-    for (int i = 0;  i < count;  ++i) {
+    for (uint32 i = 0;  i < count;  ++i) {
       copy_bytes_.push_back(source[i]);
     }
   }
@@ -349,8 +352,8 @@ bool EncodedProgram::ReadFrom(SourceStreamSet* streams) {
 
 // Safe, non-throwing version of std::vector::at().  Returns 'true' for success,
 // 'false' for out-of-bounds index error.
-template<typename T>
-bool VectorAt(const std::vector<T>& v, size_t index, T* output) {
+template<typename T, typename A>
+bool VectorAt(const std::vector<T, A>& v, size_t index, T* output) {
   if (index >= v.size())
     return false;
   *output = v[index];
@@ -390,11 +393,11 @@ bool EncodedProgram::AssembleTo(SinkStream* final_buffer) {
       }
 
       case COPY: {
-        int count;
+        uint32 count;
         if (!VectorAt(copy_counts_, ix_copy_counts, &count))
           return false;
         ++ix_copy_counts;
-        for (int i = 0;  i < count;  ++i) {
+        for (uint32 i = 0;  i < count;  ++i) {
           uint8 b;
           if (!VectorAt(copy_bytes_, ix_copy_bytes, &b))
             return false;
diff --git a/courgette/encoded_program.h b/courgette/encoded_program.h
index 25bc075..5662f2e 100644
--- a/courgette/encoded_program.h
+++ b/courgette/encoded_program.h
@@ -9,6 +9,7 @@
 
 #include "base/basictypes.h"
 #include "courgette/image_info.h"
+#include "courgette/memory_allocator.h"
 
 namespace courgette {
 
@@ -37,7 +38,7 @@ class EncodedProgram {
 
   // (3) Add instructions in the order needed to generate bytes of file.
   void AddOrigin(RVA rva);
-  void AddCopy(int count, const void* bytes);
+  void AddCopy(uint32 count, const void* bytes);
   void AddRel32(int label_index);
   void AddAbs32(int label_index);
   void AddMakeRelocs();
@@ -67,25 +68,30 @@ class EncodedProgram {
     OP_LAST
   };
 
+  typedef std::vector<RVA, MemoryAllocator<RVA> > RvaVector;
+  typedef std::vector<uint32, MemoryAllocator<uint32> > UInt32Vector;
+  typedef std::vector<uint8, MemoryAllocator<uint8> > UInt8Vector;
+  typedef std::vector<OP, MemoryAllocator<OP> > OPVector;
+
   void DebuggingSummary();
   void GenerateBaseRelocations(SinkStream *buffer);
-  void DefineLabelCommon(std::vector<RVA>*, int, RVA);
-  void FinishLabelsCommon(std::vector<RVA>* addresses);
+  void DefineLabelCommon(RvaVector*, int, RVA);
+  void FinishLabelsCommon(RvaVector* addresses);
 
   // Binary assembly language tables.
   uint64 image_base_;
-  std::vector<RVA> rel32_rva_;
-  std::vector<RVA> abs32_rva_;
-  std::vector<OP> ops_;
-  std::vector<RVA> origins_;
-  std::vector<int> copy_counts_;
-  std::vector<uint8> copy_bytes_;
-  std::vector<uint32> rel32_ix_;
-  std::vector<uint32> abs32_ix_;
+  RvaVector rel32_rva_;
+  RvaVector abs32_rva_;
+  OPVector ops_;
+  RvaVector origins_;
+  UInt32Vector copy_counts_;
+  UInt8Vector copy_bytes_;
+  UInt32Vector rel32_ix_;
+  UInt32Vector abs32_ix_;
 
   // Table of the addresses containing abs32 relocations; computed during
   // assembly, used to generate base relocation table.
-  std::vector<uint32> abs32_relocs_;
+  UInt32Vector abs32_relocs_;
 
   DISALLOW_COPY_AND_ASSIGN(EncodedProgram);
 };
diff --git a/courgette/ensemble_apply.cc b/courgette/ensemble_apply.cc
index 0785598..c865bfa 100644
--- a/courgette/ensemble_apply.cc
+++ b/courgette/ensemble_apply.cc
@@ -364,50 +364,32 @@ Status ApplyEnsemblePatch(SourceStream* base,
 Status ApplyEnsemblePatch(const FilePath::CharType* old_file_name,
                           const FilePath::CharType* patch_file_name,
                           const FilePath::CharType* new_file_name) {
-  Status status;
-
   // First read enough of the patch file to validate the header is well-formed.
   // A few varint32 numbers should fit in 100.
   FilePath patch_file_path(patch_file_name);
-  const int BIG_ENOUGH_FOR_HEADER = 100;
-  char buffer[BIG_ENOUGH_FOR_HEADER];
-  int read_count =
-      file_util::ReadFile(patch_file_path, buffer, sizeof(buffer));
-  if (read_count < 0)
+  file_util::MemoryMappedFile patch_file;
+  if (!patch_file.Initialize(patch_file_path))
     return C_READ_OPEN_ERROR;
 
   // 'Dry-run' the first step of the patch process to validate format of header.
   SourceStream patch_header_stream;
-  patch_header_stream.Init(buffer, read_count);
+  patch_header_stream.Init(patch_file.data(), patch_file.length());
   EnsemblePatchApplication patch_process;
-  status = patch_process.ReadHeader(&patch_header_stream);
+  Status status = patch_process.ReadHeader(&patch_header_stream);
   if (status != C_OK)
     return status;
 
-  // Header smells good so read the whole patch file for real.
-  int64 patch_file_size = 0;
-  if (!file_util::GetFileSize(patch_file_path, &patch_file_size))
-    return C_READ_ERROR;
-  std::string patch_file_buffer;
-  patch_file_buffer.reserve(static_cast<size_t>(patch_file_size));
-  if (!file_util::ReadFileToString(patch_file_path, &patch_file_buffer))
-    return C_READ_ERROR;
-
   // Read the old_file.
   FilePath old_file_path(old_file_name);
-  int64 old_file_size = 0;
-  if (!file_util::GetFileSize(old_file_path, &old_file_size))
-    return C_READ_ERROR;
-  std::string old_file_buffer;
-  old_file_buffer.reserve(static_cast<size_t>(old_file_size));
-  if (!file_util::ReadFileToString(old_file_path, &old_file_buffer))
+  file_util::MemoryMappedFile old_file;
+  if (!old_file.Initialize(old_file_path))
     return C_READ_ERROR;
 
   // Apply patch on streams.
   SourceStream old_source_stream;
   SourceStream patch_source_stream;
-  old_source_stream.Init(old_file_buffer);
-  patch_source_stream.Init(patch_file_buffer);
+  old_source_stream.Init(old_file.data(), old_file.length());
+  patch_source_stream.Init(patch_file.data(), patch_file.length());
   SinkStream new_sink_stream;
   status = ApplyEnsemblePatch(&old_source_stream, &patch_source_stream,
                               &new_sink_stream);
diff --git a/courgette/memory_allocator.cc b/courgette/memory_allocator.cc
new file mode 100644
index 0000000..06a0653
--- /dev/null
+++ b/courgette/memory_allocator.cc
@@ -0,0 +1,152 @@
+// 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.
+
+#include "courgette/memory_allocator.h"
+
+#include <map>
+
+#include "base/file_util.h"
+
+#ifdef OS_WIN
+
+namespace courgette {
+
+// TempFile
+
+TempFile::TempFile() : file_(base::kInvalidPlatformFileValue), size_(0) {
+}
+
+TempFile::~TempFile() {
+  Close();
+}
+
+void TempFile::Close() {
+  if (valid()) {
+    base::ClosePlatformFile(file_);
+    file_ = base::kInvalidPlatformFileValue;
+    size_ = 0;
+  }
+}
+
+bool TempFile::Create() {
+  DCHECK(file_ == base::kInvalidPlatformFileValue);
+  FilePath path;
+  if (file_util::CreateTemporaryFile(&path)) {
+    bool created = false;
+    base::PlatformFileError error_code = base::PLATFORM_FILE_OK;
+    int flags = base::PLATFORM_FILE_OPEN_ALWAYS | base::PLATFORM_FILE_READ |
+                base::PLATFORM_FILE_WRITE |
+                base::PLATFORM_FILE_DELETE_ON_CLOSE |
+                base::PLATFORM_FILE_TEMPORARY;
+    file_ = base::CreatePlatformFile(path, flags, &created, &error_code);
+    PLOG_IF(ERROR, file_ == base::kInvalidPlatformFileValue)
+        << "CreatePlatformFile";
+  }
+  return valid();
+}
+
+bool TempFile::valid() const {
+  return file_ != base::kInvalidPlatformFileValue;
+}
+
+base::PlatformFile TempFile::handle() const {
+  return file_;
+}
+
+size_t TempFile::size() const {
+  return size_;
+}
+
+bool TempFile::SetSize(size_t size) {
+  bool ret = base::TruncatePlatformFile(file_, size);
+  if (ret)
+    size_ = size;
+  return ret;
+}
+
+// FileMapping
+
+FileMapping::FileMapping() : mapping_(NULL), view_(NULL) {
+}
+
+FileMapping::~FileMapping() {
+  Close();
+}
+
+bool FileMapping::Create(HANDLE file, size_t size) {
+  DCHECK(file != INVALID_HANDLE_VALUE);
+  DCHECK(!valid());
+  mapping_ = ::CreateFileMapping(file, NULL, PAGE_READWRITE, 0, 0, NULL);
+  if (mapping_)
+    view_ = ::MapViewOfFile(mapping_, FILE_MAP_WRITE, 0, 0, size);
+
+  if (!valid()) {
+    PLOG(ERROR) << "Failed to map file";
+    Close();
+  }
+
+  return valid();
+}
+
+void FileMapping::Close() {
+  if (view_)
+    ::UnmapViewOfFile(view_);
+  if (mapping_)
+    ::CloseHandle(mapping_);
+  mapping_ = NULL;
+  view_ = NULL;
+}
+
+bool FileMapping::valid() const {
+  return view_ != NULL;
+}
+
+void* FileMapping::view() const {
+  return view_;
+}
+
+// TempMapping
+
+TempMapping::TempMapping() {
+}
+
+TempMapping::~TempMapping() {
+}
+
+bool TempMapping::Initialize(size_t size) {
+  // TODO(tommi): The assumption here is that the alignment of pointers (this)
+  // is as strict or stricter than the alignment of the element type.  This is
+  // not always true, e.g. __m128 has 16-byte alignment.
+  size += sizeof(this);
+  bool ret = file_.Create() && file_.SetSize(size) &&
+             mapping_.Create(file_.handle(), size);
+  if (ret) {
+    TempMapping** write = reinterpret_cast<TempMapping**>(mapping_.view());
+    write[0] = this;
+  }
+
+  return ret;
+}
+
+void* TempMapping::memory() const {
+  uint8* mem = reinterpret_cast<uint8*>(mapping_.view());
+  if (mem)
+    mem += sizeof(this);
+  DCHECK(mem);
+  return mem;
+}
+
+// static
+TempMapping* TempMapping::GetMappingFromPtr(void* mem) {
+  TempMapping* ret = NULL;
+  if (mem) {
+    ret = reinterpret_cast<TempMapping**>(mem)[-1];
+  }
+  DCHECK(ret);
+  return ret;
+}
+
+}  // namespace courgette
+
+#endif  // OS_WIN
diff --git a/courgette/memory_allocator.h b/courgette/memory_allocator.h
new file mode 100644
index 0000000..8e06e65
--- /dev/null
+++ b/courgette/memory_allocator.h
@@ -0,0 +1,222 @@
+// 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/logging.h"
+#include "base/platform_file.h"
+
+namespace courgette {
+
+#ifdef 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;
+
+  // Returns the size of the temp file.  If the temp file doesn't exist,
+  // the return value is 0.
+  size_t size() const;
+
+ protected:
+  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|.
+  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:
+  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.
+  bool Initialize(size_t size);
+
+  // Returns a writable pointer to the reserved memory.
+  void* memory() 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
+// 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>
+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;
+  };
+
+  MemoryAllocator() _THROW0() {
+  }
+
+  explicit MemoryAllocator(const MemoryAllocator<T>& other) _THROW0() {
+  }
+
+  template<class OtherT>
+  explicit MemoryAllocator(const MemoryAllocator<OtherT>& 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");
+
+    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();
+      if (!mapping->Initialize(bytes)) {
+        delete mapping;
+        throw std::bad_alloc("TempMapping::Initialize");
+      }
+      mem = reinterpret_cast<uint8*>(mapping->memory());
+      mem[0] = static_cast<uint8>(FILE_ALLOCATION);
+    }
+    return reinterpret_cast<pointer>(mem + 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_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> {
+ public:
+};
+
+#endif  // OS_WIN
+
+}  // namespace courgette
+
+#endif  // COURGETTE_MEMORY_ALLOCATOR_H_
diff --git a/courgette/streams.h b/courgette/streams.h
index 3dbc2b7..7be28a5 100644
--- a/courgette/streams.h
+++ b/courgette/streams.h
@@ -18,6 +18,7 @@
 
 #include "base/basictypes.h"
 
+#include "courgette/memory_allocator.h"
 #include "courgette/region.h"
 
 namespace courgette {
@@ -151,7 +152,11 @@ class SinkStream {
   void Retire();
 
  private:
-  std::string buffer_;  // Use a string to manage the stream's memory.
+  // Use a string to manage the stream's memory.
+  typedef std::basic_string<char,
+                            std::char_traits<char>,
+                            MemoryAllocator<char> > SinkBuffer;
+  SinkBuffer buffer_;
 
   DISALLOW_COPY_AND_ASSIGN(SinkStream);
 };