diff mbox series

[RFC,3/4] xfs: crude chunk allocation retry mechanism

Message ID 20220217172518.3842951-4-bfoster@redhat.com (mailing list archive)
State New
Headers show
Series xfs: track and skip realloc of busy inodes | expand

Commit Message

Brian Foster Feb. 17, 2022, 5:25 p.m. UTC
The free inode btree currently tracks all inode chunk records with
at least one free inode. This simplifies the chunk and allocation
selection algorithms as free inode availability can be guaranteed
after a few simple checks. This is no longer the case with busy
inode avoidance, however, because busy inode state is tracked in the
radix tree independent from physical allocation status.

A busy inode avoidance algorithm relies on the ability to fall back
to an inode chunk allocation one way or another in the event that
all current free inodes are busy. Hack in a crude allocation
fallback mechanism for experimental purposes. If the inode selection
algorithm is unable to locate a usable inode, allow it to return
-EAGAIN to perform another physical chunk allocation in the AG and
retry the inode allocation.

The current prototype can perform this allocation and retry sequence
repeatedly because a newly allocated chunk may still be covered by
busy in-core inodes in the radix tree (if it were recently freed,
for example). This is inefficient and temporary. It will be properly
mitigated by background chunk removal. This defers freeing of inode
chunk blocks from the free of the last used inode in the chunk to a
background task that only frees chunks once completely idle, thereby
providing a guarantee that a new chunk allocation always adds
non-busy inodes to the AG.

Not-Signed-off-by: Brian Foster <bfoster@redhat.com>
---
 fs/xfs/libxfs/xfs_ialloc.c | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

Comments

Dave Chinner Feb. 17, 2022, 11:20 p.m. UTC | #1
On Thu, Feb 17, 2022 at 12:25:17PM -0500, Brian Foster wrote:
> The free inode btree currently tracks all inode chunk records with
> at least one free inode. This simplifies the chunk and allocation
> selection algorithms as free inode availability can be guaranteed
> after a few simple checks. This is no longer the case with busy
> inode avoidance, however, because busy inode state is tracked in the
> radix tree independent from physical allocation status.
> 
> A busy inode avoidance algorithm relies on the ability to fall back
> to an inode chunk allocation one way or another in the event that
> all current free inodes are busy. Hack in a crude allocation
> fallback mechanism for experimental purposes. If the inode selection
> algorithm is unable to locate a usable inode, allow it to return
> -EAGAIN to perform another physical chunk allocation in the AG and
> retry the inode allocation.
> 
> The current prototype can perform this allocation and retry sequence
> repeatedly because a newly allocated chunk may still be covered by
> busy in-core inodes in the radix tree (if it were recently freed,
> for example). This is inefficient and temporary. It will be properly
> mitigated by background chunk removal. This defers freeing of inode
> chunk blocks from the free of the last used inode in the chunk to a
> background task that only frees chunks once completely idle, thereby
> providing a guarantee that a new chunk allocation always adds
> non-busy inodes to the AG.

I think you can get rid of this simply by checking the radix tree
tags for busy inodes at the location of the new inode chunk before
we do the cluster allocation. If there are busy inodes in the range
of the chunk (pure gang tag lookup, don't need to dereference any of
the inodes), just skip to the next chunk offset and try that. Hence
we only ever end up allocating a chunk that we know there are no
busy inodes in and this retry mechanism is unnecessary.

Cheers,

Dave.
Brian Foster Feb. 18, 2022, 2:21 p.m. UTC | #2
On Fri, Feb 18, 2022 at 10:20:33AM +1100, Dave Chinner wrote:
> On Thu, Feb 17, 2022 at 12:25:17PM -0500, Brian Foster wrote:
> > The free inode btree currently tracks all inode chunk records with
> > at least one free inode. This simplifies the chunk and allocation
> > selection algorithms as free inode availability can be guaranteed
> > after a few simple checks. This is no longer the case with busy
> > inode avoidance, however, because busy inode state is tracked in the
> > radix tree independent from physical allocation status.
> > 
> > A busy inode avoidance algorithm relies on the ability to fall back
> > to an inode chunk allocation one way or another in the event that
> > all current free inodes are busy. Hack in a crude allocation
> > fallback mechanism for experimental purposes. If the inode selection
> > algorithm is unable to locate a usable inode, allow it to return
> > -EAGAIN to perform another physical chunk allocation in the AG and
> > retry the inode allocation.
> > 
> > The current prototype can perform this allocation and retry sequence
> > repeatedly because a newly allocated chunk may still be covered by
> > busy in-core inodes in the radix tree (if it were recently freed,
> > for example). This is inefficient and temporary. It will be properly
> > mitigated by background chunk removal. This defers freeing of inode
> > chunk blocks from the free of the last used inode in the chunk to a
> > background task that only frees chunks once completely idle, thereby
> > providing a guarantee that a new chunk allocation always adds
> > non-busy inodes to the AG.
> 
> I think you can get rid of this simply by checking the radix tree
> tags for busy inodes at the location of the new inode chunk before
> we do the cluster allocation. If there are busy inodes in the range
> of the chunk (pure gang tag lookup, don't need to dereference any of
> the inodes), just skip to the next chunk offset and try that. Hence
> we only ever end up allocating a chunk that we know there are no
> busy inodes in and this retry mechanism is unnecessary.
> 

The retry mechanism exists in this series due to the factoring of the
inode allocation code moreso than whether the fallback is guaranteed to
provide a fully non-busy chunk or not. As the prototype is written, the
inode scan still needs to fall back at least once even with such a
guarantee (see my reply on the previous patch around cleaning up that
particular wart).

With regard to checking busy inode state, that is pretty much what I was
referring to by filtering or hinting the block allocation when we
discussed this on IRC. I'm explicitly trying to avoid that because for
one it unnecessarily spreads concern about busy inodes across layers. On
top of that, it assumes that there will always be some usable physical
block range available without busy inodes, which is not the case. That
means we now need to consider the fact that chunk allocation might fail
for reasons other than -ENOSPC and factor that into the inode allocation
algorithm. IOW, ISTM this just unnecessarily complicates things for
minimal benefit.

