* [PATCH 1/2] mm/filemap: use xas_try_split() in __filemap_add_folio().
2025-02-13 3:43 [PATCH 0/2] Minimize xa_node allocation during xarry split Zi Yan
@ 2025-02-13 3:43 ` Zi Yan
2025-02-13 3:43 ` [PATCH 2/2] mm/shmem: use xas_try_split() in shmem_split_large_entry() Zi Yan
2025-02-13 3:46 ` [PATCH 0/2] Minimize xa_node allocation during xarry split Zi Yan
2 siblings, 0 replies; 4+ messages in thread
From: Zi Yan @ 2025-02-13 3:43 UTC (permalink / raw)
To: Matthew Wilcox, linux-mm, linux-fsdevel
Cc: Andrew Morton, Hugh Dickins, Baolin Wang, Kairui Song,
Miaohe Lin, linux-kernel, Zi Yan
During __filemap_add_folio(), a shadow entry is covering n slots and a
folio covers m slots with m < n is to be added. Instead of splitting all
n slots, only the m slots covered by the folio need to be split and the
remaining n-m shadow entries can be retained with orders ranging from m to
n-1. This method only requires (n/XA_CHUNK_SHIFT) - (m/XA_CHUNK_SHIFT)
new xa_nodes instead of
(n % XA_CHUNK_SHIFT) * ((n/XA_CHUNK_SHIFT) - (m/XA_CHUNK_SHIFT)) new
xa_nodes, compared to the original xas_split_alloc() + xas_split() one.
For example, to insert an order-0 folio when an order-9 shadow entry is
present (assuming XA_CHUNK_SHIFT is 6), 1 xa_node is needed instead of 8.
xas_try_split_min_order() is introduced to reduce the number of calls to
xas_try_split() during split.
Signed-off-by: Zi Yan <ziy@nvidia.com>
---
include/linux/xarray.h | 7 +++++++
lib/xarray.c | 25 +++++++++++++++++++++++
mm/filemap.c | 46 +++++++++++++++++-------------------------
3 files changed, 51 insertions(+), 27 deletions(-)
diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index 9eb8c7425090..6ef3d682b189 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -1557,6 +1557,7 @@ 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);
+unsigned int xas_try_split_min_order(unsigned int order);
#else
static inline int xa_get_order(struct xarray *xa, unsigned long index)
{
@@ -1583,6 +1584,12 @@ static inline void xas_try_split(struct xa_state *xas, void *entry,
unsigned int order, gfp_t gfp)
{
}
+
+static inline unsigned int xas_try_split_min_order(unsigned int order)
+{
+ return 0;
+}
+
#endif
/**
diff --git a/lib/xarray.c b/lib/xarray.c
index c38beca77830..1805fde1c361 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1133,6 +1133,28 @@ void xas_split(struct xa_state *xas, void *entry, unsigned int order)
}
EXPORT_SYMBOL_GPL(xas_split);
+/**
+ * xas_try_split_min_order() - Minimal split order xas_try_split() can accept
+ * @order: Current entry order.
+ *
+ * xas_try_split() can split a multi-index entry to smaller than @order - 1 if
+ * no new xa_node is needed. This function provides the minimal order
+ * xas_try_split() supports.
+ *
+ * Return: the minimal order xas_try_split() supports
+ *
+ * Context: Any context.
+ *
+ */
+unsigned int xas_try_split_min_order(unsigned int order)
+{
+ if (order % XA_CHUNK_SHIFT == 0)
+ return order == 0 ? 0 : order - 1;
+
+ return order - (order % XA_CHUNK_SHIFT);
+}
+EXPORT_SYMBOL_GPL(xas_try_split_min_order);
+
/**
* xas_try_split() - Try to split a multi-index entry.
* @xas: XArray operation state.
@@ -1145,6 +1167,9 @@ EXPORT_SYMBOL_GPL(xas_split);
* be allocated, the function will use @gfp to get one. If more xa_node are
* needed, the function gives EINVAL error.
*
+ * NOTE: use xas_try_split_min_order() to get next split order instead of
+ * @order - 1 if you want to minmize xas_try_split() calls.
+ *
* Context: Any context. The caller should hold the xa_lock.
*/
void xas_try_split(struct xa_state *xas, void *entry, unsigned int order,
diff --git a/mm/filemap.c b/mm/filemap.c
index 804d7365680c..e28a7a623889 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -860,11 +860,10 @@ EXPORT_SYMBOL_GPL(replace_page_cache_folio);
noinline int __filemap_add_folio(struct address_space *mapping,
struct folio *folio, pgoff_t index, gfp_t gfp, void **shadowp)
{
- XA_STATE(xas, &mapping->i_pages, index);
- void *alloced_shadow = NULL;
- int alloced_order = 0;
+ XA_STATE_ORDER(xas, &mapping->i_pages, index, folio_order(folio));
bool huge;
long nr;
+ unsigned int forder = folio_order(folio);
VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio);
VM_BUG_ON_FOLIO(folio_test_swapbacked(folio), folio);
@@ -873,7 +872,6 @@ noinline int __filemap_add_folio(struct address_space *mapping,
mapping_set_update(&xas, mapping);
VM_BUG_ON_FOLIO(index & (folio_nr_pages(folio) - 1), folio);
- xas_set_order(&xas, index, folio_order(folio));
huge = folio_test_hugetlb(folio);
nr = folio_nr_pages(folio);
@@ -883,7 +881,7 @@ noinline int __filemap_add_folio(struct address_space *mapping,
folio->index = xas.xa_index;
for (;;) {
- int order = -1, split_order = 0;
+ int order = -1;
void *entry, *old = NULL;
xas_lock_irq(&xas);
@@ -901,21 +899,26 @@ noinline int __filemap_add_folio(struct address_space *mapping,
order = xas_get_order(&xas);
}
- /* entry may have changed before we re-acquire the lock */
- if (alloced_order && (old != alloced_shadow || order != alloced_order)) {
- xas_destroy(&xas);
- alloced_order = 0;
- }
-
if (old) {
- if (order > 0 && order > folio_order(folio)) {
+ if (order > 0 && order > forder) {
+ unsigned int split_order = max(forder,
+ xas_try_split_min_order(order));
+
/* How to handle large swap entries? */
BUG_ON(shmem_mapping(mapping));
- if (!alloced_order) {
- split_order = order;
- goto unlock;
+
+ while (order > forder) {
+ xas_set_order(&xas, index, split_order);
+ xas_try_split(&xas, old, order,
+ GFP_NOWAIT);
+ if (xas_error(&xas))
+ goto unlock;
+ order = split_order;
+ split_order =
+ max(xas_try_split_min_order(
+ split_order),
+ forder);
}
- xas_split(&xas, old, order);
xas_reset(&xas);
}
if (shadowp)
@@ -939,17 +942,6 @@ noinline int __filemap_add_folio(struct address_space *mapping,
unlock:
xas_unlock_irq(&xas);
- /* split needed, alloc here and retry. */
- if (split_order) {
- xas_split_alloc(&xas, old, split_order, gfp);
- if (xas_error(&xas))
- goto error;
- alloced_shadow = old;
- alloced_order = split_order;
- xas_reset(&xas);
- continue;
- }
-
if (!xas_nomem(&xas, gfp))
break;
}
--
2.47.2
^ permalink raw reply [flat|nested] 4+ messages in thread* [PATCH 2/2] mm/shmem: use xas_try_split() in shmem_split_large_entry().
2025-02-13 3:43 [PATCH 0/2] Minimize xa_node allocation during xarry split Zi Yan
2025-02-13 3:43 ` [PATCH 1/2] mm/filemap: use xas_try_split() in __filemap_add_folio() Zi Yan
@ 2025-02-13 3:43 ` Zi Yan
2025-02-13 3:46 ` [PATCH 0/2] Minimize xa_node allocation during xarry split Zi Yan
2 siblings, 0 replies; 4+ messages in thread
From: Zi Yan @ 2025-02-13 3:43 UTC (permalink / raw)
To: Matthew Wilcox, linux-mm, linux-fsdevel
Cc: Andrew Morton, Hugh Dickins, Baolin Wang, Kairui Song,
Miaohe Lin, linux-kernel, Zi Yan
During shmem_split_large_entry(), large swap entries are covering n slots
and an order-0 folio needs to be inserted. Instead of splitting all
n slots, only the 1 slot covered by the folio need to be split and the
remaining n-1 shadow entries can be retained with orders ranging from 0 to
n-1. This method only requires (n/XA_CHUNK_SHIFT) new xa_nodes instead of
(n % XA_CHUNK_SHIFT) * (n/XA_CHUNK_SHIFT) new xa_nodes, compared to the
original xas_split_alloc() + xas_split() one.
For example, to split an order-9 large swap entry (assuming XA_CHUNK_SHIFT
is 6), 1 xa_node is needed instead of 8.
xas_try_split_min_order() is used to reduce the number of calls to
xas_try_split() during split.
Signed-off-by: Zi Yan <ziy@nvidia.com>
---
mm/shmem.c | 43 ++++++++++++++++---------------------------
1 file changed, 16 insertions(+), 27 deletions(-)
diff --git a/mm/shmem.c b/mm/shmem.c
index 671f63063fd4..b35ba250c53d 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -2162,14 +2162,14 @@ static int shmem_split_large_entry(struct inode *inode, pgoff_t index,
{
struct address_space *mapping = inode->i_mapping;
XA_STATE_ORDER(xas, &mapping->i_pages, index, 0);
- void *alloced_shadow = NULL;
- int alloced_order = 0, i;
+ int split_order = 0;
+ int i;
/* Convert user data gfp flags to xarray node gfp flags */
gfp &= GFP_RECLAIM_MASK;
for (;;) {
- int order = -1, split_order = 0;
+ int order = -1;
void *old = NULL;
xas_lock_irq(&xas);
@@ -2181,20 +2181,21 @@ static int shmem_split_large_entry(struct inode *inode, pgoff_t index,
order = xas_get_order(&xas);
- /* Swap entry may have changed before we re-acquire the lock */
- if (alloced_order &&
- (old != alloced_shadow || order != alloced_order)) {
- xas_destroy(&xas);
- alloced_order = 0;
- }
-
/* Try to split large swap entry in pagecache */
if (order > 0) {
- if (!alloced_order) {
- split_order = order;
- goto unlock;
+ int cur_order = order;
+
+ split_order = xas_try_split_min_order(cur_order);
+
+ while (cur_order > 0) {
+ xas_set_order(&xas, index, split_order);
+ xas_try_split(&xas, old, cur_order, GFP_NOWAIT);
+ if (xas_error(&xas))
+ goto unlock;
+ cur_order = split_order;
+ split_order =
+ xas_try_split_min_order(split_order);
}
- xas_split(&xas, old, order);
/*
* Re-set the swap entry after splitting, and the swap
@@ -2213,26 +2214,14 @@ static int shmem_split_large_entry(struct inode *inode, pgoff_t index,
unlock:
xas_unlock_irq(&xas);
- /* split needed, alloc here and retry. */
- if (split_order) {
- xas_split_alloc(&xas, old, split_order, gfp);
- if (xas_error(&xas))
- goto error;
- alloced_shadow = old;
- alloced_order = split_order;
- xas_reset(&xas);
- continue;
- }
-
if (!xas_nomem(&xas, gfp))
break;
}
-error:
if (xas_error(&xas))
return xas_error(&xas);
- return alloced_order;
+ return split_order;
}
/*
--
2.47.2
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [PATCH 0/2] Minimize xa_node allocation during xarry split
2025-02-13 3:43 [PATCH 0/2] Minimize xa_node allocation during xarry split Zi Yan
2025-02-13 3:43 ` [PATCH 1/2] mm/filemap: use xas_try_split() in __filemap_add_folio() Zi Yan
2025-02-13 3:43 ` [PATCH 2/2] mm/shmem: use xas_try_split() in shmem_split_large_entry() Zi Yan
@ 2025-02-13 3:46 ` Zi Yan
2 siblings, 0 replies; 4+ messages in thread
From: Zi Yan @ 2025-02-13 3:46 UTC (permalink / raw)
To: Matthew Wilcox, linux-mm, linux-fsdevel
Cc: Andrew Morton, Hugh Dickins, Baolin Wang, Kairui Song,
Miaohe Lin, linux-kernel, Zi Yan
On 12 Feb 2025, at 22:43, 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.
>
> Let me know your comments.
The patch is on top of mm-everything-2025-02-13-02-18.
>
>
> [1] https://lore.kernel.org/linux-mm/Z6YX3RznGLUD07Ao@casper.infradead.org/
> [2] https://lore.kernel.org/linux-mm/20250211155034.268962-2-ziy@nvidia.com/
>
> Zi Yan (2):
> mm/filemap: use xas_try_split() in __filemap_add_folio().
> mm/shmem: use xas_try_split() in shmem_split_large_entry().
>
> include/linux/xarray.h | 7 +++++++
> lib/xarray.c | 25 +++++++++++++++++++++++
> mm/filemap.c | 46 +++++++++++++++++-------------------------
> mm/shmem.c | 43 +++++++++++++++------------------------
> 4 files changed, 67 insertions(+), 54 deletions(-)
>
> --
> 2.47.2
Best Regards,
Yan, Zi
^ permalink raw reply [flat|nested] 4+ messages in thread