Xxhash: Broken alignment assumption on armv6.

[plugwash]

Hi.

Recently apt started segfauling in raspbian bullseye environments on arm64 kernels.

I traced this to line 1607 of xxhash.h (line number based on the debian package)

Since armv6, arm has supported unaligned accesses through the regular ldr
and str instructions, however it does not support unaligned access for
other instructions. In this case the offending instruction being ldrd.

32-bit kernels will by default fixup unaligned accesses in the kernel, but
64-bit kernels will not (and to the best of my knowledge cannot be configured
to do so). Even if kernel fixups are operational they are likely to be far
far slower than direct access.

xxhash assumes that if __ARM_FEATURE_UNALIGNED is defined on armv6 then it
is safe to performed unaligned accesses through normal pointer dereferences.
This is not the case, because there is no guarantee that a pointer derefence
will translate into regular ldr/str instructions.

In raspbian I changed the value of XXH_FORCE_MEMORY_ACCESS on armv6
from 2 to 1 to fix this issue

[wtarreau]

We got the same report on haproxy (which embeds XXH64) and could diagnose the issue to be exactly the same, with the same conclusion: https://github.com/haproxy/haproxy/issues/1035.

It happens when users install armhf chroots on arm64. It doesn't seem common and above it was apparently an accident. But still it's a problem.

Yann, I managed to address it by splitting the unaligned condition in two (32 vs 64-bit). Since I'm only aware of ARM that's causing this trouble, I've explicitly tested this platform as not enabling the 64-bit unaligned when the 32-bit one is supported. It fixes the problem for me, but I couldn't change nor test the non-gcc cases as I'm not sure how they're supposed to work.

I'm attaching the patch which works for me, I'm going to merge it into haproxy for now, as I think it's reasonable and little-intrusive enough for such a rare case.

xxh64-fix-align2.diff.txt

[wtarreau]

By the way, this makes me realize that it's likely that xxh64 on 32-bit ARM probably does not run fast if it relies on kernel emulation. I can eventually test that if you're interested.

[Cyan4973]

Thanks @wtarreau , that's great feedback !

Sure, let's test that !

[wtarreau]

So I'm back with some tests.It's really not easy, because:

• I never can make it fail with gcc 6.3.1 nor gcc 4.7.4 but it does with gcc 9.3.0. I suspect the latter emits ldrd more easily than older ones, which may also be a reason why this issue only started to appear recently
• it stopped failing for me between r39 and r40 with commit 57fda00 ("sync with lz4 version"). Among the changes there is the way to access the unaligned data (memcpy() replaced the union), and even though it's not directly related since it's used only for unaligned-incompatible platforms, I suspect that different instruction scheduling consecutive to that large patch made the compiler lose the opportunity to use ldrd again.

I can confirm that on true armv7, it works only via kernel emulation (look at the DWord counter):

admin@clearfog:tmp$ cat /proc/cpu/alignment 
User:           5
System:         4 (msdos_partition+0x15e/0x494)
Skipped:        0
Half:           0
Word:           0
DWord:          0
Multi:          4
User faults:    2 (fixup)
admin@clearfog:tmp$ ./test-static 1 232222222222222222 456666666666666666
0: 0xbef58de2(./test-static) = 0xbf9004711c0f5e9a
1: 0xbef58df0(1) = 0xb7b41276360564d4
2: 0xbef58df2(232222222222222222) = 0xdbc65db8e2988bbe
3: 0xbef58e05(456666666666666666) = 0xb19e5aedb88f066b
admin@clearfog:tmp$ cat /proc/cpu/alignment 
User:           5
System:         4 (msdos_partition+0x15e/0x494)
Skipped:        0
Half:           0
Word:           0
DWord:          5
Multi:          4
User faults:    2 (fixup)
admin@clearfog:tmp$ ./test-static 1 232222222222222222 456666666666666666
0: 0xbef58de2(./test-static) = 0xbf9004711c0f5e9a
1: 0xbef58df0(1) = 0xb7b41276360564d4
2: 0xbef58df2(232222222222222222) = 0xdbc65db8e2988bbe
3: 0xbef58e05(456666666666666666) = 0xb19e5aedb88f066b
admin@clearfog:tmp$ cat /proc/cpu/alignment 
User:           10
System:         4 (msdos_partition+0x15e/0x494)
Skipped:        0
Half:           0
Word:           0
DWord:          10
Multi:          4
User faults:    2 (fixup)

The test code in question does this:

#include <inttypes.h>
#include <stdio.h>
#include <string.h>
#include "xxhash.h"

int main(int argc, char **argv)
{
        uint64_t h;
        int i;

        for (i = 0; i < argc; i++) {
                printf("%d: %p(%s) = ", i, argv[i], argv[i]);
                h = XXH64(argv[i], strlen(argv[i]), 0);
                printf("%#llx\n", (long long)h);
        }
        return 0;
}

My patch above applied on older r39 does obviously fix the issue, I haven't ported it to the newer versions since I cannot find the right combination of compiler and option to trigger it later :-/

We did have r39 embedded into stable haproxy versions, while latest one was upgraded to benefit from XXH3. However it would be nice to know which version the original reporter is using.

[Cyan4973]

