Archive

Archive for October 3, 2011

Memory Management Part 1: Introduction

October 3, 2011 4 comments

This is the first of a series of posts on memory management in a game engine.

Series Outline
The topics I’d like to cover are numerous and may changes depending on the response I get from previous posts. Among others, I will cover (in no particular order):

  • Allocation strategy
  • Usage tracking
  • Leaks detection
  • Allocators design
  • Multithread issues
  • Fragmentation
  • False sharing
  • Contention
  • Waste/overhead

Motivation
The memory management strategy has important effects on any game engine. Performances of the allocator(s) is important; memory leaks, overhead and fragmentation are hard to report and even harder to fix. The need for good tools is critical.

Allocation Strategy
In order to be able to track memory allocations effectively and provide services like memory leaks detection and memory usage reports, it is crucial that all allocations go through a single point in the engine. This ensure that everything is taken care of, and reduce to a minimum the unknown memory usage.

To do so, we define the only 3 functions that should be used when allocating memory:

void* _Malloc(tU32 Size, tU32 AllocType, const tChar* Desc, const tChar* File, tU32 Line);
void* _Realloc(void* Ptr, tU32 Size, const tChar* File, tU32 Line);
void _Free(void* Ptr);

That’s a good start, but the new and delete operators should also be overloaded:

inline void* operator new(size_t Size, tU32 AllocType, const tChar* Desc, const tChar* File, tU32 Line) { return _Malloc(Size, AllocType, Desc, File, Line); }
inline void* operator new[](size_t Size, tU32 AllocType, const tChar* Desc, const tChar* File, tU32 Line) { return _Malloc(Size, AllocType, Desc, File, Line); }
inline void operator delete(void* Ptr) { _Free(Ptr); }
inline void operator delete[](void* Ptr) { _Free(Ptr); }

Initially, routing these functions to CRT‘s malloc, realloc and free should be fine. In future posts we’ll implement those using our own allocators.

Notice that every allocation has to provide a description string, file and line number. This will be used to track allocations, generate reports on memory usage/fragmentation and detect memory leaks.

Also notice the AllocType parameter: this is to provide a hint on which allocator to use to perform this allocation. This will be covered in future posts, such as memory fragmentation reduction.

It could be tempting to allow allocating without this information (by using default parameters), but this is something I highly recommend against: being rigorous about this will pay at the end, since it could rapidly become a mess if we let people allocate without providing accurate information and would render sub-systems such as memory usage/fragmentation/leaks tracking unusable.

To reduce the code overhead, we can define some convenient helper macros that automatically provide source file and line numbers:

#define Malloc(SIZE, TYPE, DESC) _Malloc(SIZE, TYPE, DESC, __FILE__, __LINE__)
#define Realloc(PTR, SIZE) _Realloc(PTR, SIZE, __FILE__, __LINE__)
#define New(CLASS, TYPE, DESC) new(TYPE, DESC, __FILE__, __LINE__) CLASS
#define Delete delete

At this point, all allocations through the engine should be converted to the new wrappers we just wrote. Might not an easy task depending on the size of the codebase, but it’s worth it.

Third-party external libraries
What about third-party external libraries? Any professional libraries should come with the possibility to route their internal memory allocations. If you’re using a library that doesn’t allow that, stop using it or contact the support so they provide such functionality.

Usually, third-party libraries provide either function definitions that the user need to implement (such as Box2D‘s b2Alloc/b2Free) or an interface similar to this:

class MemoryInterface
{
public:
    virtual void* malloc(int Size)=0;
    virtual void* realloc(void* Ptr, int Size)=0;
    virtual void free(void* Ptr)=0;
};

Implementing this interface should look like this:

class EngineMemoryInterface: public MemoryInterface
{
public:
    void* malloc(int Size) { return Malloc(Size, 0, "ExternalLibraryName"); }
    void* realloc(void* Ptr, int Size) { return Realloc(Ptr, Size); }
    void free(void* Ptr) { return Free(Ptr); }
};

If the library also provides internal file and line number of the allocations, simply route them too.

Conclusion
Congratulations, you wrapped all allocations to your own memory allocator stubs. This is only the first step, but a major one. To make sure everything is still under control, I usually put a breakpoint in CRT‘s malloc and run the game once in a while. Simply open the breakpoints window, type ‘malloc’ in the function name and play the game. Should not hit the breakpoint at all.

Now that we’re all set up, we’re ready to add functionality such as memory leaks tracking, etc. See you in a next post!

%d bloggers like this: