Привет!

Сегодня я хотел бы обсудить систему управления памятью в игре The Simpsons: Hit & Run 2003. Статья будет состоять из двух частей, в первой из которых будет обсуждаться само использование такой системы управления памятью, а во второй будет рассказано о внутреннем устройстве этой системы.

Управление памятью в данной игре представлено специальными аллокаторами. Аллокатор - класс, реализующий детали распределения и освобождения ресурсов компьютерной памяти. То есть какой-то аллокатор может выделять память через обычный malloc, с логгированием выделенной информации, а другой аллокатор может заранее выделять n-ое кол-во байт под свое хранилище, из которого в последствии будет запрашиваться память.

Часть 1

Виды аллокаторов

Полный список всех видов аллокаторов, представленных в игре, можно найти в файле srrmemory.h. Там он представлен в виде перечисления (enum):

enum GameMemoryAllocator
{                                              // 
    GMA_DEFAULT = RADMEMORY_ALLOC_DEFAULT,     //    0         
    GMA_TEMP = RADMEMORY_ALLOC_TEMP,           //    1         
#ifdef RAD_GAMECUBE                                            
    GMA_GC_VMM = RADMEMORY_ALLOC_VMM,          //    2         
#endif                                                         
    GMA_PERSISTENT = 3,                        //    3         
    GMA_LEVEL,                                 //    4          
    GMA_LEVEL_MOVIE,                           //    5         
    GMA_LEVEL_FE,                              //    6         
    GMA_LEVEL_ZONE,                            //    7         
    GMA_LEVEL_OTHER,                           //    8         
    GMA_LEVEL_HUD,                             //    9         
    GMA_LEVEL_MISSION,                         //    10        
    GMA_LEVEL_AUDIO,                           //    11        
    GMA_DEBUG,                                 //    12        
    GMA_SPECIAL,                               //    13        
    GMA_MUSIC,                                 //    14        
    GMA_AUDIO_PERSISTENT,                      //    15        
    GMA_SMALL_ALLOC,                           //    16
#ifdef RAD_XBOX                                
    GMA_XBOX_SOUND_MEMORY,                     //    17           
#endif
#ifdef USE_CHAR_GAG_HEAP
    GMA_CHARS_AND_GAGS,
#else
    GMA_CHARS_AND_GAGS = GMA_LEVEL_OTHER,
#endif
    GMA_ANYWHERE_IN_LEVEL = 25,                //    25        
    GMA_ANYWHERE_IN_FE,                        //    26        
    GMA_EITHER_OTHER_OR_ZONE,                  //    27     

    GMA_ALLOCATOR_SEARCH = ALLOCATOR_SEARCH,   //   If you feel like using this one, see an example in FMVPlayer::LoadData
    NUM_GAME_MEMORY_ALLOCATORS
};

Почти для каждого элемента этого enum представлен свой отдельный аллокатор, но для GMA_ALLOCATOR_SEARCH, GMA_ANYWHERE_IN_LEVEL , GMA_ANYWHERE_IN_FE и GMA_EITHER_OTHER_OR_ZONE отдельных аллокаторов не представлено.

Практически каждый такой аллокатор представлен для отдельного типа информации, будь то музыка (GMA_MUSIC), информация связанная с уровнем (GMA_LEVEL) и так далее.

Использование

Рассмотрим использование такой системы управления памятью на примере из файла avatar.cpp:

        HeapMgr()->PushHeap (GMA_LEVEL_OTHER);

        mpVehicleMappable = new VehicleMappable;
        mpVehicleMappable->AddRef();

#ifdef RAD_PS2
        mpVehicleMappableUSB0 = new VehicleMappable;
        mpVehicleMappableUSB0->AddRef();

        mpVehicleMappableUSB1 = new VehicleMappable;
        mpVehicleMappableUSB1->AddRef();
#endif
        
        mpHumanVehicleController = new HumanVehicleController;
        mpHumanVehicleController->AddRef();
        
        mpInCarCharacterMappable = new InCarCharacterMappable;
        mpInCarCharacterMappable->AddRef();

        mpBipedCharacterMappable = new BipedCharacterMappable;
        mpBipedCharacterMappable->AddRef();

        mpCameraRelativeCharacterController = new CameraRelativeCharacterController;
        mpCameraRelativeCharacterController->AddRef();

        HeapMgr()->PopHeap (GMA_LEVEL_OTHER);

В начале идет вызов метода PushHeap, в который мы передаем тип аллокатора, из которого будем запрашивать память. Затем идет само выделение памяти через вызов перегруженного оператора new. А в конце идет вызов метода PopHeap, в который мы должны передать тип аллокатора, из которого происходило выделение памяти.

