linux/tools/testing/radix-tree, branch v4.8

radix tree test suite: Test radix_tree_replace_slot() for multiorder entries

2016-09-25T18:49:16Z

When we replace a multiorder entry, check that all indices reflect the new value. Also, compile the test suite with -O2, which shows other problems with the code due to some dodgy pointer operations in the radix tree code. Signed-off-by: Matthew Wilcox Signed-off-by: Linus Torvalds

tools/testing/radix-tree/linux/gfp.h: fix bitrotted value

2016-08-02T21:31:41Z

Apparently, the tools/testing version dates to a few flags ago, and we've sprouted 4 new ones since. Keep in sync with the value in the main tree... Link: http://lkml.kernel.org/r/23400.1469702675@turing-police.cc.vt.edu Signed-off-by: Valdis Kletnieks Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

testing/radix-tree: fix a macro expansion bug

2016-07-23T01:25:54Z

There are no parentheses around this macro and it causes a problem when we do: index = rand() % THRASH_SIZE; Link: http://lkml.kernel.org/r/20160715210953.GC19522@mwanda Signed-off-by: Dan Carpenter Acked-by: Ross Zwisler Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

radix-tree: tidy up next_chunk

2016-05-21T00:58:30Z

Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the name of the child node. Also use node_maxindex() where it makes sense. The 'rnode' variable was unnecessary; it doesn't overlap in usage with 'node', so we can just use 'node' the whole way through the function. Improve the testcase to start the walk from every index in the carefully constructed tree, and to accept any index within the range covered by the 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 radix_tree_is_indirect_ptr()

2016-05-21T00:58:30Z

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:30Z

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 test suite: remove dependencies on height

2016-05-21T00:58:30Z

verify_node() can use node->shift instead of the height. tree_verify_min_height() can be converted over to using node_maxindex() and shift_maxindex() instead of radix_tree_maxindex(). 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: fix radix_tree_dump() for multi-order entries

2016-05-21T00:58:30Z

- Print which indices are covered by every leaf entry - Print sibling entries - Print the node pointer instead of the slot entry - Build by default in userspace, and make it accessible to the test-suite 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

radix-tree: fix radix_tree_range_tag_if_tagged() for multiorder entries

2016-05-21T00:58:30Z

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: 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 test for radix_tree_locate_item()

2016-05-21T00:58:30Z

Add a unit test that provides coverage for the bug fixed in the commit entitled "radix-tree: rewrite radix_tree_locate_item fix" from Hugh Dickins. I've verified that this test fails before his patch due to miscalculated 'index' values in __locate() in lib/radix-tree.c, and passes with his fix. Link: http://lkml.kernel.org/r/1462307263-20623-1-git-send-email-ross.zwisler@linux.intel.com Signed-off-by: Ross Zwisler Cc: Hugh Dickins Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds