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]