Implementation of an STL compatible allocator for Courgette on Windows....

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"
+#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.
+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.
+template<class T>
+class MemoryAllocator : public std::_Allocator_base<T> {

[grt (UTC plus 2), 2011/02/28 15:06:41]

Does deriving from an implementation detail of Microsoft's STL really simplify
things?  Seems like this adds a layer of fragility since it relies on
undocumented behavior.  See
http://blogs.msdn.com/b/vcblog/archive/2008/08/28/the-mallocator.aspx for an
example of a fairly minimal allocator.

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

removed.  Also updated the types accordingly.

+ public:
+  typedef _Allocator_base<T> Mybase;
+  typedef typename Mybase::value_type value_type;
+  typedef value_type _FARQ* pointer;
+  typedef value_type _FARQ& reference;
+  typedef const value_type _FARQ* const_pointer;
+  typedef const value_type _FARQ& const_reference;
+  typedef _SIZT size_type;
+  typedef _PDFT difference_type;
+
+  // Each allocation is tagged with a single byte so that we know how to
+  // deallocate it.
+  enum AllocationType {
+    HEAP_ALLOCATION,
+    FILE_ALLOCATION,
+  };
+
+  // 4MB is the maximum heap allocation size that well attempt.

[grt (UTC plus 2), 2011/02/28 15:06:41]

well -> we'll

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

Done.

+  static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 4;
+
+  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--;
+    if (mem[0] == HEAP_ALLOCATION) {
+      delete [] mem;
+    } else {
+      TempMapping* mapping = TempMapping::GetMappingFromPtr(mem);

[grt (UTC plus 2), 2011/02/28 15:06:41]

DCHECK_EQ(FILE_ALLOCATION, mem[0])?

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

Done.

+      delete mapping;
+    }
+  }
+
+  pointer allocate(size_type count) {
+    size_type bytes = count * sizeof(T);

[grt (UTC plus 2), 2011/02/28 15:06:41]

check for overflow (count > max_size()), throwing std::length_error if so.

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

Done.

+    uint8* mem = NULL;
+    // First see if we can do this allocation on the heap.
+    if (count < kMaxHeapAllocationSize)
+      mem = new(std::nothrow) uint8[bytes + 1];
+    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 + 1);

[grt (UTC plus 2), 2011/02/28 15:06:41]

what if this returns false?

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

added check+throw bad_alloc

+      mem = reinterpret_cast<uint8*>(mapping->memory());
+      mem[0] = static_cast<uint8>(FILE_ALLOCATION);
+    }
+    return reinterpret_cast<pointer>(mem + 1);

[grt (UTC plus 2), 2011/02/28 15:06:41]

C++-03 20.4.1.1 says that this must return "a pointer to the initial element of
an array of storage of size n * sizeof(T), aligned appropriately for objects of
type T."  this impl will only satisfy the alignment requirement when sizeof(T)
== sizeof(uint8).  please document and COMPILE_ASSERT that if it's okay, or fix
the impl if it's not.  Also consider that returning memory that isn't aligned to
(at least) a machine word could have perf implications if you're doing
memcpy/memmove/etc.

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

fixed so that heap allocations are always correctly aligned and file allocations
are allocated on a machine word boundary.

+  }
+
+  pointer allocate(size_type count, const void _FARQ* hint) {
+    return allocate(count);
+  }
+
+  void construct(pointer _Ptr, const T& _Val) {
+    std::_Construct(_Ptr, _Val);

[grt (UTC plus 2), 2011/02/28 15:06:41]

Another implementation detail used here.

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

Done.

+  }
+
+  void destroy(pointer _Ptr) {
+    std::_Destroy(_Ptr);

[grt (UTC plus 2), 2011/02/28 15:06:41]

And here.

[tommi (sloooow) - chröme, 2011/02/28 17:50:00]

Done.

+  }
+
+  _SIZT 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_