| 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: <20230828184353.5145-7-yury.norov@gmail.com>
Date: Mon, 28 Aug 2023 11:43:46 -0700
From: Yury Norov <yury.norov@...il.com>
To: linux-kernel@...r.kernel.org
Cc: Yury Norov <yury.norov@...il.com>,
Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
Rasmus Villemoes <linux@...musvillemoes.dk>
Subject: [PATCH 06/12] bitmap: add small_cont_nbits() optimization for bitmap_remap()
When nbits is less than BITS_PER_LONG, we can handle trivial cases
inline.
Signed-off-by: Yury Norov <yury.norov@...il.com>
---
include/linux/bitmap.h | 66 ++++++++++++++++++++++++++++++++++++++++--
lib/bitmap.c | 49 ++-----------------------------
2 files changed, 66 insertions(+), 49 deletions(-)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 6acbdd2abd0c..486451b80339 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -161,6 +161,8 @@ bool __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
void __bitmap_replace(unsigned long *dst,
const unsigned long *old, const unsigned long *new,
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);
bool __bitmap_intersects(const unsigned long *bitmap1,
const unsigned long *bitmap2, unsigned int nbits);
bool __bitmap_subset(const unsigned long *bitmap1,
@@ -211,8 +213,7 @@ 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);
-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,
const unsigned long *old, const unsigned long *new, int bits);
void bitmap_onto(unsigned long *dst, const unsigned long *orig,
@@ -671,6 +672,67 @@ static inline int bitmap_find_free_region(unsigned long *bitmap, unsigned int bi
return -ENOMEM;
}
+/**
+ * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
+ * @dst: remapped result
+ * @src: subset to be remapped
+ * @old: defines domain of map
+ * @new: defines range of map
+ * @nbits: number of bits in each of these bitmaps
+ *
+ * Let @old and @new define a mapping of bit positions, such that
+ * whatever position is held by the n-th set bit in @old is mapped
+ * to the n-th set bit in @new. For example lets say that @old has
+ * bits 2 through 4 set, and @new has bits 3 through 5 set:
+ *
+ * old: 00011100
+ * |||///||
+ * new: 00111000
+ *
+ * This defines the mapping of bit position 2 to 3, 3 to 4 and 4 to 5,
+ * and of all other bit positions unchanged. So if say @src comes into
+ * this routine with bits 1, 3 and 5 set, then @dst should leave with
+ * bits 1, 4 and 5 set:
+ *
+ * src: 00101010
+ * v v v
+ * old: 00011100
+ * |||///||
+ * new: 00111000
+ * vv v
+ * dst: 00110010
+ *
+ * In the more general case, allowing for the possibility that the weight
+ * 'w' of @new is less than the weight of @old, map the position of the
+ * n-th set bit in @old to the position of the m-th set bit in @new, where
+ * m == n % w.
+ *
+ * If either of the @old and @new bitmaps are empty, or if @src and
+ * @dst point to the same location, then this routine copies @src
+ * to @dst.
+ *
+ * The positions of unset bits in @old are mapped to themselves
+ * (the identity map).
+ *
+ * Apply the above specified mapping to @src, placing the result in
+ * @dst, clearing any bits previously set in @dst.
+ */
+static inline void bitmap_remap(unsigned long *dst, const unsigned long *src,
+ const unsigned long *old, const unsigned long *new, unsigned int nbits)
+{
+ if (small_const_nbits(nbits)) {
+ if ((*src & BITMAP_LAST_WORD_MASK(nbits)) == 0 ||
+ (*old & BITMAP_LAST_WORD_MASK(nbits)) == 0 ||
+ (*new & BITMAP_LAST_WORD_MASK(nbits)) == 0 ||
+ ((*new ^ *old) & BITMAP_LAST_WORD_MASK(nbits)) == 0) {
+ *dst = *src & BITMAP_LAST_WORD_MASK(nbits);
+ return;
+ }
+ }
+
+ __bitmap_remap(dst, src, old, new, nbits);
+}
+
#endif /* __ASSEMBLY__ */
#endif /* __LINUX_BITMAP_H */
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 30c375bffe8b..2ac48d9bcbc0 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -992,52 +992,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigne
return bitmap_weight(buf, pos);
}
-/**
- * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
- * @dst: remapped result
- * @src: subset to be remapped
- * @old: defines domain of map
- * @new: defines range of map
- * @nbits: number of bits in each of these bitmaps
- *
- * Let @old and @new define a mapping of bit positions, such that
- * whatever position is held by the n-th set bit in @old is mapped
- * to the n-th set bit in @new. For example lets say that @old has
- * bits 2 through 4 set, and @new has bits 3 through 5 set:
- *
- * old: 00011100
- * |||///||
- * new: 00111000
- *
- * This defines the mapping of bit position 2 to 3, 3 to 4 and 4 to 5,
- * and of all other bit positions unchanged. So if say @src comes into
- * this routine with bits 1, 3 and 5 set, then @dst should leave with
- * bits 1, 4 and 5 set:
- *
- * src: 00101010
- * v v v
- * old: 00011100
- * |||///||
- * new: 00111000
- * vv v
- * dst: 00110010
- *
- * In the more general case, allowing for the possibility that the weight
- * 'w' of @new is less than the weight of @old, map the position of the
- * n-th set bit in @old to the position of the m-th set bit in @new, where
- * m == n % w.
- *
- * If either of the @old and @new bitmaps are empty, or if @src and
- * @dst point to the same location, then this routine copies @src
- * to @dst.
- *
- * The positions of unset bits in @old are mapped to themselves
- * (the identity map).
- *
- * Apply the above specified mapping to @src, placing the result in
- * @dst, clearing any bits previously set in @dst.
- */
-void bitmap_remap(unsigned long *dst, const unsigned long *src,
+void __bitmap_remap(unsigned long *dst, const unsigned long *src,
const unsigned long *old, const unsigned long *new,
unsigned int nbits)
{
@@ -1057,7 +1012,7 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
set_bit(find_nth_bit(new, nbits, n % w), dst);
}
}
-EXPORT_SYMBOL(bitmap_remap);
+EXPORT_SYMBOL(__bitmap_remap);
/**
* bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
--
2.39.2
Powered by blists - more mailing lists