| 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: <20230926052007.3917389-3-andriy.shevchenko@linux.intel.com>
Date: Tue, 26 Sep 2023 08:20:04 +0300
From: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
Linus Walleij <linus.walleij@...aro.org>,
Bartosz Golaszewski <bartosz.golaszewski@...aro.org>,
Yury Norov <yury.norov@...il.com>, linux-gpio@...r.kernel.org,
linux-arm-kernel@...ts.infradead.org, linux-kernel@...r.kernel.org
Cc: Shubhrajyoti Datta <shubhrajyoti.datta@....com>,
Srinivas Neeli <srinivas.neeli@....com>,
Michal Simek <michal.simek@....com>,
Bartosz Golaszewski <brgl@...ev.pl>,
Andy Shevchenko <andy@...nel.org>,
Rasmus Villemoes <linux@...musvillemoes.dk>,
Marek Behún <kabel@...nel.org>
Subject: [PATCH v1 2/5] lib/bitmap: Introduce bitmap_scatter() and bitmap_gather() helpers
These helpers are the optimized versions of the bitmap_remap()
where one of the bitmaps (source or destination) is of sequential bits.
See more in the kernel documentation of the helpers.
Signed-off-by: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
---
include/linux/bitmap.h | 9 ++++++
lib/bitmap.c | 70 ++++++++++++++++++++++++++++++++++++++++++
lib/test_bitmap.c | 23 ++++++++++++++
3 files changed, 102 insertions(+)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 1516ff979315..87013b9a7dd8 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -60,6 +60,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
@@ -208,6 +210,12 @@ int bitmap_parselist(const char *buf, unsigned long *maskp,
int nmaskbits);
int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
unsigned long *dst, int nbits);
+
+unsigned int bitmap_scatter(unsigned long *dst, const unsigned long *src,
+ const unsigned long *mask, unsigned int nbits);
+unsigned int bitmap_gather(unsigned long *dst, const unsigned long *src,
+ const unsigned long *mask, unsigned int nbits);
+
void bitmap_remap(unsigned long *dst, const unsigned long *src,
const unsigned long *old, const unsigned long *new, unsigned int nbits);
int bitmap_bitremap(int oldbit,
@@ -216,6 +224,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
const unsigned long *relmap, unsigned int bits);
void bitmap_fold(unsigned long *dst, const unsigned long *orig,
unsigned int sz, unsigned int nbits);
+
int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 935e0f96e785..31cfc7846aae 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -942,6 +942,76 @@ int bitmap_parse(const char *start, unsigned int buflen,
}
EXPORT_SYMBOL(bitmap_parse);
+/**
+ * bitmap_scatter - Scatter a bitmap according to the given mask
+ * @dst: scattered bitmap
+ * @src: gathered bitmap
+ * @mask: 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)
+ *
+ * Returns: the weight of the @mask.
+ */
+unsigned int bitmap_scatter(unsigned long *dst, const unsigned long *src,
+ const unsigned long *mask, unsigned int nbits)
+{
+ unsigned int bit;
+ int n = 0;
+
+ bitmap_zero(dst, nbits);
+
+ for_each_set_bit(bit, mask, nbits)
+ __assign_bit(bit, dst, test_bit(n++, src));
+
+ return n;
+}
+EXPORT_SYMBOL(bitmap_scatter);
+
+/**
+ * bitmap_gather - Gather a bitmap according to given mask
+ * @dst: gathered bitmap
+ * @src: scattered bitmap
+ * @mask: 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)
+ *
+ * Returns: the weight of the @mask.
+ */
+unsigned int bitmap_gather(unsigned long *dst, const unsigned long *src,
+ const unsigned long *mask, unsigned int nbits)
+{
+ unsigned int bit;
+ int n = 0;
+
+ bitmap_zero(dst, nbits);
+
+ for_each_set_bit(bit, mask, nbits)
+ __assign_bit(n++, dst, test_bit(bit, src));
+
+ return n;
+}
+EXPORT_SYMBOL(bitmap_gather);
+
/**
* bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
* @buf: pointer to a bitmap
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 1f2dc7fef17f..f43a07679998 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -50,6 +50,9 @@ static const unsigned long exp2[] __initconst = {
static const unsigned long exp2_to_exp3_mask[] __initconst = {
BITMAP_FROM_U64(0x008000020020212eULL),
};
+static const unsigned long exp2_to_exp3_maskg[] __initconst = {
+ BITMAP_FROM_U64(0x00000000000001ffULL),
+};
/* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */
static const unsigned long exp3_0_1[] __initconst = {
BITMAP_FROM_U64(0x33b3333311313137ULL),
@@ -357,6 +360,25 @@ static void __init test_replace(void)
expect_eq_bitmap(bmap, exp3_1_0, nbits);
}
+static void __init test_bitmap_sg(void)
+{
+ unsigned int nbits = 64;
+ DECLARE_BITMAP(bmap, 1024);
+ unsigned int w;
+
+ bitmap_zero(bmap, 1024);
+ w = bitmap_gather(bmap, exp2_to_exp3_mask, exp2_to_exp3_mask, nbits);
+ expect_eq_uint(bitmap_weight(exp2_to_exp3_mask, nbits), w);
+ expect_eq_uint(bitmap_weight(bmap, 1024), w);
+ expect_eq_bitmap(bmap, exp2_to_exp3_maskg, nbits);
+
+ bitmap_zero(bmap, 1024);
+ w = bitmap_scatter(bmap, exp2_to_exp3_maskg, exp2_to_exp3_mask, nbits);
+ expect_eq_uint(bitmap_weight(exp2_to_exp3_maskg, nbits), w);
+ expect_eq_uint(bitmap_weight(bmap, 1024), w);
+ expect_eq_bitmap(bmap, exp2_to_exp3_mask, nbits);
+}
+
#define PARSE_TIME 0x1
#define NO_LEN 0x2
@@ -1228,6 +1250,7 @@ static void __init selftest(void)
test_fill_set();
test_copy();
test_replace();
+ test_bitmap_sg();
test_bitmap_arr32();
test_bitmap_arr64();
test_bitmap_parse();
--
2.40.0.1.gaa8946217a0b
Powered by blists - more mailing lists