Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Liam Howlett <liam.howlett@oracle.com>
To:     "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        "damon @ lists . linux . dev" <damon@lists.linux.dev>,
        SeongJae Park <sj@kernel.org>,
        David Hildenbrand <david@redhat.com>
Subject: [PATCH v10 15/69] damon: convert __damon_va_three_regions to use the
 VMA iterator
Thread-Topic: [PATCH v10 15/69] damon: convert __damon_va_three_regions to use
 the VMA iterator
Thread-Index: AQHYhbALnOB98sBhzE+ymFEScAPgZA==
Date:   Tue, 21 Jun 2022 20:46:56 +0000
Message-ID: <20220621204632.3370049-16-Liam.Howlett@oracle.com>
References: <20220621204632.3370049-1-Liam.Howlett@oracle.com>
In-Reply-To: <20220621204632.3370049-1-Liam.Howlett@oracle.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?mdeKhMUUIG6mqsB3OCtlo9eli/+A9r7byjmgfIaE7uQQycRXFd/ITVwcD2?=
 =?iso-8859-1?Q?E1/DePoVdNsESTm4/J5C6eIb72lL5PdwBVNonnqnlqxVZBnmEKAR41gT+R?=
 =?iso-8859-1?Q?OVE4i3SWCKjY+aWQg+6V7pY+3ytOOb2I/o+M0nLJMvhjkYV/LRnZt9zvyW?=
 =?iso-8859-1?Q?vy0PcOev3gOVHi92wukwhLCA1RexooHCgTBlRqqQlT3sTr/mruGpQJjVFr?=
 =?iso-8859-1?Q?juVvzd0VlNJjuAoG/4JNF+cQ+ypPSE+wgrTswn0u+F3p8NGDGFtx0yy1QP?=
 =?iso-8859-1?Q?tngV1IrMUD/3S2Sqs3hwPoZWS4FBW/B5EwuW0CDdjprSjhp2VFUkHmPx+N?=
 =?iso-8859-1?Q?UCh54zfxT6OLLoBQidqX1Om44RqEQsqdxsbD7YMsKOESCzPMgUsvrTv1W9?=
 =?iso-8859-1?Q?D7RKDtSvtjexnsXJ9Ap51SCqXBh14tYUYpmKZq5XVrZuKfRuzKVQ5qPqWN?=
 =?iso-8859-1?Q?51p3vh5c1+MVtp34tv4iKf7i4I+4uEOBEITcjEbnT8bqYn1z/YhGYADzqc?=
 =?iso-8859-1?Q?tihPmyCsl7OjhyQ8y0xw0Fh7WqeBr+RWtF1x1sh/XP55VD9Za2iWnZtjvF?=
 =?iso-8859-1?Q?JNX0P/We6scVF53zFl79uHZtJ2M2J9EaI7QGo1PE4HXONVGTQ2Wu35tv1W?=
 =?iso-8859-1?Q?Aq7RUg7It5/co/N7fKJ54aNpb34kR1vxvg5kHgofbNO67LS+H2+i/La+2Q?=
 =?iso-8859-1?Q?dkQmrgo4Ss4VJ3HG6NCdFjnsIo3lZdr7mDXuY35+Z1x2wfT/Kae+noNDFD?=
 =?iso-8859-1?Q?e5lfT05BvYpN9/BGdgzbZxUPda8wRUV5ph0ELExQuolGXt7NJ2pRryIar9?=
 =?iso-8859-1?Q?qDHfX0sjPI/qnsUxaRCDFQMxN0xSpnZ/TZuprn0KEvwCuV+wzYm6XERO6z?=
 =?iso-8859-1?Q?8QWxXIqgu3c7QkVEMX465FnmEbs25N7JdO6Fb1TQuQ4i0g0dz7xaw+jNUO?=
 =?iso-8859-1?Q?ed99KT+edx3SaCbcAhHt2LBtcxfUWW6LJRanndX3mXM3x8LN6xFwI84Glq?=
 =?iso-8859-1?Q?PkaZnyJ027SjhasR/kvw0kz1fAJNAEkcDzZB2ZzJzjEnfrbdDTXWP3pslK?=
 =?iso-8859-1?Q?Bol141Lw8X3WMLfTwqVJeg5fL2ERH/vMbbxO9BfakJCg36/gxT2NuNXZY/?=
 =?iso-8859-1?Q?XOhR/cNt7Z8HTKEg0rEyjr/5fdChRzkdwS4hN8NJK0czPcaHqCTgteJjSj?=
 =?iso-8859-1?Q?84nT8YyckUsw1wmXW7x09JCjaO7/mPFNIGxbgMzn0SrBopAs2gu4SIWh7K?=
 =?iso-8859-1?Q?YC8bXs0g2YOe4w4UrkueBdTpMk4pOLwIV8Nvq9OIMh141nUxphgIGfdNyT?=
 =?iso-8859-1?Q?k2BrwoypU7rhqDMrY3pF88RHCo61h3JDUtw2/caHhfVTQZ1FggJ6bjsXjI?=
 =?iso-8859-1?Q?rOsvIqrb7caXknWKXpwavNCJ77IK9lIw1hqhl89L6xLmnTx9NA4yngTXDc?=
 =?iso-8859-1?Q?wG1HEXMs/mh6yL9XePV8bWlLnLC1OMeCUsv9ZN88JZNwOK4bhZAYlu8SgW?=
 =?iso-8859-1?Q?mqKiQZ/Uo5ZpL+8RE/AwK6tIrZ1ViLKPjBfYoO0p03NJ/DUC4t4vtYftBE?=
 =?iso-8859-1?Q?QRrsgwbrnVfOdZUwuG274B6+a9dbleAPyrLVEfBbBAVRo69E8yL+wPfRMw?=
 =?iso-8859-1?Q?lqDA7CnC4cCNUReSFPP9S/29pc+HCZ27AIr1iWvxKnTDS5R4QpqzyLzWd2?=
 =?iso-8859-1?Q?N3xhes07EEGYZXaLQhA+Dfu1O/z6xkjLQnolVdU2HjDW/0IrQwkZ8TJFY4?=
 =?iso-8859-1?Q?+YFNr5UVGq126ED5IhigKzxwi1l58GLCuR340HrXGbbCQBAF3M/ya4x7gI?=
 =?iso-8859-1?Q?Gc4Ia+mV0QWsDaaF6mlW18W2Kgb1QPU=3D?=
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: f9c8e348-b673-4368-8d9b-08da53c732b2
X-MS-Exchange-CrossTenant-originalarrivaltime: 21 Jun 2022 20:46:56.1761
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: Q5IlWR6mGJUbe7S3tmCd2UkNKJaKpw0w7MTc8mlZkX+YaL4QRp/l1R9qTPnKAc4LjPTIRWPlnknxQ6aq5dLDOg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR10MB3085
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.883
 definitions=2022-06-21_09:2022-06-21,2022-06-21 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 malwarescore=0
 mlxlogscore=830 bulkscore=0 phishscore=0 suspectscore=0 spamscore=0
 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2204290000 definitions=main-2206210087
