Message-ID: <54DBE027.3010209@gmail.com>
Date: Thu, 12 Feb 2015 02:05:11 +0300
From: Yury <yury.norov@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: Rasmus Villemoes <linux@rasmusvillemoes.dk>,
        George Spelvin <linux@horizon.com>
CC: akpm@linux-foundation.org, chris@chris-wilson.co.uk, davem@davemloft.net,
        dborkman@redhat.com, hannes@stressinduktion.org,
        klimov.linux@gmail.com, laijs@cn.fujitsu.com, msalter@redhat.com,
        takahiro.akashi@linaro.org, tgraf@suug.ch, valentinrothberg@gmail.com,
        linux-kernel@vger.kernel.org
Subject: Re: [PATCH v3 1/3] lib: find_*_bit reimplementation
References: <1423404619-10653-2-git-send-email-yury.norov@gmail.com>	<20150209083211.11953.qmail@ns.horizon.com> <87wq3rs3lp.fsf@rasmusvillemoes.dk>
In-Reply-To: <87wq3rs3lp.fsf@rasmusvillemoes.dk>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3464
Lines: 102


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