Skip to contentSkip to conversation

mmap lock in khugepaged

QUESTION Dev Jain 2 participants 5 messages Nov 29, 2024 – Dec 5, 2024 4 messages not in the archive Memory management

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

Dev Jain

author
#4 lore raw

+the list and Zi Yan.

Quoted 22 lines · David Hildenbrand
Quoted 8 lines
Quoted 6 lines

Maybe, we'd have to do the isolation+copy under the PMD lock. And currently, we have to drop the PMD lock in order to have the pte_offset_map_lock() work IIRC.

Is there a problem in holding two page table locks simultaneously?

Depending on CONFIG_SPLIT_PTE_PTLOCKS, it might not even be two locks (I assume we could have such configs with khugepaged).

Not sure if there could be an issue with lock inversion.

So I suspect this no not be 100% trivial :)

Quoted 7 lines
Quoted 6 lines

Most importantly, the copy that currently runs under no spinlocks would now run under spinlock. Up to 512 MiB on arm64 64K, not sure if that can be a problem ... we currently seem to take care of that

Quoted 6 lines
Quoted 1 line

But we already are taking mmap_write_lock(), so that should not matter?

We are dealing with a spinlock vs. a rwsem.

We usually want to avoid holding spinlocks for an excessive amount of time, because all other CPUs waiting for that lock will ... spin with preemption disabled instead of rescheduling and doing something useful.

Ah okay.

Quoted 10 lines

Further, without CONFIG_SPLIT_PMD_PTLOCKS, in fact everybody who wnats to take a PMD lock in that process would be spinning on the same PMD lock :)

Quoted 2 lines

I mean, if we can get rid of the mmap exclusive lock, then the copying would still be a bottleneck, and all fault handlers will back off, but

I'm trying to digest it once again, but I'm afraid I don't see how fault handlers will back off.

Won't they either see pmd_none(), to then either call pte_alloc_one() where they would spin on the PMD lock, or try allocating a PMD THP to insert it, and then spin on the PMD lock, to figure out later that it was all in vain?

Ya that's what I meant when I said "back off", sorry I wasn't clear, I didn't mean VM_FAULT_FALLBACK/RETRY or something...yes, the work will be in vain and the MMU will refault...

Quoted 10 lines

Thinking about it, I am also not sure if most other code can deal with temporary pmd_none(). These don't necessarily take the PMD lock, because "why would they" right now.

See walk_pmd_range() as one example, if it spots pmd_none() it assumes "there really is nothing" without checking the PMD lock.

As a more concrete example, assume someone calls MADV_DONTNEED and we end up in zap_pmd_range(). If we assume "pmd_none() == really nothing" we'll skip that entry without getting the PMD lock involved. That would mean that you would be breaking MADV_DONTNEED if you managed to collapse or not -- memory would not get discarded.

This is a real problem with anonymous memory.

Yes, I thought of different locking fashions but the problem seems to be that any pagetable walker will choose an action path according to the value it sees.

Quoted 2 lines

Unless I am missing something it's all very tricky and there might be a lot of such code that assumes "if I hold a mmap lock / VMA lock in read mode, pmd_none() means there is nothing even without holding the PMD lock when checking".

Yes, I was betting on the fact that, if the code assumes that pmd_none() means there is nothing, eventually when it will take the PMD lock to write to it, it will check whether the PMD changed, and back off. I wasn't aware of the MADV_DONTNEED thingy, thanks.

Quoted 18 lines
Quoted 4 lines

at least processes will be able to mmap() and do stuff with their VMAs, and I would guess that this is worth optimizing...

It would certainly be interesting to get rid of the mmap lock in write mode here, but it's all rater tricky (and the code has rather nasty hidden implications).

Quoted 11 lines
Quoted 11 lines

pte = pte_offset_map_lock(mm, &_pmd, address, &pte_ptl); if (pte) {
     ...
     spun_unlock(pte);
} ...

result = __collapse_huge_page_copy(...);
pte_unmap(pte);

Quoted 14 lines
Quoted 4 lines
Quoted 2 lines

