Inside3D!
     

Quake Memory Manager - Part 2: the Cache

 
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: Wed Jan 06, 2010 11:00 pm    Post subject: Quake Memory Manager - Part 2: the Cache Reply with quote

A little sooner than expected, but here comes part 2 of the improved Quake Memory Manager, where we're going to do the Cache. This is used for objects that are potentially reusable while Quake is running, like alias models, sounds, menu graphics and so on, and so needn't be loaded every time, and is one of the reasons why Quake maps can load so fast.

Concept

The Cache currently shares it's memory space with the Hunk, and is a rather nasty-looking mess of code with functions to move objects around and maintain least-recently-used and most-recently used lists.

We're going to have an unlimited-sized cache that is completely decoupled from the Hunk system at the end of this one, and the code in the file will really start looking a lot cleaner and more maintainable.

Sometimes it's better to fine tune code by tweaking a little here and a little there until you get where you want with it. Other times you need to rip it up and start again.

Code

Guess which one I did? Replace everything between the "CACHE SYSTEM comment header and the Memory_Init function with this:

Code:
typedef struct cache_system_s
{
   int                  size;
   cache_user_t         *user;
   char               name[MAX_OSPATH];
   struct cache_system_s   *next;
   struct cache_system_s   *prev;
} cache_system_t;

cache_system_t *cache_head = NULL;
cache_system_t *cache_tail = NULL;


void Cache_FreeLow (int new_low_hunk) {/* used by hunk */}
void Cache_FreeHigh (int new_high_hunk) {/* used by Hunk */}
void Cache_Report (void) {/* used in cl_main.c */}
void *Cache_Check (cache_user_t *c) {return c->data;}

void Cache_Free (cache_user_t *c)
{
   cache_system_t *cs = ((cache_system_t *) c) - 1;

   if (cs->prev)
      cs->prev->next = cs->next;
   else cache_head = cs->next;

   if (cs->next)
      cs->next->prev = cs->prev;
   cache_tail = cs->prev;

   // prevent Cache_Check from blowing up
   cs->user->data = NULL;

   free (cs);
}


void *Cache_Alloc (cache_user_t *c, int size, char *name)
{
   cache_system_t *cs = NULL;

   for (cs = cache_head; cs; cs = cs->next)
      if (!strcmp (cs->name, name))
         return cs->user->data;

   if (c->data) Sys_Error ("Cache_Alloc: allready allocated");
   if (size <= 0) Sys_Error ("Cache_Alloc: size %i", size);

   cs = (cache_system_t *) malloc (sizeof (cache_system_t) + size);
   cs->next = cache_head;

   if (!cache_head)
   {
      cache_head = cs;
      cs->prev = NULL;
   }
   else
   {
      cache_tail->next = cs;
      cs->prev = cache_tail;
   }

   cache_tail = cs;
   cs->next = NULL;

   strcpy (cs->name, name);
   cs->size = size;
   cs->user = c;

   c->data = (cs + 1);

   return c->data;
}


Also remove the call to Cache_Init from Memory_Init.

What's happening here is that I've completely reworked the system to live in it's own free memory space totally removed from the Hunk, and managed by standard malloc and free. It's still a double-linked list because we potentially need to remove items from the middle of the Cache (in the software model.c) and I wanted to make it easier to do so.

The only tricksy thing here is that I allocate the cache_system_t struct and the actual data in a single contiguous block. This makes it easier to retrieve the original cache_system_t struct from a user data pointer when freeing memory, although I think it's a security weakness as it allows code outside of the memory system to be able to access the system struct. It's the way ID Quake did it however, and changing it would need changes outside of zone.c, which I want to avoid.

