crypto: siphash - use _unaligned version by default
Subsystems (3)
PATCH 1/1 crypto: siphash - use _unaligned version by default
From: Arnd Bergmann <[email protected]>
On ARM v6 and later, we define CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS because the ordinary load/store instructions (ldr, ldrh, ldrb) can tolerate any misalignment of the memory address. However, load/store double and load/store multiple instructions (ldrd, ldm) may still only be used on memory addresses that are 32-bit aligned, and so we have to use the CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS macro with care, or we may end up with a severe performance hit due to alignment traps that require fixups by the kernel. Testing shows that this currently happens with clang-13 but not gcc-11. In theory, any compiler version can produce this bug or other problems, as we are dealing with undefined behavior in C99 even on architectures that support this in hardware, see also https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100363.
Fortunately, the get_unaligned() accessors do the right thing: when building for ARMv6 or later, the compiler will emit unaligned accesses using the ordinary load/store instructions (but avoid the ones that require 32-bit alignment). When building for older ARM, those accessors will emit the appropriate sequence of ldrb/mov/orr instructions. And on architectures that can truly tolerate any kind of misalignment, the get_unaligned() accessors resolve to the leXX_to_cpup accessors that operate on aligned addresses.
Since the compiler will in fact emit ldrd or ldm instructions when building this code for ARM v6 or later, the solution is to use the unaligned accessors unconditionally on architectures where this is known to be fast. The _aligned version of the hash function is however still needed to get the best performance on architectures that cannot do any unaligned access in hardware.
This new version avoids the undefined behavior and should produce the fastest hash on all architectures we support.
--- include/linux/siphash.h | 14 ++++---------- lib/siphash.c | 12 ++++++------ 2 files changed, 10 insertions(+), 16 deletions(-)
include/linux/siphash.h +4 -10
@@ -27,9 +27,7 @@ static inline bool siphash_key_is_zero(const siphash_key_t *key) }u64 __siphash_aligned (const void *data,size_t len,const siphash_key_t *key); -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u64 __siphash_unaligned (const void *data,size_t len,const siphash_key_t *key); -#endif u64 siphash_1u64 (const u64 a,const siphash_key_t *key);u64 siphash_2u64 (const u64 a,const u64 b,const siphash_key_t *key);
@@ -82,10 +80,9 @@ static inline u64 ___siphash_aligned(const __le64 *data, size_t len,static inline u64 siphash (const void *data,size_t len,const siphash_key_t *key) { -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS -if (!IS_ALIGNED ((unsigned long )data,SIPHASH_ALIGNMENT )) +if (IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) || + !IS_ALIGNED ((unsigned long )data,SIPHASH_ALIGNMENT ))return __siphash_unaligned (data, len, key); -#endif return ___siphash_aligned (data, len, key); }
@@ -96,10 +93,8 @@ typedef struct {u32 __hsiphash_aligned (const void *data,size_t len,const hsiphash_key_t *key); -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_unaligned (const void *data,size_t len,const hsiphash_key_t *key); -#endif u32 hsiphash_1u32 (const u32 a,const hsiphash_key_t *key);u32 hsiphash_2u32 (const u32 a,const u32 b,const hsiphash_key_t *key);
@@ -135,10 +130,9 @@ static inline u32 ___hsiphash_aligned(const __le32 *data, size_t len,static inline u32 hsiphash (const void *data,size_t len,const hsiphash_key_t *key) { -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS -if (!IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT )) +if (IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) || + !IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT ))return __hsiphash_unaligned (data, len, key); -#endif return ___hsiphash_aligned (data, len, key); }
lib/siphash.c +6 -6
@@ -49,6 +49,7 @@SIPROUND ; \return (v0 ^ v1) ^ (v2 ^ v3); +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u64 __siphash_aligned (const void *data,size_t len,const siphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u64));
@@ -80,8 +81,8 @@ u64 __siphash_aligned(const void *data, size_t len, const siphash_key_t *key)POSTAMBLE }EXPORT_SYMBOL (__siphash_aligned ); +#endif -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u64 __siphash_unaligned (const void *data,size_t len,const siphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u64));
@@ -113,7 +114,6 @@ u64 __siphash_unaligned(const void *data, size_t len, const siphash_key_t *key) POSTAMBLE }EXPORT_SYMBOL (__siphash_unaligned); -#endif /** * siphash_1u64 - compute 64-bit siphash PRF value of a u64
@@ -250,6 +250,7 @@ EXPORT_SYMBOL(siphash_3u32);HSIPROUND ; \return (v0 ^ v1) ^ (v2 ^ v3); +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_aligned (const void *data,size_t len,const hsiphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u64));
@@ -280,8 +281,8 @@ u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_aligned ); +#endif -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_unaligned (const void *data,size_t len,const hsiphash_key_t *key) {
@@ -313,7 +314,6 @@ u32 __hsiphash_unaligned(const void *data, size_t len, HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_unaligned); -#endif /** * hsiphash_1u32 - compute 64-bit hsiphash PRF value of a u32
@@ -418,6 +418,7 @@ EXPORT_SYMBOL(hsiphash_4u32);HSIPROUND ; \return v1 ^ v3; +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_aligned (const void *data,size_t len,const hsiphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u32));
@@ -438,8 +439,8 @@ u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_aligned ); +#endif -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_unaligned (const void *data,size_t len,const hsiphash_key_t *key) {
@@ -461,7 +462,6 @@ u32 __hsiphash_unaligned(const void *data, size_t len, HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_unaligned); -#endif /** * hsiphash_1u32 - compute 32-bit hsiphash PRF value of a u32
Signature · 1 line
2.29.2
Jason A. Donenfeld
maintainerHi Arnd,
It looks like Ard's old patch never got picked up so you're dusting it off. It looks like you're doing two things here -- moving from an ifndef to a much nicer IS_ENABLED, and changing the logic a bit. In trying to understand the logic part, I changed this in my buffer:
-#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
- if (!IS_ALIGNED((unsigned long)data, HSIPHASH_ALIGNMENT))
+ if (IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
+ !IS_ALIGNED((unsigned long)data, HSIPHASH_ALIGNMENT))
return __hsiphash_unaligned(data, len, key);
return ___hsiphash_aligned(data, len, key);into this:
- if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) &&
- !IS_ALIGNED((unsigned long)data, HSIPHASH_ALIGNMENT))
+ if (IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
+ !IS_ALIGNED((unsigned long)data, HSIPHASH_ALIGNMENT))
return __hsiphash_unaligned(data, len, key);
return ___hsiphash_aligned(data, len, key);This way I can actually think about what's happening here.
So with the old one, we use the faster aligned version if *either* the CPU has efficient unaligned access OR the bytes are statically known to be aligned. This seems sensible.
On the new one, we use the faster aligned version if *both* the bytes are statically known to be aligned (ok) AND the CPU doesn't actually support efficient unaligned accesses (?). This seems kind of weird.
It also means that CPUs with fast aligned accesses wind up calling the slower code path in some cases. Is your supposition that the compiler will always optimize the slow codepath to the fast one if the CPU it's compiling for supports that? Have you tested this on all platforms?
Would it make sense to instead just fix clang-13? Or even to just get rid of CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS for armv6 or undef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS for armv6 just in this file or maybe less messy, split CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS into two ifdefs that more sense for our usage?
Jason
Quoted 7 lines · Jason A. Donenfeld
Hi Arnd,
It looks like Ard's old patch never got picked up so you're dusting it off. It looks like you're doing two things here -- moving from an ifndef to a much nicer
IS_ENABLED, and changing the logic a bit. In trying to understand the logic part, I changed this in my buffer:
I actually found the issue independently and came up with this patch before Ard pointed me to his patch, I mainly took the description of the problem from him, as his explanation was already well written.
Quoted 18 lines
include/linux/siphash.h +2
-2-#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS -if (!IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT )) +if (IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) || + !IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT ))return __hsiphash_unaligned (data, len, key);return ___hsiphash_aligned (data, len, key);into this:
include/linux/siphash.h +2
-2-if (!IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) && - !IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT )) +if (IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) || + !IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT ))return __hsiphash_unaligned (data, len, key);return ___hsiphash_aligned (data, len, key);This way I can actually think about what's happening here.
Quoted 7 lines
So with the old one, we use the faster aligned version if *either* the CPU has efficient unaligned access OR the bytes are statically known to be aligned. This seems sensible.
On the new one, we use the faster aligned version if *both* the bytes are statically known to be aligned (ok) AND the CPU doesn't actually support efficient unaligned accesses (?). This seems kind of weird.
Yes, this is intentional. The point is that __hsiphash_unaligned() is the portable version that works with any alignment on any architecture, while __hsiphash_aligned() is either identical, or may only be called with aligned data. Passing an unaligned pointer into this function triggers undefined behavior in C99, which is how it broke on armv7, but in fact any compiler might optimize this function based on "knowing" that the lower address bits are zero.
Quoted 4 lines
It also means that CPUs with fast aligned accesses wind up calling the slower code path in some cases. Is your supposition that the compiler will always optimize the slow codepath to the fast one if the CPU it's compiling for supports that? Have you tested this on all platforms?
I have not tested this specific patch on all platforms, but I did extensive testing of the get_unaligned()/put_unaligned() helpers in my rewrite earlier this year[1], making sure that these are NOPs on all the important architectures, and that they prevent the use of trapping ldrd/ldm instructions on ARMv6/ARMv7.
Quoted 5 lines
Would it make sense to instead just fix clang-13? Or even to just get rid of
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESSfor armv6 or undefCONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESSfor armv6 just in this file or maybe less messy, splitCONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESSinto two ifdefs that more sense for our usage?
Clang is actually doing the right thing here, it may be considered a missed optimization that gcc uses two loads instead of a combined ldm or ldrd ;-)
FWIW, the bug that we saw in the decompressor relying on data alignment on x86 earlier this year only happened on gcc.
Arnd
Quoted 5 lines · Arnd Bergmann
I have not tested this specific patch on all platforms, but I did extensive testing of the get_unaligned()/put_unaligned() helpers in my rewrite earlier this year[1], making sure that these are NOPs on all the important architectures, and that they prevent the use of trapping ldrd/ldm instructions on ARMv6/ARMv7.
If you're confident that the codegen doesn't change for ARMv8 and x86{,_64}, then:
We should probably Cc stable@, right?
I'm preparing a patchset for DaveM's stable tree today, and I can take this in that patchset.
Jason
Quoted 11 lines · Jason A. Donenfeld
Quoted 5 lines · Arnd Bergmann
I have not tested this specific patch on all platforms, but I did extensive testing of the get_unaligned()/put_unaligned() helpers in my rewrite earlier this year[1], making sure that these are NOPs on all the important architectures, and that they prevent the use of trapping ldrd/ldm instructions on ARMv6/ARMv7.
If you're confident that the codegen doesn't change for ARMv8 and x86{,_64}, then:
Reviewed-by Jason A. Donenfeld <[email protected]>
Thanks
Quoted 1 line
We should probably Cc stable@, right?
Yes, I meant to add that but forgot.
Quoted 2 lines
I'm preparing a patchset for DaveM's stable tree today, and I can take this in that patchset.
It's not urgent, but I think we need to fix it and get it into stable kernels at some point. I'm happy with whatever timing works for you.
Arnd
Quoted 32 lines · Arnd Bergmann
From: Arnd Bergmann <[email protected]>
On ARM v6 and later, we define
CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESSbecause the ordinary load/store instructions (ldr, ldrh, ldrb) can tolerate any misalignment of the memory address. However, load/store double and load/store multiple instructions (ldrd, ldm) may still only be used on memory addresses that are 32-bit aligned, and so we have to use theCONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESSmacro with care, or we may end up with a severe performance hit due to alignment traps that require fixups by the kernel. Testing shows that this currently happens with clang-13 but not gcc-11. In theory, any compiler version can produce this bug or other problems, as we are dealing with undefined behavior in C99 even on architectures that support this in hardware, see also https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100363.Fortunately, the
get_unaligned()accessors do the right thing: when building for ARMv6 or later, the compiler will emit unaligned accesses using the ordinary load/store instructions (but avoid the ones that require 32-bit alignment). When building for older ARM, those accessors will emit the appropriate sequence of ldrb/mov/orr instructions. And on architectures that can truly tolerate any kind of misalignment, theget_unaligned()accessors resolve to theleXX_to_cpupaccessors that operate on aligned addresses.Since the compiler will in fact emit ldrd or ldm instructions when building this code for ARM v6 or later, the solution is to use the unaligned accessors unconditionally on architectures where this is known to be fast. The
_alignedversion of the hash function is however still needed to get the best performance on architectures that cannot do any unaligned access in hardware.
Quoted 7 lines
This new version avoids the undefined behavior and should produce the fastest hash on all architectures we support.
Reported-by Ard Biesheuvel <[email protected]>Fixes 2c956a60778c ("siphash: add cryptographically secure PRF")Signed-off-by Arnd Bergmann <[email protected]>
Quoted 141 lines
--- include/linux/siphash.h | 14 ++++---------- lib/siphash.c | 12 ++++++------ 2 files changed, 10 insertions(+), 16 deletions(-)include/linux/siphash.h +4
-10@@ -27,9 +27,7 @@ static inline bool siphash_key_is_zero(const siphash_key_t *key) }u64 __siphash_aligned (const void *data,size_t len,const siphash_key_t *key); -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u64 __siphash_unaligned (const void *data,size_t len,const siphash_key_t *key); -#endif u64 siphash_1u64 (const u64 a,const siphash_key_t *key);u64 siphash_2u64 (const u64 a,const u64 b,const siphash_key_t *key);@@ -82,10 +80,9 @@ static inline u64 ___siphash_aligned(const __le64 *data, size_t len,static inline u64 siphash (const void *data,size_t len,const siphash_key_t *key) { -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS -if (!IS_ALIGNED ((unsigned long )data,SIPHASH_ALIGNMENT )) +if (IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) || + !IS_ALIGNED ((unsigned long )data,SIPHASH_ALIGNMENT ))return __siphash_unaligned (data, len, key); -#endif return ___siphash_aligned (data, len, key); }@@ -96,10 +93,8 @@ typedef struct {u32 __hsiphash_aligned (const void *data,size_t len,const hsiphash_key_t *key); -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_unaligned (const void *data,size_t len,const hsiphash_key_t *key); -#endif u32 hsiphash_1u32 (const u32 a,const hsiphash_key_t *key);u32 hsiphash_2u32 (const u32 a,const u32 b,const hsiphash_key_t *key);@@ -135,10 +130,9 @@ static inline u32 ___hsiphash_aligned(const __le32 *data, size_t len,static inline u32 hsiphash (const void *data,size_t len,const hsiphash_key_t *key) { -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS -if (!IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT )) +if (IS_ENABLED (CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS ) || + !IS_ALIGNED ((unsigned long )data,HSIPHASH_ALIGNMENT ))return __hsiphash_unaligned (data, len, key); -#endif return ___hsiphash_aligned (data, len, key); }lib/siphash.c +6
-7@@ -49,6 +49,7 @@SIPROUND ; \return (v0 ^ v1) ^ (v2 ^ v3); +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u64 __siphash_aligned (const void *data,size_t len,const siphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u64));@@ -80,8 +81,8 @@ u64 __siphash_aligned(const void *data, size_t len, const siphash_key_t *key)POSTAMBLE }EXPORT_SYMBOL (__siphash_aligned ); +#endif -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u64 __siphash_unaligned (const void *data,size_t len,const siphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u64));@@ -113,7 +114,6 @@ u64 __siphash_unaligned(const void *data, size_t len, const siphash_key_t *key) POSTAMBLE }EXPORT_SYMBOL (__siphash_unaligned); -#endif /** * siphash_1u64 - compute 64-bit siphash PRF value of a u64 @@ -250,6 +250,7 @@ EXPORT_SYMBOL(siphash_3u32);HSIPROUND ; \return (v0 ^ v1) ^ (v2 ^ v3); +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_aligned (const void *data,size_t len,const hsiphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u64));@@ -280,8 +281,8 @@ u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_aligned ); +#endif -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_unaligned (const void *data,size_t len,const hsiphash_key_t *key) {@@ -313,7 +314,6 @@ u32 __hsiphash_unaligned(const void *data, size_t len, HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_unaligned); -#endif /** * hsiphash_1u32 - compute 64-bit hsiphash PRF value of a u32 @@ -418,6 +418,7 @@ EXPORT_SYMBOL(hsiphash_4u32);HSIPROUND ; \return v1 ^ v3; +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_aligned (const void *data,size_t len,const hsiphash_key_t *key) {const u8 *end = data + len - (len %sizeof (u32));@@ -438,8 +439,8 @@ u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_aligned ); +#endif -#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS u32 __hsiphash_unaligned (const void *data,size_t len,const hsiphash_key_t *key) {@@ -461,7 +462,6 @@ u32 __hsiphash_unaligned(const void *data, size_t len, HPOSTAMBLE }EXPORT_SYMBOL (__hsiphash_unaligned); -#endif /** * hsiphash_1u32 - compute 32-bit hsiphash PRF value of a u32 -- 2.29.2