Messages in this thread | | | Date | Thu, 12 Feb 2015 02:05:11 +0300 | From | Yury <> | 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@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
| |