Skip to contentSkip to conversation

bitmap: rework bitmap_{bit,}remap()

PATCH In review Yury Norov 3 participants 18 messages Aug 28, 2023 – Aug 29, 2023

Subsystems (2)
lore
Share & tools
lore

Yury Norov

author maintainer
#0 lore raw

cover bitmap: rework bitmap_{bit,}remap()

This series adds a test, const-time optimizaton and fixes O(N^2) complexity problem for the functions. It's based on discussion in
bitmap: optimize bitmap_remap() series [1], but there's much more work here, so I decided to give it a separete run, and don't name it as v2.

bitmap_remap() API has just one user in generic code, and few more in drivers, so this may look like an overkill. But the work gives ~10x better performance for a 1000-bit bitmaps, which is typical for nodemasks in major distros like Ubuntu.

Anyways, the work is done, so guys please review.

[1] https://lore.kernel.org/lkml/[email protected]/T/
Yury Norov (12):
bitmap: add find_nth_bit_from()
bitmap: add bitmap_weight_from()
bitmap: add test for bitmap_remap()
bitmap: add test for bitmap_bitremap()
bitmap: update comment for bitmap_{bit,}remap()
bitmap: add small_cont_nbits() optimization for bitmap_remap()
bitmap: add small_const_nbits() optimization for bitmap_bitremap()
bitmap: optiimze bitmap_bitremap()
bitmap: optimize bitmap_remap() when 'new' is empty map
bitmap: separate handling of identity and remapping parts in
bitmap_remap()
bitmap: defer calculating weight of 'new' in bitmap_remap()
bitmap: don't count bits from the beginning in bitmap_remap()

 include/linux/bitmap.h | 116 +++++++++++++++++++++++++++++++--
 include/linux/find.h   |  37 +++++++++++
 lib/bitmap.c           | 145 ++++++++++++++++++++---------------------
 lib/find_bit.c         |  29 +++++++++
 lib/test_bitmap.c      | 142 +++++++++++++++++++++++++++++++++++++++-
 5 files changed, 388 insertions(+), 81 deletions(-)
Signature · 1 line
2.39.2
author maintainer
#1 lore raw

PATCH 1/12 bitmap: add find_nth_bit_from()

Similarly to find_next_bit(), add a _from flavor for find_nth_bit(). It's useful when traversing bitmaps in a loop because it allows to not count bits from the beginning every time.

The test is added as well.

---
 include/linux/find.h | 37 +++++++++++++++++++++++++++++++++++++
 lib/find_bit.c       | 29 +++++++++++++++++++++++++++++
 lib/test_bitmap.c    | 10 +++++++++-
 3 files changed, 75 insertions(+), 1 deletion(-)
include/linux/find.h +37 -0
index 5e4f39ef2e72..f7fb88405201 100644
@@ -27,6 +27,8 @@ unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned l
 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
 					const unsigned long *addr3, unsigned long size,
 					unsigned long n);
+unsigned long __find_nth_bit_from(const unsigned long *addr, unsigned long size,
+					unsigned long start, unsigned long nth);
 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
 					 const unsigned long *addr2, unsigned long size);
 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
@@ -237,6 +239,41 @@ unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsign
 	return __find_nth_bit(addr, size, n);
 }
 
