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

[Axel Boldt-Christmas]

On Wed, 8 Oct 2025 09:42:07 GMT, Johan Sjölen <jsjolen 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
>
> src/hotspot/share/memory/metaspace/blockTree.hpp line 105:
> 
>> 103:     static Node* cast_to_node(const TreeNode* tree_node) {
>> 104:       return (Node*)((uintptr_t)tree_node - offset_of(Node, _tree_node));
>> 105:     }
> 
> We should really have this as a separate static function for the IntrusiveRBNode. It's also technically not a cast, it finds the outer data.

We could use inheritance `struct Node : public IntrusiveRBNode` and actually have it be a cast. Simplifies some things, not sure if we see other issues. But seems like a valid abstraction that the BlockTree Node is a IntrusiveRBNode.

We should probably do an assert that the node is valid() here (Should catch if any none Node IntrusiveRBNode ended up here).

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

PR Review Comment: https://git.openjdk.org/jdk/pull/27212#discussion_r2415773836