• Johannes Weiner's avatar
    lib: radix-tree: native accounting of exceptional entries · f7942430
    Johannes Weiner authored
    The way the page cache is sneaking shadow entries of evicted pages into
    the radix tree past the node entry accounting and tracking them manually
    in the upper bits of node->count is fraught with problems.
    
    These shadow entries are marked in the tree as exceptional entries,
    which are a native concept to the radix tree.  Maintain an explicit
    counter of exceptional entries in the radix tree node.  Subsequent
    patches will switch shadow entry tracking over to that counter.
    
    DAX and shmem are the other users of exceptional entries.  Since slot
    replacements that change the entry type from regular to exceptional must
    now be accounted, introduce a __radix_tree_replace() function that does
    replacement and accounting, and switch DAX and shmem over.
    
    The increase in radix tree node size is temporary.  A followup patch
    switches the shadow tracking to this new scheme and we'll no longer need
    the upper bits in node->count and shrink that back to one byte.
    
    Link: http://lkml.kernel.org/r/20161117192945.GA23430@cmpxchg.orgSigned-off-by: default avatarJohannes Weiner <hannes@cmpxchg.org>
    Reviewed-by: default avatarJan Kara <jack@suse.cz>
    Cc: Kirill A. Shutemov <kirill.shutemov@linux.intel.com>
    Cc: Hugh Dickins <hughd@google.com>
    Cc: Matthew Wilcox <mawilcox@linuxonhyperv.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    f7942430
shmem.c 106 KB