From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3EF1DEB64D9 for ; Tue, 27 Jun 2023 18:03:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CB99B8D0002; Tue, 27 Jun 2023 14:03:45 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C69688D0001; Tue, 27 Jun 2023 14:03:45 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B09D38D0002; Tue, 27 Jun 2023 14:03:45 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 9F0568D0001 for ; Tue, 27 Jun 2023 14:03:45 -0400 (EDT) Received: from smtpin22.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 3C5E78014C for ; Tue, 27 Jun 2023 18:03:45 +0000 (UTC) X-FDA: 80949300810.22.AC239F6 Received: from mail-wr1-f45.google.com (mail-wr1-f45.google.com [209.85.221.45]) by imf29.hostedemail.com (Postfix) with ESMTP id BD05112025E for ; Tue, 27 Jun 2023 18:02:32 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b="Fxc/Hj8L"; spf=pass (imf29.hostedemail.com: domain of lstoakes@gmail.com designates 209.85.221.45 as permitted sender) smtp.mailfrom=lstoakes@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1687888953; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=goa42M9DzRb9h/mnWpooF3Ny8vytrBBwoFO9ZHZqKto=; b=01ktUdCRiZYNpI3yk1UKQ0zh9E+UoBK8A97Le0IZb93oaVAj1CE6Q25d/o3nKU6Cv7kBTN hsQE4JGA4MSuikCQJJZ10ViuOowelxUbeFFLqxYVGphXKxkR3gfR7AjPBHTJ9nQyF2Ee0t oYlf0tj4LzJDJIbU/JG38cL/+xUk6Ro= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1687888953; a=rsa-sha256; cv=none; b=a+SMNUiOa/DzuSMI2M96rOKuVwio2eJe5K/qDV4TVw7/cBNuSSq43DIbYFNB9qZSRsdiaS LhaasT5nwxgl4SolS54EPzKXUfMDStyPIPeoI+jQPgQ9P+aLWj5+UTYznBgtFtmZqCSNRS 278iuwXHmvZ4L+AeXkMd9dB0SGyf+VI= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b="Fxc/Hj8L"; spf=pass (imf29.hostedemail.com: domain of lstoakes@gmail.com designates 209.85.221.45 as permitted sender) smtp.mailfrom=lstoakes@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-wr1-f45.google.com with SMTP id ffacd0b85a97d-3090d3e9c92so6554237f8f.2 for ; Tue, 27 Jun 2023 11:02:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1687888951; x=1690480951; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=goa42M9DzRb9h/mnWpooF3Ny8vytrBBwoFO9ZHZqKto=; b=Fxc/Hj8LImN3leqe0w2ISJ37IyQdRyDIpDFaEUTQTlxQhSLTXhlYwUSjxy2dAt84qy v/vp/T2L9mwLR0s+mY2EHrKTnx29gii53ZVbysrO2hnjayS+8gHpNYiPi9E7kZo2zADO W2HKo6FAP+HDWNHlZLYwW1e9Ilzy8smxf5nQLDGOiVpWUakqWbV8Z9few9bxtCryRKaM /5rlOJMa5SMj6PUJgnKaIkjzbf9MTXnE6bu1zcLm33NZJGBkrR13N1UHR6f/UO5GP96g DEIomQYkXdo5Ar6cM3cJHd1FoHG/klNgp9aRDFMTxks/frlzfVIKOxM3Q/8Cok+ELTYD QRcg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687888951; x=1690480951; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=goa42M9DzRb9h/mnWpooF3Ny8vytrBBwoFO9ZHZqKto=; b=Exu15XDYISQST2vl9crbKcQoGkez0EQolRiMw4jQZIIpRkjhqkMjLPH0Q+CuJWLJk9 tYE6TvOIvBTrceByzFaREAf6GNLNGOEKbKve/l3bkvwYjVlnun/XaVyRzwRX28EvlDz0 EOmq6gTTRyzYpHk6Iu+csj0o1N4hmZ11WrIN+28n2U4RT2dl5aiexz5PXRyESmeGWhTT 1sP4b7TVBZ3V5BvEGPtdjS7j/r/9s+tZuBHZNx7YHPKQ/wKzy6oA7F724TITacGcXEbr ebnyvisAUWkJzJXNgNrJzEIgqg2A1VqYijVs7krqCo4A2MjAFBhNwFMS6BFRdPlFmaTE pgBA== X-Gm-Message-State: AC+VfDyEMVfGkF6n+Y9tdIkDz/oHpWrBvTIoT3oQ89W6MaaK7yCLi24N +QCgawoUsIUVH6yIkIqhE8s= X-Google-Smtp-Source: ACHHUZ4iMbz92ay0FqWK+4uSCi4J4aWB19HFktwq7p/WeH4WHqfgQZ006Vr1pCcCxn/m8FW1hYPJPg== X-Received: by 2002:a5d:590c:0:b0:30f:ba85:52b9 with SMTP id v12-20020a5d590c000000b0030fba8552b9mr33941057wrd.37.1687888950771; Tue, 27 Jun 2023 11:02:30 -0700 (PDT) Received: from localhost ([2a00:23c5:dc8c:8701:1663:9a35:5a7b:1d76]) by smtp.gmail.com with ESMTPSA id f4-20020a1c6a04000000b003fba2734f1esm2781378wmc.1.2023.06.27.11.02.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 27 Jun 2023 11:02:29 -0700 (PDT) Date: Tue, 27 Jun 2023 19:02:29 +0100 From: Lorenzo Stoakes To: "Liam R. Howlett" , Joel Fernandes , linux-kernel@vger.kernel.org, Linus Torvalds , linux-kselftest@vger.kernel.org, linux-mm@kvack.org, Shuah Khan , Vlastimil Babka , Michal Hocko , Kirill A Shutemov , "Paul E. McKenney" , Suren Baghdasaryan , Kalesh Singh , Lokesh Gidra , Vineeth Pillai Subject: Re: [PATCH v4 1/7] mm/mremap: Optimize the start addresses in move_page_tables() Message-ID: References: <20230531220807.2048037-1-joel@joelfernandes.org> <20230531220807.2048037-2-joel@joelfernandes.org> <20230627175609.xrn4mle6hpi6exh7@revolver> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230627175609.xrn4mle6hpi6exh7@revolver> X-Rspamd-Queue-Id: BD05112025E X-Rspam-User: X-Stat-Signature: tyhn3tdskom3i1xmauryoyew6q81hq9g X-Rspamd-Server: rspam03 X-HE-Tag: 1687888952-726888 X-HE-Meta: U2FsdGVkX18xbTn+gkhjjw9EHdRtFsSQcqMVKKGiXoinMxTt+pHpq3o+8I6xW2VVH/hEu68GKRG2ByBISUmBdEQ20geFhGVwGl2jepBLZ28ohTYXfsJrvbl5iw1DYbYREOOMwd1W6UTUL4lbPByMtZBInI2Jjjk/6Ett9oBHQdxZbWg4XF0bLWnxazVoYcYUbVX1gHTgcystm4ueDpoCmnQjvZofqEsyqnMQsD2XUjSnDxHpmpzxL4y8ozHVqY/jVN5d3H/QE6Rl5f3rfa8hQkZsREQAlnadK0mMVnpWpBNNQ6AMU2RjUMLzSYTlT9lwGoc0d8aAU7wf8s7Wov7sTkG2hcrvgJQPpdzfCcgKoPiEbi444aPzo7igV8iQ+zHSp1xBsQbb3KsEajdz0NGBaoaX4QrmDSfS5uvvTz9LrPT0nokMhEI8vixZCu+sVL6C2yTst39PrQGoY3CymIfvTBkId2dO+0o13HtmUsbSm/+jqdqmenOUs2Hn1kw6kNh4MJIE2daKSIog3CstcvWd/n/KqEuB2PguIZAUSlMOvu6lwQLvhkoWzJ9Cg9a+LzfJyQoPbqxXjowKYVosTukpwDd9z9MYtZDUom8xZu1mJLUP0mJ8yXqT7vgt3nGrg6DsQcuqK4S9u00w1z/BBQbINdiDuFiHz3DIngeg4VDdxgUvKshC2L871OO9RE6K+7Fq2eBgJ882raqZbUYo9hO97DKt9EViRmrsTM93l6hn8HKT+IwMj/x67uc+429DUA8TD2CYkSOQ27DBQbb/I6vAwNcwrce0KebRnmh9jzD3SO44AAT5BERFz/6N7CnPWnii1ZnS/ZZvNjqrqQseGu6+6Nt21HXL7kPRgj6IK6PZNeSRycm5kFznJzfNaHcKACyxAeSsxb8dmXF2i4LbMNAC6dns6ZA73ZtFSwxvmZ3T3BsUIG9t40XWZAnT0ge4P7c9fMv6/RKgJ0dkX2wJg9f do/qDUqc mYfqeTphX+Nlzc05aCFTpUMg2wvgh3128i/KTzZKuHVVas6j6+hSUihDGxqUQmV1W+M3IbJu4rkTVVGWm15TpRz8DwYXx+sMTr7Sd13RXr5Fl4J6JArbW4pke3goQMpsXVXWrUDFKkRO77MVfxmgdxAGJKvQJiGSqg/Hp2kShHNWXffSKSEPU+aKEMbPAn4B73IlQuYe/HpTbGh1jkllWVfSMU+xyl537OUMXpEY7irp30d5EH8df9ILKBE6xnimRsq2Yo8Hyn7fijb2g7Nz1boEu78idG61xpmjd57Qj8EBe5dU03H0LdyzY/X5a4MVxBmSp6Tj6zAYC4ewee1YMyd6/p54RK2jqjV8eCgpo2Jb5gJKfMh2v5vlHHmtUsKVj5YhYY9b0QmLGYG41OGC1MZQpktdb5cUL+ZXxFwgURzdS5tjuLIOV+XjSxwgrKMkLl3V3 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000238, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Tue, Jun 27, 2023 at 01:56:09PM -0400, Liam R. Howlett wrote: [snip] > > > How about something like:- > > > > > > return find_vma_intersection(vma->mm, addr_masked, vma->vm_start) == NULL; > > > > > > Which explicitly asserts that the range in [addr_masked, vma->vm_start) is > > > empty. > > > > > > But actually, we should be able to go further and replace the previous > > > check with:- > > > > > > return find_vma_intersection(vma->mm, addr_masked, addr_to_align) == NULL; > > > > > > Which will fail if addr_to_align is offset within the VMA. > > > > Your suggestion would mean that we do a full VMA search starting from the > > root. That would not be a nice thing if say we've 1000s of VMAs? > > > > Actually Liam told me to use find_vma_prev() because given a VMA, the maple > > tree would not have to work that hard for the common case to find the > > previous VMA. Per conversing with him, there is a chance we may have to go > > one step above in the tree if we hit the edge of a node, but that's not > > supposed to be the common case. In previous code, the previous VMA could > > just be obtained using the "previous VMA" pointer, however that pointer has > > been remove since the maple tree changes and given a VMA, going to the > > previous one using the maple tree is just as fast (as I'm told). > > I think there's been a bit of a miscommunication on that.. > > If you have already found the VMA and are using the maple state, then > it's very little effort to get the next/prev. Leaf nodes can hold 16 > entries/NULL ranges, so the chances to go to the next/prev is usually in > the cpu cache already.. if you go up a level in the tree, then you will > have 10 nodes each with 16 entries each, etc, etc.. So the chances of > being on an edge node and having to walk up multiple levels to get to > the prev/next becomes rather rare.. and if you've just walked down, the > nodes on the way up will still be cached. > > Here, you're not using the maple state but searching for an address > using find_vma_prev(), but internally, that function does use a maple > state to get you the previous. So you are looking up the VMA from the > root, but the prev will very likely be in the CPU cache. > > Assuming the worst case tree (each VMA has a gap next to it, not really > going to happen as they tend to be grouped together), then we are > looking at a 4 level tree to get to 8,000 VMAs. 5 levels gets you a > minimum 80,000. I've never seen a tree of height 6 in the wild, but you > can fit 1.6M to 800K in one. > > I think the code is fine, but I wanted to clarify what we discussed. Would the same apply to find_vma_intersection(), as they equally searches from the root and allows the code to be made fairly succinct? I really am not a huge fan of find_vma_prev() searching for a VMA you already have just to get the previous one... would at lesat like to use vma_prev() on a newly defined vmi, but if find_vma_intersection() is fine then can reduce code to this. [snip]