[PATCH v4 1/2] kho: Adopt radix tree for preserved memory tracking

[Jason Gunthorpe]

On Mon, Jan 12, 2026 at 12:15:54PM +0200, Mike Rapoport wrote:
> > + * The tree is traversed using a key that encodes the page's physical address
> > + * (pa) and its order into a single unsigned long value. The encoded key value
> > + * is composed of two parts: the 'order bit' in the upper part and the 'page
> > + * offset' in the lower part.::
> > + *
> > + *   +------------+-----------------------------+--------------------------+
> > + *   | Page Order | Order Bit                   | Page Offset              |
> > + *   +------------+-----------------------------+--------------------------+
> > + *   | 0          | ...000100 ... (at bit 52)   | pa >> (PAGE_SHIFT + 0)   |
> > + *   | 1          | ...000010 ... (at bit 51)   | pa >> (PAGE_SHIFT + 1)   |
> > + *   | 2          | ...000001 ... (at bit 50)   | pa >> (PAGE_SHIFT + 2)   |
> > + *   | ...        | ...                         | ...                      |
> > + *   +------------+-----------------------------+--------------------------+
> > + *
> > + * Page Offset:
> 
> To me "page offset" reads as offset from somewhere and here it's rather pfn
> on steroids :) 
> Also in many places in the kernel "page offset" refers to the offset inside a
> page.
> 
> Can't say I can think of a better name, but it feels that it should express
> that this is an address more explicitly.

It is "Shifted Physical Address"

> > +			node = phys_to_virt((phys_addr_t)node->table[idx]);
> > +	}
> > +
> > +	/* Handle the leaf level bitmap (level 0) */
> > +	leaf = (struct kho_radix_leaf *)node;
> > +	idx = kho_radix_get_index(key, 0);
> > +	__clear_bit(idx, leaf->bitmap);
> 
> I think I already mentioned it in earlier reviews, but I don't remember any
> response.
> 
> How do we approach freeing empty bitmaps and intermediate nodes?
> If we do a few preserve/uppreserve cycles for memory that can be allocated
> and freed in between we might get many unused bitmaps.

Surely this is an error case??

We shouldn't be unpreserving at all in a normal flow?

> My view is that we should free the empty bitmaps, maybe asynchronously.
> The intermediate nodes probably don't take that much memory to bother with
> them.

Telling they are empty would be quite expensive. I think we should not
attempt to clean the tree unless there is a really good reason why we
should have good flows with alot of unpreserving activity.

I think we would be better served to treat the root cause and fixup
what ever is doing preserving/unpreserving loops.

Jason