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

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

[cee1]

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)

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

[cee1]

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)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>