]> git.ipfire.org Git - thirdparty/linux.git/commit
fs/file: optimize close_range() complexity from O(N) to O(Sparse)
authorQiliang Yuan <realwujing@gmail.com>
Fri, 23 Jan 2026 08:12:21 +0000 (03:12 -0500)
committerChristian Brauner <brauner@kernel.org>
Fri, 23 Jan 2026 10:31:49 +0000 (11:31 +0100)
commitfc94368bcee555b2cc44c2f4e7c4fcbb50404cd3
tree72eac90b8034660a26a7d96126ad5050608e4bae
parent6cbfdf89470ef3c2110f376a507d135e7a7a7378
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.

Signed-off-by: Qiliang Yuan <realwujing@gmail.com>
Signed-off-by: Qiliang Yuan <yuanql9@chinatelecom.cn>
Link: https://patch.msgid.link/20260123081221.659125-1-realwujing@gmail.com
Signed-off-by: Christian Brauner <brauner@kernel.org>
fs/file.c