synchronously scan and reclaim empty user PTE pages

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

If not, would it make sense to have a separate function that returns the pmdval and we won't have to update each and every callsite?

Hi David,

Quoted 5 lines · David Hildenbrand

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 2 lines

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

In addition, retract_page_tables() and reclaim_pgtables_pmd_entry() also used the pmdval returned by pte_offset_map_nolock().

Quoted 7 lines

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

If not, would it make sense to have a separate function that returns the pmdval and we won't have to update each and every callsite?

pte_offset_map_nolock() had already obtained the pmdval previously, just hadn't returned it. And updating those callsite is simple, so I think there may not be a need to add a separate function.

Quoted 8 lines · Qi Zheng

Hi David,

Quoted 5 lines · David Hildenbrand

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 5 lines

Quoted 2 lines

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

In addition, retract_page_tables() and reclaim_pgtables_pmd_entry() also used the pmdval returned by pte_offset_map_nolock().

Right, and I am questioning if only touching these two is sufficient, and how we can make it clearer when someone actually has to recheck the PMD.

Quoted 5 lines

Quoted 5 lines

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

Quoted 6 lines

Quoted 2 lines

If not, would it make sense to have a separate function that returns the pmdval and we won't have to update each and every callsite?

pte_offset_map_nolock() had already obtained the pmdval previously, just hadn't returned it. And updating those callsite is simple, so I think there may not be a need to add a separate function.

Let me ask this way: why is retract_page_tables() and reclaim_pgtables_pmd_entry() different to the other ones, and how would someone using pte_offset_map_nolock() know what's to do here?

IIUC, we must check the PMDVAL after taking the PTL in case

(a) we want to modify the page table to turn pte_none() entries to !pte_none(). Because it could be that the page table was removed and now is all pte_none()

(b) we want to remove the page table ourselves and want to check if it has already been removed.

Is that it?

So my thinking is if another function variant can make that clearer.

Hi David,

Quoted 27 lines · David Hildenbrand

Quoted 8 lines · Qi Zheng

Hi David,

Quoted 5 lines · David Hildenbrand

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 5 lines

Quoted 2 lines

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

In addition, retract_page_tables() and reclaim_pgtables_pmd_entry() also used the pmdval returned by pte_offset_map_nolock().

Right, and I am questioning if only touching these two is sufficient, and how we can make it clearer when someone actually has to recheck the PMD.

Quoted 8 lines

Quoted 7 lines

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

If not, would it make sense to have a separate function that returns the pmdval and we won't have to update each and every callsite?

Quoted 7 lines

Quoted 3 lines

pte_offset_map_nolock() had already obtained the pmdval previously, just hadn't returned it. And updating those callsite is simple, so I think there may not be a need to add a separate function.

Let me ask this way: why is retract_page_tables() and reclaim_pgtables_pmd_entry() different to the other ones, and how would someone using pte_offset_map_nolock() know what's to do here?

If we acuqire the PTL (PTE or PMD lock) after calling pte_offset_map_nolock(), it means we may be modifying the corresponding pte or pmd entry. In that case, we need to perform a pmd_same() check after holding the PTL, just like in pte_offset_map_lock(), to prevent the possibility of the PTE page being reclaimed at that time.

If we call pte_offset_map_nolock() and do not need to acquire the PTL afterwards, it means we are only reading the PTE page. In this case, the rcu_read_lock() in pte_offset_map_nolock() will ensure that the PTE page cannot be reclaimed.

Quoted 10 lines

IIUC, we must check the PMDVAL after taking the PTL in case

(a) we want to modify the page table to turn pte_none() entries to !pte_none(). Because it could be that the page table was removed and now is all pte_none()

(b) we want to remove the page table ourselves and want to check if it has already been removed.

Quoted 1 line

Is that it?

Yes.

Quoted 2 lines

So my thinking is if another function variant can make that clearer.

OK, how about naming it pte_offset_map_before_lock?

Quoted 38 lines · Qi Zheng

Hi David,

Quoted 27 lines · David Hildenbrand

Quoted 8 lines · Qi Zheng

Hi David,

Quoted 5 lines · David Hildenbrand

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 5 lines

Quoted 2 lines

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

In addition, retract_page_tables() and reclaim_pgtables_pmd_entry() also used the pmdval returned by pte_offset_map_nolock().

Right, and I am questioning if only touching these two is sufficient, and how we can make it clearer when someone actually has to recheck the PMD.

Quoted 8 lines

Quoted 7 lines

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

If not, would it make sense to have a separate function that returns the pmdval and we won't have to update each and every callsite?

Quoted 7 lines

Quoted 3 lines

pte_offset_map_nolock() had already obtained the pmdval previously, just hadn't returned it. And updating those callsite is simple, so I think there may not be a need to add a separate function.

Let me ask this way: why is retract_page_tables() and reclaim_pgtables_pmd_entry() different to the other ones, and how would someone using pte_offset_map_nolock() know what's to do here?

Quoted 5 lines

If we acuqire the PTL (PTE or PMD lock) after calling pte_offset_map_nolock(), it means we may be modifying the corresponding pte or pmd entry. In that case, we need to perform a pmd_same() check after holding the PTL, just like in pte_offset_map_lock(), to prevent the possibility of the PTE page being reclaimed at that time.

Okay, what I thought.

Quoted 16 lines

If we call pte_offset_map_nolock() and do not need to acquire the PTL afterwards, it means we are only reading the PTE page. In this case, the rcu_read_lock() in pte_offset_map_nolock() will ensure that the PTE page cannot be reclaimed.

Quoted 10 lines

IIUC, we must check the PMDVAL after taking the PTL in case

(a) we want to modify the page table to turn pte_none() entries to !pte_none(). Because it could be that the page table was removed and now is all pte_none()

(b) we want to remove the page table ourselves and want to check if it has already been removed.

Quoted 8 lines

Quoted 1 line

Is that it?

Yes.

Quoted 2 lines

So my thinking is if another function variant can make that clearer.

OK, how about naming it pte_offset_map_before_lock?

That's the issue with some of the code: for example in filemap_fault_recheck_pte_none() we'll call pte_offset_map_nolock() and conditionally take the PTL. But we won't be modifying the pages tables.

Maybe something like:

pte_offset_map_readonly_nolock()

and

pte_offset_map_maywrite_nolock()

The latter would require you to pass the PMD pointer such that you have to really mess up to ignore what to do with it (check PMD same or not check PMD same if you really know what you are douing).

The first would not take a PMD pointer at all, because there is no need to.

Hi David,

Quoted 87 lines · David Hildenbrand

Quoted 40 lines · Qi Zheng

Hi David,

Quoted 28 lines · David Hildenbrand

Quoted 8 lines · Qi Zheng

Hi David,

Quoted 5 lines · David Hildenbrand

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 5 lines

Quoted 2 lines

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

In addition, retract_page_tables() and reclaim_pgtables_pmd_entry() also used the pmdval returned by pte_offset_map_nolock().

Right, and I am questioning if only touching these two is sufficient, and how we can make it clearer when someone actually has to recheck the PMD.

Quoted 9 lines

Quoted 8 lines

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

If not, would it make sense to have a separate function that returns the
pmdval and we won't have to update each and every callsite?

Quoted 8 lines

Quoted 4 lines

pte_offset_map_nolock() had already obtained the pmdval previously, just
hadn't returned it. And updating those callsite is simple, so I think there may not be a need to add a separate function.

Let me ask this way: why is retract_page_tables() and reclaim_pgtables_pmd_entry() different to the other ones, and how would someone using pte_offset_map_nolock() know what's to do here?

Quoted 5 lines

If we acuqire the PTL (PTE or PMD lock) after calling pte_offset_map_nolock(), it means we may be modifying the corresponding pte or pmd entry. In that case, we need to perform a pmd_same() check after holding the PTL, just like in pte_offset_map_lock(), to prevent the possibility of the PTE page being reclaimed at that time.

Okay, what I thought.

Quoted 17 lines

If we call pte_offset_map_nolock() and do not need to acquire the PTL afterwards, it means we are only reading the PTE page. In this case, the rcu_read_lock() in pte_offset_map_nolock() will ensure that the PTE page cannot be reclaimed.

Quoted 11 lines

IIUC, we must check the PMDVAL after taking the PTL in case

(a) we want to modify the page table to turn pte_none() entries to !pte_none(). Because it could be that the page table was
removed and
      now is all pte_none()

(b) we want to remove the page table ourselves and want to check if it has already been removed.

Quoted 8 lines

Quoted 1 line

Is that it?

Yes.

Quoted 2 lines

So my thinking is if another function variant can make that clearer.

OK, how about naming it pte_offset_map_before_lock?

