On 11 Feb 2025, at 10:50, Zi Yan wrote:
It is a preparation patch for non-uniform folio split, which always split a folio into half iteratively, and minimal xarray entry split.
Currently, xas_split_alloc() and xas_split() always split all slots from a multi-index entry. They cost the same number of xa_node as the to-be-split slots. For example, to split an order-9 entry, which takes 2^(9-6)=8 slots, assuming XA_CHUNK_SHIFT is 6 (!CONFIG_BASE_SMALL), 8 xa_node are needed. Instead xas_try_split() is intended to be used iteratively to split the order-9 entry into 2 order-8 entries, then split one order-8 entry, based on the given index, to 2 order-7 entries, ..., and split one order-1 entry to 2 order-0 entries. When splitting the order-6 entry and a new xa_node is needed, xas_try_split() will try to allocate one if possible. As a result, xas_try_split() would only need one xa_node instead of 8.
When a new xa_node is needed during the split, xas_try_split() can try to allocate one but no more. -ENOMEM will be return if a node cannot be allocated. -EINVAL will be return if a sibling node is split or cascade split happens, where two or more new nodes are needed, and these are not supported by xas_try_split().
xas_split_alloc() and xas_split() split an order-9 to order-0:
--------------------------------- | | | | | | | | | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | | | | | | | | --------------------------------- | | | | ------- --- --- ------- | | ... | | V V V V
| xa_node | | xa_node | ... | xa_node | | xa_node |
xas_try_split() splits an order-9 to order-0:
| | | | | | | | | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | | | | | | | |
| | V
| xa_node |
Signed-off-by: Zi Yan ziy@nvidia.com
Documentation/core-api/xarray.rst | 14 ++- include/linux/xarray.h | 7 ++ lib/test_xarray.c | 47 +++++++++++ lib/xarray.c | 136 ++++++++++++++++++++++++++---- tools/testing/radix-tree/Makefile | 1 + 5 files changed, 188 insertions(+), 17 deletions(-)
Hi Andrew,
Do you mind folding the diff below to this one? I changed the function name but forgot the one in the xarray test. Thanks.
diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 598ca38a2f5b..cc2dd325158f 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1868,7 +1868,7 @@ static void check_split_2(struct xarray *xa, unsigned long index, xa_set_mark(xa, index, XA_MARK_1);
xas_lock(&xas); - xas_try_halve(&xas, xa, order, GFP_KERNEL); + xas_try_split(&xas, xa, order, GFP_KERNEL); if (((new_order / XA_CHUNK_SHIFT) < (order / XA_CHUNK_SHIFT)) && new_order < order - 1) { XA_BUG_ON(xa, !xas_error(&xas) || xas_error(&xas) != -EINVAL);
Best Regards, Yan, Zi