X-Proofpoint-ORIG-GUID: PXb89__T42OGcxLy04-j-WDpF0yMT6or
X-Proofpoint-GUID: PXb89__T42OGcxLy04-j-WDpF0yMT6or
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE
        autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

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.

Link: https://lkml.kernel.org/r/20220504011215.661968-1-Liam.Howlett@oracle=
.com
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>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: David Howells <dhowells@redhat.com>
Cc: Vlastimil Babka <vbabka@suse.cz>
Cc: Will Deacon <will@kernel.org>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
 mm/damon/vaddr-test.h | 36 ++++++++++-------------------
 mm/damon/vaddr.c      | 53 ++++++++++++++++++++++---------------------
 2 files changed, 39 insertions(+), 50 deletions(-)

diff --git a/mm/damon/vaddr-test.h b/mm/damon/vaddr-test.h
index d4f55f349100..bce37c487540 100644
--- a/mm/damon/vaddr-test.h
+++ b/mm/damon/vaddr-test.h
@@ -14,33 +14,19 @@
=20
 #include <kunit/test.h>
=20
-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);
=20
 	if (!nr_vmas)
 		return;
=20
-	for (i =3D 0; i < nr_vmas - 1; i++) {
-		vmas[i].vm_next =3D &vmas[i + 1];
-
-		vmas[i].vm_rb.rb_left =3D NULL;
-		vmas[i].vm_rb.rb_right =3D &vmas[i + 1].vm_rb;
-
-		largest_gap =3D 0;
-		for (j =3D i; j < nr_vmas; j++) {
-			if (j =3D=3D 0)
-				continue;
-			gap =3D vmas[j].vm_start - vmas[j - 1].vm_end;
-			if (gap > largest_gap)
-				largest_gap =3D gap;
-		}
-		vmas[i].rb_subtree_gap =3D largest_gap;
-	}
-	vmas[i].vm_next =3D NULL;
-	vmas[i].vm_rb.rb_right =3D NULL;
-	vmas[i].rb_subtree_gap =3D 0;
+	mas_lock(&mas);
+	for (i =3D 0; i < nr_vmas; i++)
+		vma_mas_store(&vmas[i], &mas);
+	mas_unlock(&mas);
 }
