Re: [PATCH] vfs: remove always taken if-branch in find_next_fd()

[Jan Kara]

On Mon 20-04-26 12:18:01, Jori Koolstra wrote:
> find_next_fd() finds the next free fd slot in the passed fdtable's
> bitmap. It does so in two steps: first it checks whether the bitmap
> has a free entry in the word containing start. If not, it looks at
> second level bitmap that registers which words in the first level bitmap
> are full and then looks at the first level bitmap at the first non-full
> word.
> 
> In the current code the second level lookup is done by:
> 
>   bitbit = find_next_zero_bit(fdt->full_fds_bits, maxbit, bitbit) *
>     BITS_PER_LONG;
> 
> where bitbit = start / BITS_PER_LONG. However, in the fast path (first
> step) we already checked the word at bitbit, so we can skip that word bit
> and start at bitbit+1. This also means that we can get rid of the branch
> 
>   if (bitbit > start)
>     start = bitbit;
> 
> since if we set
> 
>   bitbit = find_next_zero_bit(fdt->full_fds_bits, maxbit, bitbit+1) *
>     BITS_PER_LONG;
> 
> the reassigned bitbit can never be less than
> 
>   ((start/BITS_PER_LONG)+1) * BITS_PER_LONG > start
> 
> So the branch is always taken.
> 
> Obviously the reuse of the variable name bitbit (and the name itself) is
> quite confusing, so change that as well.
> 
> Signed-off-by: Jori Koolstra <jkoolstra@xxxxxxxxx>

Nice. Looks good to me. Feel free to add:

Reviewed-by: Jan Kara <jack@xxxxxxx>

								Honza

> ---
>  fs/file.c | 17 ++++++++---------
>  1 file changed, 8 insertions(+), 9 deletions(-)
> 
> diff --git a/fs/file.c b/fs/file.c
> index 384c83ce768d..b7b78efcb0d1 100644
> --- a/fs/file.c
> +++ b/fs/file.c
> @@ -544,24 +544,23 @@ struct files_struct init_files = {
>  static unsigned int find_next_fd(struct fdtable *fdt, unsigned int start)
>  {
>  	unsigned int maxfd = fdt->max_fds; /* always multiple of BITS_PER_LONG */
> -	unsigned int maxbit = maxfd / BITS_PER_LONG;
> -	unsigned int bitbit = start / BITS_PER_LONG;
> +	unsigned int max_fds_words = maxfd / BITS_PER_LONG;
> +	unsigned int fds_word_idx = start / BITS_PER_LONG;
>  	unsigned int bit;
>  
>  	/*
>  	 * Try to avoid looking at the second level bitmap
>  	 */
> -	bit = find_next_zero_bit(&fdt->open_fds[bitbit], BITS_PER_LONG,
> +	bit = find_next_zero_bit(&fdt->open_fds[fds_word_idx], BITS_PER_LONG,
>  				 start & (BITS_PER_LONG - 1));
>  	if (bit < BITS_PER_LONG)
> -		return bit + bitbit * BITS_PER_LONG;
> +		return bit + (fds_word_idx * BITS_PER_LONG);
>  
> -	bitbit = find_next_zero_bit(fdt->full_fds_bits, maxbit, bitbit) * BITS_PER_LONG;
> -	if (bitbit >= maxfd)
> +	bit = BITS_PER_LONG *
> +		find_next_zero_bit(fdt->full_fds_bits, max_fds_words, fds_word_idx + 1);
> +	if (bit >= maxfd)
>  		return maxfd;
> -	if (bitbit > start)
> -		start = bitbit;
> -	return find_next_zero_bit(fdt->open_fds, maxfd, start);
> +	return find_next_zero_bit(fdt->open_fds, maxfd, bit);
>  }
>  
>  /*
> -- 
> 2.53.0
> 
-- 
Jan Kara <jack@xxxxxxxx>
SUSE Labs, CR