Разберем этот код по порядку:

HeapManager

HeapManager является singleton классом посредником между классом HeapStack и пользователем (HeapManager хранит в своих полях экземпляр класса HeapStack). В свою очередь HeapStack является обычным стэком (структура данных), который хранит элементы типа GameMemoryAllocator.

Метод PushHeap представляет собой вызов метода Push у экземпляра HeapStack, который в свою очередь просто кладет переданный объект типа GameMemoryAllocator на вершину стэка.

Метод PopHeap представляет собой вызов метода Pop у экземпляра HeapStack, который удаляет объект, находящийся на вершине стэка.

Скрытый текст

(*) Инициализация аллокаторов происходит в методах PrepareHeapsStartup, PrepareHeapsFeSetup, PrepareHeapsInGame и PrepareHeapsSuperSprint.

Оператор new

Перегруженный оператор new имеет вид:

void* operator new( size_t size )
#ifdef RAD_PS2
#ifndef RAD_MW
throw( std::bad_alloc ) // может бросить исключение std::bad_alloc
#endif
#endif
{
    if( gMemorySystemInitialized == false )
    {
        INIT_MEM();
    }

    void* pMemory;

    if (g_NoHeapRoute)
    {
        pMemory = radMemoryAlloc( 0, size );
    }
    else
    {
        GameMemoryAllocator curr = HeapMgr()->GetCurrentHeap();
        pMemory = AllocateThis( curr, size );

#ifdef MEMORYTRACKER_ENABLED
        ::radMemoryMonitorIdentifyAllocation (pMemory, HeapMgr()->GetCurrentGroupID ());
#endif
    }


    //MEMTRACK_ALLOC( pMemory, size, 0 );

    return( pMemory );
}

Разберем каждую строчку оператора new по порядку:

INIT_MEM

Инициализация макроса INIT_MEM может отличаться в зависимости от платформы на которой запущена игра. Реализации их схожи, но для простоты разберем реализацию этого макроса для PS2:

#define INIT_MEM()  Memory::InitializeMemoryUtilities();PS2Platform::InitializeMemory();

Memory::InitializeMemoryUtilities() - функция, которая вызывается один раз за всю работу программы, и выполняет расчет максимального кол-ва свободной памяти на устройстве (а конкретно только под PS2):

void InitializeMemoryUtilities()
{
    static bool alreadyCalled = false;
    if( alreadyCalled )
    {
        return;
    }
    alreadyCalled = true;
#ifdef RAD_PS2
    //this is the largest amount of memory that is free
    g_MaxFreeMemory = GetFreeMemoryProfile();
#endif
}

Скрытый текст

(*) Стоит учитывать, что память PS2 была представлена в виде карт памяти.

Функция GetFreeMemoryProfile проходится по всем картам памяти PS2 и расчитывает, сколько памяти свободно на момент запуска игры.

Разберем код функции GetFreeMemoryProfile по порядку:

Инициализация:

    const int size = 256;
    void* pointers[ size ];
    size_t sizes[ size ];

    int index = 0;
    int i;
    for( i = 0; i < size; i++ )
    {
        pointers[ i ] = NULL;
        sizes[ i ] = 0;
    }

Сначала мы создаем два массива на 256 элементов, где массив pointers будет хранить всю выделенную память за время работы функции, а массив sizes будет хранить кол-во памяти, которое свободно под каждую карту памяти.

Далее идет главная часть функции, а именно расчет максимального кол-ва свободной памяти:

    do
    {
        int lo = 0;
        int hi = 1024*1024*256;
        int pivot;
        void* memory = NULL;
        do
        {
            pivot = ( hi + lo ) / 2;
            if( memory != NULL )
            {
                free( memory );
                memory = NULL;
            }
            memory = malloc( pivot );
            if( memory != NULL )
            {
                lo = pivot;
            }
            else
            {
                memory = malloc( lo );
                hi = pivot;
            }
        } while( ( hi - lo ) > 1 );

        if( ( memory == NULL ) && ( retrys < 2 ) )
        {
            ++retrys;
        }
        else
        {
            sizes[ index ] = lo;
            pointers[ index ] = memory;
            memory = NULL;
            ++index;
        }
    } while( ( pointers[ index - 1 ] != NULL ) && ( index < size ) );

