kernel/tools/testing/radix-tree, branch linux-5.1.y

idr: Fix idr_get_next race with idr_remove

2019-07-10T07:52:21Z

commit 5c089fd0c73411f2170ab795c9ffc16718c7d007 upstream. If the entry is deleted from the IDR between the call to radix_tree_iter_find() and rcu_dereference_raw(), idr_get_next() will return NULL, which will end the iteration prematurely. We should instead continue to the next entry in the IDR. This only happens if the iteration is protected by the RCU lock. Most IDR users use a spinlock or semaphore to exclude simultaneous modifications. It was noticed once the PID allocator was converted to use the IDR, as it uses the RCU lock, but there may be other users elsewhere in the kernel. We can't use the normal pattern of calling radix_tree_deref_retry() (which catches both a retry entry in a leaf node and a node entry in the root) as the IDR supports storing entries which are unaligned, which will trigger an infinite loop if they are encountered. Instead, we have to explicitly check whether the entry is a retry entry. Fixes: 0a835c4f090a ("Reimplement IDR and IDA using the radix tree") Reported-by: Brendan Gregg Tested-by: Brendan Gregg Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Greg Kroah-Hartman

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: Convert multiorder tests to XArray

2018-10-21T14:46:48Z

This is the last remaining user of the multiorder functionality of the radix tree. Test the XArray instead. Signed-off-by: Matthew Wilcox

radix tree tests: Convert item_delete_rcu to XArray

2018-10-21T14:46:48Z

In preparation for the removal of the multiorder radix tree code, convert item_delete_rcu() to use the XArray so it can still be called for XArrays containing multi-index entries. Signed-off-by: Matthew Wilcox

radix tree tests: Convert item_kill_tree to XArray

2018-10-21T14:46:47Z

In preparation for the removal of the multiorder radix tree code, convert item_kill_tree() to use the XArray so it can still be called for XArrays containing multi-index entries. Signed-off-by: Matthew Wilcox

radix tree tests: Move item_insert_order

2018-10-21T14:46:47Z

The remaining tests are not suitable for moving in-kernel, so move item_insert_order() into multiorder.c, make it static and make it use the XArray. Signed-off-by: Matthew Wilcox

radix tree test suite: Remove multiorder benchmarking

2018-10-21T14:46:47Z

The multiorder radix tree code is being removed, so remove the benchmarking of its performance. Signed-off-by: Matthew Wilcox

radix tree test suite: Remove __item_insert

2018-10-21T14:46:47Z

Inline it into its one caller Signed-off-by: Matthew Wilcox

xarray: Move multiorder_check to in-kernel tests

2018-10-21T14:46:46Z

This version is a little less thorough in order to be a little quicker, but tests the important edge cases. Also test adding a multiorder entry at a non-canonical index, and erasing it. Signed-off-by: Matthew Wilcox