Dodongo Feeding Glitch

All addresses are NTSC 1.0. Last update May 5th, 2016 at 23:09

Dodongos (the larger, dark green enemies) have a lesser known animation where they eat Bombs, Bomb Flowers, and Bombchus placed by their mouth. If you trigger this animation using a Bombchu, a seemingly bizarre array of glitches can occur.

What's going on:

The function at 80873FCC (virtual address) appears to drive the logic behind this animation every frame. The root cause of the glitch is that within this function the Dodongo increments a 2 byte value located at 0x01E8 past the start of the instance of the explosive it swallows. The problem is that instances of the Bombchu actor are only 0x01D4 bytes long, whereas Bombs and Bomb Flowers are 0x01F8 and 0x200 bytes respectively. In other words, the Dodongo corrupts data beyond the bounds of the Bombchu instance.

To understand what ends up being overwritten past the Bombchu actor instance, you need to understand the "Actor Heap"

The actor heap is a space that is reserved after pretty much everything else has been allocated to the main heap. It starts at 801DAA00, and ends a little bit before the space allocated for room files. A doubly-linked list is used to manage this space's limited ram. Each node is 0x30 bytes (0x10 on gamecube releases), and stores the following variables:

/* 0x00 */ short magicNumber = 0x7373;  // a static value all nodes begin with
/* 0x02 */ short isFree;                // determines if the space managed by the node can be allocated to
/* 0x04 */ int   spaceSize;             // the size in bytes of the space managed by the node. Does not include the node itself
/* 0x08 */ node* nextNode;              // points to the next node in the list, 0 if this node is the last in the list
/* 0x0C */ node* prevNode;              // points to the previous node in the list, 0 if this node is the head node

At first, the actor heap contains a single node that manages all of the available free space. When something needs to be allocated (assuming it can be), the next free node big enough is selected, the space is reserved, and a new node is created (assuming there's enough space left) to manage the remaining free space. When things are de-allocated from this space, the game will attempt to merge together adjacent nodes that mark free space.

An important thing to note is that Ocarina of Time allocates things to the nearest 0x10 byte boundary. Going back to our Bombchu instance, a Bombchu actor instance that is sized to 0x1D4 bytes. When allocated to the actor heap, the memory node before it will have a spaceSize of *at least* 0x1E0 bytes. The only time more space will be reserved is if there isn't enough free space to allocate both the 0x1E0 bytes for the Bombchu actor instance, and an additional 0x30 bytes for a new memory node to manage the remaining free space (a fairly rare occurrence though).

Back to the glitch, typically our Bombchu actor instance will be allocated to some location on the actor heap. At instance + 0x1E0, the next node in our memory management linked list will almost certainly be allocated. Thus if 0x1E8 is overwritten the "nextNode" variable of the node following the Bombchu will be corrupted, causing the linked list chain to "snap", which in turn compromises the system's ability to manage memory correctly.

With the heap node corrupted, it becomes incredibly difficult to predict how the game will behave because there are many, many different possible manipulations available. Breaking a pot, dropping a bomb, killing an enemy in one room has the potential to drastically change how the heap ends up being used in another room. The only time it is possible to predict how things will be allocated in the actor heap with relative ease is when loading/reloading an area. Though rare to set up, the glitch even has the potential of not occurring at all.

There are some observations I can go into:

1) An important thing to realize is that the lower the start address of the Bombchu actor that killed our Dodongo, the more nodes will "break off" our linked list chain. If the corrupted "next node" pointer points to data that is interpreted as not being free for re-allocation or with a small "size" component, the game can run out of space for allocating actors, causing them to fail to load (and in some situations crash the game). If the corrupted "next node" pointer points to data that IS interpreted as being free for re-allocation, the game could end up allocating actors after this "false" node. Depending on where the node is addressed, this can cause out of bounds exceptions, or crashes due to overwriting allocated data.

2) Because of the above, the more Dodongos you kill without leaving the room (provided they actually disappear when they die), the more damage you will do to the doubly-linked list since the Bombchu will be able to fit itself within the space used by the Dodongo. Reloading the room from oobs, the Dodongos are are positioned at the lowest addresses of all actors that can be destroyed in the room normally.

3) If the data managed by the node (which we'll call nC) with the corrupted "next node" pointer is deallocated, the game will mark nC as being free, then attempt to merge nC->Next into itself if it is considered to be free, then merge nC into nC->Prev if that node is free as well. A node is considered free for reallocation if the two byte value at node + 0x02 is not zero, meaning that most of the time the corrupt nC->Next node will be free.

In any case (and I hope you're a programmer)...

let nC->next be nF0, and nF0->next be nF1, and nC->prev be nP

if nC->next is "free" and nC->next->next is not null, the game will set nC->next->next->prev to nC (corrupting more data), and nC->next to nC->next->next. Finally, nC's size variable will be incremented by nC->next->Size + 0x30. If nC->next->next is not divisible by 4, the game will crash due to the game trying to store a 4 byte value to an unaligned address. I actually have a crash debugger screenshot showing this below. Emulators don't always adhere to this alignment requirement.

https://cdn.discordapp.com/attachments/82991320754294784/178939910256984065/amarec20160508-214338.PNG

then, if nC->prev (nP) is free as well...

if nF0 wasn't free, nP->next will be set to nF0, and nF0->prev will be set to nP (corrupting data).
if nF0 was free, nP->next will be set to nF1, and nF1->prev will be set to nP (corrupting data).

Lastly, if nC or nP absorbed nF0's size data, the node's size component may be big enough to mark allocated data as being freed, which can crash the game if the game attempts to allocate data at that node.

4) There is a secondary glitch that occurs when making the Dodongo eat a Bombchu. The Dodongo's death animation increments a 2 byte value at 0x1E8 past the start of the Bombchu instance for 8 frames. However, the Bombchu is de-allocated from memory before the 3rd increment, meaning that in theory, you could allocate something into the space that the Bombchu occupied mid-animation, and corrupt a value that way. The problem with this is that when a Bombchu explodes, it spawns a new instance of a normal bomb to perhaps handle the explosion. Typically, this bomb will be allocated after the Bombchu, meaning that the memory node after the bombchu will manage this bomb instance, and won't fall out of scope until after the bomb instance is deallocated (which happens after the +0x1E8 variable is no longer being updated).

5) Typically, the corrupted memory node manages the Bomb instance spawned by the eaten Bombchu. When this Bomb instance is deallocated, the game will attempt to merge together adjacent memory nodes that are marked as free. To illustrate this, let pB be the corrupt bomb instance node, p1 be the node addressed before pB, and p2 be the "false" next node referenced by pB. When the data held by pB is de-allocated, the game checks if p2 (pb->next) is marked as free. Since "free"-ness is determined by checking if the 2 byte "isFree" variable is non=zero, p2->isFree will likely be treated as free space.

In order to force the Dodongo to manipulate something other than a memory node, you would need to spawn the Bombchu instance before some other block allocated on the heap, in such a way that the Bomb instance spawned by the Bombchu won't immediately follow the Bombchu in ram. Additionally, whatever thing is allocated after the Bombchu instance must be de-allocated within the 5 frames that the animation updates the 0x1E8 variable, so that the memory can be repurposed. In other words, there's a very slim chance of being able to accomplish this.

Edit: Actually, pulling a second chu before the first is eaten should be enough to push the bomb instance elsewhere.

6) If ovl_En_Bom (the code that manages Bomb actors) can't be allocated to ram, Dodongo's will be unable to die completely, since I guess they also spawn a Bomb instance to handle their death animation. I've found a setup that triggers this, but don't fully understand why ovl_En_Bom fails to load