Skip to contentSkip to conversation

Compute contiguous empty PTEs for mTHP efficiently

PATCH In review Dev Jain 4 participants 9 messages Sep 16, 2024 – Sep 20, 2024

Subsystems (2)
lore
Share & tools
lore

Dev Jain

author
#0 lore raw

v2 cover Compute contiguous empty PTEs for mTHP efficiently

We use pte_range_none() to determine whether contiguous PTEs are empty for an mTHP allocation. Instead of iterating the while loop for every order, use some information from the previous iteration to eliminate some cases.

v1->v2:
- Break into two patches

v1: https://lore.kernel.org/all/[email protected]/

Dev Jain (2):
mm: Make pte_range_none() return number of empty PTEs
mm: Compute first_set_pte to eliminate evaluating redundant ranges

 mm/memory.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
Signature · 1 line
2.30.2
author
#1 lore raw

PATCH v2 1/2 mm: Make pte_range_none() return number of empty PTEs

In preparation for the second patch, make pte_range_none() return the number of contiguous empty PTEs.

---
 mm/memory.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
mm/memory.c +6 -6
index 6469ac99f2f7..8bb1236de93c 100644
@@ -4617,16 +4617,16 @@ vm_fault_t do_swap_page(struct vm_fault *vmf)
 	return ret;
 }
 
-static bool pte_range_none(pte_t *pte, int nr_pages)
+static int pte_range_none(pte_t *pte, int nr_pages)
 {
 	int i;
 
 	for (i = 0; i < nr_pages; i++) {
 		if (!pte_none(ptep_get_lockless(pte + i)))
-			return false;
+			return i;
 	}
 
-	return true;
+	return nr_pages;
 }
 
 static struct folio *alloc_anon_folio(struct vm_fault *vmf)
@@ -4671,7 +4671,7 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
 	order = highest_order(orders);
 	while (orders) {
 		addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-		if (pte_range_none(pte + pte_index(addr), 1 << order))
+		if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order)
 			break;
 		order = next_order(&orders, order);
 	}
@@ -4787,7 +4787,7 @@ static vm_fault_t do_anonymous_page(struct vm_fault *vmf)
 	if (nr_pages == 1 && vmf_pte_changed(vmf)) {
 		update_mmu_tlb(vma, addr, vmf->pte);
 		goto release;
-	} else if (nr_pages > 1 && !pte_range_none(vmf->pte, nr_pages)) {
+	} else if (nr_pages > 1 && pte_range_none(vmf->pte, nr_pages) != nr_pages) {
 		update_mmu_tlb_range(vma, addr, vmf->pte, nr_pages);
 		goto release;
 	}
@@ -5121,7 +5121,7 @@ vm_fault_t finish_fault(struct vm_fault *vmf)
 		update_mmu_tlb(vma, addr, vmf->pte);
 		ret = VM_FAULT_NOPAGE;
 		goto unlock;
-	} else if (nr_pages > 1 && !pte_range_none(vmf->pte, nr_pages)) {
+	} else if (nr_pages > 1 && pte_range_none(vmf->pte, nr_pages) != nr_pages) {
 		update_mmu_tlb_range(vma, addr, vmf->pte, nr_pages);
 		ret = VM_FAULT_NOPAGE;
 		goto unlock;
Signature · 1 line
2.30.2
author
#4 lore raw

PATCH v2 2/2 mm: Compute first_set_pte to eliminate evaluating redundant ranges

In reply to Dev Jain

For an mTHP allocation, we need to check, for every order, whether for that order, we have enough number of contiguous PTEs empty. Instead of iterating the while loop for every order, use some information, which is the first set PTE found, from the previous iteration to eliminate some cases. The key to understanding the correctness of the patch is that the ranges we want to examine form a strictly decreasing sequence of nested intervals.

---
 mm/memory.c | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)