+/**
+ * find_nth_bit_from - find N'th set bit in a memory region starting at @off
+ * @addr: The address to start the search at
+ * @size: The maximum number of bits to search
+ * @off: The offset to start search
+ * @n: The number of set bit, which position is needed, counting from 0
+ *
+ * The following is semantically equivalent:
+ *	 idx = find_nth_bit_from(addr, size, off, 0);
+ *	 idx = find_next_bit(addr, size, off);
+ *
+ * Return: the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static __always_inline
+unsigned long find_nth_bit_from(const unsigned long *addr, unsigned long size,
+				unsigned long start, unsigned long n)
+{
+	if (n >= size - start)
+		return size;
+
+	if (small_const_nbits(size - start) && size / BITS_PER_LONG == start / BITS_PER_LONG) {
+		unsigned long val, idx = start / BITS_PER_LONG;
+
+		val =  addr[idx] & GENMASK(size - 1, start);
+		if (val == 0)
+			return size;
+
+		val = idx * BITS_PER_LONG + fns(val, n);
+		return val < size ? val : size;
+	}
+
+	return __find_nth_bit_from(addr, size, start, n);
+}
+
 /**
  * find_nth_and_bit - find N'th set bit in 2 memory regions
  * @addr1: The 1st address to start the search at
lib/find_bit.c +29 -0
index 32f99e9a670e..49959b51df8c 100644
@@ -164,6 +164,35 @@ unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
 }
 EXPORT_SYMBOL(__find_nth_and_andnot_bit);
 
+#define FIND_NTH_BIT_FROM(FETCH, size, start, nth)				\
+({										\
+	unsigned long mask, idx, tmp, w, sz = (size), __start = (start), n = (nth);\
+										\
+	if (unlikely(__start >= sz || n > sz - __start))			\
+		goto out;							\
+										\
+	mask = BITMAP_FIRST_WORD_MASK(__start);					\
+	idx = __start / BITS_PER_LONG;						\
+										\
+	for (tmp = (FETCH) & mask; (w = hweight_long(tmp)) <= n; tmp = (FETCH)) {\
+		if ((idx + 1) * BITS_PER_LONG >= sz)				\
+			goto out;						\
+		idx++;								\
+		n -= w;								\
+	}									\
+										\
+	sz = min(idx * BITS_PER_LONG + fns(tmp, n), sz);			\
+out:										\
+	sz;									\
+})
+
+unsigned long __find_nth_bit_from(const unsigned long *addr, unsigned long size,
+					unsigned long start, unsigned long nth)
+{
+	return FIND_NTH_BIT_FROM(addr[idx], size, start, nth);
+}
+EXPORT_SYMBOL(__find_nth_bit_from);
+
 #ifndef find_next_and_bit
 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
 					unsigned long nbits, unsigned long start)
lib/test_bitmap.c +9 -1
index def7d2f9bd14..3248ed58a817 100644
@@ -223,7 +223,7 @@ static void __init test_zero_clear(void)
 
 static void __init test_find_nth_bit(void)
 {
-	unsigned long b, bit, cnt = 0;
+	unsigned long i, b, bit, cnt = 0;
 	DECLARE_BITMAP(bmap, 64 * 3);
 
 	bitmap_zero(bmap, 64 * 3);
@@ -260,6 +260,14 @@ static void __init test_find_nth_bit(void)
 		b = find_nth_bit(exp1, EXP1_IN_BITS, cnt++);
 		expect_eq_uint(b, bit);
 	}
+
+	for (i = 0; i < EXP1_IN_BITS; i++) {
+		bit = i; cnt = 0;
+		for_each_set_bit_from(bit, exp1, EXP1_IN_BITS) {
+			b = find_nth_bit_from(exp1, EXP1_IN_BITS, i, cnt++);
+			expect_eq_uint(b, bit);
+		}
+	}
 }
 
 static void __init test_fill_set(void)
Signature · 1 line
2.39.2
author maintainer
#2 lore raw

PATCH 2/12 bitmap: add bitmap_weight_from()

In reply to Yury Norov

Add a _from flavor for bitmap_weight(). It's useful when traversing bitmaps in a loop to not count bits from the beginning every time.

The test for bitmap_weight{,_from}() is added as well.

---
 include/linux/bitmap.h | 14 ++++++++++++++
 lib/bitmap.c           | 25 +++++++++++++++++++++++++
 lib/test_bitmap.c      | 18 ++++++++++++++++++
 3 files changed, 57 insertions(+)
include/linux/bitmap.h +14 -0
index 692d0a1dbe92..6acbdd2abd0c 100644
@@ -168,6 +168,8 @@ bool __bitmap_subset(const unsigned long *bitmap1,
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
 unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 				 const unsigned long *bitmap2, unsigned int nbits);
+unsigned int __bitmap_weight_from(const unsigned long *bitmap,
+					unsigned int bits, unsigned int start);
 void __bitmap_set(unsigned long *map, unsigned int start, int len);
 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
 
@@ -446,6 +448,18 @@ unsigned long bitmap_weight_and(const unsigned long *src1,
 	return __bitmap_weight_and(src1, src2, nbits);
 }
 
+static __always_inline
+unsigned int bitmap_weight_from(const unsigned long *src, unsigned int nbits, unsigned int start)
+{
+	if (unlikely(start >= nbits))
+		return 0;
+
+	if (small_const_nbits(nbits - start) && nbits / BITS_PER_LONG == start / BITS_PER_LONG)
+		return hweight_long(*src & GENMASK(nbits-1, start));
+
+	return __bitmap_weight_from(src, nbits, start);
+}
+
 static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
 		unsigned int nbits)
 {
lib/bitmap.c +25 -0
index cf77d56cf223..65c64911c92f 100644
@@ -345,6 +345,24 @@ EXPORT_SYMBOL(__bitmap_subset);
 	w;									\
 })
 
+#define BITMAP_WEIGHT_FROM(FETCH, bits, start)					\
+({										\
+	unsigned long __bits = (bits), val, idx, w = 0, __start = (start), mask;\
+										\
+	mask = BITMAP_FIRST_WORD_MASK(__start);					\
+	idx = __start / BITS_PER_LONG;						\
+										\
+	for (val = (FETCH) & mask; idx < __bits / BITS_PER_LONG; val = (FETCH))	{\
+		w += hweight_long(val);						\
+		idx++;								\
+	}									\
+										\
+	if (__bits % BITS_PER_LONG)						\
+		w += hweight_long((val) & BITMAP_LAST_WORD_MASK(__bits));	\
+										\
+	w;									\
+})
+
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 {
 	return BITMAP_WEIGHT(bitmap[idx], bits);
@@ -358,6 +376,13 @@ unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 }
 EXPORT_SYMBOL(__bitmap_weight_and);
 
+unsigned int __bitmap_weight_from(const unsigned long *bitmap,
+					unsigned int bits, unsigned int start)
+{
+	return BITMAP_WEIGHT_FROM(bitmap[idx], bits, start);
+}
+EXPORT_SYMBOL(__bitmap_weight_from);
+
 void __bitmap_set(unsigned long *map, unsigned int start, int len)
 {
 	unsigned long *p = map + BIT_WORD(start);
lib/test_bitmap.c +18 -0
index 3248ed58a817..a5d823f7589d 100644
@@ -361,6 +361,23 @@ static void __init test_bitmap_region(void)
 	expect_eq_uint(bitmap_weight(bmap, 1000), 0);
 }
 
+static void __init test_weight(void)
+{
+	DECLARE_BITMAP(bmap, 1024);
+	unsigned int idx, w;
+
+	for (idx = 0; idx < 1024; idx++)
+		__assign_bit(idx, bmap, idx);
+
+	w = bitmap_weight(bmap, 1024);
+	for (idx = 0; idx < 1024; idx++) {
+		unsigned int w1 = bitmap_weight(bmap, idx);
+		unsigned int w2 = bitmap_weight_from(bmap, 1024, idx);
+
+		expect_eq_uint(w1 + w2, w);
+	}
+}
+
 #define EXP2_IN_BITS	(sizeof(exp2) * 8)
 
 static void __init test_replace(void)
@@ -1260,6 +1277,7 @@ static void __init selftest(void)
 	test_copy();
 	test_bitmap_region();
 	test_replace();
+	test_weight();
 	test_bitmap_arr32();
 	test_bitmap_arr64();
 	test_bitmap_parse();
Signature · 1 line
2.39.2
#3 lore raw

Re: [PATCH 02/12] bitmap: add bitmap_weight_from()

Quoted 27 lines · Yury Norov

Add a _from flavor for bitmap_weight(). It's useful when traversing bitmaps in a loop to not count bits from the beginning every time.

The test for bitmap_weight{,_from}() is added as well.

---
 include/linux/bitmap.h | 14 ++++++++++++++
 lib/bitmap.c           | 25 +++++++++++++++++++++++++
 lib/test_bitmap.c      | 18 ++++++++++++++++++
 3 files changed, 57 insertions(+)
include/linux/bitmap.h +2 -0
index 692d0a1dbe92..6acbdd2abd0c 100644
@@ -168,6 +168,8 @@ bool __bitmap_subset(const unsigned long *bitmap1,
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
 unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 				 const unsigned long *bitmap2, unsigned int nbits);
+unsigned int __bitmap_weight_from(const unsigned long *bitmap,
+					unsigned int bits, unsigned int start);
 void __bitmap_set(unsigned long *map, unsigned int start, int len);
 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
 
@@ -446,6 +448,18 @@ unsigned long bitmap_weight_and(const unsigned long *src1,
 	return __bitmap_weight_and(src1, src2, nbits);

include/linux/bitmap.h unsigned long bitmap_weight_and(const unsigned long *src1, · line 458

Quoted 10 lines
include/linux/bitmap.h +8 -0
 }
 
+static __always_inline
+unsigned int bitmap_weight_from(const unsigned long *src, unsigned int nbits, unsigned int start)
+{
+	if (unlikely(start >= nbits))
+		return 0;
+
+	if (small_const_nbits(nbits - start) && nbits / BITS_PER_LONG == start / BITS_PER_LONG)
+		return hweight_long(*src & GENMASK(nbits-1, start));

This must be buggy. If I pass compile-time constants nbits==96 and start==64, the whole if() is true, and we call GENMASK with total garbage arguments, and access src[0] and not src[1] as that start-value would suggest.

Don't optimize for irrelevant cases. The expected use of this function must be that start is some runtime thing. So just make the whole if() just test whether nbits is small_const, and if so, I think the hweight_long() line is actually right as-is (though I can never remember GENMASK argument order).

Quoted 9 lines
include/linux/bitmap.h +7 -0
+#define BITMAP_WEIGHT_FROM(FETCH, bits, start)					\
+({										\
+	unsigned long __bits = (bits), val, idx, w = 0, __start = (start), mask;\
+										\
+	mask = BITMAP_FIRST_WORD_MASK(__start);					\
+	idx = __start / BITS_PER_LONG;						\
+										\

include/linux/bitmap.h unsigned long bitmap_weight_and(const unsigned long *src1,

Quoted 10 lines
include/linux/bitmap.h +10 -0
+	for (val = (FETCH) & mask; idx < __bits / BITS_PER_LONG; val = (FETCH))	{\
+		w += hweight_long(val);						\
+		idx++;								\
+	}									\
+										\
+	if (__bits % BITS_PER_LONG)						\
+		w += hweight_long((val) & BITMAP_LAST_WORD_MASK(__bits));	\
+										\
+	w;									\
+})

Why does the entire function body need to be an unholy statement expression?

Rasmus

author maintainer
#4 lore raw

PATCH 3/12 bitmap: add test for bitmap_remap()

In reply to Yury Norov

Basic functional and performance tests for bitmap_remap(). 1000 bits length is chosen for performance test because it's of the same order as default value for MAX_NUMNODES in major distros like Ubuntu (1024).

---
 lib/test_bitmap.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 80 insertions(+)
lib/test_bitmap.c +80 -0
index a5d823f7589d..e1c22d399f24 100644
@@ -378,6 +378,85 @@ static void __init test_weight(void)
 	}
 }
 
+static void __init test_remap(void)
+{
+	DECLARE_BITMAP(dst, 8);
+
+	DECLARE_BITMAP(empty, 8) = { 0 };
+	DECLARE_BITMAP(src, 8) = { 0b00101010 };
+	DECLARE_BITMAP(old, 8) = { 0b00011100 };
+	DECLARE_BITMAP(new, 8) = { 0b00111000 };
+	DECLARE_BITMAP(exp0, 8) = { 0b00110010 };
+	DECLARE_BITMAP(exp1, 8) = { 0b00011010 };
+	DECLARE_BITMAP(exp2, 8) = { 0b10000010 };
+
+	DECLARE_BITMAP(perf_exp, 1000);
+	DECLARE_BITMAP(perf_dst, 1000);
+	DECLARE_BITMAP(perf_src, 1000);
+	DECLARE_BITMAP(perf_old, 1000);
+	DECLARE_BITMAP(perf_new, 1000);
+
+	unsigned int i;
+	ktime_t time;
+
+	bitmap_remap(dst, src, old, new, 8);
+	expect_eq_bitmap(exp0, dst, 8);
+
+	/*
+	 * When old mapping is the same as new, source bits are copied to dst.
+	 * Real code must use bitmap_copy() if it's known in advance.
+	 */
+	bitmap_remap(dst, src, old, old, 8);
+	expect_eq_bitmap(src, dst, 8);
+
+	bitmap_remap(dst, src, new, new, 8);
+	expect_eq_bitmap(src, dst, 8);
+
+	/*
+	 * When either old or new mappings are empty, source bits are copied to
+	 * dst. Real code must use bitmap_copy() if it's known in advance.
+	 */
+	bitmap_remap(dst, src, empty, new, 8);
+	expect_eq_bitmap(src, dst, 8);
+
+	bitmap_remap(dst, src, old, empty, 8);
+	expect_eq_bitmap(src, dst, 8);
+
+	bitmap_remap(dst, src, empty, empty, 8);
+	expect_eq_bitmap(src, dst, 8);
+
+	/* Set extra bit in old map to test carry logic */
+	set_bit(5, old);
+	bitmap_remap(dst, src, old, new, 8);
+	expect_eq_bitmap(exp1, dst, 8);
+
+	/* Map old bits to #7 */
+	bitmap_zero(new, 8);
+	set_bit(7, new);
+	bitmap_remap(dst, src, old, new, 8);
+	expect_eq_bitmap(exp2, dst, 8);
+
+	bitmap_fill(perf_src, 1000);
+	bitmap_set(perf_old, 0, 500);
+	bitmap_clear(perf_old, 500, 500);
+
+	for (i = 0; i < 1000; i += 20) {
+		bitmap_set(perf_new, i, 10);
+		bitmap_clear(perf_new, i + 10, 10);
+	}
+
+	bitmap_copy(perf_exp, perf_new, 500);
+	bitmap_set(perf_exp, 500, 500);
+
+	time = ktime_get();
+	bitmap_remap(perf_dst, perf_src, perf_old, perf_new, 1000);
+	time = ktime_get() - time;
+
+	expect_eq_bitmap(perf_exp, perf_dst, 1000);
+	pr_err("bitmap_remap:  %llu ns\n", time);
+
+}
+
 #define EXP2_IN_BITS	(sizeof(exp2) * 8)
 
 static void __init test_replace(void)
@@ -1278,6 +1357,7 @@ static void __init selftest(void)
 	test_bitmap_region();
 	test_replace();
 	test_weight();
+	test_remap();
 	test_bitmap_arr32();
 	test_bitmap_arr64();
 	test_bitmap_parse();
Signature · 1 line
2.39.2
author maintainer
#5 lore raw

PATCH 4/12 bitmap: add test for bitmap_bitremap()

In reply to Yury Norov

Similarly to bitmap_remap, test bitmap_bitremap().

---
 lib/test_bitmap.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
lib/test_bitmap.c +34 -0
index e1c22d399f24..e9211f9a0e67 100644
@@ -378,6 +378,19 @@ static void __init test_weight(void)
 	}
 }
 
+static __always_inline void __init __test_bitremap(unsigned long *dst, unsigned long *src,
+				unsigned long *old, unsigned long *new, unsigned long nbits)
+{
+	unsigned long oldbit, newbit;
+
+	bitmap_zero(dst, nbits);
+
+	for_each_set_bit(oldbit, src, nbits) {
+		newbit = bitmap_bitremap(oldbit, old, new, nbits);
+		__set_bit(newbit, dst);
+	}
+}
+
 static void __init test_remap(void)
 {
 	DECLARE_BITMAP(dst, 8);
@@ -402,6 +415,9 @@ static void __init test_remap(void)
 	bitmap_remap(dst, src, old, new, 8);
 	expect_eq_bitmap(exp0, dst, 8);
 
+	__test_bitremap(dst, src, old, new, 8);
+	expect_eq_bitmap(exp0, dst, 8);
+
 	/*
 	 * When old mapping is the same as new, source bits are copied to dst.
 	 * Real code must use bitmap_copy() if it's known in advance.
@@ -409,6 +425,9 @@ static void __init test_remap(void)
 	bitmap_remap(dst, src, old, old, 8);
 	expect_eq_bitmap(src, dst, 8);
 
+	__test_bitremap(dst, src, old, old, 8);
+	expect_eq_bitmap(src, dst, 8);
+
 	bitmap_remap(dst, src, new, new, 8);
 	expect_eq_bitmap(src, dst, 8);
 
@@ -419,23 +438,38 @@ static void __init test_remap(void)
 	bitmap_remap(dst, src, empty, new, 8);
 	expect_eq_bitmap(src, dst, 8);
 
+	__test_bitremap(dst, src, empty, new, 8);
+	expect_eq_bitmap(src, dst, 8);
+
 	bitmap_remap(dst, src, old, empty, 8);
 	expect_eq_bitmap(src, dst, 8);
 
+	__test_bitremap(dst, src, old, empty, 8);
+	expect_eq_bitmap(src, dst, 8);
+
 	bitmap_remap(dst, src, empty, empty, 8);
 	expect_eq_bitmap(src, dst, 8);
 
+	__test_bitremap(dst, src, empty, empty, 8);
+	expect_eq_bitmap(src, dst, 8);
+
 	/* Set extra bit in old map to test carry logic */
 	set_bit(5, old);
 	bitmap_remap(dst, src, old, new, 8);
 	expect_eq_bitmap(exp1, dst, 8);
 
+	__test_bitremap(dst, src, old, new, 8);
+	expect_eq_bitmap(exp1, dst, 8);
+
 	/* Map old bits to #7 */
 	bitmap_zero(new, 8);
 	set_bit(7, new);
 	bitmap_remap(dst, src, old, new, 8);
 	expect_eq_bitmap(exp2, dst, 8);
 
+	__test_bitremap(dst, src, old, new, 8);
+	expect_eq_bitmap(exp2, dst, 8);
+
 	bitmap_fill(perf_src, 1000);
 	bitmap_set(perf_old, 0, 500);
 	bitmap_clear(perf_old, 500, 500);
Signature · 1 line
2.39.2
author maintainer
#6 lore raw

PATCH 5/12 bitmap: update comment for bitmap_{bit,}remap()

In reply to Yury Norov

Add an illustrated example for bitmap_remap(), and drop duplicated wording in bitmap_bitremap(). This exact example is tested in lib/test_bitmap.

---
 lib/bitmap.c | 54 +++++++++++++++++++++++++---------------------------
 1 file changed, 26 insertions(+), 28 deletions(-)
lib/bitmap.c +26 -28
index 65c64911c92f..30c375bffe8b 100644
@@ -1002,10 +1002,30 @@ static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigne
  *
  * 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.  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.
+ * 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
@@ -1016,13 +1036,6 @@ static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigne
  *
  * Apply the above specified mapping to @src, placing the result in
  * @dst, clearing any bits previously set in @dst.
- *
- * For example, lets say that @old has bits 4 through 7 set, and
- * @new has bits 12 through 15 set.  This defines the mapping of bit
- * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
- * bit positions unchanged.  So if say @src comes into this routine
- * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
- * 13 and 15 set.
  */
 void bitmap_remap(unsigned long *dst, const unsigned long *src,
 		const unsigned long *old, const unsigned long *new,
@@ -1053,24 +1066,9 @@ EXPORT_SYMBOL(bitmap_remap);
  *	@new: defines range of map
  *	@bits: 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.  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.
- *
- * The positions of unset bits in @old are mapped to themselves
- * (the identity map).
- *
- * Apply the above specified mapping to bit position @oldbit, returning
- * the new bit position.
+ * A special case of bitmap_remap(), when a single bit remapping is needed.
  *
- * For example, lets say that @old has bits 4 through 7 set, and
- * @new has bits 12 through 15 set.  This defines the mapping of bit
- * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
- * bit positions unchanged.  So if say @oldbit is 5, then this routine
- * returns 13.
+ * Returns: position of remapped bit
  */
 int bitmap_bitremap(int oldbit, const unsigned long *old,
 				const unsigned long *new, int bits)
Signature · 1 line
2.39.2
author maintainer
#7 lore raw

PATCH 6/12 bitmap: add small_cont_nbits() optimization for bitmap_remap()

In reply to Yury Norov

When nbits is less than BITS_PER_LONG, we can handle trivial cases inline.

---
 include/linux/bitmap.h | 66 ++++++++++++++++++++++++++++++++++++++++--
 lib/bitmap.c           | 49 ++-----------------------------
 2 files changed, 66 insertions(+), 49 deletions(-)
include/linux/bitmap.h +64 -2
index 6acbdd2abd0c..486451b80339 100644
@@ -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 */
lib/bitmap.c +2 -47

61 lines not on this page · raw message

Signature · 1 line
2.39.2
author maintainer
#8 lore raw

PATCH 7/12 bitmap: add small_const_nbits() optimization for bitmap_bitremap()

In reply to Yury Norov

When 'bits' is less than BITS_PER_LONG, we can remap a bit inline.

---
 include/linux/bitmap.h | 36 ++++++++++++++++++++++++++++++++++--
 lib/bitmap.c           | 15 ++-------------
 2 files changed, 36 insertions(+), 15 deletions(-)
include/linux/bitmap.h +34 -2
index 486451b80339..da5030a99af5 100644
@@ -163,6 +163,8 @@ void __bitmap_replace(unsigned long *dst,
 		      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,
+		const unsigned long *old, const unsigned long *new, int nbits);
 bool __bitmap_intersects(const unsigned long *bitmap1,
 			 const unsigned long *bitmap2, unsigned int nbits);
 bool __bitmap_subset(const unsigned long *bitmap1,
@@ -214,8 +216,6 @@ int bitmap_parselist(const char *buf, unsigned long *maskp,
 int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
 			unsigned long *dst, 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,
 		const unsigned long *relmap, unsigned int bits);
 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
@@ -733,6 +733,38 @@ static inline void bitmap_remap(unsigned long *dst, const unsigned long *src,
 	__bitmap_remap(dst, src, old, new, nbits);
 }
 
+/**
+ * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
+ *	@oldbit: bit position to be mapped
+ *	@old: defines domain of map
+ *	@new: defines range of map
+ *	@nbits: number of bits in each of these bitmaps
+ *
+ * A special case of bitmap_remap(), when a single bit remapping is needed.
+ *
+ * Returns: position of remapped bit
+ */
+static inline int bitmap_bitremap(int oldbit,
+		const unsigned long *old, const unsigned long *new, int nbits)
+{
+	if (small_const_nbits(nbits)) {
+		unsigned int w, n;
+
+		if ((*old & BIT(oldbit)) == 0 ||
+		    (*old & BITMAP_LAST_WORD_MASK(nbits)) == 0 ||
+		    (*new & BITMAP_LAST_WORD_MASK(nbits)) == 0 ||
+		    ((*new ^ *old) & BITMAP_LAST_WORD_MASK(nbits)) == 0) {
+			return oldbit;
+		}
+
+		w = bitmap_weight(new, nbits);
+		n = bitmap_weight(old, oldbit);
+		return find_nth_bit(new, nbits, n % w);
+	}
+
+	return __bitmap_bitremap(oldbit, old, new, nbits);
+}
+
 #endif /* __ASSEMBLY__ */
 
 #endif /* __LINUX_BITMAP_H */
lib/bitmap.c +2 -13
index 2ac48d9bcbc0..9ecdc74cb6b4 100644
@@ -1014,18 +1014,7 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 }
 EXPORT_SYMBOL(__bitmap_remap);
 
-/**
- * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
- *	@oldbit: bit position to be mapped
- *	@old: defines domain of map
- *	@new: defines range of map
- *	@bits: number of bits in each of these bitmaps
- *
- * A special case of bitmap_remap(), when a single bit remapping is needed.
- *
- * Returns: position of remapped bit
- */
-int bitmap_bitremap(int oldbit, const unsigned long *old,
+int __bitmap_bitremap(int oldbit, const unsigned long *old,
 				const unsigned long *new, int bits)
 {
 	int w = bitmap_weight(new, bits);
@@ -1035,7 +1024,7 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
 	else
 		return find_nth_bit(new, bits, n % w);
 }
-EXPORT_SYMBOL(bitmap_bitremap);
+EXPORT_SYMBOL(__bitmap_bitremap);
 
 #ifdef CONFIG_NUMA
 /**
Signature · 1 line
2.39.2
author maintainer
#9 lore raw

PATCH 8/12 bitmap: optiimze bitmap_bitremap()

In reply to Yury Norov

When 'new' map is empty, we can skip remapping entirely and return the old bit.

---
 lib/bitmap.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)
lib/bitmap.c +10 -5
index 9ecdc74cb6b4..2e8deeb8bf99 100644
@@ -1017,12 +1017,17 @@ EXPORT_SYMBOL(__bitmap_remap);
 int __bitmap_bitremap(int oldbit, const unsigned long *old,
 				const unsigned long *new, int bits)
 {
-	int w = bitmap_weight(new, bits);
-	int n = bitmap_pos_to_ord(old, oldbit, bits);
-	if (n < 0 || w == 0)
+	int w, n;
+
+	w = bitmap_weight(new, bits);
+	if (w == 0)
+		return oldbit;
+
+	n = bitmap_pos_to_ord(old, oldbit, bits);
+	if (n < 0)
 		return oldbit;
-	else
-		return find_nth_bit(new, bits, n % w);
+
+	return find_nth_bit(new, bits, n % w);
 }
 EXPORT_SYMBOL(__bitmap_bitremap);
 
Signature · 1 line
2.39.2
author maintainer
#10 lore raw

PATCH 9/12 bitmap: optimize bitmap_remap() when 'new' is empty map

In reply to Yury Norov

When 'new' map is empty, we can skip remapping entirely and replace it with bitmap_copy().

---
 lib/bitmap.c | 5 +++++
 1 file changed, 5 insertions(+)
lib/bitmap.c +5 -0
index 2e8deeb8bf99..50385d61e6ea 100644
@@ -1003,6 +1003,11 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 	bitmap_zero(dst, nbits);
 
 	w = bitmap_weight(new, nbits);
+	if (w == 0) {
+		bitmap_copy(dst, src, nbits);
+		return;
+	}
+
 	for_each_set_bit(oldbit, src, nbits) {
 		int n = bitmap_pos_to_ord(old, oldbit, nbits);
 
Signature · 1 line
2.39.2
author maintainer
#11 lore raw

PATCH 10/12 bitmap: separate handling of identity and remapping parts in bitmap_remap()

In reply to Yury Norov

For unset bits in 'old' map (identity mapping), 'src' bits must be copied to 'dst'. Doing that separately from remapping in a for-loop has some advantages:
- implicitly initialize 'dst' without calling bitmap_zero();
- optimize performance of handling identity parts, because per-word bitmap_andnot() is faster than per-bit set_bit() in a for-loop;
- make inner part of the loop unconditional;
- when 'old' map is empty, new logic simiply skips the for-loop part.

While here, replace set_bit() with a non-atomic version, because the whole function is non-atomic anyways. If atomicity required, it should be handled by user.

---
 lib/bitmap.c | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)
lib/bitmap.c +7 -8
index 50385d61e6ea..f62ea97e942c 100644
@@ -996,11 +996,10 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 		const unsigned long *old, const unsigned long *new,
 		unsigned int nbits)
 {
-	unsigned int oldbit, w;
+	unsigned int oldbit, w, n;
 
 	if (dst == src)		/* following doesn't handle inplace remaps */
 		return;
-	bitmap_zero(dst, nbits);
 
 	w = bitmap_weight(new, nbits);
 	if (w == 0) {
@@ -1008,13 +1007,13 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 		return;
 	}
 
-	for_each_set_bit(oldbit, src, nbits) {
-		int n = bitmap_pos_to_ord(old, oldbit, nbits);
+	/* Identity part */
+	bitmap_andnot(dst, src, old, nbits);
 
-		if (n < 0 || w == 0)
-			set_bit(oldbit, dst);	/* identity map */
-		else
-			set_bit(find_nth_bit(new, nbits, n % w), dst);
+	/* Remapping part */
+	for_each_and_bit(oldbit, src, old, nbits) {
+		n = bitmap_weight(old, oldbit);
+		__set_bit(find_nth_bit(new, nbits, n % w), dst);
 	}
 }
 EXPORT_SYMBOL(__bitmap_remap);
Signature · 1 line
2.39.2
author maintainer
#12 lore raw

PATCH 11/12 bitmap: defer calculating weight of 'new' in bitmap_remap()

In reply to Yury Norov

When 'old' map is empty, we don't need to calculate weight of 'new' map, because all 'src' bits are simply copied to dst.

---
 lib/bitmap.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)
lib/bitmap.c +8 -7
index f62ea97e942c..1fca60d54cb4 100644
@@ -996,23 +996,24 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 		const unsigned long *old, const unsigned long *new,
 		unsigned int nbits)
 {
-	unsigned int oldbit, w, n;
+	unsigned int oldbit, w = 0, n;
 
 	if (dst == src)		/* following doesn't handle inplace remaps */
 		return;
 
-	w = bitmap_weight(new, nbits);
-	if (w == 0) {
-		bitmap_copy(dst, src, nbits);
-		return;
-	}
-
 	/* Identity part */
 	bitmap_andnot(dst, src, old, nbits);
 
 	/* Remapping part */
 	for_each_and_bit(oldbit, src, old, nbits) {
 		n = bitmap_weight(old, oldbit);
+		if (w == 0) { /* if not initialized */
+			w = bitmap_weight(new, nbits);
+			if (w == 0) { /* if empty */
+				bitmap_copy(dst, src, nbits);
+				return;
+			}
+		}
 		__set_bit(find_nth_bit(new, nbits, n % w), dst);
 	}
 }
Signature · 1 line
2.39.2
author maintainer
#13 lore raw

PATCH 12/12 bitmap: don't count bits from the beginning in bitmap_remap()

In reply to Yury Norov

In the remapping part, we count bits in 'old' and 'new' masks from the beginning for every bit. Complexity of this approach is O(N^2). We can do it better in O(N), if switch bitmap_remap() to using _from versions of bitmap_weight() and find_nth_bit().

On kvm/x86_64 it works 9x faster than the current version for the 1000-bit bitmap in lib/test_bitmap. Because popular distros like Ubuntu has 1024-bit nodemasks, ~10x performance improvement is expected where bitmap_remap() is used.

---
 lib/bitmap.c | 22 +++++++++++++++++++---
 1 file changed, 19 insertions(+), 3 deletions(-)
lib/bitmap.c +19 -3
index 1fca60d54cb4..8bca6bcf2bc5 100644
@@ -996,7 +996,8 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 		const unsigned long *old, const unsigned long *new,
 		unsigned int nbits)
 {
-	unsigned int oldbit, w = 0, n;
+	unsigned int newbit, oldbit, w = 0, n;
+	unsigned int _oldbit, _newbit;
 
 	if (dst == src)		/* following doesn't handle inplace remaps */
 		return;
@@ -1005,8 +1006,17 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 	bitmap_andnot(dst, src, old, nbits);
 
 	/* Remapping part */
+	_oldbit = _newbit = 0;
 	for_each_and_bit(oldbit, src, old, nbits) {
-		n = bitmap_weight(old, oldbit);
+		n = bitmap_weight_from(old, oldbit, _oldbit);
+		newbit = find_nth_bit_from(new, nbits, _newbit, n);
+		if (newbit < nbits)
+			goto set_bit;
+
+		/*
+		 * If we're out of bits in 'new' map, wrap
+		 * around and start from the beginning.
+		 */
 		if (w == 0) { /* if not initialized */
 			w = bitmap_weight(new, nbits);
 			if (w == 0) { /* if empty */
@@ -1014,7 +1024,13 @@ void __bitmap_remap(unsigned long *dst, const unsigned long *src,
 				return;
 			}
 		}
-		__set_bit(find_nth_bit(new, nbits, n % w), dst);
+
+		n -= bitmap_weight_from(new, nbits, _newbit);
+		newbit = find_nth_bit(new, nbits, n % w);
+set_bit:
+		__set_bit(newbit, dst);
+		_oldbit = oldbit;
+		_newbit = newbit;
 	}
 }
 EXPORT_SYMBOL(__bitmap_remap);
Signature · 1 line
2.39.2
#14 lore raw
In reply to Yury Norov
Quoted 9 lines · Yury Norov

This series adds a test, const-time optimizaton and fixes O(N^2) complexity problem for the functions. It's based on discussion in
bitmap: optimize bitmap_remap() series [1], but there's much more work here, so I decided to give it a separete run, and don't name it as v2.

bitmap_remap() API has just one user in generic code, and few more in drivers, so this may look like an overkill. But the work gives ~10x better performance for a 1000-bit bitmaps, which is typical for nodemasks in major distros like Ubuntu.

Can you find just _one_ project on Debian Code Search or elsewhere that actually uses mbind(2), that could possibly ever trigger the use of that bitmap_remap stuff? Also, the bitmap may be order 10, but that's just because the kitchen sink distros are silly, real machines have nowhere near that number of nodes, so even if mbind is used, the bitmaps involved will never actually have anything beyond index ~64.

I think this is all total overkill for non-existing problems, and when it takes me 20 seconds to find the first bug, I really don't think it's worth the churn. I'm not giving a thorough review on the rest of the series, nor commenting on followups.

Rasmus

#15 lore raw
Quoted 18 lines · Rasmus Villemoes
Quoted 9 lines · Yury Norov

This series adds a test, const-time optimizaton and fixes O(N^2) complexity problem for the functions. It's based on discussion in
bitmap: optimize bitmap_remap() series [1], but there's much more work here, so I decided to give it a separete run, and don't name it as v2.

bitmap_remap() API has just one user in generic code, and few more in drivers, so this may look like an overkill. But the work gives ~10x better performance for a 1000-bit bitmaps, which is typical for nodemasks in major distros like Ubuntu.

Can you find just _one_ project on Debian Code Search or elsewhere that actually uses mbind(2), that could possibly ever trigger the use of that bitmap_remap stuff? Also, the bitmap may be order 10, but that's just because the kitchen sink distros are silly, real machines have nowhere near that number of nodes, so even if mbind is used, the bitmaps involved will never actually have anything beyond index ~64.

Quoted 4 lines

I think this is all total overkill for non-existing problems, and when it takes me 20 seconds to find the first bug, I really don't think it's worth the churn. I'm not giving a thorough review on the rest of the series, nor commenting on followups.

I posted one patch to replace these APIs with something else, more particular for GPIO case(s). Have you chance to look at that? With that taking in, I'm fully agree on the above statement (as we lose the user of this complicated thingy which is a niche of the NUMA as you mentioned already).

Signature · 2 lines
With Best Regards,
Andy Shevchenko
author maintainer
#16 lore raw
Quoted 25 lines · Andy Shevchenko
Quoted 18 lines · Rasmus Villemoes
Quoted 9 lines · Yury Norov

This series adds a test, const-time optimizaton and fixes O(N^2) complexity problem for the functions. It's based on discussion in
bitmap: optimize bitmap_remap() series [1], but there's much more work here, so I decided to give it a separete run, and don't name it as v2.

bitmap_remap() API has just one user in generic code, and few more in drivers, so this may look like an overkill. But the work gives ~10x better performance for a 1000-bit bitmaps, which is typical for nodemasks in major distros like Ubuntu.

Can you find just _one_ project on Debian Code Search or elsewhere that actually uses mbind(2), that could possibly ever trigger the use of that bitmap_remap stuff? Also, the bitmap may be order 10, but that's just because the kitchen sink distros are silly, real machines have nowhere near that number of nodes, so even if mbind is used, the bitmaps involved will never actually have anything beyond index ~64.

Quoted 4 lines

I think this is all total overkill for non-existing problems, and when it takes me 20 seconds to find the first bug, I really don't think it's worth the churn. I'm not giving a thorough review on the rest of the series, nor commenting on followups.

Quoted 4 lines

I posted one patch to replace these APIs with something else, more particular for GPIO case(s). Have you chance to look at that? With that taking in, I'm fully agree on the above statement (as we lose the user of this complicated thingy which is a niche of the NUMA as you mentioned already).

I saw the code in a comment in some thread but not as a separate patch, and AFAIK you said it's a work-in-progress.

Sorry if I missed your submission. Can you please send the patch or point me to the previous submission?

Also, if after your change bitmap_remap would become a NUMA-specific, should protect it with NUMA guards?

Thanks,
Yury

#17 lore raw
Quoted 3 lines · Yury Norov
Quoted 1 line · Andy Shevchenko

On Tue, Aug 29, 2023 at 09:33:29AM +0200, Rasmus Villemoes wrote:

...

Quoted 7 lines
Quoted 4 lines

I posted one patch to replace these APIs with something else, more particular for GPIO case(s). Have you chance to look at that? With that taking in, I'm fully agree on the above statement (as we lose the user of this complicated thingy which is a niche of the NUMA as you mentioned already).

I saw the code in a comment in some thread but not as a separate patch, and AFAIK you said it's a work-in-progress.

The patch itself is self-contained, the only problem it has no users as is. The work-in-progress for the test cases, but before I continue with that I want to hear if it's accepted approach.

Quoted 5 lines

Sorry if I missed your submission. Can you please send the patch or point me to the previous submission?

Also, if after your change bitmap_remap would become a NUMA-specific, should protect it with NUMA guards?

Rasmus' idea was to move that completely out of the bitmap namespace and scope.

Signature · 2 lines
With Best Regards,
Andy Shevchenko