Although Doom 3 was released 13 years ago, there is still of lot of interesting stuff to find in it. The main reason for that is: it was developed in the time of changes. The ID software team had just moved from C to C++ (using Visual C++ 6). Graphic cards were moving from fixed pipeline to programming pipeline, CPUs were getting SIMD extensions. All of this caused a lot of diversity in the code: crazy mix of C++/C/asm code, several renderer backends, code acceleration for MMX/SSE/AltiVec (yeah, Macs used PowerPC at that time). Not to mention tons of scripts and defs, including C++-like scripting language, and in-game GUI system.

I have to deal with Doom 3 engine in the context of The Dark Mod (TDM for short).

This article is about memory debugging configuration in Doom 3 SDK (more precisely, "Debug with inlines and memory log").

Example

To get started, here are some messages dumped to game console in the memory debugging configuration (current version of TDM):

Also, after exiting game, a file "tdm_main_leak_size.txt" appears with this data:

size: 40 KB, allocs: 3: idlib/containers/HashIndex.cpp, line: 53
size: 24 KB, allocs: 3: idlib/containers/HashIndex.cpp, line: 50
size: 22 KB, allocs: 212: game/Game_local.cpp, line: 7116
size: 18 KB, allocs: 523: idlib/Str.cpp, line: 90
size: 8 KB, allocs: 38: c:/thedarkmod/tdm/idlib/containers/List.h, line: 377
size: 6 KB, allocs: 138: game/DarkModGlobals.cpp, line: 467
size: 3 KB, allocs: 150: , line: 0
size: 3 KB, allocs: 35: renderer/Model_md5.cpp, line: 743
size: 2 KB, allocs: 110: game/darkModLAS.cpp, line: 1282
size: 1 KB, allocs: 8: game/Objectives/ObjectiveLocation.cpp, line: 72
size: 0 KB, allocs: 39: game/SndPropLoader.cpp, line: 723
size: 0 KB, allocs: 39: game/SndProp.cpp, line: 339
size: 0 KB, allocs: 13: game/SEED.cpp, line: 3449
size: 0 KB, allocs: 8: renderer/draw_arb2.cpp, line: 841
size: 0 KB, allocs: 8: c:/thedarkmod/tdm/idlib/math/Polynomial.h, line: 601
size: 0 KB, allocs: 2: framework/I18N.cpp, line: 428
size: 0 KB, allocs: 1: framework/FileSystem.cpp, line: 2756
size: 0 KB, allocs: 3: game/EscapePointManager.cpp, line: 181
1333 total memory blocks allocated
134 KB memory allocated

Memory leak detection does not feel new, but the fact that each message about uninitialized member contains the exact name of the member is quite intriguing.

Memory debugging

First let's deal with the simpler part: memory heap debugging. Looking at Heap.h, we see that ID_DEBUG_MEMORY enables a special piece of code:

#else /* ID_DEBUG_MEMORY */

void * Mem_Alloc( const int size, const char *fileName, const int lineNumber );
void * Mem_ClearedAlloc( const int size, const char *fileName, const int lineNumber );
void Mem_Free( void *ptr, const char *fileName, const int lineNumber );
char * Mem_CopyString( const char *in, const char *fileName, const int lineNumber );
void * Mem_Alloc16( const int size, const char *fileName, const int lineNumber );
void Mem_Free16( void *ptr, const char *fileName, const int lineNumber );

#ifdef ID_REDIRECT_NEWDELETE

__inline void *operator new( size_t s, int t1, int t2, char *fileName, int lineNumber ) {
    return Mem_Alloc( s, fileName, lineNumber );
}
__inline void operator delete( void *p, int t1, int t2, char *fileName, int lineNumber ) {
    Mem_Free( p, fileName, lineNumber );
}
__inline void *operator new[]( size_t s, int t1, int t2, char *fileName, int lineNumber ) {
    return Mem_Alloc( s, fileName, lineNumber );
}
__inline void operator delete[]( void *p, int t1, int t2, char *fileName, int lineNumber ) {
    Mem_Free( p, fileName, lineNumber );
}
__inline void *operator new( size_t s ) {
    return Mem_Alloc( s, "", 0 );
}
__inline void operator delete( void *p ) {
    Mem_Free( p, "", 0 );
}
__inline void *operator new[]( size_t s ) {
    return Mem_Alloc( s, "", 0 );
}
__inline void operator delete[]( void *p ) {
    Mem_Free( p, "", 0 );
}

#define ID_DEBUG_NEW new( 0, 0, __FILE__, __LINE__ )
#undef new
#define new ID_DEBUG_NEW

#endif

#define Mem_Alloc( size ) Mem_Alloc( size, __FILE__, __LINE__ )
#define Mem_ClearedAlloc( size ) Mem_ClearedAlloc( size, __FILE__, __LINE__ )
#define Mem_Free( ptr ) Mem_Free( ptr, __FILE__, __LINE__ )
#define Mem_CopyString( s ) Mem_CopyString( s, __FILE__, __LINE__ )
#define Mem_Alloc16( size ) Mem_Alloc16( size, __FILE__, __LINE__ )
#define Mem_Free16( ptr ) Mem_Free16( ptr, __FILE__, __LINE__ )

#endif /* ID_DEBUG_MEMORY */

The first part declares debug versions of ID's memory allocation functions, each of them having additional parameters filename and lineNumber. Then global operator new and operator delete are overriden to capture all allocations done with standard new/delete. Again, they have additional parameters. After that the main source of issues comes: new keyword is redefined with a macro, which allows to capture file and line of each call automatically.

The implementation of debug memory allocation looks like:

void *Mem_AllocDebugMemory( const int size, const char *fileName,
                    const int lineNumber, const bool align16 ) {
    //...

    void *p = mem_heap->Allocate( size + sizeof( debugMemory_t ) );
    Mem_UpdateAllocStats( size );

    debugMemory_t *m = (debugMemory_t *) p;
    m->fileName = fileName;
    m->lineNumber = lineNumber;
    m->frameNumber = idLib::frameNumber;
    m->size = size;
    m->next = mem_debugMemory;
    m->prev = NULL;
    if ( mem_debugMemory )
        mem_debugMemory->prev = m;
    mem_debugMemory = m;

    return ( ( (byte *) p ) + sizeof( debugMemory_t ) );
}

Each user-returned block of memory is prepended by 32 bytes of data, stored in debugMemory_t struct. It captures some information about allocation. When this memory is freed, size data member is used to update allocation stats and to provide some limited double-free detection. Since all the blocks are always linked in a doubly linked list, it is straight-forward to dump all used dynamic memory blocks at any moment, including doing so at program termination to detect memory leaks.

In order to see memory stats constantly during playing, you can type com_showMemoryUsage 1 into the game console, and you'll see something like this:

The main benefit of implementing memory profiling system yourself versus taking a ready third-party solution is that you can see exactly the data you need. In this case, per-frame allocation data is recorded and shown (which works thanks to Mem_ClearFrameStats being called each frame).

As for dumping memory blocks, there are three ways to do it:

1. Exit game and look into file [tdm_game]_leak_location.txt (contents were shown above): this way is used to detect memory leaks.
2. Write memoryDump into game console and look into created file memoryDump.txt. This file contains all blocks alive, and can be used to perform additional offline analysis (sample).
3. Write memoryDumpCompressed -s into game console and look into file memoryDump.txt. Unlike the previous command, this one shows per-allocation-site statistics sorted according to parameter (-s = by size), which is rather compact (300 lines):

Uninitialized members

Leaving class members of primitive type uninitialized can cause annoying and non-reproducible bugs. That's why Visual C++ fills allocated memory with magic values like 0xCD or 0xCC in debug build, to increase the chances of program crashing due to such an error. For some reason, ID devs decided to implement their own version of this system for game objects.

In the game module of Doom 3, most of the classes inherit from idClass base, which allows to create object instance by type name and supports events for scripting system. All objects in this hierarchy are manually filled with 0xCD because idClass overloads operator new and operator delete:

void * idClass::operator new( size_t s ) {
    int *p;

    s += sizeof( int );
    p = (int *)Mem_Alloc( s );
    *p = s;
    memused += s;
    numobjects++;

#ifdef ID_DEBUG_UNINITIALIZED_MEMORY
    unsigned int *ptr = (unsigned int *)p;
    int size = s;
    assert( ( size & 3 ) == 0 );
    size >>= 2;
    for ( int i = 1; i < size; i++ ) {
        ptr[i] = 0xcdcdcdcd;
    }
#endif

    return p + 1;
}

Now the remaining question is: where are the messages about uninitialized class members coming from?

Quick search by the text of message gives the following bits of code:

#define CLASS_DECLARATION( nameofsuperclass, nameofclass ) \
    //...some more ...                                     \
    idClass *nameofclass::CreateInstance( void ) {         \
        try {                                              \
            nameofclass *ptr = new nameofclass;            \
            ptr->FindUninitializedMemory();                \
            return ptr;                                    \
        }                                                  \
        catch( idAllocError & ) {                          \
            return NULL;                                   \
        }                                                  \
    }                                                      \

void idClass::FindUninitializedMemory( void ) {
#ifdef ID_DEBUG_UNINITIALIZED_MEMORY
    unsigned int *ptr = ( ( unsigned int * )this ) - 1;
    int size = *ptr;
    assert( ( size & 3 ) == 0 );
    size >>= 2;
    for ( int i = 0; i < size; i++ ) {
        if ( ptr[i] == 0xcdcdcdcd ) {
            const char *varName = GetTypeVariableName( GetClassname(), i << 2 );
            gameLocal.Warning(
                "type '%s' has uninitialized variable %s (offset %d)",
                GetClassname(), varName, i << 2
            );
        }
    }
#endif
}

The method CreateInstance (wrapped into macro CLASS_DECLARATION) allows creating game objects by type, and it is always called when a game object is created. As you see, it calls FindUninitializedMemory method after creation, which checks which words still have values 0xCDCDCDCD, and reports them. The only thing remaining is the GetTypeVariableName function, and this is where the truly dark magic is.

TypeInfo

In order to obtain name of the class member from its offset, information about all the member offsets must be embedded into the code. Currently, C++ compilers do not do that (although there are proposals for something like that). Standard C++ RTTI only stores class name and inheritance hierarchy for polymorphic types, it does not store any info about members. There are several approaches for implementing reflection in C++. Preprocessor can generate the necessary information, given that you use macros for declaring members (example), or specialized parser can generate the necessary information (e.g. Qt MOC). Doom 3 uses the latter way: homebrew parser does that.

Recall that Doom 3 uses its own C++-like scripting language, which is parsed, compiled and interpreted by custom code (see review). The lexer and parser are reused for several different tasks. The parser also performs all the job of C preprocessor: it #includes files, checks #if-s and #ifdef-s, manages #define-s and performs macro substitution. This same parser is reused in the specialized TypeInfo compiler, whose only purpose is to generate a header with all the desired type information. It parses a single cpp file of the game module, which is supposed to include headers with all the declarations. So: ID's script parser is good enough to parse Doom 3 game sources and extract data from them! Well, it has its own issues (no pragma once support, some C++11 syntax not supported), but this is a remarkable achievement nonetheless.

After having parsed everything, TypeInfo compiler generates a header GameTypeInfo.h in game/gamesys/. This header contains the following information (you can download resulting GameTypeInfo.h for TDM):

1. constants: type, name, value (including enum values and static const members);
2. enums: list of all enums, list of name/value pairs for all enums;
3. class members: type, name, offset, size;
4. classes: full list, name, base class name, pointer to members list;

Here is an example of information for members of idStr class:

static classVariableInfo_t idStr_typeInfo[] = {
    { "int", "len", (int)(&((idStr *)0)->len), sizeof( ((idStr *)0)->len ) },
    { "char *", "data", (int)(&((idStr *)0)->data), sizeof( ((idStr *)0)->data ) },
    { "int", "alloced", (int)(&((idStr *)0)->alloced), sizeof( ((idStr *)0)->alloced ) },
    { "char[20]", "baseBuffer", (int)(&((idStr *)0)->baseBuffer), sizeof( ((idStr *)0)->baseBuffer ) },
    { NULL, 0 }
};

Clearly, it contains enough information to make it possible to get member name from offset. Note that sizes and offsets are written as C++ expressions evaluated to proper values, instead of plain integer constants. This allows to avoid messing with struct alignment rules of Visual C++ compiler. However, it also requires to do an ugly hack (called "Public Morozov" in Russia) to make sure that private and protected members are accessible in TypeInfo.cpp:

// This is real evil but allows the code
// to inspect arbitrary class variables.
#define private     public
#define protected   public

Here is the full diagram for building TypeInfo in memory debugging configuration (for the case of TDM):

Saving game state

Is it worth to implement the whole TypeInfo thing just for printing the name of an uninitialized member? I think not. But this is not the only thing which relies on TypeInfo. Another thing made possible by TypeInfo is printing the whole game state in a readable text format. Normally, all the savegame data is stored in binary format, because it is much faster to do so and the resulting file is smaller (although I added compression on top of it in TDM). But text representation may be very useful for debugging issues (e.g. forgot to save/restore some member), maybe even maintaining backwards compatibility of savegame files.

