x86/bitops: implement __test_bit

arch/x86/include/asm/bitops.h +7 -0

+static __always_inline int __constant_test_bit(long nr, const unsigned long *addr)
+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long *addr)

Quoted 1 line · Michael S. Tsirkin

+static __always_inline int __constant_test_bit(long nr, const

unsigned long *addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr)

Quoted 6 lines

arch/x86/include/asm/bitops.h +6 -0

+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long

*addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr) · line 342

Quoted 10 lines

arch/x86/include/asm/bitops.h +10 -0

+{
+	int oldbit;
+
+	asm volatile("bt %2,%1\n\t"
+		     "sbb %0,%0"
+		     : "=r" (oldbit)
+		     : "m" (*addr), "Ir" (nr));
+
+	return oldbit;
+}

Color me confused, why use assembly for this at all?

Why not just use C for testing the bit (i.e. turn __constant_test_bit() into
__test_bit()) - that would also allow the compiler to propagate the result,
potentially more optimally than we can do it via SBB...

Thanks,

Ingo

Presumably because gcc can't generate bt... whether or not it is worth it is another matter.

Quoted 34 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

+static __always_inline int __constant_test_bit(long nr, const

unsigned long *addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr)

Quoted 6 lines

arch/x86/include/asm/bitops.h +6 -0

+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long

*addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr) · line 342

Quoted 10 lines

arch/x86/include/asm/bitops.h +10 -0

+{
+	int oldbit;
+
+	asm volatile("bt %2,%1\n\t"
+		     "sbb %0,%0"
+		     : "=r" (oldbit)
+		     : "m" (*addr), "Ir" (nr));
+
+	return oldbit;
+}

Color me confused, why use assembly for this at all?

Why not just use C for testing the bit (i.e. turn __constant_test_bit() into
__test_bit()) - that would also allow the compiler to propagate the result,
potentially more optimally than we can do it via SBB...

Thanks,

Ingo

Quoted 37 lines · H. Peter Anvin

Presumably because gcc can't generate bt... whether or not it is worth it is another matter.

Quoted 34 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

+static __always_inline int __constant_test_bit(long nr, const

unsigned long *addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr)

Quoted 6 lines

arch/x86/include/asm/bitops.h +6 -0

+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long

*addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr) · line 342

Quoted 10 lines

arch/x86/include/asm/bitops.h +10 -0

+{
+	int oldbit;
+
+	asm volatile("bt %2,%1\n\t"
+		     "sbb %0,%0"
+		     : "=r" (oldbit)
+		     : "m" (*addr), "Ir" (nr));
+
+	return oldbit;
+}

Color me confused, why use assembly for this at all?

Why not just use C for testing the bit (i.e. turn __constant_test_bit() into
__test_bit()) - that would also allow the compiler to propagate the result,
potentially more optimally than we can do it via SBB...

Thanks,

Ingo

Exactly:

Disassembly of section .text:

00000000 <__variable_test_bit>:
__variable_test_bit():

   0:   8b 54 24 08             mov    0x8(%esp),%edx
   4:   8b 44 24 04             mov    0x4(%esp),%eax
   8:   0f a3 02                bt     %eax,(%edx)
   b:   19 c0                   sbb    %eax,%eax
   d:   c3                      ret    
   e:   66 90                   xchg   %ax,%ax

00000010 <__constant_test_bit>:
__constant_test_bit():

  10:   8b 4c 24 04             mov    0x4(%esp),%ecx
  14:   8b 44 24 08             mov    0x8(%esp),%eax
  18:   89 ca                   mov    %ecx,%edx
  1a:   c1 fa 04                sar    $0x4,%edx
  1d:   8b 04 90                mov    (%eax,%edx,4),%eax
  20:   d3 e8                   shr    %cl,%eax
  22:   83 e0 01                and    $0x1,%eax
  25:   c3                      ret    

Quoted 55 lines · Michael S. Tsirkin

Quoted 37 lines · H. Peter Anvin

