crypto: ecc - Optimize vli additive operations using compiler builtins
Subsystems (2)
PATCH 1/1 crypto: ecc - Optimize vli additive operations using compiler builtins
Replace the software carry flag emulation with compiler builtins.
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
This yields an approximately 6-7% performance improvement on the ecc_gen_privkey, ecc_make_pub_key and crypto_ecdh_shared_secret functions on x86_64 on all curve sizes.
Additionally, the code becomes much more readable.
---
Hi,
I'd like to expand on the benchmarks, compare the generated assembly, and clarify some things.
Use of compiler builtins:
This patch uses __builtin_addcll, __builtin_subcll when available and otherwise __builtin_uaddll_overflow, __builtin_usubll_overflow. the latter have existed since ancient gcc versions, so no third fallback is needed.
I have put the add_carry and sub_borrow inline functions with the preprocessor logic for builtin selection directly in crypto/ecc.c. Please let me know if you would like them to be somewhere else.
They do not emit data-dependent branches, and so remain constant-time.
Benchmarks:
All benchmarks were run single-threaded on my AMD 7700X CPU limited to 5.6Ghz. I have measured both nanoseconds and clock cycles, since their combination can hint at downclocking issues and allows calculation of the clock speed during the benchmark.
I have omitted the raw output from the benchmarking code, as they much exceed the 72 character limit.
I have calculated the percent differences, included clock speed calculations and relevant summaries.
Macro benchmarks:
These were run in a virtualized environment using virtme-ng on the compiled linux kernel image compiled with default flags.
(the first value is the original time per operation, the second the patched one. cc is short for clock cycles)
Curve keypair generation (ecc_gen_privkey + ecc_make_pub_key):
P256:
- 646963ns/op -> 600632ns/op = -7.71%
- 2911300cc/op -> 2702854cc/op = -7.71%
- 4.4999Ghz -> 4.5000Ghz = no difference
P384:
- 1239160ns/op -> 1153940ns/op = -7.38%
- 5576250cc/op -> 5192749cc/op = -7.38%
- 4.5000Ghz -> 4.5000Ghz = no difference
Shared secret generation (crypto_ecdh_shared_secret):
P256:
- 320114ns/op -> 297548ns/op = -7.58%
- 1440521cc/op -> 1338972cc/op = -7.58%
- 4.5000Ghz -> 4.5000Ghz = no difference
P384:
- 620768ns/op -> 582560ns/op = -6.55%
- 2793467cc/op -> 2621529cc/op = -6.55%
- 4.5000Ghz -> 4.5000Ghz = no difference
The benchmarks clearly indicate a roughly 6-7% performance increase on the public API functions. It also appears that virtme-ng limited the clock speed to 4.5Ghz
Micro benchmarks:
Since the vli additive functions only rely on u64 being defined, these were run without virtualization and with varying compilers and compiler flags.
The microbenchmarks show much more mixed results, depending heavily on the compiler and optimization level used.
For instance, on gcc and O2, the vli_add present in the patch is actually 25.3% slower than the original one. I have tracked this down to gcc using a weird way to restore the carry flag after each iteration, causing way more dependent instructions, preventing ILP from executing multiple at once.
This is quite interesting, since, as far as I know, the kernel compiles with gcc and O2 by default, yet the macro-level benchmarks still show a performance increase. The effect seems to be reversed when crypto/ecc.c gets compiled. Or maybe the linux kernel uses some additional optimization flags, I am unsure.
However, most of the time, the patched version outperforms the original one by a wide margin:
- On clang -O2 or -O3, vli_add and vli_uadd show a 4.074x and 5.384x speedup.
- On gcc, vli_uadd shows a 74% performance increase at O2, and a 2.07x speedup at O3.
The performance profile of vli_sub and vli_usub is almost identical to that of vli_add and vli_uadd.
Assembly comparison:
I have put together a piece of code on Compiler explorer, to make sure it compiles on old gcc versions, view instructions and play around with compiler settings.
If you would like, you can play around yourself here:
https://godbolt.org/z/1jT5zesz8
When using clang 22.1 at -O3 -march=lunarlake, the difference between the patched and original version is particularly clear. The patched version produces this assembly in the unrolled vli_add loop:
mov rax, qword ptr [rsi + 8*rcx + 16] adc rax, qword ptr [rdx + 8*rcx + 16] mov qword ptr [rdi + 8*rcx + 16], rax mov rax, qword ptr [rsi + 8*rcx + 24] adc rax, qword ptr [rdx + 8*rcx + 24] mov qword ptr [rdi + 8*rcx + 24], rax mov rax, qword ptr [rsi + 8*rcx + 32] adc rax, qword ptr [rdx + 8*rcx + 32] mov qword ptr [rdi + 8*rcx + 32], rax mov rax, qword ptr [rsi + 8*rcx + 40] adc rax, qword ptr [rdx + 8*rcx + 40] mov qword ptr [rdi + 8*rcx + 40], rax mov rax, qword ptr [rsi + 8*rcx + 48] adc rax, qword ptr [rdx + 8*rcx + 48]
This is basically optimal for an inner loop. It's pure adc and mov instructions. The loop counting part is still nowhere near perfect, and still uses setc instructions. But it is still better than what the original version produces with the same compiler and flags:
mov r10, qword ptr [rsi + 8*rcx] lea r11, [r10 + rax] add r11, qword ptr [rdx + 8*rcx] xor ebx, ebx cmp r11, r10 setb bl cmove rbx, rax mov qword ptr [rdi + 8*rcx], r11 mov rax, qword ptr [rsi + 8*rcx + 8] lea r10, [rax + rbx] add r10, qword ptr [rdx + 8*rcx + 8] xor r11d, r11d cmp r10, rax setb r11b cmove r11, rbx mov qword ptr [rdi + 8*rcx + 8], r10 mov rax, qword ptr [rsi + 8*rcx + 16] lea r10, [rax + r11] add r10, qword ptr [rdx + 8*rcx + 16] xor ebx, ebx cmp r10, rax setb bl cmove rbx, r11 mov qword ptr [rdi + 8*rcx + 16], r10 mov rax, qword ptr [rsi + 8*rcx + 24] lea r10, [rax + rbx] add r10, qword ptr [rdx + 8*rcx + 24] xor r11d, r11d cmp r10, rax setb r11b cmove r11, rbx
This is downright horrendous. that entire block of processes only 4 limbs, thats 8 instructions per limb! The add instructions are also not adc instructions, showing that the carry flag is being fully emulated. This demonstrates how even on the newest compilers and at the highest optimization level, still cannot generate hardware carry chains without explicit use of builtins.
I should note that not just clang 22.1.0 with -O3 -march=lunarlake does this. Gcc and clang show this behaviour on every version i have tested, regardless of target architecture.
I am not very familiar with ARM or RISC-V assembly, but looking at compiler explorer, the effect clearly persists, and in the case of RISC-V actually gets much worse.
This affects all architectures across all compilers and compiler flags.
If you have gotten this far, thank you for reading this and I am looking forward to any feedback! If you would like any changes to this patch, I am very happy to send a v2.
crypto/ecc.c | 98 ++++++++++++++++++++++++++++++++-------------------- 1 file changed, 60 insertions(+), 38 deletions(-)
crypto/ecc.c +60 -38
@@ -279,6 +279,48 @@ static void vli_rshift1(u64 *vli, unsigned int ndigits) } } +#ifdef __has_builtin +#if __has_builtin (__builtin_addcll) +#define USE_BUILTIN_ADDC +#endif +#endif + +/* Computes result = left + right + carry_in and updates carry_out */ +static inline void add_carry (u64 left,u64 right,u64 *result,u64 carry_in, +u64 *carry_out) +{ +#ifdef USE_BUILTIN_ADDC + *result =__builtin_addcll (left, right, carry_in, carry_out); +#else +u64 sum1, sum2; +u64 c1 =__builtin_uaddll_overflow (left, right, &sum1); +u64 c2 =__builtin_uaddll_overflow (sum1, carry_in, &sum2); + *result = sum2; + *carry_out = c1 | c2; +#endif +} + +#ifdef __has_builtin +#if __has_builtin (__builtin_subcll) +#define USE_BUILTIN_SUBC +#endif +#endif + +/* Computes result = left - right - borrow_in and updates borrow_out */ +static inline void sub_borrow (u64 left,u64 right,u64 *result,u64 borrow_in, +u64 *borrow_out) +{ +#ifdef USE_BUILTIN_SUBC + *result =__builtin_subcll (left, right, borrow_in, borrow_out); +#else +u64 diff1, diff2; +u64 b1 =__builtin_usubll_overflow (left, right, &diff1); +u64 b2 =__builtin_usubll_overflow (diff1, borrow_in, &diff2); + *result = diff2; + *borrow_out = b1 | b2; +#endif +} +/* Computes result = left + right, returning carry. Can modify in place. */ static u64 vli_add (u64 *result,const u64 *left,const u64 *right,unsigned int ndigits)
@@ -286,15 +328,8 @@ static u64 vli_add(u64 *result, const u64 *left, const u64 *right,u64 carry =0 ;int i; -for (i =0 ; i < ndigits; i++) { -u64 sum; - - sum = left[i] + right[i] + carry; -if (sum != left[i]) - carry = (sum < left[i]); - - result[i] = sum; - } +for (i =0 ; i < ndigits; i++) +add_carry (left[i], right[i], &result[i], carry, &carry);return carry; }
@@ -303,40 +338,29 @@ static u64 vli_add(u64 *result, const u64 *left, const u64 *right,static u64 vli_uadd (u64 *result,const u64 *left,u64 right,unsigned int ndigits) { -u64 carry = right; +u64 carry;int i; -for (i =0 ; i < ndigits; i++) { -u64 sum; +if (ndigits ==0 ) +return right; - sum = left[i] + carry; -if (sum != left[i]) - carry = (sum < left[i]); -else - carry = !!carry; + carry =__builtin_uaddll_overflow (left[0 ], right, &result[0 ]); - result[i] = sum; - } +for (i =1 ; i < ndigits; i++) + carry =__builtin_uaddll_overflow (left[i], carry, &result[i]);return carry; }/* Computes result = left - right, returning borrow. Can modify in place. */ u64 vli_sub (u64 *result,const u64 *left,const u64 *right, -unsigned int ndigits) +unsigned int ndigits) {u64 borrow =0 ;int i; -for (i =0 ; i < ndigits; i++) { -u64 diff; - - diff = left[i] - right[i] - borrow; -if (diff != left[i]) - borrow = (diff > left[i]); - - result[i] = diff; - } +for (i =0 ; i < ndigits; i++) +sub_borrow (left[i], right[i], &result[i], borrow, &borrow);return borrow; }
@@ -344,20 +368,18 @@ EXPORT_SYMBOL(vli_sub);/* Computes result = left - right, returning borrow. Can modify in place. */ static u64 vli_usub (u64 *result,const u64 *left,u64 right, -unsigned int ndigits) +unsigned int ndigits) { -u64 borrow = right; +u64 borrow;int i; -for (i =0 ; i < ndigits; i++) { -u64 diff; +if (ndigits ==0 ) +return right; - diff = left[i] - borrow; -if (diff != left[i]) - borrow = (diff > left[i]); + borrow =__builtin_usubll_overflow (left[0 ], right, &result[0 ]); - result[i] = diff; - } +for (i =1 ; i < ndigits; i++) + borrow =__builtin_usubll_overflow (left[i], borrow, &result[i]);return borrow; }
Signature · 1 line
2.54.0
Stefan Berger
reviewerQuoted 5 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
It looks like you made vli_usub and vli_uadd constant-time now because otherwise the loops could be ended early once borrow == 0 or carry == 0 respectively. Are all the other functions that operate on the private keys constant-time?
Quoted 6 lines · Stefan Berger
Quoted 2 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Quoted 9 lines
Quoted 3 lines
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
It looks like you made
vli_usubandvli_uaddconstant-time now because otherwise the loops could be ended early once borrow == 0 or carry == 0 respectively. Are all the other functions that operate on the private keys constant-time?
Thanks for the reply,
My primary goal with this patch was performance optimization. I did not add early exiting because the original version didn't either.
To answer your question: No, some other functions in ecc.c are not constant-time. For example, vli_is_zero and vli_cmp both contain early exits.
My patch does remove the branches in the inner loop, however, the original ones were already constant-time in practice, because the compiler replaces the branches with cmov's.
I am happy to make any changes to this patch if you like. I could also look into making vli_cmp and vli_is_zero, or others constant-time in a future patch.
Stefan Berger
reviewerQuoted 22 lines · Fabian
Quoted 6 lines · Stefan Berger
Quoted 2 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Quoted 9 lines
Quoted 3 lines
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
It looks like you made
vli_usubandvli_uaddconstant-time now because otherwise the loops could be ended early once borrow == 0 or carry == 0 respectively. Are all the other functions that operate on the private keys constant-time?Thanks for the reply,
My primary goal with this patch was performance optimization. I did not add early exiting because the original version didn't either.
Quoted 7 lines
To answer your question: No, some other functions in
ecc.care not constant-time. For example,vli_is_zeroandvli_cmpboth contain early exits.Quoted 1 line
My patch does remove the branches in the inner loop,
however, the original ones were already constant-time in practice, because the compiler replaces the branches with cmov's.
Quoted 1 line
I am happy to make any changes to this patch if you like.
ecrdsa calls ecc_is_pubkey_valid_partial -> vli_mod_square_fast -> vli_mmod_fast and then may call vli_usub or vli_uadd via vli_mmod_special2 or vli_mmod_barret.
ecc_point_mult operates on a private key and will call vli_mmod_fast and for some non-NIST keys it may call either one of vli_usub or vli_uadd via vli_mmod_special2 or vli_mmod_barret.
Due to the private key operations it's probably better to keep the functions constant-time for now.
Quoted 2 lines
I could also look into making
vli_cmpandvli_is_zero, or others constant-time in a future patch.
I wonder whether it would be practical to suffix constant-time functions with _ct so that it becomes visible whether the call paths of functions operation on private keys only call _ct functions? Sometimes one could optimize functions shared by private and public key operations for performance -- call them with 'bool ct' in this case and suffix them with _oct (o=optimized + ct) indicating that they support both variants?
Quoted 38 lines · Stefan Berger
Quoted 22 lines · Fabian
Quoted 6 lines · Stefan Berger
Quoted 2 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Quoted 9 lines
Quoted 3 lines
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
It looks like you made
vli_usubandvli_uaddconstant-time now because otherwise the loops could be ended early once borrow == 0 or carry == 0 respectively. Are all the other functions that operate on the private keys constant-time?Thanks for the reply,
My primary goal with this patch was performance optimization. I did not add early exiting because the original version didn't either.
Quoted 7 lines
To answer your question: No, some other functions in
ecc.care not constant-time. For example,vli_is_zeroandvli_cmpboth contain early exits.Quoted 1 line
My patch does remove the branches in the inner loop,
however, the original ones were already constant-time in practice, because the compiler replaces the branches with cmov's.
Quoted 1 line
I am happy to make any changes to this patch if you like.
ecrdsa calls
ecc_is_pubkey_valid_partial->vli_mod_square_fast->vli_mmod_fastand then may callvli_usuborvli_uaddviavli_mmod_special2orvli_mmod_barret.
Quoted 6 lines
ecc_point_multoperates on a private key and will callvli_mmod_fastand for some non-NIST keys it may call either one ofvli_usuborvli_uaddviavli_mmod_special2orvli_mmod_barret.Due to the private key operations it's probably better to keep the functions constant-time for now.
Agreed.
Quoted 11 lines
Quoted 3 lines
I could also look into making
vli_cmpandvli_is_zero, or others constant-time in a future patch.I wonder whether it would be practical to suffix constant-time functions with
_ctso that it becomes visible whether the call paths of functions operation on private keys only call_ctfunctions? Sometimes one could optimize functions shared by private and public key operations for performance -- call them with 'bool ct' in this case and suffix them with_oct(o=optimized + ct) indicating that they support both variants?
I am unsure whether constant-time operations are even slower than early-exit variants by a significant margin. vli_uadd and vli_usub don't seem to be called that often anyways. I believe this probably doesn't justify the resulting binary size and complexity increase.
Let me know how you'd like to move forward.
Lukas Wunner
maintainerQuoted 4 lines · Fabian Blatter
This patch uses
__builtin_addcll,__builtin_subcllwhen available and otherwise__builtin_uaddll_overflow,__builtin_usubll_overflow. the latter have existed since ancient gcc versions, so no third fallback is needed.
crypto/ecc.c is derived from https://github.com/kmackay/micro-ecc/,
which seeks to be a portable ECC library. I suspect the portability goal is the reason why it doesn't take advantage of compiler builtins or other optimizations.
The kernel is much less encumbered, the minimum compiler versions are apparent from Documentation/process/changes.rst. If these compiler versions support the builtins you're using then everything should be alright.
Quoted 3 lines
I have put the
add_carryandsub_borrowinline functions with the preprocessor logic for builtin selection directly incrypto/ecc.c. Please let me know if you would like them to be somewhere else.
Seems reasonable to me.
Quoted 5 lines
This is quite interesting, since, as far as I know, the kernel compiles with gcc and O2 by default, yet the macro-level benchmarks still show a performance increase. The effect seems to be reversed when
crypto/ecc.cgets compiled. Or maybe the linux kernel uses some additional optimization flags, I am unsure.
You can compile the kernel with V=1 to see the full command line.
Quoted 6 lines
However, most of the time, the patched version outperforms the original one by a wide margin:
- On clang -O2 or -O3,vli_addandvli_uaddshow a 4.074x and 5.384x speedup.
- On gcc,vli_uaddshows a 74% performance increase at O2, and a 2.07x speedup at O3.
There is precedent in the tree for overriding the default -O2 with -O3, see lib/lz4/Makefile and arch/mips/vdso/Makefile.
It might be worth using that for crypto/ecc.c if it doesn't cause breakage and yields a significant speedup.
Quoted 3 lines
I am happy to make any changes to this patch if you like. I could also look into making
vli_cmpandvli_is_zero, or others constant-time in a future patch.
Your patch LGTM and I don't see a need for a v2.
Previously we discussed replacing the ECC point multiplication algorithm used by crypto/ecc.c with a newer constant time Montgomery ladder. If you are interested in continuing working on crypto/ecc.c, this might be a worthwhile topic:
https://lore.kernel.org/r/[email protected]/
Thanks,
Lukas
Quoted 4 lines · Lukas Wunner
The kernel is much less encumbered, the minimum compiler versions are apparent from
Documentation/process/changes.rst. If these compiler versions support the builtins you're using then everything should be alright.
Yes, I have tested this for both the clang and gcc minimum required versions.
Quoted 7 lines
Quoted 5 lines
This is quite interesting, since, as far as I know, the kernel compiles with gcc and O2 by default, yet the macro-level benchmarks still show a performance increase. The effect seems to be reversed when
crypto/ecc.cgets compiled. Or maybe the linux kernel uses some additional optimization flags, I am unsure.You can compile the kernel with V=1 to see the full command line.
I did this and it seems the kernel does not add any optimization flags that would seem to affect my code (other than of course -O2).
I have looked at the generated assembly again, and I've found the reason my code is faster in the kernel, but not in the micro-benchmarks at gcc -O2. The carry chains from the vli functions from my patched code are identical in the kernel & micro-benchmarks. However, for some reason, the original vli carry chains generate an extra cmov instruction in the kernel, but not in the micro-benchmark, causing an additional dependency chain for each limb. The original ecc.o object file is also ~10% bigger, which may be another factor.
Quoted 8 lines
Quoted 7 lines
However, most of the time, the patched version outperforms the original one by a wide margin:
- On clang -O2 or -O3,vli_addandvli_uaddshow a 4.074x and 5.384x speedup.
- On gcc,vli_uaddshows a 74% performance increase at O2, and a 2.07x speedup at O3.
Quoted 6 lines
There is precedent in the tree for overriding the default -O2 with -O3, see
lib/lz4/Makefileandarch/mips/vdso/Makefile.It might be worth using that for
crypto/ecc.cif it doesn't cause breakage and yields a significant speedup.
I believe this as well. The gcc -O2 code is still about ~3.5x slower than the gcc -O3 version from the microbenchmarks. What
code gcc -O3 will actually generate in the kernel is another thing, but I'm pretty certain it would improve performance further for the vli operations.
However, how this affects binary size, speed or even breakage in other areas is something entirely different.
Quoted 7 lines
Previously we discussed replacing the ECC point multiplication algorithm used by
crypto/ecc.cwith a newer constant time Montgomery ladder. If you are interested in continuing working oncrypto/ecc.c, this might be a worthwhile topic:
I will for sure look into this in the future, however, that would definitely take considerably more time.
Thanks for the reply,
Fabian
Quoted 6 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
Quoted 7 lines
This yields an approximately 6-7% performance improvement on the
ecc_gen_privkey,ecc_make_pub_keyandcrypto_ecdh_shared_secretfunctions onx86_64on all curve sizes.Additionally, the code becomes much more readable.
Signed-off-by Fabian Blatter <[email protected]>
Herbert Xu
maintainerQuoted 202 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
This yields an approximately 6-7% performance improvement on the
ecc_gen_privkey,ecc_make_pub_keyandcrypto_ecdh_shared_secretfunctions onx86_64on all curve sizes.Additionally, the code becomes much more readable.
Signed-off-by Fabian Blatter <[email protected]>---
Hi,
I'd like to expand on the benchmarks, compare the generated assembly, and clarify some things.
Use of compiler builtins:
This patch uses
__builtin_addcll,__builtin_subcllwhen available and otherwise__builtin_uaddll_overflow,__builtin_usubll_overflow. the latter have existed since ancient gcc versions, so no third fallback is needed.I have put the
add_carryandsub_borrowinline functions with the preprocessor logic for builtin selection directly incrypto/ecc.c. Please let me know if you would like them to be somewhere else.They do not emit data-dependent branches, and so remain constant-time.
Benchmarks:
All benchmarks were run single-threaded on my AMD 7700X CPU limited to 5.6Ghz. I have measured both nanoseconds and clock cycles, since their combination can hint at downclocking issues and allows calculation of the clock speed during the benchmark.
I have omitted the raw output from the benchmarking code, as they much exceed the 72 character limit.
I have calculated the percent differences, included clock speed calculations and relevant summaries.
Macro benchmarks:
These were run in a virtualized environment using virtme-ng on the compiled linux kernel image compiled with default flags.
(the first value is the original time per operation, the second the patched one. cc is short for clock cycles)
Curve keypair generation (
ecc_gen_privkey+ecc_make_pub_key):P256:
- 646963ns/op -> 600632ns/op = -7.71%
- 2911300cc/op -> 2702854cc/op = -7.71%
- 4.4999Ghz -> 4.5000Ghz = no differenceP384:
- 1239160ns/op -> 1153940ns/op = -7.38%
- 5576250cc/op -> 5192749cc/op = -7.38%
- 4.5000Ghz -> 4.5000Ghz = no differenceShared secret generation (
crypto_ecdh_shared_secret):P256:
- 320114ns/op -> 297548ns/op = -7.58%
- 1440521cc/op -> 1338972cc/op = -7.58%
- 4.5000Ghz -> 4.5000Ghz = no differenceP384:
- 620768ns/op -> 582560ns/op = -6.55%
- 2793467cc/op -> 2621529cc/op = -6.55%
- 4.5000Ghz -> 4.5000Ghz = no differenceThe benchmarks clearly indicate a roughly 6-7% performance increase on the public API functions. It also appears that virtme-ng limited the clock speed to 4.5Ghz
Micro benchmarks:
Since the vli additive functions only rely on u64 being defined, these were run without virtualization and with varying compilers and compiler flags.
The microbenchmarks show much more mixed results, depending heavily on the compiler and optimization level used.
For instance, on gcc and O2, the
vli_addpresent in the patch is actually 25.3% slower than the original one. I have tracked this down to gcc using a weird way to restore the carry flag after each iteration, causing way more dependent instructions, preventing ILP from executing multiple at once.This is quite interesting, since, as far as I know, the kernel compiles with gcc and O2 by default, yet the macro-level benchmarks still show a performance increase. The effect seems to be reversed when
crypto/ecc.cgets compiled. Or maybe the linux kernel uses some additional optimization flags, I am unsure.However, most of the time, the patched version outperforms the original one by a wide margin:
- On clang -O2 or -O3,vli_addandvli_uaddshow a 4.074x and 5.384x speedup.
- On gcc,vli_uaddshows a 74% performance increase at O2, and a 2.07x speedup at O3.The performance profile of
vli_subandvli_usubis almost identical to that ofvli_addandvli_uadd.Assembly comparison:
I have put together a piece of code on Compiler explorer, to make sure it compiles on old gcc versions, view instructions and play around with compiler settings.
If you would like, you can play around yourself here:
https://godbolt.org/z/1jT5zesz8When using clang 22.1 at -O3 -march=lunarlake, the difference between the patched and original version is particularly clear. The patched version produces this assembly in the unrolled
vli_addloop:mov rax, qword ptr [rsi + 8*rcx + 16] adc rax, qword ptr [rdx + 8*rcx + 16] mov qword ptr [rdi + 8*rcx + 16], rax mov rax, qword ptr [rsi + 8*rcx + 24] adc rax, qword ptr [rdx + 8*rcx + 24] mov qword ptr [rdi + 8*rcx + 24], rax mov rax, qword ptr [rsi + 8*rcx + 32] adc rax, qword ptr [rdx + 8*rcx + 32] mov qword ptr [rdi + 8*rcx + 32], rax mov rax, qword ptr [rsi + 8*rcx + 40] adc rax, qword ptr [rdx + 8*rcx + 40] mov qword ptr [rdi + 8*rcx + 40], rax mov rax, qword ptr [rsi + 8*rcx + 48] adc rax, qword ptr [rdx + 8*rcx + 48]This is basically optimal for an inner loop. It's pure adc and mov instructions. The loop counting part is still nowhere near perfect, and still uses setc instructions. But it is still better than what the original version produces with the same compiler and flags:
mov r10, qword ptr [rsi + 8*rcx] lea r11, [r10 + rax] add r11, qword ptr [rdx + 8*rcx] xor ebx, ebx cmp r11, r10 setb bl cmove rbx, rax mov qword ptr [rdi + 8*rcx], r11 mov rax, qword ptr [rsi + 8*rcx + 8] lea r10, [rax + rbx] add r10, qword ptr [rdx + 8*rcx + 8] xor r11d, r11d cmp r10, rax setb r11b cmove r11, rbx mov qword ptr [rdi + 8*rcx + 8], r10 mov rax, qword ptr [rsi + 8*rcx + 16] lea r10, [rax + r11] add r10, qword ptr [rdx + 8*rcx + 16] xor ebx, ebx cmp r10, rax setb bl cmove rbx, r11 mov qword ptr [rdi + 8*rcx + 16], r10 mov rax, qword ptr [rsi + 8*rcx + 24] lea r10, [rax + rbx] add r10, qword ptr [rdx + 8*rcx + 24] xor r11d, r11d cmp r10, rax setb r11b cmove r11, rbxThis is downright horrendous. that entire block of processes only 4 limbs, thats 8 instructions per limb! The add instructions are also not adc instructions, showing that the carry flag is being fully emulated. This demonstrates how even on the newest compilers and at the highest optimization level, still cannot generate hardware carry chains without explicit use of builtins.
I should note that not just clang 22.1.0 with -O3 -march=lunarlake does this. Gcc and clang show this behaviour on every version i have tested, regardless of target architecture.
I am not very familiar with ARM or RISC-V assembly, but looking at compiler explorer, the effect clearly persists, and in the case of RISC-V actually gets much worse.
This affects all architectures across all compilers and compiler flags.
Quoted 6 lines
If you have gotten this far, thank you for reading this and I am looking forward to any feedback! If you would like any changes to this patch, I am very happy to send a v2.
crypto/ecc.c | 98 ++++++++++++++++++++++++++++++++-------------------- 1 file changed, 60 insertions(+), 38 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
Quoted 208 lines · Herbert Xu
Quoted 206 lines · Fabian Blatter
Replace the software carry flag emulation with compiler builtins.
Even the newest compilers struggle with taking advantage of the hardware carry flag. Compiler builtins allow the compiler to much more easily achieve this while still remaining constant-time.
This yields an approximately 6-7% performance improvement on the
ecc_gen_privkey,ecc_make_pub_keyandcrypto_ecdh_shared_secretfunctions onx86_64on all curve sizes.Additionally, the code becomes much more readable.
Signed-off-by Fabian Blatter <[email protected]>---
Hi,
I'd like to expand on the benchmarks, compare the generated assembly, and clarify some things.
Use of compiler builtins:
This patch uses
__builtin_addcll,__builtin_subcllwhen available and otherwise__builtin_uaddll_overflow,__builtin_usubll_overflow. the latter have existed since ancient gcc versions, so no third fallback is needed.I have put the
add_carryandsub_borrowinline functions with the preprocessor logic for builtin selection directly incrypto/ecc.c. Please let me know if you would like them to be somewhere else.They do not emit data-dependent branches, and so remain constant-time.
Benchmarks:
All benchmarks were run single-threaded on my AMD 7700X CPU limited to 5.6Ghz. I have measured both nanoseconds and clock cycles, since their combination can hint at downclocking issues and allows calculation of the clock speed during the benchmark.
I have omitted the raw output from the benchmarking code, as they much exceed the 72 character limit.
I have calculated the percent differences, included clock speed calculations and relevant summaries.
Macro benchmarks:
These were run in a virtualized environment using virtme-ng on the compiled linux kernel image compiled with default flags.
(the first value is the original time per operation, the second the patched one. cc is short for clock cycles)
Curve keypair generation (
ecc_gen_privkey+ecc_make_pub_key):P256:
- 646963ns/op -> 600632ns/op = -7.71%
- 2911300cc/op -> 2702854cc/op = -7.71%
- 4.4999Ghz -> 4.5000Ghz = no differenceP384:
- 1239160ns/op -> 1153940ns/op = -7.38%
- 5576250cc/op -> 5192749cc/op = -7.38%
- 4.5000Ghz -> 4.5000Ghz = no differenceShared secret generation (
crypto_ecdh_shared_secret):P256:
- 320114ns/op -> 297548ns/op = -7.58%
- 1440521cc/op -> 1338972cc/op = -7.58%
- 4.5000Ghz -> 4.5000Ghz = no differenceP384:
- 620768ns/op -> 582560ns/op = -6.55%
- 2793467cc/op -> 2621529cc/op = -6.55%
- 4.5000Ghz -> 4.5000Ghz = no differenceThe benchmarks clearly indicate a roughly 6-7% performance increase on the public API functions. It also appears that virtme-ng limited the clock speed to 4.5Ghz
Micro benchmarks:
Since the vli additive functions only rely on u64 being defined, these were run without virtualization and with varying compilers and compiler flags.
The microbenchmarks show much more mixed results, depending heavily on the compiler and optimization level used.
For instance, on gcc and O2, the
vli_addpresent in the patch is actually 25.3% slower than the original one. I have tracked this down to gcc using a weird way to restore the carry flag after each iteration, causing way more dependent instructions, preventing ILP from executing multiple at once.This is quite interesting, since, as far as I know, the kernel compiles with gcc and O2 by default, yet the macro-level benchmarks still show a performance increase. The effect seems to be reversed when
crypto/ecc.cgets compiled. Or maybe the linux kernel uses some additional optimization flags, I am unsure.However, most of the time, the patched version outperforms the original one by a wide margin:
- On clang -O2 or -O3,vli_addandvli_uaddshow a 4.074x and 5.384x speedup.
- On gcc,vli_uaddshows a 74% performance increase at O2, and a 2.07x speedup at O3.The performance profile of
vli_subandvli_usubis almost identical to that ofvli_addandvli_uadd.Assembly comparison:
I have put together a piece of code on Compiler explorer, to make sure it compiles on old gcc versions, view instructions and play around with compiler settings.
If you would like, you can play around yourself here:
https://godbolt.org/z/1jT5zesz8When using clang 22.1 at -O3 -march=lunarlake, the difference between the patched and original version is particularly clear. The patched version produces this assembly in the unrolled
vli_addloop:mov rax, qword ptr [rsi + 8*rcx + 16] adc rax, qword ptr [rdx + 8*rcx + 16] mov qword ptr [rdi + 8*rcx + 16], rax mov rax, qword ptr [rsi + 8*rcx + 24] adc rax, qword ptr [rdx + 8*rcx + 24] mov qword ptr [rdi + 8*rcx + 24], rax mov rax, qword ptr [rsi + 8*rcx + 32] adc rax, qword ptr [rdx + 8*rcx + 32] mov qword ptr [rdi + 8*rcx + 32], rax mov rax, qword ptr [rsi + 8*rcx + 40] adc rax, qword ptr [rdx + 8*rcx + 40] mov qword ptr [rdi + 8*rcx + 40], rax mov rax, qword ptr [rsi + 8*rcx + 48] adc rax, qword ptr [rdx + 8*rcx + 48]This is basically optimal for an inner loop. It's pure adc and mov instructions. The loop counting part is still nowhere near perfect, and still uses setc instructions. But it is still better than what the original version produces with the same compiler and flags:
mov r10, qword ptr [rsi + 8*rcx] lea r11, [r10 + rax] add r11, qword ptr [rdx + 8*rcx] xor ebx, ebx cmp r11, r10 setb bl cmove rbx, rax mov qword ptr [rdi + 8*rcx], r11 mov rax, qword ptr [rsi + 8*rcx + 8] lea r10, [rax + rbx] add r10, qword ptr [rdx + 8*rcx + 8] xor r11d, r11d cmp r10, rax setb r11b cmove r11, rbx mov qword ptr [rdi + 8*rcx + 8], r10 mov rax, qword ptr [rsi + 8*rcx + 16] lea r10, [rax + r11] add r10, qword ptr [rdx + 8*rcx + 16] xor ebx, ebx cmp r10, rax setb bl cmove rbx, r11 mov qword ptr [rdi + 8*rcx + 16], r10 mov rax, qword ptr [rsi + 8*rcx + 24] lea r10, [rax + rbx] add r10, qword ptr [rdx + 8*rcx + 24] xor r11d, r11d cmp r10, rax setb r11b cmove r11, rbxThis is downright horrendous. that entire block of processes only 4 limbs, thats 8 instructions per limb! The add instructions are also not adc instructions, showing that the carry flag is being fully emulated. This demonstrates how even on the newest compilers and at the highest optimization level, still cannot generate hardware carry chains without explicit use of builtins.
I should note that not just clang 22.1.0 with -O3 -march=lunarlake does this. Gcc and clang show this behaviour on every version i have tested, regardless of target architecture.
I am not very familiar with ARM or RISC-V assembly, but looking at compiler explorer, the effect clearly persists, and in the case of RISC-V actually gets much worse.
This affects all architectures across all compilers and compiler flags.
If you have gotten this far, thank you for reading this and I am looking forward to any feedback! If you would like any changes to this patch, I am very happy to send a v2.
Quoted 8 lines
Quoted 2 lines
crypto/ecc.c | 98 ++++++++++++++++++++++++++++++++-------------------- 1 file changed, 60 insertions(+), 38 deletions(-)Patch applied. Thanks.
--
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Hi,
So about the rewrite of crypto/ecc.c to a constant-time Montgomery ladder, I'd like to just make sure it is still on the table.
I also have a few questions about the rewrite:
The paper (https://eprint.iacr.org/2020/956.pdf), which is mentioned in the conversation Lukas sent, uses a different type of curve than the current implementation. Is a rewrite using entirely different elliptic curves intended, or is there some other algorithm that should be used with the existing NIST curves?
The paper also talks about assembly and how to make it constant-time by avoiding memory operations
and doing everything in registers. Is it intended to be an Assembly implementation or is C acceptable? If it is Assembly, I could only reasonably contribute an x64 version.
Regards,
Fabian