• Hugh Dickins's avatar
    radix_tree: exceptional entries and indices · 6328650b
    Hugh Dickins authored
    A patchset to extend tmpfs to MAX_LFS_FILESIZE by abandoning its
    peculiar swap vector, instead keeping a file's swap entries in the same
    radix tree as its struct page pointers: thus saving memory, and
    simplifying its code and locking.
    
    This patch:
    
    The radix_tree is used by several subsystems for different purposes.  A
    major use is to store the struct page pointers of a file's pagecache for
    memory management.  But what if mm wanted to store something other than
    page pointers there too?
    
    The low bit of a radix_tree entry is already used to denote an indirect
    pointer, for internal use, and the unlikely radix_tree_deref_retry()
    case.
    
    Define the next bit as denoting an exceptional entry, and supply inline
    functions radix_tree_exception() to return non-0 in either unlikely
    case, and radix_tree_exceptional_entry() to return non-0 in the second
    case.
    
    If a subsystem already uses radix_tree with that bit set, no problem: it
    does not affect internal workings at all, but is defined for the
    convenience of those storing well-aligned pointers in the radix_tree.
    
    The radix_tree_gang_lookups have an implicit assumption that the caller
    can deduce the offset of each entry returned e.g.  by the page->index of
    a struct page.  But that may not be feasible for some kinds of item to
    be stored there.
    
    radix_tree_gang_lookup_slot() allow for an optional indices argument,
    output array in which to return those offsets.  The same could be added
    to other radix_tree_gang_lookups, but for now keep it to the only one
    for which we need it.
    Signed-off-by: default avatarHugh Dickins <hughd@google.com>
    Acked-by: default avatarRik van Riel <riel@redhat.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    6328650b
radix-tree.c 37.3 KB