Inside3D!
     

Quake Memory Manager - Part 3: the Hunk

 
Post new topic   Reply to topic    Inside3d Forums Forum Index -> Programming Tutorials
View previous topic :: View next topic  
Author Message
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Thu Jan 07, 2010 1:28 am    Post subject: Quake Memory Manager - Part 3: the Hunk Reply with quote

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:
#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:
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:
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. Very Happy
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines
Back to top
View user's profile Send private message Visit poster's website
Team Xlink



Joined: 25 Jun 2009
Posts: 320

PostPosted: Thu Jan 07, 2010 1:50 am    Post subject: Reply with quote

Great work, this three tutorials are very nice.

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

Thank you.
_________________
Anonymous wrote:
if it works, it works. if it doesn't, HAHAHA!
Back to top
View user's profile Send private message
reckless



Joined: 24 Jan 2008
Posts: 390
Location: inside tha debugger

PostPosted: Thu Jan 07, 2010 7:32 pm    Post subject: Reply with quote

nice saves me writing only the pk3 code in my tutorial Smile

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

in your heap.c Wink 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.
Back to top
View user's profile Send private message
r00k



Joined: 13 Nov 2004
Posts: 483

PostPosted: Thu Jan 07, 2010 7:35 pm    Post subject: Reply with quote

Quote:

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?
Back to top
View user's profile Send private message
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Fri Jan 08, 2010 5:10 pm    Post subject: Reply with quote

r00k wrote:
Quote:

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.
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines
Back to top
View user's profile Send private message Visit poster's website
dreadlorde



Joined: 24 Nov 2009
Posts: 86

PostPosted: Thu Jan 21, 2010 6:06 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message AIM Address
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Thu Jan 21, 2010 6:45 pm    Post subject: Reply with quote

Neat. Very Happy

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.
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines
Back to top
View user's profile Send private message Visit poster's website
dreadlorde



Joined: 24 Nov 2009
Posts: 86

PostPosted: Fri Jan 22, 2010 12:57 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message AIM Address
Display posts from previous:   
Post new topic   Reply to topic    Inside3d Forums Forum Index -> Programming Tutorials All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2004 phpBB Group