linux-toradex.git/tools/testing/radix-tree/linux, branch v6.11-rc5

tools: fix userspace compilation with new test_xarray changes

2024-05-06T00:28:05+00:00

Patch series "test_xarray: couple of fixes for v6-9-rc6", v2.

Here are a couple of fixes which should be merged into the queue for
v6.9-rc6.  The first one was reported by Liam, after fixing that I noticed
an issue with a test, and a fix for that is in the second patch.


This patch (of 2):

Liam reported that compiling the test_xarray on userspace was broken.  I
was not even aware that was possible but you can via and you can run these
tests in userspace with:

make -C tools/testing/radix-tree
./tools/testing/radix-tree/xarray

Add the two helpers we need to fix compilation.  We don't need a userspace
schedule() so just make it do nothing.

Link: https://lkml.kernel.org/r/20240423192221.301095-1-mcgrof@kernel.org
Link: https://lkml.kernel.org/r/20240423192221.301095-2-mcgrof@kernel.org
Fixes: a60cc288a1a2 ("test_xarray: add tests for advanced multi-index use")
Signed-off-by: Luis Chamberlain 
Reported-by: "Liam R. Howlett" 
Cc: Daniel Gomez 
Cc: Darrick J. Wong 
Cc: Dave Chinner 
Cc: Matthew Wilcox (Oracle) 
Cc: Pankaj Raghav 
Signed-off-by: Andrew Morton

maple_tree: move debug check to __mas_set_range()

2023-12-12T18:56:57+00:00

__mas_set_range() was created to shortcut resetting the maple state and a
debug check was added to the caller (the vma iterator) to ensure the
internal maple state remains safe to use.  Move the debug check from the
vma iterator into the maple tree itself so other users do not incorrectly
use the advanced maple state modification.

Fallout from this change include a large amount of debug setup needed to
be moved to earlier in the header, and the maple_tree.h radix-tree test
code needed to move the inclusion of the header to after the atomic
define.  None of those changes have functional changes.

Link: https://lkml.kernel.org/r/20231101171629.3612299-4-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Peng Zhang 
Signed-off-by: Andrew Morton

maple_tree: add init and exit to test module

2023-06-09T23:25:31+00:00

The test functions are not needed after the module is removed, so mark
them as such.  Add __exit to the module removal function.  Some other
variables have been marked as const static as well.

Link: https://lkml.kernel.org/r/20230518145544.1722059-20-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Suggested-by: Andrew Morton 
Cc: David Binderman 
Cc: Peng Zhang 
Cc: Sergey Senozhatsky 
Cc: Vernon Yang 
Cc: Wei Yang 
Signed-off-by: Andrew Morton

radix tree test suite: add lockdep_is_held to header

2022-09-27T02:46:14+00:00

maple tree uses lockdep_is_held, so define it as external in the header.

Link: https://lkml.kernel.org/r/20220906194824.2110408-7-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Tested-by: Yu Zhao 
Cc: Catalin Marinas 
Cc: David Hildenbrand 
Cc: David Howells 
Cc: Davidlohr Bueso 
Cc: "Matthew Wilcox (Oracle)" 
Cc: SeongJae Park 
Cc: Sven Schnelle 
Cc: Vlastimil Babka 
Cc: Will Deacon 
Signed-off-by: Andrew Morton

radix tree test suite: add pr_err define

2022-09-27T02:46:13+00:00

define pr_err to printk

Link: https://lkml.kernel.org/r/20220906194824.2110408-3-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Tested-by: Yu Zhao 
Cc: Catalin Marinas 
Cc: David Hildenbrand 
Cc: David Howells 
Cc: Davidlohr Bueso 
Cc: "Matthew Wilcox (Oracle)" 
Cc: SeongJae Park 
Cc: Sven Schnelle 
Cc: Vlastimil Babka 
Cc: Will Deacon 
Signed-off-by: Andrew Morton

Maple Tree: add new data structure

2022-09-27T02:46:13+00:00

Patch series "Introducing the Maple Tree"

The maple tree is an RCU-safe range based B-tree designed to use modern
processor cache efficiently.  There are a number of places in the kernel
that a non-overlapping range-based tree would be beneficial, especially
one with a simple interface.  If you use an rbtree with other data
structures to improve performance or an interval tree to track
non-overlapping ranges, then this is for you.

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
nodes.  With the increased branching factor, it is significantly shorter
than the rbtree so it has fewer cache misses.  The removal of the linked
list between subsequent entries also reduces the cache misses and the need
to pull in the previous and next VMA during many tree alterations.

The first user that is covered in this patch set is the vm_area_struct,
where three data structures are replaced by the maple tree: the augmented
rbtree, the vma cache, and the linked list of VMAs in the mm_struct.  The
long term goal is to reduce or remove the mmap_lock contention.

The plan is to get to the point where we use the maple tree in RCU mode.
Readers will not block for writers.  A single write operation will be
allowed at a time.  A reader re-walks if stale data is encountered.  VMAs
would be RCU enabled and this mode would be entered once multiple tasks
are using the mm_struct.

Davidlor said

: Yes I like the maple tree, and at this stage I don't think we can ask for
: more from this series wrt the MM - albeit there seems to still be some
: folks reporting breakage.  Fundamentally I see Liam's work to (re)move
: complexity out of the MM (not to say that the actual maple tree is not
: complex) by consolidating the three complimentary data structures very
: much worth it considering performance does not take a hit.  This was very
: much a turn off with the range locking approach, which worst case scenario
: incurred in prohibitive overhead.  Also as Liam and Matthew have
: mentioned, RCU opens up a lot of nice performance opportunities, and in
: addition academia[1] has shown outstanding scalability of address spaces
: with the foundation of replacing the locked rbtree with RCU aware trees.

A similar work has been discovered in the academic press

	https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf

Sheer coincidence.  We designed our tree with the intention of solving the
hardest problem first.  Upon settling on a b-tree variant and a rough
outline, we researched ranged based b-trees and RCU b-trees and did find
that article.  So it was nice to find reassurances that we were on the
right path, but our design choice of using ranges made that paper unusable
for us.

This patch (of 70):

The maple tree is an RCU-safe range based B-tree designed to use modern
processor cache efficiently.  There are a number of places in the kernel
that a non-overlapping range-based tree would be beneficial, especially
one with a simple interface.  If you use an rbtree with other data
structures to improve performance or an interval tree to track
non-overlapping ranges, then this is for you.

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
nodes.  With the increased branching factor, it is significantly shorter
than the rbtree so it has fewer cache misses.  The removal of the linked
list between subsequent entries also reduces the cache misses and the need
to pull in the previous and next VMA during many tree alterations.

The first user that is covered in this patch set is the vm_area_struct,
where three data structures are replaced by the maple tree: the augmented
rbtree, the vma cache, and the linked list of VMAs in the mm_struct.  The
long term goal is to reduce or remove the mmap_lock contention.

The plan is to get to the point where we use the maple tree in RCU mode.
Readers will not block for writers.  A single write operation will be
allowed at a time.  A reader re-walks if stale data is encountered.  VMAs
would be RCU enabled and this mode would be entered once multiple tasks
are using the mm_struct.

There is additional BUG_ON() calls added within the tree, most of which
are in debug code.  These will be replaced with a WARN_ON() call in the
future.  There is also additional BUG_ON() calls within the code which
will also be reduced in number at a later date.  These exist to catch
things such as out-of-range accesses which would crash anyways.

Link: https://lkml.kernel.org/r/20220906194824.2110408-1-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20220906194824.2110408-2-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Signed-off-by: Matthew Wilcox (Oracle) 
Tested-by: David Howells 
Tested-by: Sven Schnelle 
Tested-by: Yu Zhao 
Cc: Vlastimil Babka 
Cc: David Hildenbrand 
Cc: Davidlohr Bueso 
Cc: Catalin Marinas 
Cc: SeongJae Park 
Cc: Will Deacon 
Signed-off-by: Andrew Morton

tools: Move gfp.h and slab.h from radix-tree to lib

2022-02-20T06:44:37+00:00

Merge radix-tree definitions from gfp.h and slab.h with these
in tools/lib, so they can be used in other test suites.
Fix style issues in slab.h. Update radix-tree test files.

Signed-off-by: Karolina Drobnik 
Signed-off-by: Mike Rapoport 
Link: https://lore.kernel.org/r/b76ddb8a12fdf9870b55c1401213e44f5e0d0da3.1643796665.git.karolinadrobnik@gmail.com

tools: Fix math.h breakage

2021-11-30T17:14:42+00:00

Commit 98e1385ef24b ("include/linux/radix-tree.h: replace kernel.h with
the necessary inclusions") broke the radix tree test suite in two
different ways; first by including math.h which didn't exist in the
tools directory, and second by removing an implicit include of
spinlock.h before lockdep.h.  Fix both issues.

Cc: Andy Shevchenko 
Signed-off-by: Matthew Wilcox (Oracle) 
Acked-by: Andy Shevchenko 
Signed-off-by: Linus Torvalds

radix tree test suite: Fix compilation

2021-03-30T17:44:35+00:00

Commit 4bba4c4bb09a added tools/include/linux/compiler_types.h which
includes linux/compiler-gcc.h.  Unfortunately, we had our own (empty)
compiler_types.h which overrode the one added by that commit, and
so we lost the definition of __must_be_array().  Removing our empty
compiler_types.h fixes the problem and reduces our divergence from the
rest of the tools.

Signed-off-by: Matthew Wilcox (Oracle)

radix tree test suite: Fix compilation

2020-10-07T13:07:49+00:00

Introducing local_lock broke compilation; fix it all up.

Signed-off-by: Matthew Wilcox (Oracle)

linux-toradex.git/tools/testing/radix-tree/linux, branch v6.11-rc5

tools: fix userspace compilation with new test_xarray changes

maple_tree: move debug check to __mas_set_range()

maple_tree: add __init and __exit to test module

radix tree test suite: add lockdep_is_held to header

radix tree test suite: add pr_err define

Maple Tree: add new data structure

tools: Move gfp.h and slab.h from radix-tree to lib

tools: Fix math.h breakage

radix tree test suite: Fix compilation

radix tree test suite: Fix compilation

maple_tree: add init and exit to test module