Minimize xa_node allocation during xarry split
Subsystems (6)
v3 cover Minimize xa_node allocation during xarry split
Hi Andrew,
It is on top of mm-unstable with old V3 (plus a fixup) reverted, so that you can replace the old one with this. Since the patch 1/2 on mm-unstable tree is not the same as my original one, which caused a compilation issue and would confuse people due to a comment is relocated incorrectly.
Thanks.
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.
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/[email protected]/
[2] https://lore.kernel.org/linux-mm/[email protected]/
[3] 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 | 45 +++++++++++++------------------- mm/shmem.c | 59 ++++++++++++++++++++---------------------- 4 files changed, 78 insertions(+), 58 deletions(-)
Signature · 1 line
2.47.2
PATCH RESEND v3 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 | 45 +++++++++++++++++------------------------- 3 files changed, 50 insertions(+), 27 deletions(-)
include/linux/xarray.h +7 -0
@@ -1556,6 +1556,7 @@ 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); +unsigned int xas_try_split_min_order (unsigned int order);#else static inline int xa_get_order (struct xarray *xa,unsigned long index) {
@@ -1582,6 +1583,12 @@ static inline void xas_try_split(struct xa_state *xas, void *entry, unsigned int order) { } + +static inline unsigned int xas_try_split_min_order (unsigned int order) +{ +return 0 ; +} +#endif /**
lib/xarray.c +25 -0
@@ -1134,6 +1134,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);* needed, the function will use GFP_NOWAIT to get one if xas->xa_alloc is * NULL. If more new 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 +18 -27
81 lines not on this page · raw message
Signature · 1 line
2.47.2
PATCH RESEND v3 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 | 59 ++++++++++++++++++++++++++---------------------------- 1 file changed, 28 insertions(+), 31 deletions(-)
mm/shmem.c +28 -31
@@ -2153,15 +2153,16 @@ 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 , entry_order; +int i;/* Convert user data gfp flags to xarray node gfp flags */ gfp &=GFP_RECLAIM_MASK ;for (;;) { -int order =-1 , split_order =0 ;void *old =NULL ; +int cur_order; +pgoff_t swap_index;xas_lock_irq (&xas); old =xas_load (&xas);
@@ -2170,60 +2171,56 @@ static int shmem_split_large_entry(struct inode *inode, pgoff_t index, goto unlock; } - order =xas_get_order (&xas); + entry_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 ; - } +if (!entry_order) + goto unlock;/* Try to split large swap entry in pagecache */ -if (order >0 ) { -if (!alloced_order) { - split_order = order; + cur_order = entry_order; + swap_index =round_down (index,1 << entry_order); + + split_order =xas_try_split_min_order (cur_order); + +while (cur_order >0 ) { +pgoff_t aligned_index = +round_down (index,1 << cur_order); +pgoff_t swap_offset = aligned_index - swap_index; + +xas_set_order (&xas, index, split_order); +xas_try_split (&xas, old, cur_order); +if (xas_error (&xas)) goto unlock; - } -xas_split (&xas, old, order);/* * Re-set the swap entry after splitting, and the swap * offset of the original large entry must be continuous. */ -for (i =0 ; i <1 << order; i++) { -pgoff_t aligned_index =round_down (index,1 << order); +for (i =0 ; i <1 << cur_order; + i += (1 << split_order)) {swp_entry_t tmp; - tmp =swp_entry (swp_type (swap),swp_offset (swap) + i); + tmp =swp_entry (swp_type (swap), +swp_offset (swap) + swap_offset + + i);__xa_store (&mapping->i_pages, aligned_index + i,swp_to_radix_entry (tmp),0 ); } + cur_order = split_order; + split_order =xas_try_split_min_order (split_order); } 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 entry_order; }/*
Signature · 1 line
2.47.2