From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755712AbcIJQjh (ORCPT ); Sat, 10 Sep 2016 12:39:37 -0400 Received: from mail-pf0-f195.google.com ([209.85.192.195]:33715 "EHLO mail-pf0-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751699AbcIJQje (ORCPT ); Sat, 10 Sep 2016 12:39:34 -0400 From: cee1 To: linux-mm@kvack.org Cc: linux-kernel@vger.kernel.org, cee1 Subject: [PATCH] mm: unmapped_area: visit left subtree more precisely Date: Sun, 11 Sep 2016 00:39:23 +0800 Message-Id: <1473525563-20703-1-git-send-email-fykcee1@gmail.com> X-Mailer: git-send-email 2.3.2 (Apple Git-55) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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)