RFR: 8367332: Replace BlockTree tree logic with an intrusive red-black tree

[Thomas Stuefe]

On Thu, 11 Sep 2025 09:40:21 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

> Hi everyone,
> 
> Metaspace's `BlockTree` is currently implemented as a simple binary search tree, using the memory blocks it stores as the nodes. While this is straightforward and generally fine, it can become unbalanced depending on insert/remove order, leading to degraded performance.
> 
> This is a good fit for the utilities `IntrusiveRBTree`, instead of using internal tree logic. With it, we can replace all tree functions and instead rely on a few insert/remove calls. `BlockTree` still remains as the layer coordinating these blocks, and still handles the list of same-size nodes. The intrusive red-black tree only handles balancing and linking/unlinking nodes in the tree structure. 
> 
> Validation and printing are preserved by using the hooks provided by the red-black tree. We keep the same checks (and get a few more from the rb-tree), and the printed output is kept identical. The only real difference is that the red-black tree traverses the tree instead.
> 
> Testing:
> - Oracle tiers 1-8

I saw this just now. I guess this makes sense, but I admit I feel a bit apprehensive about this. Is the RBTree already mature enough? Have we ironed out all issues?

Can you please test:
- that the number of freeblock nodes stays the same pre- and post-patch? (Easiest would be with VM metaspace, I think I print out freeblock statistics somewhere)
- that the number of malloc blocks from Metaspace stays the same or that we can explain differences for a simple test? (the old tree lived completely in metaspace and needed no secondary structures; I just want to make sure its still the case. I have not looked at the new RB tree implementation for a while).

-------------

PR Comment: https://git.openjdk.org/jdk/pull/27212#issuecomment-3532388629