Presumably because gcc can't generate bt... whether or not it is worth it is another matter.

Quoted 34 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

+static __always_inline int __constant_test_bit(long nr, const

unsigned long *addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr)

Quoted 6 lines

arch/x86/include/asm/bitops.h +6 -0

+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long

*addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr) · line 342

Quoted 10 lines

arch/x86/include/asm/bitops.h +10 -0

+{
+	int oldbit;
+
+	asm volatile("bt %2,%1\n\t"
+		     "sbb %0,%0"
+		     : "=r" (oldbit)
+		     : "m" (*addr), "Ir" (nr));
+
+	return oldbit;
+}

Color me confused, why use assembly for this at all?

Why not just use C for testing the bit (i.e. turn __constant_test_bit() into
__test_bit()) - that would also allow the compiler to propagate the result,
potentially more optimally than we can do it via SBB...

Thanks,

Ingo

Exactly:

Disassembly of section .text:

00000000 <__variable_test_bit>:
__variable_test_bit():

  0:   8b 54 24 08             mov    0x8(%esp),%edx
  4:   8b 44 24 04             mov    0x4(%esp),%eax
  8:   0f a3 02                bt     %eax,(%edx)
  b:   19 c0                   sbb    %eax,%eax
  d:   c3                      ret    
  e:   66 90                   xchg   %ax,%ax

00000010 <__constant_test_bit>:
__constant_test_bit():

Quoted 8 lines

 10:   8b 4c 24 04             mov    0x4(%esp),%ecx
 14:   8b 44 24 08             mov    0x8(%esp),%eax
 18:   89 ca                   mov    %ecx,%edx
 1a:   c1 fa 04                sar    $0x4,%edx
 1d:   8b 04 90                mov    (%eax,%edx,4),%eax
 20:   d3 e8                   shr    %cl,%eax
 22:   83 e0 01                and    $0x1,%eax
 25:   c3                      ret    

But that's due to the forced interface of generating a return code. Please compare it at an inlined usage site, where GCC is free to do the comparison directly and use the result in flags.

Quoted 70 lines · Ingo Molnar

Quoted 63 lines · Michael S. Tsirkin

Quoted 37 lines · H. Peter Anvin

Presumably because gcc can't generate bt... whether or not it is worth it is another matter.

Quoted 34 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

+static __always_inline int __constant_test_bit(long nr, const

unsigned long *addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr)

Quoted 6 lines

arch/x86/include/asm/bitops.h +6 -0

+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long

*addr)

arch/x86/include/asm/bitops.h static inline int variable_test_bit(long nr, volatile const unsigned long *addr) · line 342

Quoted 10 lines

arch/x86/include/asm/bitops.h +10 -0

+{
+	int oldbit;
+
+	asm volatile("bt %2,%1\n\t"
+		     "sbb %0,%0"
+		     : "=r" (oldbit)
+		     : "m" (*addr), "Ir" (nr));
+
+	return oldbit;
+}

Color me confused, why use assembly for this at all?

Why not just use C for testing the bit (i.e. turn __constant_test_bit() into
__test_bit()) - that would also allow the compiler to propagate the result,
potentially more optimally than we can do it via SBB...

Thanks,

Ingo

Exactly:

Disassembly of section .text:

00000000 <__variable_test_bit>:
__variable_test_bit():

  0:   8b 54 24 08             mov    0x8(%esp),%edx
  4:   8b 44 24 04             mov    0x4(%esp),%eax
  8:   0f a3 02                bt     %eax,(%edx)
  b:   19 c0                   sbb    %eax,%eax
  d:   c3                      ret    
  e:   66 90                   xchg   %ax,%ax

00000010 <__constant_test_bit>:
__constant_test_bit():

 10:   8b 4c 24 04             mov    0x4(%esp),%ecx
 14:   8b 44 24 08             mov    0x8(%esp),%eax
 18:   89 ca                   mov    %ecx,%edx
 1a:   c1 fa 04                sar    $0x4,%edx
 1d:   8b 04 90                mov    (%eax,%edx,4),%eax
 20:   d3 e8                   shr    %cl,%eax
 22:   83 e0 01                and    $0x1,%eax
 25:   c3                      ret    

