linux-kernel - Re: [PATCH v3 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] [thread-next>] [day] [month] [year] [list]

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


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@...izon.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@...izon.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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/