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 12/69] mm/mmap: use the maple tree for find_vma_prev()
 instead of the rbtree
Thread-Topic: [PATCH v10 12/69] mm/mmap: use the maple tree for
 find_vma_prev() instead of the rbtree
Thread-Index: AQHYhbAKWR90m9n/e0OhSgs/pJLosw==
Date:   Tue, 21 Jun 2022 20:46:55 +0000
Message-ID: <20220621204632.3370049-13-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?kydRA2SYYJ8DPi+kxlBaxcK39oWcPU9qcpd712+nDciPgeHevOdMMTsj6V?=
 =?iso-8859-1?Q?RoI9SZv80vofqc8pYF58BPbilm+VtDsJcSoqOctMMFqjUoJzlOPgG6aXE9?=
 =?iso-8859-1?Q?E8EFluvYqQOPxyQykKYi31EOJSGG7aWPj3VL3Kf7UcUJeCEGZ2LLUKVdR1?=
 =?iso-8859-1?Q?801Sm2Z9aRQjRTXNxaQGBhMlKTzcDykvUmjyYXw/Ss6mM+dNSR+dpzmARd?=
 =?iso-8859-1?Q?ZeRvE83aLeCyX31KrCZvMo385xC2Aln3iyPR5ecCaSwApS6adrG3XX6ob0?=
 =?iso-8859-1?Q?xPIo0BTE1j3Yg2+nCWlew2GTgQvNsUhdQd/1OizKRKTwbKivAFXxz4sxxE?=
 =?iso-8859-1?Q?Xkgq1PqYtt831VNhoHi9tzC0IvqcdV21laEvUpLoEBygW7lADB6KObVTKF?=
 =?iso-8859-1?Q?hvFYsZgijvlrldU7+ySq8LatfFvtBqU+bcMtNeCu+8G7L1BPo6EHVqdMKr?=
 =?iso-8859-1?Q?NKbnVfA/aF43QcMrxlxjnSNdYWN/f7GFnb0B28Tt/7pKK0+RcmYP4RcD8Z?=
 =?iso-8859-1?Q?AVTz3HGjplH/4iccEAkd7plQi3lh/+v3Tk4IYsFmbO7x5XZZikQNXIlajY?=
 =?iso-8859-1?Q?YA91PJLxy+D+HCUEltGnuefxPRz4bokbRPFqEHiQ/8o9AKhOUf74tNE4lg?=
 =?iso-8859-1?Q?/e2RrddZDPoGR2o9LrsG3rB5mHqn6pdDT9HSDY9IKnkRK32qOzq68lk8UQ?=
 =?iso-8859-1?Q?mj5g4PSZvycYiJ/Os+l5nFNpzjXUcfYv0AezsfP2KDmlQz4y6FSbZIvSnw?=
 =?iso-8859-1?Q?YEB+mP2TFNrnHOjFZ3mGv8DI6Pk/7nvkDCaqETaN1xMZe1RTC9hqQnSDga?=
 =?iso-8859-1?Q?H6k114FxKfGLmadziwubyjFnf9tDj9HsJ6bf5vIdov3yEZIUxd2AqkR6Dm?=
 =?iso-8859-1?Q?ePmYw49v2dFfoaBk26HpViOQch9ssUtR/f/wpHLbOq47BN3DOZ5nF+X9eV?=
 =?iso-8859-1?Q?2LYRANhiH2V3Ch0ZpME0o9VtcDDbK+5yZkrEzxSe8AulvUv9mR3wnnD7Ce?=
 =?iso-8859-1?Q?25UDIODrW/ahd6eFlR65alE5u9De3qP0Ie1gtvjWje5aNcnZ2uAyytWclI?=
 =?iso-8859-1?Q?+YNcpwEFeg/WAds2UALrdSpAYLmt6vy15NDeKr8JRpgUp1Amq73BqgP6ld?=
 =?iso-8859-1?Q?ebcPvC3QSdLpzdfn3x7enxoeqNTBD+zC5f6YadtgAr9BDe9LrdOuQMF71b?=
 =?iso-8859-1?Q?uWy9tvlshck1maW2uBvLoK9nWud9Eft8FVhez6azwgvDr+5jRcBSZtUVk4?=
 =?iso-8859-1?Q?SMkAl/eM57ImoLxD/EB/yz5+tY4K8mX8qrnpRksQ4lc1ckMERkxL4KDWPv?=
 =?iso-8859-1?Q?XRLf2xzWsJHSk9/BRvtHUXJejH4+E7+5HcjDAlcil+Eze1B668W3vm3QuS?=
 =?iso-8859-1?Q?W5Toyy54GbyMsYW/8BBBpPi/vXie3VMVlh3ZKwNr3tX5TkKPwl4Eii2awr?=
 =?iso-8859-1?Q?VUwlDBrT8nseDa89PnuZfFHdQnYOdaCbZXCSt9Ez6p/6sWpJteSAsE8djE?=
 =?iso-8859-1?Q?xiYGA6xdlVvrOdwLeggqsifLwl+nxn2MyW9bTgDA2XCyjk3UWZUociEJbc?=
 =?iso-8859-1?Q?wsn5leW+iuMpRcnbKEMrMeVJ0hLkRwXNtYh3JfeFrxNJOT+zoTLTG7psn8?=
 =?iso-8859-1?Q?ltotVNch3XHi/Qa4crhJUCoTQZADIPoUGUNIFG+/nsN8C5XLquzPBI6ct6?=
 =?iso-8859-1?Q?gufjjQTkKLllh5Q/R2EfoCX5N3+vhaCz3IAVApBk0ckcmoPBdqGIvs3dAN?=
 =?iso-8859-1?Q?/vgcWHtn878b+OdaYFzV06PSLf3fnr/wSPMiSVRgvPv7tN1iET7n8LZ197?=
 =?iso-8859-1?Q?u6FNgOih3ZyLnEXQ9sOZsV7ScYfcCPk=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: 81cc9d4d-d389-422b-2885-08da53c731a5
