linux-kernel - Re: [PATCH v2] fs/file: optimize close_range() complexity from O(N) to O(Sparse)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <q6u5g43rs4jbgdfcqf4jbfi655rlpzn3wczmbew4tk5nozjvw4@imp7l33yhx6o>
Date: Fri, 23 Jan 2026 12:23:18 +0100
From: Jan Kara <jack@...e.cz>
To: Qiliang Yuan <realwujing@...il.com>
Cc: viro@...iv.linux.org.uk, brauner@...nel.org, jack@...e.cz, 
	linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org, yuanql9@...natelecom.cn
Subject: Re: [PATCH v2] fs/file: optimize close_range() complexity from O(N)
 to O(Sparse)

On Fri 23-01-26 03:12:21, Qiliang Yuan wrote:
> In close_range(), the kernel traditionally performs a linear scan over the
> [fd, max_fd] range, resulting in O(N) complexity where N is the range size.
> For processes with sparse FD tables, this is inefficient as it checks many
> unallocated slots.
> 
> This patch optimizes __range_close() by using find_next_bit() on the
> open_fds bitmap to skip holes. This shifts the algorithmic complexity from
> O(Range Size) to O(Active FDs), providing a significant performance boost
> for large-range close operations on sparse file descriptor tables.
> 
> Signed-off-by: Qiliang Yuan <realwujing@...il.com>
> Signed-off-by: Qiliang Yuan <yuanql9@...natelecom.cn>

Thanks for the patch! It looks good to me. Feel free to add:

Reviewed-by: Jan Kara <jack@...e.cz>

								Honza

> ---
> v2:
>   - Recalculate fdt after re-acquiring file_lock to avoid UAF if the
>     table is expanded/reallocated during filp_close() or cond_resched().
> v1:
>   - Initial optimization using find_next_bit() on open_fds bitmap to
>     skip holes, improving complexity to O(Active FDs).
> 
>  fs/file.c | 10 ++++++++--
>  1 file changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/fs/file.c b/fs/file.c
> index 0a4f3bdb2dec..51ddcff0081a 100644
> --- a/fs/file.c
> +++ b/fs/file.c
> @@ -777,23 +777,29 @@ static inline void __range_close(struct files_struct *files, unsigned int fd,
>  				 unsigned int max_fd)
>  {
>  	struct file *file;
> +	struct fdtable *fdt;
>  	unsigned n;
>  
>  	spin_lock(&files->file_lock);
> -	n = last_fd(files_fdtable(files));
> +	fdt = files_fdtable(files);
> +	n = last_fd(fdt);
>  	max_fd = min(max_fd, n);
>  
> -	for (; fd <= max_fd; fd++) {
> +	for (fd = find_next_bit(fdt->open_fds, max_fd + 1, fd);
> +	     fd <= max_fd;
> +	     fd = find_next_bit(fdt->open_fds, max_fd + 1, fd + 1)) {
>  		file = file_close_fd_locked(files, fd);
>  		if (file) {
>  			spin_unlock(&files->file_lock);
>  			filp_close(file, files);
>  			cond_resched();
>  			spin_lock(&files->file_lock);
> +			fdt = files_fdtable(files);
>  		} else if (need_resched()) {
>  			spin_unlock(&files->file_lock);
>  			cond_resched();
>  			spin_lock(&files->file_lock);
> +			fdt = files_fdtable(files);
>  		}
>  	}
>  	spin_unlock(&files->file_lock);
> -- 
> 2.51.0
> 
-- 
Jan Kara <jack@...e.com>
SUSE Labs, CR