Расчет кол-ва свободной памяти ведется для каждого блока в 256 МБ по отдельности (так как за один вызов функции malloc система может выделять память только из одной карты памяти) методом бинарного поиска. Изначально мы задаем переменные lo = 0, hi = 1024*1024*256 (256 МБ) и pivot (середина отрезка [lo; hi]). Далее мы пробуем выделить pivot байт функцией malloc и проверяем, не вернула ли она значение NULL (не получилось выделить pivot байт). Если malloc вернул NULL, то hi смещается к середине. Иначе смещение к середине происходит у lo. Так происходит до тех пор, пока lo и hi не сблизятся. В итоге, значение lo есть максимальное кол-во свободной памяти у текущей проверяемой карты памяти.

Затем все полученные значения lo записываются в массив sizes, а указатель memory на выделенную память размером lo записывается в массив pointers для дальнейней ее очистки.

Скрытый текст

(*) Хотя настоящий максимальный размер одной карты памяти составлял 8 МБ, разработчики The Simpsons Hit & Run задали максимальный размер одной карты памяти в 256 МБ. Это связано с тем, что в то время на рынке существовали китайские карты памяти для PS2 размерами намного большими чем 8 МБ. Китайская карта памяти наибольшего размера могла вмещать в себя 256 МБ.

Суммирование всей свободной памяти:

    size_t total = 0;
    for( i = 0; i < size; i++ )
    {
        total += sizes[ i ];
    }

Очистка выделенной памяти:

    for( i = 0; i < size; i++ )
    {
        void* pointer = pointers[ i ];
        if( pointer != NULL )
        {
            free( pointer );
            pointers[ i ] = NULL;
        }
        else
        {
            break;
        }
    }

В итоге функция GetFreeMemoryProfile возвщарает переменную total, которая и хранит кол-во байт свободной памяти.

Скрытый текст

(*) Функция GetFreeMemoryProfile вызывается только для PS2 потому, что для других платформ существовали специальные функции на проверку того, сколько памяти свободно в данный момент. Например для WIN32 существует функция GlobalMemoryStatus, через которую можно узнать информацию о текущем использовании виртуальной и физической памяти. А для PS2 такой функции небыло.

PS2Platform::InitializeMemory() - функция, которая вызывает radMemoryInitialize, тем самым инициализируя систему памяти (принцип работы функции radMemoryInitialize будет рассмотрен позже).

g_NoHeapRoute

g_NoHeapRoute - булевая переменная, которая говорит о том, включена ли система аллокаторов (false) или нет (true). Если эта переменная равна true, то вызывается функция radMemoryAlloc, куда передается параметр GMA_DEFAULT и размер запроса на выделение памяти в байтах.

То есть, если система аллокаторов отключена, то все запросы на выделение памяти будут обращены к аллокатору GMA_DEFAULT.

Если же переменная g_NoHeapRoute равна false, то происходит вызов функции AllocateThis, в которую передается тип аллокатора, являющийся текущей вершиной стэка (HeapStack) , а также кол-во запрошенных на выделение байт.

Скрытый текст

(*) Функция radMemoryAlloc как раз таки и отвечает за само выделение памяти в зависимости от аллокатора. Она запрашивает n-ое кол-во байт у некоторого аллокатора и возвращает указатель на выделенную память.

AllocateThis

AllocateThis - функция, которая запрашивает n-ое кол-во байт у некоторого аллокатора и возвращает указатель на выделенную память.

inline void* AllocateThis( GameMemoryAllocator allocator, size_t size )
{
    void* pMemory = NULL;
#ifdef CORRAL_SMALL_ALLOCS
    if( size < 201 )
    {
        if( allocator != GMA_AUDIO_PERSISTENT && allocator != GMA_PERSISTENT && allocator != GMA_TEMP)
        {
            pMemory = radMemoryAlloc( GMA_SMALL_ALLOC, size );
        }
        else
        { 
            pMemory = radMemoryAlloc( allocator, size );
        }
    }
    else
#endif
    {
        if ( allocator >= GMA_ANYWHERE_IN_LEVEL && allocator != ALLOCATOR_SEARCH )
        {
            pMemory = FindFreeMemory( allocator, size );
        }
        else
        {
            pMemory = radMemoryAlloc( allocator, size );
        }
    }

    return pMemory;
}

Если под переданный тип аллокатора не существует собственного аллокатора (allocator >= GMA_ANYWHERE_IN_LEVEL), то вызывается функция FindFreeMemory. Иначе вызывается функция radMemoryAlloc.

FindFreeMemory

FindFreeMemory - функция, которая делает запрос на выделение памяти среди некоторого списка аллокаторов.

