From: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
These helpers scatters or gathers a bitmap with the help of the mask
position bits parameter.
bitmap_scatter() does the following:
src: 0000000001011010
||||||
+------+|||||
| +----+||||
| |+----+|||
| || +-+||
| || | ||
mask: ...v..vv...v..vv
...0..11...0..10
dst: 0000001100000010
and bitmap_gather() performs this one:
mask: ...v..vv...v..vv
src: 0000001100000010
^ ^^ ^ 0
| || | 10
| || > 010
| |+--> 1010
| +--> 11010
+----> 011010
dst: 0000000000011010
bitmap_gather() can the seen as the reverse bitmap_scatter() operation.
The original work was done by Andy Shevchenko.
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Link: https://lore.kernel.org/lkml/20230926052007.3917389-3-andriy.shevchenko@linux.intel.com/
Signed-off-by: Herve Codina <herve.codina@bootlin.com>
---
Yury, Andy, I hope I correctly took into accounts the comments
reveived on Andy's v1 series and found good compromise to satisfy
your different point of view.
include/linux/bitmap.h | 101 +++++++++++++++++++++++++++++++++++++++++
lib/test_bitmap.c | 42 +++++++++++++++++
2 files changed, 143 insertions(+)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 99451431e4d6..a171030ff71c 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -62,6 +62,8 @@ struct device;
* bitmap_shift_left(dst, src, n, nbits) *dst = *src << n
* bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest
* bitmap_replace(dst, old, new, mask, nbits) *dst = (*old & ~(*mask)) | (*new & *mask)
+ * bitmap_scatter(dst, src, mask, nbits) *dst = map(dense, sparse)(src)
+ * bitmap_gather(dst, src, mask, nbits) *dst = map(sparse, dense)(src)
* bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
* bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit)
* bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap
@@ -487,6 +489,105 @@ static inline void bitmap_replace(unsigned long *dst,
__bitmap_replace(dst, old, new, mask, nbits);
}
+/**
+ * bitmap_scatter - Scatter a bitmap according to the given mask
+ * @dst: scattered bitmap
+ * @src: gathered bitmap
+ * @mask: mask representing bits to assign to in the scattered bitmap
+ * @nbits: number of bits in each of these bitmaps
+ *
+ * Scatters bitmap with sequential bits according to the given @mask.
+ *
+ * Example:
+ * If @src bitmap = 0x005a, with @mask = 0x1313, @dst will be 0x0302.
+ *
+ * Or in binary form
+ * @src @mask @dst
+ * 0000000001011010 0001001100010011 0000001100000010
+ *
+ * (Bits 0, 1, 2, 3, 4, 5 are copied to the bits 0, 1, 4, 8, 9, 12)
+ *
+ * A more 'visual' description of the operation:
+ * src: 0000000001011010
+ * ||||||
+ * +------+|||||
+ * | +----+||||
+ * | |+----+|||
+ * | || +-+||
+ * | || | ||
+ * mask: ...v..vv...v..vv
+ * ...0..11...0..10
+ * dst: 0000001100000010
+ *
+ * A relationship exists between bitmap_scatter() and bitmap_gather().
+ * bitmap_gather() can be seen as the 'reverse' bitmap_scatter() operation.
+ * See bitmap_scatter() for details related to this relationship.
+ */
+static inline void bitmap_scatter(unsigned long *dst, const unsigned long *src,
+ const unsigned long *mask, unsigned int nbits)
+{
+ unsigned int n = 0;
+ unsigned int bit;
+
+ bitmap_zero(dst, nbits);
+
+ for_each_set_bit(bit, mask, nbits)
+ __assign_bit(bit, dst, test_bit(n++, src));
+}
+
+/**
+ * bitmap_gather - Gather a bitmap according to given mask
+ * @dst: gathered bitmap
+ * @src: scattered bitmap
+ * @mask: mask representing bits to extract from in the scattered bitmap
+ * @nbits: number of bits in each of these bitmaps
+ *
+ * Gathers bitmap with sparse bits according to the given @mask.
+ *
+ * Example:
+ * If @src bitmap = 0x0302, with @mask = 0x1313, @dst will be 0x001a.
+ *
+ * Or in binary form
+ * @src @mask @dst
+ * 0000001100000010 0001001100010011 0000000000011010
+ *
+ * (Bits 0, 1, 4, 8, 9, 12 are copied to the bits 0, 1, 2, 3, 4, 5)
+ *
+ * A more 'visual' description of the operation:
+ * mask: ...v..vv...v..vv
+ * src: 0000001100000010
+ * ^ ^^ ^ 0
+ * | || | 10
+ * | || > 010
+ * | |+--> 1010
+ * | +--> 11010
+ * +----> 011010
+ * dst: 0000000000011010
+ *
+ * A relationship exists between bitmap_gather() and bitmap_scatter() (See
+ * bitmap_scatter() for the bitmap scatter detailed operations).
+ * Suppose scattered computed using bitmap_scatter(scattered, src, mask, n).
+ * The operation bitmap_gather(result, scattered, mask, n) leads to a result
+ * equal or equivalent to src.
+ *
+ * The result can be 'equivalent' because bitmap_scatter() and bitmap_gather()
+ * are not bijective.
+ * The result and src values are equivalent in that sense that a call to
+ * bitmap_scatter(res, src, mask, n) and a call to bitmap_scatter(res, result,
+ * mask, n) will lead to the same res value.
+ */
+static inline void bitmap_gather(unsigned long *dst, const unsigned long *src,
+ const unsigned long *mask, unsigned int nbits)
+{
+ unsigned int n = 0;
+ unsigned int bit;
+
+ bitmap_zero(dst, nbits);
+
+ for_each_set_bit(bit, mask, nbits)
+ __assign_bit(n++, dst, test_bit(bit, src));
+}
+
static inline void bitmap_next_set_region(unsigned long *bitmap,
unsigned int *rs, unsigned int *re,
unsigned int end)
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 65f22c2578b0..6b2b33579f56 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -380,6 +380,47 @@ static void __init test_replace(void)
expect_eq_bitmap(bmap, exp3_1_0, nbits);
}
+static const unsigned long sg_mask[] __initconst = {
+ BITMAP_FROM_U64(0x000000000000035aULL),
+};
+
+static const unsigned long sg_src[] __initconst = {
+ BITMAP_FROM_U64(0x0000000000000667ULL),
+};
+
+static const unsigned long sg_gather_exp[] __initconst = {
+ BITMAP_FROM_U64(0x0000000000000029ULL),
+};
+
+static const unsigned long sg_scatter_exp[] __initconst = {
+ BITMAP_FROM_U64(0x000000000000021aULL),
+};
+
+static void __init test_bitmap_sg(void)
+{
+ unsigned int nbits = 64;
+ DECLARE_BITMAP(bmap_gather, 100);
+ DECLARE_BITMAP(bmap_scatter, 100);
+ DECLARE_BITMAP(bmap_tmp, 100);
+ DECLARE_BITMAP(bmap_res, 100);
+
+ /* Simple gather call */
+ bitmap_zero(bmap_gather, 100);
+ bitmap_gather(bmap_gather, sg_src, sg_mask, nbits);
+ expect_eq_bitmap(sg_gather_exp, bmap_gather, nbits);
+
+ /* Simple scatter call */
+ bitmap_zero(bmap_scatter, 100);
+ bitmap_scatter(bmap_scatter, sg_src, sg_mask, nbits);
+ expect_eq_bitmap(sg_scatter_exp, bmap_scatter, nbits);
+
+ /* Scatter/gather relationship */
+ bitmap_zero(bmap_tmp, 100);
+ bitmap_gather(bmap_tmp, bmap_scatter, sg_mask, nbits);
+ bitmap_scatter(bmap_res, bmap_tmp, sg_mask, nbits);
+ expect_eq_bitmap(bmap_scatter, bmap_res, nbits);
+}
+
#define PARSE_TIME 0x1
#define NO_LEN 0x2
@@ -1252,6 +1293,7 @@ static void __init selftest(void)
test_copy();
test_bitmap_region();
test_replace();
+ test_bitmap_sg();
test_bitmap_arr32();
test_bitmap_arr64();
test_bitmap_parse();
--
2.43.0On Thu, Feb 22, 2024 at 03:22:16PM +0100, Herve Codina wrote: > From: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > > These helpers scatters or gathers a bitmap with the help of the mask > position bits parameter. > > bitmap_scatter() does the following: > src: 0000000001011010 > |||||| > +------+||||| > | +----+|||| > | |+----+||| > | || +-+|| > | || | || > mask: ...v..vv...v..vv > ...0..11...0..10 > dst: 0000001100000010 > > and bitmap_gather() performs this one: > mask: ...v..vv...v..vv > src: 0000001100000010 > ^ ^^ ^ 0 > | || | 10 > | || > 010 > | |+--> 1010 > | +--> 11010 > +----> 011010 > dst: 0000000000011010 > > bitmap_gather() can the seen as the reverse bitmap_scatter() operation. > The original work was done by Andy Shevchenko. Mine SoB is enough for a credit, but thank you :-) ... > +/** > + * bitmap_gather - Gather a bitmap according to given mask > + * @dst: gathered bitmap > + * @src: scattered bitmap > + * @mask: mask representing bits to extract from in the scattered bitmap > + * @nbits: number of bits in each of these bitmaps > + * > + * Gathers bitmap with sparse bits according to the given @mask. > + * > + * Example: > + * If @src bitmap = 0x0302, with @mask = 0x1313, @dst will be 0x001a. > + * > + * Or in binary form > + * @src @mask @dst > + * 0000001100000010 0001001100010011 0000000000011010 > + * > + * (Bits 0, 1, 4, 8, 9, 12 are copied to the bits 0, 1, 2, 3, 4, 5) > + * > + * A more 'visual' description of the operation: > + * mask: ...v..vv...v..vv > + * src: 0000001100000010 > + * ^ ^^ ^ 0 > + * | || | 10 > + * | || > 010 > + * | |+--> 1010 > + * | +--> 11010 > + * +----> 011010 > + * dst: 0000000000011010 Cool! > + * A relationship exists between bitmap_gather() and bitmap_scatter() (See Either '... (see' or '(). See' > + * bitmap_scatter() for the bitmap scatter detailed operations). > + * Suppose scattered computed using bitmap_scatter(scattered, src, mask, n). > + * The operation bitmap_gather(result, scattered, mask, n) leads to a result > + * equal or equivalent to src. This paragraph... > + * The result can be 'equivalent' because bitmap_scatter() and bitmap_gather() > + * are not bijective. > + * The result and src values are equivalent in that sense that a call to > + * bitmap_scatter(res, src, mask, n) and a call to bitmap_scatter(res, result, > + * mask, n) will lead to the same res value. ...seems duplicating this one. I would drop the latter one. > + */ -- With Best Regards, Andy Shevchenko
Hi Andy, Yury, On Thu, 22 Feb 2024 17:39:27 +0200 Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote: ... > > + * bitmap_scatter() for the bitmap scatter detailed operations). > > > + * Suppose scattered computed using bitmap_scatter(scattered, src, mask, n). > > + * The operation bitmap_gather(result, scattered, mask, n) leads to a result > > + * equal or equivalent to src. > > This paragraph... > > > + * The result can be 'equivalent' because bitmap_scatter() and bitmap_gather() > > + * are not bijective. > > > > + * The result and src values are equivalent in that sense that a call to > > + * bitmap_scatter(res, src, mask, n) and a call to bitmap_scatter(res, result, > > + * mask, n) will lead to the same res value. > > ...seems duplicating this one. > > I would drop the latter one. I would like to give details about the 'equivalent' in this scatter/gather case. If Yury is ok, I can drop this last paragraph. Thanks for the review, Regards, Hervé
On Thu, Feb 22, 2024 at 05:49:59PM +0100, Herve Codina wrote: > Hi Andy, Yury, > > On Thu, 22 Feb 2024 17:39:27 +0200 > Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote: > > ... > > > + * bitmap_scatter() for the bitmap scatter detailed operations). > > > > > + * Suppose scattered computed using bitmap_scatter(scattered, src, mask, n). > > > + * The operation bitmap_gather(result, scattered, mask, n) leads to a result > > > + * equal or equivalent to src. > > > > This paragraph... > > > > > + * The result can be 'equivalent' because bitmap_scatter() and bitmap_gather() > > > + * are not bijective. > > > > > > > + * The result and src values are equivalent in that sense that a call to > > > + * bitmap_scatter(res, src, mask, n) and a call to bitmap_scatter(res, result, > > > + * mask, n) will lead to the same res value. > > > > ...seems duplicating this one. > > > > I would drop the latter one. > > I would like to give details about the 'equivalent' in this scatter/gather case. If you would like - please do! :) > If Yury is ok, I can drop this last paragraph. The original bitmap_onto() description is 3 times longer, and barely that descriptive. I'm OK with your working and especially pictures. Thanks, Yury
Andy, Yury, On Thu, 22 Feb 2024 13:50:48 -0800 Yury Norov <yury.norov@gmail.com> wrote: > On Thu, Feb 22, 2024 at 05:49:59PM +0100, Herve Codina wrote: > > Hi Andy, Yury, > > > > On Thu, 22 Feb 2024 17:39:27 +0200 > > Andy Shevchenko <andriy.shevchenko@linux.intel.com> wrote: > > > > ... > > > > + * bitmap_scatter() for the bitmap scatter detailed operations). > > > > > > > + * Suppose scattered computed using bitmap_scatter(scattered, src, mask, n). > > > > + * The operation bitmap_gather(result, scattered, mask, n) leads to a result > > > > + * equal or equivalent to src. > > > > > > This paragraph... > > > > > > > + * The result can be 'equivalent' because bitmap_scatter() and bitmap_gather() > > > > + * are not bijective. > > > > > > > > > > + * The result and src values are equivalent in that sense that a call to > > > > + * bitmap_scatter(res, src, mask, n) and a call to bitmap_scatter(res, result, > > > > + * mask, n) will lead to the same res value. > > > > > > ...seems duplicating this one. > > > > > > I would drop the latter one. > > > > I would like to give details about the 'equivalent' in this scatter/gather case. > > If you would like - please do! :) > > > If Yury is ok, I can drop this last paragraph. > > The original bitmap_onto() description is 3 times longer, and barely > that descriptive. I'm OK with your working and especially pictures. > Right, I will keep my last paragraph in the next iteration. Regards, Hervé
On Thu, Feb 22, 2024 at 05:39:27PM +0200, Andy Shevchenko wrote: > On Thu, Feb 22, 2024 at 03:22:16PM +0100, Herve Codina wrote: > > From: Andy Shevchenko <andriy.shevchenko@linux.intel.com> > > The original work was done by Andy Shevchenko. > > Mine SoB is enough for a credit, but thank you :-) That said, you forgot to add your Co-developed-by. -- With Best Regards, Andy Shevchenko
© 2016 - 2026 Red Hat, Inc.