Messages in this thread | | | Date | Tue, 03 Jul 2012 17:37:46 -0400 | From | Rik van Riel <> | Subject | Re: [PATCH -mm v2 01/11] mm: track free size between VMAs in VMA rbtree |
| |
On 06/29/2012 07:46 PM, Michel Lespinasse wrote:
I have the free_gap(node) function now.
>> rb_link_node(&vma->vm_rb, rb_parent, rb_link); >> rb_insert_color(&vma->vm_rb,&mm->mm_rb); >> + adjust_free_gap(vma); >> + /* Propagate the new free gap between next and us up the tree. */ >> + if (vma->vm_next) >> + adjust_free_gap(vma->vm_next); >> } > > So this will work, and may be fine for a first implementation. However, > the augmented rbtree support really seems inadequate here. What we > would want is for adjust_free_gap to adjust the node's free_gap as > well as its parents, and *stop* when it reaches a node that already > has the desired free_gap instead of going all the way to the root as > it does now. But, to do that we would also need rb_insert_color() to > adjust free_gap as needed when doing tree rotations, and it doesn't > have the necessary support there. > > Basically, I think lib/rbtree.c should provide augmented rbtree support > in the form of (versions of) rb_insert_color() and rb_erase() being able to > callback to adjust the augmented node information around tree rotations, > instead of using (conservative, overkill) loops to adjust the augmented > node information after the fact
That is what I originally worked on.
I threw out that code after people told me (at LSF/MM) in no uncertain terms that I should use the augmented rbtree code :)
Will CC you on the next version.
-- All rights reversed
| |