linux-toradex.git/tools/testing/radix-tree/linux/kernel.h, branch v4.9.16

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

raxix-tree: introduce CONFIG_RADIX_TREE_MULTIORDER

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

I've been receiving increasingly concerned notes from 0day about how
much my recent changes have been bloating the radix tree.  Make it
happier by only including multiorder support if
CONFIG_TRANSPARENT_HUGEPAGES is set.

This is an independent Kconfig option, so other radix tree users can
also set it if they have a need.

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 test suite: allow testing other fan-out values

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

The defines in regression2.c are already in radix-tree.h and duplicating
them in the test case makes experimenting with other values for the
fan-out harder than necessary.  Allow the user of the radix tree to
decide what the fan-out should be rather than fixing it to 8 for
non-kernel uses.

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

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

Fairly simple tests; add various items to the tree, then make sure we
can find them again.  Also check that a pointer that we know isn't in
the tree is not found.

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 test suite: fix build

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

Add an empty linux/init.h, and definitions for a few parts of the kernel
API either in use now, or to be used in the near future.  Start using the
common definitions in tools/include/linux, although more work needs to be
done here.

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 tests: add regression3 test

2016-03-17T22:09:34+00:00

After calling radix_tree_iter_retry(), 'slot' will be set to NULL.  This
can cause radix_tree_next_slot() to dereference the NULL pointer.  Add
Konstantin Khlebnikov's test to the regression framework.

Signed-off-by: Matthew Wilcox 
Reported-by: Konstantin Khlebnikov 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix tree test harness

2016-03-17T22:09:34+00:00

This code is mostly from Andrew Morton and Nick Piggin; tarball downloaded
from http://ozlabs.org/~akpm/rtth.tar.gz with sha1sum
0ce679db9ec047296b5d1ff7a1dfaa03a7bef1bd

Some small modifications were necessary to the test harness to fix the
build with the current Linux source code.

I also made minor modifications to automatically test the radix-tree.c
and radix-tree.h files that are in the current source tree, as opposed
to a copied and slightly modified version.  I am sure more could be done
to tidy up the harness, as well as adding more tests.

[koct9i@gmail.com: fix compilation]
Signed-off-by: Matthew Wilcox 
Cc: Shuah Khan 
Cc: Johannes Weiner 
Cc: Matthew Wilcox 
Cc: "Kirill A. Shutemov" 
Cc: Ross Zwisler 
Cc: Hugh Dickins 
Signed-off-by: Konstantin Khlebnikov 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds