Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Yury Norov <yury.norov@gmail.com>
To:     Stefano Brivio <sbrivio@redhat.com>
Cc:     Yury Norov <yury.norov@gmail.com>,
        Pablo Neira Ayuso <pablo@netfilter.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
        Rasmus Villemoes <linux@rasmusvillemoes.dk>,
        linux-kernel@vger.kernel.org
Subject: [PATCH] lib/bitmap: rework bitmap_cut()
Date:   Fri,  6 Mar 2020 14:14:23 -0800
Message-Id: <20200306221423.18631-1-yury.norov@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

bitmap_cut() refers src after memmove(). If dst and src overlap,
it may cause buggy behaviour because src may become inconsistent.

The function complexity is of O(nbits * cut_bits), which can be
improved to O(nbits).

We can also rely on bitmap_shift_right() to do most of the work.

I don't like interface of bitmap_cut(). The idea of copying of a
whole bitmap inside the function from src to dst doesn't look
useful in practice. The function is introduced a few weeks ago and
was most probably inspired by bitmap_shift_*. Looking at the code,
it's easy to see that bitmap_shift_* is usually passed with
dst == src. bitmap_cut() has a single user so far, and it also
calls it with dst == src.

This patch removes dst so the whole work is made in-place. It also
switches the function to bitmap_shift_right() internally in sake of
performance and simplicity.

I've added a very basic test too.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/bitmap.h         |  7 ++---
 lib/bitmap.c                   | 51 +++++++++-------------------------
 lib/test_bitmap.c              | 32 +++++++++++++++++++++
 net/netfilter/nft_set_pipapo.c |  3 +-
 4 files changed, 49 insertions(+), 44 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 99058eb81042..ed60b7272437 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -59,7 +59,7 @@
  *  						Iterate over all set regions
  *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
  *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
- *  bitmap_cut(dst, src, first, n, nbits)       Cut n bits from first, copy rest
+ *  bitmap_cut(bmap, first, n, nbits)           Cut n bits from first, copy rest
  *  bitmap_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)
  *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
  *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
@@ -140,9 +140,8 @@ extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits);
 extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, unsigned int nbits);
-extern void bitmap_cut(unsigned long *dst, const unsigned long *src,
-		       unsigned int first, unsigned int cut,
-		       unsigned int nbits);
+extern void bitmap_cut(unsigned long *bmap, unsigned int first,
+			unsigned int cut, unsigned int nbits);
 extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 			const unsigned long *bitmap2, unsigned int nbits);
 extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 89260aa342d6..06e06e0c3096 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -170,67 +170,42 @@ EXPORT_SYMBOL(__bitmap_shift_left);
 
 /**
  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
- * @dst: destination bitmap, might overlap with src
- * @src: source bitmap
+ * @bmap:  bitmap to cut
  * @first: start bit of region to be removed
  * @cut: number of bits to remove
  * @nbits: bitmap size, in bits
  *
- * Set the n-th bit of @dst iff the n-th bit of @src is set and
- * n is less than @first, or the m-th bit of @src is set for any
- * m such that @first <= n < nbits, and m = n + @cut.
- *
  * In pictures, example for a big-endian 32-bit architecture:
  *
- * @src:
+ * @bmap:
  * 31                                   63
  * |                                    |
  * 10000000 11000001 11110010 00010101  10000000 11000001 01110010 00010101
  *                 |  |              |                                    |
  *                16  14             0                                   32
  *
- * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is:
+ * if @cut is 3, and @first is 14, bits 14-16 in @bmap are cut and @dst is:
  *
  * 31                                   63
  * |                                    |
  * 10110000 00011000 00110010 00010101  00010000 00011000 00101110 01000010
  *                    |              |                                    |
  *                    14 (bit 17     0                                   32
- *                        from @src)
- *
- * Note that @dst and @src might overlap partially or entirely.
- *
- * This is implemented in the obvious way, with a shift and carry
- * step for each moved bit. Optimisation is left as an exercise
- * for the compiler.
+ *                        from @bmap)
  */
