Gem: A Generic Handle-Based Resource Manager
By Scott Bilas
Introduction
All computer applications are databases. They spend most of their time juggling data resources – creating, destroying, caching, modifying, querying, saving, and restoring objects of various types. Games typically contain multiple types of databases, each of which is generally hard coded for each different case to keep things speedy. Some examples of game databases are file systems, texture managers, font managers, game actor managers. On top of those, there will also be a wide variety of domain-specific databases that completely depend on the game’s genre and content.
A resource database that’s built into all C++ games is the basic object memory manager. A programmer calls new to construct a new object and passes its pointer around for other objects to pass it messages. When the object is no longer needed, somebody deletes it and its resources are returned to the system. This method works great in general, but it breaks down when we have to worry about shared resources. This is where we need a more specialized database.
Let’s use a font object for our example. The font would at minimum consist of a bitmap and a set of specifications, such as the X,Y (or U,V) locations of its character cells, so the graphics system can render it to the screen. Such an object is fairly heavy duty in terms of memory usage and creation time. Different systems in the game, such as the development console and a text control within the GUI, will want to use font objects, but we can’t have each system creating its own local copy of the font object. Obviously, this would be slow and use up a lot of memory. To solve this problem we’ll come up with a way to share font objects. Chances are the solution will be called the FontMgr and will feature methods that get pointers to fonts, loading them in on the fly and caching them until they are no longer needed. The FontMgr will be made available from a global location (possibly as a Singleton) and will be responsible for all the font objects in the system.
What we’re really talking about here is a specialized database. The FontMgr will be responsible for juggling font resources and, now that it’s considered an API, will suddenly take on additional responsibilities as the central clearing house for fonts. What if someone tells it to delete a font to free up resources, but some systems in the game still have pointers to it? How do we guarantee safety of the system without sacrificing performance? Will we be copy-pasting this code again (with slight tweaks) when it comes time to build the MousePointerMgr? This gem presents a simple, safe, generic, and efficient way to manage controlled resource objects.
Method
The job of a resource manager is to create resources on demand, hand them out to anyone who asks, and then eventually delete them. Handing out those resources as simple pointers is certainly easy and convenient, but it’s not a very safe way to do it. Pointers can “dangle” – one part of the system may tell the resource manager to delete a resource, which then immediately invalidates all other outstanding pointers. There’s no good way to prevent the dangling pointer problem from happening, and the only way we would find out that someone was attempting to dereference a deleted object is when the access violation dialog box comes up and the game crashes. The problem is that, with pointers, there’s no way to know how many references are outstanding, given that clients can copy the pointers as many times as they like without telling the manager about it.
Another problem is that the underlying data organization can’t change with pointers. Any reallocation of buffers would immediately invalidate all outstanding pointers. This becomes especially important with saving the game to disk. Pointers can’t be saved to disk because the next time the game is loaded, system memory will probably be configured differently or we may even be on a completely different machine. The pointers must be converted into a form that can be restored, which will probably be an offset or a unique identifier of some sort. Working around this problem isn’t exactly trivial and can require a lot of work to support in client code.
So it’s plainly not a good idea for a safe and flexible resource manager to be handing out pointers. Rather than using pointers, or attempting to write some kind of super-intelligent over-complicated “smart pointer”, we can add one layer of abstraction and use handles instead, and put the burden on the manager class. Handles are an ancient programming concept that API’s have been using with great success for decades. An example of this is the HANDLE type returned by the CreateFile() call in Win32’s file system. A file handle, representing an open file system object, is created through the CreateFile() call, passed to other functions such as ReadFile() and SetFilePointer() for manipulation, and then finally closed off with CloseHandle(). Attempting to call those functions with an invalid or closed handle will not cause a crash, but will instead return an error code. This method is efficient, safe, and easy to understand.
Handles almost always fit into a single CPU register for efficient storage in collections and passing as parameters to functions. They can be easily checked for validity and provide a level of indirection that allows the underlying data organization to change without invalidating any outstanding handles. This has significant advantages over passing around pointers. Handles can also be easily saved to disk, because the data structures they refer to can be reconstructed in the same order on a game restore. This allows the handles to be stored directly with no conversions necessary, because they are already natively in unique identifier form.
The Handle Class
A fast and safe way to represent handles is to use an unsigned integer composed of two bitfield components (this class appears in Listing 1). The first component (m_Index) is a unique identifier for fast dereferencing into the handle manager’s database. The handle manager can use this number however it likes, but perhaps the most efficient is as a simple index into an std::vector. The second component (m_Magic) is a “magic number” that can be used to validate the handle. Upon dereferencing, the handle manager can check to make sure that the magic number component of the handle matches up with its corresponding entry in the database.
The Handle class is very simple and really doesn’t do much except manage the magic number. Upon calling Init(), the handle will be given the next magic number, which auto increments and will wrap around if necessary. Note that the magic number is not intended to be a GUID. Its purpose is to serve as a very simple and fast validity check and is relying on the high improbability of a condition arising where one object happens to have the same index and magic number (via wrapping) as another. The magic number of zero is reserved for the “null handle” – where the handle’s data is zero. The default Handle constructor sets itself to null, a state that will return true on an IsNull() query. This is convenient to use for an error condition – a function that creates an object and returns a handle to it can just return a null handle to indicate an error occurred.
In most ways the Handle class will act as a read-only unsigned integer. It’s not intended to be modified after being created, though it can safely be assigned back to null to reset it. You’ll notice that it’s a parameterized class, taking a TAG type in order to fully define it. The template parameter TAG doesn’t do anything except differentiate among types of handles – an object of type TAG is never used anywhere in the system. The motivation here is type safety. Without parameterizing Handle, a handle meant for one type of resource could be passed to a function expecting a handle to a different type of resource without a complaint from the compiler. So to keep things safe, we create a new handle type, taking any unique symbol and using it for the parameter. The TAG type can really be anything so long as it’s unique across Handle types, but it’s convenient to define an empty struct and use that in the typedef for a handle, like this texture handle example:
struct tagTexture { };
typedef Handle <tagTexture> HTexture;
Now we need a handle manager that is responsible for acquiring, dereferencing, and releasing objects (via handles) for a higher-level owner.
The HandleMgr Class
The HandleMgr class is a parameterized type composed of three main elements: a data store, a magic number store, and a free list (this class appears in Listing 2). The data store is simply a vector (or any other randomly accessible collection) of objects of type DATA. The DATA type, the first type parameter for HandleMgr, should be a very simple class that contains context information about the resource that it controls. For example, in a HandleMgr that manages files, the DATA type would probably just have the file handle and the name of the file:
struct FileEntry
{
std::string m_FileName;
HANDLE m_FileHandle; // OS file handle
};
struct tagFile { };
typedef Handle <tagFile> HFile;
typedef HandleMgr <FileEntry, HFile> FileHandleMgr;
This simple handle manager will maintain a set of context objects that correspond to all the open files that it knows about. The FileHandleMgr class will probably not be used directly by clients, but will instead be owned by another class (call it FileMgr) that handles the abstraction and knows about the problem domain (that is, what DATA is supposed to represent). This class might look something like this:
class FileMgr
{
FileHandleMgr m_Mgr;
public:
HFile OpenFile ( const char* name );
bool ReadFile ( HFile file, void* out, size_t bytes );
bool CloseFile( HFile file );
// ...
};
Upon calling any of these methods, FileMgr will ask its m_Mgr to dereference the handle to get at the actual FileEntry object. After verifying that the dereference succeeded (it will fail on an invalid handle), it will then perform the operation.
For our HandleMgr class, each handle will reference exactly one element within the object store, plus its corresponding element in the magic number store. Dereferencing the handles to get at the actual FileEntry object is as simple as using the m_Index component of the handle as an index into the object store (a very fast operation).
When dereferencing the handle, the code will also check the m_Magic component against the same index in the magic number store to make sure the handle is valid. As handles are freed and reacquired, corresponding entries in the magic number store are updated with the new handle magic numbers. This nearly guarantees that “dangling” handles on released objects won’t refer to unexpected objects when the slots are filled by a later handle acquisition, but will instead simply fail to work and return an error code. Obviously, the magic number store will always have the same number of elements as the object store.
As objects are released, the handle manager will add the indexes of the slots they occupy to the free list. This saves it the trouble of needing to search through the object store to find an open slot, which results in a tasty O(n) complexity for new handle acquisition. It’s important to note that the DATA type is not your typical C++ class. It shouldn’t have constructors and destructors that do anything important, such as acquire and release local resources. Objects contained within the object store are constructed, destroyed, and copied as the vector class sees fit. Note that the std::string used in the sample FileEntry is “simple” enough for our needs – it’s reference-counted, which minimizes the impact of its constructors and destructors and makes it nearly free for vector to copy.
When asked to acquire an object from the store, we’ll likely end up reusing an object that has already been constructed but is no longer in use, as indicated by its entry in the free list. It will need its members reinitialized before it can be used, because it won’t have had the constructor call to set it up. When an object is freed from the store, it will not get destroyed, but will instead have its index added to the free list, and as such will need its resources manually freed. These minor limitations arise from the fact that we’re embedding our DATA type directly in the vector, rather than using pointers and creating and destroying the objects with new and delete for each handle acquisition and release. The major advantage here is speed, in that the objects don’t have to be completely brought up and shut down each time. To make things more convenient, the initialize/shutdown code can be moved into member functions for easy callback by the HandleMgr owner.
The amount of handle validation necessary may depend on the application, and could even be chosen through an additional template parameter for HandleMgr. For example, the test for an invalid handle may be found to be unnecessary and could be removed (though the debug assertion should always remain). For a more robust system where error handling is important, the code could, upon detecting an invalid handle, set an error condition, and then abort the function call.
Sample Usage
In Listing 3 I provide a sample texture manager class. This class allows clients to ask it for textures by name and will construct them on demand. It automatically unloads the textures on deletion, and provides a set of query functions to use the textures. The textures are indexed by name for speedy lookup to make sure that the same texture is not added to the store twice. It would be a simple exercise to add reference counting to this example to make it safer, replacing DeleteTexture() with ReleaseTexture().
For another (larger) sample of file handle usage, see the sample code for my GDC 2000 talk, It’s Still Loading? Designing an Efficient File System, available from http://www.drizzle.com/~scottb/gdc/.
Notes
The HandleMgr class is very simple and is meant to illustrate some basic concepts, but it can be expanded in a number of ways, either with the existing HandleMgr or separate classes:
· Create a HandleMgr that will work better with larger DATA objects, holding them indirectly through pointers. It would also allow hiding of the data structure to clients.
· Add automatic reference counting as standard functionality, rather than leaving it to be the responsibility of the owner of the HandleMgr.
· Add support for constant-time iteration over the potentially sparse object store by embedding a linked list within its elements. Use STL style iterator naming and operation for consistency.
· Many databases, such as a font manager or texture manager, will likely require indexes to access objects by name to retrieve handles. Build this in as a standard feature or as a separate (derivative) class.
· The HandleMgr system is especially effective when combined with the Singleton pattern (see “An Automatic Singleton Utility” elsewhere in this book). Many of a game’s databases are naturally singletons.
· Take the Singleton pattern a little further, and make the TAG type of Handle actually be the type that it corresponds to within the HandleMgr. Then the Handle could have an operator -> that would dereference itself into a TAG by directly accessing the Singleton that manages it.
· Save game functionality should be fairly easy to add, but it is necessarily specific to your game’s architecture. The handles can be saved out directly – just make sure that the HandleMgr stores the indexes for its objects along with the object data, and on restore, all handles will remain valid.
Listing 1 – Handle
#include <cassert>
template <typename TAG>
class Handle
{
union
{
enum
{
// sizes to use for bit fields
MAX_BITS_INDEX = 16,
MAX_BITS_MAGIC = 16,
// sizes to compare against for asserting dereferences
MAX_INDEX = ( 1 << MAX_BITS_INDEX) - 1,
MAX_MAGIC = ( 1 << MAX_BITS_MAGIC) - 1,
};
struct
{
unsigned m_Index : MAX_BITS_INDEX; // index into resource array
unsigned m_Magic : MAX_BITS_MAGIC; // magic number to check
};
unsigned int m_Handle;
};
public:
// Lifetime.
Handle( void ) : m_Handle( 0 ) { }
void Init( unsigned int index );
// Query.
unsigned int GetIndex ( void ) const { return ( m_Index ); }
unsigned int GetMagic ( void ) const { return ( m_Magic ); }
unsigned int GetHandle( void ) const { return ( m_Handle ); }
bool IsNull ( void ) const { return ( !m_Handle ); }
operator unsigned int ( void ) const { return ( m_Handle ); }
};
template <typename TAG>
void Handle <TAG> :: Init( unsigned int index )
{
assert( IsNull() ); // don't allow reassignment
assert( index <= MAX_INDEX ); // verify range
static unsigned int s_AutoMagic = 0;
if ( ++s_AutoMagic > MAX_MAGIC )
{
s_AutoMagic = 1; // 0 is used for "null handle"
}
m_Index = index;
m_Magic = s_AutoMagic;
}
template <typename TAG>
inline bool operator != ( Handle <TAG> l, Handle <TAG> r )
{ return ( l.GetHandle() != r.GetHandle() ); }
template <typename TAG>
inline bool operator == ( Handle <TAG> l, Handle <TAG> r )
{ return ( l.GetHandle() == r.GetHandle() ); }
Listing 2 – HandleMgr
#include <vector>
#include <cassert>
template <typename DATA, typename HANDLE>
class HandleMgr
{
private:
// private types
typedef std::vector <DATA> UserVec;
typedef std::vector <unsigned int> MagicVec;
typedef std::vector <unsigned int> FreeVec;
// private data
UserVec m_UserData; // data we're going to get to
MagicVec m_MagicNumbers; // corresponding magic numbers
FreeVec m_FreeSlots; // keeps track of free slots in the db
public:
// Lifetime.
HandleMgr( void ) { }
~HandleMgr( void ) { }
// Handle methods.
// acquisition
DATA* Acquire( HANDLE& handle );
void Release( HANDLE handle );
// dereferencing
DATA* Dereference( HANDLE handle );
const DATA* Dereference( HANDLE handle ) const;
// other query
unsigned int GetUsedHandleCount( void ) const
{ return ( m_MagicNumbers.size() - m_FreeSlots.size() ); }
bool HasUsedHandles( void ) const
{ return ( !!GetUsedHandleCount() ); }
};
template <typename DATA, typename HANDLE>
DATA* HandleMgr <DATA, HANDLE> :: Acquire( HANDLE& handle )
{
// if free list is empty, add a new one otherwise use first one found
unsigned int index;
if ( m_FreeSlots.empty() )
{
index = m_MagicNumbers.size();
handle.Init( index );
m_UserData.push_back( DATA() );
m_MagicNumbers.push_back( handle.GetMagic() );
}
else
{
index = m_FreeSlots.back();
handle.Init( index );
m_FreeSlots.pop_back();
m_MagicNumbers[ index ] = handle.GetMagic();
}
return ( m_UserData.begin() + index );
}
template <typename DATA, typename HANDLE>
void HandleMgr <DATA, HANDLE> :: Release( HANDLE handle )
{
// which one?
unsigned int index = handle.GetIndex();
// make sure it's valid
assert( index < m_UserData.size() );
assert( m_MagicNumbers[ index ] == handle.GetMagic() );
// ok remove it - tag as unused and add to free list
m_MagicNumbers[ index ] = 0;
m_FreeSlots.push_back( index );
}
template <typename DATA, typename HANDLE>
inline DATA* HandleMgr <DATA, HANDLE>
:: Dereference( HANDLE handle )
{
if ( handle.IsNull() ) return ( 0 );
// check handle validity - $ this check can be removed for speed
// if you can assume all handle references are always valid.
unsigned int index = handle.GetIndex();
if ( ( index >= m_UserData.size() )
|| ( m_MagicNumbers[ index ] != handle.GetMagic() ) )
{
// no good! invalid handle == client programming error
assert( 0 );
return ( 0 );
}
return ( m_UserData.begin() + index );
}
template <typename DATA, typename HANDLE>
inline const DATA* HandleMgr <DATA, HANDLE>
:: Dereference( HANDLE handle ) const
{
// this lazy cast is ok - non-const version does not modify anything
typedef HandleMgr <DATA, HANDLE> ThisType;
return ( const_cast <ThisType*> ( this )->Dereference( handle ) );
}
Listing 3 – Sample Managed Class
#include <vector>
#include <map>
#include <cassert>
// ... [ platform-specific surface handle type here ]
typedef LPDIRECTDRAWSURFACE7 OsHandle;
struct tagTexture { };
typedef Handle <tagTexture> HTexture;
class TextureMgr
{
// Texture object data and db.
struct Texture
{
typedef std::vector <OsHandle> HandleVec;
std::string m_Name; // for reconstruction
unsigned int m_Width; // mip 0 width
unsigned int m_Height; // mip 1 width
HandleVec m_Handles; // handles to mip surfaces
OsHandle GetOsHandle( unsigned int mip ) const
{
assert( mip < m_Handles.size() );
return ( m_Handles[ mip ] );
}
bool Load ( const std::string& name );
void Unload( void );
};
typedef HandleMgr <Texture, HTexture> HTextureMgr;
// Index by name into db.
// case-insensitive string comparison predicate
struct istring_less
{
bool operator () ( const std::string& l, const std::string& r ) const
{ return ( ::stricmp( l.c_str(), r.c_str() ) < 0 ); }
};
typedef std::map <std::string, HTexture, istring_less > NameIndex;
typedef std::pair <NameIndex::iterator, bool> NameIndexInsertRc;
// Private data.
HTextureMgr m_Textures;
NameIndex m_NameIndex;
public:
// Lifetime.
TextureMgr( void ) { /* ... */ }
~TextureMgr( void );
// Texture management.
HTexture GetTexture ( const char* name );
void DeleteTexture( HTexture htex );
// Texture query.
const std::string& GetName( HTexture htex ) const
{ return ( m_Textures.Dereference( htex )->m_Name ); }
int GetWidth( HTexture htex ) const
{ return ( m_Textures.Dereference( htex )->m_Width ); }
int GetHeight( HTexture htex ) const
{ return ( m_Textures.Dereference( htex )->m_Height ); }
OsHandle GetTexture( HTexture htex, unsigned int mip = 0 ) const
{ return ( m_Textures.Dereference( htex )->GetOsHandle( mip ) ); }
};
TextureMgr :: ~TextureMgr( void )
{
// release all our remaining textures before we go
NameIndex::iterator i, begin = m_NameIndex.begin(), end = m_NameIndex.end();
for ( i = begin ; i != end ; ++i )
{
m_Textures.Dereference( i->second )->Unload();
}
}
HTexture TextureMgr :: GetTexture( const char* name )
{
// insert/find
NameIndexInsertRc rc =
m_NameIndex.insert( std::make_pair( name, HTexture() ) );
if ( rc.second )
{
// this is a new insertion
Texture* tex = m_Textures.Acquire( rc.first->second );
if ( !tex->Load( rc.first->first ) )
{
DeleteTexture( rc.first->second );
rc.first->second = HTexture();
}
}
return ( rc.first->second );
}
void TextureMgr :: DeleteTexture( HTexture htex )
{
Texture* tex = m_Textures.Dereference( htex );
if ( tex != 0 )
{
// delete from index
m_NameIndex.erase( m_NameIndex.find( tex->m_Name ) );
// delete from db
tex->Unload();
m_Textures.Release( htex );
}
}
bool TextureMgr::Texture :: Load( const std::string& name )
{
m_Name = name;
// ... [ load texture from file system, return false on failure ]
return ( true /* or false on error */ );
}
void TextureMgr::Texture :: Unload( void )
{
m_Name.erase();
// ... [ free up mip surfaces ]
m_Handles.clear();
}