Re: [PATCH v2 1/3] fs/file.c: add fast path in alloc_fd()

[Jan Kara <jack@suse.cz>]

On Thu 27-06-24 21:59:12, Mateusz Guzik wrote:
> On Thu, Jun 27, 2024 at 8:27 PM Ma, Yu <yu.ma@intel.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@suse.com>
SUSE Labs, CR