linux.git/include/linux/radix-tree.h, branch v4.7-rc4

radix-tree: free up the bottom bit of exceptional entries for reuse

2016-05-21T00:58:30+00:00

We are guaranteed that pointers to radix_tree_nodes always have the
bottom two bits clear (because they come from a slab cache, and slab
caches have a minimum alignment of sizeof(void *)), so we can redefine
'radix_tree_is_internal_node' to only return true if the bottom two bits
have value '01'.  This frees up one quarter of the potential values for
use by the user.

Idea from Neil Brown.

Signed-off-by: Matthew Wilcox 
Suggested-by: Neil Brown 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Ross Zwisler 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

dax: move RADIX_DAX_ definitions to dax.c

2016-05-21T00:58:30+00:00

These don't belong in radix-tree.h any more than PAGECACHE_TAG_* do.
Let's try to maintain the idea that radix-tree simply implements an
abstract data type.

Signed-off-by: NeilBrown 
Reviewed-by: Ross Zwisler 
Reviewed-by: Jan Kara 
Signed-off-by: Matthew Wilcox 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: introduce radix_tree_replace_clear_tags()

2016-05-21T00:58:30+00:00

In addition to replacing the entry, we also clear all associated tags.
This is really a one-off special for page_cache_tree_delete() which had
far too much detailed knowledge about how the radix tree works.

For efficiency, factor node_tag_clear() out of radix_tree_tag_clear() It
can be used by radix_tree_delete_item() as well as
radix_tree_replace_clear_tags().

Signed-off-by: Matthew Wilcox 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Cc: Ross Zwisler 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: rename radix_tree_is_indirect_ptr()

2016-05-21T00:58:30+00:00

As with indirect_to_ptr(), ptr_to_indirect() and
RADIX_TREE_INDIRECT_PTR, change radix_tree_is_indirect_ptr() to
radix_tree_is_internal_node().

Signed-off-by: Matthew Wilcox 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Cc: Ross Zwisler 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: rename indirect_to_ptr() to entry_to_node()

2016-05-21T00:58:30+00:00

Mirrors the earlier commit introducing node_to_entry().

Also change the type returned to be a struct radix_tree_node pointer.
That lets us simplify a couple of places in the radix tree shrink &
extend paths where we could convert an entry into a pointer, modify the
node, then convert the pointer back into an entry.

Signed-off-by: Matthew Wilcox 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Cc: Ross Zwisler 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: rename INDIRECT_PTR to INTERNAL_NODE

2016-05-21T00:58:30+00:00

The name RADIX_TREE_INDIRECT_PTR doesn't really match the meaning.
RADIX_TREE_INTERNAL_NODE is a better name.

Signed-off-by: Matthew Wilcox 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Cc: Ross Zwisler 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: remove root->height

2016-05-21T00:58:30+00:00

The only remaining references to root->height were in extend and shrink,
where it was updated.  Now we can remove it entirely.

Signed-off-by: Matthew Wilcox 
Reviewed-by: Ross Zwisler 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: replace node->height with node->shift

2016-05-21T00:58:30+00:00

node->shift represents the shift necessary for looking in the slots
array at this level.  It is equal to the old (node->height - 1) *
RADIX_TREE_MAP_SHIFT.

Signed-off-by: Matthew Wilcox 
Reviewed-by: Ross Zwisler 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: split node->path into offset and height

2016-05-21T00:58:30+00:00

Neither piece of information we're storing in node->path can be larger
than 64, so store each in its own unsigned char instead of shifting and
masking to store them both in an unsigned int.

Signed-off-by: Matthew Wilcox 
Reviewed-by: Ross Zwisler 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: add support for multi-order iterating

2016-05-21T00:58:30+00:00

This enables the macros radix_tree_for_each_slot() and friends to be
used with multi-order entries.

The way that this works is that we treat all entries in a given slots[]
array as a single chunk.  If the index given to radix_tree_next_chunk()
happens to point us to a sibling entry, we will back up iter->index so
that it points to the canonical entry, and that will be the place where
we start our iteration.

As we're processing a chunk in radix_tree_next_slot(), we process
canonical entries, skip over sibling entries, and restart the chunk
lookup if we find a non-sibling indirect pointer.  This drops back to
the radix_tree_next_chunk() code, which will re-walk the tree and look
for another chunk.

This allows us to properly handle multi-order entries mixed with other
entries that are at various heights in the radix tree.

Signed-off-by: Ross Zwisler 
Signed-off-by: Matthew Wilcox 
Cc: Konstantin Khlebnikov 
Cc: Kirill Shutemov 
Cc: Jan Kara 
Cc: Neil Brown 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds