[PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator

[PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator

[Liam Howlett]

From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>

This rather specialised walk can use the VMA iterator.  If this proves to
be too slow, we can write a custom routine to find the two largest gaps,
but it will be somewhat complicated, so let's see if we need it first.

Update the kunit test case to use the maple tree.  This also fixes an
issue with the kunit testcase not adding the last VMA to the list.

Fixes: 17ccae8bb5c9 (mm/damon: add kunit tests)
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
Reviewed-by: SeongJae Park <sj@kernel.org>
---
 mm/damon/vaddr-test.h | 37 +++++++++++-------------------
 mm/damon/vaddr.c      | 53 ++++++++++++++++++++++---------------------
 2 files changed, 40 insertions(+), 50 deletions(-)

diff --git a/mm/damon/vaddr-test.h b/mm/damon/vaddr-test.h
index 5431da4fe9d4..dbf2b8759607 100644
--- a/mm/damon/vaddr-test.h
+++ b/mm/damon/vaddr-test.h
@@ -13,34 +13,21 @@
 #define _DAMON_VADDR_TEST_H
 
 #include <kunit/test.h>
+#include "../../mm/internal.h"
 
-static void __link_vmas(struct vm_area_struct *vmas, ssize_t nr_vmas)
+static void __link_vmas(struct maple_tree *mt, struct vm_area_struct *vmas,
+			ssize_t nr_vmas)
 {
-	int i, j;
-	unsigned long largest_gap, gap;
+	int i;
+	MA_STATE(mas, mt, 0, 0);
 
 	if (!nr_vmas)
 		return;
 
-	for (i = 0; i < nr_vmas - 1; i++) {
-		vmas[i].vm_next = &vmas[i + 1];
-
-		vmas[i].vm_rb.rb_left = NULL;
-		vmas[i].vm_rb.rb_right = &vmas[i + 1].vm_rb;
-
-		largest_gap = 0;
-		for (j = i; j < nr_vmas; j++) {
-			if (j == 0)
-				continue;
-			gap = vmas[j].vm_start - vmas[j - 1].vm_end;
-			if (gap > largest_gap)
-				largest_gap = gap;
-		}
-		vmas[i].rb_subtree_gap = largest_gap;
-	}
-	vmas[i].vm_next = NULL;
-	vmas[i].vm_rb.rb_right = NULL;
-	vmas[i].rb_subtree_gap = 0;
+	mas_lock(&mas);
+	for (i = 0; i < nr_vmas; i++)
+		vma_mas_store(&vmas[i], &mas);
+	mas_unlock(&mas);
 }
 
 /*
@@ -72,6 +59,7 @@ static void __link_vmas(struct vm_area_struct *vmas, ssize_t nr_vmas)
  */
 static void damon_test_three_regions_in_vmas(struct kunit *test)
 {
+	static struct mm_struct mm;
 	struct damon_addr_range regions[3] = {0,};
 	/* 10-20-25, 200-210-220, 300-305, 307-330 */
 	struct vm_area_struct vmas[] = {
@@ -83,9 +71,10 @@ static void damon_test_three_regions_in_vmas(struct kunit *test)
 		(struct vm_area_struct) {.vm_start = 307, .vm_end = 330},
 	};
 
-	__link_vmas(vmas, 6);
+	mt_init_flags(&mm.mm_mt, MM_MT_FLAGS);
+	__link_vmas(&mm.mm_mt, vmas, ARRAY_SIZE(vmas));
 
-	__damon_va_three_regions(&vmas[0], regions);
+	__damon_va_three_regions(&mm, regions);
 
 	KUNIT_EXPECT_EQ(test, 10ul, regions[0].start);
 	KUNIT_EXPECT_EQ(test, 25ul, regions[0].end);
diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
index b2ec0aa1ff45..9a7c52982c35 100644
--- a/mm/damon/vaddr.c
+++ b/mm/damon/vaddr.c
@@ -113,37 +113,38 @@ static unsigned long sz_range(struct damon_addr_range *r)
  *
  * Returns 0 if success, or negative error code otherwise.
  */
-static int __damon_va_three_regions(struct vm_area_struct *vma,
+static int __damon_va_three_regions(struct mm_struct *mm,
 				       struct damon_addr_range regions[3])
 {
-	struct damon_addr_range gap = {0}, first_gap = {0}, second_gap = {0};
-	struct vm_area_struct *last_vma = NULL;
-	unsigned long start = 0;
-	struct rb_root rbroot;
-
-	/* Find two biggest gaps so that first_gap > second_gap > others */
-	for (; vma; vma = vma->vm_next) {
-		if (!last_vma) {
-			start = vma->vm_start;
-			goto next;
-		}
+	struct damon_addr_range first_gap = {0}, second_gap = {0};
+	VMA_ITERATOR(vmi, mm, 0);
+	struct vm_area_struct *vma, *prev = NULL;
+	unsigned long start;
 
-		if (vma->rb_subtree_gap <= sz_range(&second_gap)) {
-			rbroot.rb_node = &vma->vm_rb;
-			vma = rb_entry(rb_last(&rbroot),
-					struct vm_area_struct, vm_rb);
+	/*
+	 * Find the two biggest gaps so that first_gap > second_gap > others.
+	 * If this is too slow, it can be optimised to examine the maple
+	 * tree gaps.
+	 */
+	for_each_vma(vmi, vma) {
+		unsigned long gap;
+
+		if (!prev) {
+			start = vma->vm_start;
 			goto next;
 		}
-
-		gap.start = last_vma->vm_end;
-		gap.end = vma->vm_start;
-		if (sz_range(&gap) > sz_range(&second_gap)) {
-			swap(gap, second_gap);
-			if (sz_range(&second_gap) > sz_range(&first_gap))
-				swap(second_gap, first_gap);
+		gap = vma->vm_start - prev->vm_end;
+
+		if (gap > sz_range(&first_gap)) {
+			second_gap = first_gap;
+			first_gap.start = prev->vm_end;
+			first_gap.end = vma->vm_start;
+		} else if (gap > sz_range(&second_gap)) {
+			second_gap.start = prev->vm_end;
+			second_gap.end = vma->vm_start;
 		}
 next:
-		last_vma = vma;
+		prev = vma;
 	}
 
 	if (!sz_range(&second_gap) || !sz_range(&first_gap))
@@ -159,7 +160,7 @@ static int __damon_va_three_regions(struct vm_area_struct *vma,
 	regions[1].start = ALIGN(first_gap.end, DAMON_MIN_REGION);
 	regions[1].end = ALIGN(second_gap.start, DAMON_MIN_REGION);
 	regions[2].start = ALIGN(second_gap.end, DAMON_MIN_REGION);
-	regions[2].end = ALIGN(last_vma->vm_end, DAMON_MIN_REGION);
+	regions[2].end = ALIGN(prev->vm_end, DAMON_MIN_REGION);
 
 	return 0;
 }
@@ -180,7 +181,7 @@ static int damon_va_three_regions(struct damon_target *t,
 		return -EINVAL;
 
 	mmap_read_lock(mm);
-	rc = __damon_va_three_regions(mm->mmap, regions);
+	rc = __damon_va_three_regions(mm, regions);
 	mmap_read_unlock(mm);
 
 	mmput(mm);
-- 
2.35.1

Re: [PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator

[SeongJae Park]

On Wed, 4 May 2022 01:12:26 +0000 Liam Howlett <liam.howlett@oracle.com> wrote:

> From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
> 
> This rather specialised walk can use the VMA iterator.  If this proves to
> be too slow, we can write a custom routine to find the two largest gaps,
> but it will be somewhat complicated, so let's see if we need it first.
> 
> Update the kunit test case to use the maple tree.  This also fixes an
> issue with the kunit testcase not adding the last VMA to the list.
> 
> Fixes: 17ccae8bb5c9 (mm/damon: add kunit tests)
> Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
> Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> Reviewed-by: SeongJae Park <sj@kernel.org>
> ---
>  mm/damon/vaddr-test.h | 37 +++++++++++-------------------
>  mm/damon/vaddr.c      | 53 ++++++++++++++++++++++---------------------
>  2 files changed, 40 insertions(+), 50 deletions(-)
> 
> diff --git a/mm/damon/vaddr-test.h b/mm/damon/vaddr-test.h
> index 5431da4fe9d4..dbf2b8759607 100644
> --- a/mm/damon/vaddr-test.h
> +++ b/mm/damon/vaddr-test.h
> @@ -13,34 +13,21 @@
>  #define _DAMON_VADDR_TEST_H
>  
>  #include <kunit/test.h>
> +#include "../../mm/internal.h"

V9 maple tree patchset has moved the definition of vma_mas_store() from
internal.h to mmap.c, so inclusion of internal.h wouldn't needed here, right?

If we end up moving the definitions back to internal.h, because this file is
under mm/damon/, we can also use shorter include path, "../internal.h".


Thanks,
SJ

[...]

Re: [PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator

[Liam Howlett]

* SeongJae Park <sj@kernel.org> [220510 03:44]:
> On Wed, 4 May 2022 01:12:26 +0000 Liam Howlett <liam.howlett@oracle.com> wrote:
> 
> > From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
> > 
> > This rather specialised walk can use the VMA iterator.  If this proves to
> > be too slow, we can write a custom routine to find the two largest gaps,
> > but it will be somewhat complicated, so let's see if we need it first.
> > 
> > Update the kunit test case to use the maple tree.  This also fixes an
> > issue with the kunit testcase not adding the last VMA to the list.
> > 
> > Fixes: 17ccae8bb5c9 (mm/damon: add kunit tests)
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
> > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> > Reviewed-by: SeongJae Park <sj@kernel.org>
> > ---
> >  mm/damon/vaddr-test.h | 37 +++++++++++-------------------
> >  mm/damon/vaddr.c      | 53 ++++++++++++++++++++++---------------------
> >  2 files changed, 40 insertions(+), 50 deletions(-)
> > 
> > diff --git a/mm/damon/vaddr-test.h b/mm/damon/vaddr-test.h
> > index 5431da4fe9d4..dbf2b8759607 100644
> > --- a/mm/damon/vaddr-test.h
> > +++ b/mm/damon/vaddr-test.h
> > @@ -13,34 +13,21 @@
> >  #define _DAMON_VADDR_TEST_H
> >  
> >  #include <kunit/test.h>
> > +#include "../../mm/internal.h"
> 
> V9 maple tree patchset has moved the definition of vma_mas_store() from
> internal.h to mmap.c, so inclusion of internal.h wouldn't needed here, right?
> 
> If we end up moving the definitions back to internal.h, because this file is
> under mm/damon/, we can also use shorter include path, "../internal.h".

Yeah, that seems like a good plan.

I will be moving it back to internal to restore functionality to nommu.

Re: [PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator

[Andrew Morton]

On Tue, 10 May 2022 10:44:28 +0000 SeongJae Park <sj@kernel.org> wrote:

> On Wed, 4 May 2022 01:12:26 +0000 Liam Howlett <liam.howlett@oracle.com> wrote:
> 
> > From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
> > 
> > This rather specialised walk can use the VMA iterator.  If this proves to
> > be too slow, we can write a custom routine to find the two largest gaps,
> > but it will be somewhat complicated, so let's see if we need it first.
> > 
> > Update the kunit test case to use the maple tree.  This also fixes an
> > issue with the kunit testcase not adding the last VMA to the list.
> > 
> > Fixes: 17ccae8bb5c9 (mm/damon: add kunit tests)
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
> > Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
> > Reviewed-by: SeongJae Park <sj@kernel.org>
> > ---
> >  mm/damon/vaddr-test.h | 37 +++++++++++-------------------
> >  mm/damon/vaddr.c      | 53 ++++++++++++++++++++++---------------------
> >  2 files changed, 40 insertions(+), 50 deletions(-)
> > 
> > diff --git a/mm/damon/vaddr-test.h b/mm/damon/vaddr-test.h
> > index 5431da4fe9d4..dbf2b8759607 100644
> > --- a/mm/damon/vaddr-test.h
> > +++ b/mm/damon/vaddr-test.h
> > @@ -13,34 +13,21 @@
> >  #define _DAMON_VADDR_TEST_H
> >  
> >  #include <kunit/test.h>
> > +#include "../../mm/internal.h"
> 
> V9 maple tree patchset has moved the definition of vma_mas_store() from
> internal.h to mmap.c, so inclusion of internal.h wouldn't needed here, right?
> 
> If we end up moving the definitions back to internal.h, because this file is
> under mm/damon/, we can also use shorter include path, "../internal.h".

I put the vma_mas_store() and vma_mas_remove() declarations into
include/linux/mm.h so yes, internal.h is no longer required.  I queued
a fixlet against
damon-convert-__damon_va_three_regions-to-use-the-vma-iterator.patch


--- a/mm/damon/vaddr-test.h~damon-convert-__damon_va_three_regions-to-use-the-vma-iterator-fix
+++ a/mm/damon/vaddr-test.h
@@ -13,7 +13,6 @@
 #define _DAMON_VADDR_TEST_H
 
 #include <kunit/test.h>
-#include "../../mm/internal.h"
 
 static void __link_vmas(struct maple_tree *mt, struct vm_area_struct *vmas,
 			ssize_t nr_vmas)
_