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

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

[Wei Yang]

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

[RESEND [PATCH] 1/2] mm/mmap.c: update *next* gap after itself

[Wei Yang]

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.

Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
---
 mm/mmap.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index aa66753b175e..672ad7dc6b3c 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -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

[RESEND [PATCH] 2/2] mm/mmap.c: unlink vma before rb_erase

[Wei Yang]

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.

Signed-off-by: Wei Yang <richardw.yang@linux.intel.com>
---
 mm/mmap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index 672ad7dc6b3c..907939690a30 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -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

Re: [RESEND [PATCH] 0/2] mm/mmap.c: reduce subtree gap propagation a little

[Vlastimil Babka]

On 8/28/19 8:06 AM, Wei Yang wrote:
> 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, 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?

> 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(-)
> 

Re: [RESEND [PATCH] 0/2] mm/mmap.c: reduce subtree gap propagation a little

[Wei Yang]

On Wed, Aug 28, 2019 at 10:01:40AM +0200, Vlastimil Babka wrote:
>On 8/28/19 8:06 AM, Wei Yang wrote:
>> 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, 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

Re: [RESEND [PATCH] 0/2] mm/mmap.c: reduce subtree gap propagation a little

[Wei Yang]

Any other comments for these two?

On Wed, Aug 28, 2019 at 02:06:12PM +0800, Wei Yang wrote:
>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

-- 
Wei Yang
Help you, Help me