* [PATCH] xfrm: branchless addr4_match() on 64-bit
@ 2017-03-23 23:32 Alexey Dobriyan
2017-03-24 17:16 ` David Laight
0 siblings, 1 reply; 6+ messages in thread
From: Alexey Dobriyan @ 2017-03-23 23:32 UTC (permalink / raw)
To: steffen.klassert; +Cc: herbert, davem, netdev
Current addr4_match() code has special test for /0 prefixes because of
standard required undefined behaviour. However, it is possible to omit
it on 64-bit because shifting can be done in a 64-bit register and then
truncated to the expected value (which is 0 mask).
Implicit truncation by htonl() fits nicely into R32-within-R64 model
on x86-64.
Space savings: none (coincidence)
Branch savings: 1
Before:
movzx eax,BYTE PTR [rdi+0x2a] # ->prefixlen_d
test al,al
jne xfrm_selector_match + 0x23f
...
movzx eax,BYTE PTR [rbx+0x2b] # ->prefixlen_s
test al,al
je xfrm_selector_match + 0x1c7
After (no branches):
mov r8d,0x20
mov rdx,0xffffffffffffffff
mov esi,DWORD PTR [rsi+0x2c]
mov ecx,r8d
sub cl,BYTE PTR [rdi+0x2a]
xor esi,DWORD PTR [rbx]
mov rdi,rdx
xor eax,eax
shl rdi,cl
bswap edi
Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
---
include/net/xfrm.h | 5 +++++
1 file changed, 5 insertions(+)
--- a/include/net/xfrm.h
+++ b/include/net/xfrm.h
@@ -844,10 +844,15 @@ static inline bool addr_match(const void *token1, const void *token2,
static inline bool addr4_match(__be32 a1, __be32 a2, u8 prefixlen)
{
+#ifdef CONFIG_64BIT
+ /* L in UL is not a typo. */
+ return !((a1 ^ a2) & htonl(~0UL << (32 - prefixlen)));
+#else
/* C99 6.5.7 (3): u32 << 32 is undefined behaviour */
if (prefixlen == 0)
return true;
return !((a1 ^ a2) & htonl(0xFFFFFFFFu << (32 - prefixlen)));
+#endif
}
static __inline__
^ permalink raw reply [flat|nested] 6+ messages in thread* RE: [PATCH] xfrm: branchless addr4_match() on 64-bit
2017-03-23 23:32 [PATCH] xfrm: branchless addr4_match() on 64-bit Alexey Dobriyan
@ 2017-03-24 17:16 ` David Laight
2017-03-25 16:37 ` Alexey Dobriyan
0 siblings, 1 reply; 6+ messages in thread
From: David Laight @ 2017-03-24 17:16 UTC (permalink / raw)
To: 'Alexey Dobriyan', steffen.klassert; +Cc: herbert, davem, netdev
From: Alexey Dobriyan
> Sent: 23 March 2017 23:33
> Current addr4_match() code has special test for /0 prefixes because of
> standard required undefined behaviour. However, it is possible to omit
> it on 64-bit because shifting can be done in a 64-bit register and then
> truncated to the expected value (which is 0 mask).
>
> Implicit truncation by htonl() fits nicely into R32-within-R64 model
> on x86-64.
...
> static inline bool addr4_match(__be32 a1, __be32 a2, u8 prefixlen)
> {
> +#ifdef CONFIG_64BIT
> + /* L in UL is not a typo. */
> + return !((a1 ^ a2) & htonl(~0UL << (32 - prefixlen)));
> +#else
> /* C99 6.5.7 (3): u32 << 32 is undefined behaviour */
> if (prefixlen == 0)
> return true;
> return !((a1 ^ a2) & htonl(0xFFFFFFFFu << (32 - prefixlen)));
> +#endif
Can't this just be written:
if (sizeof (long) == 4 && prefixlen == 0)
return true;
return !((a1 ^ a2) & htonl(0xFFFFFFFFUL << (32 - prefixlen)));
David
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] xfrm: branchless addr4_match() on 64-bit
2017-03-24 17:16 ` David Laight
@ 2017-03-25 16:37 ` Alexey Dobriyan
2017-03-25 16:41 ` [PATCH v2] " Alexey Dobriyan
0 siblings, 1 reply; 6+ messages in thread
From: Alexey Dobriyan @ 2017-03-25 16:37 UTC (permalink / raw)
To: David Laight; +Cc: steffen.klassert, herbert, davem, netdev
On Fri, Mar 24, 2017 at 05:16:44PM +0000, David Laight wrote:
> From: Alexey Dobriyan
> > Sent: 23 March 2017 23:33
> > Current addr4_match() code has special test for /0 prefixes because of
> > standard required undefined behaviour. However, it is possible to omit
> > it on 64-bit because shifting can be done in a 64-bit register and then
> > truncated to the expected value (which is 0 mask).
> >
> > Implicit truncation by htonl() fits nicely into R32-within-R64 model
> > on x86-64.
> ...
> > static inline bool addr4_match(__be32 a1, __be32 a2, u8 prefixlen)
> > {
> > +#ifdef CONFIG_64BIT
> > + /* L in UL is not a typo. */
> > + return !((a1 ^ a2) & htonl(~0UL << (32 - prefixlen)));
> > +#else
> > /* C99 6.5.7 (3): u32 << 32 is undefined behaviour */
> > if (prefixlen == 0)
> > return true;
> > return !((a1 ^ a2) & htonl(0xFFFFFFFFu << (32 - prefixlen)));
> > +#endif
>
> Can't this just be written:
>
> if (sizeof (long) == 4 && prefixlen == 0)
Indeed.
> return true;
> return !((a1 ^ a2) & htonl(0xFFFFFFFFUL << (32 - prefixlen)));
0xFFFFFFFFUL is really long movabs, ~0UL is better.
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH v2] xfrm: branchless addr4_match() on 64-bit
2017-03-25 16:37 ` Alexey Dobriyan
@ 2017-03-25 16:41 ` Alexey Dobriyan
2017-03-27 10:37 ` Steffen Klassert
0 siblings, 1 reply; 6+ messages in thread
From: Alexey Dobriyan @ 2017-03-25 16:41 UTC (permalink / raw)
To: steffen.klassert; +Cc: herbert, davem, netdev, David.Laight
Current addr4_match() code has special test for /0 prefixes because of
standard required undefined behaviour. However, it is possible to omit
it on 64-bit because shifting can be done within a 64-bit register and
then truncated to the expected value (which is 0 mask).
Implicit truncation by htonl() fits nicely into R32-within-R64 model
on x86-64.
Space savings: none (coincidence)
Branch savings: 1
Before:
movzx eax,BYTE PTR [rdi+0x2a] # ->prefixlen_d
test al,al
jne xfrm_selector_match + 0x23f
...
movzx eax,BYTE PTR [rbx+0x2b] # ->prefixlen_s
test al,al
je xfrm_selector_match + 0x1c7
After (no branches):
mov r8d,0x20
mov rdx,0xffffffffffffffff
mov esi,DWORD PTR [rsi+0x2c]
mov ecx,r8d
sub cl,BYTE PTR [rdi+0x2a]
xor esi,DWORD PTR [rbx]
mov rdi,rdx
xor eax,eax
shl rdi,cl
bswap edi
Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
---
include/net/xfrm.h | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
--- a/include/net/xfrm.h
+++ b/include/net/xfrm.h
@@ -845,9 +845,9 @@ static inline bool addr_match(const void *token1, const void *token2,
static inline bool addr4_match(__be32 a1, __be32 a2, u8 prefixlen)
{
/* C99 6.5.7 (3): u32 << 32 is undefined behaviour */
- if (prefixlen == 0)
+ if (sizeof(long) == 4 && prefixlen == 0)
return true;
- return !((a1 ^ a2) & htonl(0xFFFFFFFFu << (32 - prefixlen)));
+ return !((a1 ^ a2) & htonl(~0UL << (32 - prefixlen)));
}
static __inline__
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v2] xfrm: branchless addr4_match() on 64-bit
2017-03-25 16:41 ` [PATCH v2] " Alexey Dobriyan
@ 2017-03-27 10:37 ` Steffen Klassert
2017-03-27 13:11 ` Alexey Dobriyan
0 siblings, 1 reply; 6+ messages in thread
From: Steffen Klassert @ 2017-03-27 10:37 UTC (permalink / raw)
To: Alexey Dobriyan; +Cc: herbert, davem, netdev, David.Laight
On Sat, Mar 25, 2017 at 07:41:17PM +0300, Alexey Dobriyan wrote:
> Current addr4_match() code has special test for /0 prefixes because of
> standard required undefined behaviour. However, it is possible to omit
> it on 64-bit because shifting can be done within a 64-bit register and
> then truncated to the expected value (which is 0 mask).
>
> Implicit truncation by htonl() fits nicely into R32-within-R64 model
> on x86-64.
>
> Space savings: none (coincidence)
> Branch savings: 1
>
> Before:
>
> movzx eax,BYTE PTR [rdi+0x2a] # ->prefixlen_d
> test al,al
> jne xfrm_selector_match + 0x23f
> ...
> movzx eax,BYTE PTR [rbx+0x2b] # ->prefixlen_s
> test al,al
> je xfrm_selector_match + 0x1c7
>
> After (no branches):
>
> mov r8d,0x20
> mov rdx,0xffffffffffffffff
> mov esi,DWORD PTR [rsi+0x2c]
> mov ecx,r8d
> sub cl,BYTE PTR [rdi+0x2a]
> xor esi,DWORD PTR [rbx]
> mov rdi,rdx
> xor eax,eax
> shl rdi,cl
> bswap edi
>
> Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
Also applied to ipsec-next, thanks for the patches Alexey!
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2] xfrm: branchless addr4_match() on 64-bit
2017-03-27 10:37 ` Steffen Klassert
@ 2017-03-27 13:11 ` Alexey Dobriyan
0 siblings, 0 replies; 6+ messages in thread
From: Alexey Dobriyan @ 2017-03-27 13:11 UTC (permalink / raw)
To: Steffen Klassert; +Cc: herbert, davem, netdev, David Laight
On Mon, Mar 27, 2017 at 1:37 PM, Steffen Klassert
<steffen.klassert@secunet.com> wrote:
> On Sat, Mar 25, 2017 at 07:41:17PM +0300, Alexey Dobriyan wrote:
>> After (no branches):
>>
>> mov r8d,0x20
>> mov rdx,0xffffffffffffffff
>> mov esi,DWORD PTR [rsi+0x2c]
>> mov ecx,r8d
>> sub cl,BYTE PTR [rdi+0x2a]
>> xor esi,DWORD PTR [rbx]
>> mov rdi,rdx
>> xor eax,eax
>> shl rdi,cl
>> bswap edi
>>
>> Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
>
> Also applied to ipsec-next, thanks for the patches Alexey!
Speaking of optimizations.
1) All those ntohl() invocations inside hashes are likely
unnecessary (hashing is hashing after all).
2) I din't look closely but it can be further optimized by storing
32 - prefixlen (or 128 - prefixlen) but I don't know if you'll accept
such horror. :-)
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2017-03-27 13:11 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-03-23 23:32 [PATCH] xfrm: branchless addr4_match() on 64-bit Alexey Dobriyan
2017-03-24 17:16 ` David Laight
2017-03-25 16:37 ` Alexey Dobriyan
2017-03-25 16:41 ` [PATCH v2] " Alexey Dobriyan
2017-03-27 10:37 ` Steffen Klassert
2017-03-27 13:11 ` Alexey Dobriyan
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.