Re: [PATCH v2 1/3] lib: find_*_bit reimplementation

[Rasmus Villemoes <linux@rasmusvillemoes.dk>]

On Wed, Feb 04 2015, Yury <yury.norov@gmail.com> wrote:

> On 02.02.2015 13:43, Rasmus Villemoes wrote:
>>> @@ -23,86 +50,22 @@
>>>  unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
>>>  			    unsigned long offset)
>>>  {
>>> -	const unsigned long *p = addr + BITOP_WORD(offset);
>>> -	unsigned long result = offset & ~(BITS_PER_LONG-1);
>>> -	unsigned long tmp;
>>> -
>>>  	if (offset >= size)
>>>  		return size;
>> Why can't this ...
>>
>>
>>> -	size -= result;
>>> -	offset %= BITS_PER_LONG;
>>> -	if (offset) {
>>> -		tmp = *(p++);
>>> -		tmp &= (~0UL << offset);
>>> -		if (size < BITS_PER_LONG)
>>> -			goto found_first;
>>> -		if (tmp)
>>> -			goto found_middle;
>>> -		size -= BITS_PER_LONG;
>>> -		result += BITS_PER_LONG;
>>> -	}
>>> -	while (size & ~(BITS_PER_LONG-1)) {
>>> -		if ((tmp = *(p++)))
>>> -			goto found_middle;
>>> -		result += BITS_PER_LONG;
>>> -		size -= BITS_PER_LONG;
>>> -	}
>>> -	if (!size)
>>> -		return result;
>>> -	tmp = *p;
>>>  
>>> -found_first:
>>> -	tmp &= (~0UL >> (BITS_PER_LONG - size));
>>> -	if (tmp == 0UL)		/* Are any bits set? */
>>> -		return result + size;	/* Nope. */
>>> -found_middle:
>>> -	return result + __ffs(tmp);
>>> +	return min(_find_next_bit(addr, size, offset, 1), size);
>> ... and this be part of _find_next_bit? Can find_next_bit not be simply
>> 'return _find_next_bit(addr, size, offset, 1);', and similarly for
>> find_next_zero_bit? Btw., passing true and false for the boolean
>> parameter may be a little clearer.
> I moved size checkers out of '_find_next_bit' to let user call it from his code
> if he knows for sure that size/offset pair is valid. This may help save a couple
> of clocks. I think, I'll walk over the code to find how many such places we have.
> If not too much / not in critical paths, checks may be moved into the function.

But _find_next_bit is static, so outsiders can't call it... The branches
are easily predicted and hence almost free, so I think it's better to do
the code deduplication and move the bounds checking inside
_find_next_bit, so that find_next_bit is literally just 'return
_find_next_bit(addr, size, offset, 0ul);' and find_next_zero_bit is
'return _find_next_bit(addr, size, offset, ~0ul);'.

Rasmus