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@chinatelecom.cn>
Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
Signed-off-by: Jing Wu <realwujing@gmail.com>
---
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@gmail.com>

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@chinatelecom.cn>
> Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
> Signed-off-by: Jing Wu <realwujing@gmail.com>

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...

								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@gmail.com>
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

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@chinatelecom.cn>
> > Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
> > Signed-off-by: Jing Wu <realwujing@gmail.com>
> 
> 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@gmail.com>
> > 
> -- 
> Jan Kara <jack@suse.com>
> SUSE Labs, CR