mm/memory.c +18 -2
index 8bb1236de93c..e81c6abe09ce 100644
@@ -4633,10 +4633,11 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
 {
 	struct vm_area_struct *vma = vmf->vma;
 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
+	pte_t *first_set_pte = NULL, *align_pte, *pte;
 	unsigned long orders;
 	struct folio *folio;
 	unsigned long addr;
-	pte_t *pte;
+	int max_empty;
 	gfp_t gfp;
 	int order;
 
@@ -4671,8 +4672,23 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
 	order = highest_order(orders);
 	while (orders) {
 		addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-		if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order)
+		align_pte = pte + pte_index(addr);
+
+		/* Range to be scanned known to be empty */
+		if (align_pte + (1 << order) <= first_set_pte)
+			break;
+
+		/* Range to be scanned contains first_set_pte */
+		if (align_pte <= first_set_pte)
+			goto repeat;
+
+		/* align_pte > first_set_pte, so need to check properly */
+		max_empty = pte_range_none(align_pte, 1 << order);
+		if (max_empty == 1 << order)
 			break;
+
+		first_set_pte = align_pte + max_empty;
+repeat:
 		order = next_order(&orders, order);
 	}
 
Signature · 1 line
2.30.2
Reviewed-by on v2 1/2
#2 lore raw

Re: [PATCH v2 1/2] mm: Make pte_range_none() return number of empty PTEs

In reply to Dev Jain
Quoted 4 lines · Dev Jain

In preparation for the second patch, make pte_range_none() return the number of contiguous empty PTEs.

LGTM.

Quoted 55 lines
---
  mm/memory.c | 12 ++++++------
  1 file changed, 6 insertions(+), 6 deletions(-)
mm/memory.c +6 -6
index 6469ac99f2f7..8bb1236de93c 100644
@@ -4617,16 +4617,16 @@ vm_fault_t do_swap_page(struct vm_fault *vmf)
  	return ret;
  }
 
-static bool pte_range_none(pte_t *pte, int nr_pages)
+static int pte_range_none(pte_t *pte, int nr_pages)
  {
  	int i;
 
  	for (i = 0; i < nr_pages; i++) {
  		if (!pte_none(ptep_get_lockless(pte + i)))
-			return false;
+			return i;
  	}
 
-	return true;
+	return nr_pages;
  }
 
  static struct folio *alloc_anon_folio(struct vm_fault *vmf)
@@ -4671,7 +4671,7 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
  	order = highest_order(orders);
  	while (orders) {
  		addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-		if (pte_range_none(pte + pte_index(addr), 1 << order))
+		if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order)
  			break;
  		order = next_order(&orders, order);
  	}
@@ -4787,7 +4787,7 @@ static vm_fault_t do_anonymous_page(struct vm_fault *vmf)
  	if (nr_pages == 1 && vmf_pte_changed(vmf)) {
  		update_mmu_tlb(vma, addr, vmf->pte);
  		goto release;
-	} else if (nr_pages > 1 && !pte_range_none(vmf->pte, nr_pages)) {
+	} else if (nr_pages > 1 && pte_range_none(vmf->pte, nr_pages) != nr_pages) {
  		update_mmu_tlb_range(vma, addr, vmf->pte, nr_pages);
  		goto release;
  	}
@@ -5121,7 +5121,7 @@ vm_fault_t finish_fault(struct vm_fault *vmf)
  		update_mmu_tlb(vma, addr, vmf->pte);
  		ret = VM_FAULT_NOPAGE;
  		goto unlock;
-	} else if (nr_pages > 1 && !pte_range_none(vmf->pte, nr_pages)) {
+	} else if (nr_pages > 1 && pte_range_none(vmf->pte, nr_pages) != nr_pages) {
  		update_mmu_tlb_range(vma, addr, vmf->pte, nr_pages);
  		ret = VM_FAULT_NOPAGE;
  		goto unlock;
#5 lore raw

Re: [PATCH v2 2/2] mm: Compute first_set_pte to eliminate evaluating redundant ranges

In reply to Dev Jain
Quoted 8 lines · Dev Jain

For an mTHP allocation, we need to check, for every order, whether for that order, we have enough number of contiguous PTEs empty. Instead of iterating the while loop for every order, use some information, which is the first set PTE found, from the previous iteration to eliminate some cases. The key to understanding the correctness of the patch is that the ranges we want to examine form a strictly decreasing sequence of nested intervals.

Could we include some benchmark data here, as suggested by Ryan in this thread?

https://lore.kernel.org/linux-mm/[email protected]/

Quoted 51 lines
---
 mm/memory.c | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)
