Memory system - Part 5

This is the final installment in a series of posts about Molecule’s memory system. Today, we are going to look at the final piece of the puzzle, glueing together different things like raw memory allocation, bounds checking, memory tracking, and more.

In the last post of the series, we identified a lot of different use cases for the memory system, and discussed its requirements. Specifically, one thing we want to be able is to arbitrarily combine different features into simple memory arenas. As you may have guessed already, policy-based design is a tremendously powerful instrument which helps in fulfilling this task.

So, without further ado, here’s the solution I came up with as a base memory arena implementation in Molecule:

template <class AllocationPolicy, class ThreadPolicy, class BoundsCheckingPolicy, class MemoryTrackingPolicy, class MemoryTaggingPolicy>
class MemoryArena
{
public:
    template <class AreaPolicy>
    explicit MemoryArena(const AreaPolicy& area)
        : m_allocator(area.GetStart(), area.GetEnd())
    {
    }

    void* Allocate(size_t size, size_t alignment, const SourceInfo& sourceInfo)
    {
        m_threadGuard.Enter();

        const size_t originalSize = size;
        const size_t newSize = size + BoundsCheckingPolicy::SIZE_FRONT + BoundsCheckingPolicy::SIZE_BACK;

        char* plainMemory = static_cast<char*>(m_allocator.Allocate(newSize, alignment, BoundsCheckingPolicy::SIZE_FRONT));

        m_boundsChecker.GuardFront(plainMemory);
        m_memoryTagger.TagAllocation(plainMemory + BoundsCheckingPolicy::SIZE_FRONT, originalSize);
        m_boundsChecker.GuardBack(plainMemory + BoundsCheckingPolicy::SIZE_FRONT + originalSize);

        m_memoryTracker.OnAllocation(plainMemory, newSize, alignment, sourceInfo);

        m_threadGuard.Leave();

        return (plainMemory + BoundsCheckingPolicy::SIZE_FRONT);
    }

    void Free(void* ptr)
    {
        m_threadGuard.Enter();

        char* originalMemory = static_cast<char*>(ptr) - BoundsCheckingPolicy::SIZE_FRONT;
        const size_t allocationSize = m_allocator.GetAllocationSize(originalMemory);

        m_boundsChecker.CheckFront(originalMemory);
        m_boundsChecker.CheckBack(originalMemory + BoundsCheckingPolicy::SIZE_FRONT + allocationSize);

        m_memoryTracker.OnDeallocation(originalMemory);

        m_memoryTagger.TagDeallocation(originalMemory, allocationSize);

        m_allocator.Free(originalMemory);

        m_threadGuard.Leave();
    }

private:
    AllocationPolicy m_allocator;
    ThreadPolicy m_threadGuard;
    BoundsCheckingPolicy m_boundsChecker;
    MemoryTrackingPolicy m_memoryTracker;
    MemoryTaggingPolicy m_memoryTagger;
};

By being able to substitute different parts of the arena’s implementation using templates, the functionality is split into mutiple classes, each responsible only for one single thing. Additionally, we can combine whatever we want using a simple typedef, like in the following example:

typedef MemoryArena<LinearAllocator, SingleThreadPolicy, NoBoundsChecking, NoMemoryTracking, NoMemoryTagging> SimpleArena;

Remember that there’s absolutely no virtual function call overhead involved! By using different typedefs for certain build configurations (Debug, Release, Retail), you have all the benefits of debugging aids like bounds checking and memory tracking, while having blazingly-fast allocations in retail-builds. For example, Molecule’s application arena looks something like the following:

#if ME_DEBUG || ME_RELEASE
  typedef MemoryArena<LinearAllocator, SingleThreadPolicy, SimpleBoundsChecking, SimpleMemoryTracking, SimpleMemoryTagging> ApplicationArena;
#else
  typedef MemoryArena<LinearAllocator, SingleThreadPolicy, NoBoundsChecking, NoMemoryTracking, NoMemoryTagging> ApplicationArena;
#endif

In retail-builds, all the No*-implementations will be used, which contain nothing more than purely empty inline functions:

class NoBoundsChecking
{
public:
  static const size_t SIZE_FRONT = 0;
  static const size_t SIZE_BACK = 0;

  inline void GuardFront(void*) const {}
  inline void GuardBack(void*) const {}

  inline void CheckFront(const void*) const {}
  inline void CheckBack(const void*) const {}
};

class NoMemoryTracking
{
public:
  inline void OnAllocation(void*, size_t, size_t, const SourceInfo&) const {}
  inline void OnDeallocation(void*) const {}
};

class NoMemoryTagging
{
public:
  inline void TagAllocation(void*, size_t) const {}
  inline void TagDeallocation(void*, size_t) const {}
};

Debugging

