• Matthew Wilcox's avatar
    radix-tree: improve multiorder iterators · 148deab2
    Matthew Wilcox authored
    This fixes several interlinked problems with the iterators in the
    presence of multiorder entries.
    
    1. radix_tree_iter_next() would only advance by one slot, which would
       result in the iterators returning the same entry more than once if
       there were sibling entries.
    
    2. radix_tree_next_slot() could return an internal pointer instead of
       a user pointer if a tagged multiorder entry was immediately followed by
       an entry of lower order.
    
    3. radix_tree_next_slot() expanded to a lot more code than it used to
       when multiorder support was compiled in.  And I wasn't comfortable with
       entry_to_node() being in a header file.
    
    Fixing radix_tree_iter_next() for the presence of sibling entries
    necessarily involves examining the contents of the radix tree, so we now
    need to pass 'slot' to radix_tree_iter_next(), and we need to change the
    calling convention so it is called *before* dropping the lock which
    protects the tree.  Also rename it to radix_tree_iter_resume(), as some
    people thought it was necessary to call radix_tree_iter_next() each time
    around the loop.
    
    radix_tree_next_slot() becomes closer to how it looked before multiorder
    support was introduced.  It only checks to see if the next entry in the
    chunk is a sibling entry or a pointer to a node; this should be rare
    enough that handling this case out of line is not a performance impact
    (and such impact is amortised by the fact that the entry we just
    processed was a multiorder entry).  Also, radix_tree_next_slot() used to
    force a new chunk lookup for untagged entries, which is more expensive
    than the out of line sibling entry skipping.
    
    Link: http://lkml.kernel.org/r/1480369871-5271-55-git-send-email-mawilcox@linuxonhyperv.comSigned-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
    Tested-by: default avatarKirill A. Shutemov <kirill.shutemov@linux.intel.com>
    Cc: Konstantin Khlebnikov <koct9i@gmail.com>
    Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
    Cc: Matthew Wilcox <mawilcox@microsoft.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    148deab2
regression3.c 2.95 KB