linux-stable.git/tools/testing/radix-tree/maple.c, branch linux-6.8.y

maple_tree: fix warning comparing pointer to 0

2023-12-20T22:48:12+00:00

Avoid pointer type value compared with 0 to make code clear.

./tools/testing/radix-tree/maple.c:34142:15-16: WARNING comparing pointer to 0.

Link: https://lkml.kernel.org/r/20231208020450.7003-1-jiapeng.chong@linux.alibaba.com
Reported-by: Abaci Robot 
Closes: https://bugzilla.openanolis.cn/show_bug.cgi?id=7696
Signed-off-by: Jiapeng Chong 
Cc: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Signed-off-by: Andrew Morton

sync mm-stable with mm-hotfixes-stable to pick up depended-upon changes

2023-12-20T22:47:18+00:00

maple_tree: do not preallocate nodes for slot stores

2023-12-20T21:46:19+00:00

mas_preallocate() defaults to requesting 1 node for preallocation and then
,depending on the type of store, will update the request variable.  There
isn't a check for a slot store type, so slot stores are preallocating the
default 1 node.  Slot stores do not require any additional nodes, so add a
check for the slot store case that will bypass node_count_gfp().  Update
the tests to reflect that slot stores do not require allocations.

User visible effects of this bug include increased memory usage from the
unneeded node that was allocated.

Link: https://lkml.kernel.org/r/20231213205058.386589-1-sidhartha.kumar@oracle.com
Fixes: 0b8bb544b1a7 ("maple_tree: update mas_preallocate() testing")
Signed-off-by: Sidhartha Kumar 
Cc: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Peng Zhang 
Cc: 	[6.6+]
Signed-off-by: Andrew Morton

maple_tree: remove mas_searchable()

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

Now that the status of the maple state is outside of the node, the
mas_searchable() function can be dropped for easier open-coding of what is
going on.

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

maple_tree: separate ma_state node from status

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

The maple tree node is overloaded to keep status as well as the active
node.  This, unfortunately, results in a re-walk on underflow or overflow.
Since the maple state has room, the status can be placed in its own enum
in the structure.  Once an underflow/overflow is detected, certain modes
can restore the status to active and others may need to re-walk just that
one node to see the entry.

The status being an enum has the benefit of detecting unhandled status in
switch statements.

[Liam.Howlett@oracle.com: fix comments about MAS_*]
  Link: https://lkml.kernel.org/r/20231106154124.614247-1-Liam.Howlett@oracle.com
[Liam.Howlett@oracle.com: update forking to separate maple state and node]
  Link: https://lkml.kernel.org/r/20231106154551.615042-1-Liam.Howlett@oracle.com
[Liam.Howlett@oracle.com: fix mas_prev() state separation code]
  Link: https://lkml.kernel.org/r/20231207193319.4025462-1-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20231101171629.3612299-9-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Peng Zhang 
Signed-off-by: Andrew Morton

maple_tree: add end of node tracking to the maple state

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

Analysis of the mas_for_each() iteration showed that there is a
significant time spent finding the end of a node.  This time can be
greatly reduced if the end of the node is cached in the maple state.  Care
must be taken to update & invalidate as necessary.

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

maple_tree: skip other tests when BENCH is enabled

2023-12-11T00:51:33+00:00

Skip other tests when BENCH is enabled so that performance can be measured
in user space.

Link: https://lkml.kernel.org/r/20231027033845.90608-8-zhangpeng.00@bytedance.com
Signed-off-by: Peng Zhang 
Reviewed-by: Liam R. Howlett 
Cc: Christian Brauner 
Cc: Jonathan Corbet 
Cc: Mateusz Guzik 
Cc: Mathieu Desnoyers 
Cc: Matthew Wilcox 
Cc: Michael S. Tsirkin 
Cc: Mike Christie 
Cc: Nicholas Piggin 
Cc: Peter Zijlstra 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: add test for mtree_dup()

2023-12-11T00:51:32+00:00

Add test for mtree_dup().

Test by duplicating different maple trees and then comparing the two
trees.  Includes tests for duplicating full trees and memory allocation
failures on different nodes.

Link: https://lkml.kernel.org/r/20231027033845.90608-6-zhangpeng.00@bytedance.com
Signed-off-by: Peng Zhang 
Reviewed-by: Liam R. Howlett 
Cc: Christian Brauner 
Cc: Jonathan Corbet 
Cc: Mateusz Guzik 
Cc: Mathieu Desnoyers 
Cc: Matthew Wilcox 
Cc: Michael S. Tsirkin 
Cc: Mike Christie 
Cc: Nicholas Piggin 
Cc: Peter Zijlstra 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: update mas_preallocate() testing

2023-08-18T17:12:49+00:00

Since the mas_preallocate() calculation has been updated to be more
precise, the testing must also be updated to check for what is expected.

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

maple_tree: re-introduce entry to mas_preallocate() arguments

2023-08-18T17:12:48+00:00

The current preallocation strategy is to preallocate the absolute
worst-case allocation for a tree modification.  The entry (or NULL) is
needed to know how many nodes are needed to write to the tree.  Start by
adding the argument to the mas_preallocate() definition.

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