[PATCH 0/3] Bitmap optimisations

[PATCH 0/3] Bitmap optimisations

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

These three bitmap patches use more efficient specialisations when the
compiler can figure out that it's safe to do so.

Matthew Wilcox (3):
  bitmap: Optimise bitmap_set and bitmap_clear of a single bit
  Turn bitmap_set and bitmap_clear into memset when possible
  bitmap: Use memcmp optimisation in more situations

 include/linux/bitmap.h | 33 +++++++++++++++++++++++++++------
 lib/bitmap.c           |  8 ++++----
 2 files changed, 31 insertions(+), 10 deletions(-)

-- 
2.11.0

[PATCH 1/3] bitmap: Optimise bitmap_set and bitmap_clear of a single bit

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

We have eight users calling bitmap_clear for a single bit and seventeen
calling bitmap_set for a single bit.  Rather than fix all of them to call
__clear_bit or __set_bit, turn bitmap_clear and bitmap_set into inline
functions and make this special case efficient.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/bitmap.h | 23 ++++++++++++++++++++---
 lib/bitmap.c           |  8 ++++----
 2 files changed, 24 insertions(+), 7 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 3b77588a9360..4e0f0c8167af 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -112,9 +112,8 @@ extern int __bitmap_intersects(const unsigned long *bitmap1,
 extern int __bitmap_subset(const unsigned long *bitmap1,
 			const unsigned long *bitmap2, unsigned int nbits);
 extern int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
-
-extern void bitmap_set(unsigned long *map, unsigned int start, int len);
-extern void bitmap_clear(unsigned long *map, unsigned int start, int len);
+extern void __bitmap_set(unsigned long *map, unsigned int start, int len);
+extern void __bitmap_clear(unsigned long *map, unsigned int start, int len);
 
 extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 						    unsigned long size,
@@ -315,6 +314,24 @@ static __always_inline int bitmap_weight(const unsigned long *src, unsigned int
 	return __bitmap_weight(src, nbits);
 }
 
+static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
+		unsigned int nbits)
+{
+	if (__builtin_constant_p(nbits) && nbits == 1)
+		__set_bit(start, map);
+	else
+		__bitmap_set(map, start, nbits);
+}
+
+static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
+		unsigned int nbits)
+{
+	if (__builtin_constant_p(nbits) && nbits == 1)
+		__clear_bit(start, map);
+	else
+		__bitmap_clear(map, start, nbits);
+}
+
 static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 				unsigned int shift, int nbits)
 {
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 0b66f0e5eb6b..6e354a6d0dbb 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -251,7 +251,7 @@ int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
-void bitmap_set(unsigned long *map, unsigned int start, int len)
+void __bitmap_set(unsigned long *map, unsigned int start, int len)
 {
 	unsigned long *p = map + BIT_WORD(start);
 	const unsigned int size = start + len;
@@ -270,9 +270,9 @@ void bitmap_set(unsigned long *map, unsigned int start, int len)
 		*p |= mask_to_set;
 	}
 }
-EXPORT_SYMBOL(bitmap_set);
+EXPORT_SYMBOL(__bitmap_set);
 
-void bitmap_clear(unsigned long *map, unsigned int start, int len)
+void __bitmap_clear(unsigned long *map, unsigned int start, int len)
 {
 	unsigned long *p = map + BIT_WORD(start);
 	const unsigned int size = start + len;
@@ -291,7 +291,7 @@ void bitmap_clear(unsigned long *map, unsigned int start, int len)
 		*p &= ~mask_to_clear;
 	}
 }
