linux-kernel - Re: [PATCH v2 1/3] fs/file.c: add fast path in alloc

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20240628091237.o5slz77tpwb5kdwj@quack3>
Date: Fri, 28 Jun 2024 11:12:37 +0200
From: Jan Kara <jack@...e.cz>
To: Mateusz Guzik <mjguzik@...il.com>
Cc: "Ma, Yu" <yu.ma@...el.com>, Christian Brauner <brauner@...nel.org>,
	Jan Kara <jack@...e.cz>, viro@...iv.linux.org.uk,
	edumazet@...gle.com, linux-fsdevel@...r.kernel.org,
	linux-kernel@...r.kernel.org, pan.deng@...el.com,
	tianyou.li@...el.com, tim.c.chen@...el.com,
	tim.c.chen@...ux.intel.com
Subject: Re: [PATCH v2 1/3] fs/file.c: add fast path in alloc_fd()

On Thu 27-06-24 21:59:12, Mateusz Guzik wrote:
> On Thu, Jun 27, 2024 at 8:27 PM Ma, Yu <yu.ma@...el.com> wrote:
> > 2. For fast path implementation, the essential and simple point is to
> > directly return an available bit if there is free bit in [0-63]. I'd
> > emphasize that it does not only improve low number of open fds (even it
> > is the majority case on system as Honza agreed), but also improve the
> > cases that lots of fds open/close frequently with short task (as per the
> > algorithm, lower bits will be prioritized to allocate after being
> > recycled). Not only blogbench, a synthetic benchmark, but also the
> > realistic scenario as claimed in f3f86e33dc3d("vfs: Fix pathological
> > performance case for __alloc_fd()"), which literally introduced this
> > 2-levels bitmap searching algorithm to vfs as we see now.
> 
> I don't understand how using next_fd instead is supposed to be inferior.
> 
> Maybe I should clarify that by API contract the kernel must return the
> lowest free fd it can find. To that end it maintains the next_fd field
> as a hint to hopefully avoid some of the search work.
> 
> In the stock kernel the first thing done in alloc_fd is setting it as
> a starting point:
>         fdt = files_fdtable(files);
>         fd = start;
>         if (fd < files->next_fd)
>                 fd = files->next_fd;
> 
> that is all the calls which come here with 0 start their search from
> next_fd position.

Yup.

> Suppose you implemented the patch as suggested by me and next_fd fits
> the range of 0-63. Then you get the benefit of lower level bitmap
> check just like in the patch you submitted, but without having to
> first branch on whether you happen to be in that range.
> 
> Suppose next_fd is somewhere higher up, say 80. With your general
> approach the optimization wont be done whatsoever or it will be
> attempted at the 0-63 range when it is an invariant it finds no free
> fds.
> 
> With what I'm suggesting the general idea of taking a peek at the
> lower level bitmap can be applied across the entire fd space. Some
> manual mucking will be needed to make sure this never pulls more than
> one cacheline, easiest way out I see would be to align next_fd to
> BITS_PER_LONG for the bitmap search purposes.

Well, all you need to do is to call:

	bit = find_next_zero_bit(fdt->open_fds[start / BITS_PER_LONG],
				 BITS_PER_LONG, start & (BITS_PER_LONG-1));
	if (bit < BITS_PER_LONG)
		return bit + (start & ~(BITS_PER_LONG - 1));


in find_next_fd(). Not sure if this is what you meant by aligning next_fd
to BITS_PER_LONG...

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