This series hasn’t been much more than a quick over of the memory management issues facing console game development. Hopefully it’s been informative, but keep in mind it’s only an introduction and was fairly light on many of the nitty-gritty implementations details.
To wrap up this series here’s a few quick topics that deserve mentioning, as well as some links to some suggested reading.
One topic that needs mentioning is debugging. While our primary goal in designing a memory management system is to efficiently track and allocate memory usage in our game, we can take advantage of our allocators to facilitate debugging.
Many classes of bugs are related to memory usage: uninitialized variables, buffer overruns, invalid pointers or pointers that have been freed, just to name a few. Fortunately we can use our memory allocators to help find some of these issues.
One very simple trick is to clear memory to known values depending on its state, for example:
- Set to 0xcc when the heap is first created, represents “clean” memory.
- Set to 0xaa when allocated.
- Set to 0xdd when freed.
Now if you look at your data in a debugger, you can tell if variables have been properly initialized, or if you’re accessing data that’s already been freed. You could also use different values for each allocator, so you could check where data came from.
Note: Don’t use 0 as a default value, you’ll hide more uninitialized variable bugs than with a less common value. The Windows debug C-runtime also does something similar.
Guards, Sentinels and Page Faults
Buffer overruns can be a problem, but we can look for those too. One way is to insert sentinel or guard values before and after each allocation then check that those values don’t get altered. This only detects writes to the beginning and end of blocks, but can catch a number of errors.
Here’s a quick example where we have a 1-byte buffer overrun
char *str = gAllocator.Alloc(4); strcpy( str, "help" ); gAllocator.Free(str);
Let’s see how our allocator can catch this. When we first allocate the string, our allocator will have a layout like this, using the guard value 0xbaadf00d. (The other common magic-number being 0xdeadbeef, programmers like food I guess)
size guard data guard ----------- ----------- ----------- ----------- 00 00 00 04 ba ad f0 0d aa aa aa aa ba ad f0 0d
After the strcpy, we’ll have this
size guard data guard ----------- ----------- ----------- ----------- 00 00 00 04 ba ad f0 0d 68 65 6C 70 00 ad f0 0d
When we free the block, or when we choose to validate or memory manually, we’ll see that the end guard has been altered and can assert. While useful this technique won’t catch all buffer overruns, only writes, and only if they touch the guard. If we’d overwritten by 5 bytes we wouldn’t have caught the error. We could add a larger guard, but really most buffer overruns are off-by-one type errors. Also we don’t catch reads, which are really just as bad as writing.
A more sophisticated approach is to use the virtual memory system. Even though consoles don’t have a swap disk, often they do support memory protection. Memory protection lets us indicate whether a page of memory can be read or written to.
The idea is simple: allocate memory so that the end of the block is at then of of the page. Then set the memory protection of the next page to forbid any access: both read and write. If some code tries to access that page, by buffer run or whatever, you’ll get a page fault.
This method is superior to the sentinels because the bad access is caught immediately not when we validate the heap. Also it will catch a larger range of overrun (usually 4kb or larger, depending on the page size). However it can be difficult to implement and not all platforms will support this method. But if possibly, it can be a good way of finding buffer overruns.
We only looked at a few allocator patterns: simple heap allocation, fixed block allocation and stack allocation. There are many other useful patterns that haven’t discussed, some other common allocators are
- Linear allocator (or frame allocator) – similar to the stack allocator, but doesn’t support freeing individual blocks. Instead the all allocations are freed together with one Clear or Reset call. This pattern is useful for a set of allocations that have the same lifespan (like one frame). Very fast and no fragmentation, it works well for temporary allocations with short lifespans.
- Handle allocator – not so much an allocator as a way of referencing memory. Instead of returning a pointer on allocation, we return a handle to memory which can be used to access the actual data. Handles allow us to do lots of neat things like rearrange blocks of memory behind the scenes (for defragmentation uses or cache friendly access).
I’ve mentioned that allocation from the global heap is slow and inefficient, but didn’t really go into alternatives. The most common way to avoid such allocation is using memory pools. A memory pool is a fixed heap of memory shared by a single type of object. Take a particle system for example, it’s really just a collection of particle objects, instead of allocating our particles from the general allocator we use or particle pool. We can easily do so using our fixed block allocator:
FixedBlockAllocator< sizeof(MyObject), MaxObjects> myPoolAllocator;
Since memory pools are so important, they really deserve their own article.
You can’t mention memory management without mentioning garbage collection. Pretty much every new and modern language touts its garbage collecting environment as improving stability and productivity. Many people go so far as to claim that lack of garbage collection makes C++ a primitive, backwards language. They couldn’t be farther from the truth! While I find garbage collection very useful when writing tools and other PC side code, the reality is that for memory and CPU constrained systems like game consoles, garbage collection can cause as many problems as it purports to solve.
One really good think about C++ is that object lifetimes are well defined. When you exit a scope or call delete destructors are called and resources are returned to the system. Not so with garbage collection, which often only triggers when various heuristics indicate it’s a good time to do so. This make it difficult to know how much memory is available and nearly impossible to judge memory fragmentation.
Additionally since garbage collection is a very expensive operation it will cause spikes in CPU time when it occurs. It’s not always predictable when this will happen, so it can disrupt a well tuned program if collection occurs at a inconvenient time.
Most importantly garbage collection is really orthogonal to the memory management problems we’ve been looking at. Garbage collection’s main purpose is to remove the hassle of managing object lifetime from the programmer, where a game’s memory management system is focused on memory as a global resource and how we should allocate, track and profile.
I’ve completely ignored multi-threading in these articles. At first glance there’s not too much required – we can wrap or main allocator’s Alloc and Free methods in a mutex and we’re good to go. However that assumes we don’t have too much contention on our allocator. Threads also have other memory related concerns we need to understand – per-thread stack memory, thread local store, even using per-thread allocators to remove the need for locks. This is a topic that requires more than a single paragraph to examine.
Links & Further Reading
- The Memory Management Reference – a large collection of information about memory management
- Play by Play: Effective Memory Management a summary of issues, similar to this series
- Doug Lea’s Malloc (dlmalloc) is a sophisticated general heap allocator meant to replace malloc. The linked articles explains the design decisions. From personal experience I’ve found this allocator to be a good replacement for most default malloc implementations.
- Electronic Arts Standard Template Library (EASTL) is Electronic Arts’ version of the Standard Template Library customized for game programming. The link mentions a number of game programming issues that influenced its design, including memory allocation.
- Microsoft Advanced Windows Debugging and Troubleshooting covers Windows specific issues, but does have a number of articles related to memory issues.