That's the issue with some of the code: for example in filemap_fault_recheck_pte_none() we'll call pte_offset_map_nolock() and conditionally take the PTL. But we won't be modifying the pages tables.

Maybe something like:

pte_offset_map_readonly_nolock()

and

pte_offset_map_maywrite_nolock()

Quoted 5 lines

The latter would require you to pass the PMD pointer such that you have to really mess up to ignore what to do with it (check PMD same or not check PMD same if you really know what you are douing).

The first would not take a PMD pointer at all, because there is no need to.

These two function names LGTM. Will do in the next version.

Quoted 94 lines · Qi Zheng

Hi David,

Quoted 91 lines · David Hildenbrand

Quoted 40 lines · Qi Zheng

Hi David,

Quoted 28 lines · David Hildenbrand

Quoted 8 lines · Qi Zheng

Hi David,

Quoted 5 lines · David Hildenbrand

Quoted 3 lines · Qi Zheng

Make pte_offset_map_nolock() return pmdval so that we can recheck the *pmd once the lock is taken. This is a preparation for freeing empty PTE pages, no functional changes are expected.

Quoted 5 lines

Quoted 2 lines

Skimming the patches, only patch #4 updates one of the callsites (collapse_pte_mapped_thp).

In addition, retract_page_tables() and reclaim_pgtables_pmd_entry() also used the pmdval returned by pte_offset_map_nolock().

Right, and I am questioning if only touching these two is sufficient, and how we can make it clearer when someone actually has to recheck the PMD.

Quoted 9 lines

Quoted 8 lines

Wouldn't we have to recheck if the PMD val changed in more cases after taking the PTL?

If not, would it make sense to have a separate function that returns the
pmdval and we won't have to update each and every callsite?

Quoted 8 lines

Quoted 4 lines

pte_offset_map_nolock() had already obtained the pmdval previously, just
hadn't returned it. And updating those callsite is simple, so I think there may not be a need to add a separate function.

Let me ask this way: why is retract_page_tables() and reclaim_pgtables_pmd_entry() different to the other ones, and how would someone using pte_offset_map_nolock() know what's to do here?

Quoted 5 lines

If we acuqire the PTL (PTE or PMD lock) after calling pte_offset_map_nolock(), it means we may be modifying the corresponding pte or pmd entry. In that case, we need to perform a pmd_same() check after holding the PTL, just like in pte_offset_map_lock(), to prevent the possibility of the PTE page being reclaimed at that time.

Okay, what I thought.

Quoted 17 lines

If we call pte_offset_map_nolock() and do not need to acquire the PTL afterwards, it means we are only reading the PTE page. In this case, the rcu_read_lock() in pte_offset_map_nolock() will ensure that the PTE page cannot be reclaimed.

Quoted 11 lines

IIUC, we must check the PMDVAL after taking the PTL in case

(a) we want to modify the page table to turn pte_none() entries to !pte_none(). Because it could be that the page table was removed and
       now is all pte_none()

(b) we want to remove the page table ourselves and want to check if it has already been removed.

Quoted 8 lines

Quoted 1 line

Is that it?

Yes.

Quoted 2 lines

So my thinking is if another function variant can make that clearer.

OK, how about naming it pte_offset_map_before_lock?

That's the issue with some of the code: for example in filemap_fault_recheck_pte_none() we'll call pte_offset_map_nolock() and conditionally take the PTL. But we won't be modifying the pages tables.

Maybe something like:

pte_offset_map_readonly_nolock()

and

pte_offset_map_maywrite_nolock()

The latter would require you to pass the PMD pointer such that you have to really mess up to ignore what to do with it (check PMD same or not check PMD same if you really know what you are douing).

Quoted 3 lines

Quoted 1 line

The first would not take a PMD pointer at all, because there is no need to.

These two function names LGTM. Will do in the next version.

That is probably something you can send as a separate patch independent of this full series.

Then we might also get more review+thoughts from other folks!

This configuration variable will be used to build the code needed to free empty user page table pages.

This feature is not available on all architectures yet, so ARCH_SUPPORTS_PT_RECLAIM is needed. We can remove it once all architectures support this feature.

Quoted 6 lines · Qi Zheng

This configuration variable will be used to build the code needed to free empty user page table pages.

This feature is not available on all architectures yet, so ARCH_SUPPORTS_PT_RECLAIM is needed. We can remove it once all architectures support this feature.

Please squash this into #4