void* FindFreeMemory( GameMemoryAllocator allocator, size_t size )
{
    GameMemoryAllocator* list = NULL;
    unsigned int numAvailable = 0;

    if ( allocator == GMA_ANYWHERE_IN_LEVEL )
    {
        list = AVAILABLE_FOR_RENT_IN_LEVEL;
        numAvailable = sizeof ( AVAILABLE_FOR_RENT_IN_LEVEL ) / sizeof( GameMemoryAllocator );
    }
    else if ( allocator == GMA_ANYWHERE_IN_FE )
    {
        list = AVAILABLE_FOR_RENT_IN_FE;
        numAvailable = sizeof ( AVAILABLE_FOR_RENT_IN_FE ) / sizeof( GameMemoryAllocator );
    }
    else if ( allocator == GMA_EITHER_OTHER_OR_ZONE )
    {
        list = AVAILABLE_IN_OTHER_OR_ZONE;
        numAvailable = sizeof ( AVAILABLE_IN_OTHER_OR_ZONE ) / sizeof( GameMemoryAllocator );       
    }
    else
    {
        rAssert( false );
    }

    if ( list != NULL )
    {
        ::radMemorySetUsableAllocators( (radMemoryAllocator*)list, numAvailable );
        void* memory = radMemoryAlloc( ALLOCATOR_SEARCH, size );
      
        return memory;
    }

    return NULL;
}

Сначала мы создаем указатель на некоторый список аллокаторов и переменную, которая будет хранить кол-во элементов этого списка. Далее, в зависимости от переданного типа аллокатора в функцию, указатель list начинает указывать на начало одного из трех массивов, содержащих типы аллокаторов так или иначе связанных между собой:

static GameMemoryAllocator AVAILABLE_FOR_RENT_IN_LEVEL[] =
{
    GMA_TEMP,
    GMA_LEVEL_ZONE,                            //    7         6     6
    GMA_LEVEL_OTHER,                           //    8         7     7
    GMA_LEVEL_MISSION,                         //    10        9     9
    GMA_LEVEL_HUD                              //    9         8     8
};
static GameMemoryAllocator AVAILABLE_FOR_RENT_IN_FE[] =
{
    GMA_LEVEL_MOVIE,                           //    5         4     4
    GMA_LEVEL_FE,                              //    6         5     5
    GMA_LEVEL_AUDIO                            //    11        10    10
};
static GameMemoryAllocator AVAILABLE_IN_OTHER_OR_ZONE[] =
{
    GMA_LEVEL_OTHER,                           //    8         7     7
    GMA_LEVEL_ZONE                             //    7         6     6
};

Затем, вызывается функция radMemorySetUsableAllocators, загружающая данные о типах аллокаторах, которые будут участвовать в запросах на выделение памяти, и, наконец вызывается функция radMemoryAlloc, куда передается ALLOCATOR_SEARCH в качестве типа аллокатора.

(1*) При передаче ALLOCATOR_SEARCH в функцию radMemoryAlloc в качестве типа аллокатора, radMemoryAlloc ведет себя по другому: он создает запросы на выделение памяти не у одного аллокатора, а у целого списка, загруженного ранее через функцию radMemorySetUsableAllocators. Соответственно он берет память у одного (или нескольких если память предыдущих уже закончилась) из этих аллокаторов.

Скрытый текст

(*) Обычно в функцию radMemoryAlloc тип аллокатора больший или равный GMA_ANYWHERE_IN_LEVEL передают тогда, когда вам все равно, какой именно из аллокаторов общего типа (AVAILABLE_FOR_RENT_IN_LEVEL, AVAILABLE_FOR_RENT_IN_FE или AVAILABLE_IN_OTHER_OR_ZONE) должен выделять память.

Заключение 1 части

Скрытый текст

(*) Вообще существует еще одна перегрузка оператора new, которая никак не взаимодействует с HeapManager. Использование: new(GMA_PERSISTENT) HeapManager Эта перегрузка полезна, когда вам нужно выделить память только под один объект. Реализация этого оператора new почти никак не отличается от реализации разобранного оператора new.

В заключение первой части я хотел бы представить итоговую блок-схему системы выделения памяти:

Часть 2

IRadMemoryAllocator

IRadMemoryAllocator - базовый интерфейс для всех аллокаторов в игре.

struct IRadMemoryAllocator : public IRefCount
{
    virtual void* GetMemory( unsigned int size ) = 0;
	virtual void  FreeMemory( void* pMemory ) = 0;
    virtual bool  CanFreeMemory( void * pMemory ) = 0;

