[PATCH] mm: unmapped_area: visit left subtree more precisely

From: cee1
Date: Sat Sep 10 2016 - 12:40:06 EST


unmapped_area() tries to find an unmapped area between info.low_limit and
info.high_limit:

info.low_limit info.high_limit
^ ^
| |
_____|______________________________________________|_______
|_____|__1__|__________________________________|__2__|_______|
| |
V |
low_limit = info.low_limit + length V
high_limit = info.high_limit - length

The lowest possible unmapped_area is at 1)
The highest possible unmapped_area us at 2)

unmapped_are() will first try to find any gap which is:
- gap_start <= high_limit
- gap_end >= low_limit
- big enough, i.e. gap_end - gap_start >= length

The search starts from the lowest gap, up to the highest gap, that means
a rbtree In-order traversal.

In the old logic, it visits left subtree if:
- it has gaps big enough
- "the highest gap_end" of the node >= low_limit

It will be more precise, if it uses "the highest gap_end" of
the left subtree, which is vma->vm_prev->vm_start.
---
mm/mmap.c | 16 ++++++++++------
1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index ca9d91b..e65c04d 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -1630,19 +1630,25 @@ unsigned long unmapped_area(struct vm_unmapped_area_info *info)

while (true) {
/* Visit left subtree if it looks promising */
- gap_end = vma->vm_start;
- if (gap_end >= low_limit && vma->vm_rb.rb_left) {
+ if (vma->vm_rb.rb_left) {
struct vm_area_struct *left =
rb_entry(vma->vm_rb.rb_left,
struct vm_area_struct, vm_rb);
- if (left->rb_subtree_gap >= length) {
+
+ VM_BUG_ON(!vma->vm_prev);
+ gap_end = vma->vm_prev->vm_start;
+
+ if (gap_end >= low_limit &&
+ left->rb_subtree_gap >= length) {
vma = left;
continue;
}
}

- gap_start = vma->vm_prev ? vma->vm_prev->vm_end : 0;
check_current:
+ gap_start = vma->vm_prev ? vma->vm_prev->vm_end : 0;
+ gap_end = vma->vm_start;
+
/* Check if current node has a suitable gap */
if (gap_start > high_limit)
return -ENOMEM;
@@ -1668,8 +1674,6 @@ check_current:
vma = rb_entry(rb_parent(prev),
struct vm_area_struct, vm_rb);
if (prev == vma->vm_rb.rb_left) {
- gap_start = vma->vm_prev->vm_end;
- gap_end = vma->vm_start;
goto check_current;
}
}
--
2.3.2 (Apple Git-55)