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@xxxxxxxxx>
> Signed-off-by: Qiliang Yuan <yuanql9@xxxxxxxxxxxxxxx>
> ---
> 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