kernel/linux.git/tools/testing/radix-tree/maple.c, branch v6.6.131

maple_tree: do not preallocate nodes for slot stores

2024-01-05T14:19:43+00:00

commit 4249f13c11be8b8b7bf93204185e150c3bdc968d upstream. 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 Signed-off-by: Greg Kroah-Hartman

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

maple_tree: add test for expanding range in RCU mode

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

Add test for expanding range in RCU mode. If we use the fast path of the slot store to expand range in RCU mode, this test will fail. Link: https://lkml.kernel.org/r/20230628073657.75314-3-zhangpeng.00@bytedance.com Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett Signed-off-by: Andrew Morton

maple_tree: fix node allocation testing on 32 bit

2023-07-17T19:53:22+00:00

Internal node counting was altered and the 64 bit test was updated, however the 32bit test was missed. Restore the 32bit test to a functional state. Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/ Link: https://lkml.kernel.org/r/20230712173916.168805-2-Liam.Howlett@oracle.com Fixes: 541e06b772c1 ("maple_tree: remove GFP_ZERO from kmem_cache_alloc() and kmem_cache_alloc_bulk()") Signed-off-by: Liam R. Howlett Cc: 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