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" <li...@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 <li...@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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
