On Sat, Oct 3, 2020 at 2:51 AM Syed Nayyar Waris <syednwaris@xxxxxxxxx> wrote: Now I remember... This needs to be revisited. > This macro iterates for each group of bits (clump) with set bits, > within a bitmap memory region. For each iteration, "start" is set to > the bit offset of the found clump, while the respective clump value is > stored to the location pointed by "clump". Additionally, the > bitmap_get_value and bitmap_set_value functions are introduced to Mark functions like func() in the text as well. > respectively get and set a value of n-bits in a bitmap memory region. > The n-bits can have any size less than or equal to BITS_PER_LONG. > Moreover, during setting value of n-bit in bitmap, if a situation arise > that the width of next n-bit is exceeding the word boundary, then it > will divide itself such that some portion of it is stored in that word, > while the remaining portion is stored in the next higher word. Similar > situation occurs while retrieving value of n-bits from bitmap. retrieving the value from a bitmap ... > +/** > + * bitmap_get_value - get a value of n-bits from the memory region > + * @map: address to the bitmap memory region > + * @start: bit offset of the n-bit value > + * @nbits: size of value in bits > + * > + * Returns value of nbits located at the @start bit offset within the @map > + * memory region. > + */ > +static inline unsigned long bitmap_get_value(const unsigned long *map, > + unsigned long start, > + unsigned long nbits) > +{ > + const size_t index = BIT_WORD(start); > + const unsigned long offset = start % BITS_PER_LONG; > + const unsigned long ceiling = roundup(start + 1, BITS_PER_LONG); > + const unsigned long space = ceiling - start; > + unsigned long value_low, value_high; > + > + if (space >= nbits) > + return (map[index] >> offset) & GENMASK(nbits - 1, 0); This is UB in GENMASK() when nbits == 0. > + else { > + value_low = map[index] & BITMAP_FIRST_WORD_MASK(start); > + value_high = map[index + 1] & BITMAP_LAST_WORD_MASK(start + nbits); > + return (value_low >> offset) | (value_high << space); > + } > +} ... > +/** > + * bitmap_set_value - set n-bit value within a memory region > + * @map: address to the bitmap memory region > + * @value: value of nbits > + * @start: bit offset of the n-bit value > + * @nbits: size of value in bits > + */ > +static inline void bitmap_set_value(unsigned long *map, > + unsigned long value, > + unsigned long start, unsigned long nbits) > +{ > + const size_t index = BIT_WORD(start); > + const unsigned long offset = start % BITS_PER_LONG; > + const unsigned long ceiling = roundup(start + 1, BITS_PER_LONG); > + const unsigned long space = ceiling - start; > + value &= GENMASK(nbits - 1, 0); This is UB when nbits == 0. > + if (space >= nbits) { > + map[index] &= ~(GENMASK(nbits + offset - 1, offset)); UB when nbits == 0 and start == 0. > + map[index] |= value << offset; > + } else { > + map[index] &= ~BITMAP_FIRST_WORD_MASK(start); > + map[index] |= value << offset; > + map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits); > + map[index + 1] |= (value >> space); And another LKP finding was among these lines, but I don't remember the details. > + } > +} > + > #endif /* __ASSEMBLY__ */ > > #endif /* __LINUX_BITMAP_H */ > diff --git a/include/linux/bitops.h b/include/linux/bitops.h > index 99f2ac30b1d9..36a445e4a7cc 100644 > --- a/include/linux/bitops.h > +++ b/include/linux/bitops.h > @@ -62,6 +62,19 @@ extern unsigned long __sw_hweight64(__u64 w); > (start) < (size); \ > (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) > > +/** > + * for_each_set_clump - iterate over bitmap for each clump with set bits > + * @start: bit offset to start search and to store the current iteration offset > + * @clump: location to store copy of current 8-bit clump > + * @bits: bitmap address to base the search on > + * @size: bitmap size in number of bits > + * @clump_size: clump size in bits > + */ > +#define for_each_set_clump(start, clump, bits, size, clump_size) \ > + for ((start) = find_first_clump(&(clump), (bits), (size), (clump_size)); \ > + (start) < (size); \ > + (start) = find_next_clump(&(clump), (bits), (size), (start) + (clump_size), (clump_size))) > + > static inline int get_bitmask_order(unsigned int count) > { > int order; > diff --git a/lib/find_bit.c b/lib/find_bit.c > index 49f875f1baf7..1341bd39b32a 100644 > --- a/lib/find_bit.c > +++ b/lib/find_bit.c > @@ -190,3 +190,17 @@ unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, > return offset; > } > EXPORT_SYMBOL(find_next_clump8); > + > +unsigned long find_next_clump(unsigned long *clump, const unsigned long *addr, > + unsigned long size, unsigned long offset, > + unsigned long clump_size) > +{ > + offset = find_next_bit(addr, size, offset); > + if (offset == size) > + return size; > + > + offset = rounddown(offset, clump_size); > + *clump = bitmap_get_value(addr, offset, clump_size); > + return offset; > +} > +EXPORT_SYMBOL(find_next_clump); > -- > 2.26.2 > -- With Best Regards, Andy Shevchenko