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] [day] [month] [year] [list]

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

On Fri, 23 Jan 2026 03:12:21 -0500, 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.
> 
> [...]

Applied to the vfs-7.0.misc branch of the vfs/vfs.git tree.
Patches in the vfs-7.0.misc branch should appear in linux-next soon.

Please report any outstanding bugs that were missed during review in a
new review to the original patch series allowing us to drop it.

It's encouraged to provide Acked-bys and Reviewed-bys even though the
patch has now been applied. If possible patch trailers will be updated.

Note that commit hashes shown below are subject to change due to rebase,
trailer updates or similar. If in doubt, please check the listed branch.

tree:   https://git.kernel.org/pub/scm/linux/kernel/git/vfs/vfs.git
branch: vfs-7.0.misc

[1/1] fs/file: optimize close_range() complexity from O(N) to O(Sparse)
      https://git.kernel.org/vfs/vfs/c/fc94368bcee5