linux-kernel - Re: [PATCH v4 1/7] mm/mremap: Optimize the start addresses in move_page

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Tue, 27 Jun 2023 16:28:30 -0400
From:   "Liam R. Howlett" <Liam.Howlett@...cle.com>
To:     Lorenzo Stoakes <lstoakes@...il.com>
Cc:     Joel Fernandes <joel@...lfernandes.org>,
        linux-kernel@...r.kernel.org,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        linux-kselftest@...r.kernel.org, linux-mm@...ck.org,
        Shuah Khan <shuah@...nel.org>,
        Vlastimil Babka <vbabka@...e.cz>,
        Michal Hocko <mhocko@...e.com>,
        Kirill A Shutemov <kirill@...temov.name>,
        "Paul E. McKenney" <paulmck@...nel.org>,
        Suren Baghdasaryan <surenb@...gle.com>,
        Kalesh Singh <kaleshsingh@...gle.com>,
        Lokesh Gidra <lokeshgidra@...gle.com>,
        Vineeth Pillai <vineeth@...byteword.org>
Subject: Re: [PATCH v4 1/7] mm/mremap: Optimize the start addresses in
 move_page_tables()

* Lorenzo Stoakes <lstoakes@...il.com> [230627 14:02]:
> 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 think so.

> 
> 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.

find_vma_intersection() will work as well.

> [snip]