Re: [PATCH] fs/inode: replace goto-again rescan with cursor in evict_inodes()

[Mateusz Guzik]

On Tue, Jul 14, 2026 at 04:57:46PM +0200, Jan Kara wrote:
> On Tue 14-07-26 09:14:54, Jing Wu wrote:
> > evict_inodes() traverses sb->s_inodes to reclaim all zero-refcount
> > inodes at unmount time.  When the traversal yields to the scheduler
> > via cond_resched(), the current code jumps back to a "goto again"
> > label and restarts the list_for_each_entry loop from the head.
> > Inodes already marked I_FREEING are skipped cheaply, but the
> > repeated scans make the total work O(n * r) where r is the number
> > of reschedule events -- proportional to O(n^2) in the worst case on
> > systems with many inodes and memory pressure.
> > 
> > Replace the goto-again pattern with a sentinel cursor node embedded
> > in sb->s_inodes.  list_move() advances the cursor past each visited
> > inode in O(1).  Dropping and reacquiring s_inode_list_lock around
> > cond_resched() leaves the cursor in place, so the loop resumes from
> > exactly the current position rather than the list head, giving O(n)
> > total traversal.
> > 
> > Co-developed-by: Qiliang Yuan <yuanql9@xxxxxxxxxxxxxxx>
> > Signed-off-by: Qiliang Yuan <yuanql9@xxxxxxxxxxxxxxx>
> > Signed-off-by: Jing Wu <realwujing@xxxxxxxxx>
> 
> Do you observe some real problems with the code in evict_inodes()? If yes,
> they should be mentioned in the changelog. Because we should in fact skip
> very little inodes on s_inodes list (most of them should be readily
> evictable) and thus your worry about quadratic behavior shouldn't apply.
> 
> Also your solution with the cursor has the problem that now everybody
> scanning s_inodes list has to be aware of the special cursor node. So your
> patch breaks these other places scanning s_inodes list and if you were to
> fix them, things would get ugly and complex quickly...
> 

I think the fact that inode list scan is open-coded everywhere is a
problem in its own right and needs to be abstracted away, regardless of
what happens with the above idea.

The sb list lock is already highly contented and *any* attempt at fixing
it will require all places doing the walk to get patched.

Apart from that the hand-rolled scan encourages holding the lock of the
duration, which is pretty terrible in its own right.

The restart from scratch thing is a known problem type and inserting a
marker to get around it is the idiomatic solution, albeit just like you
I do suspect in the case of evict_inodes() this is not a serious
concern.

iow, the thing to do is provide some iterator API. but in the spirit of
reducing continuous hold time it very much will want a solution to the
restart problem (for example with a marker), in turn addressing the
evict_inodes() worry.

I was looking at this few years back $elsewhere. I think a sensible
approach would slurp some inodes into an array and process them
unlocked, rinse & repeat.

Grabbing a bunch of inodes into an array could be also to reduce
contention during memory reclaim for example.

> 								Honza
> 
> > ---
> > evict_inodes() is called at unmount time to reclaim all zero-refcount
> > inodes on a superblock.  Its current implementation uses a "goto again"
> > pattern: after dropping s_inode_list_lock for cond_resched() and
> > dispose_list(), it restarts list_for_each_entry from the list head.
> > 
> > In the common case (clean unmount, all files closed) the goto loop
> > terminates quickly because dispose_list() removes evicted inodes before
> > the restart.  However, when many inodes have a positive refcount and
> > cannot be evicted -- as happens with a force-unmount while file
> > descriptors are still open -- the restarts scan O(n) skippable inodes
> > each time, making total work O(n * r) proportional to O(n^2) in the
> > worst case.
> > 
> > This series replaces the goto-again pattern with a sentinel cursor node
> > embedded in sb->s_inodes, allowing the traversal to resume from its
> > current position after each lock drop.
> > ---
> >  fs/inode.c | 24 +++++++++++++++++++++---
> >  1 file changed, 21 insertions(+), 3 deletions(-)
> > 
> > diff --git a/fs/inode.c b/fs/inode.c
> > index acf206beb2e03..19197368c6a67 100644
> > --- a/fs/inode.c
> > +++ b/fs/inode.c
> > @@ -880,15 +880,31 @@ static void dispose_list(struct list_head *head)
> >   * called by superblock shutdown after having SB_ACTIVE flag removed,
> >   * so any inode reaching zero refcount during or after that call will
> >   * be immediately evicted.
> > + *
> > + * Use a cursor node embedded in sb->s_inodes to resume traversal after
> > + * dropping s_inode_list_lock for cond_resched() + dispose_list().  This
> > + * avoids restarting the scan from the list head on each reschedule, giving
> > + * O(n) total traversal instead of O(n * r) where r is the reschedule count.
> >   */
> >  void evict_inodes(struct super_block *sb)
> >  {
> >  	struct inode *inode;
> >  	LIST_HEAD(dispose);
> > +	/*
> > +	 * Embed a cursor node directly in sb->s_inodes.  list_move() advances
> > +	 * it past each visited inode in O(1), so the loop resumes from exactly
> > +	 * the current position after lock drop rather than from the list head.
> > +	 */
> > +	struct list_head cursor;
> >  
> > -again:
> >  	spin_lock(&sb->s_inode_list_lock);
> > -	list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
> > +	list_add(&cursor, &sb->s_inodes);
> > +
> > +	while (cursor.next != &sb->s_inodes) {
> > +		inode = list_entry(cursor.next, struct inode, i_sb_list);
> > +		/* Leave the cursor immediately after the current inode. */
> > +		list_move(&cursor, &inode->i_sb_list);
> > +
> >  		if (icount_read_once(inode))
> >  			continue;
> >  
> > @@ -916,9 +932,11 @@ void evict_inodes(struct super_block *sb)
> >  			spin_unlock(&sb->s_inode_list_lock);
> >  			cond_resched();
> >  			dispose_list(&dispose);
> > -			goto again;
> > +			spin_lock(&sb->s_inode_list_lock);
> >  		}
> >  	}
> > +
> > +	list_del(&cursor);
> >  	spin_unlock(&sb->s_inode_list_lock);
> >  
> >  	dispose_list(&dispose);
> > 
> > ---
> > base-commit: 502d801f0ab03e4f32f9a33d203154ce84887921
> > change-id: 20260713-feat-fs-evict-inodes-cursor-c23c9bd3c11f
> > 
> > Best regards,
> > -- 
> > Jing Wu <realwujing@xxxxxxxxx>
> > 
> -- 
> Jan Kara <jack@xxxxxxxx>
> SUSE Labs, CR