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/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.

[sra1, 2011/02/28 20:28:38]

Add somewhere: Since the file will be used as backing for a memory allocation,
it will never be so big that size_t cannot represent it's size.
Otherwise someone will wonder why the size is not [u]int64.

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

Done.

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

[sra1, 2011/02/28 20:28:38]

The two classes before this are all implementation detail.  They could be moved
to the .cc

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

This class holds member variables (not pointers) of those classes they need to
be there.

+ 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.

[sra1, 2011/02/28 20:28:38]

I would add a comment about the 'why', something like:

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.

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

Done.

+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.

[sra1, 2011/02/28 20:28:38]

I think this is OK, but I would have done this slightly differently:

1. Keep a 'global' data structure mapping address to TempMapping.
2. Normal allocations are not in the table.

Keeping the allocation metadata separate has several nice properties:

1. The allocation constraints are automatically satisfied by the underlying
allocators (operator new/filesystem).

2. If I ask for a nice round number like 5MB I don't get an extra cluster
allocated.

3. The allocation metadata is very diffuse.  A side table has greater cache
and/or page density.  You don't page in the first page of the file just to close
the file.  (Ditto for cache lines but that is not the issue here.)

4. Separated metadata is less likely to get trashed on buffer underrun.

Normally with a separated-metadata allocator there would be some effort to make
the lookup on deallocation fast.  Here a simple map<void*, TempMapping*> would
be fine - we do at most a couple of thousand allocations.

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

I thought about that kind of approach but went with this approach because it was
simpler and didn't depend on other allocations.  However, you have a point and
I'm happy to oblige.
Do you mind that I do that on a separate changelist and likely not in time for
the push this week?

[sra1, 2011/02/28 23:18:07]

Sure.

+  enum AllocationType {
+    HEAP_ALLOCATION,
+    FILE_ALLOCATION,
+  };
+
+  // 4MB is the maximum heap allocation size that we'll attempt.

[sra1, 2011/02/28 20:28:38]

Say why it is 4MB, rather than, say, 128k or 32MB.

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

To be honest this is a finger-in-the air estimate based on non scientific
observation.  Let me gather some numbers and pick something that I can more
easily justify.  As for 32MB, that's likely too big.  I ran tests with 40MB as
the cliff and it caused other heap allocations to start failing in low memory
situatons.

[sra1, 2011/02/28 23:18:07]

Thanks for measuring.

+  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 -= 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_