mm/filemap: optimize folio adding and splitting

From: Kairui Song <[email protected]>

xas_split_alloc could fail with NOMEM, and in such case, it should abort early instead of keep going and fail the xas_split below.

Signed-off-by Kairui Song <[email protected]>

 mm/filemap.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

mm/filemap.c +4 -1

index 7437b2bd75c1..f07ea0b97698 100644
@@ -880,9 +880,12 @@ noinline int __filemap_add_folio(struct address_space *mapping,
 		unsigned int order = xa_get_order(xas.xa, xas.xa_index);
 		void *entry, *old = NULL;
 
-		if (order > folio_order(folio))
+		if (order > folio_order(folio)) {
 			xas_split_alloc(&xas, xa_load(xas.xa, xas.xa_index),
 					order, gfp);
+			if (xas_error(&xas))
+				goto error;
+		}
 		xas_lock_irq(&xas);
 		xas_for_each_conflict(&xas, entry) {
 			old = entry;

Signature · 1 line

2.43.0

From: Kairui Song <[email protected]>

__filemap_add_folio only has two callers, one never passes hugetlb folio and one always passes in hugetlb folio. So move the hugetlb related cgroup charging out of it to make the code cleaner.

Signed-off-by Kairui Song <[email protected]>

From: Kairui Song <[email protected]>

It can be used after xas_load to check the order of loaded entries. Compared to xa_get_order, it saves an XA_STATE and avoid a rewalk.

Signed-off-by Kairui Song <[email protected]>

+EXPORT_SYMBOL(xas_get_order);

From: Kairui Song <[email protected]>

Instead of doing multiple tree walks, do one optimism range check with lock hold, and exit if raced with another insertion. If a shadow exists, check it with a new xas_get_order helper before releasing the lock to avoid redundant tree walks for getting its order.

Drop the lock and do the allocation only if a split is needed.

In the best case, it only need to walk the tree once. If it needs to alloc and split, 3 walks are issued (One for first ranced conflict check and order retrieving, one for the second check after allocation, one for the insert after split).

Testing with 4k pages, in an 8G cgroup, with 20G brd as block device:

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine=mmap --rw=randread --time_based \
--ramp_time=30s --runtime=5m --group_reporting

Before:
bw ( MiB/s): min= 790, max= 3665, per=100.00%, avg=2499.17, stdev=20.64, samples=8698
iops : min=202295, max=938417, avg=639785.81, stdev=5284.08, samples=8698

After (+4%):
bw ( MiB/s): min= 451, max= 3868, per=100.00%, avg=2599.83, stdev=23.39, samples=8653
iops : min=115596, max=990364, avg=665556.34, stdev=5988.20, samples=8653

Test result with THP (do a THP randread then switch to 4K page in hope it issues a lot of splitting):

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine mmap -thp=1 --readonly \
--rw=randread --random_distribution=random \
--time_based --runtime=5m --group_reporting

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine mmap --readonly \
--rw=randread --random_distribution=random \
--time_based --runtime=5s --group_reporting

Before:
bw ( KiB/s): min=28071, max=62359, per=100.00%, avg=53542.44, stdev=179.77, samples=9520
iops : min= 7012, max=15586, avg=13379.39, stdev=44.94, samples=9520
bw ( MiB/s): min= 2457, max= 6193, per=100.00%, avg=3923.21, stdev=82.48, samples=144
iops : min=629220, max=1585642, avg=1004340.78, stdev=21116.07, samples=144

After (+-0.0%):
bw ( KiB/s): min=30561, max=63064, per=100.00%, avg=53635.82, stdev=177.21, samples=9520
iops : min= 7636, max=15762, avg=13402.82, stdev=44.29, samples=9520
bw ( MiB/s): min= 2449, max= 6145, per=100.00%, avg=3914.68, stdev=81.15, samples=144
iops : min=627106, max=1573156, avg=1002158.11, stdev=20774.77, samples=144

The performance is better (+4%) for 4K cached read and unchanged for THP.

Signed-off-by Kairui Song <[email protected]>

---
 mm/filemap.c | 127 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 76 insertions(+), 51 deletions(-)

mm/filemap.c +0 -0

index 6bbec8783793..c1484bcdbddb 100644

mm/filemap.c +7 -0

+{
+	void *entry, *shadow, *alloced_shadow = NULL;
+	int order, alloced_order = 0;
+
+	gfp &= GFP_RECLAIM_MASK;
+	for (;;) {
+		shadow = NULL;

mm/filemap.c +24 -0

+			if (shadowp)
+				*shadowp = shadow;
+		}
+
+		xas_store(xas, folio);
+		/* Success, return with mapping locked */
+		if (!xas_error(xas))
+			return 0;
+unlock:
+		/*
+		 * Unlock path, if errored, return unlocked.
+		 * If allocation needed, alloc and retry.
+		 */
+		xas_unlock_irq(xas);
+		if (order) {
+			if (unlikely(alloced_order))
+				xas_destroy(xas);
+			xas_split_alloc(xas, shadow, order, gfp);
+			if (!xas_error(xas)) {
+				alloced_shadow = shadow;
+				alloced_order = order;
+			}
+			goto next;
+		}

Quoted 68 lines · Kairui Song

From: Kairui Song <[email protected]>

Instead of doing multiple tree walks, do one optimism range check with lock hold, and exit if raced with another insertion. If a shadow exists, check it with a new xas_get_order helper before releasing the lock to avoid redundant tree walks for getting its order.

Drop the lock and do the allocation only if a split is needed.

In the best case, it only need to walk the tree once. If it needs to alloc and split, 3 walks are issued (One for first ranced conflict check and order retrieving, one for the second check after allocation, one for the insert after split).

Testing with 4k pages, in an 8G cgroup, with 20G brd as block device:

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine=mmap --rw=randread --time_based \
--ramp_time=30s --runtime=5m --group_reporting

Before:
bw ( MiB/s): min= 790, max= 3665, per=100.00%, avg=2499.17, stdev=20.64, samples=8698
iops : min=202295, max=938417, avg=639785.81, stdev=5284.08, samples=8698

After (+4%):
bw ( MiB/s): min= 451, max= 3868, per=100.00%, avg=2599.83, stdev=23.39, samples=8653
iops : min=115596, max=990364, avg=665556.34, stdev=5988.20, samples=8653

Test result with THP (do a THP randread then switch to 4K page in hope it issues a lot of splitting):

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine mmap -thp=1 --readonly \
--rw=randread --random_distribution=random \
--time_based --runtime=5m --group_reporting

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine mmap --readonly \
--rw=randread --random_distribution=random \
--time_based --runtime=5s --group_reporting

Before:
bw ( KiB/s): min=28071, max=62359, per=100.00%, avg=53542.44, stdev=179.77, samples=9520
iops : min= 7012, max=15586, avg=13379.39, stdev=44.94, samples=9520
bw ( MiB/s): min= 2457, max= 6193, per=100.00%, avg=3923.21, stdev=82.48, samples=144
iops : min=629220, max=1585642, avg=1004340.78, stdev=21116.07, samples=144

After (+-0.0%):
bw ( KiB/s): min=30561, max=63064, per=100.00%, avg=53635.82, stdev=177.21, samples=9520
iops : min= 7636, max=15762, avg=13402.82, stdev=44.29, samples=9520
bw ( MiB/s): min= 2449, max= 6145, per=100.00%, avg=3914.68, stdev=81.15, samples=144
iops : min=627106, max=1573156, avg=1002158.11, stdev=20774.77, samples=144

The performance is better (+4%) for 4K cached read and unchanged for THP.

Signed-off-by Kairui Song <[email protected]>

---
 mm/filemap.c | 127 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 76 insertions(+), 51 deletions(-)

mm/filemap.c +0 -0

index 6bbec8783793..c1484bcdbddb 100644
@@ -848,12 +848,77 @@ void replace_page_cache_folio(struct folio *old, struct folio *new)
 }
 EXPORT_SYMBOL_GPL(replace_page_cache_folio);
 

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 852

Quoted 2 lines

mm/filemap.c +2 -0

+static int __split_add_folio_locked(struct xa_state *xas, struct folio *folio,
+                                 pgoff_t index, gfp_t gfp, void **shadowp)

I don't love the name of this function. Splitting is a rare thing that it does. I'd suggest it's more filemap_store().

Quoted 12 lines

mm/filemap.c +11 -0

+{
+     void *entry, *shadow, *alloced_shadow = NULL;
+     int order, alloced_order = 0;
+
+     gfp &= GFP_RECLAIM_MASK;
+     for (;;) {
+             shadow = NULL;
+             order = 0;
+
+             xas_for_each_conflict(xas, entry) {
+                     if (!xa_is_value(entry))

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 869

Quoted 6 lines

mm/filemap.c +6 -0

+                             return -EEXIST;
+                     shadow = entry;
+             }
+
+             if (shadow) {
+                     if (shadow == xas_reload(xas)) {

Why do you need the xas_reload here?

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 879

Quoted 11 lines

mm/filemap.c +10 -0

+                             order = xas_get_order(xas);
+                             if (order && order > folio_order(folio)) {
+                                     /* entry may have been split before we acquired lock */
+                                     if (shadow != alloced_shadow || order != alloced_order)
+                                             goto unlock;
+                                     xas_split(xas, shadow, order);
+                                     xas_reset(xas);
+                             }
+                             order = 0;
+                     }

I don't think this is right. I think we can end up skipping a split and storing a folio into a slot which is of greater order than the folio we're storing.

Quoted 30 lines

mm/filemap.c +29 -0

+                     if (shadowp)
+                             *shadowp = shadow;
+             }
+
+             xas_store(xas, folio);
+             /* Success, return with mapping locked */
+             if (!xas_error(xas))
+                     return 0;
+unlock:
+             /*
+              * Unlock path, if errored, return unlocked.
+              * If allocation needed, alloc and retry.
+              */
+             xas_unlock_irq(xas);
+             if (order) {
+                     if (unlikely(alloced_order))
+                             xas_destroy(xas);
+                     xas_split_alloc(xas, shadow, order, gfp);
+                     if (!xas_error(xas)) {
+                             alloced_shadow = shadow;
+                             alloced_order = order;
+                     }
+                     goto next;
+             }
+             /* xas_nomem result checked by xas_error below */
+             xas_nomem(xas, gfp);
+next:
+             xas_lock_irq(xas);
+             if (xas_error(xas))

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 913

Quoted 5 lines

mm/filemap.c +5 -0

+                     return xas_error(xas);
+
+             xas_reset(xas);
+     }
+}

Splitting this out into a different function while changing the logic really makes this hard to review ;-(

I don't object to splitting the function, but maybe two patches; one to move the logic and a second to change it?

Quoted 70 lines · Matthew Wilcox

Quoted 68 lines · Kairui Song

From: Kairui Song <[email protected]>

Instead of doing multiple tree walks, do one optimism range check with lock hold, and exit if raced with another insertion. If a shadow exists, check it with a new xas_get_order helper before releasing the lock to avoid redundant tree walks for getting its order.

Drop the lock and do the allocation only if a split is needed.

In the best case, it only need to walk the tree once. If it needs to alloc and split, 3 walks are issued (One for first ranced conflict check and order retrieving, one for the second check after allocation, one for the insert after split).

Testing with 4k pages, in an 8G cgroup, with 20G brd as block device:

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine=mmap --rw=randread --time_based \
--ramp_time=30s --runtime=5m --group_reporting

Before:
bw ( MiB/s): min= 790, max= 3665, per=100.00%, avg=2499.17, stdev=20.64, samples=8698
iops : min=202295, max=938417, avg=639785.81, stdev=5284.08, samples=8698

After (+4%):
bw ( MiB/s): min= 451, max= 3868, per=100.00%, avg=2599.83, stdev=23.39, samples=8653
iops : min=115596, max=990364, avg=665556.34, stdev=5988.20, samples=8653

Test result with THP (do a THP randread then switch to 4K page in hope it issues a lot of splitting):

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine mmap -thp=1 --readonly \
--rw=randread --random_distribution=random \
--time_based --runtime=5m --group_reporting

fio -name=cached --numjobs=16 --filename=/mnt/test.img \
--buffered=1 --ioengine mmap --readonly \
--rw=randread --random_distribution=random \
--time_based --runtime=5s --group_reporting

Before:
bw ( KiB/s): min=28071, max=62359, per=100.00%, avg=53542.44, stdev=179.77, samples=9520
iops : min= 7012, max=15586, avg=13379.39, stdev=44.94, samples=9520
bw ( MiB/s): min= 2457, max= 6193, per=100.00%, avg=3923.21, stdev=82.48, samples=144
iops : min=629220, max=1585642, avg=1004340.78, stdev=21116.07, samples=144

After (+-0.0%):
bw ( KiB/s): min=30561, max=63064, per=100.00%, avg=53635.82, stdev=177.21, samples=9520
iops : min= 7636, max=15762, avg=13402.82, stdev=44.29, samples=9520
bw ( MiB/s): min= 2449, max= 6145, per=100.00%, avg=3914.68, stdev=81.15, samples=144
iops : min=627106, max=1573156, avg=1002158.11, stdev=20774.77, samples=144

The performance is better (+4%) for 4K cached read and unchanged for THP.

Signed-off-by Kairui Song <[email protected]>

---
 mm/filemap.c | 127 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 76 insertions(+), 51 deletions(-)

mm/filemap.c +0 -0

index 6bbec8783793..c1484bcdbddb 100644
@@ -848,12 +848,77 @@ void replace_page_cache_folio(struct folio *old, struct folio *new)
 }
 EXPORT_SYMBOL_GPL(replace_page_cache_folio);
 

Quoted 3 lines

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 852

Quoted 2 lines

mm/filemap.c +2 -0

+static int __split_add_folio_locked(struct xa_state *xas, struct folio *folio,
+                                 pgoff_t index, gfp_t gfp, void **shadowp)

Thanks for the very helpful review!

Quoted 2 lines

I don't love the name of this function. Splitting is a rare thing that it does. I'd suggest it's more filemap_store().

Yes, the function name is a bit misleading indeed, I can rename it as you suggested, eg. __filemap_store_locked ?

Quoted 12 lines

Quoted 12 lines

mm/filemap.c +11 -0

+{
+     void *entry, *shadow, *alloced_shadow = NULL;
+     int order, alloced_order = 0;
+
+     gfp &= GFP_RECLAIM_MASK;
+     for (;;) {
+             shadow = NULL;
+             order = 0;
+
+             xas_for_each_conflict(xas, entry) {
+                     if (!xa_is_value(entry))

Quoted 8 lines

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 869

Quoted 6 lines

mm/filemap.c +6 -0

+                             return -EEXIST;
+                     shadow = entry;
+             }
+
+             if (shadow) {
+                     if (shadow == xas_reload(xas)) {

Why do you need the xas_reload here?

This part of code works based on the guarantee that If there is a larger entry, it will be the first and only entry iterated by xas_for_each_conflict/xas_find_conflict. I added an xas_reload is here to ensure that. But on second thought, this seems not needed indeed.

Will it be better if I write this part this way?

+ shadow = NULL;
+ order = -1;
+ xas_for_each_conflict(xas, entry) {

(quoted diff) +11 -0

+          /*
+          * If there is a larger entry, it will be the first
+          * and only entry iterated.
+          */
+         if (order == -1)
+                  order = xas_get_order(xas);
+         shadow = entry;
+ }
+
+ if (shadow) {
+          /* check if alloc & split need, or if previous alloc is

still valid */

If there is a larger slot, xas_for_each_conflict and check above should catch that?

Quoted 30 lines

Quoted 30 lines

mm/filemap.c +29 -0

+                     if (shadowp)
+                             *shadowp = shadow;
+             }
+
+             xas_store(xas, folio);
+             /* Success, return with mapping locked */
+             if (!xas_error(xas))
+                     return 0;
+unlock:
+             /*
+              * Unlock path, if errored, return unlocked.
+              * If allocation needed, alloc and retry.
+              */
+             xas_unlock_irq(xas);
+             if (order) {
+                     if (unlikely(alloced_order))
+                             xas_destroy(xas);
+                     xas_split_alloc(xas, shadow, order, gfp);
+                     if (!xas_error(xas)) {
+                             alloced_shadow = shadow;
+                             alloced_order = order;
+                     }
+                     goto next;
+             }
+             /* xas_nomem result checked by xas_error below */
+             xas_nomem(xas, gfp);
+next:
+             xas_lock_irq(xas);
+             if (xas_error(xas))

Quoted 8 lines

mm/filemap.c void replace_page_cache_folio(struct folio *old, struct folio *new) · line 913

Quoted 5 lines

mm/filemap.c +5 -0

+                     return xas_error(xas);
+
+             xas_reset(xas);
+     }
+}

Splitting this out into a different function while changing the logic really makes this hard to review ;-(

Sorry about this :(

This patch basically rewrites the logic of __filemap_add_folio and the function is getting long, so I thought it would be easier to understand if we split it out.
I initially updated the code in place but that change diff seems more messy to me.

Quoted 4 lines

I don't object to splitting the function, but maybe two patches; one to move the logic and a second to change it?

I can keep it in place in V2.