Re: [PATCH v4 3/4] mm: Optimize mprotect() by PTE-batching

[Lorenzo Stoakes <lorenzo.stoakes@oracle.com>]

On Tue, Jul 01, 2025 at 12:31:02PM +0100, Ryan Roberts wrote:
> >> The issue is the efficiency. Assuming we want to keep the PTE scan contained
> >> within the core folio_pte_batch() function and we _don't_ want to add PAE
> >> awareness to that function, then we have 2 separate, independent loops; one for
> >> PTE scanning and the other for PAE scanning. If the first loop scans through ans
> >> returns 512, but then the PAE scan returns 1, we return 1. If we don't remember
> >> for the next time that we already determined we have a PTE batch of 512 (now
> >> 511) then we will rescan the 511 PTEs and potentially return 1 again due to PAE.
> >> Then 510, then 509...
> >
> > Hm really?
> >
> > The idea is mprotect_folio_pte_batch() would look ahead and determine the
> > PAE/non-PAE sub-batch and return this nr_pages. It'd check 'this page is PAE, so
> > when's the next page that is not/hit max_nr_pages?'
> >
> > So that'd be 1 in the first case.
> >
> > Then you loop around and go again, and this time it'd check 'this page is !PAE,
> > so when's the next page that is/hit max_nr_pages?' and then it'd return 511.
> >
> > A better example I think is e.g. if we had, for the sake argument, it return 16,
> > 16, 480.
> >
> > Then we scan ahead 16, set nr_ptes = 16, process 16 PTEs. Then the same again,
> > then the same again only for 480 PTEs.
> >
> > Each time we set nr_ptes = the sub-batch size.
> >
> > So I don't think we'll see O(n^2) here?
> >
> > It would be like:
> >
> > 	do {
> > 		/* now returns sub-batch count */
> > 		nr_ptes = mprotect_folio_pte_batch(folio, addr, pte, oldpte,
> > 				   max_nr_ptes, FPB_IGNORE_SOFT_DIRTY);
> >
> > 		... rest of logic remains roughly the same ...
> > 	} while (...);
> >
> > I may be being naive here in some way?
>
> I believe so, yes. But usually it's me that ends up being wrong. Let me try to
> explain my point and we shall see...

Haha no, being embarrassingly wrong is my speciality. Don't take that from me ;)

But in this case I think you're right here actually and I've underestimated the
complication here.

>
> There are 2 separate requirements that need to be met for a batch to be assembled:
>
>   - All PTEs have to map consecutive pages from the same folio, all with the
>     same pgprots (except a/d/sd).
>   - If anon, all of the mapped pages must have the same PAE value.
>
> The first requirement is managed by scanning forward through PTEs until it hits
> the first PTE that is non-conformant (or hits max_nr). Currently implemented by
> folio_pte_batch().

OK so I think this is the crux. The folio_pte_batch() is naive to the PAE thing,
and so we end up having to rescan.

>
> The second requirement is managed by scanning through the struct pages, checking
> PAE (or hits max_nr).
>
> The final batch is determined according to the smaller of the 2 batches
> determined using both these checks.
>
> So, assuming we don't want to fold both of those into the same loop (which would
> enable checking the PTE and PAE in lock-step, mprotect_folio_pte_batch() needs
> to call both folio_pte_batch() and loop over the pages looking at PAE in order
> to decide where the batch boundary is.
>
> If we want it to be stateless, then if it scans the PTEs first and that batch is
> larger than the batch determined for the subsequent PAE scan, we return the
> smaller and next time it is called it will rescan those excess PTEs. The same
> logic applies in reverse if you scan PAE first.
>
> If we make it stateless, it can remember "I've already scanned PTEs and the PTE
> batch ends at X. So now I just need to iterate through that to create
> sub-batches taking PAE into account".

Right yeah. Statelessness is not crucial here and doesn't seem workable then.


> > The current implementation is not acceptable on the basis of adding a horrible
> > level of complexity. That function is already terrible, and adding an inner loop
> > for this batch special casing with _sub batches_ to account for PAE- nobody is
> > going to understand what's going on.
> >
> > 	do {
> > 		if (...) {
> > 			while (...) {
> > 				help!!!
> >
> >
> > We can do better, and I'm going to go further and say - this series _has_ to do
> > better, because I can't accept that, however we do it.
> >
> > I want the efficiency gainz as much as you guys but I"m convinced we can do it
> > without causing eye bleeding confusion...
>
> That's completely reasonable - we will get there! I'm very happy for this to be
> refactored into help function(s) to make it more accessible.

We'll definitely get there :)

>
> I'm just saying that fundamentally, we either need to flatten this to a single
> loop so that the PTE and PAE can be assessed in lock-step and we never
> over-scan. Or we need to keep some state to remember when we have already
> scanned for a PTE batch and are currently working our way through that chunking
> it into sub-batches based on PAE. I don't think we should entertain a stateless
> two-loop solution.

Yes.

>
> >
> >>
> >>>
> >>> We might need to pass a flag to say 'don't account for this' for prot numa case.
> >>
> >> Yep, another bool ;-)
> >
> > Yeah... but we can't sensibly add a flag for this so the flag idea doesn't fly
> > for that either... :>)
> >
> > I mean I don't think we actually need that flag, let it skip the sub-batch size
> > then check again. Now that, I reckon, is a small overhead.
>
> Yeah, agreed. That's probably fine in practice.

Ack.

Let me fiddle with this code and see if I can suggest something sensible.