Systematic Gaming

August 26, 2008

Memory Management: Summary

Filed under: game programming, memory management — Tags: , — systematicgaming @ 2:59 am

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.

Debugging

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.

Initializing Memory

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.

Allocators

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

Memory Pools

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.

Garbage Collection

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.

Multi-Threading

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

About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

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

The Silver is the New Black Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: