[PATCH 0/6] bitmap: cleanup bitmap_*_region() implementation

[PATCH 0/6] bitmap: cleanup bitmap_*_region() implementation

[Yury Norov]

bitmap_{allocate,find_free,release}_region() functions are implemented
on top of _reg_op() machinery. It duplicates existing generic functionality
with no benefits. In fact, generic alternatives may work even better
because they optimized for small_const_nbits() case and overall very well
optimized for performance and code generation.

This series drops _reg_op() entirely.

Yury Norov (6):
  bitmap: fix opencoded bitmap_allocate_region()
  bitmap: replace _reg_op(REG_OP_ALLOC) with bitmap_set()
  bitmap: replace _reg_op(REG_OP_RELEASE) with bitmap_clear()
  bitmap: replace _reg_op(REG_OP_ISFREE) with find_next_bit()
  bitmap: drop _reg_op()
  bitmap: move functions

 include/linux/bitmap.h |  65 ++++++++++++++++++-
 lib/bitmap.c           | 140 -----------------------------------------
 2 files changed, 62 insertions(+), 143 deletions(-)

-- 
2.39.2

[PATCH 1/6] bitmap: fix opencoded bitmap_allocate_region()

[Yury Norov]

bitmap_find_region() opencodes bitmap_allocate_region(). Fix it.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/bitmap.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index ddb31015e38a..0bed9d943d96 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1314,12 +1314,10 @@ int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
 {
 	unsigned int pos, end;		/* scans bitmap by regions of size order */
 
-	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
-		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
-			continue;
-		__reg_op(bitmap, pos, order, REG_OP_ALLOC);
-		return pos;
-	}
+	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end)
+		if (!bitmap_allocate_region(bitmap, pos, order))
+			return pos;
+
 	return -ENOMEM;
 }
 EXPORT_SYMBOL(bitmap_find_free_region);
-- 
2.39.2

[PATCH 2/6] bitmap: replace _reg_op(REG_OP_ALLOC) with bitmap_set()

[Yury Norov]

_reg_op(REG_OP_ALLOC) duplicates bitmap_set(). Drop it.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/bitmap.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 0bed9d943d96..346b848170e4 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1352,9 +1352,12 @@ EXPORT_SYMBOL(bitmap_release_region);
  */
 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
 {
+	unsigned int nbits = pos + BIT(order);
+
 	if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 		return -EBUSY;
-	return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
+	bitmap_set(bitmap, pos, nbits);
+	return 0;
 }
 EXPORT_SYMBOL(bitmap_allocate_region);
 
-- 
2.39.2

[PATCH 3/6] bitmap: replace _reg_op(REG_OP_RELEASE) with bitmap_clear()

[Yury Norov]

_reg_op(REG_OP_RELEASE) duplicates bitmap_clear(). Drop it.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/bitmap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 346b848170e4..9be083ad71bf 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1335,7 +1335,7 @@ EXPORT_SYMBOL(bitmap_find_free_region);
  */
 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
 {
-	__reg_op(bitmap, pos, order, REG_OP_RELEASE);
+	bitmap_clear(bitmap, pos, pos + BIT(order));
 }
 EXPORT_SYMBOL(bitmap_release_region);
 
-- 
2.39.2

[PATCH 4/6] bitmap: replace _reg_op(REG_OP_ISFREE) with find_next_bit()

[Yury Norov]

_reg_op(REG_OP_ISFREE) can be trivially replaced with find_next_bit().
Drop it.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/bitmap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 9be083ad71bf..e0c3bba79181 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1354,7 +1354,7 @@ int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
 {
 	unsigned int nbits = pos + BIT(order);
 
-	if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
+	if (find_next_bit(bitmap, pos, nbits) < nbits)
 		return -EBUSY;
 	bitmap_set(bitmap, pos, nbits);
 	return 0;
-- 
2.39.2

[PATCH 5/6] bitmap: drop _reg_op() function

[Yury Norov]

Now that all _reg_op() users are switched alternative functions, _reg_op()
machinery is not needed anymore.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/bitmap.c | 76 ----------------------------------------------------
 1 file changed, 76 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index e0c3bba79181..7cfe0b442c73 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1220,82 +1220,6 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
 }
 #endif /* CONFIG_NUMA */
 
