• Davidlohr Bueso's avatar
    rbtree: cache leftmost node internally · cd9e61ed
    Davidlohr Bueso authored
    Patch series "rbtree: Cache leftmost node internally", v4.
    
    A series to extending rbtrees to internally cache the leftmost node such
    that we can have fast overlap check optimization for all interval tree
    users[1].  The benefits of this series are that:
    
    (i)   Unify users that do internal leftmost node caching.
    (ii)  Optimize all interval tree users.
    (iii) Convert at least two new users (epoll and procfs) to the new interface.
    
    This patch (of 16):
    
    Red-black tree semantics imply that nodes with smaller or greater (or
    equal for duplicates) keys always be to the left and right,
    respectively.  For the kernel this is extremely evident when considering
    our rb_first() semantics.  Enabling lookups for the smallest node in the
    tree in O(1) can save a good chunk of cycles in not having to walk down
    the tree each time.  To this end there are a few core users that
    explicitly do this, such as the scheduler and rtmutexes.  There is also
    the desire for interval trees to have this optimization allowing faster
    overlap checking.
    
    This patch introduces a new 'struct rb_root_cached' which is just the
    root with a cached pointer to the leftmost node.  The reason why the
    regular rb_root was not extended instead of adding a new structure was
    that this allows the user to have the choice between memory footprint
    and actual tree performance.  The new wrappers on top of the regular
    rb_root calls are:
    
     - rb_first_cached(cached_root) -- which is a fast replacement
         for rb_first.
    
     - rb_insert_color_cached(node, cached_root, new)
    
     - rb_erase_cached(node, cached_root)
    
    In addition, augmented cached interfaces are also added for basic
    insertion and deletion operations; which becomes important for the
    interval tree changes.
    
    With the exception of the inserts, which adds a bool for updating the
    new leftmost, the interfaces are kept the same.  To this end, porting rb
    users to the cached version becomes really trivial, and keeping current
    rbtree semantics for users that don't care about the optimization
    requires zero overhead.
    
    Link: http://lkml.kernel.org/r/20170719014603.19029-2-dave@stgolabs.netSigned-off-by: default avatarDavidlohr Bueso <dbueso@suse.de>
    Reviewed-by: default avatarJan Kara <jack@suse.cz>
    Acked-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    cd9e61ed
rbtree.txt 14.8 KB