1. 15 Dec, 2017 1 commit
  2. 09 Sep, 2017 3 commits
    • Davidlohr Bueso's avatar
      rbtree: add some additional comments for rebalancing cases · 35dc67d7
      Davidlohr Bueso authored
      While overall the code is very nicely commented, it might not be
      immediately obvious from the diagrams what is going on.  Add a very
      brief summary of each case.  Opposite cases where the node is the left
      child are left untouched.
      
      Link: http://lkml.kernel.org/r/20170719014603.19029-4-dave@stgolabs.netSigned-off-by: default avatarDavidlohr Bueso <dbueso@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      35dc67d7
    • Davidlohr Bueso's avatar
      rbtree: optimize root-check during rebalancing loop · 2aadf7fc
      Davidlohr Bueso authored
      The only times the nil-parent (root node) condition is true is when the
      node is the first in the tree, or after fixing rbtree rule #4 and the
      case 1 rebalancing made the node the root.  Such conditions do not apply
      most of the time:
      
      (i) The common case in an rbtree is to have more than a single node,
          so this is only true for the first rb_insert().
      
      (ii) While there is a chance only one first rotation is needed, cases
          where the node's uncle is black (cases 2,3) are more common as we can
          have the following scenarios during the rotation looping:
      
          case1 only, case1+1, case2+3, case1+2+3, case3 only, etc.
      
      This patch, therefore, adds an unlikely() optimization to this
      conditional.  When profiling with CONFIG_PROFILE_ANNOTATED_BRANCHES, a
      kernel build shows that the incorrect rate is less than 15%, and for
      workloads that involve insert mostly trees overtime tend to have less
      than 2% incorrect rate.
      
      Link: http://lkml.kernel.org/r/20170719014603.19029-3-dave@stgolabs.netSigned-off-by: default avatarDavidlohr Bueso <dbueso@suse.de>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      2aadf7fc
    • 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
  3. 25 Feb, 2017 1 commit
  4. 13 Dec, 2016 1 commit
  5. 06 Jul, 2016 1 commit
  6. 28 May, 2015 1 commit
    • Peter Zijlstra's avatar
      rbtree: Make lockless searches non-fatal · d72da4a4
      Peter Zijlstra authored
      Change the insert and erase code such that lockless searches are
      non-fatal.
      
      In and of itself an rbtree cannot be correctly searched while
      in-modification, we can however provide weaker guarantees that will
      allow the rbtree to be used in conjunction with other techniques, such
      as latches; see 9b0fd802 ("seqcount: Add raw_write_seqcount_latch()").
      
      For this to work we need the following guarantees from the rbtree
      code:
      
       1) a lockless reader must not see partial stores, this would allow it
          to observe nodes that are invalid memory.
      
       2) there must not be (temporary) loops in the tree structure in the
          modifier's program order, this would cause a lookup which
          interrupts the modifier to get stuck indefinitely.
      
      For 1) we must use WRITE_ONCE() for all updates to the tree structure;
      in particular this patch only does rb_{left,right} as those are the
      only element required for simple searches.
      
      It generates slightly worse code, probably because volatile. But in
      pointer chasing heavy code a few instructions more should not matter.
      
      For 2) I have carefully audited the code and drawn every intermediate
      link state and not found a loop.
      
      Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
      Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Reviewed-by: default avatarMichel Lespinasse <walken@google.com>
      Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
      Signed-off-by: default avatarRusty Russell <rusty@rustcorp.com.au>
      d72da4a4
  7. 08 Aug, 2014 1 commit
  8. 11 Sep, 2013 1 commit
    • Cody P Schafer's avatar
      rbtree: add postorder iteration functions · 9dee5c51
      Cody P Schafer authored
      Postorder iteration yields all of a node's children prior to yielding the
      node itself, and this particular implementation also avoids examining the
      leaf links in a node after that node has been yielded.
      
      In what I expect will be its most common usage, postorder iteration allows
      the deletion of every node in an rbtree without modifying the rbtree nodes
      (no _requirement_ that they be nulled) while avoiding referencing child
      nodes after they have been "deleted" (most commonly, freed).
      
      I have only updated zswap to use this functionality at this point, but
      numerous bits of code (most notably in the filesystem drivers) use a hand
      rolled postorder iteration that NULLs child links as it traverses the
      tree.  Each of those instances could be replaced with this common
      implementation.
      
      1 & 2 add rbtree postorder iteration functions.
      3 adds testing of the iteration to the rbtree runtime tests
      4 allows building the rbtree runtime tests as builtins
      5 updates zswap.
      
      This patch:
      
      Add postorder iteration functions for rbtree.  These are useful for safely
      freeing an entire rbtree without modifying the tree at all.
      Signed-off-by: default avatarCody P Schafer <cody@linux.vnet.ibm.com>
      Reviewed-by: default avatarSeth Jennings <sjenning@linux.vnet.ibm.com>
      Cc: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Michel Lespinasse <walken@google.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      9dee5c51
  9. 11 Jan, 2013 1 commit
  10. 09 Oct, 2012 17 commits
  11. 07 Mar, 2012 1 commit
  12. 28 Jan, 2011 1 commit
  13. 05 Jul, 2010 1 commit
    • 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
  14. 18 Feb, 2010 1 commit
  15. 17 Jun, 2009 3 commits
  16. 01 Apr, 2009 1 commit
  17. 10 Jan, 2009 1 commit
  18. 30 Sep, 2006 1 commit
  19. 05 Jun, 2006 1 commit
  20. 21 Apr, 2006 1 commit