• Peter Zijlstra's avatar
    rbtree: Undo augmented trees performance damage and regression · b945d6b2
    Peter Zijlstra authored
    Reimplement augmented RB-trees without sprinkling extra branches
    all over the RB-tree code (which lives in the scheduler hot path).
    
    This approach is 'borrowed' from Fabio's BFQ implementation and
    relies on traversing the rebalance path after the RB-tree-op to
    correct the heap property for insertion/removal and make up for
    the damage done by the tree rotations.
    
    For insertion the rebalance path is trivially that from the new
    node upwards to the root, for removal it is that from the deepest
    node in the path from the to be removed node that will still
    be around after the removal.
    
    [ This patch also fixes a video driver regression reported by
      Ali Gholami Rudi - the memtype->subtree_max_end was updated
      incorrectly. ]
    Acked-by: default avatarSuresh Siddha <suresh.b.siddha@intel.com>
    Acked-by: default avatarVenkatesh Pallipadi <venki@google.com>
    Signed-off-by: default avatarPeter Zijlstra <a.p.zijlstra@chello.nl>
    Tested-by: default avatarAli Gholami Rudi <ali@rudi.ir>
    Cc: Fabio Checconi <fabio@gandalf.sssup.it>
    Cc: "H. Peter Anvin" <hpa@zytor.com>
    Cc: Andrew Morton <akpm@linux-foundation.org>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    LKML-Reference: <1275414172.27810.27961.camel@twins>
    Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
    b945d6b2
rbtree.c 9.95 KB