Home > Programming, Tutorial > Memory Management Part 2: Allocations Tracking

Memory Management Part 2: Allocations Tracking

Introduction
In this post, I’ll cover the basics of memory allocations tracking. If you haven’t read my previous post on allocation strategy, make sure to read it before continuing.

Here’s what we want to achieve:

  • Keep track of every single allocation in the game with its allocation source (file, line, etc).
  • Categorize every allocation into high-level categories, such as Textures, Meshes, AI, etc.
  • Track memory leaks and generate categorized memory usage reports.
  • Minimize the impacts on the game’s performance, memory usage and fragmentation.

Minimizing Impacts
Keeping track of all allocations in a game engine might use a large amount of memory by itself; when tracking memory for usage reports or leaks, this may not be a problem. On the other hand, when using the system to gather information on fragmentation, it is crucial that it has a minimum impact on memory usage, or it may alter the results.

How to achieve that? The obvious answer is that the tracking system should not allocate its memory from the game engine’s allocators. Here we introduce the FreeList class:

template<class T> class FreeList
{
    T* Free;

public:
    FreeList()
    : Free(NULL)
    {}

    inline T* New()
    {
        if(!Free)
        {
            const tU32 AllocSize = 65536;
            const tU32 NumAllocPerBatch = AllocSize / sizeof(T);

            T* AllocBatch = (T*)VirtualAlloc(NULL, AllocSize, MEM_COMMIT, PAGE_READWRITE);

            for(tU32 i=0; i<NumAllocPerBatch; i++)
            {
                Delete(AllocBatch++);
            }
        }

        T* Result = Free;
        Free = *((T**)Free);
        return Result;
    }

    inline void Delete(T* Ptr)
    {
        *(T**)Ptr = Free;
        Free = Ptr;
    }
};

A free-list is a very important concept when designing memory allocators. The particularity of this implementation is that it will allocates 64KB pages directly from the OS whenever it is empty. It then uses the first bytes of each free elements that fits in the page to link to other free elements.

The fact that it allocates directly from the OS ensure that it doesn’t interfere with normal memory allocations in the engine, and minimize fragmentation since it allocates contiguous elements in OS pages.

In heavy usage scenarios, a FreeList will link free elements between multiple pages, but still it shouldn’t affect fragmentation, since it doesn’t share the same OS pages as the game engine’s allocators.

Tracking Allocations Hook
Now we’re ready to track allocations. The first step is to “hijack” our 3 memory functions we defined in the first part (lines 4, 11 and 17):

void* _Malloc(tU32 Size, tU32 AllocType, const tChar* Desc, const tChar* File, tU32 Line)
{
    void* Result = malloc(Size);
    RegisterAlloc(Result, Size, AllocType, Desc, File, Line);
    return Result;
}

void* _Realloc(void* Ptr, tU32 Size, const tChar* File, tU32 Line)
{
    void* Result = realloc(Ptr, Size);
    UpdateAlloc(Ptr, Result, Size, File, Line);
    return Result;
}

void _Free(void* Ptr)
{
    UnregisterAlloc(Ptr);
    return free(Ptr);
}

Implementation
Next, we need to implement RegisterAlloc, UpdateAlloc and UnregisterAlloc. The first step is to define the allocation structure AllocDesc that will hold information on a single allocation, and the allocation category TagDesc that will hold the allocation’s category information, such as the category’s name (the Desc string provided with each allocation call), the total allocated size, etc:

struct AllocDesc
{
    void* Ptr;        // Allocation address
    tU32 Size;        // Allocation size
    TagDesc* Tag;     // Pointer to the allocation category
    AllocDesc* Next;  // Next allocation in the hashtable
}
struct TagDesc
{
    tU32 CRC;         // Category description string CRC
    tU32 Size;        // Total size of all allocations in this category
    tChar Tag[128];   // Category name
    TagDesc* Next;    // Next category in the hashtable
}

The steps for registering an allocation looks like this:

  1. Create a new AllocDesc from a FreeList<AllocDesc> (line 4).
  2. Register this new allocation into its category (line 13).
  3. Register the new AllocDesc into the hashtable (lines 16-18).
void RegisterAlloc(void* Ptr, tU32 Size, const tChar* Desc, const tChar* File, tU32 Line)
{
    // Allocate a new AllocDesc from the freelist
    AllocDesc* NewAllocDesc = FreeAllocs.Allocate();

    // Set the allocation info
    NewAllocDesc->Ptr = Ptr;
    NewAllocDesc->Size = Size;
    NewAllocDesc->File = File;
    NewAllocDesc->Line = Line;

    // Register the allocation into its category (this updates the category total size)
    NewAllocDesc->Tag = TagDesc::Register(Desc, Size);

    // Register the allocation in the fixed-size hashtable
    tU32 PtrHash = GetPtrHash(Ptr) & (ALLOC_DESC_SIZE - 1);
    NewAllocDesc->Next = Hash[PtrHash];
    Hash[PtrHash] = NewAllocDesc;
}

