• Matthew Wilcox's avatar
    radix tree: use GFP_ZONEMASK bits of gfp_t for flags · fa290cda
    Matthew Wilcox authored
    Patch series "XArray", v9.  (First part thereof).
    
    This patchset is, I believe, appropriate for merging for 4.17.  It
    contains the XArray implementation, to eventually replace the radix
    tree, and converts the page cache to use it.
    
    This conversion keeps the radix tree and XArray data structures in sync
    at all times.  That allows us to convert the page cache one function at
    a time and should allow for easier bisection.  Other than renaming some
    elements of the structures, the data structures are fundamentally
    unchanged; a radix tree walk and an XArray walk will touch the same
    number of cachelines.  I have changes planned to the XArray data
    structure, but those will happen in future patches.
    
    Improvements the XArray has over the radix tree:
    
     - The radix tree provides operations like other trees do; 'insert' and
       'delete'. But what most users really want is an automatically
       resizing array, and so it makes more sense to give users an API that
       is like an array -- 'load' and 'store'. We still have an 'insert'
       operation for users that really want that semantic.
    
     - The XArray considers locking as part of its API. This simplifies a
       lot of users who formerly had to manage their own locking just for
       the radix tree. It also improves code generation as we can now tell
       RCU that we're holding a lock and it doesn't need to generate as much
       fencing code. The other advantage is that tree nodes can be moved
       (not yet implemented).
    
     - GFP flags are now parameters to calls which may need to allocate
       memory. The radix tree forced users to decide what the allocation
       flags would be at creation time. It's much clearer to specify them at
       allocation time.
    
     - Memory is not preloaded; we don't tie up dozens of pages on the off
       chance that the slab allocator fails. Instead, we drop the lock,
       allocate a new node and retry the operation. We have to convert all
       the radix tree, IDA and IDR preload users before we can realise this
       benefit, but I have not yet found a user which cannot be converted.
    
     - The XArray provides a cmpxchg operation. The radix tree forces users
       to roll their own (and at least four have).
    
     - Iterators take a 'max' parameter. That simplifies many users and will
       reduce the amount of iteration done.
    
     - Iteration can proceed backwards. We only have one user for this, but
       since it's called as part of the pagefault readahead algorithm, that
       seemed worth mentioning.
    
     - RCU-protected pointers are not exposed as part of the API. There are
       some fun bugs where the page cache forgets to use rcu_dereference()
       in the current codebase.
    
     - Value entries gain an extra bit compared to radix tree exceptional
       entries. That gives us the extra bit we need to put huge page swap
       entries in the page cache.
    
     - Some iterators now take a 'filter' argument instead of having
       separate iterators for tagged/untagged iterations.
    
    The page cache is improved by this:
    
     - Shorter, easier to read code
    
     - More efficient iterations
    
     - Reduction in size of struct address_space
    
     - Fewer walks from the top of the data structure; the XArray API
       encourages staying at the leaf node and conducting operations there.
    
    This patch (of 8):
    
    None of these bits may be used for slab allocations, so we can use them
    as radix tree flags as long as we mask them off before passing them to
    the slab allocator. Move the IDR flag from the high bits to the
    GFP_ZONEMASK bits.
    
    Link: http://lkml.kernel.org/r/20180313132639.17387-3-willy@infradead.orgSigned-off-by: default avatarMatthew Wilcox <mawilcox@microsoft.com>
    Acked-by: default avatarJeff Layton <jlayton@kernel.org>
    Cc: Darrick J. Wong <darrick.wong@oracle.com>
    Cc: Dave Chinner <david@fromorbit.com>
    Cc: Ryusuke Konishi <konishi.ryusuke@lab.ntt.co.jp>
    Cc: Will Deacon <will.deacon@arm.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    fa290cda
radix-tree.c 62.2 KB