0/2] mm/mmap.c: reduce subtree gap propagation a little

When insert and delete a vma, it will compute and propagate related subtree gap. After some investigation, we can reduce subtree gap propagation a little.

[1]: This one reduce the propagation by update *next* gap after itself, since
*next* must be a parent in this case.
[2]: This one achieve this by unlinking vma from list.

After applying these two patches, test shows it reduce 0.3% function call for vma_compute_subtree_gap.

BTW, this series is based on some un-merged cleanup patched.

---
This version is rebased on current linus tree, whose last commit is commit 9e8312f5e160 ("Merge tag 'nfs-for-5.3-3' of
git://git.linux-nfs.org/projects/trondmy/linux-nfs").

Wei Yang (2):
mm/mmap.c: update *next* gap after itself
mm/mmap.c: unlink vma before rb_erase

 mm/mmap.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

2.17.1

Since we link a vma to the leaf of a rb_tree, *next* must be a parent of vma if *next* is not NULL. This means if we update *next* gap first, it will be re-update again if vma's gap is bigger.

For example, we have a vma tree like this:

                a
                [0x9000, 0x10000]
            /            \
        b                 c
        [0x8000, 0x9000]  [0x10000, 0x11000]

The gap for each node is:

a's gap = 0x8000
b's gap = 0x8000
c's gap = 0x0

Now we want to insert d [0x6000, 0x7000], then the tree look like this:

                a
                [0x9000, 0x10000]
            /            \
        b                 c
        [0x8000, 0x9000]  [0x10000, 0x11000]
     /
    d
    [0x6000, 0x7000]

b is the *next* of d. If we update b's gap first, it would be 0x1000 and propagate to a. And then when update d's gap, which is 0x6000 and propagate through b to a again.

If we update d's gap first, the un-consistent gap 0x1000 will not be propagated.

---
 mm/mmap.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

index aa66753b175e..672ad7dc6b3c 100644
@@ -587,12 +587,6 @@ static unsigned long count_vma_pages_range(struct mm_struct *mm,
 void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
 		struct rb_node **rb_link, struct rb_node *rb_parent)
 {
-	/* Update tracking information for the gap following the new vma. */
-	if (vma->vm_next)
-		vma_gap_update(vma->vm_next);
-	else
-		mm->highest_vm_end = vm_end_gap(vma);
-
 	/*
 	 * vma->vm_prev wasn't known when we followed the rbtree to find the
 	 * correct insertion point for that vma. As a result, we could not

@@ -605,6 +599,13 @@ void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
 	rb_link_node(&vma->vm_rb, rb_parent, rb_link);
 	vma->rb_subtree_gap = 0;
 	vma_gap_update(vma);
+
+	/* Update tracking information for the gap following the new vma. */
+	if (vma->vm_next)
+		vma_gap_update(vma->vm_next);
+	else
+		mm->highest_vm_end = vm_end_gap(vma);
+
 	vma_rb_insert(vma, &mm->mm_rb);
 }
 

2.17.1

Current sequence to remove a vma is:

vma_rb_erase_ignore()
__vma_unlink_list()
vma_gap_update()

This may do some extra subtree_gap propagation due the vma is unlink from list after rb_erase.

For example, we have a tree:

                    a
                    [0x9000, 0x10000]
                /            \
            b                 c
            [0x8000, 0x9000]  [0x10000, 0x11000]
         /
        d
        [0x6000, 0x7000]

The gap for each node is:

a's gap = 0x6000
b's gap = 0x6000
c's gap = 0x0
d's gap = 0x6000

Now we want to remove node d. Since we don't unlink d from link when doing rb_erase, b's gap would still be computed to 0x1000. This leads to the vma_gap_update() after list unlink would recompute b and a's gap.

For this case, by unlink the list before rb_erase, we would have one time less of vma_compute_subtree_gap.

---
 mm/mmap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 672ad7dc6b3c..907939690a30 100644
@@ -678,8 +678,8 @@ static __always_inline void __vma_unlink_common(struct mm_struct *mm,
 						struct vm_area_struct *vma,
 						struct vm_area_struct *ignore)
 {
-	vma_rb_erase_ignore(vma, &mm->mm_rb, ignore);
 	__vma_unlink_list(mm, vma);
+	vma_rb_erase_ignore(vma, &mm->mm_rb, ignore);
 	/* Kill the cache */
 	vmacache_invalidate(mm);
 }

2.17.1

BTW, what's the overall motivation of focusing so much micro-optimization effort on the vma tree lately? This has been rather stable code where we can be reasonably sure of all bugs being found. Now even after some review effort, subtle bugs can be introduced. And Matthew was warning for a while about an upcoming major rewrite of the whole data structure, which will undo all this effort?

Hi, Vlastimil

Thanks for your comment.

I just found there could be some refine for the code and then I modify and test it. Hope this could help a little.

You concern is valid. The benefits / cost may be not that impressive. The community have the final decision. For me, I just want to make it better if we can.

Wei Yang
Help you, Help me

Any other comments for these two?

Wei Yang
Help you, Help me