Index | FAQ | Search | Memberlist | Usergroups | Profile | Log in to check your private messages | Log in | Register

Quake Memory Manager - Part 3: the Hunk

| Inside3d Forums Forum Index -> Programming Tutorials

View previous topic :: View next topic
Author | Message
--- | ---
mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Thu Jan 07, 2010 1:28 am Post subject: Quake Memory Manager - Part 3: the Hunk |

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.
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines

Back to top |

Team Xlink Joined: 25 Jun 2009 Posts: 320 |

Posted: Thu Jan 07, 2010 1:50 am Post subject: |

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

Anonymous wrote:
if it works, it works. if it doesn't, HAHAHA!

Back to top |

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

Posted: Thu Jan 07, 2010 7:32 pm Post subject: |

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.

Back to top |

r00k Joined: 13 Nov 2004 Posts: 483 |

Posted: Thu Jan 07, 2010 7:35 pm Post subject: |

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 |

mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Fri Jan 08, 2010 5:10 pm Post subject: |

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 |

dreadlorde Joined: 24 Nov 2009 Posts: 86 |

Posted: Thu Jan 21, 2010 6:06 pm Post subject: |

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 |

mh Joined: 12 Jan 2008 Posts: 910 |

Posted: Thu Jan 21, 2010 6:45 pm Post subject: |

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. _________________ DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines

Back to top |

dreadlorde Joined: 24 Nov 2009 Posts: 86 |

Posted: Fri Jan 22, 2010 12:57 am Post subject: |

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 |

Display posts from previous:

| 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