Deep in __collapse_huge_page_copy() we seem to re-rake the PTL lock. No-split-spinlock confiogs might be problematic ...

Could you elaborate a little? I haven't read about the older config...

See above regarding CONFIG_SPLIT_PTE_PTLOCKS and friends.

Quoted 7 lines
Quoted 6 lines

I recall that for shmem that's "easier", because we don't have to reinstall a PMD immediately, we cna be sure that the page table is kept empty/unmodified, ...

All in all, the general solution seems to be that, if I can take all pagetable walkers into an invalid state and make them backoff, then I am safe. For example, we do not zero out the PMD, we take the pte PTL, we do stuff, then instead of setting the PTEs to zero, we set it to a universal invalid state upon which no pagetable walker can take an action; an instance of that can be to set the PTE to a swap entry such that the fault handler ends up in do_swap_page() ->print_bad_pte(). So now we can take the PMD lock (in fact we don't need it since any pagetable walking is rendered useless) and populate the PMD to resume the new pagetable walking. Another *ridiculous* idea may be to remember the PGD we came from and nuke it (but I guess there is an alternate path for that in walk_pgd_range() and so on?)

Quoted 2 lines
#5 lore raw
Quoted 26 lines
Quoted 8 lines

Thinking about it, I am also not sure if most other code can deal with temporary pmd_none(). These don't necessarily take the PMD lock, because "why would they" right now.

See walk_pmd_range() as one example, if it spots pmd_none() it assumes "there really is nothing" without checking the PMD lock.

Quoted 8 lines

As a more concrete example, assume someone calls MADV_DONTNEED and we end up in zap_pmd_range(). If we assume "pmd_none() == really nothing" we'll skip that entry without getting the PMD lock involved. That would mean that you would be breaking MADV_DONTNEED if you managed to collapse or not -- memory would not get discarded.

This is a real problem with anonymous memory.

Yes, I thought of different locking fashions but the problem seems to be that any pagetable walker will choose an action path according to the value it sees.

Quoted 5 lines

Unless I am missing something it's all very tricky and there might be a lot of such code that assumes "if I hold a mmap lock / VMA lock in read mode, pmd_none() means there is nothing even without holding the PMD lock when checking".

Quoted 5 lines

Yes, I was betting on the fact that, if the code assumes that pmd_none() means there is nothing, eventually when it will take the PMD lock to write to it, it will check whether
the PMD changed, and back off. I wasn't aware of the MADV_DONTNEED thingy, thanks.

Note that this is just the tip of the iceberg. Most page table walkers that deal with anonymous memory have the same requirement.

Quoted 8 lines
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

I recall that for shmem that's "easier", because we don't have to reinstall a PMD immediately, we cna be sure that the page table is kept empty/unmodified, ...

Quoted 12 lines

All in all, the general solution seems to be that, if I can take all
pagetable walkers into an invalid state and make them backoff, then I am
safe.
For example, we do not zero out the PMD, we take the pte PTL, we do> stuff, then instead of setting the PTEs to zero, we set it to a universal invalid state upon which no pagetable walker can take an action; an
instance of that can be to set the PTE to a swap entry such that the fault
handler ends up in do_swap_page() ->print_bad_pte(). So now we can take
the PMD lock (in fact we don't need it since any pagetable walking
is rendered useless) and populate the PMD to resume the new pagetable
walking. Another *ridiculous* idea may be to remember the PGD we
came from and nuke it (but I guess there is an alternate path for that
in walk_pgd_range() and so on?)

What might work is introducing a PMD marker (note: we don't have PMD markers yet) for that purpose. Likely, the PMD marker may only be set while the PMD lock is being held, and we must not drop the PMD lock temporarily (otherwise people will spin on the value by repeadetly (un)locking the PMD lock, which is stupid).

Then you have to make sure that each and every page table walker handles that properly.

Then, there is the problem with holding the PMD lock for too long as I mentioned.

Last but not least, there are more issues that I haven't even described before (putting aside the other issue):

Our page table walkers can handle the transitions:

PMD leaf -> PMD none
* concurrent zap / MADV_DONTNEED / !anon PMD split

PMD leaf -> PTE table
* concurrent anon PMD split
* concurrent zap / MADV_DONTNEED / !anon PMD split + PTE table allocation

PTE table (empty) -> PMD none
* concurrent page table reclaim, part of collapsing file THPs
* collapse_pte_mapped_thp()
* retract_page_tables()

I think they *cannot* tolerate the transition *properly*:

PTE table (non-empty) -> PMD leaf
* what you want do do ;)

-> Observe how we skip to the next PMD in all page table walkers / give up if pte_offset_map_lock() and friends fail! I even think there are more issues hiding there with pte_offset_map_ro_nolock().

Of course, on top of all of this, you should net significantly degrade the ordinary page table walker performance ...

I don't want to discourage you, but it's all extremely complicated.

Signature · 3 lines
Cheers,

David / dhildenb
author
#6 lore raw
Quoted 88 lines · David Hildenbrand
Quoted 26 lines
Quoted 8 lines

Thinking about it, I am also not sure if most other code can deal with temporary pmd_none(). These don't necessarily take the PMD lock, because "why would they" right now.

See walk_pmd_range() as one example, if it spots pmd_none() it assumes "there really is nothing" without checking the PMD lock.

Quoted 8 lines

As a more concrete example, assume someone calls MADV_DONTNEED and we end up in zap_pmd_range(). If we assume "pmd_none() == really nothing" we'll skip that entry without getting the PMD lock involved. That would mean that you would be breaking MADV_DONTNEED if you managed to collapse or not -- memory would not get discarded.

This is a real problem with anonymous memory.

Yes, I thought of different locking fashions but the problem seems to be that any pagetable walker will choose an action path according to the value it sees.

Quoted 5 lines

Unless I am missing something it's all very tricky and there might be a lot of such code that assumes "if I hold a mmap lock / VMA lock in read mode, pmd_none() means there is nothing even without holding the PMD lock when checking".

Quoted 5 lines

Yes, I was betting on the fact that, if the code assumes that pmd_none() means there is nothing, eventually when it will take the PMD lock to write to it, it will check whether
the PMD changed, and back off. I wasn't aware of the MADV_DONTNEED thingy, thanks.

Note that this is just the tip of the iceberg. Most page table walkers that deal with anonymous memory have the same requirement.

Quoted 8 lines
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

I recall that for shmem that's "easier", because we don't have to reinstall a PMD immediately, we cna be sure that the page table is kept empty/unmodified, ...

Quoted 4 lines

All in all, the general solution seems to be that, if I can take all pagetable walkers into an invalid state and make them backoff, then I am safe.
For example, we do not zero out the PMD, we take the pte PTL, we do>

stuff, then instead of setting the PTEs to zero, we set it to a universal

Quoted 8 lines

invalid state upon which no pagetable walker can take an action; an instance of that can be to set the PTE to a swap entry such that the fault handler ends up in do_swap_page() ->print_bad_pte(). So now we can take the PMD lock (in fact we don't need it since any pagetable walking is rendered useless) and populate the PMD to resume the new pagetable walking. Another *ridiculous* idea may be to remember the PGD we came from and nuke it (but I guess there is an alternate path for that in walk_pgd_range() and so on?)

What might work is introducing a PMD marker (note: we don't have PMD markers yet) for that purpose. Likely, the PMD marker may only be set while the PMD lock is being held, and we must not drop the PMD lock temporarily (otherwise people will spin on the value by repeadetly (un)locking the PMD lock, which is stupid).

Then you have to make sure that each and every page table walker handles that properly.

Then, there is the problem with holding the PMD lock for too long as I mentioned.

Last but not least, there are more issues that I haven't even described before (putting aside the other issue):

Our page table walkers can handle the transitions:

PMD leaf -> PMD none
* concurrent zap / MADV_DONTNEED / !anon PMD split

PMD leaf -> PTE table
* concurrent anon PMD split
* concurrent zap / MADV_DONTNEED / !anon PMD split + PTE table allocation

PTE table (empty) -> PMD none
* concurrent page table reclaim, part of collapsing file THPs
 * collapse_pte_mapped_thp()
 * retract_page_tables()

I think they *cannot* tolerate the transition *properly*:

PTE table (non-empty) -> PMD leaf
* what you want do do ;)

Quoted 9 lines

-> Observe how we skip to the next PMD in all page table walkers /
give up if pte_offset_map_lock() and friends fail! I even think there are more issues hiding there with pte_offset_map_ro_nolock().

Of course, on top of all of this, you should net significantly degrade the ordinary page table walker performance ...

I don't want to discourage you, but it's all extremely complicated.

Thanks for the detailed reply!

author
#7 lore raw

Re: [QUESTION] anon_vma lock in khugepaged

In reply to a message not in the archive
Quoted 5 lines · Dev Jain

Hi, I was looking at khugepaged code and I cannot figure out what will the problem be if we take the mmap lock in read mode. Shouldn't just taking the PMD lock, then PTL, then unlocking PTL, then unlocking PMD, solve any races with page table walkers?

Similar questions:

1. Why do we need anon_vma_lock_write() in collapse_huge_page()? AFAIK we need to walk anon_vma's either when we are forking or when we are unmapping a folio and need to find all VMAs mapping it; the former path takes the mmap_write_lock() and so we have no problem, and for the latter, if we just had anon_vma_lock_read(), then it may happen that kswapd isolates folio from LRU, and traverses rmap and swaps the folio out and khugepaged fails in folio_isolate_lru(), but then that is not a fatal problem but just a performance degradation due to a race (wherein the entire code is racy anyways). What am I missing?

2. In what all scenarios does rmap come into play? Fork, swapping out, any other I am missing?

3. Please confirm the correctness: In stark contrast to page migration, we do not need to do rmap walk and nuke all PTEs referencing the folio, because for anon non-shmem folios, the only way the folio can be shared is forking, and, if that is the case, folio_put() will not release the folio in __collapse_huge_page_copy_succeeded() -> free_page_and_swap_cache(), so the old folio is still there and child processes can read from it. Page migration requires that we are able
to deallocate the old folios.

#8 lore raw

Re: [QUESTION] anon_vma lock in khugepaged

Quoted 17 lines · Dev Jain
Quoted 5 lines · Dev Jain

Hi, I was looking at khugepaged code and I cannot figure out what will the problem be if we take the mmap lock in read mode. Shouldn't just taking the PMD lock, then PTL, then unlocking PTL, then unlocking PMD, solve any races with page table walkers?

Similar questions:

1. Why do we need anon_vma_lock_write() in collapse_huge_page()? AFAIK we need to walk anon_vma's either when we are forking or when we are unmapping a folio and need to find all VMAs mapping it; the former path takes the mmap_write_lock() and so we have no problem, and for the latter, if we just had anon_vma_lock_read(), then it may happen that kswapd isolates folio from LRU, and traverses rmap and swaps the folio out and khugepaged fails in folio_isolate_lru(), but then that is not a fatal problem but just a performance degradation due to a race (wherein the entire code is racy anyways). What am I missing?

Quoted 8 lines

2. In what all scenarios does rmap come into play? Fork, swapping out, any other I am missing?

3. Please confirm the correctness: In stark contrast to page migration, we do not need to do rmap walk and nuke all PTEs referencing the folio, because for anon non-shmem folios, the only way the folio can be shared is forking, and, if that is the case, folio_put() will not release the folio in __collapse_huge_page_copy_succeeded() -> free_page_and_swap_cache(), so the old folio is still there and child processes can read from it. Page migration requires that we are able
to deallocate the old folios.

Without going too much into detail: I think one reason is that try_to_unmap() and friends should not fail (not finding all PTEs/PMDs) simply because there is concurrent collapse going on.

Observe how try_to_unmap() and friends take the folio lock first, and how collapse tries taking the folio locks only after it already invalidated the PMDP.

Likely there are other reasons, but this is the "obvious" one I can think of.

We really try preventing *any* concurrent page table walkers, and that requires the mmap lock+vma lock in write + rmap lock in write.

Signature · 3 lines
Cheers,

David / dhildenb