Java Edition:Parallel Asynchronous Threads
Parallel asynchronous threads are extremely complex, arguably the most complicated method for any discontinued feature. Utilized properly, they allow for every possible block item, block and falling block[note 1] to be obtained in survival. For many of them, it's the only way to get them in release versions of the game, or at all.
To perform the desired corruptions and race conditions needed for obtaining discontinued blocks, items and falling blocks, obtaining block updates on a different thread from the main game is a necessity.
Terminology Crash Course
As one of the most complicated exploits ever performed in Minecraft, there is a lot of terminology and internal game mechanics that first must be understood. These all play a crucial role in being able to pull this exploit off.
Multi-Threading and Race Conditions
In singlethreaded programs, instructions are executed one after another, like shown below. This is how the majority of Minecraft's game logic is and is designed to be handled.
| Time ➔ | |||
| Process 1 | Process 2 | Process 3 | Process 4 |
In multithreaded programs, multiple instructions can be executed at the same time. Do note that processes can start and end at completely different times, unlike depicted in the table below.
| Time ➔ | ||||
| Thread 1 | Process 1 | Process 2 | Process 3 | Process 4 |
|---|---|---|---|---|
| Thread 2 | Process 5 | Process 6 | Process 7 | |
A race condition arises in software when multiple threads are accessing and modifying the same variables in memory. If the threads take a different amount of time than expected, or run at unexpected times, they can overwrite and undo each other's modifications, which can cause software bugs due to unanticipated behavior.
For the below example, the threads do not run concurrently, and the desired output is produced:
| Thread 1 | Thread 2 | Integer value | |
|---|---|---|---|
| 0 | |||
| read value | ← | 0 | |
| increase value | 0 | ||
| write back | → | 1 | |
| read value | ← | 1 | |
| increase value | 1 | ||
| write back | → | 2 |
However, if the two threads run simultaneously without locking or synchronization, the outcome of the operation can be different from the expected result. The alternative sequence of operations below demonstrates this scenario:
| Thread 1 | Thread 2 | Integer value | |
|---|---|---|---|
| 0 | |||
| read value | ← | 0 | |
| read value | ← | 0 | |
| increase value | 0 | ||
| increase value | 0 | ||
| write back | → | 1 | |
| write back | → | 1 |
There are two vital race conditions exploited within Minecraft to produce block updates on a separate game thread: Concurrent modification of the world's loaded chunk map, and the concurrent modification of a chunk's block data.
The Chunk Hashmap
The chunk hashmap is an array of currently loaded chunks. Whenever a new chunk is loaded, a hash value is calculated based on its position. The game will then try to assign the chunk to the index of its hash value. Some chunks can have the same hash value, in which case the game will search for the next free index where the chunk can be assigned. Similar process occurs when the game needs to get a chunk from the hashmap with getChunk. The game will first look at the index corresponding to the hash, and if it contains the incorrect chunk, it will look at the next higher index and check again. This repeats until it finds the chunk or has searched the entire hashmap.
If there are multiple chunks with same hash in the hashmap, and one of them is unloaded, the chunk with the highest index will take its place.
Clustering Chunks
A chunk can become "clustered" if its index is far away from its hash, and all indexes between the hash and the real index are filled with chunks with different hashes. The farther apart the index and the hash, the more clustered the chunk is.
| Index | Chunk | Hash |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | A | 2 |
| 3 | B | 3 |
| 4 | C | 4 |
| 5 | D | 4 |
| 6 | E | 5 |
| 7 | F | 2 |
Observers on Instant Scheduling
When the instant scheduling flag is enabled, observers double the amount of block updates that going through it. If a line of observers is made, the number of updates sent by last observer is defined by formula 2n, n being the number of observers. If made long enough, the observer line can send thousands of updates per second for hours, days, months, or even years.
Updating too many observers on the main thread when instant scheduling is enabled can lead to freezes and crashes due to a game tick taking more than 60 seconds to process. Observer lines running asynchronous updates do not have these issues, as the lag is not on the main thread.
Why Stained Glass and Beacons
Every time a stained glass block or stained glass pane block is placed or broken, a thread independent from the main game thread is created, which searches downwards for beacons in order to change the beam color. This is the only known way to have another thread run logic in the world other than the main game thread, due to the presence of several getBlockState calls made to check for valid beacons.
Putting It All Together ("The Unload Method")
In short, a beacon thread needs to populate a chunk, which will produce block updates from decoration placement to be detected by observers and produce block updates on the beacon thread.
When a glass thread finds a solid block below the stained glass, getBlockState is called, which attempts to load the chunk from the hashmap to fetch the block data from the chunk (in the example below, the game is looking for a chunk at yellow index). If the unload chunk (red) is unloaded on the main thread while the beacon thread searches for the glass chunk (yellow) on the beacon thread, the glass chunk will get reassigned to the unload chunk's location in the hashmap. For the search of the glass chunk within the hashmap to miss the glass chunk due to its move to an index value that has already been searched, the glass chunk must be clustered as much as possible to delay the search while the main game thread unloads the unload chunk and moves the glass chunk to the unload chunk's former index.
Hashmap Visualization:
get method
|
≠yellow, ↷ | ≠yellow, ↷ | checking... | ||||
| Loaded chunks in a hashmap |
|
|
|
|
|
|
|
remove method
|
get method
|
≠yellow, ↷ | ≠yellow, ↷ | checking... | ||||
| Loaded chunks in a hashmap |
|
|
|
|
|
|
|
remove method
|
↑ | ← | ← | ← | ↲ |
get method
|
≠yellow, ↷ | ≠yellow, ↷ | ≠yellow, ↷ | ≠yellow, ↷ | ≠yellow, ↷ | ≠yellow, ↷ | Chunk not found! |
| Loaded chunks in a hashmap |
|
|
|
|
|
| |
remove method
|
↑ | ← | ← | ← | ↲ |
The glass threads will be started at the Sync task including actions from client packets phase of the game tick, from players placing the stained glass, and they must survive until the Chunk unloading phase. To shorten the Mob spawning phase, which is extremely computationally expensive, mob switches for all 4 types of mobs are highly recommended (passive, hostile, ambient and water).
However, there needs to be some slight lag on the main game thread directly after creating the beacon threads due to a possible uncaught ConcurrentModificationException. This is achieved by placing the last stained glass block next to an extended BUD piston, which upon receiving the block update, will retract to update a small line of ~6-10 observers (hardware dependent).
| [...] |
| Sync task including actions from client packets (player actions) |
| [...] |
| Mob spawning |
| Chunk unloading |
| [...] |
To extend the lifetime of the glass threads as much as possible, the glass will be placed as high in the world as possible to extend the amount of blocks searched vertically. Beacons are also placed below the stained glass, as if the thread finds a beacon, it will schedule an update task for the beacon, slightly slowing the thread. Multiple stained glass should be placed as well to create many threads at once, as a synchronized block of code greatly slows down the execution of the glass threads when more than one is running.
The movement of the glass chunk in the hashmap during the search for it will result in the getBlockState call searching for beacons failing to find the chunk. The game will then default to loading the chunk from the disk, even though it's already loaded into memory. This reload will try to populate any unpopulated chunks adjacent in the negative x and z diretion.
One of them needs to be a loaded, but unpopulated chunk. The unpopulated chunk will populate on the asynchronous thread, placing world decorations that can be detected by an observer, such as dungeons or liquid falls. Chaining observers off of the update produced from asynchronous population creates the asynchronous observer line.
Those observers are on instant scheduling, but they won't lag the main game thread because they are running on the beacon thread.
Performing Chunk Swaps and Getting Asynchronous Observer Lines
Performing Unload Method in Survival
In Singleplayer
In Multiplayer
This tutorial is based on this world download.
To begin, player 1 must log in before player 2. A third player is also used for control of the unload chunk, but this player will not move or do anything during the process, so it does not matter what order this player logs in with. Player 2 must then load the unload chunk, as it will have the same hash as the beacon tower chunk, and it needs to occupy the ideal spot in the hashmap. Now, player 1 will need to load the beacon tower, and next to this beacon tower will need to be an "invisible chunk", which is further explained in this section (link to invisible chunk explanation, which should be contained in a "population exploits" section.) The invisible chunk is an unpopulated, but loaded chunk required to allow the async thread to run the population code. After the invisible chunk is created, player 1 moves over to the beacon tower. Player 2 can now activate a small lag machine, which should lag the game for about 15 seconds. During this period of lag, player 2 moves over a chunk border, which will cause the unloading of the unload chunk, and player 1 will place stained glass above the beacon tower, which will create many threads calling getBlockState. During all this, it's important to keep in mind the order of these actions. All the actions of player 1 will get processed before the actions of player 2, because player 1 logged in earlier. Now, after the player requests have been finalized (except for the async tasks, which will continue running), the tick moves on to the next phase, which is mob spawning. To make the mob spawning phase as short as possible, we use mob switches for all 4 types of mobs (passive, hostile, ambient and water), because then the game will not attempt to spawn mobs, severely lowering the amount of necessary calculations. Now the unload chunk phase begins, and if the race condition is met, some threads are still alive when the beacon tower chunk gets moved to the front of the hashmap. Due to this shift occurring during the async search, the async thread may fail to find it, which will force the game to load the chunk from disk. This loading will check around itself if there are chunks which have not been populated yet, and it will find the invisible chunk. The async thread will populate the invisible chunk, making it turn visible, and during the population of that chunk, the placement of a liquid spring can be detected using observers. These observers will start blinking due to the updates provided by the liquid pocket. Additionally, the liquid pocket turns instant tile ticking on, so the observers exponentially multiply the updates from the async thread. If everything has gone well, then you have just achieved one of the most difficult bugs currently known.
Getting Multiple Asynchronous Observer Lines
Utilizing Asynchronous Observer Lines
Block Transmutation
Asynchronous observer lines can be used to trick the game into placing a block with data value of a shield being equipped.
Block Transmutation in Theory
This method requires an asynchronous observer line as well as 1000 cluster chunks. Glass chunk needs to be clustered.
The player needs to move a block from main hand to offhand and place the block. Meanwhile asynchronous observer line will be targeted at the dispenser which is equipping the player with a shield with desired data value.
Performing Block Transmutation in Survival
Palette Corruption
Asynchronous observer lines can be used to copy blocks in a subchunk, or even create new ones.
Blockstate Palettes
In each subchunk the blockstates get stored in a palette. The type of the palette on the number of different blockstates in the chunk.
| Number of Blockstates | Palette Type |
|---|---|
| 0-16 | Linear |
| 17-256 | Hashmap |
| 257+ | Registry |
Palettes upsize immediately when enough blockstates is added. They only downsize upon reloading the chunk.
Here are some differences between hashmap and registry palette.
| Hashmap | Registry |
|---|---|
| Contains only blockstates that exist (or existed) in the subchunk. | Contains every blockstate in the game. |
| IDs assigned to blocks can be changed. | IDs are always the same for every blockstate. |
| Word tearing can be used to replace block by another block that exists in the subchunk. | Word tearing can be used to create blocks that did not exist before. |
Hashmap Palette
Registry Palette
| Decimal Block ID | 137 |
| 9 bit Binary Block ID | 010001001 |
| Block ID + Metadata | 0100010010000 |
Falling Block Swaps
How Sand Works
Between the moment a sand block receives a block update to point where it turns into a falling block the following processes are executed:
- When sand gets a block update the
scheduleUpdatemethod is called, which callsupdateBlockTick. - A check for instant tile tick is made.
- If instant tile tick is on, a check is made if the current block in that position is equal to the sand block.
- If that is true, the
updateTickmethod is called, which calls thecheckFallablemethod. - A check is made to see if the instant falling flag is off and to make sure the sand isn't in a lazy chunk.
- If both of those checks return "true", the non-instant falling code will be run
- The falling block entity will now re-get the blocktype and it's state from the world, and it will set itself to that blocktype and -state.
- If that is true, the
- If instant tile tick is on, a check is made if the current block in that position is equal to the sand block.
If the block state is changed between the current block/sand block check and the last process, the falling version of a different block can be obtained, and this is why we need a different thread in the first place: there simply are no operations in between these two checks that can be used to change the block at the sand's position. This means we require a whole different thread to do it for us, as different threads can execute tasks at the same time, and therefore also inbetween a task from another thread.
At the first tick of a falling block existing a check is made if the falling block has the state same block state as the block at it's position. If yes the block is set to air. Otherwise the falling block is deleted. This means that if you change the blocktype too late, the created falling block will simply delete itself instead of becoming the block at it's origin location.
Generic Method
Other Setups
Videos on the Subject of Async Exploits
A collection of videos made by the team who discovered asynchronous exploits can be found here