Messages in this thread | | | From | Rasmus Villemoes <> | Subject | Re: [PATCH v3 1/3] lib: find_*_bit reimplementation | Date | Mon, 09 Feb 2015 12:53:38 +0100 |
| |
[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
| |