linux-toradex.git/lib/test_maple_tree.c, branch v6.14-rc2

test_maple_tree: test exhausted upper limit of mtree_alloc_cyclic()

2025-01-26T04:22:19+00:00

When the upper bound of the search is exhausted, the maple state may be
returned in an error state of -EBUSY.  This means maple state needs to be
reset before the second search in mas_alloc_cylic() to ensure the search
happens.  This test ensures the issue is not recreated.

Link: https://lkml.kernel.org/r/20241216190113.1226145-3-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Reviewed-by: Yang Erkun 
Cc: Christian Brauner 
Cc: Chuck Lever  says:
Signed-off-by: Andrew Morton

maple_tree: add a test check deficient node

2025-01-14T06:40:41+00:00

Add a test to assert when resulting a deficient node on splitting.

We can achieve this by build a tree with two nodes. With the left
node with consecutive data from 0 and leave some room for the final
insert to locate in left node. And the right node a full node to force
the split happens on the left node.

Link: https://lkml.kernel.org/r/20241113031616.10530-3-richard.weiyang@gmail.com
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Sidhartha Kumar 
Cc: Lorenzo Stoakes 
Signed-off-by: Andrew Morton

maple_tree: add a test checking storing null

2024-11-11T21:09:42+00:00

Add a test to assert that, when storing null to am empty tree or a
single entry tree it will not result into:

  * a root node with range [0, ULONG_MAX] set to NULL
  * a root node with consecutive slot set to NULL

[akpm@linux-foundation.org: work around build error (mas_root)]
Link: https://lkml.kernel.org/r/20241031231627.14316-6-richard.weiyang@gmail.com
Signed-off-by: Wei Yang 
Reviewed-by: Liam R. Howlett 
Cc: Liam R. Howlett 
Cc: Sidhartha Kumar 
Cc: Lorenzo Stoakes 
Signed-off-by: Andrew Morton

test_maple_tree: add the missing MODULE_DESCRIPTION() macro

2024-07-04T02:30:05+00:00

make allmodconfig && make W=1 C=1 reports: WARNING: modpost: missing
MODULE_DESCRIPTION() in lib/test_maple_tree.o

Add the missing invocation of the MODULE_DESCRIPTION() macro.

Link: https://lkml.kernel.org/r/20240531-md-lib-test_maple_tree-v1-1-7b1b485aeec3@quicinc.com
Signed-off-by: Jeff Johnson 
Reviewed-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

test_maple_tree: testing the cyclic allocation

2024-02-21T08:34:26+00:00

This tests the interactions of the cyclic allocations, the maple state
index and last, and overflow.

Signed-off-by: Liam R. Howlett 
Signed-off-by: Chuck Lever 
Link: https://lore.kernel.org/r/170820144894.6328.13052830860966450674.stgit@91.116.238.104.host.secureserver.net
Signed-off-by: Christian Brauner

maple_tree: don't find node end in mtree_lookup_walk()

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

Since the pivot being set is now reliable, the optimized loop no longer
needs to find the node end.  The redundant check for a dead node can also
be avoided as there is no danger of using the wrong pivot since the
results will be thrown out in the case of a dead node by the later check.

This patch also adds a benchmark test for the function to the maple tree
test framework.  The benchmark shows an average increase performance of
5.98% over 3 runs with this commit.

Link: https://lkml.kernel.org/r/20231101171629.3612299-12-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: update check_forking() and bench_forking()

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

Updated check_forking() and bench_forking() to use __mt_dup() to duplicate
maple tree.

Link: https://lkml.kernel.org/r/20231027033845.90608-9-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: 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 GFP_KERNEL to allocations in mas_expected_entries()

2023-10-18T19:12:41+00:00

Users complained about OOM errors during fork without triggering
compaction.  This can be fixed by modifying the flags used in
mas_expected_entries() so that the compaction will be triggered in low
memory situations.  Since mas_expected_entries() is only used during fork,
the extra argument does not need to be passed through.

Additionally, the two test_maple_tree test cases and one benchmark test
were altered to use the correct locking type so that allocations would not
trigger sleeping and thus fail.  Testing was completed with lockdep atomic
sleep detection.

The additional locking change requires rwsem support additions to the
tools/ directory through the use of pthreads pthread_rwlock_t.  With this
change test_maple_tree works in userspace, as a module, and in-kernel.

Users may notice that the system gave up early on attempting to start new
processes instead of attempting to reclaim memory.

Link: https://lkml.kernel.org/r/20230915093243epcms1p46fa00bbac1ab7b7dca94acb66c44c456@epcms1p4
Link: https://lkml.kernel.org/r/20231012155233.2272446-1-Liam.Howlett@oracle.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett 
Reviewed-by: Peng Zhang 
Cc: 
Cc: 
Signed-off-by: Andrew Morton