Re: [PATCH v3 2/7] x86/sgx: Add infrastructure to identify SGX EPC pages

[Matthew Wilcox <willy@infradead.org>]

On Fri, Jul 30, 2021 at 11:35:38PM +0000, Luck, Tony wrote:
> >	xa_store_range(&epc_page_ranges,
> >		       section->phys_addr,
> >		       section->end_phys_addr, ...);
> >
> > ... you did it based on PFNs:
> >
> >	xa_store_range(&epc_page_ranges,
> >		       section->phys_addr     >> PAGE_SHIFT,
> >		       section->end_phys_addr >> PAGE_SHIFT, ...);
> >
> > SGX sections are at *least* page-aligned, so this should be fine.
> 
> I found xa_dump() (hidden inside #ifdef XA_DEBUG)
> 
> Trying both with and without the >> PAGE_SHIFT made no difference
> to the number of lines of console output that xa_dump() spits out.
> 266 either way.
> 
> There are only two ranges on this system
> 
> [   11.937592] sgx: EPC section 0x8000c00000-0x807f7fffff
> [   11.945811] sgx: EPC section 0x10000c00000-0x1007fffffff
> 
> So I'm a little bit sad that xarray appears to have broken them up
> into a bunch of pieces.

That's inherent in the (current) back end data structure, I'm afraid.
As a radix tree, it can only look up based on the N bits available at
each level of the tree, so if your entry is an aligned power-of-64,
everything is nice and neat, and you're a single entry at one level
of the tree.  If you're an arbitrary range, things get more complicated,
and I have to do a little dance to redirect the lookup towards the
canonical entry.

Liam and I are working on a new replacement data structure called the
Maple Tree, but it's not yet ready to replace the radix tree back end.
It looks like it would be perfect for your case; there would be five
entries in it, stored in one 256-byte node:

	NULL
0x8000bfffff
	p1
0x807f7fffff
	NULL
0x10000c00000
	p2
0x1007fffffff
	NULL
0xffff'ffff'ffff'ffff

It would actually turn into a linear scan, because that's just the
fastest way to find something in a list of five elements.  A third
range would take us to a list of seven elements, which still fits
in a single node.  Once we get to more than that, you'd have a
two-level tree, which would work until you have more than ~20 ranges.

We could do better for your case by storing 10x (start, end, p) in each
leaf node, but we're (currently) optimising for VMAs which tend to be
tightly packed, meaning that an implicit 'start' element is a better
choice as it gives us 15x (end, p) pairs.