linux-kernel - Re: [PATCH] fs/file: optimize FD allocation complexity with 3-level summary bitmap

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <53tznvyksgax5523tgnxk5hi5psi5qz4rvfsmywvv2pqjrb3hd@shlvji3mviy4>
Date: Fri, 23 Jan 2026 12:19:18 +0100
From: Jan Kara <jack@...e.cz>
To: Qiliang Yuan <realwujing@...il.com>
Cc: viro@...iv.linux.org.uk, brauner@...nel.org, jack@...e.cz, 
	linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org, yuanql9@...natelecom.cn
Subject: Re: [PATCH] fs/file: optimize FD allocation complexity with 3-level
 summary bitmap

On Thu 22-01-26 12:03:45, Qiliang Yuan wrote:
> Current FD allocation performs a two-level bitmap search (open_fds and
> full_fds_bits). This results in O(N/64) complexity when searching for a
> free FD, as the kernel needs to scan the first-level summary bitmap.
> 
> For processes with very large FD limits (e.g., millions of sockets),
> scanning even the level 1 summary bitmap can become a bottleneck during
> high-frequency allocation.
> 
> This patch introduces a third level of summary bitmap (full_fds_bits_l2),
> where each bit represents whether a 64-word chunk (4096 FDs) in open_fds
> is fully allocated. This reduces the search complexity to O(N/4096),
> making FD allocation significantly more scalable for high-concurrency
> workloads.
> 
> Signed-off-by: Qiliang Yuan <realwujing@...il.com>
> Signed-off-by: Qiliang Yuan <yuanql9@...natelecom.cn>

Thanks for the patch! I tend to agree with Mateusz that performance numbers
(of some realistic load) for this are needed - not only for your case of
application with huge number of fds but also for tasks with lower number of
fds. Because you are adding another memory (and cacheline) load in the fd
allocation path also for the applications that are happy with the current
2-level allocation scheme. And that is actually a vast majority of
applications... And yes, the additional load does matter as for example
commit 0c40bf47cf2 ("fs/file.c: add fast path in find_next_fd()") provided
measurable improvements when avoiding it.

								Honza

-- 
Jan Kara <jack@...e.com>
SUSE Labs, CR