The code is located in the same TypeInfo.cpp file. It contains several methods which traverse all the game objects and do something with them. All of them rely on the methods idTypeInfoTools::WriteClass_r and  idTypeInfoTools::WriteVariable_r, which implement the traversal itself. The latter method is responsible for interpreting every possible type of class member; for instance it contains special code which supports traversing all elements of idList container (which is ID's equivalent to std::vector):

int idTypeInfoTools::WriteVariable_r(
    const void *varPtr, const char *varName, const char *varType,
    const char *scope, const char *prefix, const int pointerDepth
) {
    //...(more code)...
    } else if ( token == "idList" ) {
        idList<int> *list = ((idList<int> *)varPtr);
        Write(varName, varType, scope, prefix, ".num", va( "%d", list->Num() ), NULL, 0);
        Write(varName, varType, scope, prefix, ".granularity", va( "%d", list->GetGranularity() ), NULL, 0);
        if ( list->Num() && ParseTemplateArguments( typeSrc, templateArgs ) ) {
            void *listVarPtr = list->Ptr();
            for ( i = 0; i < list->Num(); i++ ) {
                idStr listVarName = va( "%s[%d]", varName, i );
                int size = WriteVariable_r(listVarPtr, listVarName, templateArgs, scope, prefix, pointerDepth);
                if ( size == -1 )
                    break;
                listVarPtr = (void *)( ( (byte *) listVarPtr ) + size );
            }
        }

        typeSize = sizeof( idList<int> );
    } else if ( token == "idStaticList" ) {
    //...(more code)...
}

During traversal, method Write is called, as you can see on lines 5 and 8 of the last listing. This is actually not a method, but a function pointer, which is initialized differently depending on the current needs. This method accepts seven parameters:

varType | prefix | scope | varName | postfix | value | varSize
====================================================================================================
"float" | "" | "idEntity" | "m_MinLODBias" | "" | "0" | 4
"idBounds" | "idEntity::renderEntity." | "renderEntity_t" | "bounds" | "" | "(-6.75103283 -2.63098955 -20)-(7 2.5482502 49.51835632)" | 24
"idDict" | "" | "idEntity" | "spawnArgs" | "[7]" | "'noclipmodel'  '0'" | 0
"idEntity::entityFlags_s" | "" | "idEntity" | "fl" | ".invisible" | "false" | 0
"idList < idEntityPtr < idActor > >" | "idEntity::m_userManager." | "UserManager" | "m_users" | ".num" | "0" | 0

In this text, first line specifies order of seven parameters, and each of the next lines shows one example of their values, seven values per line, splitted with vertical dash. The first example corresponds to member idEntity::m_MinLODBias of float type, having zero value. The second one corresponds to member renderEntity_s::bounds of type idBounds (coordinates of two vertices are given), where renderEntity_s itself is a member idEntity::renderEntity. The third one shows 7-th entry of idEntity::spawnArgs dictionary (idDict) as 'key'-'value' pair. The forth example is a boolean value entityFlags_s::invisible in bitset structure idEntity::fl. The last one corresponds to number of elements in UserManager::m_Users, which has type idList (aggregated in idEntity::m_userManager).

Now let's return back to Doom 3 and game state saving. Whenever you save game in memory debugging configuration, a file named like "Quicksave_1_save.gameState.txt" is created near the ordinary savegame file. This is a text file of size about 40MB, where each member of each game entity is fully described. The full version of this file can be downloaded, and here is a small excerpt from it:

entity 36 idStaticEntity {
idEntity::entityNumber = "36"
idEntity::entityDefNumber = "28"
idEntity::spawnNode = "<unknown type 'idLinkList < idEntity >'>"
idEntity::activeNode = "<unknown type 'idLinkList < idEntity >'>"
idEntity::snapshotNode = "<unknown type 'idLinkList < idEntity >'>"
idEntity::snapshotSequence = "-1"
idEntity::snapshotBits = "0"
idEntity::name = "func_static_5"
idEntity::spawnArgs[0] = "'classname'  'func_static'"
idEntity::spawnArgs[1] = "'name'  'func_static_5'"
idEntity::spawnArgs[2] = "'model'  'models/darkmod/furniture/seating/chair_simple01.lwo'"
idEntity::spawnArgs[3] = "'origin'  '216.743 -47.89 20'"
idEntity::spawnArgs[4] = "'rotation'  '0.707107 -0.707107 0 0.707107 0.707107 0 0 0 1'"
idEntity::spawnArgs[5] = "'inline'  '0'"
idEntity::spawnArgs[6] = "'spawnclass'  'idStaticEntity'"
idEntity::spawnArgs[7] = "'solid'  '1'"
idEntity::spawnArgs[8] = "'noclipmodel'  '0'"
idEntity::scriptObject.idScriptObject::type = "<pointer type 'idTypeDef *' not listed>"
idEntity::scriptObject.idScriptObject::data = "<NULL>"
idEntity::thinkFlags = "0"
idEntity::dormantStart = "-2920"
idEntity::cinematic = "0"
idEntity::cameraTarget = "<NULL>"
idEntity::targets.num = "0"
idEntity::targets.granularity = "16"
idEntity::health = "0"
idEntity::maxHealth = "0"
idEntity::fl.notarget = "false"
idEntity::fl.noknockback = "false"

Whenever you restore game from a save in this configuration, full game state after loading is saved into file "Quicksave_1_restore.gameState.txt". Moreover, this restored state is compared field-by-field with the old one (which was written on save) using the same game state traversal code, and messages about mismatches (i.e. state diffs) are printed to the game console:

Conclusion

So all of this was about a tiny little part of Doom 3 source code: memory debugging and typeinfo processing. It is worth noting that typeinfo stuff was completely removed by ID from Doom3 BFG (it is missing in the sources). Most likely this is because of the maintenance burden it causes. You can read more about the issues caused by all this hackery in the corresponding TDM wiki article.

Speaking of TDM, now we have to understand how much value this system has. The first moves would be to fix all the issues detected currently, and to add support for some new data structures (include STL stuff). The TypeInfo system would either give some benefit or be removed, and it is not clear yet which path would be taken.