The original Quake Cache system had a function for flushing the entire cache, but it was unused (most likely because it shouldn't be done while a server is active!) and so I didn't bother implementing it. Doubly-linked lists are Computer Science 101, so look at your favourite textbook or article if you want to implement it yourself.

Cleaning Up

I've been a bit more brutal this time, removing functions that weren't used outside of zone.c and tidying up a bit more myself. There shouldn't be much cleaning up to do this time.

The Next Part

And so on to the Hunk. Quake actually maintains two Hunks, one at the upper-end and one at the lower-end of it's memory block. The changes needed here are already written and working, but I'm going to review them and decide if I want to split the Hunk into two separate blocks or keep things as they are, and also see what potential for cleaning up there is.
_________________
DirectQ Engine - New release 1.8.666a, 9th August 2010
MHQuake Blog (General)
Direct3D 8 Quake Engines


Last edited by mh on Sat Jan 16, 2010 11:11 pm; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
metlslime



Joined: 05 Feb 2008
Posts: 177

PostPosted: Thu Jan 07, 2010 12:06 am    Post subject: Reply with quote

Question on both of these... I think there was probably a good reason that Carmack wrote all this funky memory management code back in the day. My theories are:

- malloc/free many times with small allottments are a performance hit compared to one big malloc.

- on systems with barely enough RAM to play quake, these techniques are necessary to ensure that you don't run out (i.e. less fragmentation)

- for development with a target system spec (i.e. the game must run with an 8mb heap) it's easier for content developers to verify that their game will run, if the memory system's behavior is repeatable across gameplay sessions and different machines.

I guess if these are the only concerns, we probably don't need to fear using lots of malloc/free anymore.
Back to top
View user's profile Send private message
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Thu Jan 07, 2010 12:47 am    Post subject: Reply with quote

Lots of malloc/free actually still does hurt a lot; do it wrong and you can count your map load times in minutes (there's actually a bug in QuakeII's memory code that does something similar to this, passing over the entire previously allocated buffer for each subsequent small allocation, and is the main reason why QII maps take so long to load).

For the zone it's no great overhead, there's so few objects in there to begin with. For the cache any objects going in there are large enough to begin with, and they're reused, so we can discount that.

The hunk is another matter entirely which I'll be addressing in part 3 by allocating in 64K blocks.

Another reason for writing the code the way it was is that Quake was originally a DOS game. QuakeII and beyond have completely different and much simpler code.
_________________
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
Baker



Joined: 14 Mar 2006
Posts: 1538

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

I have a cache question if you don't mind.

I desperately want to eradicate all the .lmp loading even from the software renderer in favor of even a hardcoded .txt file loading 256-color paletted files in PCX or TGA format (with a shared single palette) or with GL engines just any format.

My past efforts to unravel exactly what all the cache file stuff is for with the graphics have really impeded me.

For the software renderer, I can understand a little. For GLQuake, it is a bit unclear to me why it is even necessary.

(Then again, maybe if I looked at it again I'd "get it" now as I often run into code that in the past I couldn't understand and then suddenly it all ends up making sense.)
Back to top
View user's profile Send private message
metlslime



Joined: 05 Feb 2008
Posts: 177

PostPosted: Thu Jan 07, 2010 3:05 am    Post subject: Reply with quote

Quote:
Lots of malloc/free actually still does hurt a lot; do it wrong and you can count your map load times in minutes (there's actually a bug in QuakeII's memory code that does something similar to this, passing over the entire previously allocated buffer for each subsequent small allocation, and is the main reason why QII maps take so long to load).


whoah, maybe someone should patch that? Smile
Back to top
View user's profile Send private message
frag.machine



Joined: 25 Nov 2006
Posts: 728

PostPosted: Sat Jan 16, 2010 10:24 pm    Post subject: Reply with quote

I am applying this tutorial to a clean FitzQuake 0.85 code base, and turns out it requires a Cache_Flush() function (called from the "game" command to unload menus, sbars and models). Problem is, I tried to re-implement it using the original function as base and the engine crashes when executing the "game blah" (where blah is a valid game dir, like hipnotic or rogue for example). Where follows what I am doing:

Code:

void Cache_Flush (void)
{
   while ((cache_head->next) && (cache_head->next->user))
      Cache_Free (cache_head->next->user); // reclaim the space
}


Also, FitzQuake frees textures in original Cache_Free () - in a bit dangerous way I guess, because the function calls TexMgr_FreeTexturesForOwner() blindly assuming the cache object is an alias model (what may not be the case).

Any ideas ?
_________________
frag.machine - Q2K4 Project
http://fragmachine.quakedev.com/
Back to top
View user's profile Send private message Visit poster's website
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Sat Jan 16, 2010 10:42 pm    Post subject: Reply with quote

Most likely cause is the different way I've implemented the cache_head variable. In original Quake it's never NULL (it's not even a pointer if memory serves).

Let me bash away at this for a short while; I should be able to get a working Cache_Flush soon.

_________________


Here we go:

Code:
void Cache_Flush (void)
{
   cache_system_t *cs = NULL;

   if (sv.active)
   {
      Con_Printf ("the cache cannot be flushed while the server is active!\n");
      return;
   }

   // because we're throwing stuff away we don't need to worry about relinking list pointers
   for (cs = cache_head; cs;)
   {
      cache_system_t *tmp = cs->next;

      // prevent Cache_Check from blowing up
      cs->user->data = NULL;

      free (cs);
      cs = tmp;
   }

   // !!! important !!!
   cache_head = cache_tail = NULL;
}


This is also safe to be called from the console (via Cmd_AddCommand) and works with both software and GLQuake.

My original Cache_Free implementation above should also set cs->user->data to NULL before the free; I'll add that fix.
_________________
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
metlslime



Joined: 05 Feb 2008
Posts: 177

PostPosted: Sun Jan 17, 2010 11:35 am    Post subject: Reply with quote

Quote:
Also, FitzQuake frees textures in original Cache_Free () - in a bit dangerous way I guess, because the function calls TexMgr_FreeTexturesForOwner() blindly assuming the cache object is an alias model (what may not be the case).

While I agree this is a hack, it's harmless because you can pass any arbitrary non-null pointer you want into TexMgr_FreeTexturesForOwner() -- it simply won't free anything unless that pointer matches the owner field of a texture. If you pass in null it would free all textures without an owner, though, which would be undesireable Razz

Actually the dangerous part is the pointer math which assumes that the cache_user_t is the last component of the model_t struct.
Back to top
View user's profile Send private message
frag.machine



Joined: 25 Nov 2006
Posts: 728

PostPosted: Sun Jan 17, 2010 5:26 pm    Post subject: Reply with quote

mh wrote:
Most likely cause is the different way I've implemented the cache_head variable. In original Quake it's never NULL (it's not even a pointer if memory serves).

Let me bash away at this for a short while; I should be able to get a working Cache_Flush soon.

_________________


Here we go:

Code:
void Cache_Flush (void)
{
   cache_system_t *cs = NULL;

   if (sv.active)
   {
      Con_Printf ("the cache cannot be flushed while the server is active!\n");
      return;
   }

   // because we're throwing stuff away we don't need to worry about relinking list pointers
   for (cs = cache_head; cs;)
   {
      cache_system_t *tmp = cs->next;

      // prevent Cache_Check from blowing up
      cs->user->data = NULL;

      free (cs);
      cs = tmp;
   }

   // !!! important !!!
   cache_head = cache_tail = NULL;
}


This is also safe to be called from the console (via Cmd_AddCommand) and works with both software and GLQuake.

My original Cache_Free implementation above should also set cs->user->data to NULL before the free; I'll add that fix.


Yup, it worked fine, thanks. Unfortunately, the gltexture free part stills broken. I believe it's just a matter of finding the correct point to place the call to TexMgr_FreeTexturesForOwner(). Let me make some more tests before yelling for help. Wink
_________________
frag.machine - Q2K4 Project
http://fragmachine.quakedev.com/
Back to top
View user's profile Send private message Visit poster's website
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Sun Jan 17, 2010 6:51 pm    Post subject: Reply with quote

frag.machine wrote:
Yup, it worked fine, thanks. Unfortunately, the gltexture free part stills broken. I believe it's just a matter of finding the correct point to place the call to TexMgr_FreeTexturesForOwner(). Let me make some more tests before yelling for help. Wink

You can probably already make some good guesses. Smile

Work ahead, and be sure to post your solution. Wink
_________________
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
frag.machine



Joined: 25 Nov 2006
Posts: 728

PostPosted: Sun Jan 17, 2010 10:18 pm    Post subject: Reply with quote

metlslime wrote:
While I agree this is a hack, it's harmless because you can pass any arbitrary non-null pointer you want into TexMgr_FreeTexturesForOwner() -- it simply won't free anything unless that pointer matches the owner field of a texture. If you pass in null it would free all textures without an owner, though, which would be undesireable Razz


I tried to put it approximately in the same point of the original Cache_Free() function but it didn't work as expected. Since we are flushing everything during the "game" command, can I assume is safe to make one single call to TexMgr_FreeTexturesForOwner() after Cache_Flush() passing in null as parameter then ? After all, console, menus and other textures will be reloaded anyway (either from the new game folder or from id1 if not found). Right ? Question
_________________
frag.machine - Q2K4 Project
http://fragmachine.quakedev.com/
Back to top
View user's profile Send private message Visit poster's website
mh



Joined: 12 Jan 2008
Posts: 910

PostPosted: Sun Jan 17, 2010 10:26 pm    Post subject: Reply with quote

I would have put it before cs->user->data = NULL, and would have used something like TexMgr_FreeTexturesForOwner ((model_t *)(cs->user + 1) - 1), but your logic seems pretty good - just pass NULL and it should do everything. Maybe do it before Cache_Flush though?
_________________
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
metlslime



Joined: 05 Feb 2008
Posts: 177

PostPosted: Mon Jan 18, 2010 10:43 am    Post subject: Reply with quote

frag.machine wrote:
metlslime wrote:
While I agree this is a hack, it's harmless because you can pass any arbitrary non-null pointer you want into TexMgr_FreeTexturesForOwner() -- it simply won't free anything unless that pointer matches the owner field of a texture. If you pass in null it would free all textures without an owner, though, which would be undesireable Razz

I tried to put it approximately in the same point of the original Cache_Free() function but it didn't work as expected. Since we are flushing everything during the "game" command, can I assume is safe to make one single call to TexMgr_FreeTexturesForOwner() after Cache_Flush() passing in null as parameter then ? After all, console, menus and other textures will be reloaded anyway (either from the new game folder or from id1 if not found). Right ? Question

Not quite; passing NULL would only free textures without an owner, not all textures regardless of owner.

However if you notice, TexMgr_NewGame() already clears almost every texture, this accomplishes what is needed for a game switch.

But if Cache_Free is called under any other circumstances, you'd leave orphaned textures if you don't free them at the same time.
Back to top
View user's profile Send private message
frag.machine



Joined: 25 Nov 2006
Posts: 728

PostPosted: Mon Jan 18, 2010 2:19 pm    Post subject: Reply with quote

I see. I'll try then using TexMgr_NewGame() from the "game" command instead, so I don't turn Cache_Free() unusable under other circumstances. And, as mh suggested, I'll do that before calling Cache_Free(). Let's see if this does the trick. Smile

UPDATE: Not worked. :/ Nothing crashes, but alias models textures get garbled.
_________________
frag.machine - Q2K4 Project
http://fragmachine.quakedev.com/
Back to top
View user's profile Send private message Visit poster's website
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