Quoted 3 lines

But that's due to the forced interface of generating a return code. Please compare it at an inlined usage site, where GCC is free to do the comparison directly and use the result in flags.

just curious :
it seems __variable_test_bit() use less instructions,
why not always use __variable_test_bit() , remove __constant_test_bit() version ?

Quoted 13 lines

Disassembly of section .text:

00000000 <__variable_test_bit>:
__variable_test_bit():

   0:   8b 54 24 08             mov    0x8(%esp),%edx
   4:   8b 44 24 04             mov    0x4(%esp),%eax
   8:   0f a3 02                bt     %eax,(%edx)
   b:   19 c0                   sbb    %eax,%eax
   d:   c3                      ret    
   e:   66 90                   xchg   %ax,%ax

00000010 <__constant_test_bit>:
__constant_test_bit():

Quoted 8 lines

  10:   8b 4c 24 04             mov    0x4(%esp),%ecx
  14:   8b 44 24 08             mov    0x8(%esp),%eax
  18:   89 ca                   mov    %ecx,%edx
  1a:   c1 fa 04                sar    $0x4,%edx
  1d:   8b 04 90                mov    (%eax,%edx,4),%eax
  20:   d3 e8                   shr    %cl,%eax
  22:   83 e0 01                and    $0x1,%eax
  25:   c3                      ret    

But that's due to the forced interface of generating a return code. Please compare it at an inlined usage site, where GCC is free to do the comparison directly and use the result in flags.

Quoted 55 lines · Michael S. Tsirkin

Quoted 37 lines · H. Peter Anvin

Presumably because gcc can't generate bt... whether or not it is worth it is another matter.

Quoted 34 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

+static __always_inline int __constant_test_bit(long nr, const

unsigned long *addr)

Review

Quoted 6 lines

(quoted diff) +6 -0

+{
+	return ((1UL << (nr & (BITS_PER_LONG-1))) &
+		(addr[nr >> _BITOPS_LONG_SHIFT])) != 0;
+}
+
+static inline int __variable_test_bit(long nr, const unsigned long

*addr)

Review

Quoted 10 lines

(quoted diff) +10 -0

+{
+	int oldbit;
+
+	asm volatile("bt %2,%1\n\t"
+		     "sbb %0,%0"
+		     : "=r" (oldbit)
+		     : "m" (*addr), "Ir" (nr));
+
+	return oldbit;
+}

Color me confused, why use assembly for this at all?

Why not just use C for testing the bit (i.e. turn __constant_test_bit() into
__test_bit()) - that would also allow the compiler to propagate the result,
potentially more optimally than we can do it via SBB...

Thanks,

Ingo

Exactly:

Disassembly of section .text:

00000000 <__variable_test_bit>:
__variable_test_bit():

   0:   8b 54 24 08             mov    0x8(%esp),%edx
   4:   8b 44 24 04             mov    0x4(%esp),%eax
   8:   0f a3 02                bt     %eax,(%edx)
   b:   19 c0                   sbb    %eax,%eax
   d:   c3                      ret    
   e:   66 90                   xchg   %ax,%ax

00000010 <__constant_test_bit>:
__constant_test_bit():

Quoted 8 lines

  10:   8b 4c 24 04             mov    0x4(%esp),%ecx
  14:   8b 44 24 08             mov    0x8(%esp),%eax
  18:   89 ca                   mov    %ecx,%edx
  1a:   c1 fa 04                sar    $0x4,%edx
  1d:   8b 04 90                mov    (%eax,%edx,4),%eax
  20:   d3 e8                   shr    %cl,%eax
  22:   83 e0 01                and    $0x1,%eax
  25:   c3                      ret    

But that's due to the forced interface of generating a return code. Please compare it at an inlined usage site, where GCC is free to do the comparison directly and use the result in flags.

Thanks,

Ingo

I applied this patch on top of mine:

arch/x86/include/asm/bitops.h +0 -11

-static inline int __variable_test_bit(long nr, const unsigned long *addr)
-{
-	int oldbit;
-
-	asm volatile("bt %2,%1\n\t"
-		     "sbb %0,%0"
-		     : "=r" (oldbit)
-		     : "m" (*addr), "Ir" (nr));
-
-	return oldbit;
-}

And the code size went up:

   134836    2997    8372  146205   23b1d arch/x86/kvm/kvm-intel.ko  ->
   134846    2997    8372  146215   23b27 arch/x86/kvm/kvm-intel.ko     

   342690   47640     441  390771   5f673 arch/x86/kvm/kvm.ko ->
   342738   47640     441  390819   5f6a3 arch/x86/kvm/kvm.ko   

I tried removing __always_inline, this had no effect.

Quoted 1 line · Michael S. Tsirkin

I applied this patch on top of mine:

Yeah, looks similar to the one I sent.

Quoted 14 lines

arch/x86/include/asm/bitops.h +0 -11

-static inline int __variable_test_bit(long nr, const unsigned long *addr)
-{
-	int oldbit;
-
-	asm volatile("bt %2,%1\n\t"
-		     "sbb %0,%0"
-		     : "=r" (oldbit)
-		     : "m" (*addr), "Ir" (nr));
-
-	return oldbit;
-}

And the code size went up:

Quoted 7 lines

   134836    2997    8372  146205   23b1d arch/x86/kvm/kvm-intel.ko  ->
   134846    2997    8372  146215   23b27 arch/x86/kvm/kvm-intel.ko     

   342690   47640     441  390771   5f673 arch/x86/kvm/kvm.ko ->
   342738   47640     441  390819   5f6a3 arch/x86/kvm/kvm.ko   

I tried removing __always_inline, this had no effect.

But code size isn't the only factor.

Uros Bizjak pointed out that the reason GCC does not use the "BT reg,mem" instruction is that it's highly suboptimal even on recent microarchitectures, Sandy Bridge is listed as having a 10 cycles latency (!) for this instruction:

http://www.agner.org/optimize/instruction_tables.pdf

this instruction had bad latency going back to Pentium 4 CPUs.

... so unless something changed in this area with Skylake I think using the __variable_test_bit() code of the kernel is a bad choice and looking at kernel size only is misleading.

It makes sense for atomics, but not for unlocked access.

Thanks,

Ingo

Quoted 43 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

I applied this patch on top of mine:

Yeah, looks similar to the one I sent.

Quoted 14 lines

arch/x86/include/asm/bitops.h +0 -11

-static inline int __variable_test_bit(long nr, const unsigned long *addr)
-{
-	int oldbit;
-
-	asm volatile("bt %2,%1\n\t"
-		     "sbb %0,%0"
-		     : "=r" (oldbit)
-		     : "m" (*addr), "Ir" (nr));
-
-	return oldbit;
-}

And the code size went up:

Quoted 7 lines

   134836    2997    8372  146205   23b1d arch/x86/kvm/kvm-intel.ko  ->
   134846    2997    8372  146215   23b27 arch/x86/kvm/kvm-intel.ko     

   342690   47640     441  390771   5f673 arch/x86/kvm/kvm.ko ->
   342738   47640     441  390819   5f6a3 arch/x86/kvm/kvm.ko   

I tried removing __always_inline, this had no effect.

But code size isn't the only factor.

Uros Bizjak pointed out that the reason GCC does not use the "BT reg,mem" instruction is that it's highly suboptimal even on recent microarchitectures, Sandy Bridge is listed as having a 10 cycles latency (!) for this instruction:

http://www.agner.org/optimize/instruction_tables.pdf

this instruction had bad latency going back to Pentium 4 CPUs.

