Minimize xa_node allocation during xarry split
Subsystems (6)
cover Minimize xa_node allocation during xarry split
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.
[1] https://lore.kernel.org/linux-mm/[email protected]/
[2] https://lore.kernel.org/linux-mm/[email protected]/
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(-)
Signature · 1 line
2.47.2
PATCH 1/2 mm/filemap: use xas_try_split() in __filemap_add_folio().
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.
--- include/linux/xarray.h | 7 +++++++ lib/xarray.c | 25 +++++++++++++++++++++++ mm/filemap.c | 46 +++++++++++++++++------------------------- 3 files changed, 51 insertions(+), 27 deletions(-)
include/linux/xarray.h +7 -0
@@ -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 /**
lib/xarray.c +25 -0
@@ -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,
mm/filemap.c +19 -27
82 lines not on this page · raw message
Signature · 1 line
2.47.2
PATCH 2/2 mm/shmem: use xas_try_split() in shmem_split_large_entry().
In reply to Zi YanDuring 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.
--- mm/shmem.c | 43 ++++++++++++++++--------------------------- 1 file changed, 16 insertions(+), 27 deletions(-)
mm/shmem.c +16 -27
@@ -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; }/*
Signature · 1 line
2.47.2
Quoted 49 lines · Zi Yan
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_nodeallocations. But its callers,__filemap_add_folio()andshmem_split_large_entry(), use at most 1xa_node. To minimizexa_nodeallocation 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()andshmem_split_large_entry().
xas_split_alloc()andxas_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 toxas_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_SHIFTdoes not requirexa_nodeallocation and requires 1xa_nodewhen n=l *XA_CHUNK_SHIFTand m = n - 1, so it is OK to usexas_try_split()with n > m + 1 when no newxa_nodeis needed.
Quoted 3 lines
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.
Quoted 9 lines
[1] https://lore.kernel.org/linux-mm/[email protected]/
[2] https://lore.kernel.org/linux-mm/[email protected]/Zi Yan (2):
mm/filemap: usexas_try_split()in__filemap_add_folio(). mm/shmem: usexas_try_split()inshmem_split_large_entry().
Quoted 8 lines
include/linux/xarray.h | 7 +++++++ lib/xarray.c | 25 +++++++++++++++++++++++ mm/filemap.c | 46 +++++++++++++++++------------------------- mm/shmem.c | 43 +++++++++++++++------------------------ 4 files changed, 67 insertions(+), 54 deletions(-)Signature · 1 line
2.47.2
Best Regards,
Yan, Zi