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

[Jan Beulich <jbeulich@xxxxxxxx>]

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
>>
>> "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).

Jan