    virtual void* GetMemoryAligned( unsigned int size, unsigned int alignment ) = 0;
	virtual void  FreeMemoryAligned( void * pMemory ) = 0;
    virtual bool  CanFreeMemoryAligned( void * pMemory ) = 0;

	//
	// Memory statistics
	//

    virtual void GetStatus(
		unsigned int * totalFreeMemory,
		unsigned int * largestBlock,
		unsigned int * numberOfObjects,
		unsigned int * highWaterMark );

    virtual unsigned int GetSize( void );
};

Кратко пробежимся по всем обязательным методам, которые должны содержать аллокаторы:

GetMemory - выделение памяти из аллокатора и возвращение указателя на выделенную память.

FreeMemory - очищает память по переданному указателю.

CanFreeMemory - проверка на принадлежность переданного указателя к данному аллокатору (при очистке памяти).

GetMemoryAligned - то же самое что и GetMemory, только при выделении памяти также учитывается выравнивание.

FreeMemoryAligned - очищает выравненную память по переданному указателю.

CanFreeMemoryAligned - то же самое что и CanFreeMemory (с учетом выравнивания).

radMemoryInitialize

radMemoryInitialize - Функция, которая инициализирует систему аллокаторов (задает стандартные аллокаторы).

Тело функции radMemoryInitialize:

if( g_Initialized )
    {
        return;
    }

#ifdef RAD_GAMECUBE
    ::radMemoryPlatInitialize( sizeVMMainMemory, sizeVMARAM );
#else
    ::radMemoryPlatInitialize( );
#endif

    //This is memory reserved to really bad situations where we need to printf.
#ifndef RAD_GAMECUBE
    gEmergencyMemory = radMemoryPlatAlloc( 1024 * 32 );
#endif

    rAssert( g_Initialized == false );
    g_Initialized = true;

    g_pRadMemoryAllocator_Malloc = new ( g_MemoryForMalloc ) radMemoryAllocatorMalloc( );

    g_AllocatorTreeNode_Root.m_pIRadMemoryAllocator = g_pRadMemoryAllocator_Malloc;
    g_AllocatorTreeNode_Root.m_pChildren_Head = NULL;
    g_AllocatorTreeNode_Root.m_pSibling_Next = NULL;
    g_AllocatorTreeNode_Root.m_pParent = NULL;

    for( unsigned int i = 0; i < ALLOCATOR_TABLE_SIZE; i ++ )
    {
        g_AllocatorTreeNodes[ i ].m_pChildren_Head = NULL;
        g_AllocatorTreeNodes[ i ].m_pParent = NULL;
        g_AllocatorTreeNodes[ i ].m_pSibling_Next = NULL;
        g_AllocatorTreeNodes[ i ].m_pIRadMemoryAllocator = g_pRadMemoryAllocator_Malloc;
    }

#ifdef RAD_GAMECUBE
    unsigned aramSize = (1024 * 1024 * 16) - sizeVMARAM;
    radMemorySpaceInitialize( aramSize );
    sVMMDLHeapInitialized = false;

    if ((sizeVMMainMemory != 0) && (sizeVMARAM != 0))
    {
        bool ok = VMAlloc( 0x7E000000, sizeVMARAM );
        rAssert( ok );
        vmmHeap = radMemoryCreateDougLeaHeap( (void *)0x7E000000, sizeVMARAM, RADMEMORY_ALLOC_DEFAULT, "GameCube_VMM" );
        rAssert(vmmHeap != NULL);
        radMemoryRegisterAllocator( RADMEMORY_ALLOC_VMM, RADMEMORY_ALLOC_DEFAULT, vmmHeap );
        sVMMDLHeapInitialized = true;
#ifndef RAD_RELEASE
        VMSetLogStatsCallback(&gcnVMMLogStats);
#endif
    }

#else
    radMemorySpaceInitialize( );
#endif

    //
    // Initialize static heap
    //
    //g_StaticHeap.CreateHeap( STATIC_HEAP_SIZE );

g_AllocatorTreeNodes - массив типа radMemoryAllocatorTreeNode (кол-во элементов g_AllocatorTreeNodes совпадает с кол-вом элементов перечисления GameMemoryAllocators)

struct radMemoryAllocatorTreeNode
{
    IRadMemoryAllocator        * m_pIRadMemoryAllocator; // the allocator pointer
    radMemoryAllocatorTreeNode * m_pChildren_Head; // list of sub allocators
    radMemoryAllocatorTreeNode * m_pSibling_Next;  // list pointer used by parent 
    radMemoryAllocatorTreeNode * m_pParent;        // optomization                 
};

