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

[Casper Norrbin]

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 ran a few DaCapo benchmarks as a sanity check to ensure that there were no unexpected side effects from these changes. The VM.info output (expandable section below) shows that the values remain the same, as expected.

<details>
<summary>VM.info output (expandable)</summary>

Output before this patch:

Metaspace:
Metaspace        used 99301K, committed 100608K, reserved 1179648K
 class space     used 11954K, committed 12544K, reserved 1048576K

Usage:
  Non-class:     85.30 MB used.
      Class:     11.67 MB used.
       Both:     96.97 MB used.

Virtual space:
  Non-class space:      128.00 MB reserved,      86.00 MB ( 67%) committed,  2 nodes.
      Class space:        1.00 GB reserved,      12.25 MB (  1%) committed,  1 nodes.
             Both:        1.12 GB reserved,      98.25 MB (  9%) committed. 

Chunk freelists:
   Non-Class:  10.08 MB
       Class:  3.83 MB
        Both:  13.91 MB

num_allocs: 635176.
num_deallocs: 6834.
num_allocs_from_deallocated_blocks: 21675.
num_chunks_retired: 3605.
num_allocs_failed_limit: 9.
num_arena_births: 1780.
num_arena_deaths: 438.
num_vsnodes_births: 3.
num_vsnodes_deaths: 0.
num_space_committed: 1572.
num_space_uncommitted: 0.
num_chunks_returned_to_freelist: 575.
num_chunks_taken_from_freelist: 5386.
num_chunk_merges: 209.
num_chunk_splits: 3640.
num_chunks_enlarged: 5236.
num_inconsistent_stats: 0.


Output after this patch:

Metaspace:
Metaspace        used 99311K, committed 100608K, reserved 1179648K
 class space     used 11951K, committed 12544K, reserved 1048576K

Usage:
  Non-class:     85.31 MB used.
      Class:     11.67 MB used.
       Both:     96.98 MB used.

Virtual space:
  Non-class space:      128.00 MB reserved,      86.00 MB ( 67%) committed,  2 nodes.
      Class space:        1.00 GB reserved,      12.25 MB (  1%) committed,  1 nodes.
             Both:        1.12 GB reserved,      98.25 MB (  9%) committed. 

Chunk freelists:
   Non-Class:  10.31 MB
       Class:  3.83 MB
        Both:  14.14 MB

Internal statistics:

num_allocs: 635534.
num_deallocs: 6709.
num_allocs_from_deallocated_blocks: 21265.
num_chunks_retired: 3600.
num_allocs_failed_limit: 9.
num_arena_births: 1790.
num_arena_deaths: 438.
num_vsnodes_births: 3.
num_vsnodes_deaths: 0.
num_space_committed: 1572.
num_space_uncommitted: 0.
num_chunks_returned_to_freelist: 556.
num_chunks_taken_from_freelist: 5391.
num_chunk_merges: 213.
num_chunk_splits: 3672.
num_chunks_enlarged: 5268.
num_inconsistent_stats: 0.

</details>

To quickly recap how the intrusive tree works: we embed an `IntrusiveNode` inside an external structure. This `IntrusiveNode` is a lightweight data class containing three pointers, used to connect elements in a tree structure. The user must provide comparison functions that operate on the external data, since the intrusive tree neither manages nor allocates memory itself. When a node is added or removed, only the pointers within `IntrusiveNode` are updated.

By swapping the `BlockTree` parent/child pointers to use an `IntrusiveNode`, we are effectively maintaining the same tree structure, just managed differently. The process for inserts/removals remain similar, but we now also balance the tree, which only involves shuffling some pointers. Importantly, no additional memory allocation is done: all relevant data still resides in the outside class (`BlockTree::Node` in this case). The main difference is that pointer management is handled by a separate class, rather than maintaining internal tree logic within `BlockTree`.

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

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