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

[Jan Kara]

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

								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