=20
 /*
@@ -72,6 +58,7 @@ static void __link_vmas(struct vm_area_struct *vmas, ssiz=
e_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] =3D {0,};
 	/* 10-20-25, 200-210-220, 300-305, 307-330 */
 	struct vm_area_struct vmas[] =3D {
@@ -83,9 +70,10 @@ static void damon_test_three_regions_in_vmas(struct kuni=
t *test)
 		(struct vm_area_struct) {.vm_start =3D 307, .vm_end =3D 330},
 	};
=20
-	__link_vmas(vmas, 6);
+	mt_init_flags(&mm.mm_mt, MM_MT_FLAGS);
+	__link_vmas(&mm.mm_mt, vmas, ARRAY_SIZE(vmas));
=20
-	__damon_va_three_regions(&vmas[0], regions);
+	__damon_va_three_regions(&mm, regions);
=20
 	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 59e1653799f8..5767be72c181 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 =3D {0}, first_gap =3D {0}, second_gap =3D {0=
};
-	struct vm_area_struct *last_vma =3D NULL;
-	unsigned long start =3D 0;
-	struct rb_root rbroot;
-
-	/* Find two biggest gaps so that first_gap > second_gap > others */
-	for (; vma; vma =3D vma->vm_next) {
-		if (!last_vma) {
-			start =3D vma->vm_start;
-			goto next;
-		}
+	struct damon_addr_range first_gap =3D {0}, second_gap =3D {0};
+	VMA_ITERATOR(vmi, mm, 0);
+	struct vm_area_struct *vma, *prev =3D NULL;
+	unsigned long start;
=20
-		if (vma->rb_subtree_gap <=3D sz_range(&second_gap)) {
-			rbroot.rb_node =3D &vma->vm_rb;
-			vma =3D 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 =3D vma->vm_start;
 			goto next;
 		}
-
-		gap.start =3D last_vma->vm_end;
-		gap.end =3D 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 =3D vma->vm_start - prev->vm_end;
+
+		if (gap > sz_range(&first_gap)) {
+			second_gap =3D first_gap;
+			first_gap.start =3D prev->vm_end;
+			first_gap.end =3D vma->vm_start;
+		} else if (gap > sz_range(&second_gap)) {
+			second_gap.start =3D prev->vm_end;
+			second_gap.end =3D vma->vm_start;
 		}
 next:
-		last_vma =3D vma;
+		prev =3D vma;
 	}
=20
 	if (!sz_range(&second_gap) || !sz_range(&first_gap))
@@ -159,7 +160,7 @@ static int __damon_va_three_regions(struct vm_area_stru=
ct *vma,
 	regions[1].start =3D ALIGN(first_gap.end, DAMON_MIN_REGION);
 	regions[1].end =3D ALIGN(second_gap.start, DAMON_MIN_REGION);
 	regions[2].start =3D ALIGN(second_gap.end, DAMON_MIN_REGION);
-	regions[2].end =3D ALIGN(last_vma->vm_end, DAMON_MIN_REGION);
+	regions[2].end =3D ALIGN(prev->vm_end, DAMON_MIN_REGION);
=20
 	return 0;
 }
@@ -180,7 +181,7 @@ static int damon_va_three_regions(struct damon_target *=
t,
 		return -EINVAL;
=20
 	mmap_read_lock(mm);
-	rc =3D __damon_va_three_regions(mm->mmap, regions);
+	rc =3D __damon_va_three_regions(mm, regions);
 	mmap_read_unlock(mm);
=20
 	mmput(mm);
--=20
2.35.1