linux-kernel - Re: [PATCH v3 0/2] Minimize xa_node allocation during xarry split

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: <104F428F-B514-401A-931F-182B636026BB@nvidia.com>
Date: Fri, 07 Mar 2025 15:33:41 -0500
From: Zi Yan <ziy@...dia.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: Hugh Dickins <hughd@...gle.com>, Kairui Song <kasong@...cent.com>,
 Miaohe Lin <linmiaohe@...wei.com>, linux-kernel@...r.kernel.org,
 Zi Yan <ziy@...dia.com>, Baolin Wang <baolin.wang@...ux.alibaba.com>,
 Matthew Wilcox <willy@...radead.org>, linux-fsdevel@...r.kernel.org,
 linux-mm@...ck.org
Subject: Re: [PATCH v3 0/2] Minimize xa_node allocation during xarry split

On 26 Feb 2025, at 16:08, Zi Yan wrote:

> Hi all,
>
> When splitting a multi-index entry in XArray from order-n to order-m,
> existing xas_split_alloc()+xas_split() approach requires
> 2^(n % XA_CHUNK_SHIFT) xa_node allocations. But its callers,
> __filemap_add_folio() and shmem_split_large_entry(), use at most 1 xa_node.
> To minimize xa_node allocation and remove the limitation of no split from
> order-12 (or above) to order-0 (or anything between 0 and 5)[1],
> xas_try_split() was added[2], which allocates
> (n / XA_CHUNK_SHIFT - m / XA_CHUNK_SHIFT) xa_node. It is used
> for non-uniform folio split, but can be used by __filemap_add_folio()
> and shmem_split_large_entry().
>
> 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 |
> -----------
>
> xas_try_split() is designed to be called iteratively with n = m + 1.
> xas_try_split_mini_order() is added to minmize the number of calls to
> xas_try_split() by telling the caller the next minimal order to split to
> instead of n - 1. Splitting order-n to order-m when m= l * XA_CHUNK_SHIFT
> does not require xa_node allocation and requires 1 xa_node
> when n=l * XA_CHUNK_SHIFT and m = n - 1, so it is OK to use
> xas_try_split() with n > m + 1 when no new xa_node is needed.
>
> xfstests quick group test passed on xfs and tmpfs.
>
> It is on top of Buddy allocator like (or non-uniform)
> folio split V9[2], which is on top of mm-everything-2025-02-26-03-56.
>
> Changelog
> ===
> From V2[3]:
> 1. Fixed shmem_split_large_entry() by setting swap offset correct.
>    (Thank Baolin for the detailed review)
> 2. Used updated xas_try_split() to avoid a bug when xa_node is allocated
>    by xas_nomem() instead of xas_try_split() itself.
>
> Let me know your comments.
>
>
> [1] https://lore.kernel.org/linux-mm/Z6YX3RznGLUD07Ao@casper.infradead.org/
> [2] https://lore.kernel.org/linux-mm/20250226210032.2044041-1-ziy@nvidia.com/
> [3] https://lore.kernel.org/linux-mm/20250218235444.1543173-1-ziy@nvidia.com/

Hi Andrew,

Do you want me to resend this? This still applies cleanly on mm-everything-2025-03-07-07-55 plus V10.

Thanks.

Best Regards,
Yan, Zi