В функции radMemoryInitialize массив g_AllocatorTreeNodes заполняется стандартными значениями, а именно:

    for( unsigned int i = 0; i < ALLOCATOR_TABLE_SIZE; i ++ ) // ALLOCATOR_TABLE_SIZE = 30
    {
        g_AllocatorTreeNodes[ i ].m_pChildren_Head = NULL;
        g_AllocatorTreeNodes[ i ].m_pParent = NULL;
        g_AllocatorTreeNodes[ i ].m_pSibling_Next = NULL;
        g_AllocatorTreeNodes[ i ].m_pIRadMemoryAllocator = g_pRadMemoryAllocator_Malloc;
    }

Где g_pRadMemoryAllocator_Malloc является экземпляром класса radMemoryAllocatorMalloc (radMemoryAllocatorMalloc также наследуется от IRadMemoryAllocator).

radMemoryAllocatorMalloc - это аллокатор, который не имеет своего собственного хранилища. То есть он в конечном итоге выделяет память через malloc.

radMemoryAlloc

radMemoryAlloc - функция, которая отвечает за само выделение памяти в зависимости от аллокатора. Она запрашивает n-ое кол-во байт у переданного аллокатора и возвращает указатель на выделенную память.

Тело функции radMemoryAlloc:

#ifdef RAD_PS2
    if(     (numberOfBytes<201)
        && gbSmallAllocCreated 
        && (allocator != HACK_AUDIO_PERSISTENT)
        && (allocator != HACK_PERSISTENT)
        && (allocator != RADMEMORY_ALLOC_TEMP)
        )
    {
        allocator = HACK_SMALL_ALLOC;
    }
#endif
#if ( defined RAD_XBOX ) || ( defined RAD_GAMECUBE ) || ( defined RAD_MW )
    if ( !g_Initialized )
    {
        MemoryHackCallback();
    }
#endif
    if ( numberOfBytes == 0 )
    {
        return NULL;
    }

    rAssert( g_Initialized == true );
    rAssert( allocator < ALLOCATOR_TABLE_SIZE || allocator == ALLOCATOR_SEARCH );

    #ifdef RAD_XBOX
        //rAssert( allocator != 2 );
    #endif
    void * pMem;

    if ( allocator == ALLOCATOR_SEARCH )
    {
        pMem = radMemoryAllocSearch( numberOfBytes, 0 );
    }
    else
    {
        IRadMemoryAllocator * pIRadMemoryAllocator =
            g_AllocatorTreeNodes[ allocator ].m_pIRadMemoryAllocator;

        pMem = pIRadMemoryAllocator->GetMemory( numberOfBytes );
        ::radMemoryMonitorIdentifyAllocation ( pMem, g_CurrentMemoryIdentification );
    }

    if (g_MemoryActivityCallback)
    {
        g_MemoryActivityCallback->MemoryAllocated( allocator, pMem, numberOfBytes );
    }

    CheckForOutOfMemory( pMem, numberOfBytes, allocator ); // логи
    LEAK_DETECTION_ADD_ALLOCATION( pMem, numberOfBytes, allocator ); // логи
    return pMem;

Как можно увидеть, если переданный тип аллокатора не является ALLOCATOR_SEARCH, то из массива g_AllocatorTreeNodes берется аллокатор под индексом allocator (pIRadMemoryAllocator), и у взятого pIRadMemoryAllocator вызывается метод GetMemory, который и выделяет нужное количество памяти. В случае же, если переданный тип аллокатора является ALLOCATOR_SEARCH, то вызывается функция radMemoryAllocSearch, работа которой не отличается от описанной в (1*).

Создание аллокаторов

Создание аллокаторов (как и было отмечено ранее) происходит в методах PrepareHeapsStartup, PrepareHeapsFeSetup, PrepareHeapsInGame и PrepareHeapsSuperSprint класса HeapManager. Для создания каждого отдельного аллокатора вызывается функция CreateHeap (из файла createheap.cpp), которая и занимается созданием аллокатора.

IRadMemoryHeap

Все GameMemoryAllocators (у которых имеется аллокатор) являются аллокаторами, производными от класса IRadMemoryHeap (несмотря на название Heap, никакой кучи как структуры данных там не реализовано).

IRadMemoryHeap - аллокатор, который поддерживает выделение памяти для объектов разного размера. При этом сам механизм выделения памяти у аллокаторов, производных от IRadMemoryHeap, может отличаться.

Heap аллокаторов существует три разновидности: Static Heap, Tracking Heap и Doug Lea Heap:

