Skip to contentSkip to conversation

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

PATCH Superseded Qiliang Yuan 5 participants 7 messages Jan 22 – Feb 18 VFS

lore
Share & tools
lore
#0 lore raw

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
index 0a4f3bdb2dec..c7c3ee03f8df 100644
@@ -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
maintainer
#1 lore raw
Quoted 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 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 +0 -0
index 0a4f3bdb2dec..c7c3ee03f8df 100644

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.

#2 lore raw

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
index 0a4f3bdb2dec..51ddcff0081a 100644
@@ -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
reviewer Reviewed-by on v2 1/1
#3 lore raw
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 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.

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

Honza

Quoted 50 lines

---
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
index 0a4f3bdb2dec..51ddcff0081a 100644
@@ -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
maintainer Applied
#4 lore raw
In reply to Qiliang Yuan
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 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
#5 lore raw

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

#6 lore raw
In reply to Qiliang Yuan
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 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).

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