Now in order to pursue high performance, applications mostly use some high-performance user-mode memory allocators, such as jemalloc or tcmalloc. These memory allocators use madvise(MADV_DONTNEED or MADV_FREE) to release physical memory, but neither MADV_DONTNEED nor MADV_FREE will release page table memory, which may cause huge page table memory usage.

The following are a memory usage snapshot of one process which actually happened on our server:

         VIRT:  55t
         RES:   590g
         VmPTE: 110g

In this case, most of the page table entries are empty. For such a PTE page where all entries are empty, we can actually free it back to the system for others to use.

As a first step, this commit attempts to synchronously free the empty PTE pages in zap_page_range_single() (MADV_DONTNEED etc will invoke this). In order to reduce overhead, we only handle the cases with a high probability of generating empty PTE pages, and other cases will be filtered out, such as:

Quoted 17 lines · Qi Zheng

Now in order to pursue high performance, applications mostly use some high-performance user-mode memory allocators, such as jemalloc or tcmalloc. These memory allocators use madvise(MADV_DONTNEED or MADV_FREE) to release physical memory, but neither MADV_DONTNEED nor MADV_FREE will release page table memory, which may cause huge page table memory usage.

The following are a memory usage snapshot of one process which actually happened on our server:

         VIRT:  55t
         RES:   590g
         VmPTE: 110g

In this case, most of the page table entries are empty. For such a PTE page where all entries are empty, we can actually free it back to the system for others to use.

Quoted 5 lines

As a first step, this commit attempts to synchronously free the empty PTE pages in zap_page_range_single() (MADV_DONTNEED etc will invoke this). In order to reduce overhead, we only handle the cases with a high probability of generating empty PTE pages, and other cases will be filtered out, such as:

It doesn't make particular sense during munmap() where we will just remove the page tables manually directly afterwards. We should limit it to the !munmap case -- in particular MADV_DONTNEED.

To minimze the added overhead, I further suggest to only try reclaim asynchronously if we know that likely all ptes will be none, that is,

when we just zapped *all* ptes of a PTE page table -- our range spans the complete PTE page table.

Just imagine someone zaps a single PTE, we really don't want to start scanning page tables and involve an (rather expensive) walk_page_range just to find out that there is still something mapped.

Last but not least, would there be a way to avoid the walk_page_range() and simply trigger it from zap_pte_range(), possibly still while holding the PTE table lock?

We might have to trylock the PMD, but that should be doable.

Hi David,

Quoted 25 lines · Qi Zheng

Quoted 17 lines

Now in order to pursue high performance, applications mostly use some high-performance user-mode memory allocators, such as jemalloc or tcmalloc. These memory allocators use madvise(MADV_DONTNEED or MADV_FREE) to release physical memory, but neither MADV_DONTNEED nor MADV_FREE will release page table memory, which may cause huge page table memory usage.

The following are a memory usage snapshot of one process which actually happened on our server:

         VIRT:  55t
         RES:   590g
         VmPTE: 110g

In this case, most of the page table entries are empty. For such a PTE page where all entries are empty, we can actually free it back to the system for others to use.

Quoted 6 lines

As a first step, this commit attempts to synchronously free the empty PTE pages in zap_page_range_single() (MADV_DONTNEED etc will invoke this). In order to reduce overhead, we only handle the cases with a high probability
of generating empty PTE pages, and other cases will be filtered out, such as:

Quoted 3 lines

It doesn't make particular sense during munmap() where we will just remove the page tables manually directly afterwards. We should limit it to the !munmap case -- in particular MADV_DONTNEED.

munmap directly calls unmap_single_vma() instead of zap_page_range_single(), so the munmap case has already been excluded here. On the other hand, if we try to reclaim in zap_pte_range(), we need to identify the munmap case.

Of course, we could just modify the MADV_DONTNEED case instead of all the callers of zap_page_range_single(), perhaps we could add a new parameter to identify the MADV_DONTNEED case?

Quoted 4 lines

To minimze the added overhead, I further suggest to only try reclaim asynchronously if we know that likely all ptes will be none, that is,

asynchronously? What you probably mean to say is synchronously, right?

Quoted 6 lines

when we just zapped *all* ptes of a PTE page table -- our range spans the complete PTE page table.

Just imagine someone zaps a single PTE, we really don't want to start scanning page tables and involve an (rather expensive) walk_page_range just to find out that there is still something mapped.

