lkml.org 
[lkml]   [2010]   [Jun]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    SubjectRe: [PATCH] rbtree: undo augmented damage -v2
    From
    Date
    On Tue, 2010-06-01 at 10:00 -0700, Venkatesh Pallipadi wrote:
    > I am not seeing how this can cover all the callbacks we will need to
    > maintain the augmented tree property. May be I am missing something.

    Yes, indeed, how about the below delta, which my eevdf code did do but I
    overlooked on the conversion to the PAT code.

    That removes the break as you said, but also adds code to update the
    child nodes when walking up the path.

    So in your rotation case:

    G P
    / \ --> / \
    P U N G
    / <-- \
    N U

    Say we take the right rotation, then the traversal up from N to P will
    find that since N was the left child of P and it has a right child (G)
    it will also update G.

    Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
    ---
    arch/x86/mm/pat_rbtree.c | 23 ++++++++++++-----------
    1 files changed, 12 insertions(+), 11 deletions(-)

    diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
    index f537087..ca19aae 100644
    --- a/arch/x86/mm/pat_rbtree.c
    +++ b/arch/x86/mm/pat_rbtree.c
    @@ -81,20 +81,21 @@ static void update_node_max_end(struct rb_node *node)
    /* Update 'subtree_max_end' for a node and all its ancestors */
    static void update_path_max_end(struct rb_node *node)
    {
    - u64 old_max_end, new_max_end;
    + struct rb_node *parent;

    - while (node) {
    - struct memtype *data = container_of(node, struct memtype, rb);
    -
    - old_max_end = data->subtree_max_end;
    - update_node_max_end(node);
    - new_max_end = data->subtree_max_end;
    +up:
    + update_node_max_end(node);
    + parent = rb_parent(node);
    + if (!parent)
    + return;

    - if (new_max_end == old_max_end)
    - break;
    + if (node == parent->rb_left && parent->rb_right)
    + update_node_max_end(parent->rb_right);
    + else if (parent->rb_left)
    + update_node_max_end(parent->rb_left);

    - node = rb_parent(node);
    - }
    + node = parent;
    + goto up;
    }

    /* Find the first (lowest start addr) overlapping range from rb tree */


    \
     
     \ /
      Last update: 2010-06-01 19:21    [W:0.023 / U:0.464 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site