kernel/lib/radix-tree.c, branch linux-5.1.y

radix tree: Don't return retry entries from lookup

2018-12-06T13:26:16Z

Commit 66ee620f06f9 ("idr: Permit any valid kernel pointer to be stored") changed the radix tree lookup so that it stops when reaching the bottom of the tree. However, the condition was added in the wrong place, making it possible to return retry entries to the caller. Reorder the tests to check for the retry entry before checking whether we're at the bottom of the tree. The retry entry should never be found in the tree root, so it's safe to defer the check until the end of the loop. Add a regression test to the test-suite to be sure this doesn't come back. Fixes: 66ee620f06f9 ("idr: Permit any valid kernel pointer to be stored") Reported-by: Greg Kurz Signed-off-by: Matthew Wilcox

radix tree: Remove multiorder support

2018-10-21T14:46:48Z

All users have now been converted to the XArray. Removing the support reduces code size and ensures new users will use the XArray instead. Signed-off-by: Matthew Wilcox

radix tree test suite: Convert tag_tagged_items to XArray

2018-10-21T14:46:45Z

The tag_tagged_items() function is supposed to test the page-writeback tagging code. Since that has been converted to the XArray, there's not much point in testing the radix tree's tagging code. This requires using the pthread mutex embedded in the xarray instead of an external lock, so remove the pthread mutexes which protect xarrays/radix trees. Also remove radix_tree_iter_tag_set() as this was the last user. Signed-off-by: Matthew Wilcox

radix tree: Remove radix_tree_clear_tags

2018-10-21T14:46:45Z

The page cache was the only user of this interface and it has now been converted to the XArray. Transform the test into a test of xas_init_marks(). Signed-off-by: Matthew Wilcox

radix tree: Remove radix_tree_maybe_preload_order

2018-10-21T14:46:45Z

This function was only used by the page cache which is now converted to the XArray. Signed-off-by: Matthew Wilcox

radix tree: Remove split/join code

2018-10-21T14:46:44Z

radix_tree_split and radix_tree_join were never used upstream. Remove them; if they're needed in future they will be replaced by XArray equivalents. Signed-off-by: Matthew Wilcox

radix tree: Remove radix_tree_update_node_t

2018-10-21T14:46:44Z

The only user of this functionality was the workingset code, and it's now been converted to the XArray. Remove __radix_tree_delete_node() entirely as it was also only used by the workingset code. Signed-off-by: Matthew Wilcox

shmem: Convert shmem_alloc_hugepage to XArray

2018-10-21T14:46:40Z

xa_find() is a slightly easier API to use than radix_tree_gang_lookup_slot() because it contains its own RCU locking. This commit removes the last user of radix_tree_gang_lookup_slot() so remove the function too. Signed-off-by: Matthew Wilcox

page cache: Add and replace pages using the XArray

2018-10-21T14:46:33Z

Use the XArray APIs to add and replace pages in the page cache. This removes two uses of the radix tree preload API and is significantly shorter code. It also removes the last user of __radix_tree_create() outside radix-tree.c itself, so make it static. Signed-off-by: Matthew Wilcox

ida: Convert to XArray

2018-10-21T14:46:33Z

Use the XA_TRACK_FREE ability to track which entries have a free bit, similarly to how it uses the radix tree's IDR_FREE tag. This eliminates the per-cpu ida_bitmap preload, and fixes the memory consumption regression I introduced when making the IDR able to store any pointer. Signed-off-by: Matthew Wilcox