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

[Casper Norrbin]

On Fri, 14 Nov 2025 11:57:35 GMT, Johan Sjölen <jsjolen 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.

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

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