linux-toradex.git/include/linux/radix-tree.h, branch v4.8-rc1

radix-tree: fix comment about "exceptional" bits

2016-08-02T23:35:08+00:00

The bottom two bits of radix tree entries are reserved for special use
by the radix tree code itself.  A comment detailing their usage was
added by commit 3bcadd6fa6c4 ("radix-tree: free up the bottom bit of
exceptional entries for reuse")

This comment states that if the bottom two bits are '11', this means
that this is a locked exceptional entry.

It turns out that this bit combination was never actually used.  Radix
tree locking for DAX was indeed implemented, but it actually used the
third LSB:

  /* We use lowest available exceptional entry bit for locking */
  #define RADIX_DAX_ENTRY_LOCK (1 << RADIX_TREE_EXCEPTIONAL_SHIFT)

This locking code was also made specific to the DAX code instead of
being generally implemented in radix-tree.h.

So, fix the comment.

Link: http://lkml.kernel.org/r/1468997731-2155-1-git-send-email-ross.zwisler@linux.intel.com
Signed-off-by: Ross Zwisler 
Reviewed-by: Johannes Thumshirn 
Cc: Dave Chinner 
Cc: Jan Kara 
Cc: Konstantin Khlebnikov 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: implement radix_tree_maybe_preload_order()

2016-07-26T23:19:19+00:00

The new helper is similar to radix_tree_maybe_preload(), but tries to
preload number of nodes required to insert (1 << order) continuous
naturally-aligned elements.

This is required to push huge pages into pagecache.

Link: http://lkml.kernel.org/r/1466021202-61880-24-git-send-email-kirill.shutemov@linux.intel.com
Signed-off-by: Kirill A. Shutemov 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: fix radix_tree_iter_retry() for tagged iterators.

2016-07-23T01:25:54+00:00

radix_tree_iter_retry() resets slot to NULL, but it doesn't reset tags.
Then NULL slot and non-zero iter.tags passed to radix_tree_next_slot()
leading to crash:

  RIP: radix_tree_next_slot include/linux/radix-tree.h:473
    find_get_pages_tag+0x334/0x930 mm/filemap.c:1452
  ....
  Call Trace:
    pagevec_lookup_tag+0x3a/0x80 mm/swap.c:960
    mpage_prepare_extent_to_map+0x321/0xa90 fs/ext4/inode.c:2516
    ext4_writepages+0x10be/0x2b20 fs/ext4/inode.c:2736
    do_writepages+0x97/0x100 mm/page-writeback.c:2364
    __filemap_fdatawrite_range+0x248/0x2e0 mm/filemap.c:300
    filemap_write_and_wait_range+0x121/0x1b0 mm/filemap.c:490
    ext4_sync_file+0x34d/0xdb0 fs/ext4/fsync.c:115
    vfs_fsync_range+0x10a/0x250 fs/sync.c:195
    vfs_fsync fs/sync.c:209
    do_fsync+0x42/0x70 fs/sync.c:219
    SYSC_fdatasync fs/sync.c:232
    SyS_fdatasync+0x19/0x20 fs/sync.c:230
    entry_SYSCALL_64_fastpath+0x23/0xc1 arch/x86/entry/entry_64.S:207

We must reset iterator's tags to bail out from radix_tree_next_slot()
and go to the slow-path in radix_tree_next_chunk().

Fixes: 46437f9a554f ("radix-tree: fix race in gang lookup")
Link: http://lkml.kernel.org/r/1468495196-10604-1-git-send-email-aryabinin@virtuozzo.com
Signed-off-by: Andrey Ryabinin 
Reported-by: Dmitry Vyukov 
Acked-by: Konstantin Khlebnikov 
Cc: Matthew Wilcox 
Cc: Hugh Dickins 
Cc: Ross Zwisler 
Cc: 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

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