5th Generation Memory Management
Project Pokémon » RAM Research » 5th Generation Memory Management
Memory Management in Pokemon Black/White and Pokemon Black2/White2

 

First thing, let's define some terms:

EWRAM- External work RAM; extends from 0x2000000-0x23FFFFF, meaning DS titles have 4mb of RAM to work with. This number is expanded to 8mb(0x2000000-0x27FFFFF) during development using a debug DS dev system and 16mb on the DSi(0x2000000-0x2FFFFFF). This work RAM is mostly controlled by the AMR9 CPU. The ARM7 controls the bit where the ARM7 binary is written to. (0x23E0000-end of binary)

IWRAM- Internal work RAM; runs from 0x37F8000-0x37FFFFF and is generally(always?) allocated for use by the ARM7 CPU. This starts at 0x3000000, but the mirror at 0x37F8000 is used so that it can be combined with the ARM7’s 64k of RAM to give it 96k contiguous RAM to work with.

'HPXE'/'EXPH'- Extended Heaps- a type of memory allocation done using the DS' system library. They're marked with the signature 'EXPH' in ASCII in RAM but the letters are reversed because the ARM CPU is running in little endian mode. (0x48504584/0x84455048 in RAM)

'DU'/'UD'- This is the "block used" marker in RAM. It's supposed to be 'UD', but will show as 'DU' in RAM due to the endianness. (0x4455/0x5544 in RAM)

'RF'/'FR'- Same as above, except this marker means "block free". (0x4652/0x5246 in RAM)

SDK- The Nitro SDK, the official devkit for the DS.

NNS- The Nitro system library. It's sort of the foundation for the main systems in the console.(2d/3d gfx, sound, memory, general graphics) This set of libraries works with the SDK libraries, sort of as a supporting foundation.

MSL- The compiler that comes with the SDK(Metrowerks' CodeWarrior) includes a special set of libraries supplied by the vendor. These libraries handle things like floating point math and include a large set of C-standard library functions for embedded systems(there's no floating point hardware on the console, thus it's all done in software and is rather slow).

194E- This is a special marker used by GameFreak(abbreviated to GF from now on) to indicate that a block of memory is both allocated and ready/in use by one of GF's defined source files.

194D- This is a GF marker that the block of memory is to be freed/is freed.

ARM9- This is the main processor in the DS. It runs at roughly 66mhz. It runs the core program, called the "ARM9 binary" that generally consists of the most vital engine components to run the game. All of the libraries are compiled into the ARM9 binary as well.

ARM7- This is the subprocessor in the DS, it runs at roughly 33.5mhz. The "ARM7 binary" is the main program that this CPU runs. This CPU also handles much of the hardware I/O tasks for the console.

Gamefreak uses a fairly simple, yet effective, method for managing memory in the 5th gen games. The games themselves are quite large(BW at 192mb and B2W2 at 310mb) and they(B2W2) have roughly 3.22mb to work with after subtracting out room in EWRAM for the ARM9 binary and static BSS space. There is also 656k of VRAM and some of that may be allocated as work RAM if it is left over. In large games such as these however, not much is often left. The ARM9 binary is 620kb and the overlays add up to 3.51mb, so the code alone add up to over 4mb even though the DS has 4mb of RAM. This means that space is usually at a premium and memory has to be carefully managed to prevent any sort of accidents or conflicts in RAM. This is especially important because there are 344 overlays in B2W2. Overlays are basically modularized code which is loaded and unloaded from memory as needed, much like a DLL file in Windows. If an overlay is needed and loaded into memory and a second one is accidentally written over the first as it’s running, the game will crash hard and be unable to recover.

So what happens, exactly? To fully explain the process, we have to start way back as the game is booting. The way this works is that Nintendo-provided code, commonly called "crt0", (“crt” = C-runtime, “0” for the very beginning) starts and initializes the system, sets up video memory, establishes the coprocessors, initializes tightly coupled memory and all the stacks, eats up the rest of the first video frame, then hands control off to the Main() function of the application being run by the system. Once the game hits Main() it runs an initialization routine that initializes the OS, starts Timer0, enables the alarm system, graphics init, fixed point init, the VRAM transfer manager, and some other miscellaneous system-related startup and config. The next routine that runs in Main() is where everything important that belongs to GF begins. One of the subroutines here is the memory management system setup. There are 3 arguments passed to this memory manager initializer: the size of the system heap to allocate, the number of heaps to allocate, and the total number of blocks that can potentially be allocated from GF’s system. The system heap allocation is a different type of memory allocation from the system functions that GF uses. There are 3 built-in types:

  1. Foundation allocation functions that come from the system library

  2. OS-related functions that come from the SDK

  3. Malloc/calloc/realloc, etc from the MSL library


(All function names that start with a lower case letter are provided by me.)

So basically, memoryAllocationSystemInit runs and calls startAllocSys which then runs and calls an SDK function that allocates from the low end of the EWRAM arena. This function allocates memory up to the start of the ARM7 binary. Once this is done, the game allocates the “main” heap where it stores multiple important sets of values. This system block of memory starts at 0x21FED04(W2U) and is 0x6000 bytes long. Once this main block is allocated, the game runs the setup for the management system. At 0x21FEC40 it initializes a byte array 193 elements long, each byte set to 0xFF by default. Each byte stands for a location of a heap of memory. The heaps are allocated starting from 00, but not in order. They can be allocated from any of the 193 heap locations, and the block they’re allocated from will be given the next group ID number in the sequence. I.E. if block_array[12] is the first allocated, it will be filled with group ID 0x00, if block_array[19] is next, it will be 0x01, etc. The other half of the management system is at 0x21FEAA0, and is a set of C-style structs that are 16 bytes long. The struct looks like this:
 

typedef struct {

NNSFndHeapHandle* heapHandle; //heap handles are equivalent to pointers to the heaps in the final rom
NNSFndHeapHandle* heapMain;
void* pHeap;
u16 blkCount;
bool isMainHeap;
u8 padding;
} blockAlloc;


 
So basically it’s a list of heap handle, heap the block was allocated from, a pointer to the block in RAM, number of blocks allocated from this heap, and a note of whether or not this heap is a “main” heap, a heap allocated from the arena, not from another larger heap.

There are 3 types of allocations in the system: main heaps, sub heaps, and blocks. When a main heap is allocated(which is rarely), the function is passed a new block group ID, a starting address, and a size. From there it’s allocated and the info struct has only 2 fields entered onto the next entry, the heap handle and TRUE for the main heap marker. The starting address may be specified numerically or by reference. Sub heaps are the next smaller type of allocation. They are allocated out of the main heaps using the same arguments but smaller lengths. They have their own heap group IDs for collections of heaps allocated from the same main heap. The smallest allocation type is the block. Blocks are allocated mostly as storage for data that code from source files needs to act upon. When a source file needs storage, it calls:


void* allocateBlockFromExpHeap(int blkGroupID, u32 blockLength, bool clearBlock, const char *pSourceFile, int marker)


The block group IDs keep the blocks that are from the same files associated with each other. These blocks have 28-byte headers. The first 2 bytes are a u16 which is the block group ID(argument 1). Block IDs come in two types, those with the highest bit in the short set and those without. The blocks without the highest bit set are allocated from the beginning of free space in the heap. This the normal means by which memory is allocated in this system. However, if the highest bit is set in the block ID value(ex. 0x8007 for block ID 7), then the alignment becomes negative. This means that the memory is allocated for the block ID group from the end of the heap that is being used into it instead of from the beginning towards the end. The second u16 is the allocation status. This has 2 possibilities: 194E means the block is allocated and ready, but 194D means the block is freed. The next 18 bytes is a char array that contains the name of the source file the memory is being allocated to service or at least the first 18 bytes of that filename. Each source file has a char array with the source file name at (probably) the top of the file or maybe in the header. Something along the lines of: (ex.)
 

static char* sSrcName = {“g3d_system.c”};

 
The block header looks like so:
 

typedef struct {

u16 blkGroupID;
u16 blkStatus;
char[18] srcName;
u16 blkMarker;
u16 unknown;
u16 size;
} blockHeader;


 

Every time a block is declared via the allocation function a pointer to the source filename is supplied and an 18-byte copy occurs from that source to block_base + 0x4. The bool clearBlock is an indicator of whether or not a memory clearing function should run on the block that was just allocated. The marker is an individualized number which is different for every single block and allows for differentiation between them. The free and used indicators are used at the block level, as well. ‘FR’ and ‘UD’ are written by the Nitro system calls, not by GF’s system. A called allocation function might look like so: (ex.)

void* pBlk = allocateBlockFromExpHeap(g3dID, (sizeof(array1)+sizeof(array2)+sizeof(var6)), TRUE, sSrcName, G3D_DUALSCREEN_MARKER);

That will allocate a block in the g3d 3d system group with the marker that it’s for the dual-screen 3d DS hack to make both screens do 3d at once with an adequate size for whatever data needs to be temporarily saved. The expanded heap allocation system uses an allocator which has a different block info struct:
 

typedef struct {

u16 blockMarker;
void* block_after_header;
u32 size;
char[18] srcFile;
} blockInfo;


 
The allocator has a set of statuses that are set based on different things happening while allocating the different kinds of heaps and blocks. The statuses are defined like so:

Heap allocator status:

0 - Normal block/allocator is working

1 - Block out of range(past limit)/block already freed

2 - Block is missing handle

3 - Unable to allocate a sub heap from a main heap

4 - Heap has no blocks/no blocks left after freeing

5 - Unable to create main heap

When a block is freed, a pointer to the block is passed to “freeBlock”. The status marker(header + 2) is set to 194D, the block group count for the heap has 1 subtracted from it, and then a system function runs; this frees the memory back to a sub expanded heap and does heap management to remove the block and recycle that memory region. It then updates the management header for the heap to reflect the changes.

Freeing a sub heap involves passing a heap group ID(which is the ID assigned to all blocks in the sub heap) to “freeSubHeapToMainHeap”. This function validates the heap by checking to make sure the heap still has blocks allocated in it and if so, verifying the heap handle then checking the heap length, free size, allocatable size, and block count in the heap. Then it runs a function which verifies each block’s header. After verifying the blocks, “freeHeapToMainExpHeap” is passed the group ID. Here, the handle is validated again, the main heap the sub heap was allocated from is retrieved, and a pointer to the sub heap is pulled from the 16-byte info struct at 21FEAA0 + (0x10 *groupID). A system function then runs that “destroys” the sub heap by removing it from the internal allocation list that belongs to the system. Finally, a system function frees the sub heap back to its parent main heap and then all elements of the heap info struct for that entry are zeroed out and the function returns TRUE. If the function returns FALSE, then there was an error in the freeing process and “freeSubHeapToMainHeap” gets and checks the allocator status, panicking if there is an issue. Main heaps are rarely allocated and never freed.

 
-Bond697
 


White 2 Important Address List:
(subtract 0x40 for Black 2)

0x21FEC40 - Heap byte array
0x21FEAA0 - Heap info structs
0x214185C - GameFreak's allocator info
0x214186A - Allocator status
0x203A228 - allocateBlockFromExpHeap
0x203A188 - mallocSubHeap
0x203A1A4 - mallocMainHeap