Static Heap - обычный Pool аллокатор, в котором заранее выделяется память под хранилище, и потом из этого хранилища берется память. Освобождение памяти для данного аллокатора не предусмотрено (то есть метод FreeMemory в StaticHeap пустой).
Tracking Heap - аллокатор, который выделяет память через malloc, но информацию о выделенной памяти он сохраняет у себя в хранилище для дальнейшей очистки. В отличие от StaticHeap может очищать выделенную память.
Doug Lea Heap - аллокатор, который выделяет память через dlmalloc, но информацию о выделенной памяти он сохраняет у себя в хранилище для дальнейшей очистки. В отличие от StaticHeap может очищать выделенную память.

Скрытый текст

(*) dlmalloc имеет свои минусы и плюсы по сравнению со стандартным malloc, но главный его плюс заключается в том, что реализация dlmalloc не зависит от платформы (в отличие от malloc). Также считается, что dlmalloc выгоднее при выделении малого кол-ва памяти (<= 201 байт) чем malloc.

CreateHeap

Тело функции CreateHeap:

void CreateHeap ( GameMemoryAllocator allocator, const unsigned int size )
{
    unsigned int index = static_cast< unsigned int >( allocator );
    rAssert( g_HeapArray[ index ] == NULL );

    HeapType type    = g_HeapCreationData[ index ].type;
    const char* name = g_HeapCreationData[ index ].name;
    GameMemoryAllocator parent = g_HeapCreationData[ index ].parent;

    rReleasePrintf ("Creating Heap: %s (%d)\n", name, size );

    #ifdef RAD_RELEASE
    if( type == HEAP_TYPE_TRACKING )
    {
        type = HEAP_TYPE_NONE;
    }
    #endif

    switch( type )
    {
        case HEAP_TYPE_STATIC :
        {
            HeapMgr()->PushHeap( GMA_DEBUG );
            g_HeapArray[ index ] = radMemoryCreateStaticHeap( size, RADMEMORY_ALLOC_DEFAULT, name );
            g_HeapArray[ index ]->AddRef();
            HeapMgr()->PopHeap( GMA_DEBUG );
            break;
        }
        case HEAP_TYPE_TRACKING :
        {
            HeapMgr()->PushHeap( GMA_DEBUG );
            g_HeapArray[ index ] = radMemoryCreateTrackingHeap( size, RADMEMORY_ALLOC_DEFAULT, name );
            HeapMgr()->PopHeap( GMA_DEBUG );
            break;
        }
        case HEAP_TYPE_DOUG_LEA :
        {
            HeapMgr()->PushHeap( GMA_DEBUG );
            g_HeapArray[ index ] = radMemoryCreateDougLeaHeap( size, RADMEMORY_ALLOC_DEFAULT, name );
            g_HeapArray[ index ]->AddRef();
            HeapMgr()->PopHeap( GMA_DEBUG );
            break;
        }
        case HEAP_TYPE_NONE :
        {
            //rAssert( false );
            return;
        }
        default:
        {
            rAssert( false );
            return;
        }
    }
    radMemoryRegisterAllocator( allocator, parent,g_HeapArray[ index ] );
}

g_HeapCreationData - массив типа HeapCreationData, который содержит информацию о создаваемых аллокаторах, а именно: тип, родитель, название:

struct HeapCreationData
{
    HeapType            type;
    GameMemoryAllocator parent;
    char                name[ 256 ];
};

HeapCreationData g_HeapCreationData[] = 
{
    { HEAP_TYPE_DOUG_LEA, GMA_DEFAULT, "Default"              },      
    { HEAP_TYPE_DOUG_LEA, GMA_DEFAULT, "Temp"                 },      
    { HEAP_TYPE_NONE,     GMA_DEFAULT, "Gamecube VMM"         },      
#ifdef RAD_WIN32
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Persistent"           },  // no static heap for pc
#else
    { HEAP_TYPE_STATIC,   GMA_DEFAULT, "Persistent"           },
#endif // RAD_WIN32
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level"                },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level Movie"          },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level FE"             },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level Zone"           },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level Other"          },
    { HEAP_TYPE_DOUG_LEA, GMA_DEFAULT, "Level Hud"            },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level Mission"        },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Level Audio"          },
    { HEAP_TYPE_NONE,     GMA_DEFAULT, "Debug"                },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Special"              },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Music"                },
    { HEAP_TYPE_DOUG_LEA, GMA_DEFAULT, "Audio Persistent"     },
    { HEAP_TYPE_DOUG_LEA, GMA_DEFAULT, "Small Alloc"          },
