From: Andy Shevchenko <andy.shevchenko@gmail.com>
To: Syed Nayyar Waris <syednwaris@gmail.com>
Cc: Linus Walleij <linus.walleij@linaro.org>,
Andrew Morton <akpm@linux-foundation.org>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
William Breathitt Gray <vilhelm.gray@gmail.com>,
Arnd Bergmann <arnd@arndb.de>,
Linux-Arch <linux-arch@vger.kernel.org>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v10 1/4] bitops: Introduce the for_each_set_clump macro
Date: Sat, 3 Oct 2020 11:44:17 +0300 [thread overview]
Message-ID: <CAHp75VcoGAjrPa7rcORsaDXZLb-n+U3hG0k6O+weMVYweSPVxg@mail.gmail.com> (raw)
In-Reply-To: <dcd0580812ebae079e6f5035b990b195ccc6b709.1601679791.git.syednwaris@gmail.com>
On Sat, Oct 3, 2020 at 2:51 AM Syed Nayyar Waris <syednwaris@gmail.com> 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
next prev parent reply other threads:[~2020-10-03 8:44 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-02 23:47 [PATCH v10 0/4] Introduce the for_each_set_clump macro Syed Nayyar Waris
2020-10-02 23:48 ` [PATCH v10 1/4] bitops: " Syed Nayyar Waris
2020-10-03 8:44 ` Andy Shevchenko [this message]
2020-10-03 11:36 ` Syed Nayyar Waris
2020-10-03 12:45 ` Andy Shevchenko
2020-10-03 12:56 ` William Breathitt Gray
2020-10-03 13:02 ` Andy Shevchenko
2020-10-03 15:08 ` Syed Nayyar Waris
2020-10-05 9:35 ` Andy Shevchenko
2020-10-02 23:49 ` [PATCH v10 2/4] lib/test_bitmap.c: Add for_each_set_clump test cases Syed Nayyar Waris
2020-10-02 23:51 ` [PATCH v10 3/4] gpio: thunderx: Utilize for_each_set_clump macro Syed Nayyar Waris
2020-10-02 23:52 ` [PATCH v10 4/4] gpio: xilinx: Utilize generic bitmap_get_value and _set_value Syed Nayyar Waris
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAHp75VcoGAjrPa7rcORsaDXZLb-n+U3hG0k6O+weMVYweSPVxg@mail.gmail.com \
--to=andy.shevchenko@gmail.com \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=arnd@arndb.de \
--cc=linus.walleij@linaro.org \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=syednwaris@gmail.com \
--cc=vilhelm.gray@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).