In the munmap path, we first execute unmap and then reclaim the page tables:

unmap_vmas
free_pgtables

Therefore, I think doing something similar in zap_page_range_single() would be more consistent:

unmap_single_vma
try_to_reclaim_pgtables

And I think that the main overhead should be in flushing TLB and freeing the pages. Of course, I will do some performance testing to see the actual impact.

Quoted 1 line

Quoted 3 lines

Last but not least, would there be a way to avoid the walk_page_range() and simply trigger it from zap_pte_range(), possibly still while holding the PTE table lock?

I've tried doing it that way before, but ultimately I did not choose to do it that way because of the following reasons:

1. need to identify the munmap case

2. trying to record the count of pte_none() within the original zap_pte_range() loop is not very convenient. The most convenient approach is still to loop 512 times to scan the PTE page.

3. still need to release the pte lock, and then re-acquire the pmd lock and pte lock.

Quoted 2 lines · Qi Zheng

Hi David,

Really sorry for the slow replies, I'm struggling with a mixture of public holidays, holiday and too many different discussions (well, and some stuff I have to finish myself).

Quoted 30 lines · David Hildenbrand

Quoted 25 lines · Qi Zheng

Quoted 17 lines

Now in order to pursue high performance, applications mostly use some high-performance user-mode memory allocators, such as jemalloc or tcmalloc. These memory allocators use madvise(MADV_DONTNEED or MADV_FREE) to release physical memory, but neither MADV_DONTNEED nor MADV_FREE will release page table memory, which may cause huge page table memory usage.

The following are a memory usage snapshot of one process which actually happened on our server:

          VIRT:  55t
          RES:   590g
          VmPTE: 110g

In this case, most of the page table entries are empty. For such a PTE page where all entries are empty, we can actually free it back to the system for others to use.

Quoted 6 lines

As a first step, this commit attempts to synchronously free the empty PTE pages in zap_page_range_single() (MADV_DONTNEED etc will invoke this). In order to reduce overhead, we only handle the cases with a high probability
of generating empty PTE pages, and other cases will be filtered out, such as:

Quoted 3 lines

It doesn't make particular sense during munmap() where we will just remove the page tables manually directly afterwards. We should limit it to the !munmap case -- in particular MADV_DONTNEED.

Quoted 8 lines

munmap directly calls unmap_single_vma() instead of zap_page_range_single(), so the munmap case has already been excluded here. On the other hand, if we try to reclaim in zap_pte_range(), we need to identify the munmap case.

Of course, we could just modify the MADV_DONTNEED case instead of all the callers of zap_page_range_single(), perhaps we could add a new parameter to identify the MADV_DONTNEED case?

See below, zap_details might come in handy.

Quoted 31 lines

Quoted 4 lines

To minimze the added overhead, I further suggest to only try reclaim asynchronously if we know that likely all ptes will be none, that is,

asynchronously? What you probably mean to say is synchronously, right?

Quoted 6 lines

when we just zapped *all* ptes of a PTE page table -- our range spans the complete PTE page table.

Just imagine someone zaps a single PTE, we really don't want to start scanning page tables and involve an (rather expensive) walk_page_range just to find out that there is still something mapped.

In the munmap path, we first execute unmap and then reclaim the page tables:

unmap_vmas
free_pgtables

Therefore, I think doing something similar in zap_page_range_single() would be more consistent:

unmap_single_vma
try_to_reclaim_pgtables

And I think that the main overhead should be in flushing TLB and freeing the pages. Of course, I will do some performance testing to see the actual impact.

Quoted 1 line

Quoted 6 lines

Quoted 3 lines

Last but not least, would there be a way to avoid the walk_page_range() and simply trigger it from zap_pte_range(), possibly still while holding the PTE table lock?

I've tried doing it that way before, but ultimately I did not choose to do it that way because of the following reasons:

I think we really should avoid another page table walk if possible.

Quoted 2 lines

1. need to identify the munmap case

We already have "struct zap_details". Maybe we can extend that to specify what our intention are (either where we come from or whether we want to try ripping out apge tables directly).

Quoted 3 lines

2. trying to record the count of pte_none() within the original zap_pte_range() loop is not very convenient. The most convenient approach is still to loop 512 times to scan the PTE page.

Right, the code might need some reshuffling. As we might temporary drop the PTL (break case), fully relying on everything being pte_none() doesn't always work.

We could either handle it in zap_pmd_range(), after we processed a full PMD range. zap_pmd_range() knows for sure whether the full PMD range was covered, even if multiple zap_pte_range() calls were required.

Or we could indicate to zap_pte_range() the original range. Or we could make zap_pte_range() simply handle the retrying itself, and not get called multiple times for a single PMD range.

So the key points are:

(a) zap_pmd_range() should know for sure whether the full range is covered by the zap.
(b) zap_pte_range() knows whether it left any entries being (IOW, it n never ran into the "!should_zap_folio" case)
(c) we know whether we temporarily had to drop the PTL and someone might have converted pte_none() to something else.

Teaching zap_pte_range() to handle a full within-PMD range itself sounds cleanest.

Then we can handle it fully in zap_pte_range():

(a) if we had to leave entries behind (!pte_none()), no need to try ripping out the page table.

(b) if we didn't have to drop the PTL, we can remove the page table without even re-verifying whether the entries are pte_none(). We

    know they are. If we had to drop the PTL, we have to re-verify at least the PTEs that were not zapped in the last iteration.

So there is the chance to avoid pte_none() checks completely, or minimze them if we had to drop the PTL.

Anything I am missing? Please let me know if anything is unclear.

Reworking the retry logic for zap_pte_range(), to be called for a single PMD only once is likely the first step.

Quoted 3 lines

3. still need to release the pte lock, and then re-acquire the pmd lock and pte lock.

Yes, if try-locking the PMD fails.

Quoted 3 lines

(b) if we didn't have to drop the PTL, we can remove the page table without even re-verifying whether the entries are pte_none(). We

If we want to remove the PTE page, we must hold the pmd lock (for clearing pmd entry). To prevent ABBA deadlock, we must first release the pte lock and then re-acquire the pmd lock + pte lock. Right? If so, then rechecking pte_none() is unavoidable. Unless we hold the pmd lock + pte lock in advance to execute the original code loop.

Quoted 9 lines

Quoted 3 lines

(b) if we didn't have to drop the PTL, we can remove the page table without even re-verifying whether the entries are pte_none(). We

If we want to remove the PTE page, we must hold the pmd lock (for clearing pmd entry). To prevent ABBA deadlock, we must first release the pte lock and then re-acquire the pmd lock + pte lock. Right? If so, then rechecking pte_none() is unavoidable. Unless we hold the pmd lock + pte lock in advance to execute the original code loop.

Try-locking the PMD should work, and succeed in many cases, right? And if that fails, we could fallback to what you describe.

Changes in RFC v2:
- fix compilation errors in [RFC PATCH 5/7] and [RFC PATCH 7/7] reproted by kernel test robot
- use pte_offset_map_nolock() + pmd_same() instead of check_pmd_still_valid() in retract_page_tables() (in [RFC PATCH 4/7])
- rebase onto the next-20240805

Hi all,

Previously, we tried to use a completely asynchronous method to reclaim empty user PTE pages [1]. After discussing with David Hildenbrand, we decided to implement synchronous reclaimation in the case of madvise(MADV_DONTNEED) as the first step.

So this series aims to synchronously scan and reclaim empty user PTE pages in zap_page_range_single() (madvise(MADV_DONTNEED) etc will invoke this). In zap_page_range_single(), mmu_gather is used to perform batch tlb flushing and page freeing operations. Therefore, if we want to free the empty PTE page in this path, the most natural way is to add it to mmu_gather as well. There are two problems that need to be solved here:

1. Now, if CONFIG_MMU_GATHER_RCU_TABLE_FREE is selected, mmu_gather will free page table pages by semi RCU:

- batch table freeing: asynchronous free by RCU
- single table freeing: IPI + synchronous free

But this is not enough to free the empty PTE page table pages in paths other that munmap and exit_mmap path, because IPI cannot be synchronized with rcu_read_lock() in pte_offset_map{_lock}(). So we should let single table also be freed by RCU like batch table freeing.

2. When we use mmu_gather to batch flush tlb and free PTE pages, the TLB is not flushed before pmd lock is unlocked. This may result in the following two situations:

1) Userland can trigger page fault and fill a huge page, which will cause the existence of small size TLB and huge TLB for the same address.

2) Userland can also trigger page fault and fill a PTE page, which will cause the existence of two small size TLBs, but the PTE page they map are different.

For case 1), according to Intel's TLB Application note (317080), some CPUs of x86 do not allow it:

