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

[Thomas Stuefe]

On Fri, 14 Nov 2025 12:40:20 GMT, Casper Norrbin <cnorrbin at openjdk.org> wrote:

> > 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?
> 
> I believe it has matured enough. It is already used in NMT and C2 printing, and in ZGC to track physical memory very similarly to what is done in here.
> 
> > 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).
> 
> The intrusive red-black tree lives entirely in outside memory and does not allocate any structures of its own, so the same freeblock nodes also become nodes for the red-black tree. Nothing of this should change, but I can test this further to confirm.
> 
> > We can await RDP1 and integrate this after that. It's closing in on that anyway.
> 
> I have no problem waiting a little more to integrate.

Thank you. Let's wait for 27 with this one. I will give it a look until then.

I am fine with the direction of this patch. I think this was one of the reasons I pinged Johan(?) some time ago about writing a general-purpose RedBlack tree.

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

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