Registering a new category goes like this:

  1. Lookup in the hashtable for the category (lines 3-17).
  2. If it already exist, increment the category’s size by the allocation size (line 12).
  3. If it doesn’t exist, create a new one from a FreeList<TagDesc> (line 20).
  4. Register the new TagDesc into the hashtable (lines 31-32).
static TagDesc* TagDesc::Register(const tChar* Tag, tU32 Size)
{
    tU32 TagCRC = Strhash(Tag);
    tU32 TagHash = TagCRC & (ALLOC_DESC_SIZE - 1);
    TagDesc* CurTag = CurTag = Hash[TagHash];

    while(CurTag)
    {
        if(CurTag->CRC == TagCRC)
        {
            // This category already exist, update its size and return it
            CurTag->Size += Size;
            return CurTag;
        }

        CurTag = CurTag->Next;
    }

    // Allocate a new TagDesc from the freelist
    CurTag = FreeTags.Allocate();

    // Set the category info
    CurTag->CRC = TagCRC;
    CurTag->Size = Size;

    tU32 TagLen = Min(strlen(Tag), 127);
    memcpy(CurTag->Tag, Tag, TagLen);
    CurTag->Tag[TagLen] = 0;

    // Register the category in the fixed-size hashtable
    CurTag->Next = Hash[TagHash];
    Hash[TagHash] = CurTag;

    return CurTag;
}

UpdateAlloc and UnregisterAlloc are straightforward. Simply update the allocation and category accordingly.

Analyzing the Data
Then comes the fun part: dumping and analyzing the gathered information. I usually dump all the data into a comma-separated values compatible format, because I tend to use Excel to analyze the data:

void DumpAllocs()
{
    printf("Address,Category,CategorySize,AllocSize\n");
    for(tU32 i=0; i<ALLOC_DESC_SIZE; i++)
    {
        AllocDesc* Alloc = Hash[i];
        while(Alloc)
        {
            printf("0x%08x,%s,%d,%d\n", Alloc->Ptr, Alloc->Tag->Tag, Alloc->Tag->Size, Alloc->Size);
            Alloc = Alloc->Next;
        }
    }
}

Which looks like this when turned into a quick report in Excel:

  Meshes 11336K
  Sounds 41553K
Textures 7867K

Tracking memory leaks
With this memory tracking up and running, it’s easy to setup a quick memory leaks detection system by dumping all allocations at a certain point in the game, then dumping another snapshot later on. Then, by comparing the 2 snapshots, we can quickly show the deltas for each categories and/or even for all allocations. The tricky part is to analyze the data correctly and identify what is normal and what are the real memory leaks.

Conclusion
This essentially covers the basics of memory allocations tracking. A lot of advanced stuff can be added, like tracking memory allocations using the call-stack, on-screen and even over-the-network memory visualization, etc. Simply implement what suits your needs best!

About these ads
  1. TuskGotTola
    October 7, 2011 at 7:30 am | #1

    I stucked on this:

    inline void Delete(T* Ptr)
    {
    *(T**)Ptr = Free;
    Free = Ptr;
    }

    What this magic is all about?

  2. jfdube
    October 7, 2011 at 7:34 am | #2

    When a free element is returned to the pool, we use the first bytes of it to link to the next free elements that are currently in the pool. The line *(T**)Ptr points to the very first bytes of the element, and we store the pointer to the first free element in it.

    You can see it like this:

    Ptr.Next = Free;
    Free = Ptr;

  3. Calv
    March 27, 2012 at 1:03 am | #3

    You’ll have to forgive me if I missed it, but could you please explain why you’re allocating OS pages through ‘VirtualAlloc’ instead of ‘HeapAlloc’ or even the default ‘malloc’? I don’t know much about VirtualAlloc beyond so brief encounters with it in black and white on the web. Thanks.

    • jfdube
      March 27, 2012 at 7:25 am | #4

      When you use malloc() for example, the underlying allocator will allocate OS pages through VirtualAlloc and then split the pages into smaller chunks to satisfy smaller allocations. In order to maintain these chunks, it needs to keep track of them using additional memory (see my post on memory fragmentation). VirtualAlloc will always return full-pages, even when calling it with sizes smaller than the page size. There’s is no added headers to the pages itself, and the pages are always aligned to the OS page size, which is exactly what we want.

  1. October 12, 2011 at 7:59 am | #1
  2. October 22, 2011 at 9:05 pm | #2
  3. January 13, 2012 at 2:11 pm | #3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: