Skip to contentSkip to conversation

crypto: arm/chacha-neon - optimize for non-block size multiples

PATCH In review Ard Biesheuvel 3 participants 5 messages Nov 3, 2020 – Dec 12, 2020

Subsystems (2)
Arm (32-bit) Crypto API
lore
Share & tools
lore

Ard Biesheuvel

author
#0 lore raw

PATCH v2 1/1 crypto: arm/chacha-neon - optimize for non-block size multiples

The current NEON based ChaCha implementation for ARM is optimized for multiples of 4x the ChaCha block size (64 bytes). This makes sense for block encryption, but given that ChaCha is also often used in the context of networking, it makes sense to consider arbitrary length inputs as well.

For example, WireGuard typically uses 1420 byte packets, and performing ChaCha encryption involves 5 invocations of chacha_4block_xor_neon() and 3 invocations of chacha_block_xor_neon(), where the last one also involves a memcpy() using a buffer on the stack to process the final chunk of 1420 % 64 == 12 bytes.

Let's optimize for this case as well, by letting chacha_4block_xor_neon() deal with any input size between 64 and 256 bytes, using NEON permutation instructions and overlapping loads and stores. This way, the 140 byte tail of a 1420 byte input buffer can simply be processed in one go.

This results in the following performance improvements for 1420 byte blocks, without significant impact on power-of-2 input sizes. (Note that Raspberry Pi is widely used in combination with a 32-bit kernel, even though the core is 64-bit capable)

   Cortex-A8  (BeagleBone)       :   7%
   Cortex-A15 (Calxeda Midway)   :  21%
   Cortex-A53 (Raspberry Pi 3)   :   3%
   Cortex-A72 (Raspberry Pi 4)   :  19%
Cc Eric Biggers <[email protected]>
Cc "Jason A . Donenfeld" <[email protected]>
Signed-off-by Ard Biesheuvel <[email protected]>

---
v2:
- avoid memcpy() if the residual byte count is exactly 64 bytes
- get rid of register based post increments, and simply rewind the src pointer as needed (the dst pointer did not need the register post increment in the first place)
- add benchmark results for 32-bit CPUs to commit log.

 arch/arm/crypto/chacha-glue.c      | 34 +++----
 arch/arm/crypto/chacha-neon-core.S | 97 ++++++++++++++++++--
 2 files changed, 107 insertions(+), 24 deletions(-)
arch/arm/crypto/chacha-glue.c +17 -17
index 59da6c0b63b6..7b5cf8430c6d 100644
@@ -23,7 +23,7 @@
 asmlinkage void chacha_block_xor_neon(const u32 *state, u8 *dst, const u8 *src,
 				      int nrounds);
 asmlinkage void chacha_4block_xor_neon(const u32 *state, u8 *dst, const u8 *src,
-				       int nrounds);
+				       int nrounds, unsigned int nbytes);
 asmlinkage void hchacha_block_arm(const u32 *state, u32 *out, int nrounds);
 asmlinkage void hchacha_block_neon(const u32 *state, u32 *out, int nrounds);
 

@@ -42,24 +42,24 @@ static void chacha_doneon(u32 *state, u8 *dst, const u8 *src,
 {
 	u8 buf[CHACHA_BLOCK_SIZE];
 
-	while (bytes >= CHACHA_BLOCK_SIZE * 4) {
-		chacha_4block_xor_neon(state, dst, src, nrounds);
-		bytes -= CHACHA_BLOCK_SIZE * 4;
-		src += CHACHA_BLOCK_SIZE * 4;
-		dst += CHACHA_BLOCK_SIZE * 4;
-		state[12] += 4;
-	}
-	while (bytes >= CHACHA_BLOCK_SIZE) {
-		chacha_block_xor_neon(state, dst, src, nrounds);
-		bytes -= CHACHA_BLOCK_SIZE;
-		src += CHACHA_BLOCK_SIZE;
-		dst += CHACHA_BLOCK_SIZE;
-		state[12]++;
+	while (bytes > CHACHA_BLOCK_SIZE) {
+		unsigned int l = min(bytes, CHACHA_BLOCK_SIZE * 4U);
+
+		chacha_4block_xor_neon(state, dst, src, nrounds, l);
+		bytes -= l;
+		src += l;
+		dst += l;
+		state[12] += DIV_ROUND_UP(l, CHACHA_BLOCK_SIZE);
 	}
 	if (bytes) {
-		memcpy(buf, src, bytes);
-		chacha_block_xor_neon(state, buf, buf, nrounds);
-		memcpy(dst, buf, bytes);
+		const u8 *s = src;
+		u8 *d = dst;
+
+		if (bytes != CHACHA_BLOCK_SIZE)
+			s = d = memcpy(buf, src, bytes);
+		chacha_block_xor_neon(state, d, s, nrounds);
+		if (d != dst)
+			memcpy(dst, buf, bytes);
 	}
 }
arch/arm/crypto/chacha-neon-core.S +90 -7

167 lines not on this page · raw message

Signature · 1 line
2.17.1
maintainer
#1 lore raw
Quoted 38 lines · Ard Biesheuvel

The current NEON based ChaCha implementation for ARM is optimized for multiples of 4x the ChaCha block size (64 bytes). This makes sense for block encryption, but given that ChaCha is also often used in the context of networking, it makes sense to consider arbitrary length inputs as well.

For example, WireGuard typically uses 1420 byte packets, and performing ChaCha encryption involves 5 invocations of chacha_4block_xor_neon() and 3 invocations of chacha_block_xor_neon(), where the last one also involves a memcpy() using a buffer on the stack to process the final chunk of 1420 % 64 == 12 bytes.

Let's optimize for this case as well, by letting chacha_4block_xor_neon() deal with any input size between 64 and 256 bytes, using NEON permutation instructions and overlapping loads and stores. This way, the 140 byte tail of a 1420 byte input buffer can simply be processed in one go.

This results in the following performance improvements for 1420 byte blocks, without significant impact on power-of-2 input sizes. (Note that Raspberry Pi is widely used in combination with a 32-bit kernel, even though the core is 64-bit capable)

   Cortex-A8  (BeagleBone)       :   7%
   Cortex-A15 (Calxeda Midway)   :  21%
   Cortex-A53 (Raspberry Pi 3)   :   3%
   Cortex-A72 (Raspberry Pi 4)   :  19%
Cc Eric Biggers <[email protected]>
Cc "Jason A . Donenfeld" <[email protected]>
Signed-off-by Ard Biesheuvel <[email protected]>

---
v2:
- avoid memcpy() if the residual byte count is exactly 64 bytes
- get rid of register based post increments, and simply rewind the src pointer as needed (the dst pointer did not need the register post increment in the first place)
- add benchmark results for 32-bit CPUs to commit log.

Quoted 3 lines
 arch/arm/crypto/chacha-glue.c      | 34 +++----
 arch/arm/crypto/chacha-neon-core.S | 97 ++++++++++++++++++--
 2 files changed, 107 insertions(+), 24 deletions(-)

Patch applied. Thanks.

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
#2 lore raw
In reply to Ard Biesheuvel

Hi Ard,

Quoted 31 lines · Ard Biesheuvel
arch/arm/crypto/chacha-glue.c +9 -16
@@ -42,24 +42,24 @@ static void chacha_doneon(u32 *state, u8 *dst, const u8 *src,
 {
 	u8 buf[CHACHA_BLOCK_SIZE];
 
-	while (bytes >= CHACHA_BLOCK_SIZE * 4) {
-		chacha_4block_xor_neon(state, dst, src, nrounds);
-		bytes -= CHACHA_BLOCK_SIZE * 4;
-		src += CHACHA_BLOCK_SIZE * 4;
-		dst += CHACHA_BLOCK_SIZE * 4;
-		state[12] += 4;
-	}
-	while (bytes >= CHACHA_BLOCK_SIZE) {
-		chacha_block_xor_neon(state, dst, src, nrounds);
-		bytes -= CHACHA_BLOCK_SIZE;
-		src += CHACHA_BLOCK_SIZE;
-		dst += CHACHA_BLOCK_SIZE;
-		state[12]++;
+	while (bytes > CHACHA_BLOCK_SIZE) {
+		unsigned int l = min(bytes, CHACHA_BLOCK_SIZE * 4U);
+
+		chacha_4block_xor_neon(state, dst, src, nrounds, l);
+		bytes -= l;
+		src += l;
+		dst += l;
+		state[12] += DIV_ROUND_UP(l, CHACHA_BLOCK_SIZE);
 	}
 	if (bytes) {
-		memcpy(buf, src, bytes);
-		chacha_block_xor_neon(state, buf, buf, nrounds);
-		memcpy(dst, buf, bytes);
+		const u8 *s = src;

arch/arm/crypto/chacha-glue.c static void chacha_doneon(u32 *state, u8 *dst, const u8 *src, · line 65

Quoted 10 lines
arch/arm/crypto/chacha-glue.c +7 -0
+		u8 *d = dst;
+
+		if (bytes != CHACHA_BLOCK_SIZE)
+			s = d = memcpy(buf, src, bytes);
+		chacha_block_xor_neon(state, d, s, nrounds);
+		if (d != dst)
+			memcpy(dst, buf, bytes);
 	}
 }

Shouldn't this be incrementing the block counter after chacha_block_xor_neon()? It might be needed by the library API.

Also, even with that fixed, this patch is causing the self-tests (both the chacha20poly1305_selftest(), and the crypto API tests for chacha20-neon, xchacha20-neon, and xchacha12-neon) to fail when I boot a kernel in QEMU. This doesn't happen on real hardware (Raspberry Pi 2), and I don't see any other bugs in this patch, so I'm not sure what the problem is. Did you run the self-tests on every platform you tested this on?

- Eric

author
#3 lore raw
Quoted 40 lines · Eric Biggers

Hi Ard,

Quoted 36 lines · Ard Biesheuvel
arch/arm/crypto/chacha-glue.c +14 -16
@@ -42,24 +42,24 @@ static void chacha_doneon(u32 *state, u8 *dst, const u8 *src,
 {
      u8 buf[CHACHA_BLOCK_SIZE];
 
-     while (bytes >= CHACHA_BLOCK_SIZE * 4) {
-             chacha_4block_xor_neon(state, dst, src, nrounds);
-             bytes -= CHACHA_BLOCK_SIZE * 4;
-             src += CHACHA_BLOCK_SIZE * 4;
-             dst += CHACHA_BLOCK_SIZE * 4;
-             state[12] += 4;
-     }
-     while (bytes >= CHACHA_BLOCK_SIZE) {
-             chacha_block_xor_neon(state, dst, src, nrounds);
-             bytes -= CHACHA_BLOCK_SIZE;
-             src += CHACHA_BLOCK_SIZE;
-             dst += CHACHA_BLOCK_SIZE;
-             state[12]++;
+     while (bytes > CHACHA_BLOCK_SIZE) {
+             unsigned int l = min(bytes, CHACHA_BLOCK_SIZE * 4U);
+
+             chacha_4block_xor_neon(state, dst, src, nrounds, l);
+             bytes -= l;
+             src += l;
+             dst += l;
+             state[12] += DIV_ROUND_UP(l, CHACHA_BLOCK_SIZE);
      }
      if (bytes) {
-             memcpy(buf, src, bytes);
-             chacha_block_xor_neon(state, buf, buf, nrounds);
-             memcpy(dst, buf, bytes);
+             const u8 *s = src;
+             u8 *d = dst;
+
+             if (bytes != CHACHA_BLOCK_SIZE)
+                     s = d = memcpy(buf, src, bytes);
+             chacha_block_xor_neon(state, d, s, nrounds);
Quoted 9 lines

arch/arm/crypto/chacha-glue.c static void chacha_doneon(u32 *state, u8 *dst, const u8 *src, · line 65

Quoted 5 lines
arch/arm/crypto/chacha-glue.c +2 -0
+             if (d != dst)
+                     memcpy(dst, buf, bytes);
      }
 }

Shouldn't this be incrementing the block counter after chacha_block_xor_neon()? It might be needed by the library API.

Yeah, good point. 'bytes' could be exactly CHACHA_BLOCK_SIZE now, which wasn't the case before.

I'll send a fix.

Quoted 7 lines

Also, even with that fixed, this patch is causing the self-tests (both the chacha20poly1305_selftest(), and the crypto API tests for chacha20-neon, xchacha20-neon, and xchacha12-neon) to fail when I boot a kernel in QEMU. This doesn't happen on real hardware (Raspberry Pi 2), and I don't see any other bugs in this patch, so I'm not sure what the problem is. Did you run the self-tests on every platform you tested this on?

Does your QEMU lack this patch? I found that bug working on this code.

https://git.qemu.org/?p=qemu.git;a=commitdiff;h=604cef3e57eaeeef77074d78f6cf2eca1be11c62

_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

#4 lore raw
Quoted 64 lines · Ard Biesheuvel
Quoted 40 lines · Eric Biggers

Hi Ard,

Quoted 36 lines · Ard Biesheuvel
arch/arm/crypto/chacha-glue.c +14 -16
@@ -42,24 +42,24 @@ static void chacha_doneon(u32 *state, u8 *dst, const u8 *src,
 {
      u8 buf[CHACHA_BLOCK_SIZE];
 
-     while (bytes >= CHACHA_BLOCK_SIZE * 4) {
-             chacha_4block_xor_neon(state, dst, src, nrounds);
-             bytes -= CHACHA_BLOCK_SIZE * 4;
-             src += CHACHA_BLOCK_SIZE * 4;
-             dst += CHACHA_BLOCK_SIZE * 4;
-             state[12] += 4;
-     }
-     while (bytes >= CHACHA_BLOCK_SIZE) {
-             chacha_block_xor_neon(state, dst, src, nrounds);
-             bytes -= CHACHA_BLOCK_SIZE;
-             src += CHACHA_BLOCK_SIZE;
-             dst += CHACHA_BLOCK_SIZE;
-             state[12]++;
+     while (bytes > CHACHA_BLOCK_SIZE) {
+             unsigned int l = min(bytes, CHACHA_BLOCK_SIZE * 4U);
+
+             chacha_4block_xor_neon(state, dst, src, nrounds, l);
+             bytes -= l;
+             src += l;
+             dst += l;
+             state[12] += DIV_ROUND_UP(l, CHACHA_BLOCK_SIZE);
      }
      if (bytes) {
-             memcpy(buf, src, bytes);
-             chacha_block_xor_neon(state, buf, buf, nrounds);
-             memcpy(dst, buf, bytes);
+             const u8 *s = src;
+             u8 *d = dst;
+
+             if (bytes != CHACHA_BLOCK_SIZE)
+                     s = d = memcpy(buf, src, bytes);
+             chacha_block_xor_neon(state, d, s, nrounds);
Quoted 9 lines

arch/arm/crypto/chacha-glue.c static void chacha_doneon(u32 *state, u8 *dst, const u8 *src, · line 65

Quoted 5 lines
arch/arm/crypto/chacha-glue.c +2 -0
+             if (d != dst)
+                     memcpy(dst, buf, bytes);
      }
 }

Shouldn't this be incrementing the block counter after chacha_block_xor_neon()? It might be needed by the library API.

Yeah, good point. 'bytes' could be exactly CHACHA_BLOCK_SIZE now, which wasn't the case before.

I'll send a fix.

Quoted 7 lines

Also, even with that fixed, this patch is causing the self-tests (both the chacha20poly1305_selftest(), and the crypto API tests for chacha20-neon, xchacha20-neon, and xchacha12-neon) to fail when I boot a kernel in QEMU. This doesn't happen on real hardware (Raspberry Pi 2), and I don't see any other bugs in this patch, so I'm not sure what the problem is. Did you run the self-tests on every platform you tested this on?

Quoted 3 lines

Does your QEMU lack this patch? I found that bug working on this code.

https://git.qemu.org/?p=qemu.git;a=commitdiff;h=604cef3e57eaeeef77074d78f6cf2eca1be11c62

It doesn't have that patch. That must be the problem then; good to hear that you've already fixed it.

- Eric

_______________________________________________
linux-arm-kernel mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel