| Message ID | 20220504011215.661968-1-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Prepare for maple tree | expand |
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 [...]
* 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.
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)
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);