-void bitmap_cut(unsigned long *dst, const unsigned long *src,
-		unsigned int first, unsigned int cut, unsigned int nbits)
+void bitmap_cut(unsigned long *bmap, unsigned int first,
+		unsigned int cut, unsigned int nbits)
 {
-	unsigned int len = BITS_TO_LONGS(nbits);
-	unsigned long keep = 0, carry;
-	int i;
-
-	memmove(dst, src, len * sizeof(*dst));
-
-	if (first % BITS_PER_LONG) {
-		keep = src[first / BITS_PER_LONG] &
-		       (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));
-	}
+	unsigned long tmp;
+	unsigned long *b = bmap + first / BITS_PER_LONG;
 
-	while (cut--) {
-		for (i = first / BITS_PER_LONG; i < len; i++) {
-			if (i < len - 1)
-				carry = dst[i + 1] & 1UL;
-			else
-				carry = 0;
+	if (first % BITS_PER_LONG)
+		tmp = b[0] & BITMAP_LAST_WORD_MASK(first);
 
-			dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));
-		}
-	}
+	bitmap_shift_right(b, b, cut - first, nbits - first);
 
-	dst[first / BITS_PER_LONG] &= ~0UL << (first % BITS_PER_LONG);
-	dst[first / BITS_PER_LONG] |= keep;
+	if (first % BITS_PER_LONG)
+		b[0] = tmp | (b[0] & BITMAP_FIRST_WORD_MASK(first));
 }
 EXPORT_SYMBOL(bitmap_cut);
 
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 6b13150667f5..4b2fef13003d 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -540,6 +540,37 @@ static void __init test_bitmap_arr32(void)
 	}
 }
 
+struct test_bitmap_cut {
+	unsigned int first;
+	unsigned int last;
+	unsigned int nbits;
+	unsigned long in;
+	unsigned long out;
+};
+
+static struct test_bitmap_cut test_cut[] = {
+	{ 0,  0,  BITS_PER_LONG, 0xdeadbeefUL, 0xdeadbeefUL },
+	{ 0,  8,  BITS_PER_LONG, 0xdeadbeefUL, 0xdeadbeUL },
+	{ 4,  8,  BITS_PER_LONG, 0xdeadbeefUL, 0xdeadbefUL },
+	{ 8,  24, BITS_PER_LONG, 0xdeadbeefUL, 0xdeefUL },
+	{ 16, 32, BITS_PER_LONG, 0xdeadbeefUL, 0xbeefUL },
+};
+
+static void __init test_bitmap_cut(void)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
+		struct test_bitmap_cut *t = &test_cut[i];
+
+		bitmap_cut(&t->in, t->first, t->last, t->nbits);
+		if (!bitmap_equal(&t->in, &t->out, t->nbits)) {
+			pr_err("bitmap_cut #%d failed:\n%*pb.\nExpected:\n%*pb\n",
+					i, t->nbits, &t->in, t->nbits, &t->out);
+		}
+	}
+}
+
 static void noinline __init test_mem_optimisations(void)
 {
 	DECLARE_BITMAP(bmap1, 1024);
@@ -617,6 +648,7 @@ static void __init selftest(void)
 	test_copy();
 	test_replace();
 	test_bitmap_arr32();
+	test_bitmap_cut();
 	test_bitmap_parse();
 	test_bitmap_parse_user();
 	test_bitmap_parselist();
diff --git a/net/netfilter/nft_set_pipapo.c b/net/netfilter/nft_set_pipapo.c
index 26395c8188b1..68faaf9a4f66 100644
--- a/net/netfilter/nft_set_pipapo.c
+++ b/net/netfilter/nft_set_pipapo.c
@@ -1397,8 +1397,7 @@ static void pipapo_drop(struct nft_pipapo_match *m,
 			pos = f->lt + g * NFT_PIPAPO_BUCKETS * f->bsize;
 
 			for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
-				bitmap_cut(pos, pos, rulemap[i].to,
-					   rulemap[i].n,
+				bitmap_cut(pos, rulemap[i].to, rulemap[i].n,
 					   f->bsize * BITS_PER_LONG);
 
 				pos += f->bsize;
-- 
2.20.1