On 18 Feb 2025, at 10:44, David Hildenbrand wrote:
> On 17.02.25 23:05, Zi Yan wrote:
>> On 17 Feb 2025, at 16:44, David Hildenbrand wrote:
>>
>>> On 11.02.25 16: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 <z...@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(-)
>>>>
>>>> diff --git a/Documentation/core-api/xarray.rst
>>>> b/Documentation/core-api/xarray.rst
>>>> index f6a3eef4fe7f..c6c91cbd0c3c 100644
>>>> --- a/Documentation/core-api/xarray.rst
>>>> +++ b/Documentation/core-api/xarray.rst
>>>> @@ -489,7 +489,19 @@ Storing ``NULL`` into any index of a multi-index
>>>> entry will set the
>>>> entry at every index to ``NULL`` and dissolve the tie. A multi-index
>>>> entry can be split into entries occupying smaller ranges by calling
>>>> xas_split_alloc() without the xa_lock held, followed by taking the lock
>>>> -and calling xas_split().
>>>> +and calling xas_split() or calling xas_try_split() with xa_lock. The
>>>> +difference between xas_split_alloc()+xas_split() and xas_try_alloc() is
>>>> +that xas_split_alloc() + xas_split() split the entry from the original
>>>> +order to the new order in one shot uniformly, whereas xas_try_split()
>>>> +iteratively splits the entry containing the index non-uniformly.
>>>> +For example, to split an order-9 entry, which takes 2^(9-6)=8 slots,
>>>> +assuming ``XA_CHUNK_SHIFT`` is 6, xas_split_alloc() + xas_split() need
>>>> +8 xa_node. xas_try_split() splits 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 1 xa_node instead of 8.
>>>> Functions and structures
>>>> ========================
>>>> diff --git a/include/linux/xarray.h b/include/linux/xarray.h
>>>> index 0b618ec04115..9eb8c7425090 100644
>>>> --- a/include/linux/xarray.h
>>>> +++ b/include/linux/xarray.h
>>>> @@ -1555,6 +1555,8 @@ int xa_get_order(struct xarray *, unsigned long
>>>> index);
>>>> int xas_get_order(struct xa_state *xas);
>>>> void xas_split(struct xa_state *, void *entry, unsigned int order);
>>>> void xas_split_alloc(struct xa_state *, void *entry, unsigned int
>>>> order, gfp_t);
>>>> +void xas_try_split(struct xa_state *xas, void *entry, unsigned int order,
>>>> + gfp_t gfp);
>>>> #else
>>>> static inline int xa_get_order(struct xarray *xa, unsigned long index)
>>>> {
>>>> @@ -1576,6 +1578,11 @@ static inline void xas_split_alloc(struct xa_state
>>>> *xas, void *entry,
>>>> unsigned int order, gfp_t gfp)
>>>> {
>>>> }
>>>> +
>>>> +static inline void xas_try_split(struct xa_state *xas, void *entry,
>>>> + unsigned int order, gfp_t gfp)
>>>> +{
>>>> +}
>>>> #endif
>>>> /**
>>>> diff --git a/lib/test_xarray.c b/lib/test_xarray.c
>>>> index 6932a26f4927..598ca38a2f5b 100644
>>>> --- a/lib/test_xarray.c
>>>> +++ b/lib/test_xarray.c
>>>> @@ -1857,6 +1857,49 @@ static void check_split_1(struct xarray *xa,
>>>> unsigned long index,
>>>> xa_destroy(xa);
>>>> }
>>>> +static void check_split_2(struct xarray *xa, unsigned long index,
>>>> + unsigned int order, unsigned int new_order)
>>>> +{
>>>> + XA_STATE_ORDER(xas, xa, index, new_order);
>>>> + unsigned int i, found;
>>>> + void *entry;
>>>> +
>>>> + xa_store_order(xa, index, order, xa, GFP_KERNEL);
>>>> + xa_set_mark(xa, index, XA_MARK_1);
>>>> +
>>>> + xas_lock(&xas);
>>>> + xas_try_halve(&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);
>>>> + xas_unlock(&xas);
>>>> + goto out;
>>>> + }
>>>> + for (i = 0; i < (1 << order); i += (1 << new_order))
>>>> + __xa_store(xa, index + i, xa_mk_index(index + i), 0);
>>>> + xas_unlock(&xas);
>>>> +
>>>> + for (i = 0; i < (1 << order); i++) {
>>>> + unsigned int val = index + (i & ~((1 << new_order) - 1));
>>>> + XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));
>>>> + }
>>>> +
>>>> + xa_set_mark(xa, index, XA_MARK_0);
>>>> + XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
>>>> +
>>>> + xas_set_order(&xas, index, 0);
>>>> + found = 0;
>>>> + rcu_read_lock();
>>>> + xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_1) {
>>>> + found++;
>>>> + XA_BUG_ON(xa, xa_is_internal(entry));
>>>> + }
>>>> + rcu_read_unlock();
>>>> + XA_BUG_ON(xa, found != 1 << (order - new_order));
>>>> +out:
>>>> + xa_destroy(xa);
>>>> +}
>>>> +
>>>> static noinline void check_split(struct xarray *xa)
>>>> {
>>>> unsigned int order, new_order;
>>>> @@ -1868,6 +1911,10 @@ static noinline void check_split(struct xarray *xa)
>>>> check_split_1(xa, 0, order, new_order);
>>>> check_split_1(xa, 1UL << order, order,
>>>> new_order);
>>>> check_split_1(xa, 3UL << order, order,
>>>> new_order);
>>>> +
>>>> + check_split_2(xa, 0, order, new_order);
>>>> + check_split_2(xa, 1UL << order, order, new_order);
>>>> + check_split_2(xa, 3UL << order, order, new_order);
>>>> }
>>>> }
>>>> }
>>>> diff --git a/lib/xarray.c b/lib/xarray.c
>>>> index 116e9286c64e..c38beca77830 100644
>>>> --- a/lib/xarray.c
>>>> +++ b/lib/xarray.c
>>>> @@ -1007,6 +1007,31 @@ static void node_set_marks(struct xa_node *node,
>>>> unsigned int offset,
>>>> }
>>>> }
>>>> +static struct xa_node *__xas_alloc_node_for_split(struct xa_state *xas,
>>>> + void *entry, gfp_t gfp)
>>>> +{
>>>> + unsigned int i;
>>>> + void *sibling = NULL;
>>>> + struct xa_node *node;
>>>> + unsigned int mask = xas->xa_sibs;
>>>> +
>>>> + node = kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp);
>>>> + if (!node)
>>>> + return NULL;
>>>> + node->array = xas->xa;
>>>> + for (i = 0; i < XA_CHUNK_SIZE; i++) {
>>>> + if ((i & mask) == 0) {
>>>> + RCU_INIT_POINTER(node->slots[i], entry);
>>>> + sibling = xa_mk_sibling(i);
>>>> + } else {
>>>> + RCU_INIT_POINTER(node->slots[i], sibling);
>>>> + }
>>>> + }
>>>> + RCU_INIT_POINTER(node->parent, xas->xa_alloc);
>>>> +
>>>> + return node;
>>>> +}
>>>> +
>>>> /**
>>>> * xas_split_alloc() - Allocate memory for splitting an entry.
>>>> * @xas: XArray operation state.
>>>> @@ -1025,7 +1050,6 @@ void xas_split_alloc(struct xa_state *xas, void
>>>> *entry, unsigned int order,
>>>> gfp_t gfp)
>>>> {
>>>> unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;
>>>> - unsigned int mask = xas->xa_sibs;
>>>> /* XXX: no support for splitting really large entries yet */
>>>> if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT <= order))
>>>> @@ -1034,23 +1058,9 @@ void xas_split_alloc(struct xa_state *xas, void
>>>> *entry, unsigned int order,
>>>> return;
>>>> do {
>>>> - unsigned int i;
>>>> - void *sibling = NULL;
>>>> - struct xa_node *node;
>>>> -
>>>> - node = kmem_cache_alloc_lru(radix_tree_node_cachep,
>>>> xas->xa_lru, gfp);
>>>> + struct xa_node *node = __xas_alloc_node_for_split(xas, entry,
>>>> gfp);
>>>> if (!node)
>>>> goto nomem;
>>>> - node->array = xas->xa;
>>>> - for (i = 0; i < XA_CHUNK_SIZE; i++) {
>>>> - if ((i & mask) == 0) {
>>>> - RCU_INIT_POINTER(node->slots[i], entry);
>>>> - sibling = xa_mk_sibling(i);
>>>> - } else {
>>>> - RCU_INIT_POINTER(node->slots[i], sibling);
>>>> - }
>>>> - }
>>>> - RCU_INIT_POINTER(node->parent, xas->xa_alloc);
>>>> xas->xa_alloc = node;
>>>> } while (sibs-- > 0);
>>>> @@ -1122,6 +1132,100 @@ void xas_split(struct xa_state *xas, void
>>>> *entry, unsigned int order)
>>>> xas_update(xas, node);
>>>> }
>>>> EXPORT_SYMBOL_GPL(xas_split);
>>>> +
>>>> +/**
>>>> + * xas_try_split() - Try to split a multi-index entry.
>>>> + * @xas: XArray operation state.
>>>> + * @entry: New entry to store in the array.
>>>> + * @order: Current entry order.
>>>> + * @gfp: Memory allocation flags.
>>>> + *
>>>> + * The size of the new entries is set in @xas. The value in @entry is
>>>> + * copied to all the replacement entries. If and only if one xa_node
>>>> needs to
>>>> + * be allocated, the function will use @gfp to get one. If more xa_node
>>>> are
>>>> + * needed, the function gives EINVAL error.
>>>> + *
>>>> + * Context: Any context. The caller should hold the xa_lock.
>>>> + */
>>>> +void xas_try_split(struct xa_state *xas, void *entry, unsigned int order,
>>>> + gfp_t gfp)
>>>> +{
>>>> + unsigned int sibs = (1 << (order % XA_CHUNK_SHIFT)) - 1;
>>>> + unsigned int offset, marks;
>>>> + struct xa_node *node;
>>>> + void *curr = xas_load(xas);
>>>> + int values = 0;
>>>> +
>>>> + node = xas->xa_node;
>>>> + if (xas_top(node))
>>>> + return;
>>>> +
>>>> + if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
>>>> + gfp |= __GFP_ACCOUNT;
>>>> +
>>>> + marks = node_get_marks(node, xas->xa_offset);
>>>> +
>>>> + offset = xas->xa_offset + sibs;
>>>> + do {
>>>> + if (xas->xa_shift < node->shift) {
>>>> + struct xa_node *child = xas->xa_alloc;
>>>> + unsigned int expected_sibs =
>>>> + (1 << ((order - 1) % XA_CHUNK_SHIFT)) - 1;
>>>> +
>>>> + /*
>>>> + * No support for splitting sibling entries
>>>> + * (horizontally) or cascade split (vertically), which
>>>> + * requires two or more new xa_nodes.
>>>> + * Since if one xa_node allocation fails,
>>>> + * it is hard to free the prior allocations.
>>>> + */
>>>> + if (sibs || xas->xa_sibs != expected_sibs) {
>>>> + xas_destroy(xas);
>>>> + xas_set_err(xas, -EINVAL);
>>>> + return;
>>>> + }
>>>> +
>>>> + if (!child) {
>>>> + child = __xas_alloc_node_for_split(xas, entry,
>>>> + gfp);
>>>> + if (!child) {
>>>> + xas_destroy(xas);
>>>> + xas_set_err(xas, -ENOMEM);
>>>> + return;
>>>> + }
>>>> + }
>>>
>>> No expert on this, just wondering ...
>>>
>>> ... what is the effect if we halfway-through fail the split? Is it okay to
>>> leave that "partially split" thing in place? Can callers deal with that?
>>
>> Good question.
>>
>
> Let me rephrase: In __split_unmapped_folio(), we call xas_try_split(). If
> that fails, we stop the split and effectively skip over the
> __split_folio_to_order(). The folio remains unsplit (no order change:
> old_order).
Right. To be more specific, in !uniform_split case, the original folio
can be split and old_order can change. Namely, if the caller wants to
split an order-9, folio_split() can split it to 2 order-6s, 1 order-7,
and 1 order-8 then cannot allocate a new xa_node due to memory constrains
and stop. The caller will get 2 order-6s, 1 order-7, and 1 order-8
and folio_split() returns -ENOMEM. The caller needs to handle this
situation, although it should be quite rare. Because unless the caller
is splitting order-12 (or even higher orders) to order-0, at most
1 xa_node is needed.
>
> xas_try_split() was instructed to split from old_order -> split_order.
>
> xas_try_split() documents that: "The value in @entry is copied to all the
> replacement entries.", meaning after the split, all entries will be pointing
> at the folio.
Right.
>
> Now, can it happen that xas_try_split() would ever perform a partial split in
> any way, when invoked from __split_unmapped_folio(), such that we run into
> the do { } while(); loop and fail with -ENOMEM after already having performed
> changes -- xas_update().
>
> Or is that simply impossible?
Right. It is impossible. xas_try_split() either splits by copying @entry
to all the replacement entries, or is trying to allocate a new xa_node,
which can result in -ENOMEM. These two will not be mixed.
>
> Maybe it's just the do { } while(); loop in there that is confusing me.
> (again, no expert)
Yeah, that the do while loop is confusing. Let me restructure the code
so that the do while loop only runs in the @entry copy case not the
xa_node allocation case.
>
>> xas_try_split() imposes what kind of split it does and is usually used to
>> split from order N to order N-1:
>
> You mean that old_order -> split_order will in the case of
> __split_unmapped_folio() always be a difference of 1?
Yes for !uniform_split case. For uniform_split case (split_huge_page*() uses),
xas_split() is used and all required new xa_node are preallocated by
xas_split_alloc() in __folio_split().
>
>>
>> 1. when N is a multiplier of XA_CHUNK_SHIFT, a new xa_node is needed, so
>> either child (namely xas->xa_alloc) is not NULL, meaning someone called
>> xa_nomem() to allocate a xa_node before xas_try_split() or child is NULL
>> and an allocation is needed. If child is still NULL after the allocation,
>> meaning we are out of memory, no split is done;
>>
>> 2. when N is not, no new xa_node is needed, xas_try_split() just rewrites
>> existing slot values to perform the split (the code after the hunk above).
>> No fail will happen. For this split, since no new xa_node is needed,
>> the caller is actually allowed to split from N to a value smaller than
>> N-1 as long as N-1 is >= (N - N % XA_CHUNK_SHIFT).
>>
>>
>> Various checks make sure xas_try_split() only sees the two above situation:
>>
>> a. "xas->xa_shift < node->shift" means the split crosses XA_CHUNK_SHIFT,
>> at least 1 new xa_node is needed; the else branch only handles the case
>> 2 above;
>>
>> b. for the then branch the "if (sibs || xas->xa_sibs != expected_sibs)"
>> check makes sure N is a multiplier of XA_CHUNK_SHIFT and the new order
>> has to be N-1. In "if (sibs || xas->xa_sibs != expected_sibs)",
>> "sibs != 0" means the from order N covers more than 1 slot, so more than 1
>> new xa_node is needed, "xas->xa_sibs != expected_sibs" makes sure
>> the new order is N-1 (you can see it from how expected_sibs is assigned).
>
> Thanks!
>
>>
>> Let me know if you have any other question.
>
> Thanks for the details!
Thank you for checking the code. :)
Best Regards,
Yan, Zi
