[PATCH] fs/file: optimize close_range() complexity from O(N) to O(Sparse)

[PATCH] fs/file: optimize close_range() complexity from O(N) to O(Sparse)

[Qiliang Yuan]

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@gmail.com>
Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
---
 fs/file.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/fs/file.c b/fs/file.c
index 0a4f3bdb2dec..c7c3ee03f8df 100644
--- a/fs/file.c
+++ b/fs/file.c
@@ -777,13 +777,17 @@ 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);
-- 
2.51.0

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

[Al Viro]

On Thu, Jan 22, 2026 at 11:35:53AM -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.
> 
> Signed-off-by: Qiliang Yuan <realwujing@gmail.com>
> Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
> ---
>  fs/file.c | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)
> 
> diff --git a/fs/file.c b/fs/file.c
> index 0a4f3bdb2dec..c7c3ee03f8df 100644
> --- a/fs/file.c
> +++ b/fs/file.c
> @@ -777,13 +777,17 @@ 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);

Careful - that thing might be expanded and reallocated once you drop
->file_lock (i.e. every time you close anything).  IOW, every time
you regain the lock, you need to recalculate fdt.

Other than that, looks sane.

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

[Qiliang Yuan]

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

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

[Jan Kara]

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

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

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

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

[Christian Brauner]

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

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

[Qiliang Yuan]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=y, Size: 868 bytes --]

Hi Christian,

Thanks for your feedback and for applying this patch to the vfs-7.0.misc branch!

On Fri, Jan 23, 2026 at 3:38 PM Christian Brauner <brauner@kernel.org> wrote:
> 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.
>
> [1/1] fs/file: optimize close_range() complexity from O(N) to O(Sparse)
>       https://git.kernel.org/vfs/vfs/c/fc94368bcee5

I tried to locate the commit in vfs/vfs-7.0.misc (and also searched by subject),
but I couldn’t find it yet.

Subject:
fs/file: optimize close_range() complexity from O(N) to O(Sparse)

Is the patch still in your local queue / pending push, or did it land with a
different commit hash after a rebase?

Just wanted to double-check the current status.
Thanks again for the review and for taking the patch.

Best regards,
Qiliang

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

[Eric Biggers]

On Fri, Jan 23, 2026 at 03:12:21AM -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.
> 
> Signed-off-by: Qiliang Yuan <realwujing@gmail.com>
> Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
> ---
> 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(-)

Well, the time complexity is still linear.  Just the constant factor is
better now because now it skips 64 fds at a time rather than 1.
Probably still worth it, but the claim that the time complexity is now
"O(Active FDs)" is false.

- Eric