fs/file: optimize close_range() complexity from O(N) to O(Sparse)
PATCH 1/1 fs/file: optimize close_range() complexity from O(N) to O(Sparse)
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.
--- fs/file.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-)
fs/file.c +6 -2
@@ -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);
Signature · 1 line
2.51.0
Al Viro
maintainerQuoted 21 lines · 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 usingfind_next_bit()on theopen_fdsbitmap 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 <[email protected]>Signed-off-by Qiliang Yuan <[email protected]>--- fs/file.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-)fs/file.c +0
-0
fs/file.c static inline void __range_close(struct files_struct *files, unsigned int fd, · line 784
Quoted 9 lines
fs/file.c +2
-1@@ -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 1/1 fs/file: optimize close_range() complexity from O(N) to O(Sparse)
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.
---
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(-)
fs/file.c +8 -2
@@ -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);
Signature · 1 line
2.51.0
Quoted 5 lines · 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.
Quoted 7 lines
This patch optimizes
__range_close()by usingfind_next_bit()on theopen_fdsbitmap 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 <[email protected]>Signed-off-by Qiliang Yuan <[email protected]>
Thanks for the patch! It looks good to me. Feel free to add:
Honza
Quoted 50 lines
---
v2:
- Recalculate fdt after re-acquiringfile_lockto avoid UAF if the table is expanded/reallocated duringfilp_close()orcond_resched().
v1:
- Initial optimization usingfind_next_bit()onopen_fdsbitmap to skip holes, improving complexity to O(Active FDs).fs/file.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-)fs/file.c +8
-2@@ -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);Signature · 1 line
2.51.0
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR
Quoted 11 lines · 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 usingfind_next_bit()on theopen_fdsbitmap 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
Hi Christian,
Thanks for your feedback and for applying this patch to the vfs-7.0.misc branch!
Quoted 5 lines · Christian Brauner
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
Quoted 20 lines · 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 usingfind_next_bit()on theopen_fdsbitmap 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 <[email protected]>Signed-off-by Qiliang Yuan <[email protected]>---
v2:
- Recalculate fdt after re-acquiringfile_lockto avoid UAF if the table is expanded/reallocated duringfilp_close()orcond_resched().
v1:
- Initial optimization usingfind_next_bit()onopen_fdsbitmap to skip holes, improving complexity to O(Active FDs).
Quoted 2 lines
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