```
If software modifies the paging structures so that the page size used for a 4-KByte range of linear addresses changes, the TLBs may subsequently contain both ordinary and large-page translations for the address range.12 A reference to a linear address in the address range may use either translation. Which of the two translations is used may vary from one execution to another and the choice may be implementation-specific.

Software wishing to prevent this uncertainty should not write to a paging- structure entry in a way that would change, for any linear address, both the page size and either the page frame or attributes. It can instead use the following algorithm: first mark the relevant paging-structure entry (e.g., PDE) not present; then invalidate any translations for the affected linear addresses (see Section 5.2); and then modify the relevant paging-structure entry to mark it present and establish translation(s) for the new page size. ```

We can also learn more information from the comments above pmdp_invalidate() in __split_huge_pmd_locked().

For case 2), we can see from the comments above ptep_clear_flush() in wp_page_copy() that this situation is also not allowed. Even without this patch series, madvise(MADV_DONTNEED) can also cause this situation:

CPU 0 CPU 1

madvise (MADV_DONTNEED)
--> clear pte entry
pte_unmap_unlock
touch and tlb miss
--> set pte entry
mmu_gather flush tlb

But strangely, I didn't see any relevant fix code, maybe I missed something, or is this guaranteed by userland?

Anyway, this series defines the following two functions to be implemented by the architecture. If the architecture does not allow the above two situations, then define these two functions to flush the tlb before set_pmd_at().

- arch_flush_tlb_before_set_huge_page
- arch_flush_tlb_before_set_pte_page

As a first step, we supported this feature on x86_64 and selectd the newly introduced CONFIG_ARCH_SUPPORTS_PT_RECLAIM.

In order to reduce overhead, we only handle the cases with a high probability of generating empty PTE pages, and other cases will be filtered out, such as:

- hugetlb vma (unsuitable)
- userfaultfd_wp vma (may reinstall the pte entry)
- writable private file mapping case (COW-ed anon page is not zapped)
- etc

For userfaultfd_wp and writable private file mapping cases (and MADV_FREE case, of course), consider scanning and freeing empty PTE pages asynchronously in the future.

This series is based on next-20240805.

Comments and suggestions are welcome!

Thanks,
Qi

[1]. https://lore.kernel.org/lkml/[email protected]/

Qi Zheng (7):
mm: pgtable: make pte_offset_map_nolock() return pmdval
mm: introduce CONFIG_PT_RECLAIM
mm: pass address information to pmd_install()
mm: pgtable: try to reclaim empty PTE pages in zap_page_range_single()
x86: mm: free page table pages by RCU instead of semi RCU
x86: mm: define arch_flush_tlb_before_set_huge_page
x86: select ARCH_SUPPORTS_PT_RECLAIM if X86_64

  Documentation/mm/split_page_table_lock.rst |   3 +-
  arch/arm/mm/fault-armv.c                   |   2 +-
  arch/powerpc/mm/pgtable.c                  |   2 +-
  arch/x86/Kconfig                           |   1 +
  arch/x86/include/asm/pgtable.h             |   6 +
  arch/x86/include/asm/tlb.h                 |  19 +++
  arch/x86/kernel/paravirt.c                 |   7 ++
  arch/x86/mm/pgtable.c                      |  23 +++-
  include/linux/hugetlb.h                    |   2 +-
  include/linux/mm.h                         |  13 +-
  include/linux/pgtable.h                    |  14 +++
  mm/Kconfig                                 |  14 +++
  mm/Makefile                                |   1 +
  mm/debug_vm_pgtable.c                      |   2 +-
  mm/filemap.c                               |   4 +-
  mm/gup.c                                   |   2 +-
  mm/huge_memory.c                           |   3 +
  mm/internal.h                              |  17 ++-
  mm/khugepaged.c                            |  32 +++--
  mm/memory.c                                |  21 ++--
  mm/migrate_device.c                        |   2 +-
  mm/mmu_gather.c                            |   9 +-
  mm/mprotect.c                              |   8 +-
  mm/mremap.c                                |   4 +-
  mm/page_vma_mapped.c                       |   2 +-
  mm/pgtable-generic.c                       |  21 ++--
  mm/pt_reclaim.c                            | 131 +++++++++++++++++++++
  mm/userfaultfd.c                           |  10 +-
  mm/vmscan.c                                |   2 +-
  29 files changed, 321 insertions(+), 56 deletions(-)

create mode 100644 mm/pt_reclaim.c

