Re: [PATCH v2 15/18] IOMMU/x86: prefill newly allocate page tables

[Jan Beulich <jbeulich@xxxxxxxx>]

On 14.12.2021 12:41, Roger Pau Monné wrote:
> On Tue, Dec 14, 2021 at 10:15:37AM +0100, Jan Beulich wrote:
>> On 13.12.2021 16:51, Roger Pau Monné wrote:
>>> On Fri, Sep 24, 2021 at 11:54:58AM +0200, Jan Beulich wrote:
>>>> Page table are used for two purposes after allocation: They either start
>>>> out all empty, or they get filled to replace a superpage. Subsequently,
>>>> to replace all empty or fully contiguous page tables, contiguous sub-
>>>> regions will be recorded within individual page tables. Install the
>>>> initial set of markers immediately after allocation. Make sure to retain
>>>> these markers when further populating a page table in preparation for it
>>>> to replace a superpage.
>>>>
>>>> The markers are simply 4-bit fields holding the order value of
>>>> contiguous entries. To demonstrate this, if a page table had just 16
>>>> entries, this would be the initial (fully contiguous) set of markers:
>>>>
>>>> index  0 1 2 3 4 5 6 7 8 9 A B C D E F
>>>> marker 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0
> 
> Could you expand bit more on this explanation?
> 
> I don't get how such markers are used, or how they relate to the page
> table entries. I guess the point is to note whether entries are
> populated, and whether such populated entries are contiguous?
> 
> Could you provide a more visual example maybe, about what would go
> into each relevant page table entry, including the marker
> information?

I'm not sure I understand what you're after. The markers say "This
2^^marker aligned range is contiguous" (including the case of
contiguously clear). And they go into a vendor dependent ignored
4-bit field in each PTE. (Obviously odd numbered PTEs won't ever
be updated from holding a zero marker.)

An intermediate page table is eligible for replacement when the
marker of entry 0 is 9.

>>>> "Contiguous" here means not only present entries with successively
>>>> increasing MFNs, each one suitably aligned for its slot, but also a
>>>> respective number of all non-present entries.
>>>
>>> I'm afraid I'm slightly lost with all this, please bear with me. Is
>>> this just a performance improvement when doing super-page
>>> replacements, or there's more to it?
>>
>> What I wanted to strictly avoid is to have to scan entire pages for
>> contiguity (i.e. on average touching half a page), like e.g.
>> map_pages_to_xen() and modify_xen_mappings() do. Hence I tried to
>> find a scheme where for any individual update only a predictably
>> very limited number of entries need inspecting (some of these then
>> of course also need updating).
> 
> Thanks. So there's some extra cost here of having to update those
> markers when a page table entry is modified.

Well, yes, in order to re-coalesce _some_ extra cost is to be paid in
any event.

Jan