• Matthew Wilcox's avatar
    radix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries · 070c5ac2
    Matthew Wilcox authored
    I had previously decided that tagging a single multiorder entry would
    count as tagging 2^order entries for the purposes of 'nr_to_tag'.  I now
    believe that decision to be a mistake, and it should count as a single
    entry.  That's more likely to be what callers expect.
    
    When walking back up the tree from a newly-tagged entry, the current
    code assumed we were starting from the lowest level of the tree; if we
    have a multiorder entry with an order at least RADIX_TREE_MAP_SHIFT in
    size then we need to shift the index by 'shift' before we start walking
    back up the tree, or we will end up not setting tags on higher entries,
    and then mistakenly thinking that entries below a certain point in the
    tree are not tagged.
    
    If the first index we examine is a sibling entry of a tagged multiorder
    entry, we were not tagging it.  We need to examine the canonical entry,
    and the easiest way to do that is to use radix_tree_descend().  We then
    have to skip over sibling slots when looking for the next entry in the
    tree or we will end up walking back to the canonical entry.
    
    Add several tests for radix_tree_range_tag_if_tagged().
    Signed-off-by: default avatarMatthew Wilcox <willy@linux.intel.com>
    Reviewed-by: default avatarRoss Zwisler <ross.zwisler@linux.intel.com>
    Cc: Konstantin Khlebnikov <koct9i@gmail.com>
    Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
    Cc: Jan Kara <jack@suse.com>
    Cc: Neil Brown <neilb@suse.de>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    070c5ac2
radix-tree.c 44 KB