The point of background freeing inode chunks was that it makes this
problem go away because then we ensure that inode chunks aren't freed
until all associated busy inodes are cleared, and so we preserve the
historical behavior that an inode chunk allocation guarantees immediate
ability to allocate an inode. I thought we agreed in the previous
discussion that this was the right approach since it seemed to be in the
long term direction for XFS anyways.. hm?

Brian

> Cheers,
> 
> Dave.
> -- 
> Dave Chinner
> david@fromorbit.com
>
Dave Chinner Feb. 18, 2022, 10:54 p.m. UTC | #3
On Fri, Feb 18, 2022 at 09:21:40AM -0500, Brian Foster wrote:
> On Fri, Feb 18, 2022 at 10:20:33AM +1100, Dave Chinner wrote:
> > On Thu, Feb 17, 2022 at 12:25:17PM -0500, Brian Foster wrote:
> > > The free inode btree currently tracks all inode chunk records with
> > > at least one free inode. This simplifies the chunk and allocation
> > > selection algorithms as free inode availability can be guaranteed
> > > after a few simple checks. This is no longer the case with busy
> > > inode avoidance, however, because busy inode state is tracked in the
> > > radix tree independent from physical allocation status.
> > > 
> > > A busy inode avoidance algorithm relies on the ability to fall back
> > > to an inode chunk allocation one way or another in the event that
> > > all current free inodes are busy. Hack in a crude allocation
> > > fallback mechanism for experimental purposes. If the inode selection
> > > algorithm is unable to locate a usable inode, allow it to return
> > > -EAGAIN to perform another physical chunk allocation in the AG and
> > > retry the inode allocation.
> > > 
> > > The current prototype can perform this allocation and retry sequence
> > > repeatedly because a newly allocated chunk may still be covered by
> > > busy in-core inodes in the radix tree (if it were recently freed,
> > > for example). This is inefficient and temporary. It will be properly
> > > mitigated by background chunk removal. This defers freeing of inode
> > > chunk blocks from the free of the last used inode in the chunk to a
> > > background task that only frees chunks once completely idle, thereby
> > > providing a guarantee that a new chunk allocation always adds
> > > non-busy inodes to the AG.
> > 
> > I think you can get rid of this simply by checking the radix tree
> > tags for busy inodes at the location of the new inode chunk before
> > we do the cluster allocation. If there are busy inodes in the range
> > of the chunk (pure gang tag lookup, don't need to dereference any of
> > the inodes), just skip to the next chunk offset and try that. Hence
> > we only ever end up allocating a chunk that we know there are no
> > busy inodes in and this retry mechanism is unnecessary.
> > 
> 
> The retry mechanism exists in this series due to the factoring of the
> inode allocation code moreso than whether the fallback is guaranteed to
> provide a fully non-busy chunk or not. As the prototype is written, the
> inode scan still needs to fall back at least once even with such a
> guarantee (see my reply on the previous patch around cleaning up that
> particular wart).
> 
> With regard to checking busy inode state, that is pretty much what I was
> referring to by filtering or hinting the block allocation when we
> discussed this on IRC. I'm explicitly trying to avoid that because for
> one it unnecessarily spreads concern about busy inodes across layers. On
> top of that, it assumes that there will always be some usable physical
> block range available without busy inodes, which is not the case. That
> means we now need to consider the fact that chunk allocation might fail
> for reasons other than -ENOSPC and factor that into the inode allocation
> algorithm. IOW, ISTM this just unnecessarily complicates things for
> minimal benefit.

For the moment, if inode allocation fails because we have busy
inodes after chunk allocation has already been done, then we are
hitting a corner case that isn't typical fast path operation. I
think that we should not complicate things by trying to optimise
this case unnecessarily.

I'd just expedite reclaim using synchronize_rcu() and re-run the
finobt scan as it will always succeed the second time because we
haven't dropped the AGI log and all freed inodes have now passed
through a grace period. Indeed, we need this expedited reclaim path
anyway because if we fail to allocate a new chunk and there are busy
inodes, we need to wait for busy inodes to become unbusy to avoid
premature ENOSPC while there are still avaialbe free inodes.

In the case of the updated inode lifecycle stuff I'm working on, a
log force will replace the synchronise_rcu() call because the inodes
will be XFS_ISTALE and journal IO completion of the cluster buffers
will trigger the inodes to be reclaimed immediately as writeback is
elided for XFS_ISTALE inodes. We may need an AIL push in other
cases, but I'll cross that river when I get to it.

> The point of background freeing inode chunks was that it makes this
> problem go away because then we ensure that inode chunks aren't freed
> until all associated busy inodes are cleared, and so we preserve the
> historical behavior that an inode chunk allocation guarantees immediate
> ability to allocate an inode. I thought we agreed in the previous
> discussion that this was the right approach since it seemed to be in the
> long term direction for XFS anyways.. hm?

Long term, yes, but we need something that works effectively and
efficiently now, with minimal additional overhead, because we're
going to have to live with this code in the allocation fast path for
some time yet.

Really, I want foreground inode allocation to know nothing about
inode chunk allocation. If there are no inodes available for
allocation, it kicks background inode chunk management and sleeps
waiting for to be given an allocated inode it can use. It shouldn't
even have to know about busy inodes - just work from an in-memory
per-ag free list of inode numbers that can be immediately allocated.

