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

[Luck, Tony]

Sent from my iPhone

> On Aug 3, 2021, at 14:47, Matthew Wilcox
> 
> 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.

That’s good to know. While current xarray
implementation might be a bit wasteful[1],
things will get better.

I’m still going with xarray to keep the source
simple.

-Tony

[1] A few KBytes extra doesn’t even sound
too terrible to manage tens of MBytes (or
more) of SGX EPC memory on a system
with a half TByte total memory.