Re: [RFC PATCH 1/6] mm: augment vma rbtree with rb_subtree_gap

[Rik van Riel <riel@redhat.com>]

On 10/31/2012 06:33 AM, Michel Lespinasse wrote:
> 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: Michel Lespinasse <walken@google.com>

Reviewed-by: Rik van Riel <riel@redhat.com>

-- 
All rights reversed

--
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>