-/*
- * Common code for bitmap_*_region() routines.
- *	bitmap: array of unsigned longs corresponding to the bitmap
- *	pos: the beginning of the region
- *	order: region size (log base 2 of number of bits)
- *	reg_op: operation(s) to perform on that region of bitmap
- *
- * Can set, verify and/or release a region of bits in a bitmap,
- * depending on which combination of REG_OP_* flag bits is set.
- *
- * A region of a bitmap is a sequence of bits in the bitmap, of
- * some size '1 << order' (a power of two), aligned to that same
- * '1 << order' power of two.
- *
- * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
- * Returns 0 in all other cases and reg_ops.
- */
-
-enum {
-	REG_OP_ISFREE,		/* true if region is all zero bits */
-	REG_OP_ALLOC,		/* set all bits in region */
-	REG_OP_RELEASE,		/* clear all bits in region */
-};
-
-static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
-{
-	int nbits_reg;		/* number of bits in region */
-	int index;		/* index first long of region in bitmap */
-	int offset;		/* bit offset region in bitmap[index] */
-	int nlongs_reg;		/* num longs spanned by region in bitmap */
-	int nbitsinlong;	/* num bits of region in each spanned long */
-	unsigned long mask;	/* bitmask for one long of region */
-	int i;			/* scans bitmap by longs */
-	int ret = 0;		/* return value */
-
-	/*
-	 * Either nlongs_reg == 1 (for small orders that fit in one long)
-	 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
-	 */
-	nbits_reg = 1 << order;
-	index = pos / BITS_PER_LONG;
-	offset = pos - (index * BITS_PER_LONG);
-	nlongs_reg = BITS_TO_LONGS(nbits_reg);
-	nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
-
-	/*
-	 * Can't do "mask = (1UL << nbitsinlong) - 1", as that
-	 * overflows if nbitsinlong == BITS_PER_LONG.
-	 */
-	mask = (1UL << (nbitsinlong - 1));
-	mask += mask - 1;
-	mask <<= offset;
-
-	switch (reg_op) {
-	case REG_OP_ISFREE:
-		for (i = 0; i < nlongs_reg; i++) {
-			if (bitmap[index + i] & mask)
-				goto done;
-		}
-		ret = 1;	/* all bits in region free (zero) */
-		break;
-
-	case REG_OP_ALLOC:
-		for (i = 0; i < nlongs_reg; i++)
-			bitmap[index + i] |= mask;
-		break;
-
-	case REG_OP_RELEASE:
-		for (i = 0; i < nlongs_reg; i++)
-			bitmap[index + i] &= ~mask;
-		break;
-	}
-done:
-	return ret;
-}
-
 /**
  * bitmap_find_free_region - find a contiguous aligned mem region
  *	@bitmap: array of unsigned longs corresponding to the bitmap
-- 
2.39.2

[PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h

[Yury Norov]

Now that bitmap_*_region() functions are implemented as thin wrappers
around others, it's worth to move them to the header, as it opens room
for compile-time optimizations.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/bitmap.h | 65 ++++++++++++++++++++++++++++++++++++++++--
 lib/bitmap.c           | 65 ------------------------------------------
 2 files changed, 62 insertions(+), 68 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 03644237e1ef..6c8d28419616 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -216,9 +216,68 @@ 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);
+
+/**
+ * bitmap_find_free_region - find a contiguous aligned mem region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *	@order: region size (log base 2 of number of bits) to find
+ *
+ * Find a region of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).  Only consider regions of length
+ * a power (@order) of two, aligned to that power of two, which
+ * makes the search algorithm much faster.
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+static inline int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
+{
+	unsigned int pos, end;		/* scans bitmap by regions of size order */
+
+	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end)
+		if (!bitmap_allocate_region(bitmap, pos, order))
+			return pos;
+
+	return -ENOMEM;
+}
+
+/**
+ * bitmap_release_region - release allocated bitmap region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@pos: beginning of bit region to release
+ *	@order: region size (log base 2 of number of bits) to release
+ *
+ * This is the complement to __bitmap_find_free_region() and releases
+ * the found region (by clearing it in the bitmap).
+ *
+ * No return value.
+ */
+static inline void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
+{
+	bitmap_clear(bitmap, pos, pos + BIT(order));
+}
+
+/**
+ * bitmap_allocate_region - allocate bitmap region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@pos: beginning of bit region to allocate
+ *	@order: region size (log base 2 of number of bits) to allocate
+ *
+ * Allocate (set bits in) a specified region of a bitmap.
+ *
+ * Return 0 on success, or %-EBUSY if specified region wasn't
+ * free (not all bits were zero).
+ */
+static inline int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
+{
+	unsigned int nbits = pos + BIT(order);
+
+	if (find_next_bit(bitmap, pos, nbits) < nbits)
+		return -EBUSY;
+	bitmap_set(bitmap, pos, nbits);
+	return 0;
+}
 
 #ifdef __BIG_ENDIAN
 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 7cfe0b442c73..1c5d1f5d2071 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1220,71 +1220,6 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
 }
 #endif /* CONFIG_NUMA */
 
-/**
- * bitmap_find_free_region - find a contiguous aligned mem region
- *	@bitmap: array of unsigned longs corresponding to the bitmap
- *	@bits: number of bits in the bitmap
- *	@order: region size (log base 2 of number of bits) to find
- *
- * Find a region of free (zero) bits in a @bitmap of @bits bits and
- * allocate them (set them to one).  Only consider regions of length
- * a power (@order) of two, aligned to that power of two, which
- * makes the search algorithm much faster.
- *
- * Return the bit offset in bitmap of the allocated region,
- * or -errno on failure.
- */
-int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
-{
-	unsigned int pos, end;		/* scans bitmap by regions of size order */
-
-	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end)
-		if (!bitmap_allocate_region(bitmap, pos, order))
-			return pos;
-
-	return -ENOMEM;
-}
-EXPORT_SYMBOL(bitmap_find_free_region);
-
-/**
- * bitmap_release_region - release allocated bitmap region
- *	@bitmap: array of unsigned longs corresponding to the bitmap
- *	@pos: beginning of bit region to release
- *	@order: region size (log base 2 of number of bits) to release
- *
- * This is the complement to __bitmap_find_free_region() and releases
- * the found region (by clearing it in the bitmap).
- *
- * No return value.
- */
-void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
-{
-	bitmap_clear(bitmap, pos, pos + BIT(order));
-}
-EXPORT_SYMBOL(bitmap_release_region);
-
-/**
- * bitmap_allocate_region - allocate bitmap region
- *	@bitmap: array of unsigned longs corresponding to the bitmap
- *	@pos: beginning of bit region to allocate
- *	@order: region size (log base 2 of number of bits) to allocate
- *
- * Allocate (set bits in) a specified region of a bitmap.
- *
- * Return 0 on success, or %-EBUSY if specified region wasn't
- * free (not all bits were zero).
- */
-int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
-{
-	unsigned int nbits = pos + BIT(order);
-
-	if (find_next_bit(bitmap, pos, nbits) < nbits)
-		return -EBUSY;
-	bitmap_set(bitmap, pos, nbits);
-	return 0;
-}
-EXPORT_SYMBOL(bitmap_allocate_region);
-
 /**
  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
  * @dst:   destination buffer
-- 
2.39.2

Re: [PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h

[kernel test robot]

Hi Yury,

kernel test robot noticed the following build errors:

[auto build test ERROR on linus/master]
[also build test ERROR on v6.5-rc3 next-20230726]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-fix-opencoded-bitmap_allocate_region/20230727-100500
base:   linus/master
patch link:    https://lore.kernel.org/r/20230727020207.36314-7-yury.norov%40gmail.com
patch subject: [PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h
config: loongarch-allyesconfig (https://download.01.org/0day-ci/archive/20230727/202307271224.8Qeoqasq-lkp@intel.com/config)
compiler: loongarch64-linux-gcc (GCC) 12.3.0
reproduce: (https://download.01.org/0day-ci/archive/20230727/202307271224.8Qeoqasq-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202307271224.8Qeoqasq-lkp@intel.com/

All error/warnings (new ones prefixed by >>):

   scripts/genksyms/parse.y: warning: 9 shift/reduce conflicts [-Wconflicts-sr]
   scripts/genksyms/parse.y: warning: 5 reduce/reduce conflicts [-Wconflicts-rr]
   scripts/genksyms/parse.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
   In file included from include/linux/cpumask.h:12,
                    from arch/loongarch/include/asm/processor.h:9,
                    from arch/loongarch/include/asm/thread_info.h:15,
                    from include/linux/thread_info.h:60,
                    from include/asm-generic/current.h:5,
                    from ./arch/loongarch/include/generated/asm/current.h:1,
                    from include/linux/sched.h:12,
                    from arch/loongarch/kernel/asm-offsets.c:8:
   include/linux/bitmap.h: In function 'bitmap_find_free_region':
>> include/linux/bitmap.h:239:22: error: implicit declaration of function 'bitmap_allocate_region' [-Werror=implicit-function-declaration]
     239 |                 if (!bitmap_allocate_region(bitmap, pos, order))
         |                      ^~~~~~~~~~~~~~~~~~~~~~
   include/linux/bitmap.h: In function 'bitmap_release_region':
>> include/linux/bitmap.h:258:9: error: implicit declaration of function 'bitmap_clear'; did you mean 'bitmap_remap'? [-Werror=implicit-function-declaration]
     258 |         bitmap_clear(bitmap, pos, pos + BIT(order));
         |         ^~~~~~~~~~~~
         |         bitmap_remap
   include/linux/bitmap.h: At top level:
>> include/linux/bitmap.h:272:19: error: static declaration of 'bitmap_allocate_region' follows non-static declaration
     272 | static inline int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
         |                   ^~~~~~~~~~~~~~~~~~~~~~
   include/linux/bitmap.h:239:22: note: previous implicit declaration of 'bitmap_allocate_region' with type 'int()'
     239 |                 if (!bitmap_allocate_region(bitmap, pos, order))
         |                      ^~~~~~~~~~~~~~~~~~~~~~
   include/linux/bitmap.h: In function 'bitmap_allocate_region':
>> include/linux/bitmap.h:278:9: error: implicit declaration of function 'bitmap_set'; did you mean 'bitmap_cut'? [-Werror=implicit-function-declaration]
     278 |         bitmap_set(bitmap, pos, nbits);
         |         ^~~~~~~~~~
         |         bitmap_cut
   include/linux/bitmap.h: At top level:
>> include/linux/bitmap.h:510:29: warning: conflicting types for 'bitmap_set'; have 'void(long unsigned int *, unsigned int,  unsigned int)'
     510 | static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
         |                             ^~~~~~~~~~
>> include/linux/bitmap.h:510:29: error: static declaration of 'bitmap_set' follows non-static declaration
   include/linux/bitmap.h:278:9: note: previous implicit declaration of 'bitmap_set' with type 'void(long unsigned int *, unsigned int,  unsigned int)'
     278 |         bitmap_set(bitmap, pos, nbits);
         |         ^~~~~~~~~~
>> include/linux/bitmap.h:526:29: warning: conflicting types for 'bitmap_clear'; have 'void(long unsigned int *, unsigned int,  unsigned int)'
     526 | static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
         |                             ^~~~~~~~~~~~
>> include/linux/bitmap.h:526:29: error: static declaration of 'bitmap_clear' follows non-static declaration
   include/linux/bitmap.h:258:9: note: previous implicit declaration of 'bitmap_clear' with type 'void(long unsigned int *, unsigned int,  unsigned int)'
     258 |         bitmap_clear(bitmap, pos, pos + BIT(order));
         |         ^~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:17:6: warning: no previous prototype for 'output_ptreg_defines' [-Wmissing-prototypes]
      17 | void output_ptreg_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:64:6: warning: no previous prototype for 'output_task_defines' [-Wmissing-prototypes]
      64 | void output_task_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:79:6: warning: no previous prototype for 'output_thread_info_defines' [-Wmissing-prototypes]
      79 | void output_thread_info_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:95:6: warning: no previous prototype for 'output_thread_defines' [-Wmissing-prototypes]
      95 | void output_thread_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:138:6: warning: no previous prototype for 'output_thread_fpu_defines' [-Wmissing-prototypes]
     138 | void output_thread_fpu_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:178:6: warning: no previous prototype for 'output_mm_defines' [-Wmissing-prototypes]
     178 | void output_mm_defines(void)
         |      ^~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:210:6: warning: no previous prototype for 'output_sc_defines' [-Wmissing-prototypes]
     210 | void output_sc_defines(void)
         |      ^~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:218:6: warning: no previous prototype for 'output_signal_defines' [-Wmissing-prototypes]
     218 | void output_signal_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:256:6: warning: no previous prototype for 'output_smpboot_defines' [-Wmissing-prototypes]
     256 | void output_smpboot_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:266:6: warning: no previous prototype for 'output_pbe_defines' [-Wmissing-prototypes]
     266 | void output_pbe_defines(void)
         |      ^~~~~~~~~~~~~~~~~~
   arch/loongarch/kernel/asm-offsets.c:278:6: warning: no previous prototype for 'output_fgraph_ret_regs_defines' [-Wmissing-prototypes]
     278 | void output_fgraph_ret_regs_defines(void)
         |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   cc1: some warnings being treated as errors
   make[3]: *** [scripts/Makefile.build:116: arch/loongarch/kernel/asm-offsets.s] Error 1
   make[3]: Target 'prepare' not remade because of errors.
   make[2]: *** [Makefile:1287: prepare0] Error 2
   make[2]: Target 'prepare' not remade because of errors.
   make[1]: *** [Makefile:234: __sub-make] Error 2
   make[1]: Target 'prepare' not remade because of errors.
   make: *** [Makefile:234: __sub-make] Error 2
   make: Target 'prepare' not remade because of errors.


vim +/bitmap_allocate_region +239 include/linux/bitmap.h

   202	
   203	int bitmap_parse(const char *buf, unsigned int buflen,
   204				unsigned long *dst, int nbits);
   205	int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
   206				unsigned long *dst, int nbits);
   207	int bitmap_parselist(const char *buf, unsigned long *maskp,
   208				int nmaskbits);
   209	int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
   210				unsigned long *dst, int nbits);
   211	void bitmap_remap(unsigned long *dst, const unsigned long *src,
   212			const unsigned long *old, const unsigned long *new, unsigned int nbits);
   213	int bitmap_bitremap(int oldbit,
   214			const unsigned long *old, const unsigned long *new, int bits);
   215	void bitmap_onto(unsigned long *dst, const unsigned long *orig,
   216			const unsigned long *relmap, unsigned int bits);
   217	void bitmap_fold(unsigned long *dst, const unsigned long *orig,
   218			unsigned int sz, unsigned int nbits);
   219	
   220	/**
   221	 * bitmap_find_free_region - find a contiguous aligned mem region
   222	 *	@bitmap: array of unsigned longs corresponding to the bitmap
   223	 *	@bits: number of bits in the bitmap
   224	 *	@order: region size (log base 2 of number of bits) to find
   225	 *
   226	 * Find a region of free (zero) bits in a @bitmap of @bits bits and
   227	 * allocate them (set them to one).  Only consider regions of length
   228	 * a power (@order) of two, aligned to that power of two, which
   229	 * makes the search algorithm much faster.
   230	 *
   231	 * Return the bit offset in bitmap of the allocated region,
   232	 * or -errno on failure.
   233	 */
   234	static inline int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
   235	{
   236		unsigned int pos, end;		/* scans bitmap by regions of size order */
   237	
   238		for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end)
 > 239			if (!bitmap_allocate_region(bitmap, pos, order))
   240				return pos;
   241	
   242		return -ENOMEM;
   243	}
   244	
   245	/**
   246	 * bitmap_release_region - release allocated bitmap region
   247	 *	@bitmap: array of unsigned longs corresponding to the bitmap
   248	 *	@pos: beginning of bit region to release
   249	 *	@order: region size (log base 2 of number of bits) to release
   250	 *
   251	 * This is the complement to __bitmap_find_free_region() and releases
   252	 * the found region (by clearing it in the bitmap).
   253	 *
   254	 * No return value.
   255	 */
   256	static inline void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
   257	{
 > 258		bitmap_clear(bitmap, pos, pos + BIT(order));
   259	}
   260	
   261	/**
   262	 * bitmap_allocate_region - allocate bitmap region
   263	 *	@bitmap: array of unsigned longs corresponding to the bitmap
   264	 *	@pos: beginning of bit region to allocate
   265	 *	@order: region size (log base 2 of number of bits) to allocate
   266	 *
   267	 * Allocate (set bits in) a specified region of a bitmap.
   268	 *
   269	 * Return 0 on success, or %-EBUSY if specified region wasn't
   270	 * free (not all bits were zero).
   271	 */
 > 272	static inline int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
   273	{
   274		unsigned int nbits = pos + BIT(order);
   275	
   276		if (find_next_bit(bitmap, pos, nbits) < nbits)
   277			return -EBUSY;
 > 278		bitmap_set(bitmap, pos, nbits);
   279		return 0;
   280	}
   281	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h

