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]

Message-ID: <87wq3rs3lp.fsf@rasmusvillemoes.dk>
Date:	Mon, 09 Feb 2015 12:53:38 +0100
From:	Rasmus Villemoes <linux@...musvillemoes.dk>
To:	"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, yury.norov@...il.com,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3 1/3] lib: find_*_bit reimplementation

[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
--
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/