• M
    mm: augment vma rbtree with rb_subtree_gap · d3737187
    Michel Lespinasse 提交于
    Define vma->rb_subtree_gap as the largest gap between any vma in the
    subtree rooted at that vma, and their predecessor.  Or, for a recursive
    definition, vma->rb_subtree_gap is the max of:
    
     - vma->vm_start - vma->vm_prev->vm_end
     - rb_subtree_gap fields of the vmas pointed by vma->rb.rb_left and
       vma->rb.rb_right
    
    This will allow get_unmapped_area_* to find a free area of the right
    size in O(log(N)) time, instead of potentially having to do a linear
    walk across all the VMAs.
    
    Also define mm->highest_vm_end as the vm_end field of the highest vma,
    so that we can easily check if the following gap is suitable.
    
    This does have the potential to make unmapping VMAs more expensive,
    especially for processes with very large numbers of VMAs, where the VMA
    rbtree can grow quite deep.
    Signed-off-by: NMichel Lespinasse <walken@google.com>
    Reviewed-by: NRik van Riel <riel@redhat.com>
    Cc: Hugh Dickins <hughd@google.com>
    Cc: Russell King <linux@arm.linux.org.uk>
    Cc: Ralf Baechle <ralf@linux-mips.org>
    Cc: Paul Mundt <lethal@linux-sh.org>
    Cc: "David S. Miller" <davem@davemloft.net>
    Cc: Chris Metcalf <cmetcalf@tilera.com>
    Cc: Ingo Molnar <mingo@elte.hu>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: "H. Peter Anvin" <hpa@zytor.com>
    Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
    d3737187
mmap.c 74.8 KB