Skip to contentSkip to conversation

A small improvement in the allocation algorithm

RFC PATCH In review Carlos Maiolino 3 participants 11 messages Sep 18, 2019 – Sep 25, 2019 XFS filesystem

lore
Share & tools
lore
#0 lore raw

cover A small improvement in the allocation algorithm

This is totally based on the discussion between Brian, Dave and me regarding the issues we have on the allocation mechanism, and this patchset is just used to put the ideas together.

Dave, this is a small improvement based on your hack on your original patch, to 'fix' the total number. And based on my last reply to the thread

It still does need improvement, and I need to check the math, but I think we should maybe start here.

I just removed the hack from your patch, and moved the args.total fix to the 2nd patch.

What you guys think about it?

Carlos Maiolino (1):
xfs: Limit total allocation request to maximum possible

Dave Chinner (1):
xfs: cap longest free extent to maximum allocatable

 fs/xfs/libxfs/xfs_alloc.c | 3 ++-
 fs/xfs/libxfs/xfs_bmap.c  | 5 +++++
 2 files changed, 7 insertions(+), 1 deletion(-)
Signature · 1 line
2.20.1
#1 lore raw

PATCH 1/2 xfs: cap longest free extent to maximum allocatable

From: Dave Chinner <[email protected]>

Cap longest extent to the largest we can allocate based on limits calculated at mount time. Dynamic state (such as finobt blocks) can result in the longest free extent exceeding the size we can allocate, and that results in failure to align full AG allocations when the AG is empty.

Result:

xfs_io-4413 [003] 426.412459: xfs_alloc_vextent_loopfailed: dev 8:96 agno 0 agbno 32 minlen 243968 maxlen 244000 mod 0 prod 1 minleft 1 total 262148 alignment 32 minalignslop 0 len 0 type NEAR_BNO otype START_BNO wasdel 0 wasfromfl 0 resv 0 datatype 0x5 firstblock 0xffffffffffffffff

minlen and maxlen are now separated by the alignment size, and allocation fails because args.total > free space in the AG.

---
 fs/xfs/libxfs/xfs_alloc.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +2 -1