In this situation, inodes that have been recently unlinked don't
show up on that list until they can be reallocated safely. This
is all managed asynchronously in the background by the inodegc state
machine (what I'm currently working on) and when the inode is
finally reclaimed it is moved into the free list and allowed to be
reallocated.

IOWs, the long term direction is to make sure that the
foreground inode allocator doesn't even know about the existence of
busy inodes and it gets faster and simpler as we push all the mess
into the background that runs all the slow path allocation and
freeing algorithms.

Cheers,

Dave.
Brian Foster Feb. 20, 2022, 6:48 p.m. UTC | #4
On Sat, Feb 19, 2022 at 09:54:40AM +1100, Dave Chinner wrote:
> On Fri, Feb 18, 2022 at 09:21:40AM -0500, Brian Foster wrote:
> > On Fri, Feb 18, 2022 at 10:20:33AM +1100, Dave Chinner wrote:
> > > On Thu, Feb 17, 2022 at 12:25:17PM -0500, Brian Foster wrote:
> > > > The free inode btree currently tracks all inode chunk records with
> > > > at least one free inode. This simplifies the chunk and allocation
> > > > selection algorithms as free inode availability can be guaranteed
> > > > after a few simple checks. This is no longer the case with busy
> > > > inode avoidance, however, because busy inode state is tracked in the
> > > > radix tree independent from physical allocation status.
> > > > 
> > > > A busy inode avoidance algorithm relies on the ability to fall back
> > > > to an inode chunk allocation one way or another in the event that
> > > > all current free inodes are busy. Hack in a crude allocation
> > > > fallback mechanism for experimental purposes. If the inode selection
> > > > algorithm is unable to locate a usable inode, allow it to return
> > > > -EAGAIN to perform another physical chunk allocation in the AG and
> > > > retry the inode allocation.
> > > > 
> > > > The current prototype can perform this allocation and retry sequence
> > > > repeatedly because a newly allocated chunk may still be covered by
> > > > busy in-core inodes in the radix tree (if it were recently freed,
> > > > for example). This is inefficient and temporary. It will be properly
> > > > mitigated by background chunk removal. This defers freeing of inode
> > > > chunk blocks from the free of the last used inode in the chunk to a
> > > > background task that only frees chunks once completely idle, thereby
> > > > providing a guarantee that a new chunk allocation always adds
> > > > non-busy inodes to the AG.
> > > 
> > > I think you can get rid of this simply by checking the radix tree
> > > tags for busy inodes at the location of the new inode chunk before
> > > we do the cluster allocation. If there are busy inodes in the range
> > > of the chunk (pure gang tag lookup, don't need to dereference any of
> > > the inodes), just skip to the next chunk offset and try that. Hence
> > > we only ever end up allocating a chunk that we know there are no
> > > busy inodes in and this retry mechanism is unnecessary.
> > > 
> > 
> > The retry mechanism exists in this series due to the factoring of the
> > inode allocation code moreso than whether the fallback is guaranteed to
> > provide a fully non-busy chunk or not. As the prototype is written, the
> > inode scan still needs to fall back at least once even with such a
> > guarantee (see my reply on the previous patch around cleaning up that
> > particular wart).
> > 
> > With regard to checking busy inode state, that is pretty much what I was
> > referring to by filtering or hinting the block allocation when we
> > discussed this on IRC. I'm explicitly trying to avoid that because for
> > one it unnecessarily spreads concern about busy inodes across layers. On
> > top of that, it assumes that there will always be some usable physical
> > block range available without busy inodes, which is not the case. That
> > means we now need to consider the fact that chunk allocation might fail
> > for reasons other than -ENOSPC and factor that into the inode allocation
> > algorithm. IOW, ISTM this just unnecessarily complicates things for
> > minimal benefit.
> 
> For the moment, if inode allocation fails because we have busy
> inodes after chunk allocation has already been done, then we are
> hitting a corner case that isn't typical fast path operation. I
> think that we should not complicate things by trying to optimise
> this case unnecessarily.
> 

Not really, it's one of the first problems I ran into with the chunk
allocation fallback in place.

> I'd just expedite reclaim using synchronize_rcu() and re-run the
> finobt scan as it will always succeed the second time because we
> haven't dropped the AGI log and all freed inodes have now passed
> through a grace period. Indeed, we need this expedited reclaim path
> anyway because if we fail to allocate a new chunk and there are busy
> inodes, we need to wait for busy inodes to become unbusy to avoid
> premature ENOSPC while there are still avaialbe free inodes.
> 

My experiments to this point suggest that would be extremely slow, to
the point where there's not much value to anything beyond patch 1. The
finobt is going to be relatively small with any sort of mixed alloc/free
workload as records cycle in and out, so a "sync per batch" is
effectively the behavior I already see with patch 1 alone and it's a
performance killer (with non-expedited grace periods, at least). We do
need the rcu sync -ENOSPC fallback as you say, but IMO it should be a
last resort.

> In the case of the updated inode lifecycle stuff I'm working on, a
> log force will replace the synchronise_rcu() call because the inodes
> will be XFS_ISTALE and journal IO completion of the cluster buffers
> will trigger the inodes to be reclaimed immediately as writeback is
> elided for XFS_ISTALE inodes. We may need an AIL push in other
> cases, but I'll cross that river when I get to it.
> 

Ok.

> > The point of background freeing inode chunks was that it makes this
> > problem go away because then we ensure that inode chunks aren't freed
> > until all associated busy inodes are cleared, and so we preserve the
> > historical behavior that an inode chunk allocation guarantees immediate
> > ability to allocate an inode. I thought we agreed in the previous
> > discussion that this was the right approach since it seemed to be in the
> > long term direction for XFS anyways.. hm?
> 
> Long term, yes, but we need something that works effectively and
> efficiently now, with minimal additional overhead, because we're
> going to have to live with this code in the allocation fast path for
> some time yet.
> 

Right, but I thought this is why we were only going to do the background
freeing part of the whole "background inode management" thing?

Short of that, I'm not aware of a really great option atm. IMO, pushing
explicit busy inode state/checking down into the block allocator is kind
of a gross layering violation. The approach this series currently uses
is simple and effective, but it's an unbound retry mechanism that just
continues to allocate chunks until we get one we can use, which is too
crude for production.

Perhaps a simple enough short term option is to use the existing block
alloc min/max range mechanisms (as mentioned on IRC). For example:

- Use the existing min/max_agbno allocation arg input values to attempt
  one or two chunk allocs outside of the known range of busy inodes for
  the AG (i.e., allocate blocks higher than the max busy agino or lower
  than the min busy agino).
- If success, then we know we've got a chunk w/o busy inodes.
- If failure, fall back to the existing chunk alloc calls, take whatever
  we get and retry the finobt scan (perhaps more aggressively checking
  each record) hoping we got a usable new record.
- If that still fails, then fall back to synchronize_rcu() as a last
  resort and grab one of the previously busy inodes.

I couldn't say for sure if that would be effective enough without
playing with it a bit, but that would sort of emulate an algorithm that
filtered chunk block allocations with at least one busy inode without
having to modify block allocation code. If it avoids an RCU sync in the
majority of cases it might be effective enough as a stopgap until
background freeing exists. Thoughts?

> Really, I want foreground inode allocation to know nothing about
> inode chunk allocation. If there are no inodes available for
> allocation, it kicks background inode chunk management and sleeps
> waiting for to be given an allocated inode it can use. It shouldn't
> even have to know about busy inodes - just work from an in-memory
> per-ag free list of inode numbers that can be immediately allocated.
> 
> In this situation, inodes that have been recently unlinked don't
> show up on that list until they can be reallocated safely. This
> is all managed asynchronously in the background by the inodegc state
> machine (what I'm currently working on) and when the inode is
> finally reclaimed it is moved into the free list and allowed to be
> reallocated.
> 

I think that makes a lot of sense. That's quite similar to another
experiment I was playing with that essentially populated a capped size
pool of background inactivated inodes that the allocation side could
pull directly from (i.e., so allocation actually becomes a radix tree
lookup instead of a filtered btree scan), but so far I was kind of
fighting with the existing mechanisms, trying not to peturb sustained
remove performance, etc., and hadn't been able to produce a performance
benefit yet. Perhaps this will work out better with the bigger picture
changes to inode lifecycle and background inode management in place..

Brian

> IOWs, the long term direction is to make sure that the
> foreground inode allocator doesn't even know about the existence of
> busy inodes and it gets faster and simpler as we push all the mess
> into the background that runs all the slow path allocation and
> freeing algorithms.
> 
> Cheers,
> 
> Dave.
> -- 
> Dave Chinner
> david@fromorbit.com
>
Dave Chinner Feb. 23, 2022, 7 a.m. UTC | #5
On Sun, Feb 20, 2022 at 01:48:10PM -0500, Brian Foster wrote:
> On Sat, Feb 19, 2022 at 09:54:40AM +1100, Dave Chinner wrote:
> > On Fri, Feb 18, 2022 at 09:21:40AM -0500, Brian Foster wrote:
> > > The point of background freeing inode chunks was that it makes this
> > > problem go away because then we ensure that inode chunks aren't freed
> > > until all associated busy inodes are cleared, and so we preserve the
> > > historical behavior that an inode chunk allocation guarantees immediate
> > > ability to allocate an inode. I thought we agreed in the previous
> > > discussion that this was the right approach since it seemed to be in the
> > > long term direction for XFS anyways.. hm?
> > 
> > Long term, yes, but we need something that works effectively and
> > efficiently now, with minimal additional overhead, because we're
> > going to have to live with this code in the allocation fast path for
> > some time yet.
> > 
> 
> Right, but I thought this is why we were only going to do the background
> freeing part of the whole "background inode management" thing?
> 
> Short of that, I'm not aware of a really great option atm. IMO, pushing
> explicit busy inode state/checking down into the block allocator is kind
> of a gross layering violation. The approach this series currently uses
> is simple and effective, but it's an unbound retry mechanism that just
> continues to allocate chunks until we get one we can use, which is too
> crude for production.

*nod*

Right, that's why I want to get this whole mechanism completely
detached from the VFS inode RCU life cycle rules and instead
synchronised by internal IO operations such as log forces.

The code I currently have is based on your changes, just without the
fallback chunk allocation. I'm not really even scanning the irecs;
I just look at the number of free inodes and count the number of
busy inodes over the range of the record. If they aren't the same,
we've got inodes in that record we can allocate from. I only do a
free inode-by-free inode busy check once the irec we are going to
allocate from has been selected.

Essentially, I'm just scanning records in the finobt to find the
first with a non-busy inode. If we fall off the end of the finobt,
it issues a log force and kicks the AIL and then retries the
allocation from the finobt. There isn't any attempt to allocate new
inode chunks in the case, but it may end up being necessary and can
be done without falling back to the outer loops.

i.e. as long as we track whether we've allocated a new inode chunk
or not, we can bound the finobt search to a single retry. If we
allocated a new chunk before entering the finobt search, then all we
need is a log force because the busy inodes, by definition, are
XFS_ISTALE at this point and waiting for a CIL push before they can
be reclaimed. At this point an retry of the finobt scan will find
those inodes that were busy now available for allocation.

If we haven't allocated a new chunk, then we can do so immediately
and retry the allocation. If we still find them all busy, we force
the log...

IOWs, once we isolate this busy inode tracking from the VFS inode
RCU requirements, we can bound the allocation behaviour because
chunk allocation and log forces provide us with a guarantee that the
newly allocated inode chunks contain inodes that can be immediately
reallocated without having to care about where the new inode chunk
is located....

> Perhaps a simple enough short term option is to use the existing block
> alloc min/max range mechanisms (as mentioned on IRC). For example:
> 
> - Use the existing min/max_agbno allocation arg input values to attempt
>   one or two chunk allocs outside of the known range of busy inodes for
>   the AG (i.e., allocate blocks higher than the max busy agino or lower
>   than the min busy agino).
> - If success, then we know we've got a chunk w/o busy inodes.
> - If failure, fall back to the existing chunk alloc calls, take whatever
>   we get and retry the finobt scan (perhaps more aggressively checking
>   each record) hoping we got a usable new record.
> - If that still fails, then fall back to synchronize_rcu() as a last
>   resort and grab one of the previously busy inodes.
> 
> I couldn't say for sure if that would be effective enough without
> playing with it a bit, but that would sort of emulate an algorithm that
> filtered chunk block allocations with at least one busy inode without
> having to modify block allocation code. If it avoids an RCU sync in the
> majority of cases it might be effective enough as a stopgap until
> background freeing exists. Thoughts?

It might work, but I'm not a fan of how many hoops we are considering
jumping through to avoid getting tangled up in the RCU requirements
for VFS inode life cycles. I'd much prefer just being able to say
"all inodes busy, log force, try again" like we do with busy extent
limited block allocation...

That said, the complexity gets moved elsewhere (the VFS inode
lifecycle management) rather than into the inode allocator, but I
think that's a valid trade-off because the RCU requirements for
inode reallocation come from the VFS inode lifecycle constraints.

> > Really, I want foreground inode allocation to know nothing about
> > inode chunk allocation. If there are no inodes available for
> > allocation, it kicks background inode chunk management and sleeps
> > waiting for to be given an allocated inode it can use. It shouldn't
> > even have to know about busy inodes - just work from an in-memory
> > per-ag free list of inode numbers that can be immediately allocated.
> > 
> > In this situation, inodes that have been recently unlinked don't
> > show up on that list until they can be reallocated safely. This
> > is all managed asynchronously in the background by the inodegc state
> > machine (what I'm currently working on) and when the inode is
> > finally reclaimed it is moved into the free list and allowed to be
> > reallocated.
> > 
> 
> I think that makes a lot of sense. That's quite similar to another
> experiment I was playing with that essentially populated a capped size
> pool of background inactivated inodes that the allocation side could
> pull directly from (i.e., so allocation actually becomes a radix tree
> lookup instead of a filtered btree scan), but so far I was kind of
> fighting with the existing mechanisms, trying not to peturb sustained
> remove performance, etc., and hadn't been able to produce a performance
> benefit yet. Perhaps this will work out better with the bigger picture
> changes to inode lifecycle and background inode management in place..

*nod*

The "don't have a perf impact" side of thigns is generally why I
test all my new code with fsmark and other scalability tests before
I go anywhere near fstests. If it doesn't perform, it's not worth
trying to make work correctly...

Cheers,

Dave.
Brian Foster Feb. 28, 2022, 9:45 p.m. UTC | #6
On Wed, Feb 23, 2022 at 06:00:58PM +1100, Dave Chinner wrote:
> On Sun, Feb 20, 2022 at 01:48:10PM -0500, Brian Foster wrote:
> > On Sat, Feb 19, 2022 at 09:54:40AM +1100, Dave Chinner wrote:
> > > On Fri, Feb 18, 2022 at 09:21:40AM -0500, Brian Foster wrote:
> > > > The point of background freeing inode chunks was that it makes this
> > > > problem go away because then we ensure that inode chunks aren't freed
> > > > until all associated busy inodes are cleared, and so we preserve the
> > > > historical behavior that an inode chunk allocation guarantees immediate
> > > > ability to allocate an inode. I thought we agreed in the previous
> > > > discussion that this was the right approach since it seemed to be in the
> > > > long term direction for XFS anyways.. hm?
> > > 
> > > Long term, yes, but we need something that works effectively and
> > > efficiently now, with minimal additional overhead, because we're
> > > going to have to live with this code in the allocation fast path for
> > > some time yet.
> > > 
> > 
> > Right, but I thought this is why we were only going to do the background
> > freeing part of the whole "background inode management" thing?
> > 
> > Short of that, I'm not aware of a really great option atm. IMO, pushing
> > explicit busy inode state/checking down into the block allocator is kind
> > of a gross layering violation. The approach this series currently uses
> > is simple and effective, but it's an unbound retry mechanism that just
> > continues to allocate chunks until we get one we can use, which is too
> > crude for production.
> 
> *nod*
> 
> Right, that's why I want to get this whole mechanism completely
> detached from the VFS inode RCU life cycle rules and instead
> synchronised by internal IO operations such as log forces.
> 
> The code I currently have is based on your changes, just without the
> fallback chunk allocation. I'm not really even scanning the irecs;
> I just look at the number of free inodes and count the number of
> busy inodes over the range of the record. If they aren't the same,
> we've got inodes in that record we can allocate from. I only do a
> free inode-by-free inode busy check once the irec we are going to
> allocate from has been selected.
> 
> Essentially, I'm just scanning records in the finobt to find the
> first with a non-busy inode. If we fall off the end of the finobt,
> it issues a log force and kicks the AIL and then retries the
> allocation from the finobt. There isn't any attempt to allocate new
> inode chunks in the case, but it may end up being necessary and can
> be done without falling back to the outer loops.
> 

Sure, that was just done for expediency to test the approach. That said,
as a first step I wouldn't be opposed to something that similarly falls
back to the outer loop so long as it incorporates a check like described
below to restrict the retry attempt(s). The logic is simple enough that
more extensive cleanups could come separately..

> i.e. as long as we track whether we've allocated a new inode chunk
> or not, we can bound the finobt search to a single retry. If we
> allocated a new chunk before entering the finobt search, then all we
> need is a log force because the busy inodes, by definition, are
> XFS_ISTALE at this point and waiting for a CIL push before they can
> be reclaimed. At this point an retry of the finobt scan will find
> those inodes that were busy now available for allocation.
> 

Remind me what aspect of the prospective VFS changes prevents inode
allocation from seeing a free inode with not-yet-elapsed RCU grace
period..? Will this delay freeing (or evicting) the inode until a grace
period elapses from when the last reference was dropped?

> If we haven't allocated a new chunk, then we can do so immediately
> and retry the allocation. If we still find them all busy, we force
> the log...
> 
> IOWs, once we isolate this busy inode tracking from the VFS inode
> RCU requirements, we can bound the allocation behaviour because
> chunk allocation and log forces provide us with a guarantee that the
> newly allocated inode chunks contain inodes that can be immediately
> reallocated without having to care about where the new inode chunk
> is located....
> 
> > Perhaps a simple enough short term option is to use the existing block
> > alloc min/max range mechanisms (as mentioned on IRC). For example:
> > 
> > - Use the existing min/max_agbno allocation arg input values to attempt
> >   one or two chunk allocs outside of the known range of busy inodes for
> >   the AG (i.e., allocate blocks higher than the max busy agino or lower
> >   than the min busy agino).
> > - If success, then we know we've got a chunk w/o busy inodes.
> > - If failure, fall back to the existing chunk alloc calls, take whatever
> >   we get and retry the finobt scan (perhaps more aggressively checking
> >   each record) hoping we got a usable new record.
> > - If that still fails, then fall back to synchronize_rcu() as a last
> >   resort and grab one of the previously busy inodes.
> > 
> > I couldn't say for sure if that would be effective enough without
> > playing with it a bit, but that would sort of emulate an algorithm that
> > filtered chunk block allocations with at least one busy inode without
> > having to modify block allocation code. If it avoids an RCU sync in the
> > majority of cases it might be effective enough as a stopgap until
> > background freeing exists. Thoughts?
> 
> It might work, but I'm not a fan of how many hoops we are considering
> jumping through to avoid getting tangled up in the RCU requirements
> for VFS inode life cycles. I'd much prefer just being able to say
> "all inodes busy, log force, try again" like we do with busy extent
> limited block allocation...
> 

Well presumably that works fine for your implementation of busy inodes,
but not so much for the variant intended to work around the RCU inode
reuse problem. ISTM this all just depends on the goals and plan here,
and I'm not seeing clear enough reasoning to grok what that is. A
summary of the options discussed so far:

- deferred inode freeing - ideal but too involved, want something sooner
  and more simple
- hinted non-busy chunk allocation - simple but jumping through too many
  RCU requirement hoops
- sync RCU and retry - most analogous to longer term busy inode
  allocation handling (i.e. just replace rcu sync w/ log force and
  retry), but RCU sync is too performance costly as a direct fallback

ISTM the options here range from simple and slow, to moderately simple
and effective (TBD), to complex and ideal. So what is the goal for this
series? My understanding to this point is that VFS changes are a ways
out, so the first step was busy inodes == inodes with pending grace
periods and a rework of the busy inode definition comes later with the
associated VFS changes. That essentially means this series gets fixed up
and posted as a mergeable component in the meantime, albeit with a
"general direction" that is compatible with longer term changes.

However, every RCU requirement/characteristic that this series has to
deal with is never going to be 100% perfectly aligned with the longer
term busy inode requirements because the implementations/definitions
will differ, particularly if the RCU handling is pushed up into the VFS.
So if we're concerned about that, the alternative approach is to skip
incrementally addressing the RCU inode reuse problem and just fold
whatever bits of useful logic from here into your inode lifecycle work
as needed and drop this as a mergeable component.

Brian

> That said, the complexity gets moved elsewhere (the VFS inode
> lifecycle management) rather than into the inode allocator, but I
> think that's a valid trade-off because the RCU requirements for
> inode reallocation come from the VFS inode lifecycle constraints.
> 
> > > Really, I want foreground inode allocation to know nothing about
> > > inode chunk allocation. If there are no inodes available for
> > > allocation, it kicks background inode chunk management and sleeps
> > > waiting for to be given an allocated inode it can use. It shouldn't
> > > even have to know about busy inodes - just work from an in-memory
> > > per-ag free list of inode numbers that can be immediately allocated.
> > > 
> > > In this situation, inodes that have been recently unlinked don't
> > > show up on that list until they can be reallocated safely. This
> > > is all managed asynchronously in the background by the inodegc state
> > > machine (what I'm currently working on) and when the inode is
> > > finally reclaimed it is moved into the free list and allowed to be
> > > reallocated.
> > > 
> > 
> > I think that makes a lot of sense. That's quite similar to another
> > experiment I was playing with that essentially populated a capped size
> > pool of background inactivated inodes that the allocation side could
> > pull directly from (i.e., so allocation actually becomes a radix tree
> > lookup instead of a filtered btree scan), but so far I was kind of
> > fighting with the existing mechanisms, trying not to peturb sustained
> > remove performance, etc., and hadn't been able to produce a performance
> > benefit yet. Perhaps this will work out better with the bigger picture
> > changes to inode lifecycle and background inode management in place..
> 
> *nod*
> 
> The "don't have a perf impact" side of thigns is generally why I
> test all my new code with fsmark and other scalability tests before
> I go anywhere near fstests. If it doesn't perform, it's not worth
> trying to make work correctly...
> 
> Cheers,
> 
> Dave.
> -- 
> Dave Chinner
> david@fromorbit.com
>
Dave Chinner Feb. 28, 2022, 10:55 p.m. UTC | #7
On Mon, Feb 28, 2022 at 04:45:49PM -0500, Brian Foster wrote:
> On Wed, Feb 23, 2022 at 06:00:58PM +1100, Dave Chinner wrote:
> > i.e. as long as we track whether we've allocated a new inode chunk
> > or not, we can bound the finobt search to a single retry. If we
> > allocated a new chunk before entering the finobt search, then all we
> > need is a log force because the busy inodes, by definition, are
> > XFS_ISTALE at this point and waiting for a CIL push before they can
> > be reclaimed. At this point an retry of the finobt scan will find
> > those inodes that were busy now available for allocation.
> 
> Remind me what aspect of the prospective VFS changes prevents inode
> allocation from seeing a free inode with not-yet-elapsed RCU grace
> period..? Will this delay freeing (or evicting) the inode until a grace
> period elapses from when the last reference was dropped?

It will delay it until the inode has been reclaimed, in which case
reallocating it will result in a new struct xfs_inode being
allocated from slab, and we're all good. Any lookup that finds the
old inode will see either I_WILL_FREE, I_FREEING, I_CLEAR,
XFS_NEED_INACTIVE, XFS_IRECLAIM or ip->i_ino == 0 depending on what
point the lookup occurs. Hence the lookup will be unable to take a
new reference to the unlinked inode, and the lookup retry should
then get the newly allocated xfs_inode once it has been inserted
into the radix tree...

IOWs, it gets rid of recycling altogether, and that's how we avoid
the RCU grace period issues with recycled inodes.

> > > Perhaps a simple enough short term option is to use the existing block
> > > alloc min/max range mechanisms (as mentioned on IRC). For example:
> > > 
> > > - Use the existing min/max_agbno allocation arg input values to attempt
> > >   one or two chunk allocs outside of the known range of busy inodes for
> > >   the AG (i.e., allocate blocks higher than the max busy agino or lower
> > >   than the min busy agino).
> > > - If success, then we know we've got a chunk w/o busy inodes.
> > > - If failure, fall back to the existing chunk alloc calls, take whatever
> > >   we get and retry the finobt scan (perhaps more aggressively checking
> > >   each record) hoping we got a usable new record.
> > > - If that still fails, then fall back to synchronize_rcu() as a last
> > >   resort and grab one of the previously busy inodes.
> > > 
> > > I couldn't say for sure if that would be effective enough without
> > > playing with it a bit, but that would sort of emulate an algorithm that
> > > filtered chunk block allocations with at least one busy inode without
> > > having to modify block allocation code. If it avoids an RCU sync in the
> > > majority of cases it might be effective enough as a stopgap until
> > > background freeing exists. Thoughts?
> > 
> > It might work, but I'm not a fan of how many hoops we are considering
> > jumping through to avoid getting tangled up in the RCU requirements
> > for VFS inode life cycles. I'd much prefer just being able to say
> > "all inodes busy, log force, try again" like we do with busy extent
> > limited block allocation...
> > 
> 
> Well presumably that works fine for your implementation of busy inodes,
> but not so much for the variant intended to work around the RCU inode
> reuse problem. ISTM this all just depends on the goals and plan here,
> and I'm not seeing clear enough reasoning to grok what that is. A
> summary of the options discussed so far:
> 
> - deferred inode freeing - ideal but too involved, want something sooner
>   and more simple
> - hinted non-busy chunk allocation - simple but jumping through too many
>   RCU requirement hoops
> - sync RCU and retry - most analogous to longer term busy inode
>   allocation handling (i.e. just replace rcu sync w/ log force and
>   retry), but RCU sync is too performance costly as a direct fallback
> 
> ISTM the options here range from simple and slow, to moderately simple
> and effective (TBD), to complex and ideal. So what is the goal for this
> series?

To find out if we can do something fast and effective (and without
hacks that might bite us unexepectedly) with RCU grace periods that
is less intrusive than changing inode life cycles. If it turns out
that we can change the inode life cycle faster than we can come up
with a RCU grace period based solution, then we should just go with
inode life cycle changes and forget about the interim RCU grace
period detection changes...

> My understanding to this point is that VFS changes are a ways
> out, so the first step was busy inodes == inodes with pending grace
> periods and a rework of the busy inode definition comes later with the
> associated VFS changes. That essentially means this series gets fixed up
> and posted as a mergeable component in the meantime, albeit with a
> "general direction" that is compatible with longer term changes.

It seems to me that the RCU detection code is also a ways out,
so I'm trying to keep our options open and not have us duplicate
work unnecessarily.

> However, every RCU requirement/characteristic that this series has to
> deal with is never going to be 100% perfectly aligned with the longer
> term busy inode requirements because the implementations/definitions
> will differ, particularly if the RCU handling is pushed up into the VFS.
> So if we're concerned about that, the alternative approach is to skip
> incrementally addressing the RCU inode reuse problem and just fold
> whatever bits of useful logic from here into your inode lifecycle work
> as needed and drop this as a mergeable component.

*nod*

The signs are pointing somewhat that way, but I'm still finding
the occasional unexpected gotcha in the code that I have to work
around. I think I've got them all, but until I've got it working it
pays to keep our options open....

Cheers,

Dave.
Brian Foster March 1, 2022, 3:05 p.m. UTC | #8
On Tue, Mar 01, 2022 at 09:55:56AM +1100, Dave Chinner wrote:
> On Mon, Feb 28, 2022 at 04:45:49PM -0500, Brian Foster wrote:
> > On Wed, Feb 23, 2022 at 06:00:58PM +1100, Dave Chinner wrote:
> > > i.e. as long as we track whether we've allocated a new inode chunk
> > > or not, we can bound the finobt search to a single retry. If we
> > > allocated a new chunk before entering the finobt search, then all we
> > > need is a log force because the busy inodes, by definition, are
> > > XFS_ISTALE at this point and waiting for a CIL push before they can
> > > be reclaimed. At this point an retry of the finobt scan will find
> > > those inodes that were busy now available for allocation.
> > 
> > Remind me what aspect of the prospective VFS changes prevents inode
> > allocation from seeing a free inode with not-yet-elapsed RCU grace
> > period..? Will this delay freeing (or evicting) the inode until a grace
> > period elapses from when the last reference was dropped?
> 
> It will delay it until the inode has been reclaimed, in which case
> reallocating it will result in a new struct xfs_inode being
> allocated from slab, and we're all good. Any lookup that finds the
> old inode will see either I_WILL_FREE, I_FREEING, I_CLEAR,
> XFS_NEED_INACTIVE, XFS_IRECLAIM or ip->i_ino == 0 depending on what
> point the lookup occurs. Hence the lookup will be unable to take a
> new reference to the unlinked inode, and the lookup retry should
> then get the newly allocated xfs_inode once it has been inserted
> into the radix tree...
> 
> IOWs, it gets rid of recycling altogether, and that's how we avoid
> the RCU grace period issues with recycled inodes.
> 
> > > > Perhaps a simple enough short term option is to use the existing block
> > > > alloc min/max range mechanisms (as mentioned on IRC). For example:
> > > > 
> > > > - Use the existing min/max_agbno allocation arg input values to attempt
> > > >   one or two chunk allocs outside of the known range of busy inodes for
> > > >   the AG (i.e., allocate blocks higher than the max busy agino or lower
> > > >   than the min busy agino).
> > > > - If success, then we know we've got a chunk w/o busy inodes.
> > > > - If failure, fall back to the existing chunk alloc calls, take whatever
> > > >   we get and retry the finobt scan (perhaps more aggressively checking
> > > >   each record) hoping we got a usable new record.
> > > > - If that still fails, then fall back to synchronize_rcu() as a last
> > > >   resort and grab one of the previously busy inodes.
> > > > 
> > > > I couldn't say for sure if that would be effective enough without
> > > > playing with it a bit, but that would sort of emulate an algorithm that
> > > > filtered chunk block allocations with at least one busy inode without
> > > > having to modify block allocation code. If it avoids an RCU sync in the
> > > > majority of cases it might be effective enough as a stopgap until
> > > > background freeing exists. Thoughts?
> > > 
> > > It might work, but I'm not a fan of how many hoops we are considering
> > > jumping through to avoid getting tangled up in the RCU requirements
> > > for VFS inode life cycles. I'd much prefer just being able to say
> > > "all inodes busy, log force, try again" like we do with busy extent
> > > limited block allocation...
> > > 
> > 
> > Well presumably that works fine for your implementation of busy inodes,
> > but not so much for the variant intended to work around the RCU inode
> > reuse problem. ISTM this all just depends on the goals and plan here,
> > and I'm not seeing clear enough reasoning to grok what that is. A
> > summary of the options discussed so far:
> > 
> > - deferred inode freeing - ideal but too involved, want something sooner
> >   and more simple
> > - hinted non-busy chunk allocation - simple but jumping through too many
> >   RCU requirement hoops
> > - sync RCU and retry - most analogous to longer term busy inode
> >   allocation handling (i.e. just replace rcu sync w/ log force and
> >   retry), but RCU sync is too performance costly as a direct fallback
> > 
> > ISTM the options here range from simple and slow, to moderately simple
> > and effective (TBD), to complex and ideal. So what is the goal for this
> > series?
> 
> To find out if we can do something fast and effective (and without
> hacks that might bite us unexepectedly) with RCU grace periods that
> is less intrusive than changing inode life cycles. If it turns out
> that we can change the inode life cycle faster than we can come up
> with a RCU grace period based solution, then we should just go with
> inode life cycle changes and forget about the interim RCU grace
> period detection changes...
> 
> > My understanding to this point is that VFS changes are a ways
> > out, so the first step was busy inodes == inodes with pending grace
> > periods and a rework of the busy inode definition comes later with the
> > associated VFS changes. That essentially means this series gets fixed up
> > and posted as a mergeable component in the meantime, albeit with a
> > "general direction" that is compatible with longer term changes.
> 
> It seems to me that the RCU detection code is also a ways out,
> so I'm trying to keep our options open and not have us duplicate
> work unnecessarily.
> 

It depends..? All discussions to this point around the "proper" fix to
the RCU inode recycle / lifecycle issue suggested a timeline of a year
or longer. Hence my initial thought process around the busy inode +
deferred inode freeing being a reasonable strategy. If the chunk
allocation hint thing is effective, then with that it's really just a
matter of factoring that in along with some allocation cleanups (i.e.
one chunk alloc retry limit, refining the !busy inode selection logic,
etc.) and then perhaps a few weeks or so of review/test/dev cycles on
top of that.

I've no real sense of where the lifecycle stuff is at or how invasive it
is, so have no real reference to compare against. In any event, my
attempts to progress this have kind of tripped my early wack-a-mole
detector so I'll leave this alone for now and we can come back to it as
an incremental step if the need arises.

Brian

> > However, every RCU requirement/characteristic that this series has to
> > deal with is never going to be 100% perfectly aligned with the longer
> > term busy inode requirements because the implementations/definitions
> > will differ, particularly if the RCU handling is pushed up into the VFS.
> > So if we're concerned about that, the alternative approach is to skip
> > incrementally addressing the RCU inode reuse problem and just fold
> > whatever bits of useful logic from here into your inode lifecycle work
> > as needed and drop this as a mergeable component.
> 
> *nod*
> 
> The signs are pointing somewhat that way, but I'm still finding
> the occasional unexpected gotcha in the code that I have to work
> around. I think I've got them all, but until I've got it working it
> pays to keep our options open....
> 
> Cheers,
> 
> Dave.
> -- 
> Dave Chinner
> david@fromorbit.com
>
diff mbox series

Patch

diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
index b418fe0c0679..3eb41228e210 100644
--- a/fs/xfs/libxfs/xfs_ialloc.c
+++ b/fs/xfs/libxfs/xfs_ialloc.c
@@ -27,6 +27,7 @@ 
 #include "xfs_log.h"
 #include "xfs_rmap.h"
 #include "xfs_ag.h"
+#include "xfs_trans_space.h"
 
 /*
  * Lookup a record by ino in the btree given by cur.
@@ -1689,6 +1690,7 @@  xfs_dialloc_try_ag(
 			goto out_release;
 		}
 
+alloc:
 		error = xfs_ialloc_ag_alloc(*tpp, agbp, pag);
 		if (error < 0)
 			goto out_release;
@@ -1706,8 +1708,22 @@  xfs_dialloc_try_ag(
 
 	/* Allocate an inode in the found AG */
 	error = xfs_dialloc_ag(*tpp, agbp, pag, parent, &ino);
-	if (!error)
+	if (!error) {
 		*new_ino = ino;
+	} else if (error == -EAGAIN) {
+		/*
+		 * XXX: Temporary hack to retry allocs until background chunk
+		 * freeing is worked out.
+		 */
+		error = xfs_mod_fdblocks(pag->pag_mount,
+			       -((int64_t)XFS_IALLOC_SPACE_RES(pag->pag_mount)),
+			       false);
+		if (error)
+			goto out_release;
+		(*tpp)->t_blk_res += XFS_IALLOC_SPACE_RES(pag->pag_mount);
+		goto alloc;
+	}
+
 	return error;
 
 out_release: