[PATCH 01/16] lib/bitmap: add bitmap_check_params()

[Yury Norov <yury.norov@gmail.com>]

bitmap_check_params() takes all arguments passed into bitmap functions
and runs sanity checks. bitmap_check(), bitmap_check_op() and
bitmap_check_move() are convenient wrappers for frequent cases.

The following patches of this series clear all warnings found with
bitmap_check_params() for x86_64, arm64 and powerpc64.

The last patch introduces CONFIG_DEBUG_BITMAP option to let user enable
bitmap_check_params().

No functional changes for existing kernel users, and for the following
functions inline parameters checks removed:
 - bitmap_pos_to_ord;
 - bitmap_remap;
 - bitmap_onto;
 - bitmap_fold.

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

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 035d4ac66641..6a0d9170c4f0 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -8,9 +8,46 @@
 #include <linux/bitops.h>
 #include <linux/find.h>
 #include <linux/limits.h>
+#include <linux/printk.h>
 #include <linux/string.h>
 #include <linux/types.h>
 
+#define CHECK_B2		BIT(0)
+#define CHECK_B3		BIT(1)
+#define CHECK_START		BIT(2)
+#define CHECK_OFF		BIT(3)
+#define CHECK_OVERLAP12		BIT(4)
+#define CHECK_OVERLAP13		BIT(5)
+#define CHECK_OVERLAP23		BIT(6)
+#define CHECK_OFF_EQ_0		BIT(7)
+#define CHECK_START_LE_OFF	BIT(8)
+
+#define NBITS_MAX	(INT_MAX-1)
+
+#ifdef CONFIG_DEBUG_BITMAP
+#define bitmap_check_params(b1, b2, b3, nbits, start, off, flags)		\
+	do {									\
+		if (__bitmap_check_params((b1), (b2), (b3), (nbits),		\
+						(start), (off), (flags))) {	\
+			pr_warn("Bitmap: parameters check failed");		\
+			pr_warn("%s [%d]: %s\n", __FILE__, __LINE__, __func__);	\
+		}								\
+	} while (0)
+
+bool __bitmap_check_params(const unsigned long *b1, const unsigned long *b2,
+				const unsigned long *b3, const unsigned long nbits,
+				const unsigned long start, const unsigned long off,
+				const unsigned long flags);
+#else
+#define bitmap_check_params(b1, b2, b3, nbits, start, off, flags)
+#endif
+
+#define bitmap_check(buf, nbits) bitmap_check_params(buf, NULL, NULL, nbits, 0, 0, 0)
+#define bitmap_check_op(dst, src1, src2, nbits) \
+	bitmap_check_params(dst, src1, src2, nbits, 0, 0, CHECK_B2 | CHECK_B3 | CHECK_OVERLAP23)
+#define bitmap_check_move(dst, src, nbits) \
+	bitmap_check_params(dst, src, NULL, nbits, 0, 0, CHECK_B2 | CHECK_OVERLAP12)
+
 struct device;
 
 /*
@@ -239,6 +276,8 @@ static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
 {
 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 
+	bitmap_check(dst, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = 0;
 	else
@@ -249,6 +288,8 @@ static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
 {
 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 
+	bitmap_check(dst, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = ~0UL;
 	else
@@ -260,6 +301,8 @@ static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
 {
 	unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 
+	bitmap_check_move(dst, src, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = *src;
 	else
@@ -318,6 +361,8 @@ void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits);
 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,
 			const unsigned long *src2, unsigned int nbits)
 {
+	bitmap_check_op(dst, src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
 	return __bitmap_and(dst, src1, src2, nbits);
@@ -326,6 +371,8 @@ static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,
 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
 			const unsigned long *src2, unsigned int nbits)
 {
+	bitmap_check_op(dst, src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = *src1 | *src2;
 	else
@@ -335,6 +382,8 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
 static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
 			const unsigned long *src2, unsigned int nbits)
 {
+	bitmap_check_op(dst, src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = *src1 ^ *src2;
 	else
@@ -344,6 +393,8 @@ static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
 static inline bool bitmap_andnot(unsigned long *dst, const unsigned long *src1,
 			const unsigned long *src2, unsigned int nbits)
 {
+	bitmap_check_op(dst, src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
 	return __bitmap_andnot(dst, src1, src2, nbits);
@@ -352,6 +403,8 @@ static inline bool bitmap_andnot(unsigned long *dst, const unsigned long *src1,
 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
 			unsigned int nbits)
 {
+	bitmap_check_move(dst, src, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = ~(*src);
 	else
@@ -368,6 +421,8 @@ static inline void bitmap_complement(unsigned long *dst, const unsigned long *sr
 static inline bool bitmap_equal(const unsigned long *src1,
 				const unsigned long *src2, unsigned int nbits)
 {
+	bitmap_check_move(src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
 	if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
@@ -390,6 +445,9 @@ static inline bool bitmap_or_equal(const unsigned long *src1,
 				   const unsigned long *src3,
 				   unsigned int nbits)
 {
+	bitmap_check_params(src1, src2, src3, nbits, 0, 0, CHECK_B2 | CHECK_B3 |
+				CHECK_OVERLAP12 | CHECK_OVERLAP13 | CHECK_OVERLAP23);
+
 	if (!small_const_nbits(nbits))
 		return __bitmap_or_equal(src1, src2, src3, nbits);
 
@@ -400,6 +458,8 @@ static inline bool bitmap_intersects(const unsigned long *src1,
 				     const unsigned long *src2,
 				     unsigned int nbits)
 {
+	bitmap_check_move(src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
 	else
@@ -409,6 +469,8 @@ static inline bool bitmap_intersects(const unsigned long *src1,
 static inline bool bitmap_subset(const unsigned long *src1,
 				 const unsigned long *src2, unsigned int nbits)
 {
+	bitmap_check_move(src1, src2, nbits);
+
 	if (small_const_nbits(nbits))
 		return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
 	else
@@ -417,6 +479,8 @@ static inline bool bitmap_subset(const unsigned long *src1,
 
 static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)
 {
+	bitmap_check(src, nbits);
+
 	if (small_const_nbits(nbits))
 		return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
 
@@ -425,6 +489,8 @@ static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)
 
 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
 {
+	bitmap_check(src, nbits);
+
 	if (small_const_nbits(nbits))
 		return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
 
@@ -434,6 +500,8 @@ static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
 static __always_inline
 unsigned long bitmap_weight(const unsigned long *src, unsigned int nbits)
 {
+	bitmap_check(src, nbits);
+
 	if (small_const_nbits(nbits))
 		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
 	return __bitmap_weight(src, nbits);
@@ -442,6 +510,9 @@ unsigned long bitmap_weight(const unsigned long *src, unsigned int nbits)
 static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
 		unsigned int nbits)
 {
+	bitmap_check_params(map, NULL, NULL, start + nbits, start, nbits,
+				CHECK_START | CHECK_OFF | CHECK_OFF_EQ_0);
+
 	if (__builtin_constant_p(nbits) && nbits == 1)
 		__set_bit(start, map);
 	else if (small_const_nbits(start + nbits))
@@ -458,6 +529,9 @@ static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
 static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
 		unsigned int nbits)
 {
+	bitmap_check_params(map, NULL, NULL, start + nbits, start, nbits,
+				CHECK_START | CHECK_OFF | CHECK_OFF_EQ_0);
+
 	if (__builtin_constant_p(nbits) && nbits == 1)
 		__clear_bit(start, map);
 	else if (small_const_nbits(start + nbits))
@@ -474,6 +548,8 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
 static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits)
 {
+	bitmap_check_params(dst, src, NULL, nbits, shift, 0, CHECK_START);
+
 	if (small_const_nbits(nbits))
 		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
 	else
@@ -483,6 +559,8 @@ static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *s
 static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits)
 {
+	bitmap_check_params(dst, src, NULL, nbits, shift, 0, CHECK_START);
+
 	if (small_const_nbits(nbits))
 		*dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
 	else
@@ -495,6 +573,10 @@ static inline void bitmap_replace(unsigned long *dst,
 				  const unsigned long *mask,
 				  unsigned int nbits)
 {
+	bitmap_check_op(dst, old, mask, nbits);
+	bitmap_check_op(dst, new, mask, nbits);
+	bitmap_check_op(dst, old, new, nbits);
+
 	if (small_const_nbits(nbits))
 		*dst = (*old & ~(*mask)) | (*new & *mask);
 	else
@@ -505,6 +587,8 @@ static inline void bitmap_next_set_region(unsigned long *bitmap,
 					  unsigned int *rs, unsigned int *re,
 					  unsigned int end)
 {
+	bitmap_check(bitmap, end);
+
 	*rs = find_next_bit(bitmap, end, *rs);
 	*re = find_next_zero_bit(bitmap, end, *rs + 1);
 }
@@ -571,6 +655,11 @@ static inline unsigned long bitmap_get_value8(const unsigned long *map,
 	const size_t index = BIT_WORD(start);
 	const unsigned long offset = start % BITS_PER_LONG;
 
+#ifdef DEBUG_BITMAP
+	bitmap_check_params(map, NULL, NULL, start + 8, start, 0, CHECK_START);
+	WARN_ON(start % 8);
+#endif
+
 	return (map[index] >> offset) & 0xFF;
 }
 
@@ -586,6 +675,12 @@ static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
 	const size_t index = BIT_WORD(start);
 	const unsigned long offset = start % BITS_PER_LONG;
 
+#ifdef DEBUG_BITMAP
+	bitmap_check_params(map, NULL, NULL, start + 8, start, 0, CHECK_START);
+	WARN_ON(start % 8);
+	WARN_ON(value > 0xFFUL);
+#endif
+
 	map[index] &= ~(0xFFUL << offset);
 	map[index] |= value << offset;
 }
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 2b67cd657692..cd4dd848ea6a 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -22,6 +22,71 @@
 
 #include "kstrtox.h"
 
+#ifdef CONFIG_DEBUG_BITMAP
+static inline const bool check_overlap(const unsigned long *b1, const unsigned long *b2,
+			  unsigned long nbits)
+{
+	return min(b1, b2) + DIV_ROUND_UP(nbits, BITS_PER_LONG) > max(b1, b2);
+}
+
+bool __bitmap_check_params(const unsigned long *b1, const unsigned long *b2,
+				const unsigned long *b3, const unsigned long nbits,
+				const unsigned long start, const unsigned long off,
+				const unsigned long flags)
+{
+	bool warn = false;
+
+	warn |= WARN_ON(b1 == NULL);
+	warn |= WARN_ON(nbits == 0);
+	warn |= WARN_ON(nbits > NBITS_MAX);
+
+	if (flags & CHECK_B2) {
+		warn |= WARN_ON(b2 == NULL);
+		warn |= WARN_ON(flags & CHECK_OVERLAP12 &&
+				check_overlap(b1, b2, nbits));
+	}
+
+	if (flags & CHECK_B3) {
+		warn |= WARN_ON(b3 == NULL);
+		warn |= WARN_ON(flags & CHECK_OVERLAP13 &&
+				check_overlap(b1, b3, nbits));
+	}
+
+	if (flags & CHECK_OVERLAP23)
+		warn |= WARN_ON(check_overlap(b2, b3, nbits));
+
+	if (flags & CHECK_START)
+		warn |= WARN_ON(start >= nbits);
+
+	if (flags & CHECK_OFF)
+		warn |= WARN_ON(off > nbits);
+
+	if (flags & CHECK_OFF_EQ_0)
+		warn |= WARN_ON(off == 0);
+
+	if (flags & CHECK_START_LE_OFF)
+		warn |= WARN_ON(start > off);
+
+	if (flags & CHECK_B2 && flags & CHECK_B3)
+		warn |= WARN_ON(b2 == b3);
+
+	if (warn) {
+		/*
+		 * Convert kernel addresses to unsigned long because
+		 * %pK hides actual values with the lack of randomization.
+		 */
+		pr_warn("b1:\t\t%lx\n", (unsigned long)b1);
+		pr_warn("b2:\t\t%lx\n", (unsigned long)b2);
+		pr_warn("b3:\t\t%lx\n", (unsigned long)b3);
+		pr_warn("nbits:\t%lu\n", nbits);
+		pr_warn("start:\t%lu\n", start);
+		pr_warn("off:\t%lu\n", off);
+	}
+	return warn;
+}
+EXPORT_SYMBOL(__bitmap_check_params);
+#endif
+
 /**
  * DOC: bitmap introduction
  *
@@ -214,6 +279,9 @@ void bitmap_cut(unsigned long *dst, const unsigned long *src,
 	unsigned long keep = 0, carry;
 	int i;
 
+	bitmap_check_params(dst, src, NULL, nbits, first, first + cut,
+				CHECK_B2 | CHECK_START | CHECK_OFF);
+
 	if (first % BITS_PER_LONG) {
 		keep = src[first / BITS_PER_LONG] &
 		       (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));
@@ -410,6 +478,10 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 					     unsigned long align_offset)
 {
 	unsigned long index, end, i;
+
+	bitmap_check_params(map, NULL, NULL, size, start, start + nr,
+				CHECK_START | CHECK_OFF | CHECK_START_LE_OFF);
+
 again:
 	index = find_next_zero_bit(map, size, start);
 
@@ -797,6 +869,8 @@ int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
 	struct region r;
 	long ret;
 
+	bitmap_check(maskp, nmaskbits);
+
 	r.nbits = nmaskbits;
 	bitmap_zero(maskp, r.nbits);
 
@@ -900,6 +974,8 @@ int bitmap_parse(const char *start, unsigned int buflen,
 	int unset_bit;
 	int chunk;
 
+	bitmap_check(maskp, nmaskbits);
+
 	for (chunk = 0; ; chunk++) {
 		end = bitmap_find_region_reverse(start, end);
 		if (start > end)
@@ -950,7 +1026,9 @@ EXPORT_SYMBOL(bitmap_parse);
  */
 static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
 {
-	if (pos >= nbits || !test_bit(pos, buf))
+	bitmap_check_params(buf, NULL, NULL, nbits, pos, 0, CHECK_START);
+
+	if (!test_bit(pos, buf))
 		return -1;
 
 	return __bitmap_weight(buf, pos);
@@ -1024,8 +1102,13 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
 {
 	unsigned int oldbit, w;
 
-	if (dst == src)		/* following doesn't handle inplace remaps */
-		return;
+	bitmap_check_params(dst, src, old, nbits, 0, 0,
+				CHECK_B2 | CHECK_B3 | CHECK_OVERLAP12 |
+				CHECK_OVERLAP13 | CHECK_OVERLAP23);
+	bitmap_check_params(dst, src, new, nbits, 0, 0,
+				CHECK_B2 | CHECK_B3 | CHECK_OVERLAP12 |
+				CHECK_OVERLAP13 | CHECK_OVERLAP23);
+
 	bitmap_zero(dst, nbits);
 
 	w = bitmap_weight(new, nbits);
@@ -1069,8 +1152,13 @@ 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);
+	int w, n;
+
+	bitmap_check_params(old, new, NULL, bits, oldbit, 0, CHECK_B2 |
+				CHECK_START | CHECK_OVERLAP12);
+
+	w = bitmap_weight(new, bits);
+	n = bitmap_pos_to_ord(old, oldbit, bits);
 	if (n < 0 || w == 0)
 		return oldbit;
 	else
@@ -1190,8 +1278,9 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
 {
 	unsigned int n, m;	/* same meaning as in above comment */
 
-	if (dst == orig)	/* following doesn't handle inplace mappings */
-		return;
+	bitmap_check_params(dst, orig, relmap, bits, 0, 0, CHECK_B2 | CHECK_B3 |
+				CHECK_OVERLAP12 | CHECK_OVERLAP13 | CHECK_OVERLAP23);
+
 	bitmap_zero(dst, bits);
 
 	/*
@@ -1229,8 +1318,8 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
 {
 	unsigned int oldbit;
 
-	if (dst == orig)	/* following doesn't handle inplace mappings */
-		return;
+	bitmap_check_move(dst, orig, sz);
+
 	bitmap_zero(dst, nbits);
 
 	for_each_set_bit(oldbit, orig, nbits)
@@ -1332,6 +1421,8 @@ int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
 {
 	unsigned int pos, end;		/* scans bitmap by regions of size order */
 
+	bitmap_check_params(bitmap, NULL, NULL, bits, (1 << order), 0, CHECK_OFF);
+
 	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			continue;
@@ -1355,6 +1446,8 @@ EXPORT_SYMBOL(bitmap_find_free_region);
  */
 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
 {
+	bitmap_check_params(bitmap, NULL, NULL, pos + (1 << order), pos, pos + (1 << order),
+				CHECK_START | CHECK_OFF);
 	__reg_op(bitmap, pos, order, REG_OP_RELEASE);
 }
 EXPORT_SYMBOL(bitmap_release_region);
@@ -1372,6 +1465,8 @@ EXPORT_SYMBOL(bitmap_release_region);
  */
 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
 {
+	bitmap_check_params(bitmap, NULL, NULL, pos + (1 << order), pos, pos + (1 << order),
+				CHECK_START | CHECK_OFF);
 	if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 		return -EBUSY;
 	return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
@@ -1391,6 +1486,8 @@ void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int n
 {
 	unsigned int i;
 
+	bitmap_check_move(dst, src, nbits);
+
 	for (i = 0; i < nbits/BITS_PER_LONG; i++) {
 		if (BITS_PER_LONG == 64)
 			dst[i] = cpu_to_le64(src[i]);
@@ -1476,6 +1573,8 @@ void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits
 {
 	unsigned int i, halfwords;
 
+	bitmap_check_move(bitmap, (unsigned long *)buf, nbits);
+
 	halfwords = DIV_ROUND_UP(nbits, 32);
 	for (i = 0; i < halfwords; i++) {
 		bitmap[i/2] = (unsigned long) buf[i];
@@ -1499,6 +1598,8 @@ void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
 {
 	unsigned int i, halfwords;
 
+	bitmap_check_move(bitmap, (unsigned long *)buf, nbits);
+
 	halfwords = DIV_ROUND_UP(nbits, 32);
 	for (i = 0; i < halfwords; i++) {
 		buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
@@ -1524,6 +1625,8 @@ void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits
 {
 	int n;
 
+	bitmap_check_move(bitmap, (unsigned long *)buf, nbits);
+
 	for (n = nbits; n > 0; n -= 64) {
 		u64 val = *buf++;
 
@@ -1554,6 +1657,8 @@ void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits)
 {
 	const unsigned long *end = bitmap + BITS_TO_LONGS(nbits);
 
+	bitmap_check_move(bitmap, (unsigned long *)buf, nbits);
+
 	while (bitmap < end) {
 		*buf = *bitmap++;
 		if (bitmap < end)
-- 
2.34.1