Quake Memory Manager - Part 3: the Hunk

[mh]

As promised, here comes part 3 where we tackle the Hunk. This is the main part of Quake's memory system and is used to store the map and various other big objects.

Quake actually has 2 hunks, 3 if you count temp allocations, they're all in a single buffer, and we're going to need to deal with them all. The low hunk is used for the vast majority of allocations, whereas the high hunk is used by software Quake for it's video buffer and surface cache, and for temp file loads.

We're going to replace the temp file loading with straight-up malloc, and in an ideal world we could also replace the rest of the high hunk similarly. Unfortunately the fact that it's there and that it could be used by your engine for other things means that we need to mostly retain it.

Now the bad news: this is the section where we need to get platform-specific. The code here is going to be Windows only, although there are only 3 lines that need changing, and I've marked them all with #ifdef _WIN32.

The Code

There are a few parts to this, so I'll give each in turn and discuss it after I've given it.

Put this at the start of your zone.c file after including quakedef.h:

Code: Select all

#ifdef _WIN32
#include <windows.h>
#else
      // to do
#endif

OK, this lets you know straight up that we're in platform-specific land. I don't know Linux and don't have the capacity to compile or test on it, so rather than risking getting fingers burned I'm leaving it to anyone who wants to. It would be great if anyone who did a Linux or other OS port of this code would post their changes on here so that all can share the info.

Anyway, next up we're replacing the entire hunk system (between the Hunk comment header and the Cache comment header) with this lot:

Code: Select all

void *hunk_tempptr = NULL;

void Hunk_TempFree (void)
{
   if (hunk_tempptr)
   {
      free (hunk_tempptr);
      hunk_tempptr = NULL;
   }
}

void *Hunk_TempAlloc (int size)
{
   Hunk_TempFree ();
   hunk_tempptr = malloc (size);

   return hunk_tempptr;
}


#define   HUNK_SENTINAL   0x1df001ed

typedef struct
{
   int      sentinal;
   int      size;
   char   name[8];
} hunk_t;

typedef struct hunk_type_s
{
   byte *hunkbuffer;
   int maxmb;
   int lowmark;
   int used;
} hunk_type_t;


hunk_type_t high_hunk = {NULL, 32 * 1024 * 1024, 0, 0};
hunk_type_t low_hunk = {NULL, 1024 * 1024 * 1024, 0, 0};


void *Hunk_TypeAlloc (hunk_type_t *ht, int size, char *name)
{
   hunk_t *hp;

   if (!ht->hunkbuffer)
   {
#ifdef _WIN32
      ht->hunkbuffer = VirtualAlloc (NULL, ht->maxmb, MEM_RESERVE, PAGE_NOACCESS);
#else
      // to do
#endif
      ht->lowmark = 0;
      ht->used = 0;
   }

   size = sizeof (hunk_t) + ((size + 15) & ~15);

   while (ht->lowmark + size >= ht->used)
   {
#ifdef _WIN32
      VirtualAlloc (ht->hunkbuffer + ht->used, 65536, MEM_COMMIT, PAGE_READWRITE);
#else
      // to do
#endif
      ht->used += 65536;
   }

   hp = (hunk_t *) (ht->hunkbuffer + ht->lowmark);
   ht->lowmark += size;

   memcpy (hp->name, name, 8);
   hp->sentinal = HUNK_SENTINAL;
   hp->size = size;

   memset ((hp + 1), 0, size - sizeof (hunk_t));
   return (hp + 1);
}


void Hunk_TypeFreeToLowMark (hunk_type_t *ht, int mark)
{
   memset (ht->hunkbuffer + mark, 0, ht->used - mark);
   ht->lowmark = mark;
}


int Hunk_TypeLowMark (hunk_type_t *ht)
{
   return ht->lowmark;
}


void Hunk_Check (void) {/* used in cl_parse.c */}
void *Hunk_AllocName (int size, char *name) {return Hunk_TypeAlloc (&low_hunk, size, name);}
void *Hunk_Alloc (int size) {return Hunk_TypeAlloc (&low_hunk, size, "unused");}
int   Hunk_LowMark (void) {return Hunk_TypeLowMark (&low_hunk);}
void Hunk_FreeToLowMark (int mark) {Hunk_TypeFreeToLowMark (&low_hunk, mark);}
int   Hunk_HighMark (void) {Hunk_TempFree (); return Hunk_TypeLowMark (&high_hunk);}
void Hunk_FreeToHighMark (int mark) {Hunk_TempFree (); Hunk_TypeFreeToLowMark (&high_hunk, mark);}
void *Hunk_HighAllocName (int size, char *name) {Hunk_TempFree (); return Hunk_TypeAlloc (&high_hunk, size, name);}

