* [PATCH 0/2] mm/mmap.c: reduce subtree gap propagation a little
@ 2019-08-26 7:31 Wei Yang
2019-08-26 7:31 ` [PATCH 1/2] mm/mmap.c: update *next* gap after itself Wei Yang
2019-08-26 7:31 ` [PATCH 2/2] mm/mmap.c: unlink vma before rb_erase Wei Yang
0 siblings, 2 replies; 3+ messages in thread
From: Wei Yang @ 2019-08-26 7:31 UTC (permalink / raw)
To: akpm, vbabka, kirill.shutemov, yang.shi; +Cc: linux-mm, linux-kernel, 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.4% function all for
vma_compute_subtree_gap.
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH 1/2] mm/mmap.c: update *next* gap after itself
2019-08-26 7:31 [PATCH 0/2] mm/mmap.c: reduce subtree gap propagation a little Wei Yang
@ 2019-08-26 7:31 ` Wei Yang
2019-08-26 7:31 ` [PATCH 2/2] mm/mmap.c: unlink vma before rb_erase Wei Yang
1 sibling, 0 replies; 3+ messages in thread
From: Wei Yang @ 2019-08-26 7:31 UTC (permalink / raw)
To: akpm, vbabka, kirill.shutemov, yang.shi; +Cc: linux-mm, linux-kernel, 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
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH 2/2] mm/mmap.c: unlink vma before rb_erase
2019-08-26 7:31 [PATCH 0/2] mm/mmap.c: reduce subtree gap propagation a little Wei Yang
2019-08-26 7:31 ` [PATCH 1/2] mm/mmap.c: update *next* gap after itself Wei Yang
@ 2019-08-26 7:31 ` Wei Yang
1 sibling, 0 replies; 3+ messages in thread
From: Wei Yang @ 2019-08-26 7:31 UTC (permalink / raw)
To: akpm, vbabka, kirill.shutemov, yang.shi; +Cc: linux-mm, linux-kernel, 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
^ permalink raw reply related [flat|nested] 3+ messages in thread
end of thread, other threads:[~2019-08-26 7:31 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-08-26 7:31 [PATCH 0/2] mm/mmap.c: reduce subtree gap propagation a little Wei Yang
2019-08-26 7:31 ` [PATCH 1/2] mm/mmap.c: update *next* gap after itself Wei Yang
2019-08-26 7:31 ` [PATCH 2/2] mm/mmap.c: unlink vma before rb_erase Wei Yang
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).