Skip to contentSkip to conversation

khugepaged: remove redundant index check for pmd-folios

PATCH Applied Dev Jain 7 participants 8 messages Feb 27 – Mar 4

Subsystems (2)
lore
Share & tools
lore

Dev Jain

author reviewer
#0 lore raw

PATCH v2 1/1 khugepaged: remove redundant index check for pmd-folios

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

---
v1->v2:
- Remove the check instead of converting to VM_WARN_ON
- While at it, simplify the comments

Based on mm-new (8982358e1c87).

 mm/khugepaged.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)
mm/khugepaged.c +4 -10
index 5f668c1dd0fe4..b7b4680d27ab1 100644
@@ -2015,9 +2015,7 @@ static enum scan_result collapse_file(struct mm_struct *mm, unsigned long addr,
 		 * we locked the first folio, then a THP might be there already.
 		 * This will be discovered on the first iteration.
 		 */
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
 			result = SCAN_PTE_MAPPED_HUGEPAGE;
 			goto out_unlock;
 		}
@@ -2345,15 +2343,11 @@ static enum scan_result hpage_collapse_scan_file(struct mm_struct *mm,
 			continue;
 		}
 
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
 			result = SCAN_PTE_MAPPED_HUGEPAGE;
 			/*
-			 * For SCAN_PTE_MAPPED_HUGEPAGE, further processing
-			 * by the caller won't touch the page cache, and so
-			 * it's safe to skip LRU and refcount checks before
-			 * returning.
+			 * PMD-sized THP implies that we can only try
+			 * retracting the PTE table.
 			 */
 			folio_put(folio);
 			break;
Signature · 1 line
2.34.1
maintainer Acked-by on v2 1/1
#1 lore raw
Quoted 13 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Quoted 7 lines

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

---

There might be some conflict with Nicos changes.

Signature · 3 lines
Cheers,

David
reviewer Reviewed-by on v2 1/1
#2 lore raw
In reply to Dev Jain
Quoted 53 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

---
v1->v2:
- Remove the check instead of converting to VM_WARN_ON
- While at it, simplify the comments

Based on mm-new (8982358e1c87).

  mm/khugepaged.c | 14 ++++----------
  1 file changed, 4 insertions(+), 10 deletions(-)
mm/khugepaged.c +2 -6
index 5f668c1dd0fe4..b7b4680d27ab1 100644
@@ -2015,9 +2015,7 @@ static enum scan_result collapse_file(struct mm_struct *mm, unsigned long addr,
  		 * we locked the first folio, then a THP might be there already.
  		 * This will be discovered on the first iteration.
  		 */
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
  			result = SCAN_PTE_MAPPED_HUGEPAGE;
  			goto out_unlock;
  		}
@@ -2345,15 +2343,11 @@ static enum scan_result hpage_collapse_scan_file(struct mm_struct *mm,
  			continue;
  		}
 
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
  			result = SCAN_PTE_MAPPED_HUGEPAGE;

mm/khugepaged.c static enum scan_result hpage_collapse_scan_file(struct mm_struct *mm, · line 2353

Quoted 10 lines
mm/khugepaged.c +2 -4
  			/*
-			 * For SCAN_PTE_MAPPED_HUGEPAGE, further processing
-			 * by the caller won't touch the page cache, and so
-			 * it's safe to skip LRU and refcount checks before
-			 * returning.
+			 * PMD-sized THP implies that we can only try
+			 * retracting the PTE table.
  			 */
  			folio_put(folio);
  			break;

LGTM!

The proof is sound, the combination of the loop invariant, natural alignment, and VMA alignment requirements indeed makes the index check redundant :D

reviewer Reviewed-by on v2 1/1
#3 lore raw
In reply to Dev Jain
Quoted 13 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Quoted 7 lines

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

---

Reviewed-by on v2 1/1
#4 lore raw
In reply to Dev Jain
Quoted 13 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Quoted 6 lines

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

Very mathematical :)

LGTM so:

Quoted 47 lines

---
v1->v2:
- Remove the check instead of converting to VM_WARN_ON
- While at it, simplify the comments

Based on mm-new (8982358e1c87).

 mm/khugepaged.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)
mm/khugepaged.c +4 -11
index 5f668c1dd0fe4..b7b4680d27ab1 100644
@@ -2015,9 +2015,7 @@ static enum scan_result collapse_file(struct mm_struct *mm, unsigned long addr,
 		 * we locked the first folio, then a THP might be there already.
 		 * This will be discovered on the first iteration.
 		 */
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
 			result = SCAN_PTE_MAPPED_HUGEPAGE;
 			goto out_unlock;
 		}
@@ -2345,15 +2343,11 @@ static enum scan_result hpage_collapse_scan_file(struct mm_struct *mm,
 			continue;
 		}
 
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
 			result = SCAN_PTE_MAPPED_HUGEPAGE;
 			/*
-			 * For SCAN_PTE_MAPPED_HUGEPAGE, further processing
-			 * by the caller won't touch the page cache, and so
-			 * it's safe to skip LRU and refcount checks before
-			 * returning.
+			 * PMD-sized THP implies that we can only try
+			 * retracting the PTE table.
 			 */
 			folio_put(folio);
 			break;
--

2.34.1

#5 lore raw
In reply to Dev Jain
Quoted 8 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

This is because __filemap_add_folio() align the index to folio_order(), right?

Quoted 11 lines

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

Signature · 2 lines
Wei Yang
Help you, Help me
author reviewer
#6 lore raw
Quoted 11 lines · Wei Yang
Quoted 8 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

This is because __filemap_add_folio() align the index to folio_order(), right?

No, see code around instances of mapping_align_index(). We retrieve the max order from the index, not the other way around. We already are given the index to put the folio at, by the caller, so have to construct the order from that.

Quoted 13 lines
Quoted 12 lines

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

Reviewed-by on v2 1/1
#7 lore raw
In reply to Dev Jain
Quoted 13 lines · Dev Jain

Claim: folio_order(folio) == HPAGE_PMD_ORDER => folio->index == start.

Proof: Both loops in hpage_collapse_scan_file and collapse_file, which iterate on the xarray, have the invariant that
start <= folio->index < start + HPAGE_PMD_NR ... (i)

A folio is always naturally aligned in the pagecache, therefore
folio_order == HPAGE_PMD_ORDER => IS_ALIGNED(folio->index, HPAGE_PMD_NR) == true ... (ii)

thp_vma_allowable_order -> thp_vma_suitable_order requires that the virtual offsets in the VMA are aligned to the order,
=> IS_ALIGNED(start, HPAGE_PMD_NR) == true ... (iii)

Quoted 6 lines

Combining (i), (ii) and (iii), the claim is proven.

Therefore, remove this check.
While at it, simplify the comments.

Quoted 44 lines

---
v1->v2:
- Remove the check instead of converting to VM_WARN_ON
- While at it, simplify the comments

Based on mm-new (8982358e1c87).

 mm/khugepaged.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)
mm/khugepaged.c +4 -10
index 5f668c1dd0fe4..b7b4680d27ab1 100644
@@ -2015,9 +2015,7 @@ static enum scan_result collapse_file(struct mm_struct *mm, unsigned long addr,
 		 * we locked the first folio, then a THP might be there already.
 		 * This will be discovered on the first iteration.
 		 */
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
 			result = SCAN_PTE_MAPPED_HUGEPAGE;
 			goto out_unlock;
 		}
@@ -2345,15 +2343,11 @@ static enum scan_result hpage_collapse_scan_file(struct mm_struct *mm,
 			continue;
 		}
 
-		if (folio_order(folio) == HPAGE_PMD_ORDER &&
-		    folio->index == start) {
-			/* Maybe PMD-mapped */
+		if (folio_order(folio) == HPAGE_PMD_ORDER) {
 			result = SCAN_PTE_MAPPED_HUGEPAGE;
 			/*
-			 * For SCAN_PTE_MAPPED_HUGEPAGE, further processing
-			 * by the caller won't touch the page cache, and so
-			 * it's safe to skip LRU and refcount checks before
-			 * returning.
+			 * PMD-sized THP implies that we can only try
+			 * retracting the PTE table.
 			 */
 			folio_put(folio);
 			break;