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.