X-MS-Exchange-CrossTenant-originalarrivaltime: 21 Jun 2022 20:46:55.2387
 (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: CDPwlZTprsd+gpvvuT2d1Jm0lLEOGtgBOmctM4ZUkDuuXdycOqfdziB4QrksIuQGA90/Jj0bYoBWJFp9OfF5HQ==
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=999 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: Umxzezvu2qs6B6GA3XFWZ0gNOpx4cg_K
X-Proofpoint-GUID: Umxzezvu2qs6B6GA3XFWZ0gNOpx4cg_K
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>

Use the maple tree's advanced API and a maple state to walk the tree for
the entry at the address of the next vma, then use the maple state to walk
back one entry to find the previous entry.

Add kernel documentation comments for this API.

Link: https://lkml.kernel.org/r/20220504010716.661115-14-Liam.Howlett@oracl=
e.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: David Howells <dhowells@redhat.com>
Cc: SeongJae Park <sj@kernel.org>
Cc: Will Deacon <will@kernel.org>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
 mm/mmap.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index fdb61252448f..08845a0317bf 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2512,23 +2512,30 @@ struct vm_area_struct *find_vma(struct mm_struct *m=
m, unsigned long addr)
 }
 EXPORT_SYMBOL(find_vma);
=20
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *ppr=
ev.
+/**
+ * find_vma_prev() - Find the VMA for a given address, or the next vma and
+ * set %pprev to the previous VMA, if any.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ * @pprev: The pointer to set to the previous VMA
+ *
+ * Note that RCU lock is missing here since the external mmap_lock() is us=
ed
+ * instead.
+ *
+ * Returns: The VMA associated with @addr, or the next vma.
+ * May return %NULL in the case of no vma at addr or above.
  */
 struct vm_area_struct *
 find_vma_prev(struct mm_struct *mm, unsigned long addr,
 			struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
=20
-	vma =3D find_vma(mm, addr);
-	if (vma) {
-		*pprev =3D vma->vm_prev;
-	} else {
-		struct rb_node *rb_node =3D rb_last(&mm->mm_rb);
-
-		*pprev =3D rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : N=
ULL;
-	}
+	vma =3D mas_walk(&mas);
+	*pprev =3D mas_prev(&mas, 0);
+	if (!vma)
+		vma =3D mas_next(&mas, ULONG_MAX);
 	return vma;
 }
=20
--=20
2.35.1