By not relying on #if/#endif clauses buried deep within the source code itself, but rather using the compiler’s template mechanism in order to build our code, we can arbitrarily toggle different kinds of debugging aids using our typedefs, without even having access to the implementations’ source code.

As an example, whenever a memory leak is found, the SimpleMemoryTracking implementation will tell me about it – it just increments/decrements a counter on each allocation/deallocation, respectively. As soon as I know that the code contains leaks, I can simply switch to the ExtendedMemoryTracking implementation in the typedef, and be informed exactly about the place the leak occured. This helps against debug-builds which can no longer be used because they use too much memory for tracking purposes, or are simply too slow because of all the overhead.

Same for bounds checking – usable in debug builds, and the user can toggle between different implementations easily. Ever wanted to enable extended bounds checking in retail builds for those hard-to-find bugs only occuring in those builds? You can do that now!

Thread-Safety

As stated in the last post of the series, not every allocation needs to be thread-safe. For example, Molecule’s application arena is single-threaded by default, because there’s no loading-thread (or others) involved at that time – that’s what the level arena is for.

Essentially, being single-threaded is zero overhead:

class SingleThreadPolicy
{
public:
  inline void Enter(void) const {}
  inline void Leave(void) const {}
};

Other arenas certainly need their allocations to be thread-safe, which is were the MultiThreadPolicy comes into play:

template <class SynchronizationPrimitive>
class MultiThreadPolicy
{
public:
  inline void Enter(void)
  {
    m_primitive.Enter();
  }

  inline void Leave(void)
  {
    m_primitive.Leave();
  }

private:
  SynchronizationPrimitive m_primitive;
};

As you can see, the policy takes a template parameter as well, which provides the synchronization primitive to be used. This way, users can decide for themselves which primitive they need. Most of the time, this will either be a mutex or a critical section, but in those rare occasions where a spin-lock proved to be faster (e.g. for a linear allocator in a multi-threaded render queue), you can use exactly that, and not pay the overhead of more heavy-weight primitives.

Memory areas

Memory areas define where memory is being allocated from. The most common areas are the HeapArea and the StackArea. The first allocates memory directly from the OS, while the latter allocates memory on the stack using alloca(). Additionally, there could be areas for GPU memory (e.g. PS3), write-combined memory (Xbox360), external memory (Wii), etc.

Again, all of them can be combined with any allocator and any kind of debugging aid needed.

Extensibility

The base memory arena implementation can easily be extended without having to touch the source code at all. For example, Molecule provides a facility for recording each and every allocation in an application, which can later be replayed in an external tool (so-called memory replays). This is made possible by simply piggy-backing one allocator onto another:

template <class Arena>
class RecordingArena
{
public:
  void* Allocate(size_t size, size_t alignment, const SourceInfo& sourceInfo)
  {
    // send info via TCP/IP...
    return m_arena.Allocate(size, alignment, sourceInfo);
  }

  void Free(void* ptr)
  {
    // send info via TCP/IP...
    m_arena.Free(ptr);
  }

private:
  Arena m_arena;
};

The RecordingArena is not concerned with how the memory is actually allocated – all it does is send information via TCP/IP to an external application, and use any arena (provided by the template parameter) as the actual Allocate()/Free() implementation.

Usage

Memory arenas and areas are really simple to use. Want to have a pool of objects allocated on the stack, confined to a single thread?

typedef MemoryArena<PoolAllocator, SingleThreadPolicy, NoBoundsChecking, NoMemoryTracking, NoMemoryTagging> ST_PoolStackArena;

void SomeFunction()
{
    char* stackArea[2048];
    ST_PoolStackArena arena(stackArea);

    MyObject* obj = ME_NEW(MyObject, arena);
    // ...
    ME_DELETE(obj, arena);
}

Want to have a multi-threaded stack-based allocator allocating from GPU memory?

typedef MemoryArena<StackBasedAllocator, MultiThreadPolicy<CriticalSection>, NoBoundsChecking, NoMemoryTracking, NoMemoryTagging> MT_StackBasedArena;

// ...
GpuArea gpuArea(16*1024*1024);
MT_StackBasedArena gpuArena(gpuArea);

TextureData* data = ME_NEW(TextureData, gpuArena);
// ...
ME_DELETE(data , gpuArena);
}

A general-purpose, thread-safe allocator with all kinds of debugging bells and whistles ? A linear, lock-free allocator for temporary one-frame allocations? You get the idea, the possibilities are endless.

Conclusion

This concludes the mini-series about Molecule’s memory system. So far, I have been quite happy with the memory system for now: Leaks and memory overwrites can be found quite fast, fragmentation is kept to an absolute minimum (by using the right allocator for the job, application-wide and level-wide allocations have zero fragmentation, as well as many kinds of one-frame allocations, I/O allocations, and others), and it can easily be extended.

About these ads