[kernel test robot]

Hi Yury,

kernel test robot noticed the following build errors:

[auto build test ERROR on linus/master]
[also build test ERROR on v6.5-rc3 next-20230726]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-fix-opencoded-bitmap_allocate_region/20230727-100500
base:   linus/master
patch link:    https://lore.kernel.org/r/20230727020207.36314-7-yury.norov%40gmail.com
patch subject: [PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h
config: hexagon-randconfig-r036-20230726 (https://download.01.org/0day-ci/archive/20230727/202307271307.tipWMyPF-lkp@intel.com/config)
compiler: clang version 17.0.0 (https://github.com/llvm/llvm-project.git 4a5ac14ee968ff0ad5d2cc1ffa0299048db4c88a)
reproduce: (https://download.01.org/0day-ci/archive/20230727/202307271307.tipWMyPF-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202307271307.tipWMyPF-lkp@intel.com/

All errors (new ones prefixed by >>):

   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:14:
   In file included from include/linux/sem.h:5:
   In file included from include/uapi/linux/sem.h:5:
   In file included from include/linux/ipc.h:5:
   In file included from include/linux/spinlock.h:63:
   In file included from include/linux/lockdep.h:14:
   In file included from include/linux/smp.h:13:
   In file included from include/linux/cpumask.h:12:
>> include/linux/bitmap.h:239:8: error: call to undeclared function 'bitmap_allocate_region'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     239 |                 if (!bitmap_allocate_region(bitmap, pos, order))
         |                      ^
>> include/linux/bitmap.h:258:2: error: call to undeclared function 'bitmap_clear'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     258 |         bitmap_clear(bitmap, pos, pos + BIT(order));
         |         ^
   include/linux/bitmap.h:258:2: note: did you mean '__bitmap_clear'?
   include/linux/bitmap.h:171:6: note: '__bitmap_clear' declared here
     171 | void __bitmap_clear(unsigned long *map, unsigned int start, int len);
         |      ^
   include/linux/bitmap.h:272:19: error: static declaration of 'bitmap_allocate_region' follows non-static declaration
     272 | static inline int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
         |                   ^
   include/linux/bitmap.h:239:8: note: previous implicit declaration is here
     239 |                 if (!bitmap_allocate_region(bitmap, pos, order))
         |                      ^
>> include/linux/bitmap.h:278:2: error: call to undeclared function 'bitmap_set'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]
     278 |         bitmap_set(bitmap, pos, nbits);
         |         ^
   include/linux/bitmap.h:510:29: error: static declaration of 'bitmap_set' follows non-static declaration
     510 | static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
         |                             ^
   include/linux/bitmap.h:278:2: note: previous implicit declaration is here
     278 |         bitmap_set(bitmap, pos, nbits);
         |         ^
   include/linux/bitmap.h:526:29: error: static declaration of 'bitmap_clear' follows non-static declaration
     526 | static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
         |                             ^
   include/linux/bitmap.h:258:2: note: previous implicit declaration is here
     258 |         bitmap_clear(bitmap, pos, pos + BIT(order));
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:97:11: warning: array index 3 is past the end of the array (that has type 'unsigned long[2]') [-Warray-bounds]
      97 |                 return (set->sig[3] | set->sig[2] |
         |                         ^        ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:97:25: warning: array index 2 is past the end of the array (that has type 'unsigned long[2]') [-Warray-bounds]
      97 |                 return (set->sig[3] | set->sig[2] |
         |                                       ^        ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:113:11: warning: array index 3 is past the end of the array (that has type 'const unsigned long[2]') [-Warray-bounds]
     113 |                 return  (set1->sig[3] == set2->sig[3]) &&
         |                          ^         ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:113:27: warning: array index 3 is past the end of the array (that has type 'const unsigned long[2]') [-Warray-bounds]
     113 |                 return  (set1->sig[3] == set2->sig[3]) &&
         |                                          ^         ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:114:5: warning: array index 2 is past the end of the array (that has type 'const unsigned long[2]') [-Warray-bounds]
     114 |                         (set1->sig[2] == set2->sig[2]) &&
         |                          ^         ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:114:21: warning: array index 2 is past the end of the array (that has type 'const unsigned long[2]') [-Warray-bounds]
     114 |                         (set1->sig[2] == set2->sig[2]) &&
         |                                          ^         ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];
         |         ^
   In file included from arch/hexagon/kernel/asm-offsets.c:12:
   In file included from include/linux/compat.h:17:
   In file included from include/linux/fs.h:33:
   In file included from include/linux/percpu-rwsem.h:7:
   In file included from include/linux/rcuwait.h:6:
   In file included from include/linux/sched/signal.h:6:
   include/linux/signal.h:156:1: warning: array index 3 is past the end of the array (that has type 'const unsigned long[2]') [-Warray-bounds]
     156 | _SIG_SET_BINOP(sigorsets, _sig_or)
         | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   include/linux/signal.h:137:8: note: expanded from macro '_SIG_SET_BINOP'
     137 |                 a3 = a->sig[3]; a2 = a->sig[2];                         \
         |                      ^      ~
   include/uapi/asm-generic/signal.h:62:2: note: array 'sig' declared here
      62 |         unsigned long sig[_NSIG_WORDS];


vim +/bitmap_allocate_region +239 include/linux/bitmap.h

   202	
   203	int bitmap_parse(const char *buf, unsigned int buflen,
   204				unsigned long *dst, int nbits);
   205	int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
   206				unsigned long *dst, int nbits);
   207	int bitmap_parselist(const char *buf, unsigned long *maskp,
   208				int nmaskbits);
   209	int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
   210				unsigned long *dst, int nbits);
   211	void bitmap_remap(unsigned long *dst, const unsigned long *src,
   212			const unsigned long *old, const unsigned long *new, unsigned int nbits);
   213	int bitmap_bitremap(int oldbit,
   214			const unsigned long *old, const unsigned long *new, int bits);
   215	void bitmap_onto(unsigned long *dst, const unsigned long *orig,
   216			const unsigned long *relmap, unsigned int bits);
   217	void bitmap_fold(unsigned long *dst, const unsigned long *orig,
   218			unsigned int sz, unsigned int nbits);
   219	
   220	/**
   221	 * bitmap_find_free_region - find a contiguous aligned mem region
   222	 *	@bitmap: array of unsigned longs corresponding to the bitmap
   223	 *	@bits: number of bits in the bitmap
   224	 *	@order: region size (log base 2 of number of bits) to find
   225	 *
   226	 * Find a region of free (zero) bits in a @bitmap of @bits bits and
   227	 * allocate them (set them to one).  Only consider regions of length
   228	 * a power (@order) of two, aligned to that power of two, which
   229	 * makes the search algorithm much faster.
   230	 *
   231	 * Return the bit offset in bitmap of the allocated region,
   232	 * or -errno on failure.
   233	 */
   234	static inline int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
   235	{
   236		unsigned int pos, end;		/* scans bitmap by regions of size order */
   237	
   238		for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end)
 > 239			if (!bitmap_allocate_region(bitmap, pos, order))
   240				return pos;
   241	
   242		return -ENOMEM;
   243	}
   244	
   245	/**
   246	 * bitmap_release_region - release allocated bitmap region
   247	 *	@bitmap: array of unsigned longs corresponding to the bitmap
   248	 *	@pos: beginning of bit region to release
   249	 *	@order: region size (log base 2 of number of bits) to release
   250	 *
   251	 * This is the complement to __bitmap_find_free_region() and releases
   252	 * the found region (by clearing it in the bitmap).
   253	 *
   254	 * No return value.
   255	 */
   256	static inline void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
   257	{
 > 258		bitmap_clear(bitmap, pos, pos + BIT(order));
   259	}
   260	
   261	/**
   262	 * bitmap_allocate_region - allocate bitmap region
   263	 *	@bitmap: array of unsigned longs corresponding to the bitmap
   264	 *	@pos: beginning of bit region to allocate
   265	 *	@order: region size (log base 2 of number of bits) to allocate
   266	 *
   267	 * Allocate (set bits in) a specified region of a bitmap.
   268	 *
   269	 * Return 0 on success, or %-EBUSY if specified region wasn't
   270	 * free (not all bits were zero).
   271	 */
   272	static inline int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
   273	{
   274		unsigned int nbits = pos + BIT(order);
   275	
   276		if (find_next_bit(bitmap, pos, nbits) < nbits)
   277			return -EBUSY;
 > 278		bitmap_set(bitmap, pos, nbits);
   279		return 0;
   280	}
   281	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 1/6] bitmap: fix opencoded bitmap_allocate_region()

