| 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
| ||
|
Message-ID: <ZSCLuCu9yMyDdHni@yury-ThinkPad>
Date: Fri, 6 Oct 2023 15:35:49 -0700
From: Yury Norov <yury.norov@...il.com>
To: Alexander Potapenko <glider@...gle.com>
Cc: catalin.marinas@....com, will@...nel.org, pcc@...gle.com,
andreyknvl@...il.com, andriy.shevchenko@...ux.intel.com,
aleksander.lobakin@...el.com, linux@...musvillemoes.dk,
linux-kernel@...r.kernel.org, linux-arm-kernel@...ts.infradead.org,
eugenis@...gle.com, syednwaris@...il.com, william.gray@...aro.org,
Arnd Bergmann <arnd@...db.de>
Subject: Re: [PATCH v6 1/5] lib/bitmap: add bitmap_{read,write}()
On Fri, Oct 06, 2023 at 03:45:25PM +0200, Alexander Potapenko wrote:
> From: Syed Nayyar Waris <syednwaris@...il.com>
>
> The two new functions allow reading/writing values of length up to
> BITS_PER_LONG bits at arbitrary position in the bitmap.
>
> The code was taken from "bitops: Introduce the for_each_set_clump macro"
> by Syed Nayyar Waris with a number of changes and simplifications:
> - instead of using roundup(), which adds an unnecessary dependency
> on <linux/math.h>, we calculate space as BITS_PER_LONG-offset;
> - indentation is reduced by not using else-clauses (suggested by
> checkpatch for bitmap_get_value());
> - bitmap_get_value()/bitmap_set_value() are renamed to bitmap_read()
> and bitmap_write();
> - some redundant computations are omitted.
>
> Cc: Arnd Bergmann <arnd@...db.de>
> Signed-off-by: Syed Nayyar Waris <syednwaris@...il.com>
> Signed-off-by: William Breathitt Gray <william.gray@...aro.org>
> Link: https://lore.kernel.org/lkml/fe12eedf3666f4af5138de0e70b67a07c7f40338.1592224129.git.syednwaris@gmail.com/
> Suggested-by: Yury Norov <yury.norov@...il.com>
> Co-developed-by: Alexander Potapenko <glider@...gle.com>
> Signed-off-by: Alexander Potapenko <glider@...gle.com>
>
> ---
> This patch was previously called "lib/bitmap: add
> bitmap_{set,get}_value()"
> (https://lore.kernel.org/lkml/20230720173956.3674987-2-glider@google.com/)
>
> v6:
> - As suggested by Yury Norov, do not require bitmap_read(..., 0) to
> return 0.
>
> v5:
> - Address comments by Yury Norov:
> - updated code comments and patch title/description
> - replace GENMASK(nbits - 1, 0) with BITMAP_LAST_WORD_MASK(nbits)
> - more compact bitmap_write() implementation
>
> v4:
> - Address comments by Andy Shevchenko and Yury Norov:
> - prevent passing values >= 64 to GENMASK()
> - fix commit authorship
> - change comments
> - check for unlikely(nbits==0)
> - drop unnecessary const declarations
> - fix kernel-doc comments
> - rename bitmap_{get,set}_value() to bitmap_{read,write}()
> ---
> include/linux/bitmap.h | 68 ++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 68 insertions(+)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 03644237e1efb..e72c054d21d48 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -76,7 +76,11 @@ struct device;
> * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst
> * bitmap_to_arr64(buf, src, nbits) Copy nbits from buf to u64[] dst
> * bitmap_get_value8(map, start) Get 8bit value from map at start
> + * bitmap_read(map, start, nbits) Read an nbits-sized value from
> + * map at start
> * bitmap_set_value8(map, value, start) Set 8bit value to map at start
> + * bitmap_write(map, value, start, nbits) Write an nbits-sized value to
> + * map at start
> *
> * Note, bitmap_zero() and bitmap_fill() operate over the region of
> * unsigned longs, that is, bits behind bitmap till the unsigned long
> @@ -583,6 +587,33 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map,
> return (map[index] >> offset) & 0xFF;
> }
>
> +/**
> + * bitmap_read - read 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, nonzero, up to BITS_PER_LONG
> + *
> + * Returns: value of nbits located at the @start bit offset within the @map
> + * memory region.
> + */
> +static inline unsigned long bitmap_read(const unsigned long *map,
> + unsigned long start,
> + unsigned long nbits)
> +{
> + size_t index = BIT_WORD(start);
> + unsigned long offset = start % BITS_PER_LONG;
> + unsigned long space = BITS_PER_LONG - offset;
> + unsigned long value_low, value_high;
> +
> + if (unlikely(!nbits))
> + return 0;
> + if (space >= nbits)
> + return (map[index] >> offset) & GENMASK(nbits - 1, 0);
> + 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_value8 - set an 8-bit value within a memory region
> * @map: address to the bitmap memory region
> @@ -599,6 +630,43 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
> map[index] |= value << offset;
> }
>
> +/**
> + * bitmap_write - write n-bit value within a memory region
> + * @map: address to the bitmap memory region
> + * @value: value to write, clamped to nbits
> + * @start: bit offset of the n-bit value
> + * @nbits: size of value in bits, nonzero, up to BITS_PER_LONG.
> + *
> + * bitmap_write() behaves similarly to @nbits calls of assign_bit(), i.e. bits
> + * beyond @nbits are ignored:
> + *
> + * for (bit = 0; bit < nbits; bit++)
> + * assign_bit(start + bit, bitmap, val & BIT(bit));
__assign_bit()
> + */
'behaves similarly' sounds like an understatement. I think, it behaves
much faster because it can assign up to 64 bits at once, not mentioning
the pressure on cache lines traffic.
How faster - that's a good question. I'd be really pleased if you add
a performance test for bitmap_write/read. Or I can do it myself later.
You can find examples in the same lib/test_bitmap.c.
> +static inline void bitmap_write(unsigned long *map,
> + unsigned long value,
> + unsigned long start, unsigned long nbits)
> +{
> + size_t index = BIT_WORD(start);
> + unsigned long offset = start % BITS_PER_LONG;
> + unsigned long space = BITS_PER_LONG - offset;
> + unsigned long mask;
> +
> + if (unlikely(!nbits))
> + return;
can you please add more empty lines to separate blocks visually?
> + mask = BITMAP_LAST_WORD_MASK(nbits);
> + value &= mask;
> + if (space >= nbits) {
> + map[index] &= ~(mask << offset);
> + map[index] |= value << offset;
> + return;
> + }
> + 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);
> +}
I compiled the below fix on spark64 BE machine:
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -608,7 +608,7 @@ static inline unsigned long bitmap_read(const unsigned long *map,
if (unlikely(!nbits))
return 0;
if (space >= nbits)
- return (map[index] >> offset) & GENMASK(nbits - 1, 0);
+ return (map[index] >> offset) & BITMAP_LAST_WORD_MASK(nbits);
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);
@@ -661,9 +661,9 @@ static inline void bitmap_write(unsigned long *map,
map[index] |= value << offset;
return;
}
- map[index] &= ~BITMAP_FIRST_WORD_MASK(start);
+ map[index] &= BITMAP_LAST_WORD_MASK(start);
map[index] |= value << offset;
- map[index + 1] &= ~BITMAP_LAST_WORD_MASK(start + nbits);
+ map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits);
map[index + 1] |= (value >> space);
}
All the tests are passed just as before, and there's no any difference
reported by bloat-o-meter. Can you please use non-negation versions as
they are more straightforward?
> +
> #endif /* __ASSEMBLY__ */
>
> #endif /* __LINUX_BITMAP_H */
> --
> 2.42.0.609.gbb76f46606-goog
Powered by blists - more mailing lists