linux-stable.git/tools/testing/radix-tree/linux/kernel.h, branch v4.12.2

radix tree test suite: Add config option for map shift

2017-02-14T02:44:10+00:00

Add config option "SHIFT=" to Makefile for building test suite
with any value of RADIX_TREE_MAP_SHIFT between 3 and 7 inclusive.

Signed-off-by: Rehas Sachdeva 
[mawilcox@microsoft.com: .gitignore, quieten grep, remove on clean]
Signed-off-by: Matthew Wilcox

ida: Move ida_bitmap to a percpu variable

2017-02-14T02:44:01+00:00

When we preload the IDA, we allocate an IDA bitmap.  Instead of storing
that preallocated bitmap in the IDA, we store it in a percpu variable.
Generally there are more IDAs in the system than CPUs, so this cuts down
on the number of preallocated bitmaps that are unused, and about half
of the IDA users did not call ida_destroy() so they were leaking IDA
bitmaps.

Signed-off-by: Matthew Wilcox

Reimplement IDR and IDA using the radix tree

2017-02-14T02:44:01+00:00

The IDR is very similar to the radix tree.  It has some functionality that
the radix tree did not have (alloc next free, cyclic allocation, a
callback-based for_each, destroy tree), which is readily implementable on
top of the radix tree.  A few small changes were needed in order to use a
tag to represent nodes with free space below them.  More extensive
changes were needed to support storing NULL as a valid entry in an IDR.
Plain radix trees still interpret NULL as a not-present entry.

The IDA is reimplemented as a client of the newly enhanced radix tree.  As
in the current implementation, it uses a bitmap at the last level of the
tree.

Signed-off-by: Matthew Wilcox 
Signed-off-by: Matthew Wilcox 
Tested-by: Kirill A. Shutemov 
Cc: Konstantin Khlebnikov 
Cc: Ross Zwisler 
Cc: Tejun Heo 
Signed-off-by: Andrew Morton

radix tree test suite: Reduce kernel.h

2017-02-13T21:09:42+00:00

Many of the definitions in the radix-tree kernel.h are redundant with
others in tools/include, or are no longer used, such as panic().
Move the definition of __init to init.h and in_interrupt() to preempt.h

Signed-off-by: Matthew Wilcox

tools: Provide a definition of WARN_ON

2017-01-28T02:29:39+00:00

The definition of WARN_ON being used by the radix tree test suite was
deficient in two ways: it did not provide a return value, and it stopped
execution instead of continuing.  This version of WARN_ON tells you
which file & line the assertion was triggered in.

Signed-off-by: Matthew Wilcox

radix tree test suite: Remove duplicate bitops code

2017-01-28T02:29:39+00:00

By adding __set_bit and __clear_bit to the tools include directory, we
can share the bitops code.  This reveals an include loop between kernel.h,
log2.h, bitmap.h and bitops.h.  Break it the same way as the kernel does;
by moving the kernel.h include from bitops.h to bitmap.h.

Signed-off-by: Matthew Wilcox

radix tree test suite: add some more functionality

2016-12-15T00:04:10+00:00

IDR needs more functionality from the kernel: kmalloc()/kfree(), and
xchg().

Link: http://lkml.kernel.org/r/1480369871-5271-67-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox 
Tested-by: Kirill A. Shutemov 
Cc: Konstantin Khlebnikov 
Cc: Ross Zwisler 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix tree test suite: use common find-bit code

2016-12-15T00:04:10+00:00

Remove the old find_next_bit code in favour of linking in the find_bit
code from tools/lib.

Link: http://lkml.kernel.org/r/1480369871-5271-48-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox 
Tested-by: Kirill A. Shutemov 
Cc: Konstantin Khlebnikov 
Cc: Ross Zwisler 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

radix tree test suite: benchmark for iterator

2016-12-15T00:04:09+00:00

This adds simple benchmark for iterator similar to one I've used for
commit 78c1d78488a3 ("radix-tree: introduce bit-optimized iterator")

Building with make BENCHMARK=1 set radix tree order to 6, this allows to
get performance comparable to in kernel performance.

Link: http://lkml.kernel.org/r/1480369871-5271-43-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Konstantin Khlebnikov 
Signed-off-by: Matthew Wilcox 
Tested-by: Kirill A. Shutemov 
Cc: Ross Zwisler 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

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