Clarification on the Usage and Purpose of the `dynamap` Red-Black Tree in Box64

[devarajabc]

While examining Box64's memory management system, particularly the usage of rbtree, I observed unusual behavior involving the dynamap tree. By running Box64 combined with Wine64 on a Windows 64-bit chess game, I noticed that the dynamap tree significantly outnumbers other trees in node count. However, despite the high node usage, nodes from dynamap were rarely (if ever) actively accessed during execution (rb_get, rb_get_64, rb_get_end, rb_get_end_64, rb_get_right or rb_get_left calls).

Additionally, I collected detailed statistics on node creation and usage: A total of 54,306 rbtree nodes were created during execution. Only 17,886 nodes were released before the process terminated.

Among the released nodes, the breakdown of unused nodes (i.e., created but never accessed) is as follows:

1. blockstree: 0 unused nodes
2. db_sizes: 52 unused nodes
3. dynamap: 16,697 unused nodes (100% of released dynamap nodes were unused)
4. envmap: 1 unused node
5. mapallmem: 158 unused nodes
6. mapmem: 105 unused nodes
7. memprot: 873 unused nodes
8. rbt_dynmem: 0 unused nodes

To further verify this observation, I experimentally disabled the usage of dynamap within the Box64 codebase and repeated my tests. Surprisingly, the system functioned perfectly without noticeable issues.

int rb_set_64(rbtree_t *tree, uintptr_t start, uintptr_t end, uint64_t data) {
    if(!strcmp(“dynamap”, tree->name))
        return 0;
    //--skip--//
}

Given these observations, I seek clarification on the following points:

1. Intended Purpose: What was the initial purpose behind implementing the dynamap tree within Box64's memory management system?

2. Node Utilization: Why does dynamap contain so many nodes if these nodes are rarely (or never) accessed during regular operations?

3. Impact of Removal: Considering that disabling dynamap had no observable negative impact in my tests, could removing or optimizing dynamap improve memory efficiency or overall performance?

Experimental Environment:

1. Box64 Version: v0.3.5 d3d3fa25 on apr 7
2. Wine64 Version: wine-9.22
3. Host System: Raspberry Pi 400 running Linux Debian 6.12.3-arm64 #1 SMP Debian 6.12.3-1 (2024-12-07) aarch64 GNU/Linux
4. Game Tested: chess
5. Build Configuration:

cmake \
    -G Ninja \
    -D RPI4ARM64=1 -D ARM_DYNAREC=ON \
    -D CMAKE_BUILD_TYPE=RelWithDebInfo \
    -D CMAKE_C_COMPILER=aarch64-none-linux-gnu-gcc \
    ..
ninja

[ptitSeb]

Ok, interesting.

So those rbtree are multiple in fact. There is one per 2M block of memory allocated for dynarec blocks. Those rbtree are then use by FindDynablockFromNativeAddress(...) that allows getting back the dynablock_t struture based on a Native address. This is used for Signal handling. The rbtree is used to avoid a sequencial browsing of the memory mapping. Altho, when I look at those numbers you got, maybe the rbtree is a bit overkill, as it's not used too often. Well, signal handling is important, espcialy for windows program, but maybe that particular rbtree can be removed. I'll do some test later.

[devarajabc]

Update: I've added a second diagram showing node count accumulation with dynamap disabled . Also clarified that the test was conducted on a Raspberry Pi 400.

[ptitSeb]

So, I pushed a changed in box64 to not populate this rbtree unless needed. That means the 1st time a signal appears on a new address, the old way to find the dynablocks (slower) will be used. But for a repeated addressn it will use the faster rbtree. This should reduce rbtree nodes dramatycaly, and hopefully still get good signal handling times

[ptitSeb]

Hi bro please fix missing extension next box64 update. I wanna launch WWE 2K25 on box64 next update. I know you can fix all missing extension problems. Thank you God bless you ❤️🥰

I have no idea what you are talking about. But this is CLEARLY not the ticket for that. If you want something, create a ticket, don't parasite random ticket.

[devarajabc]

So, I pushed a changed in box64 to not populate this rbtree unless needed. That means the 1st time a signal appears on a new address, the old way to find the dynablocks (slower) will be used. But for a repeated addressn it will use the faster rbtree. This should reduce rbtree nodes dramatycaly, and hopefully still get good signal handling times

Thanks for the update !

I’d like to replicate your test on my Raspberry Pi 400. Could you let me know what test case or scenario you used to evaluate the new behavior?

[devarajabc]

Also, as a next step, I'm planning to build a memory profiling tool for Box64, specifically focused on rbtree usage. To do so, I’d like to confirm the intended usage and purpose of each red-black tree currently in use (e.g., db_sizes, envmap, etc.)— especially what the rbnode->data field represents in each of these trees.

Could you provide a brief explanation or point me to where these are documented in the codebase? Thanks again for the clarification !

[devarajabc]

@ptitSeb Here are the statistics on node creation and usage after commit 91848ef.

In my case, the number of nodes in dynamap is zero, resulting in nearly 90% memory savings compared to the previous version.

However, I realize the statistics I gathered may not be fully accurate, as my current test case likely doesn't trigger dynamap usage. If you could share the test case you used for validation, that would be very helpful.

[jserv]

Here are the statistics on node creation and usage after commit 91848ef.

To ensure meaningful analysis and meaningful insights from the statistics, provide comprehensive steps of your experimental methodology. Include detailed test case specifications, environmental configurations, and procedural steps that would allow others to reproduce your experiments precisely. Without this transparency, the reported metrics cannot be reliably validated or meaningfully correlated with real-world usage patterns.

[ptitSeb]

@ptitSeb Here are the statistics on node creation and usage after commit 91848ef.

In my case, the number of nodes in dynamap is zero, resulting in nearly 90% memory savings compared to the previous version.

However, I realize the statistics I gathered may not be fully accurate, as my current test case likely doesn't trigger dynamap usage. If you could share the test case you used for validation, that would be very helpful.

You needs some signal! You can try something in wine, some C# / Unity3D game, or try the "test21" from the tests folder...

[LukeShortCloud]

I believe everything here has been addressed. Can this be closed?