Actor Heap Explanation (in progress)

How the Actor Heap works in Majora's Mask (in the context of finding heap manipulations for SRM; Stale Reference Manipulation)

===

Some resources:
 Spectrum is a tool that can be used to view the actor heap on emulator: https://wiki.cloudmodding.com/oot/App:Spectrum
 Actor List (very useful for matching actor Ids to their actors): https://wiki.cloudmodding.com/mm/Actor_List_(Variables)

Note: Some of the names in the Actor List might be a bit unclear at first. For example, Actor Id 0009 is labelled as "Powder Keg" but it is also the Actor Id for Bomb.


===Intro===
The actor heap is a part of memory where actors are dynamically allocated. There are 3 things that get loaded into the part of the heap that we're concerned with:
 1. Actor Instances (labelled "AI" in Spectrum)
 2. Actor Overlays (labelled "AF" in Spectrum; "AF" for "Actor File")
 3. Heap Nodes (have size 0x10 on English and size 0x30 on JP; labelled "LINK" in Spectrum, this name probably comes from links in a linked list data structure)


An Actor Instance is basically a block of memory that corresponds to a specific instance of an actor (for example, Spring Mountain Village has 5 frogs in it and thus has 5 individual frog Actor Instances). An Actor Overlay is a block of memory that essentially contains "code" or sets of instructions that the corresponding actor instances read from in order to function properly. Regardless of how many actor instances of a given kind of actor exist, there will only be a single Overlay that they all read from (for example, there are 5 frog Actor Instances in Spring Mountain Village, but only 1 frog Overlay that they all normally read code from).

An overlay will always allocate in earlier (in time) than the instance - essentially the overlay being on the heap is a prerequisite for the instance being on the heap (with few exceptions... instances with actor Id 000E are Collectibles, such as rupees or other item drops, and do not have an associated overlay that gets allocated; this is the only exception I can think of). It is worth noting that actor instances with the same Id always have the same size, but they might be different types. For example, a red rupee and a green rupee are both 000E instances, but some data in their actor instances is slightly different to change the type of rupees they are (for the purposes of simulating the heap in search of heap manipulations, we can treat them all the same because they have the same size and instances with the same Id correspond to the same overlay).

Whenever anything gets allocated into the heap, it gets allocated to an address which tells us exactly where its first byte is stored in memory. Everything in the actor heap will ALWAYS have an address that is a multiple of 0x10. An example of what the heap can look like in Spectrum can be found here: https://imgur.com/a/ZvhYPQq

===HEAP NODES===
Heap nodes are size 0x10 files (0x30 on JP) that sit between all loaded actors, and surround gaps that new actors can be allocated into. In this way, nodes are used to keep track of the size of gaps in the heap for easy allocation.

Whenever an instance or overlay loads into the heap, the nodes are checked. The first node is checked first, if it has enough free space directly after it then it will allocate there. If not, it will go onto the next node and check there - and so on until it finds a spot.

Once it finds a spot, the file will allocate there and will check if it needs to place a node. Nodes will always stick around if there is a file allocated either directly before them or directly after them (or both). So you will never find a file which isn't sandwiched by two nodes, even if there's a gap in the heap.

For example, let's say the heap looks like this:

Node
Actor0 (Size 0x100)
Node
[Free space] (Size 0x120)
Node
Actor0  (Size 0x100)
Node

And let's say we want to load another Actor0 instance into the heap. The first available node would be the one before the free space, and an Actor0 instance would fill up 0x100 of the space. A node would then be placed on the end of Actor0 and we would end up with:

Node
Actor0 (Size 0x100)
Node
Actor0 (Size 0x100) <-- New Actor0 instance
Node
[Free space] (Size 0x10) <-- Now we have less free space as Actor0 took up 0x100 bytes and the new node took up 0x10 bytes
Node
Actor0  (Size 0x100)
Node

But let's say we wanted to instead load in the actor Actor1 which has size 0x110. Clearly there's enough room there, but if we try to place a node directly after it, we would end up with two nodes next to each other, which is pretty useless as there's no space between them.

What happens instead is that the node before the new actor will essentially just treat the actor as if it has size 0x120 instead of 0x110, so that it perfectly fits in the gap. In this way we can find inconsistencies in the amount of space actors take up on the heap.

===Relevant Part of the Heap===
As explained a little bit in the description of the picture linked above (https://imgur.com/a/ZvhYPQq), we are only concerned with part of the actor heap. Assuming you have Tatl, Link and Tatl are always the first things loaded in the heap and thus this part of the heap will always be the same. Because of this, we don't care about anything above the heap node which will always be at the address 0x40B140 (on English).

As you probably gathered from the description of nodes above, whenever you see 2 consecutive nodes (or LINKS in Spectrum), there will be some amount of free space between them that things can allocate into (labeled by an F for Free space in Spectrum). Looking toward the bottom of the first picture, you will see 2 consecutive nodes, pictured here: https://imgur.com/a/vPIblHI

In this second picture, we have 2 consecutive nodes which shows that there is free space (that's what the F in spectrum indicates). Notice that the address of the second node (0x5736A0) is much larger than the address of the first node (0x422960) which tells us that there are 0x5736A0 - 0x422960 - 0x10 = 0x150D30 = 1,379,632 bytes of free space between these nodes. In practice, this is much more space than we'll ever use and thus we consider the first node with address 0x5XXXXX to be the end of the "relevant part" of the heap.

===More on Overlays===
I categorize overlays into 2 types.
 Type A: The overlay allocates into the earliest spot it can on the heap
 Type B: The overlay allocates after the relevant part of the heap

For actors with Type A overlays, the overlay will deallocate if all the corresponding instances deallocate.

Looking again at the first image (https://imgur.com/a/ZvhYPQq), we can see examples of each overlay type.

At 0x41D710, we see an overlay with Id 0024 (this is the Id for Skulltula) and it is loaded just above the AI for the skulltula. This is an example of what I call a Type A Overlay.

At 0x575110, we see an overlay with Id 0018 (this is the Id for Loading Plane) and we notice that this is loaded after the relevant part of the heap, which its actor instance is loaded at 0x40B150, which is just after the start of the relevant part of the relevant part of the heap.

When simulating the actor heap, I only care about simulating Type A Overlays because Type B Overlays are never in the relevant part of the heap and thus have no effect on the heap manipulation.

===Rooms in Scenes===
Each area in the game that we pass through a loading zone to reach is referred to as a Scene. Each scene is made up of some number of Rooms (most scenes only have a single Room, such as West Clock Town or Great Bay). Scenes that have multiple Rooms are candidates for performing SRM. Rooms are separated either by loading planes (Id 0018) or doors (Id 0005 for example, various other types of doors exist).

An example of a Scene with multiple rooms is Deku Palace. The room you appear in when you enter Deku Palace from Southern Swamp is Room 0. The room to the right (which contains the magic bean grotto) is Room 1 and the room to the left (which contains the Heart Piece) is Room 2.

Associated with each room is a list of actors that the room will try to allocate once you enter it. When you enter a given room, the actors in this list will get allocated, one-by-one in the same order every time you enter it, and each instance (or overlay) gets allocated into the earliest part of the heap that it fits into.

Keep in mind that when an actor which has a Type A overlay gets allocated, first its overlay gets allocated (if the overlay is not already allocated) and then the corresponding instance gets allocated.

So if you load a Scene from the same room (for example, loading Deku Palace from Room 0 by entering Deku Palace from Southern Swamp), the actors (overlays and instances) will always load in the same order. Loading a scene from a given room is a good way to figure out in what order the actors load.

[EDIT: some places load actors in slightly different orders on scene load vs. room load; see e.g. https://pastebin.com/WVj6iaQf (actor 015B: bad bats) and https://pastebin.com/CubcinzJ (actor 0212: circle of stalchildren); Bad bats are created from an original bad bat and I think the same happens with actor 0212 and this pattern probably has something to do with why they behave differently on scene load; this pattern applies to other scenes with these actors]


===Loading Rooms===

Note that when I refer to Overlays allocating/deallocating, I'm only talking about Type A Overlays because these are the only Overlays that I care about for my purposes.


Simplified Case: 2 Rooms With Only 1 Loading Plane/Door Connecting Them, No "Spawners"

Suppose you are initially in Room 0 so the actor heap contains all of the actors associated with Room 0 which weren't deallocated (if it wasn't clear by now, you can deallocate some kinds of actors by doing things in-game, such as breaking a pot to deallocate it). Then suppose you pass through a short* loading plane to load Room 1. Here is what happens, in order:
 1. everything from Room 1 loads one-by-one, in order
 2. everything from Room 0 deallocates (EXCEPT for the loading plane you passed through AND the 3-day Clock Actor AND any overlays for which instances also exist in Room 1 because these overlays only deallocate once no such instances exist)
 3. Any "cleared" actors will deallocate, often leaving a gap in the heap (also, if a new instance of the 3-day Clock Actor was allocated, this will deallocate at this step as well; the clock actor closer to the top of the heap will stay allocated)

* Note: There are two types of loading planes. "Long" Loading Planes and "Short" Loading Planes. Short Loading Planes are loading planes you'll see in places like Deku Palace where both connecting rooms are only allocated at the same time for a few frames at most. Long Loading Planes are loading planes you'll see in places like Beneath the Graveyard or Bomber's Hideout where it gets dark when you pass through it and both rooms are loaded at the same time as long as you are in the long loading plane area. In the case of a long loading plane, steps 2 and 3 above switch, but the result is the same because it doesn't matter in what order things deallocate in (at least in the absense of spawners, as well mention below).

An actor is "cleared" if there is some flag set for the actor that makes it so that it is not in the scene. For example, consider Big Octos in the Southern Swamp. If you kill a Big Octo (which deallocates it from the heap) and then reload the room, the Big Octo will still be deallocated. However, even though it is deallocated, it will still initially load when the room is loaded, but then it will immediately deallocate. Notice how this is very different from most other actors that we can deallocate, such as pots, which will come back when we reload the room.

The only time (at least, I don't have a counterexample to this claim) that a "cleared" actor will NOT attempt to load (before immediately deallocating) is if the actor is "Category 5". Actors are split up into several categories and most enemies are Category 5. Looking back at the first picture linked (https://imgur.com/a/ZvhYPQq), you'll see a 5 next to the 0024 AI (which is a skulltula) which indicates that it is Category 5. However, the skulltula is not clearable because it will come back whenever you reload the room.

An example of where this concept is relevant is Beneath the Graveyard. In Room 1 of Beneath the Graveyard, a 50 Rupee Chest appears once you kill all of the bad bats (which are all Category 5 instances). Once the chest appears (side note: the chest was actually already allocated in the heap before it even appeared, some actors behave this way), the bad bats will never reappear when reloading the room (without Song of Time of course) because a flag was set to clear them. Also, the bats will never even attempt to load when you reload the room because they are Category 5 (and thus there will NOT be any gap leftover in the heap due to the bats deallocating immediately after allocating) [EDIT: There is one known counterexample to this rule: there is an example of a Category 5 actor that when cleared will reload on room load and then deallocate (instead of never reloading at all), namely the skulltula in Bomber's hideout on the way to the balloon].

--- Note About Spawners
There are some actors known as spawners. An example of a spawner is a Rupee Cluster (Id 00E8). There are only 2 rupee clusters in the game. One in Deku Palace and one in Beneath the Graveyard. They are the clusters of 6 green rupees surrounding a single red rupee. Other examples of spawners include grass clusters and butterflies (both found in Spring Mountain Village). The way spawners allocate is different from how other actors spawn in the sense that the spawner itself will allocate normally, but then the actors that it spawns will spawn afterwards (and these "spawned" actors get allocated AFTER everything else when a room gets loaded). For example, when a rupee cluster gets loaded, a 00E8 Overlay and AI get loaded and then 7 000E AIs get loaded afterwards (with no corresponding overlay since actor 000E doesn't have a Type A overlay). Note that red rupees and green rupees share the same actor Id 000E.

Slightly Less Simplified Case: 2 Rooms With Only 1 Loading Plane/Door Connecting Them, Rupee Cluster in New Room

Suppose that you are initially in Room 0 and you pass through a short loading plane in Room 1, which contains a Rupee Cluster. Here is what happens:
 1. everything from Room 1 loads one-by-one, in order
 2. everything from Room 0 deallocates (EXCEPT for the loading plane you passed through AND the 3-day Clock Actor AND any overlays for which instances also exist in Room 1 because these overlays only deallocate once no such instances exist)
 3. Any "cleared" actors will deallocate, often leaving a gap in the heap (also, if a new instance of the 3-day Clock Actor was allocated, this will deallocate at this step as well; the clock actor closer to the top of the heap will stay allocated; EDIT: not actually sure if it is always the one close to the top or just the new one, when simulating heaps deallocating the new one has always worked for me; also worth noting that Dampe (id 01CA) in graveyard can behave like the clock (id 015A))
 4. 7 Rupee Instances (Id 000E) from the rupee cluster will get allocated

However, things get more complicated with spawners...

The instances that get spawned by a spawner (e.g. the 7 000E instances in the case of a rupee cluster) can deallocate based on the camera's position. (Here is a video that showcases this: https://www.youtube.com/watch?v=wWDT7w3GQbI)

This idea can come into play in Beneath the Graveyard, for example. If the camera is not facing a direction such that the rupee cluster is on camera, then the rupee will not allocate when you load the room until you look at them. In Beneath the Graveyard, since there is a long loading plane, both rooms can be loaded at the same time


EDIT: see this video + description for an example of a heap manip using camera manip to deallocate spawners: https://www.youtube.com/watch?v=9b1bIVR_x2A

There is more info on the actor heap not written here, but this should give you most of the fundamentals important for exploring it more. I never finished writing this, so dm me with questions.