index 372ad55631fc..35b39fc863a0 100644
@@ -1989,7 +1989,8 @@ xfs_alloc_longest_free_extent(
 	 * reservations and AGFL rules in place, we can return this extent.
 	 */
 	if (pag->pagf_longest > delta)
-		return pag->pagf_longest - delta;
+		return min_t(xfs_extlen_t, pag->pag_mount->m_ag_max_usable,
+				pag->pagf_longest - delta);
 
 	/* Otherwise, let the caller try for 1 block if there's space. */
 	return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
Signature · 1 line
2.20.1
#2 lore raw

Re: [PATCH 1/2] xfs: cap longest free extent to maximum allocatable

Quoted 10 lines · Carlos Maiolino

From: Dave Chinner <[email protected]>

Cap longest extent to the largest we can allocate based on limits calculated at mount time. Dynamic state (such as finobt blocks) can result in the longest free extent exceeding the size we can allocate, and that results in failure to align full AG allocations when the AG is empty.

Result:

Quoted 8 lines

xfs_io-4413 [003] 426.412459: xfs_alloc_vextent_loopfailed: dev 8:96 agno 0 agbno 32 minlen 243968 maxlen 244000 mod 0 prod 1 minleft 1 total 262148 alignment 32 minalignslop 0 len 0 type NEAR_BNO otype START_BNO wasdel 0 wasfromfl 0 resv 0 datatype 0x5 firstblock 0xffffffffffffffff

minlen and maxlen are now separated by the alignment size, and allocation fails because args.total > free space in the AG.

---

Seems fine, but what about the bma.minlen alignment fix (in xfs_bmap_btalloc()) Dave suggested in the previous thread?

Brian

Quoted 20 lines
 fs/xfs/libxfs/xfs_alloc.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +2 -1
index 372ad55631fc..35b39fc863a0 100644
@@ -1989,7 +1989,8 @@ xfs_alloc_longest_free_extent(
 	 * reservations and AGFL rules in place, we can return this extent.
 	 */
 	if (pag->pagf_longest > delta)
-		return pag->pagf_longest - delta;
+		return min_t(xfs_extlen_t, pag->pag_mount->m_ag_max_usable,
+				pag->pagf_longest - delta);
 
 	/* Otherwise, let the caller try for 1 block if there's space. */
 	return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
Signature · 1 line
2.20.1
#3 lore raw

Re: [PATCH 1/2] xfs: cap longest free extent to maximum allocatable

Quoted 16 lines · Brian Foster
Quoted 15 lines · Carlos Maiolino

From: Dave Chinner <[email protected]>

Cap longest extent to the largest we can allocate based on limits calculated at mount time. Dynamic state (such as finobt blocks) can result in the longest free extent exceeding the size we can allocate, and that results in failure to align full AG allocations when the AG is empty.

Result:

xfs_io-4413 [003] 426.412459: xfs_alloc_vextent_loopfailed: dev 8:96 agno 0 agbno 32 minlen 243968 maxlen 244000 mod 0 prod 1 minleft 1 total 262148 alignment 32 minalignslop 0 len 0 type NEAR_BNO otype START_BNO wasdel 0 wasfromfl 0 resv 0 datatype 0x5 firstblock 0xffffffffffffffff

minlen and maxlen are now separated by the alignment size, and allocation fails because args.total > free space in the AG.

Quoted 6 lines
Quoted 3 lines

---

Seems fine, but what about the bma.minlen alignment fix (in xfs_bmap_btalloc()) Dave suggested in the previous thread?

I forgot to git add that while playing with this set :P

Quoted 23 lines

Brian

Quoted 20 lines
 fs/xfs/libxfs/xfs_alloc.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
fs/xfs/libxfs/xfs_alloc.c +2 -1
index 372ad55631fc..35b39fc863a0 100644
@@ -1989,7 +1989,8 @@ xfs_alloc_longest_free_extent(
 	 * reservations and AGFL rules in place, we can return this extent.
 	 */
 	if (pag->pagf_longest > delta)
-		return pag->pagf_longest - delta;
+		return min_t(xfs_extlen_t, pag->pag_mount->m_ag_max_usable,
+				pag->pagf_longest - delta);
 
 	/* Otherwise, let the caller try for 1 block if there's space. */
 	return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
Signature · 1 line
2.20.1
Signature · 1 line
Carlos
#4 lore raw

PATCH 2/2 xfs: Limit total allocation request to maximum possible

In reply to Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

---
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +5 -0
index 07aad70f3931..3aa0bf5cc7e3 100644
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
+		/* We can never have total larger than blen, so trim it now */
+		if (args.total > blen)
+			args.total = blen;
+
 		if (error)
 			return error;
 	} else if (ap->tp->t_flags & XFS_TRANS_LOWMODE) {
Signature · 1 line
2.20.1
#5 lore raw

Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible

Quoted 7 lines · Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

---

Confused.. what was wrong with the original bma.total patch that it needs to be replaced? I was assuming we'd replace the allocation retry patch with the minlen alignment fixups and combine those with the bma.total patch to fix the problem. Hm?

Quoted 8 lines
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +0 -0
index 07aad70f3931..3aa0bf5cc7e3 100644

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_btalloc( · line 3484

Quoted 8 lines
fs/xfs/libxfs/xfs_bmap.c +5 -0
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
+		/* We can never have total larger than blen, so trim it now */
+		if (args.total > blen)
+			args.total = blen;
+

I don't think this is safe. The reason the original patch only updated certain callers is because those callers only used it for extra blocks that are already incorported into bma.minleft by the bmap layer itself. There are still other callers for which bma.total is specifically intended to be larger than the map size.

(I think the whole total thing is still kind of a confusing mess in this regard, but fixing that is a separate problem.)

Brian

Quoted 6 lines
fs/xfs/libxfs/xfs_bmap.c +0 -0
 		if (error)
 			return error;
 	} else if (ap->tp->t_flags & XFS_TRANS_LOWMODE) {
Signature · 1 line
2.20.1
#6 lore raw

Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible

Quoted 11 lines · Brian Foster
Quoted 7 lines · Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

---

Confused.. what was wrong with the original bma.total patch that it needs to be replaced?

At this point in time, what you mean by the 'original' patch? :) Yours? Or Dave's?

If you meant yours, I was just trying to find out a way to fix it without modifying the callers, nothing else than that.

If you meant regarding Dave's proposal, as he tagged his proposal as a /* Hack */, I was just looking for ways to change total, instead of cropping it to 0.

And giving the fact args.total > blen seems unreasonable, giving it will certainly tail here, I just thought it might be a reasonable way to change args.total value.

By no means this patchset was meant to supersede yours or Dave's idea though, I was just looking for a different approach, if feasible.

Quoted 18 lines

I was assuming we'd replace the allocation retry
patch with the minlen alignment fixups and combine those with the bma.total patch to fix the problem. Hm?

Quoted 14 lines
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +3 -0
index 07aad70f3931..3aa0bf5cc7e3 100644
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
+		/* We can never have total larger than blen, so trim it now */
+		if (args.total > blen)
Quoted 8 lines

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_btalloc( · line 3484

Quoted 2 lines
fs/xfs/libxfs/xfs_bmap.c +2 -0
+			args.total = blen;
+

I don't think this is safe. The reason the original patch only updated certain callers is because those callers only used it for extra blocks that are already incorported into bma.minleft by the bmap layer itself. There are still other callers for which bma.total is specifically intended to be larger than the map size.

Afaik, yes, but still, total is basically used to attempt an allocation of data
+ metadata on the same AG if possible, reducing args.total to match blen, the 'worst' case would be to have an allocation of data + metadata on different ags, which, if total is larger than blen, it will fall into that behavior anyway.

Quoted 9 lines

Brian

Quoted 6 lines
fs/xfs/libxfs/xfs_bmap.c +0 -0
 		if (error)
 			return error;
 	} else if (ap->tp->t_flags & XFS_TRANS_LOWMODE) {
Signature · 1 line
2.20.1
Signature · 1 line
Carlos
#7 lore raw

Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible

Quoted 7 lines · Carlos Maiolino
Quoted 6 lines · Brian Foster
Quoted 5 lines · Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

---

Confused.. what was wrong with the original bma.total patch that it needs to be replaced?

At this point in time, what you mean by the 'original' patch? :) Yours? Or Dave's?

The original patch I posted..

Quoted 10 lines

If you meant yours, I was just trying to find out a way to fix it without modifying the callers, nothing else than that.

If you meant regarding Dave's proposal, as he tagged his proposal as a /* Hack */, I was just looking for ways to change total, instead of cropping it to 0.

And giving the fact args.total > blen seems unreasonable, giving it will certainly tail here, I just thought it might be a reasonable way to change args.total value.

I think the code is flaky, but I'm not sure why that's unreasonable. The intent of args.total is to be larger than the mapping length.

Quoted 31 lines

By no means this patchset was meant to supersede yours or Dave's idea though, I was just looking for a different approach, if feasible.

Quoted 18 lines

I was assuming we'd replace the allocation retry
patch with the minlen alignment fixups and combine those with the bma.total patch to fix the problem. Hm?

Quoted 14 lines
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +3 -0
index 07aad70f3931..3aa0bf5cc7e3 100644
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
+		/* We can never have total larger than blen, so trim it now */
+		if (args.total > blen)
Quoted 8 lines

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_btalloc( · line 3484

Quoted 2 lines
fs/xfs/libxfs/xfs_bmap.c +2 -0
+			args.total = blen;
+

I don't think this is safe. The reason the original patch only updated certain callers is because those callers only used it for extra blocks that are already incorported into bma.minleft by the bmap layer itself. There are still other callers for which bma.total is specifically intended to be larger than the map size.

Quoted 5 lines

Afaik, yes, but still, total is basically used to attempt an allocation of data
+ metadata on the same AG if possible, reducing args.total to match blen, the 'worst' case would be to have an allocation of data + metadata on different ags, which, if total is larger than blen, it will fall into that behavior anyway.

Maybe..? There is no requirement that the additional blocks accounted by args.total be contiguous with the allocation for the mapping, so I don't see how you could reliably predict that.

Brian

Quoted 13 lines
Quoted 10 lines

Brian

Quoted 6 lines
fs/xfs/libxfs/xfs_bmap.c +0 -0
 		if (error)
 			return error;
 	} else if (ap->tp->t_flags & XFS_TRANS_LOWMODE) {
Signature · 1 line
2.20.1
Signature · 1 line
Carlos
#8 lore raw

Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible

Quoted 71 lines · Brian Foster
Quoted 7 lines · Carlos Maiolino
Quoted 6 lines · Brian Foster
Quoted 5 lines · Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

---

Confused.. what was wrong with the original bma.total patch that it needs to be replaced?

At this point in time, what you mean by the 'original' patch? :) Yours? Or Dave's?

The original patch I posted..

Quoted 10 lines

If you meant yours, I was just trying to find out a way to fix it without modifying the callers, nothing else than that.

If you meant regarding Dave's proposal, as he tagged his proposal as a /* Hack */, I was just looking for ways to change total, instead of cropping it to 0.

And giving the fact args.total > blen seems unreasonable, giving it will certainly tail here, I just thought it might be a reasonable way to change args.total value.

I think the code is flaky, but I'm not sure why that's unreasonable. The intent of args.total is to be larger than the mapping length.

Quoted 31 lines

By no means this patchset was meant to supersede yours or Dave's idea though, I was just looking for a different approach, if feasible.

Quoted 18 lines

I was assuming we'd replace the allocation retry
patch with the minlen alignment fixups and combine those with the bma.total patch to fix the problem. Hm?

Quoted 14 lines
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +3 -0
index 07aad70f3931..3aa0bf5cc7e3 100644
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
+		/* We can never have total larger than blen, so trim it now */
+		if (args.total > blen)
Quoted 8 lines

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_btalloc( · line 3484

Quoted 2 lines
fs/xfs/libxfs/xfs_bmap.c +2 -0
+			args.total = blen;
+

I don't think this is safe. The reason the original patch only updated certain callers is because those callers only used it for extra blocks that are already incorported into bma.minleft by the bmap layer itself. There are still other callers for which bma.total is specifically intended to be larger than the map size.

Quoted 5 lines

Afaik, yes, but still, total is basically used to attempt an allocation of data
+ metadata on the same AG if possible, reducing args.total to match blen, the 'worst' case would be to have an allocation of data + metadata on different ags, which, if total is larger than blen, it will fall into that behavior anyway.

Quoted 3 lines

Maybe..? There is no requirement that the additional blocks accounted by args.total be contiguous with the allocation for the mapping, so I don't see how you could reliably predict that.

I'm not predicting, {bma,ap}.total is basically:
data size requested + all metadata space it may need, so the original request can try to allocate everything as close as possible. And, if not possible, we give up on it by reducing .total.

One of the issues here, is that we reduce .total maybe 'too late', when we consider it already LOW SPACE mode, that's why Dave's fix does not 'fix' the original problem without zeroing .total.
My patch was just an attempt to use a different approach to round down .total to a reasonable size, without messing with the callers of xfs_bmap_alloc(). Anyway, again, I'm not saying my patch is the right approach. I was just trying a different one.

Quoted 16 lines

Brian

Quoted 13 lines
Quoted 10 lines

Brian

Quoted 6 lines
fs/xfs/libxfs/xfs_bmap.c +0 -0
 		if (error)
 			return error;
 	} else if (ap->tp->t_flags & XFS_TRANS_LOWMODE) {
Signature · 1 line
2.20.1
Signature · 1 line
Carlos
Signature · 1 line
Carlos
#9 lore raw

Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible

In reply to Carlos Maiolino
Quoted 15 lines · Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

---
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +0 -0
index 07aad70f3931..3aa0bf5cc7e3 100644

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_btalloc( · line 3481

Quoted 5 lines
fs/xfs/libxfs/xfs_bmap.c +2 -0
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
+		/* We can never have total larger than blen, so trim it now */

Yes we can. blen is typically the largest contiguous extent in the filesystem or AG in question. It is not typically the total free space in the AG, which only occurs when the AG is empty. i.e. in normal situations, we can allocate both blen and the rest of the metadata from the same AG as there is more than one free extent in the AG.

I think that for the purposes of a single > AG size allocation, the total needs to be clamped to the free space in the AG that is selected, not the length of the allocation we are trying....

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]
#10 lore raw

Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible

Quoted 20 lines · Dave Chinner
Quoted 19 lines · Carlos Maiolino

The original allocation request may have a total value way beyond possible limits.

Trim it down to the maximum possible if needed

---
 fs/xfs/libxfs/xfs_bmap.c | 5 +++++
 1 file changed, 5 insertions(+)
fs/xfs/libxfs/xfs_bmap.c +1 -0
index 07aad70f3931..3aa0bf5cc7e3 100644
@@ -3477,6 +3477,11 @@ xfs_bmap_btalloc(
 			error = xfs_bmap_btalloc_filestreams(ap, &args, &blen);
 		else
 			error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+
Quoted 9 lines

fs/xfs/libxfs/xfs_bmap.c xfs_bmap_btalloc( · line 3481

Quoted 1 line
fs/xfs/libxfs/xfs_bmap.c +1 -0
+		/* We can never have total larger than blen, so trim it now */

Yes we can. blen is typically the largest contiguous extent in the filesystem or AG in question. It is not typically the total free space in the AG, which only occurs when the AG is empty. i.e. in normal situations, we can allocate both blen and the rest of the metadata from the same AG as there is more than one free extent in the AG.

Right..

Quoted 4 lines

I think that for the purposes of a single > AG size allocation, the total needs to be clamped to the free space in the AG that is selected, not the length of the allocation we are trying....

As already noted, I do think args.total could use some work. But unless I'm missing something about the set of callers modified in the original patch, I'd rather not tweak a core bmap mechanism in service to callers that have no reason to use said mechanism in the first place.

And I know that such a change would affect legitimate args.total users too and so still might be appropriate, I just think that's something for a separate patch (even if in the same series)...

Brian

Quoted 6 lines

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]