Skip to contentSkip to conversation

xfrm: branchless addr4_match() on 64-bit

PATCH Superseded Alexey Dobriyan 3 participants 6 messages Mar 23, 2017 – Mar 27, 2017

Subsystems (3)
Networking Network drivers Networking IPsec
lore
Share & tools
lore

Alexey Dobriyan

author
#0 lore raw

PATCH 1/1 xfrm: branchless addr4_match() on 64-bit

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 <[email protected]>

---

 include/net/xfrm.h |    5 +++++
 1 file changed, 5 insertions(+)
include/net/xfrm.h +5 -0
@@ -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__
#1 lore raw

From: Alexey Dobriyan

Quoted 8 lines

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.

...

include/net/xfrm.h static inline bool addr_match(const void *token1, const void *token2, · line 855

Quoted 11 lines

static inline bool addr4_match(__be32 a1, __be32 a2, u8 prefixlen) {

include/net/xfrm.h +5 -0
+#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
author
#2 lore raw
Quoted 24 lines · David Laight

From: Alexey Dobriyan

Quoted 8 lines

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.

...

include/net/xfrm.h static inline bool addr_match(const void *token1, const void *token2, · line 855

Quoted 11 lines

static inline bool addr4_match(__be32 a1, __be32 a2, u8 prefixlen) {

include/net/xfrm.h +5 -0
+#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:

Quoted 1 line
  	if (sizeof (long) == 4 && prefixlen == 0)

Indeed.

Quoted 2 lines
  		return true;
	return !((a1 ^ a2) & htonl(0xFFFFFFFFUL << (32 - prefixlen)));

0xFFFFFFFFUL is really long movabs, ~0UL is better.

author
#3 lore raw

PATCH v2 1/1 xfrm: branchless addr4_match() on 64-bit

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 <[email protected]>

---

 include/net/xfrm.h |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/net/xfrm.h +2 -2
@@ -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__
maintainer
#4 lore raw
Quoted 34 lines · Alexey Dobriyan

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
Quoted 1 line
Signed-off-by Alexey Dobriyan <[email protected]>

Also applied to ipsec-next, thanks for the patches Alexey!

author
#5 lore raw
Quoted 14 lines · Steffen Klassert
Quoted 13 lines · Alexey Dobriyan

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
Quoted 3 lines
Quoted 1 line
Signed-off-by Alexey Dobriyan <[email protected]>

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. :-)