mm/memory.c +18 -3
index 8bb1236de93c..e81c6abe09ce 100644
@@ -4633,10 +4633,11 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
 {
        struct vm_area_struct *vma = vmf->vma;
 #ifdef CONFIG_TRANSPARENT_HUGEPAGE
+       pte_t *first_set_pte = NULL, *align_pte, *pte;
        unsigned long orders;
        struct folio *folio;
        unsigned long addr;
-       pte_t *pte;
+       int max_empty;
        gfp_t gfp;
        int order;
 
@@ -4671,8 +4672,23 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
        order = highest_order(orders);
        while (orders) {
                addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-               if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order)
+               align_pte = pte + pte_index(addr);
+
+               /* Range to be scanned known to be empty */
+               if (align_pte + (1 << order) <= first_set_pte)
+                       break;
+
+               /* Range to be scanned contains first_set_pte */
+               if (align_pte <= first_set_pte)
+                       goto repeat;
+
+               /* align_pte > first_set_pte, so need to check properly */
+               max_empty = pte_range_none(align_pte, 1 << order);
+               if (max_empty == 1 << order)
                        break;
+
+               first_set_pte = align_pte + max_empty;
+repeat:
                order = next_order(&orders, order);
        }
 
--
Quoted 2 lines

2.30.2

Thanks
barry

Reviewed-by on v2 1/2
#3 lore raw

Re: [PATCH v2 1/2] mm: Make pte_range_none() return number of empty PTEs

In reply to Dev Jain
Quoted 34 lines · Dev Jain

In preparation for the second patch, make pte_range_none() return the number of contiguous empty PTEs.

---
 mm/memory.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
mm/memory.c +3 -3
index 6469ac99f2f7..8bb1236de93c 100644
@@ -4617,16 +4617,16 @@ vm_fault_t do_swap_page(struct vm_fault *vmf)
        return ret;
 }
 
-static bool pte_range_none(pte_t *pte, int nr_pages)
+static int pte_range_none(pte_t *pte, int nr_pages)
 {
        int i;
 
        for (i = 0; i < nr_pages; i++) {
                if (!pte_none(ptep_get_lockless(pte + i)))
-                       return false;
+                       return i;
        }
 
-       return true;
+       return nr_pages;
 }
 
 static struct folio *alloc_anon_folio(struct vm_fault *vmf)

mm/memory.c static struct folio *alloc_anon_folio(struct vm_fault *vmf) · line 4674

Quoted 5 lines
mm/memory.c +1 -1
@@ -4671,7 +4671,7 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
        order = highest_order(orders);
        while (orders) {
                addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-               if (pte_range_none(pte + pte_index(addr), 1 << order))
+               if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order)

Minor suggestion: it's a bit odd that we're doing 1 << order twice. Perhaps consider
introducing a local variable, nr_pages, for clarity.

Otherwise,

Quoted 22 lines
mm/memory.c +2 -3
                        break;
                order = next_order(&orders, order);
        }
@@ -4787,7 +4787,7 @@ static vm_fault_t do_anonymous_page(struct vm_fault *vmf)
        if (nr_pages == 1 && vmf_pte_changed(vmf)) {
                update_mmu_tlb(vma, addr, vmf->pte);
                goto release;
-       } else if (nr_pages > 1 && !pte_range_none(vmf->pte, nr_pages)) {
+       } else if (nr_pages > 1 && pte_range_none(vmf->pte, nr_pages) != nr_pages) {
                update_mmu_tlb_range(vma, addr, vmf->pte, nr_pages);
                goto release;
        }
@@ -5121,7 +5121,7 @@ vm_fault_t finish_fault(struct vm_fault *vmf)
                update_mmu_tlb(vma, addr, vmf->pte);
                ret = VM_FAULT_NOPAGE;
                goto unlock;
-       } else if (nr_pages > 1 && !pte_range_none(vmf->pte, nr_pages)) {
+       } else if (nr_pages > 1 && pte_range_none(vmf->pte, nr_pages) != nr_pages) {
                update_mmu_tlb_range(vma, addr, vmf->pte, nr_pages);
                ret = VM_FAULT_NOPAGE;
                goto unlock;
--
Quoted 2 lines

2.30.2

Thanks
Barry

author
#6 lore raw

Re: [PATCH v2 2/2] mm: Compute first_set_pte to eliminate evaluating redundant ranges

In reply to Barry Song
Quoted 11 lines · Barry Song
Quoted 7 lines · Dev Jain

For an mTHP allocation, we need to check, for every order, whether for that order, we have enough number of contiguous PTEs empty. Instead of iterating the while loop for every order, use some information, which is the first set PTE found, from the previous iteration to eliminate some cases. The key to understanding the correctness of the patch is that the ranges we want to examine form a strictly decreasing sequence of nested intervals.

Could we include some benchmark data here, as suggested by Ryan in this thread?

https://lore.kernel.org/linux-mm/[email protected]/

Can you please verify and get some numbers for the following program, because if I am doing this correctly, it would be a regression :)
https://www.codedump.xyz/cpp/Zuvf8FwvRPH21UO2

The program does this: disable THP completely -> mmap 1G VMA -> touch the last page of a 32K sized boundary. That is, 0th till 32K/4K - 2 pages are empty, while the 32K/4K - 1'th page is touched, and so on -> madvise the entire VMA -> enable all THPs except 2M -> touch all pages.

Therefore, we have 0 - 6 PTEs empty, 7th is filled, and so on. Eventually, kernel will fall down to finding 4 contiguous PTEs empty and allocate 4K * 4 = 16K mTHP.

The result without the patches:

real: 8.250s
user: 0.941s
sys: 7.077s

real: 8.175s
user: 0.939s
sys: 7.021s

With the patches:

real: 8.584s
user: 1.089s
sys: 7.234s

real: 8.429s
user: 0.954s
sys: 7.220s

You can change the #iterations in the for loop to magnify this, and the current code surprisingly wins.

Quoted 54 lines
Quoted 50 lines
---
  mm/memory.c | 20 ++++++++++++++++++--
  1 file changed, 18 insertions(+), 2 deletions(-)
mm/memory.c +18 -3
index 8bb1236de93c..e81c6abe09ce 100644
@@ -4633,10 +4633,11 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
  {
         struct vm_area_struct *vma = vmf->vma;
  #ifdef CONFIG_TRANSPARENT_HUGEPAGE
+       pte_t *first_set_pte = NULL, *align_pte, *pte;
         unsigned long orders;
         struct folio *folio;
         unsigned long addr;
-       pte_t *pte;
+       int max_empty;
         gfp_t gfp;
         int order;
 
@@ -4671,8 +4672,23 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf)
         order = highest_order(orders);
         while (orders) {
                 addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-               if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order)
+               align_pte = pte + pte_index(addr);
+
+               /* Range to be scanned known to be empty */
+               if (align_pte + (1 << order) <= first_set_pte)
+                       break;
+
+               /* Range to be scanned contains first_set_pte */
+               if (align_pte <= first_set_pte)
+                       goto repeat;
+
+               /* align_pte > first_set_pte, so need to check properly */
+               max_empty = pte_range_none(align_pte, 1 << order);
+               if (max_empty == 1 << order)
                         break;
+
+               first_set_pte = align_pte + max_empty;
+repeat:
                 order = next_order(&orders, order);
         }
 
--
Quoted 2 lines

2.30.2

Thanks
barry

#7 lore raw

Re: [PATCH v2 2/2] mm: Compute first_set_pte to eliminate evaluating redundant ranges

Quoted 10 lines · Dev Jain
Quoted 8 lines · Barry Song
Quoted 7 lines · Dev Jain

For an mTHP allocation, we need to check, for every order, whether for that order, we have enough number of contiguous PTEs empty. Instead of iterating the while loop for every order, use some information, which is the first set PTE found, from the previous iteration to eliminate some cases. The key to understanding the correctness of the patch is that the ranges we want to examine form a strictly decreasing sequence of nested intervals.

Quoted 7 lines
Quoted 3 lines

Could we include some benchmark data here, as suggested by Ryan in this thread?

https://lore.kernel.org/linux-mm/[email protected]/

Can you please verify and get some numbers for the following program, because if I am doing this correctly, it would be a regression :)
https://www.codedump.xyz/cpp/Zuvf8FwvRPH21UO2

Some brief comments on the test code:

- You don't need to enable/disable the top-level control. Regardless, I don't think this breaks the benchmark.

- I think you have an off-by-1 in your for loop condition:

for (unsigned long i = 1; (i * border) < size; ++i) {

I think this needs to be:

for (unsigned long i = 1; (i * border) <= size; ++i) {

It just means that the final 32K block will get a single 32K mapping.

- You're measuring the whole program; including mmap/munmap and enabling/disabling mTHP. It would be much better to just measure the loop that writes to each page after mTHP is enabled.

I modified the code to iterate for 10 seconds and on each iteration, measure only the time spent in the interesting loop. Running on Apple M2 VM:

Before the change:

ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.070028 seconds per GB (iterations=98)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.068495 seconds per GB (iterations=96)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.070207 seconds per GB (iterations=93)

After the change:

ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.076923 seconds per GB (iterations=88)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.072206 seconds per GB (iterations=96)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.072397 seconds per GB (iterations=89)

So this looks pretty clearly slower to me. So suggest we shouldn't take this patch.

Quoted 22 lines

The program does this: disable THP completely -> mmap 1G VMA -> touch the last page of a 32K sized boundary. That is, 0th till 32K/4K - 2 pages are empty, while the 32K/4K - 1'th page is touched, and so on -> madvise the entire VMA -> enable all THPs except 2M -> touch all pages.

Therefore, we have 0 - 6 PTEs empty, 7th is filled, and so on. Eventually, kernel will fall down to finding 4 contiguous PTEs empty and allocate 4K * 4 = 16K mTHP.

The result without the patches:

real: 8.250s
user: 0.941s
sys: 7.077s

real: 8.175s
user: 0.939s
sys: 7.021s

With the patches:

Quoted 7 lines

real: 8.584s
user: 1.089s
sys: 7.234s

real: 8.429s
user: 0.954s
sys: 7.220s

What HW did you measure this on? I'm guessing this is measuring multiple iterations, otherwise it looks extremely slow. If you were measuring on FVP, for example, that would not give representative performance numbers.

Thanks,
Ryan

Quoted 62 lines

You can change the #iterations in the for loop to magnify this, and the current code surprisingly wins.

Quoted 57 lines
Quoted 50 lines

---
  mm/memory.c | 20 ++++++++++++++++++--

  1 file changed, 18 insertions(+), 2 deletions(-)
mm/memory.c +18 -2
index 8bb1236de93c..e81c6abe09ce 100644
@@ -4633,10 +4633,11 @@ static struct folio *alloc_anon_folio(struct vm_fault
 *vmf)
   {
          struct vm_area_struct *vma = vmf->vma;
   #ifdef CONFIG_TRANSPARENT_HUGEPAGE
+       pte_t *first_set_pte = NULL, *align_pte, *pte;
          unsigned long orders;
          struct folio *folio;
          unsigned long addr;
-       pte_t *pte;
+       int max_empty;
          gfp_t gfp;
          int order;
@@ -4671,8 +4672,23 @@ static struct folio *alloc_anon_folio(struct vm_fault
 *vmf)
          order = highest_order(orders);
          while (orders) {
                  addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-               if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 <<
 order)
+               align_pte = pte + pte_index(addr);
+
+               /* Range to be scanned known to be empty */
+               if (align_pte + (1 << order) <= first_set_pte)
+                       break;
+
+               /* Range to be scanned contains first_set_pte */
+               if (align_pte <= first_set_pte)
+                       goto repeat;
+
+               /* align_pte > first_set_pte, so need to check properly */
+               max_empty = pte_range_none(align_pte, 1 << order);
+               if (max_empty == 1 << order)
                          break;
+
+               first_set_pte = align_pte + max_empty;
+repeat:
                  order = next_order(&orders, order);
Quoted 5 lines

         }

Signature · 1 line
2.30.2

Thanks
barry

author
#8 lore raw

Re: [PATCH v2 2/2] mm: Compute first_set_pte to eliminate evaluating redundant ranges

Quoted 50 lines · Ryan Roberts
Quoted 9 lines · Dev Jain
Quoted 8 lines · Barry Song
Quoted 7 lines · Dev Jain

For an mTHP allocation, we need to check, for every order, whether for that order, we have enough number of contiguous PTEs empty. Instead of iterating the while loop for every order, use some information, which is the first set PTE found, from the previous iteration to eliminate some cases. The key to understanding the correctness of the patch is that the ranges we want to examine form a strictly decreasing sequence of nested intervals.

Quoted 6 lines
Quoted 3 lines

Could we include some benchmark data here, as suggested by Ryan in this thread?

https://lore.kernel.org/linux-mm/[email protected]/

Can you please verify and get some numbers for the following program, because if I am doing this correctly, it would be a regression :)
https://www.codedump.xyz/cpp/Zuvf8FwvRPH21UO2

Some brief comments on the test code:

- You don't need to enable/disable the top-level control. Regardless, I don't think this breaks the benchmark.

- I think you have an off-by-1 in your for loop condition:

for (unsigned long i = 1; (i * border) < size; ++i) {

I think this needs to be:

for (unsigned long i = 1; (i * border) <= size; ++i) {

It just means that the final 32K block will get a single 32K mapping.

- You're measuring the whole program; including mmap/munmap and enabling/disabling mTHP. It would be much better to just measure the loop that writes to each page after mTHP is enabled.

I modified the code to iterate for 10 seconds and on each iteration, measure only the time spent in the interesting loop. Running on Apple M2 VM:

Before the change:

ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.070028 seconds per GB (iterations=98)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.068495 seconds per GB (iterations=96)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.070207 seconds per GB (iterations=93)

After the change:

Quoted 8 lines
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.076923 seconds per GB (iterations=88)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.072206 seconds per GB (iterations=96)
ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte
Average: 0.072397 seconds per GB (iterations=89)

So this looks pretty clearly slower to me. So suggest we shouldn't take this patch.

Thanks for testing!

Quoted 27 lines
Quoted 27 lines

The program does this: disable THP completely -> mmap 1G VMA -> touch the last page of a 32K sized boundary. That is, 0th till 32K/4K - 2 pages are empty, while the 32K/4K - 1'th page is touched, and so on -> madvise the entire VMA -> enable all THPs except 2M -> touch all pages.

Therefore, we have 0 - 6 PTEs empty, 7th is filled, and so on. Eventually, kernel will fall down to finding 4 contiguous PTEs empty and allocate 4K * 4 = 16K mTHP.

The result without the patches:

real: 8.250s
user: 0.941s
sys: 7.077s

real: 8.175s
user: 0.939s
sys: 7.021s

With the patches:

real: 8.584s
user: 1.089s
sys: 7.234s

Quoted 6 lines
Quoted 3 lines

real: 8.429s
user: 0.954s
sys: 7.220s

What HW did you measure this on? I'm guessing this is measuring multiple iterations, otherwise it looks extremely slow. If you were measuring on FVP, for example, that would not give representative performance numbers.

I measured with qemu.

Quoted 64 lines

Thanks,
Ryan

Quoted 60 lines

You can change the #iterations in the for loop to magnify this, and the current code surprisingly wins.

Quoted 56 lines
Quoted 49 lines
---
   mm/memory.c | 20 ++++++++++++++++++--
   1 file changed, 18 insertions(+), 2 deletions(-)
mm/memory.c +18 -2
index 8bb1236de93c..e81c6abe09ce 100644
@@ -4633,10 +4633,11 @@ static struct folio *alloc_anon_folio(struct vm_fault
 *vmf)
   {
          struct vm_area_struct *vma = vmf->vma;
   #ifdef CONFIG_TRANSPARENT_HUGEPAGE
+       pte_t *first_set_pte = NULL, *align_pte, *pte;
          unsigned long orders;
          struct folio *folio;
          unsigned long addr;
-       pte_t *pte;
+       int max_empty;
          gfp_t gfp;
          int order;
@@ -4671,8 +4672,23 @@ static struct folio *alloc_anon_folio(struct vm_fault
 *vmf)
          order = highest_order(orders);
          while (orders) {
                  addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order);
-               if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 <<
 order)
+               align_pte = pte + pte_index(addr);
+
+               /* Range to be scanned known to be empty */
+               if (align_pte + (1 << order) <= first_set_pte)
+                       break;
+
+               /* Range to be scanned contains first_set_pte */
+               if (align_pte <= first_set_pte)
+                       goto repeat;
+
+               /* align_pte > first_set_pte, so need to check properly */
+               max_empty = pte_range_none(align_pte, 1 << order);
+               if (max_empty == 1 << order)
                          break;
+
+               first_set_pte = align_pte + max_empty;
+repeat:
                  order = next_order(&orders, order);
Quoted 5 lines

         }

Signature · 1 line
2.30.2

Thanks
barry