Re: [PATCH v7 1/8] xarray: add xas_try_split() to split a multi-index entry.

[Zi Yan]

On 11 Feb 2025, at 19:57, Zi Yan wrote:

> 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@xxxxxxxxxx>
>> ---
>>  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.