Skip to contentSkip to conversation

xfs: Reduce unnecessary searches when searching for the best extents

PATCH Applied Chi Zhiling 3 participants 4 messages Oct 25, 2024 – Nov 2, 2024 XFS filesystem

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 xfs: Reduce unnecessary searches when searching for the best extents

From: Chi Zhiling <[email protected]>

Recently, we found that the CPU spent a lot of time in xfs_alloc_ag_vextent_size when the filesystem has millions of fragmented spaces.

The reason is that we conducted much extra searching for extents that could not yield a better result, and these searches would cost a lot of time when there were millions of extents to search through. Even if we get the same result length, we don't switch our choice to the new one, so we can definitely terminate the search early.

Since the result length cannot exceed the found length, when the found length equals the best result length we already have, we can conclude the search.

We did a test in that filesystem:
[root@localhost ~]# xfs_db -c freesp /dev/vdb
from to extents blocks pct

      1       1     215     215   0.01
      2       3  994476 1988952  99.99

Before this patch:

 0)               |  xfs_alloc_ag_vextent_size [xfs]() {
 0) * 15597.94 us |  }

After this patch:
0) | xfs_alloc_ag_vextent_size [xfs]() {
0) 19.176 us | }

---
 fs/xfs/libxfs/xfs_alloc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +1 -1
index 04f64cf9777e..22bdbb3e9980 100644
@@ -1923,7 +1923,7 @@ xfs_alloc_ag_vextent_size(
 				error = -EFSCORRUPTED;
 				goto error0;
 			}
-			if (flen < bestrlen)
+			if (flen <= bestrlen)
 				break;
 			busy = xfs_alloc_compute_aligned(args, fbno, flen,
 					&rbno, &rlen, &busy_gen);
Signature · 1 line
2.43.0
Reviewed-by on v1 1/1
#1 lore raw
Quoted 16 lines · Chi Zhiling

From: Chi Zhiling <[email protected]>

Recently, we found that the CPU spent a lot of time in xfs_alloc_ag_vextent_size when the filesystem has millions of fragmented spaces.

The reason is that we conducted much extra searching for extents that could not yield a better result, and these searches would cost a lot of time when there were millions of extents to search through. Even if we get the same result length, we don't switch our choice to the new one, so we can definitely terminate the search early.

Since the result length cannot exceed the found length, when the found length equals the best result length we already have, we can conclude the search.

Quoted 5 lines

We did a test in that filesystem:
[root@localhost ~]# xfs_db -c freesp /dev/vdb
from to extents blocks pct

      1       1     215     215   0.01
      2       3  994476 1988952  99.99

Ok, so you have *badly* fragmented free space. That going to cause lots more problems than only "allocation searches take a long time". e.g. you can't allocate inodes in a AG that is fragmented this badly - not even sparse inode clusters....

Quoted 7 lines

Before this patch:

 0)               |  xfs_alloc_ag_vextent_size [xfs]() {
 0) * 15597.94 us |  }

After this patch:
0) | xfs_alloc_ag_vextent_size [xfs]() {
0) 19.176 us | }

Yup, that's a good improvement.

Quoted 10 lines
---
 fs/xfs/libxfs/xfs_alloc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +0 -0
index 04f64cf9777e..22bdbb3e9980 100644

fs/xfs/libxfs/xfs_alloc.c xfs_alloc_ag_vextent_size( · line 1929

Quoted 8 lines
fs/xfs/libxfs/xfs_alloc.c +1 -1
@@ -1923,7 +1923,7 @@ xfs_alloc_ag_vextent_size(
 				error = -EFSCORRUPTED;
 				goto error0;
 			}
-			if (flen < bestrlen)
+			if (flen <= bestrlen)
 				break;
 			busy = xfs_alloc_compute_aligned(args, fbno, flen,
 					&rbno, &rlen, &busy_gen);

Yup, I think that works fine. We aren't caring about using locality as a secondary search key so as soon as we have a candidate extent of a length that that the remaining extents in the free space btree can't improve on, we are done.

Nice work!

Signature · 2 lines
Dave Chinner
[email protected]
#2 lore raw
Quoted 22 lines · Dave Chinner
Quoted 16 lines · Chi Zhiling

From: Chi Zhiling <[email protected]>

Recently, we found that the CPU spent a lot of time in xfs_alloc_ag_vextent_size when the filesystem has millions of fragmented spaces.

The reason is that we conducted much extra searching for extents that could not yield a better result, and these searches would cost a lot of time when there were millions of extents to search through. Even if we get the same result length, we don't switch our choice to the new one, so we can definitely terminate the search early.

Since the result length cannot exceed the found length, when the found length equals the best result length we already have, we can conclude the search.

Quoted 5 lines

We did a test in that filesystem:
[root@localhost ~]# xfs_db -c freesp /dev/vdb

    from      to extents  blocks    pct
       1       1     215     215   0.01
       2       3  994476 1988952  99.99
Quoted 4 lines

Ok, so you have *badly* fragmented free space. That going to cause lots more problems than only "allocation searches take a long time". e.g. you can't allocate inodes in a AG that is fragmented this badly - not even sparse inode clusters....

Yes, this usually happens in some systems that use Mysql table compression, which continuously punches holes in file, eventually causing most fragment lengths to converge to the hole size.

Quoted 34 lines
Quoted 8 lines

Before this patch:

  0)               |  xfs_alloc_ag_vextent_size [xfs]() {
  0) * 15597.94 us |  }

After this patch:
0) | xfs_alloc_ag_vextent_size [xfs]() {
0) 19.176 us | }

Yup, that's a good improvement.

Quoted 10 lines
---
  fs/xfs/libxfs/xfs_alloc.c | 2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +0 -0
index 04f64cf9777e..22bdbb3e9980 100644

fs/xfs/libxfs/xfs_alloc.c xfs_alloc_ag_vextent_size( · line 1929

Quoted 8 lines
fs/xfs/libxfs/xfs_alloc.c +1 -1
@@ -1923,7 +1923,7 @@ xfs_alloc_ag_vextent_size(
  				error = -EFSCORRUPTED;
  				goto error0;
  			}
-			if (flen < bestrlen)
+			if (flen <= bestrlen)
  				break;
  			busy = xfs_alloc_compute_aligned(args, fbno, flen,
  					&rbno, &rlen, &busy_gen);

Yup, I think that works fine. We aren't caring about using locality as a secondary search key so as soon as we have a candidate extent of a length that that the remaining extents in the free space btree can't improve on, we are done.

Quoted 3 lines

Nice work!

Thanks!

Quoted 1 line
maintainer Applied
#3 lore raw
In reply to Chi Zhiling
Quoted 11 lines · Chi Zhiling

Recently, we found that the CPU spent a lot of time in xfs_alloc_ag_vextent_size when the filesystem has millions of fragmented spaces.

The reason is that we conducted much extra searching for extents that could not yield a better result, and these searches would cost a lot of time when there were millions of extents to search through. Even if we get the same result length, we don't switch our choice to the new one, so we can definitely terminate the search early.

[...]

Applied to for-next, thanks!

[1/1] xfs: Reduce unnecessary searches when searching for the best extents

      commit: 3ef22684038aa577c10972ee9c6a2455f5fac941

Best regards,

Signature · 1 line
Carlos Maiolino <[email protected]>