linux-kernel - Re: [PATCH v2 1/3] lib: find_*

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]

Date:	Thu, 05 Feb 2015 16:01:26 +0100
From:	Rasmus Villemoes <linux@...musvillemoes.dk>
To:	Yury <yury.norov@...il.com>
Cc:	klimov.linux@...il.com, davem@...emloft.net,
	akpm@...ux-foundation.org, hannes@...essinduktion.org,
	dborkman@...hat.com, laijs@...fujitsu.com,
	takahiro.akashi@...aro.org, valentinrothberg@...il.com,
	linux@...izon.com, msalter@...hat.com, chris@...is-wilson.co.uk,
	tgraf@...g.ch, linux-kernel@...r.kernel.org,
	Yury Norov <y.norov@...sung.com>
Subject: Re: [PATCH v2 1/3] lib: find_*_bit reimplementation

On Wed, Feb 04 2015, Yury <yury.norov@...il.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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/