2. When we use mmu_gather to batch flush tlb and free PTE pages, the TLB is not flushed before pmd lock is unlocked. This may result in the following two situations:

1) Userland can trigger page fault and fill a huge page, which will cause the existence of small size TLB and huge TLB for the same address.

2) Userland can also trigger page fault and fill a PTE page, which will cause the existence of two small size TLBs, but the PTE page they map are different.

For case 1), according to Intel's TLB Application note (317080), some CPUs of x86 do not allow it:

```
If software modifies the paging structures so that the page size used for a 4-KByte range of linear addresses changes, the TLBs may subsequently contain both ordinary and large-page translations for the address range.12 A reference to a linear address in the address range may use either translation. Which of the two translations is used may vary from one execution to another and the choice may be implementation-specific.

Software wishing to prevent this uncertainty should not write to a paging- structure entry in a way that would change, for any linear address, both the page size and either the page frame or attributes. It can instead use the following algorithm: first mark the relevant paging-structure entry (e.g., PDE) not present; then invalidate any translations for the affected linear addresses (see Section 5.2); and then modify the relevant paging-structure entry to mark it present and establish translation(s) for the new page size. ```

We can also learn more information from the comments above pmdp_invalidate() in __split_huge_pmd_locked().

For case 2), we can see from the comments above ptep_clear_flush() in wp_page_copy() that this situation is also not allowed. Even without this patch series, madvise(MADV_DONTNEED) can also cause this situation:

CPU 0 CPU 1

madvise (MADV_DONTNEED)
--> clear pte entry
pte_unmap_unlock
touch and tlb miss
--> set pte entry
mmu_gather flush tlb

But strangely, I didn't see any relevant fix code, maybe I missed something, or is this guaranteed by userland?

Anyway, this series defines the following two functions to be implemented by the architecture. If the architecture does not allow the above two situations, then define these two functions to flush the tlb before set_pmd_at().

- arch_flush_tlb_before_set_huge_page
- arch_flush_tlb_before_set_pte_page

Hi all,

On 2024/8/5 20:55, Qi Zheng wrote:

[...]

Quoted 48 lines

2. When we use mmu_gather to batch flush tlb and free PTE pages, the TLB is not flushed before pmd lock is unlocked. This may result in the following two situations:

    1) Userland can trigger page fault and fill a huge page, which will cause the existence of small size TLB and huge TLB for the same address.

    2) Userland can also trigger page fault and fill a PTE page, which will cause the existence of two small size TLBs, but the PTE page they map are different.

    For case 1), according to Intel's TLB Application note (317080), some CPUs of x86 do not allow it:

    ```
    If software modifies the paging structures so that the page size used for a
    4-KByte range of linear addresses changes, the TLBs may subsequently contain
    both ordinary and large-page translations for the address range.12 A reference
    to a linear address in the address range may use either translation. Which of
    the two translations is used may vary from one execution to another and the
    choice may be implementation-specific.

    Software wishing to prevent this uncertainty should not write to a paging-
    structure entry in a way that would change, for any linear address, both the
    page size and either the page frame or attributes. It can instead use the
    following algorithm: first mark the relevant paging-structure entry (e.g.,
    PDE) not present; then invalidate any translations for the affected linear
    addresses (see Section 5.2); and then modify the relevant paging-structure
    entry to mark it present and establish translation(s) for the new page size.
    ```

    We can also learn more information from the comments above pmdp_invalidate() in __split_huge_pmd_locked().

    For case 2), we can see from the comments above ptep_clear_flush() in wp_page_copy() that this situation is also not allowed. Even without this patch series, madvise(MADV_DONTNEED) can also cause this situation:

            CPU 0                         CPU 1

    madvise (MADV_DONTNEED)
    -->  clear pte entry
         pte_unmap_unlock
                                       touch and tlb miss --> set pte entry mmu_gather flush tlb

Quoted 2 lines

    But strangely, I didn't see any relevant fix code, maybe I missed something, or is this guaranteed by userland?

I'm still quite confused about this, is there anyone who is familiar with this part?

Thanks,
Qi

Quoted 8 lines

    Anyway, this series defines the following two functions to be implemented by the architecture. If the architecture does not allow the above two situations, then define these two functions to flush the tlb before set_pmd_at().

    - arch_flush_tlb_before_set_huge_page
    - arch_flush_tlb_before_set_pte_page

[...]

Quoted 1 line