#ifdef RAD_XBOX
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "XBOX Sound"           },
#endif
#ifdef USE_CHAR_GAG_HEAP
    { HEAP_TYPE_DOUG_LEA, GMA_DEFAULT, "Characters and Gags"  },
#endif
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Anywhere in Level"    },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Anywhere in FE"       },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Either Other or Zone" },
    { HEAP_TYPE_TRACKING, GMA_DEFAULT, "Search"               },
    { HEAP_TYPE_NONE,     GMA_DEFAULT, "???"                  },
    { HEAP_TYPE_NONE,     GMA_DEFAULT, "???"                  },
};

В конце, после самого создания аллокатора в функциях radMemoryCreateStaticHeap, radMemoryCreateTrackingHeap или radMemoryCreateDougLeaHeap вызывается функция radMemoryRegisterAllocator, которая заменяет аллокатор, лежащий по индексу allocator в массиве g_AllocatorTreeNodes, на созданный нами аллокатор.

radMemoryCreateStaticHeap

Для примера рассмотрим создание Static Heap.

radMemoryCreateStaticHeap - функция, которая занимается созданием Pool аллокатора.

Тело функции radMemoryCreateStaticHeap:

    rReleasePrintf("%s ", pName );
    StaticHeap* pHeap = new ( allocator ) StaticHeap; // выделение памяти через radMemoryAllocatorMalloc
    pHeap->CreateHeap( size );
    return pHeap;

Тело функции StaticHeap::CreateHeap:

    m_FreeingAllowed = false;
    m_TotalAllocations = 0;
    m_TotalSize = size;
    m_BasePointer = reinterpret_cast< char* >( radMemoryPlatAlloc( size ) );
    rAssert( m_BasePointer != NULL );
    m_CurrentPointer = m_BasePointer;
    m_End = reinterpret_cast< char* >( reinterpret_cast< size_t >( m_BasePointer ) + size );
    m_Overflow = 0;

    rReleasePrintf("StaticHeap Start: 0x%x, End:0x%x\n", m_BasePointer, m_End );

    #ifdef RADMEMORYMONITOR
    {
        radMemoryMonitorIdentifyAllocation( (void*)m_BasePointer, g_nameFTech, "StaticAllocator::m_StartOfMemory" );
        radMemoryMonitorDeclareSection( (void*)m_BasePointer, m_TotalSize, IRadMemoryMonitor::MemorySectionType_DynamicData );
        char szName[ 128 ];
        sprintf( szName, "[StaticAllocator]" );
        radMemoryMonitorIdentifySection( (void*)m_BasePointer, szName );
    }
    #endif // RADMEMORYMONITOR

Как можно видеть, в функции StaticHeap::CreateHeap память под хранилище выделяется функцией radMemoryPlatAlloc, которая представляет из себя обычный вызов функции malloc с дополнительным логгированием.

Скрытый текст

Как можно заметить по массиву g_HeapCreationData, только GMA_PERSISTENT соответствует StaticHeap. Также стоит отметить, что все самые главные классы в игре выделяются именно через аллокатор GMA_PERSISTENT.

Код из файла (ps2main.cpp):

    HeapMgr()->PushHeap (GMA_PERSISTENT);

	//Process any commandline options from the command.txt file
	ProcessCommandLineArgumentsFromFile();

    //
    // Instantiate all the singletons before doing anything else.
    //
    CreateSingletons();

    //
    // Construct the platform object.
    //
    PS2Platform* pPlatform = PS2Platform::CreateInstance();
    rAssert( pPlatform != NULL );

    //
    // Create the game object.
    //
    Game* pGame = Game::CreateInstance( pPlatform );
    rAssert( pGame != NULL );

    //
    // Initialize the game.
    //
    pGame->Initialize();

    HeapMgr()->PopHeap (GMA_PERSISTENT);

Поэтому можно сказать, что выделять память через GMA_PERSISTENT стоит приемущественно для тяжелых типов данных, потому что выделения памяти через GMA_PERSISTENT происходят намного быстрее, чем те же выделения через другие аллокаторы.

Вывод

Для выделения памяти под тяжелые типы данных лучше использовать Static Heap (GMA_PERSISTENT), под легкие Doug Lea Heap, а под средние Tracking Heap.

Надеюсь, эта статья была полезна и интересна мододелам и просто прохожим.

Полный исходный код игры The Simpsons: Hit & Run 2003 вы можете посмотреть здесь:

GitHub - FlexodMR/Simpsons: Original source for "The Simpsons: Hit & Run" game

github.com

Система управления памятью в The Simpsons: Hit & Run 2003