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

[Yury <yury.norov@gmail.com>]

On 09.02.2015 14:53, Rasmus Villemoes wrote:
> [Yury, please do remember to Cc everyone who has previously
> participated]
>
> On Mon, Feb 09 2015, "George Spelvin" <linux@horizon.com> wrote:
>
>> Two more comments on the code.  Two minor, but one that
>> seems like a bug, so for now, it's
>>
>> Nacked-by: George Spelvin <linux@horizon.com> 
>>
>> Specifically, it seems like find_last_bit used to ignore trailing
>> garbage in the bitmap, but now will stop searching if the last word
>> contains some set bits not within size.
> True, though see below.
>
>> The minor one is that I don't think the first-word masking needs to
>> be conditional.  The general code works fine if the start is aligned
>> (HIGH_BITS_MASK just generates an all-ones mask), is quite quick, and
>> saves a test & conditional branch.
>>
> I also noted that during the first review, but when I tried to compile
> it gcc actually generated slightly worse code, so I decided not to
> comment on it. I don't have a strong preference either way, though.
>
>> Previously, the last word was masked, so bits beyond "size" were ignored.
>> With the revised code, something like find_last_bit(array, 96) will return 96
>> if array[1] >> 32 is non-zero, even if array[1] & 0xffffffff is zero.
>>
>> Looking through the callers, I haven't found a case where this matters yet
>> so perhaps it's a safe optimization, but this really needs to be more
>> clearly documented if intentional.
>>
>> If no change was desired, I'd think a good way to do this would be:
>>
>>  unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
>>  {
>> 	size_t idx = DIV_ROUND_UP(size, BITS_PER_LONG);
>>  	unsigned long tmp = addr[--idx];
>>
>> 	tmp &= (2UL << (size % BITS_PER_LONG)) - 1;	/* Mask last word */
>>
>> 	while (!tmp) {
>> 		if (!idx)
>> 			return size;
>>  		tmp = addr[--idx];
>> 	}
>> 	return idx * BITS_PER_LONG + __fls(tmp);
>> }
> How should that work? If size is for example 1, the mask evaluates to 3UL,
> while what is needed is 1UL. If size is aligned, the mask becomes 1UL,
> which is also not right.
>
> Also, I think it is best to handle size==0 appropriately, meaning that
> one cannot dereference addr in any way (and certainly not addr[-1]).
>
> So how about
>
> unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
> {
> 	size_t idx = DIV_ROUND_UP(size, BITS_PER_LONG);
> 	unsigned long mask = LAST_WORD_MASK(size);
>
> 	while (idx--) {
> 		unsigned long val = addr[idx] & mask;
> 		if (val)
> 			return idx * BITS_PER_LONG + __fls(val);
> 		mask = ~0ul;
> 	}
> 	return size;
> }
>
> Rasmus
Rasmus, your version has ANDing by mask, and resetting the mask at each iteration
of main loop. I think we can avoid it. What do you think on next?

unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
        size_t idx;
        unsigned long tmp;

        if (!size)
                return 0;

        idx = DIV_ROUND_UP(size, BITS_PER_LONG) - 1;
        tmp = addr[idx] & LAST_WORD_MASK(size);

        while (!tmp) {
                if (!idx--)
                        return size;
                tmp = addr[idx];
        }
        return idx * BITS_PER_LONG + __fls(tmp);
}

Yury