linux-kernel - Re: [PATCH 1/2] x86/bitops: implement __test

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Tue, 01 Sep 2015 16:48:52 -0700
From:	"H. Peter Anvin" <hpa@...or.com>
To:	"Michael S. Tsirkin" <mst@...hat.com>,
	Ingo Molnar <mingo@...nel.org>
CC:	linux-kernel@...r.kernel.org, Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>, x86@...nel.org,
	Rusty Russell <rusty@...tcorp.com.au>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Uros Bizjak <ubizjak@...il.com>
Subject: Re: [PATCH 1/2] x86/bitops: implement __test_bit

On 09/01/2015 08:03 AM, Michael S. Tsirkin wrote:
>>>
>>> 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@...in test]$ diff a.c b.c
>  31c31
>  <               if (__variable_test_bit(1, &addr))
>  ---
>  >               if (__constant_test_bit(1, &addr))
> 
> [mst@...in test]$ gcc -Wall -O2 a.c; time ./a.out
> 
> real    0m0.532s
> user    0m0.531s
> sys     0m0.000s
> [mst@...in 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
> 

I think this is well understood.  The use of bts/btc in locked
operations is sometimes justified since it reports the bit status back
out, whereas in unlocked operations bts/btc has no benefit except for
code size.  bt is a read operation, and is therefore "never/always"
atomic; it cannot be locked because there is no read/write pair to lock.

So it is strictly an issue of code size versus performance.

However, your test is simply faulty:

 804843f:	50                   	push   %eax
 8048440:	6a 01                	push   $0x1
 8048442:	e8 b4 ff ff ff       	call   80483fb <__variable_test_bit>

You're encapsulating the __variable_test_bit() version into an expensive
function call, whereas the __constant_test_bit() seems to emit code that
is quite frankly completely bonkers insane:

 8048444:	8b 45 ec             	mov    -0x14(%ebp),%eax
 8048447:	83 e0 1f             	and    $0x1f,%eax
 804844a:	89 c1                	mov    %eax,%ecx
 804844c:	d3 ea                	shr    %cl,%edx
 804844e:	89 d0                	mov    %edx,%eax
 8048450:	83 e0 01             	and    $0x1,%eax
 8048453:	85 c0                	test   %eax,%eax
 8048455:	0f 95 c0             	setne  %al
 8048458:	0f b6 c0             	movzbl %al,%eax
 804845b:	85 c0                	test   %eax,%eax
 804845d:	74 00                	je     804845f <main+0x64>

Observe the sequence and/test/setne/movzbl/test!

	-hpa


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/