A small improvement in the allocation algorithm
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
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
@@ -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
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 typeNEAR_BNOotypeSTART_BNOwasdel 0 wasfromfl 0 resv 0 datatype0x5firstblock0xffffffffffffffffminlen and maxlen are now separated by the alignment size, and allocation fails because args.total > free space in the AG.
Signed-off-by Dave Chinner <[email protected]>Signed-off-by Carlos Maiolino <[email protected]>---
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@@ -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
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 typeNEAR_BNOotypeSTART_BNOwasdel 0 wasfromfl 0 resv 0 datatype0x5firstblock0xffffffffffffffffminlen 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
Signed-off-by Dave Chinner <[email protected]>Signed-off-by Carlos Maiolino <[email protected]>---
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@@ -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
PATCH 2/2 xfs: Limit total allocation request to maximum possible
In reply to Carlos MaiolinoThe 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
@@ -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
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
Signed-off-by Carlos Maiolino <[email protected]>---
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
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
-0if (error)return error; }else if (ap->tp->t_flags &XFS_TRANS_LOWMODE ) {Signature · 1 line
2.20.1
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
Signed-off-by Carlos Maiolino <[email protected]>---
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@@ -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
-0if (error)return error; }else if (ap->tp->t_flags &XFS_TRANS_LOWMODE ) {Signature · 1 line
2.20.1
Signature · 1 line
Carlos
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
Signed-off-by Carlos Maiolino <[email protected]>---
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@@ -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
-0if (error)return error; }else if (ap->tp->t_flags &XFS_TRANS_LOWMODE ) {Signature · 1 line
2.20.1Signature · 1 line
Carlos
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
Signed-off-by Carlos Maiolino <[email protected]>---
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@@ -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
-0if (error)return error; }else if (ap->tp->t_flags &XFS_TRANS_LOWMODE ) {Signature · 1 line
2.20.1Signature · 1 line
Carlos
Signature · 1 line
Carlos
Re: [PATCH 2/2] xfs: Limit total allocation request to maximum possible
In reply to Carlos MaiolinoQuoted 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
Signed-off-by Carlos Maiolino <[email protected]>--- fs/xfs/libxfs/xfs_bmap.c | 5 +++++ 1 file changed, 5 insertions(+)fs/xfs/libxfs/xfs_bmap.c +0
-0
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]
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
Signed-off-by Carlos Maiolino <[email protected]>--- fs/xfs/libxfs/xfs_bmap.c | 5 +++++ 1 file changed, 5 insertions(+)fs/xfs/libxfs/xfs_bmap.c +1
-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); +
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]