linux.git/tools/testing/radix-tree, branch v6.5-rc2

Merge mm-hotfixes-stable into mm-stable to pick up depended-upon changes.

2023-06-23T23:58:19+00:00

radix-tree: move declarations to header

2023-06-12T18:31:50+00:00

The xarray.c file contains the only call to radix_tree_node_rcu_free(),
and it comes with its own extern declaration for it.  This means the
function definition causes a missing-prototype warning:

lib/radix-tree.c:288:6: error: no previous prototype for 'radix_tree_node_rcu_free' [-Werror=missing-prototypes]

Instead, move the declaration for this function to a new header that can
be included by both, and do the same for the radix_tree_node_cachep
variable that has the same underlying problem but does not cause a warning
with gcc.

[zhangpeng.00@bytedance.com: fix building radix tree test suite]
  Link: https://lkml.kernel.org/r/20230521095450.21332-1-zhangpeng.00@bytedance.com
Link: https://lkml.kernel.org/r/20230516194212.548910-1-arnd@kernel.org
Signed-off-by: Arnd Bergmann 
Signed-off-by: Peng Zhang 
Cc: Matthew Wilcox (Oracle) 
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

maple_tree: make test code work without debug enabled

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

The test code is less useful without debug, but can still do general
validations.  Define mt_dump(), mas_dump() and mas_wr_dump() as a noop if
debug is not enabled and document it in the test module information that
more information can be obtained with another kernel config option.

MT_BUG_ON() will report a failures without tree dumps, and the output will
be less useful.

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

maple_tree: add format option to mt_dump()

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

Allow different formatting strings to be used when dumping the tree. 
Currently supports hex and decimal.

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

maple_tree: avoid unnecessary ascending

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

The maple tree node limits are implied by the parent.  When walking up the
tree, the limit may not be known until a slot that does not have implied
limits are encountered.  However, if the node is the left-most or
right-most node, the walking up to find that limit can be skipped.

This commit also fixes the debug/testing code that was not setting the
limit on walking down the tree as that optimization is not compatible with
this change.

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

maple_tree: add a test case to check maple_alloc

2023-04-18T23:29:56+00:00

Add a test case to check whether the number of maple_alloc structures is
actually equal to mas->alloc->total.

Link: https://lkml.kernel.org/r/20230411041005.26205-2-zhangpeng.00@bytedance.com
Signed-off-by: Peng Zhang 
Cc: Liam R. Howlett 
Signed-off-by: Andrew Morton

maple_tree: fix write memory barrier of nodes once dead for RCU mode

2023-04-06T01:06:21+00:00

During the development of the maple tree, the strategy of freeing multiple
nodes changed and, in the process, the pivots were reused to store
pointers to dead nodes.  To ensure the readers see accurate pivots, the
writers need to mark the nodes as dead and call smp_wmb() to ensure any
readers can identify the node as dead before using the pivot values.

There were two places where the old method of marking the node as dead
without smp_wmb() were being used, which resulted in RCU readers seeing
the wrong pivot value before seeing the node was dead.  Fix this race
condition by using mte_set_node_dead() which has the smp_wmb() call to
ensure the race is closed.

Add a WARN_ON() to the ma_free_rcu() call to ensure all nodes being freed
are marked as dead to ensure there are no other call paths besides the two
updated paths.

This is necessary for the RCU mode of the maple tree.

Link: https://lkml.kernel.org/r/20230227173632.3292573-6-surenb@google.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett 
Signed-off-by: Suren Baghdasaryan 
Cc: 
Signed-off-by: Andrew Morton

maple_tree: remove the parameter entry of mas_preallocate

2023-02-03T06:32:52+00:00

The parameter entry of mas_preallocate is not used, so drop it.

Link: https://lkml.kernel.org/r/20230110154211.1758562-1-vernon2gm@gmail.com
Signed-off-by: Vernon Yang 
Cc: Liam Howlett 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton

maple_tree: remove GFP_ZERO from kmem_cache_alloc() and kmem_cache_alloc_bulk()

2023-01-19T01:12:54+00:00

Preallocations are common in the VMA code to avoid allocating under
certain locking conditions.  The preallocations must also cover the
worst-case scenario.  Removing the GFP_ZERO flag from the
kmem_cache_alloc() (and bulk variant) calls will reduce the amount of time
spent zeroing memory that may not be used.  Only zero out the necessary
area to keep track of the allocations in the maple state.  Zero the entire
node prior to using it in the tree.

This required internal changes to node counting on allocation, so the test
code is also updated.

This restores some micro-benchmark performance: up to +9% in mmtests mmap1
by my testing +10% to +20% in mmap, mmapaddr, mmapmany tests reported by
Red Hat

Link: https://bugzilla.redhat.com/show_bug.cgi?id=2149636
Link: https://lkml.kernel.org/r/20230105160427.2988454-1-Liam.Howlett@oracle.com
Signed-off-by: Liam Howlett 
Reported-by: Jirka Hladky 
Suggested-by: Matthew Wilcox (Oracle) 
Signed-off-by: Andrew Morton