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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <3BC99886-609B-4820-B65D-FCA2E11A02F3@nvidia.com>
Date: Tue, 11 Feb 2025 19:57:09 -0500
From: Zi Yan <ziy@...dia.com>
To: <linux-mm@...ck.org>, Andrew Morton <akpm@...ux-foundation.org>,
 "Kirill A . Shutemov" <kirill.shutemov@...ux.intel.com>,
 "Matthew Wilcox (Oracle)" <willy@...radead.org>
Cc: Ryan Roberts <ryan.roberts@....com>, Hugh Dickins <hughd@...gle.com>,
 David Hildenbrand <david@...hat.com>, Yang Shi <yang@...amperecomputing.com>,
 Miaohe Lin <linmiaohe@...wei.com>, Kefeng Wang <wangkefeng.wang@...wei.com>,
 Yu Zhao <yuzhao@...gle.com>, John Hubbard <jhubbard@...dia.com>,
 Baolin Wang <baolin.wang@...ux.alibaba.com>,
 <linux-kselftest@...r.kernel.org>, <linux-kernel@...r.kernel.org>,
 Zi Yan <ziy@...dia.com>
Subject: Re: [PATCH v7 1/8] xarray: add xas_try_split() to split a multi-index
 entry.

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