Some important things to take note of here.

• Again I've marked the Windows-only bits as above.
• We make use of the Operating System's virtual memory subsystem here, by reserving an initial block of 1 GB for most allocations and 32 MB for the video buffer (if you're paranoid you could increase this to 64, but there's no need to go higher).
• Memory is pulled from these chunks in 64K blocks, specifically because lots of small allocations can hurt your performance. 64K nicely matches the page size on Windows too.
• Quake doesn't actually allocate that full 1GB! All that happens is that we have a block of contiguous memory available for making future allocations from.
• I don't decommit memory because there are other parts of the Quake code that expect a pointer to the Hunk to be still valid even after Hunk_FreeToLowMark.
• Temp allocs just use straight malloc now and don't even touch the Hunk.

The final code change is your new Memory_Init function:

Code: Select all

void Memory_Init (void *buf, int size)
{
   free (host_parms.membase);
   host_parms.memsize = low_hunk.maxmb;
}

Here we're throwing away the original memory that was allocated on startup and resetting the memory size. We could get rid of these steps entirely by changing the relevant code in sys_win.c, but I didn't want to go outside of zone.c for these tutorials.

Cleaning Up

You can now go through the file and delete anything left over that's no longer used. I said that I'd release a full zone.c incorporating these changes, but I'd prefer at this stage to wait for comments and bugs to shake out, as well as the possibility of at least a Linux and an OSX port.

In Conclusion

By following these 3 tutorials we have implemented a Quake memory manager that's considerably more powerful, not to mention simpler, than the one that comes with Quake. Users no longer have any need to specify -heapsize as Quake can dynamically expand it's memory up to 1 GB (more when you include the cache - which is why I chose only 1 GB here), and anything they do specify will be thrown out.

Even if you have no intention of using this system longer term, it could serve as a useful stepping stone to implementing one of your own as you would no longer need to have to deal with the original code.

The most obvious next steps include:

• Somebody do a Linux and/or Mac OSX port.
• Remove -heapsize and the original parms.membase allocation.
• Get rid of the 64K chunks and alloc a chunk large enough (rounded up to the nearest 64K) for the requested size instead.
• Put the video buffer in it's own memory space via malloc and free.

It's been quite a bit of fun to put these tutorials together, and I hope I've given you something that's interesting and useful here.

[Team Xlink]

Great work, this three tutorials are very nice.

This platform specific part has give me inspiration to attempt one for my platform as well.

Thank you.

[revelator]

nice saves me writing only the pk3 code in my tutorial

albeit a few small differences i think the code had different names

in your heap.c i should be able to rewrite those parts though.

and

#ifdef _WIN32
#include <windows.h>
#else
// to do
#endif

well if its linux

#ifdef _WIN32
#include <windows.h>
#else if defined(_linux)
#include<mman.h> // linux memory manager functions
#endif

allthough some modifications might be nessesary in the code where you wrote

#ifdef _WIN32
VirtualAlloc (ht->hunkbuffer + ht->used, 65536, MEM_COMMIT, PAGE_READWRITE);
#else if defined(_linux)
// to do
mmap(*linux equivalent parameters*);
#endif

VirtualFree is munmap on linux the parameters for both are a bit different though.

[r00k]

Get rid of the 64K chunks and alloc a chunk large enough (rounded up to the nearest 64K) for the requested size instead.

Will this make our memory fragmented?

[mh]

Get rid of the 64K chunks and alloc a chunk large enough (rounded up to the nearest 64K) for the requested size instead.

Will this make our memory fragmented?

Not at all because it's initially reserved in a single contiguous block which can only grow or shrink linearally. You can't deallocate from the middle of the block, same as with the old Hunk.

[dreadlorde]

Here are some links for people who want to know some more about how Linux does memory management.

http://kernelnewbies.org/KernelMemoryAllocation
http://www.linuxhq.com/guides/TLK/mm/memory.html
http://linux-mm.org/

Some links about memory allocation in general:

http://en.wikipedia.org/wiki/Manual_memory_management
http://en.wikipedia.org/wiki/Dynamic_memory_allocation

[mh]

Neat.

It would be really cool if somebody wrote, tested and posted equivalent code for Linux; I could probably hack something together from documentation but I'm not in a position to test it and I couldn't stand over it.

[dreadlorde]

I could test it if you want to do it, I don't have enough experience in C to do something like this just by reading documentation yet.