... so unless something changed in this area with Skylake I think using the __variable_test_bit() code of the kernel is a bad choice and looking at kernel size only is misleading.

Quoted 5 lines

It makes sense for atomics, but not for unlocked access.

Thanks,

Ingo

Hmm - so do you take back the ack?

I compared this:
int main(int argc, char **argv)
{

        long long int i;
        const unsigned long addr = 0;
        for (i = 0; i < 1000000000ull; ++i) {
                asm volatile("");
                if (__variable_test_bit(1, &addr))
                asm volatile("");
        }
        return 0;
}

with the __constant_test_bit variant.

__constant_test_bit code does appear to be slower on an i7 processor.

test_bit isn't atomic either. Maybe drop variable_test_bit there too?

Quoted 48 lines · Michael S. Tsirkin

Quoted 47 lines · Ingo Molnar

Quoted 1 line · Michael S. Tsirkin

I applied this patch on top of mine:

Yeah, looks similar to the one I sent.

Quoted 14 lines

arch/x86/include/asm/bitops.h +0 -11

-static inline int __variable_test_bit(long nr, const unsigned long *addr)
-{
-	int oldbit;
-
-	asm volatile("bt %2,%1\n\t"
-		     "sbb %0,%0"
-		     : "=r" (oldbit)
-		     : "m" (*addr), "Ir" (nr));
-
-	return oldbit;
-}

And the code size went up:

Quoted 7 lines

   134836    2997    8372  146205   23b1d arch/x86/kvm/kvm-intel.ko  ->
   134846    2997    8372  146215   23b27 arch/x86/kvm/kvm-intel.ko     

   342690   47640     441  390771   5f673 arch/x86/kvm/kvm.ko ->
   342738   47640     441  390819   5f6a3 arch/x86/kvm/kvm.ko   

I tried removing __always_inline, this had no effect.

But code size isn't the only factor.

Uros Bizjak pointed out that the reason GCC does not use the "BT reg,mem" instruction is that it's highly suboptimal even on recent microarchitectures, Sandy Bridge is listed as having a 10 cycles latency (!) for this instruction:

http://www.agner.org/optimize/instruction_tables.pdf

this instruction had bad latency going back to Pentium 4 CPUs.

... so unless something changed in this area with Skylake I think using the __variable_test_bit() code of the kernel is a bad choice and looking at kernel size only is misleading.

It makes sense for atomics, but not for unlocked access.

Thanks,

Quoted 3 lines

Quoted 1 line

Ingo

Hmm - so do you take back the ack?

I have no strong feelings either way, it simply strikes me as misguided to explicitly optimize for something that is listed as a high overhead instruction.

Assuming it really is high overhead:

Quoted 17 lines

I compared this:
int main(int argc, char **argv)
{

        long long int i;
        const unsigned long addr = 0;
        for (i = 0; i < 1000000000ull; ++i) {
                asm volatile("");
                if (__variable_test_bit(1, &addr))
                asm volatile("");
        }
        return 0;
}

with the __constant_test_bit variant.

__constant_test_bit code does appear to be slower on an i7 processor.

              if (__constant_test_bit(1, &addr))

Quoted 6 lines

Quoted 2 lines

Hmm - so do you take back the ack?

I have no strong feelings either way, it simply strikes me as misguided to explicitly optimize for something that is listed as a high overhead instruction.

[mst@robin test]$ diff a.c b.c
31c31
< if (__variable_test_bit(1, &addr))
---

Quoted 1 line

              if (__constant_test_bit(1, &addr))

[mst@robin test]$ gcc -Wall -O2 a.c; time ./a.out

real    0m0.532s
user    0m0.531s
sys     0m0.000s

[mst@robin test]$ gcc -Wall -O2 b.c; time ./a.out

real    0m0.517s
user    0m0.517s
sys     0m0.000s

So __constant_test_bit is faster even though it's using more instructions

$ gcc -Wall -O2 a.c; -objdump -ld ./a.out