I'm not surprised that old versions of xxhash get into such issues (r39 is from 2014),
and indeed, more recent versions are supposed to be safer in this regards.

However, "safer" is not "perfect", and it's possible to imagine issues with less common architectures, that deserve to be tested.

The issue underlined here is that the code generated for ARMv6, when compiled using gcc, and when __ARM_FEATURE_UNALIGNED is enabled, trusts that loading unaligned memory will work fine.
Unfortunately, this is only true if a normal ldr/sdr instructions are used.

However, depending on instruction extensions, there are also more complex ways to load data, including multi-load instructions (from the vector extension I assume?) which can be used "under the hood" by the compiler.
Hence, we don't know, from just ARMv6 + __ARM_FEATURE_UNALIGNED, if loading will be limited to ldr/sdr, or if it will use some other strict-align only instruction (namely ldrd).

Moving back to mode 1, using packed attribute, makes it safer. Problem is, it also makes it a lot slower (on gcc, clang doesn't have this problem).

One thing that would be useful to know is if there are other macros that could help detecting this situation. Is ldrd conditional to some instruction set extension that could be detected ? For example, @plugwash, was __ARM_NEON__ defined ? If yes, and if the align-only instruction comes from a NEON extension, we could drop mode 2 on detecting it, thus preserving performance when only ldr/sdr are available.

I also agree with @wtarreau that knowing the version number of the tested xxhash library would be very useful.

[plugwash]

afaict ldrd is part of the armv6 baseline, at least specifing -march=armv6 is enough to make gcc use it.

no raspbian is not built with neon enabled (armv6 processors don't have neon).

Version of xxhash in debian/raspbian is 0.8.2

I followed your godbolt link, switched it to a modern version of gcc, added 64-bit functions and added -march=armv6

https://gcc.godbolt.org/z/PofMxE

My conclusion is.

The packed struct implementations are correct but very inefficient.

The implementation relying on undefined behaviour compiles to a single ldr instruction (ok) for 32-bit and a single ldrd instruction (not ok) for 64-bit.

The implementation using memcpy compiles to a single ldr instruction for 32-bit and a slightly messy but still better than the struct based approach implementation for 64-bit.

Based on these results I intend to switch the raspbian xxhash package to the memcpy implementation.

[Cyan4973]

Interestingly, for armv7, all implementations are looking good to read 32-bit values,
but the memcpy() variant is the worst to read 64-bit values, so the packed structure is best in this case.

Anyway, let's update the macro which controls default settings for these arm architectures.

[wtarreau]

Yann, the code you showed as an example isn't correctly compiled, because the default arch in compiler explorer is armv5, which does not support unaligned accesses. If you use armv7-a like basically all ARM-based distros nowadays relying on armhf, then you'll see that the unaligned code is simplified to just one ldr since the compiler knows the arch supports this. Just add "-march=armv7-a" to the build option and you'll see ldr appear.

This is actually what I like with this approach. I think that for 64 bits we should simply always have the union: relevant 64-bit CPUs are perfectly capable of 64-bit unaligned accesses, and the compiler knows how to optimally implement the access by just emitting two ldr in this case.

The memcpy() version remains particularly ugly on legacy compilers and started to be optimized really recently. 5.4 is not pretty for example, compared to the struct.

So for me this leads to the following:

• when caller knows the access is aligned: on 32-bit, use a direct dereference ; on 64-bit, use a struct (hence the compiler will emit two ldr instead of one ldrd)
• when caller doesn't know if the access is aligned, on 32-bit and on 64-bit, use a struct.

Some benchmarks would be needed, but I don't remember noticing that significant a gain on 32-bit platforms by using a single ldrd instead of two ldr.

[wtarreau]

Here's a link showing what I meant: https://gcc.godbolt.org/z/jKTMhf

[wtarreau]

I would even not be surprised to see better performance using two independent loads as the CPU doesn't have 64-bit operations and will have to work on the two 32-bit registers anyway, so most of the operations could possibly start out of order, while with a single ldrd it couldn't start before both are loaded (presumably with a good fetch unit, both should happen in a single cycle though).

[wtarreau]

@plugwash sorry I missed your link and we're basically doing the same :-) Indeed it's interesting to see that gcc does stupid things on armv6! I'm not that much surprised considering that this platform is basically dead since the first rpi was one of the very rare devices using it, so probably nobody cared to optimize for it :-/ Fortunately it's easy enough to detect, and I think it could be addressed using the memcpy() or even by hand using two u32 (and gives the same code as the single u64 one on armv7):

typedef struct  __attribute__ ((__packed__)) { u32 a; u32 b;} uu64d;
u64 readu64d(const void* ptr) { return ((u64)((const uu64d*)ptr)->b << 32) | ((u64)((const uu64d*)ptr)->a); }

Oh, I didn't notice that actually on armv6 it does emit ldrd for memcpy() but not for the struct one. That's particularly strange, especially since it loads using ldr from RAM, stored into stack and reloads from stack. I think gcc doesn't know very well if armv6 does really support unaligned accesses or not :-/

[wtarreau]

@Cyan4973 given this successfully passed the tests, I guess you're going to merge your patch and I can use the same in our local copy ?