[Andy Shevchenko]

On Wed, Jul 26, 2023 at 07:02:02PM -0700, Yury Norov wrote:
> bitmap_find_region() opencodes bitmap_allocate_region(). Fix it.

...

> +	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end)

In the other patch you use BIT(order), why not here?

> +		if (!bitmap_allocate_region(bitmap, pos, order))
> +			return pos;

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 4/6] bitmap: replace _reg_op(REG_OP_ISFREE) with find_next_bit()

[Andy Shevchenko]

On Wed, Jul 26, 2023 at 07:02:05PM -0700, Yury Norov wrote:
> _reg_op(REG_OP_ISFREE) can be trivially replaced with find_next_bit().
> Drop it.

The verb here is incorrect, you don't drop it, you replaced it.

Same for the other patches.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h

[Andy Shevchenko]

On Wed, Jul 26, 2023 at 07:02:07PM -0700, Yury Norov wrote:
> Now that bitmap_*_region() functions are implemented as thin wrappers
> around others, it's worth to move them to the header, as it opens room
> for compile-time optimizations.

Don't forget to run

	scripts/kernel-doc -v -none -Wall

against this header.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 6/6] bitmap: move bitmap_*_region functions to bitmap.h

[Yury Norov]

On Thu, Jul 27, 2023 at 3:07 AM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> On Wed, Jul 26, 2023 at 07:02:07PM -0700, Yury Norov wrote:
> > Now that bitmap_*_region() functions are implemented as thin wrappers
> > around others, it's worth to move them to the header, as it opens room
> > for compile-time optimizations.
>
> Don't forget to run
>
>         scripts/kernel-doc -v -none -Wall
>
> against this header.

OK, will do. Also, I seemingly created patched from the wrong branch,
so it's a wrong order of declarations in the header. Sorry that, I'll
send v2 after collecting some more comments.