-EXPORT_SYMBOL(bitmap_clear);
+EXPORT_SYMBOL(__bitmap_clear);
 
 /**
  * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
-- 
2.11.0

[PATCH 2/3] Turn bitmap_set and bitmap_clear into memset when possible

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Several callers have constant 'start' and an 'nbits' that is a multiple of
8, so we can turn them into calls to memset.  We don't need the entirety
of 'start' and 'nbits' to  be constant, we just need to know whether
they're divisible by 8.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/bitmap.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 4e0f0c8167af..0b3e4452b054 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -319,6 +319,9 @@ static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
 {
 	if (__builtin_constant_p(nbits) && nbits == 1)
 		__set_bit(start, map);
+	else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
+		 __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
+		memset(map + start / 8, 0xff, nbits / 8);
 	else
 		__bitmap_set(map, start, nbits);
 }
@@ -328,6 +331,9 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
 {
 	if (__builtin_constant_p(nbits) && nbits == 1)
 		__clear_bit(start, map);
+	else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
+		 __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
+		memset(map + start / 8, 0, nbits / 8);
 	else
 		__bitmap_clear(map, start, nbits);
 }
-- 
2.11.0

[PATCH 3/3] bitmap: Use memcmp optimisation in more situations

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Commit 7dd968163f ("bitmap: bitmap_equal memcmp optimization") was
rather more restrictive than necessary; we can use memcmp() to implement
bitmap_equal() as long as the number of bits can be proved to be a
multiple of 8.  And architectures other than s390 may be able to make
good use of this optimisation.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/bitmap.h | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 0b3e4452b054..26244e0098f0 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -266,10 +266,8 @@ static inline int bitmap_equal(const unsigned long *src1,
 {
 	if (small_const_nbits(nbits))
 		return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
-#ifdef CONFIG_S390
-	if (__builtin_constant_p(nbits) && (nbits % BITS_PER_LONG) == 0)
+	if (__builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
 		return !memcmp(src1, src2, nbits / 8);
-#endif
 	return __bitmap_equal(src1, src2, nbits);
 }
 
-- 
2.11.0

Re: [PATCH 2/3] Turn bitmap_set and bitmap_clear into memset when possible

[Rasmus Villemoes]

On Wed, Jun 07 2017, Matthew Wilcox <willy@infradead.org> wrote:

> From: Matthew Wilcox <mawilcox@microsoft.com>
>
> Several callers have constant 'start' and an 'nbits' that is a multiple of
> 8, so we can turn them into calls to memset.  We don't need the entirety
> of 'start' and 'nbits' to  be constant, we just need to know whether
> they're divisible by 8.
>
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> ---
>  include/linux/bitmap.h | 6 ++++++
>  1 file changed, 6 insertions(+)
>
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 4e0f0c8167af..0b3e4452b054 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -319,6 +319,9 @@ static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
>  {
>  	if (__builtin_constant_p(nbits) && nbits == 1)
>  		__set_bit(start, map);
> +	else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
> +		 __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
> +		memset(map + start / 8, 0xff, nbits / 8);
>  	else

Isn't the pointer arithmetic wrong here? I think you need to cast map to
(char*).

> 
>  		__bitmap_set(map, start, nbits);
>  }
> @@ -328,6 +331,9 @@ static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
>  {
>  	if (__builtin_constant_p(nbits) && nbits == 1)
>  		__clear_bit(start, map);
> +	else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
> +		 __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
> +		memset(map + start / 8, 0, nbits / 8);
>  	else

Ditto.

Do you have an example of how the generated code changes, both in the
case of actual constants and a case where gcc can see that start and
nbits are byte-aligned without knowing their actual values?

Re: [PATCH 0/3] Bitmap optimisations

[Rasmus Villemoes]

On Wed, Jun 07 2017, Matthew Wilcox <willy@infradead.org> wrote:

> From: Matthew Wilcox <mawilcox@microsoft.com>
>
> These three bitmap patches use more efficient specialisations when the
> compiler can figure out that it's safe to do so.
>

With the pointer arithmetic fixed,

Acked-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>

Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

[Andy Shevchenko]

On Wed, Jun 7, 2017 at 5:29 PM, Matthew Wilcox <willy@infradead.org> wrote:

> Commit 7dd968163f ("bitmap: bitmap_equal memcmp optimization") was
> rather more restrictive than necessary; we can use memcmp() to implement
> bitmap_equal() as long as the number of bits can be proved to be a
> multiple of 8.  And architectures other than s390 may be able to make
> good use of this optimisation.

> -       if (__builtin_constant_p(nbits) && (nbits % BITS_PER_LONG) == 0)
> +       if (__builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
>                 return !memcmp(src1, src2, nbits / 8);

I'm not sure this is a fully correct change.
What exactly ' & 7' part does?
For me looks like you may just drop it.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

[Matthew Wilcox]

On Thu, Jun 08, 2017 at 04:48:04AM +0300, Andy Shevchenko wrote:
> > Commit 7dd968163f ("bitmap: bitmap_equal memcmp optimization") was
> > rather more restrictive than necessary; we can use memcmp() to implement
> > bitmap_equal() as long as the number of bits can be proved to be a
> > multiple of 8.  And architectures other than s390 may be able to make
> > good use of this optimisation.
> 
> > -       if (__builtin_constant_p(nbits) && (nbits % BITS_PER_LONG) == 0)
> > +       if (__builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
> >                 return !memcmp(src1, src2, nbits / 8);
> 
> I'm not sure this is a fully correct change.
> What exactly ' & 7' part does?
> For me looks like you may just drop it.

We only need to know if the bottom 3 bits are 0 to apply this optimisation.
For example, if we have a user which does this:

	nbits = 8;
	if (argle)
		nbits += 8;
	if (bitmap_equal(ptr1, ptr2, nbits))
		blah();

then we can use memcmp() because gcc can deduce that the bottom 3 bits
are never set (try it!  it works!).  We don't need nbits as a whole to
be const.

Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

[Andy Shevchenko]

On Thu, Jun 8, 2017 at 5:55 AM, Matthew Wilcox <willy@infradead.org> wrote:
> On Thu, Jun 08, 2017 at 04:48:04AM +0300, Andy Shevchenko wrote:
>> > Commit 7dd968163f ("bitmap: bitmap_equal memcmp optimization") was
>> > rather more restrictive than necessary; we can use memcmp() to implement
>> > bitmap_equal() as long as the number of bits can be proved to be a
>> > multiple of 8.  And architectures other than s390 may be able to make
>> > good use of this optimisation.
>>
>> > -       if (__builtin_constant_p(nbits) && (nbits % BITS_PER_LONG) == 0)
>> > +       if (__builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
>> >                 return !memcmp(src1, src2, nbits / 8);
>>
>> I'm not sure this is a fully correct change.
>> What exactly ' & 7' part does?
>> For me looks like you may just drop it.
>
> We only need to know if the bottom 3 bits are 0 to apply this optimisation.
> For example, if we have a user which does this:
>
>         nbits = 8;
>         if (argle)
>                 nbits += 8;
>         if (bitmap_equal(ptr1, ptr2, nbits))
>                 blah();
>
> then we can use memcmp() because gcc can deduce that the bottom 3 bits
> are never set (try it!  it works!).  We don't need nbits as a whole to
> be const.

What I'm talking about is that by my opinion the both below are equivalent.
__builtin_constant_p(nbits)
__builtin_constant_p(nbits & 7)

Thus, again, what & 7 does there?

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

[Rasmus Villemoes]

On 8 June 2017 at 14:31, Andy Shevchenko <andy.shevchenko@gmail.com> wrote:
> On Thu, Jun 8, 2017 at 5:55 AM, Matthew Wilcox <willy@infradead.org> wrote:
>> We only need to know if the bottom 3 bits are 0 to apply this optimisation.
>> For example, if we have a user which does this:
>>
>>         nbits = 8;
>>         if (argle)
>>                 nbits += 8;
>>         if (bitmap_equal(ptr1, ptr2, nbits))
>>                 blah();
>>
>> then we can use memcmp() because gcc can deduce that the bottom 3 bits
>> are never set (try it!  it works!).  We don't need nbits as a whole to
>> be const.
>
> What I'm talking about is that by my opinion the both below are equivalent.
> __builtin_constant_p(nbits)
> __builtin_constant_p(nbits & 7)

They are not. Read Matthew's example again. Assuming that argle is
something non-constant (maybe an argument to the function), the value
of nbits at the time of the bitmap_equal call is _not_ a
compile-time-constant. However, if the compiler is smart (which at
least some versions of gcc are), the compiler may deduce that nbits is
either 8 or 16; there really are no other options. Hence it _is_
statically known that nbits is divisible by 8, so the expression
nbits&7 _is_ compile-time constant (0), so gcc can change the
bitmap_equal call to a memcmp call.

(It may then either pass a run-time value of nbits>>3 and emit a
single memcmp call, or it may decide to unroll the two options,
creating two memcmp calls with 1 and 2 as compile-time arguments;
these may or may not then in turn be "inlined" to code doing roughly
*(u8*)p1 == *(u8*)p2 and similarly for u16 casts).

Re: [PATCH 3/3] bitmap: Use memcmp optimisation in more situations

[Andy Shevchenko]

On Thu, Jun 8, 2017 at 4:43 PM, Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
> On 8 June 2017 at 14:31, Andy Shevchenko <andy.shevchenko@gmail.com> wrote:
>> On Thu, Jun 8, 2017 at 5:55 AM, Matthew Wilcox <willy@infradead.org> wrote:
>>> We only need to know if the bottom 3 bits are 0 to apply this optimisation.
>>> For example, if we have a user which does this:
>>>
>>>         nbits = 8;
>>>         if (argle)
>>>                 nbits += 8;
>>>         if (bitmap_equal(ptr1, ptr2, nbits))
>>>                 blah();
>>>
>>> then we can use memcmp() because gcc can deduce that the bottom 3 bits
>>> are never set (try it!  it works!).  We don't need nbits as a whole to
>>> be const.
>>
>> What I'm talking about is that by my opinion the both below are equivalent.
>> __builtin_constant_p(nbits)
>> __builtin_constant_p(nbits & 7)
>
> They are not. Read Matthew's example again. Assuming that argle is
> something non-constant (maybe an argument to the function), the value
> of nbits at the time of the bitmap_equal call is _not_ a
> compile-time-constant. However, if the compiler is smart (which at
> least some versions of gcc are), the compiler may deduce that nbits is
> either 8 or 16; there really are no other options. Hence it _is_
> statically known that nbits is divisible by 8, so the expression
> nbits&7 _is_ compile-time constant (0), so gcc can change the
> bitmap_equal call to a memcmp call.

Yeah, thanks for detailed explanation.
So, basically what we do, we consider
1. 3 LSBs _is_ constant, *and*
2. They are equal to 0.

> (It may then either pass a run-time value of nbits>>3 and emit a
> single memcmp call, or it may decide to unroll the two options,
> creating two memcmp calls with 1 and 2 as compile-time arguments;
> these may or may not then in turn be "inlined" to code doing roughly
> *(u8*)p1 == *(u8*)p2 and similarly for u16 casts).

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 2/3] Turn bitmap_set and bitmap_clear into memset when possible

[Matthew Wilcox]

On Wed, Jun 07, 2017 at 11:16:37PM +0200, Rasmus Villemoes wrote:
> On Wed, Jun 07 2017, Matthew Wilcox <willy@infradead.org> wrote:
> > @@ -319,6 +319,9 @@ static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
> >  {
> >  	if (__builtin_constant_p(nbits) && nbits == 1)
> >  		__set_bit(start, map);
> > +	else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
> > +		 __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
> > +		memset(map + start / 8, 0xff, nbits / 8);
> >  	else
> 
> Isn't the pointer arithmetic wrong here? I think you need to cast map to
> (char*).

Good catch.  I've added a test case to test_bitmap.c and it catches
the problem.

> Do you have an example of how the generated code changes, both in the
> case of actual constants and a case where gcc can see that start and
> nbits are byte-aligned without knowing their actual values?

Here's an example of start == 0 and nbits being clearly a multiple of 8,
courtesy of btrfs's extent-io-tests.c.

Before:
  f1:   48 8b 5c 24 10          mov    0x10(%rsp),%rbx
  f6:   4c 8b 3c 24             mov    (%rsp),%r15
  fa:   31 f6                   xor    %esi,%esi
  fc:   44 8d 34 dd 00 00 00    lea    0x0(,%rbx,8),%r14d
 103:   00 
 104:   4c 8d 2c dd 00 00 00    lea    0x0(,%rbx,8),%r13
 10b:   00 
 10c:   4c 89 ff                mov    %r15,%rdi
 10f:   44 89 f2                mov    %r14d,%edx
 112:   e8 00 00 00 00          callq  117 <__test_eb_bitmaps+0x77>
                        113: R_X86_64_PC32      bitmap_set-0x4
 117:   31 d2                   xor    %edx,%edx
 119:   31 f6                   xor    %esi,%esi
 11b:   4c 89 e9                mov    %r13,%rcx
 11e:   4c 89 e7                mov    %r12,%rdi
 121:   e8 00 00 00 00          callq  126 <__test_eb_bitmaps+0x86>
                        122: R_X86_64_PC32      extent_buffer_bitmap_set-0x4

After:
  f1:   4c 8b 7c 24 10          mov    0x10(%rsp),%r15
  f6:   be ff 00 00 00          mov    $0xff,%esi
  fb:   48 89 df                mov    %rbx,%rdi
  fe:   4d 89 fe                mov    %r15,%r14
 101:   4e 8d 2c fd 00 00 00    lea    0x0(,%r15,8),%r13
 108:   00 
 109:   41 81 e6 ff ff ff 1f    and    $0x1fffffff,%r14d
 110:   4c 89 f2                mov    %r14,%rdx
 113:   e8 00 00 00 00          callq  118 <__test_eb_bitmaps+0x78>
                        114: R_X86_64_PC32      memset-0x4
 118:   48 8b 2c 24             mov    (%rsp),%rbp
 11c:   31 d2                   xor    %edx,%edx
 11e:   31 f6                   xor    %esi,%esi
 120:   4c 89 e9                mov    %r13,%rcx
 123:   48 89 ef                mov    %rbp,%rdi
 126:   e8 00 00 00 00          callq  12b <__test_eb_bitmaps+0x8b>
                        127: R_X86_64_PC32      extent_buffer_bitmap_set-0x4

It's actually slightly less efficient in the caller (although obviously
memset() is going to execute faster than bitmap_set()).  Partly because
x86 made some odd choices about the behaviour of an 8-bit move instruction
(it leaves the upper 24 bits intact, rather than zeroing them, so gcc
has to use a 32-bit move instruction to put 0xff into the second argument
to memset()), and partly because gcc is seeing us do:

	unsigned long len;
	len = len * 8 / 8;

so it's (very reasonably) transforming that into len &= 0x1fff'ffff'ffff'ffff;
That's partly a quirk of how this particular function is written.

Re: [PATCH 2/3] Turn bitmap_set and bitmap_clear into memset when possible

[Rasmus Villemoes]

> It's actually slightly less efficient in the caller (although obviously
> memset() is going to execute faster than bitmap_set()).  Partly because
> x86 made some odd choices about the behaviour of an 8-bit move instruction
> (it leaves the upper 24 bits intact, rather than zeroing them, so gcc
> has to use a 32-bit move instruction to put 0xff into the second argument
> to memset()),

Heh, I thought gcc knew and made full use of the semantics of memset,
so that only the low byte matters. I suppose there might be
architectures where passing -1 is slightly cheaper (at least in code
size) than 255... [quick checking] indeed, on x86_64, there's no
change in the generated code, but on 32 bit, gcc ends up doing

6a ff                   push   $0xffffffff

instead of

68 ff 00 00 00          push   $0xff