• Matthew Wilcox's avatar
    radix_tree: add support for multi-order entries · e6145236
    Matthew Wilcox authored
    With huge pages, it is convenient to have the radix tree be able to
    return an entry that covers multiple indices.  Previous attempts to deal
    with the problem have involved inserting N duplicate entries, which is a
    waste of memory and leads to problems trying to handle aliased tags, or
    probing the tree multiple times to find alternative entries which might
    cover the requested index.
    This approach inserts one canonical entry into the tree for a given
    range of indices, and may also insert other entries in order to ensure
    that lookups find the canonical entry.
    This solution only tolerates inserting powers of two that are greater
    than the fanout of the tree.  If we wish to expand the radix tree's
    abilities to support large-ish pages that is less than the fanout at the
    penultimate level of the tree, then we would need to add one more step
    in lookup to ensure that any sibling nodes in the final level of the
    tree are dereferenced and we return the canonical entry that they
    Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
    Cc: Johannes Weiner <hannes@cmpxchg.org>
    Cc: Matthew Wilcox <willy@linux.intel.com>
    Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
    Cc: Ross Zwisler <ross.zwisler@linux.intel.com>
    Cc: Hugh Dickins <hughd@google.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
filemap.c 76.2 KB