The Zone Memory Allocation System in Quake 2

Quake 2 uses a family of 5 functions for its memory allocation. John Carmack refers to them as the Zone Memory Allocation family of functions, and they are quite efficient and useful for modern game programmers to look at, considering they were initially developed in the early 1990s. Carmack programs in C, so if you’re unfamiliar with the language you may find them difficult to follow, but let’s look at them as a ‘basic’ way to manage your memory allocation in your game.

Before we begin, here’s a link to a console app I created to help understand what is going on underneath the hood when you use these functions. The project was programmed in Visual Studio 2008 in Windows XP.

ztest

The Data Structure

Here is the basic data structure that the ZMA functions use:

#define Z_MAGIC 0x1d1d

typedef struct zhead_s
{
struct zhead_s *prev, *next;
short magic;
short tag;
int size;
} zhead_t;

zhead_t z_chain;
int z_count, z_bytes;

This allows you to create an instance of a zhead_t object. This object is 16 bytes big on a 32-bit system – each of the struct pointers is 4 bytes each, the two shorts are 2 bytes each, and the int is 4 bytes big. The code creates the head of the linked list, named z_chain, and then maintains two integers, z_count and z_bytes, to keep track of how many objects are currently created and the number of bytes they are taking up. Let’s go through each item to discuss what it does.

prev and next – each of these are pointers to the previous or next items in the linked list. I will show you later that Carmack initializes them to point to z_chain itself, so they are never null.

magic – these functions are going to be all about working with raw pointers, and you need to make sure you are pointing to a valid zhead_t before you go free()ing anything. The magic value needs to match the Z_MAGIC that was defined earlier, or else there is something drastically wrong.

tag – this can potentially be used to keep track of what the space was malloc()ed for. In Doom and Quake this is used, but the Quake 2 code actually never uses the tag. Still, valuable to have, and it ensures that the entire struct is a multiple of 4.

size – this object tells you how many bytes of memory this zhead_t has reserved – we’ll get here in just a minute.

The Functions

There are 5 functions that manage the zhead_t objects. They are as follows:

void *Z_Malloc (int size) – This object uses malloc() to reserve size amount of bytes in memory. So if size is 100, then you will end up reserving a total of 116 bytes – 100 of open memory and 16 bytes for the appropriate zhead_t object to maintain it. In this example it would malloc() 116 bytes, it would set the zhead_t object in the first 16 bytes, and then it would return the address to the 100 bytes following the object. This is very important to keep in mind – you will receive a pointer for the space you can use, so you don’t need to worry about the zhead_t object at all – it is completely transparent when using the functions.

void Z_Free(void *ptr) – This object takes a pointer that you were sent by the Z_Malloc function and free()s it. It also adjusts the zhead_t chain so that it is no longer referenced their either.

void Z_TagMalloc (int size, int tag) – Does the same as Z_Malloc, just it allows you to pass a value to set the tag to. Actually Z_Malloc simply calls Z_TagMalloc with a value of 0 for the tag variable.

void Z_FreeTags(int tag) – goes through the chain of zhead_t objects, and it free()s any object with tag set to the tag variable. Not used in Quake 2.

If you look at the source code included in the ztest sample I posted to earlier, you will see that I have added a couple functions. The most important one is Z_Init.

void Z_Init(void) – This function is a simple line that sets the values of z_chain->prev and z_chain->next to the address of z_chain itself. This line is in the initialization code of the Quake 2 engine, and I didn’t want to make the z_chain object visible to the main() function.

void Z_Print(void) – This prints out lots of values for the z_chain – all of the objects that have been reserved, their addresses, etc etc.

Using the test suite

The ztest code will demonstrate how all of this works. Here are a few steps that may help you get started.

  • Either run the version of the program in the Release folder, or if you are on Linux, you may need to recompile. I used Standard C, except I use scanf_s() instead of scanf() for input – not sure if that’s on Linux or not.
  • Only input numbers. If you input letters it hangs because scanf() is awesome like that.
  • Start by choosing 3. Print tags. It will show that there are 0 bytes held thus far in 0 blocks. It will also give the address of z_chain in decimal (4207476 in my system) and show that both ->next and ->prev point to that same address.
  • Use the 1. Allocate memory function to allocate any amount of memory – let’s say 1000 bytes. In my system it creates the new zhead_t object at memory location 3420416, meaning it returns the address 3420432 – the first byte of actual usable memory. It also sets the tag to 1, since this is the first block created.
  • Create another new block of memory, lets make this one 2000 bytes of memory. Now we have the second zhead_t object located at memory 3432128 and the 2000 blocks beginning at 3432144. We also see now we have 3032 bytes being used in 2 blocks.
  • Use the ’3. Print tags’ feature again to see the following:
  • -zchain is still at the head, but zchain->next is the second block that we created. A new block of space is always added to the front of the chain.
    -zchain’s address is much different than the other addresses. This is because it is created on the stack, whereas the other objects are created dynamically on the heap.
    -the magic value is always 7453, or the same as the 0x1d1d that we saw defined at the beginning. This means everything is working as it should.
  • Feel free to remove some of them as well with the ’2. Release memory’ function. It will want a 1 or a 2 to release the first or second block created. Notice that if you type in 1 it will erase the 1000 byte block since it created that block first.

This was an afternoon project that I hope helps you understand how memory management in Quake (and in the C programming language) works. It’s one of my first little experiment tests, and I learned quite a bit putting this together. Good luck!