Android and ARM regressions in master 1.2

[joakim-noah]

I recently tried building master both natively and as a linux/x64 cross-compiler and ran into these issues with the tests. I will look into these more and submit patches for the phobos bugs upstream, would like some help with the LDC ones.

LDC issues

• std.digest.murmurhash segfaults with a Bus error on its last test, when it tries to compute the unalignedHash with any llvm optimizations. This is reproducible going back to ltsmaster: all of 0.17.3, 1.1.1, and 1.2 (each built against llvm 3.9.1) pass this test without optimizations but segfault with -01 or higher optimizations. This module was added with 1.2 so obviously it wasn't tested with those older D versions before, but it seems to have uncovered some ARM codegen issue.
• std.random segfaults with this error when compiled with -O2 or higher:
  Fatal error in EH code: _Unwind_RaiseException failed with reason code: 9 Aborted
  A gdb backtrace shows that it fails in the massive last test block. ldc 0.17.3 can't build the 1.2 version of this module's tests because of a static assert, while 1.1.1 has no problem with it, even with all optimizations. This looks like the ARM codegen errors we were getting before, @smolt?

Phobos issues

• Vlad added a new linux-only test that seems to expect too much precision from std.file on Android, it passes if I change the last digit from a 7 to 0.
• tsbockman added some tests to std.json that needed to be relaxed for platforms with 64-bit reals. Adding Android to those two version blocks gets the tests to pass again.
• Vlad added a File.reopen to std.stdio which can't change modes on Android:
  std/stdio.d(658): Cannot reopen file in mode 'w' (Bad address)

I used to build for Android/x86 from upstream and catch these stdlib issues early, but haven't done that in awhile, especially since my last x86 device died more than a year ago. I may look into installing Android/x86 in a VPS and run the upstream tests there.

The good news is that @kinke's 1.2 changes to somewhat allow cross-compiling reals work fine, ie all the same druntime/phobos tests pass when cross-compiled from linux/x64, so that applying #1317 wasn't needed anymore. Also, the full dmd-testsuite still passes natively on Android/ARM. 💃

[kinke]

Thanks for the nice overview.

I suspected the std.json double roundtrip test to fail for 64-bit reals in general, but wasn't sure, so thanks for confirming. The relaxed tests should probably be upstreamed then (for GDC etc.).

[joakim-noah]

I looked into the murmurhash segfault, looks like the issue we had before with the unaligned exception table on ARM, ldc-developers/druntime#51. The last test checks the digest when run on unaligned data and segfaults when it reads the first unaligned 128-bit Element in this loop. With unoptimized codegen, ie -O0, it reads the first block in the foreach loop with the following ARM assembly (r0 has the address of the first unaligned block):

ldr     r2, [r0]
ldr     r3, [r0, #4]
ldr     r1, [r0, #8]
ldr     r0, [r0, #12]

That works fine because ldr doesn't care if r0 is aligned. However, when any more optimizations are used, ie -O1, it tries to turn the first two loads into a ldm, which does care that the address isn't aligned (r7 now has the first unaligned address):

ldm     r7, {r2, r3}
ldr     r0, [r7, #8]
ldr     r1, [r7, #12]

I'm guessing this has to do with the cast in the foreach too, so that the optimizer just thinks it's a properly aligned Element, ie some type info has been lost.

I'm unsure what to do about this, the whole point of the test seems to be to check that the digest works with unaligned data.

Update: I miscounted before and implied that the 128-bit Element is loaded into two 32-bit registers, updated the assembly to show it's actually four. Doesn't change the substance of the problem, but may have been confusing before.

[dnadlinger]

I'd say it's invalid code. D pointers/arrays are guaranteed to be aligned.

[joakim-noah]

@klickverbot, just so we're clear, the API of digest.put is to take a ubyte array, and since anyone can always pass an arbitrary ubyte slice to put, I don't think it's unreasonable for the ubyte slice passed in to be sometimes unaligned to word boundaries like this. Murmurhash's put grabs those ubytes in 16-byte chunks, so it is prone to this issue, which is why @gchatelet checks for it with this test.

One interesting thing I just noticed is that if I extract the unaligned test for 32-bit optimized Murmurhash with 128-bit Elements into a standalone file, it also segfaults because of the same optimization, while it didn't in the unittest for some reason, so even the 32-bit version shows the same problem.

Are you saying that users of Murmurhash should know never to pass unaligned ubyte arrays to it? Or that something else is "invalid code?"

[kinke]

ubyte arrays should never be unaligned as the ubyte alignment is 1. MurmurHash3.put() after a quick glance seems buggy as it first fills up its internal buffer (e.g., 128-bit buffer, 11 bytes already used => read first 5 data bytes) and then accesses the remaining data (starting at offset 5) in chunks by casting it to a Element (potentially a uint[4] or ulong[2]) slice. And that's where the required alignment (4/8 bytes) is likely to be violated for data.ptr + 5. I.e., it not just depends on the alignment of data.ptr, but also on the status of the hasher's internal buffer.

[joakim-noah]

ubyte arrays should never be unaligned as the ubyte alignment is 1.

On ARM, it seems to depend on the optimization level, ie at -O0 the ARM codegen will sometimes allocate ubyte arrays that are not aligned. In any case, a slice into an ubyte array can obviously be unaligned, which is what this test depends on. Given the way the test is setup, surely you agree that at least one of data[0 .. $-1] or data[1 .. $], the two slices passes to Murmurhash, must have its first ubyte at an unaligned address? After that, the below analysis means that the same address plus 16 is what goes into the loop.

MurmurHash3.put() after a quick glance seems buggy as it first fills up its internal buffer (e.g., 128-bit buffer, 11 bytes already used => read first 5 data bytes) and then accesses the remaining data (starting at offset 5) in chunks by casting it to a Element (potentially a uint[4] or ulong[2]) slice. And that's where the required alignment (4/8 bytes) is likely to be violated for data.ptr + 5. I.e., it not just depends on the alignment of data.ptr, but also on the status of the hasher's internal buffer.

I don't know what's going on on x86 or whatever arch you're testing, but on ARM with the given tests, the chunks always start at data.ptr + 16, because bufferSize is 0 and so bufferLeeway always jumps ahead by exactly one Element, ie 16 bytes. The status of the internal buffer seems to play no role for this bug on ARM.

[kinke]

I don't know what's going on on x86 or whatever arch you're testing, but on ARM with the given tests, the chunks always start at data.ptr + 16, because bufferSize is 0 and so bufferLeeway always jumps ahead by exactly one Element, ie 16 bytes. The status of the internal buffer seems to play no role for this bug on ARM.

I just skimmed through the code, no test performed. The way the test is set up (separately hashing 2 1KB blocks), bufferSize is indeed always 0, but it's not in the general case and the Phobos code doesn't handle resulting misalignments at all. It's not the reason for the particular test case failure on ARM but it's another way how unaligned memory accesses can result.
X86 allows misaligned memory access by default, although it may cost performance.

So I guess the code should be updated for non-misalignment-friendly architectures by checking if (cast(size_t) (data.ptr + bufferLeeway)) & (Element.sizeof - 1) == 0 and only then use the chunked approach (or try to use smaller chunks).

Edit: I don't know if an additional LDC intrinsic for unaligned loads (emitting a load T, T* ptr, align 1 in IR) would work (edit: obviously should as -O0 works) and whether it'd allow for more efficient code.

[dnadlinger]

ubyte arrays should never be unaligned as the ubyte alignment is 1

On ARM, it seems to depend on the optimization level

What @kinke and I were getting at is that ubyte arrays (or pointers) can by definition never be misaligned, because their alignment constraint is only is 1 byte.

I presume you are using "aligned" to specifically mean word-size aligned. This is in general not enough, as some instructions – e.g. aligned SIMD loads even on x86 – might require larger alignments. In this specific case, word-size alignment might of course be enough to avoid the crash.

The upshot is that the implementation that just casts ubyte[] to Element[] is invalid.

[joakim-noah]

It's not the reason for the particular test case failure on ARM but it's another way how unaligned memory accesses can result.

Ah, I thought you were saying it was the reason for this failure, got it now.

I presume you are using "aligned" to specifically mean word-size aligned.

Yes, this is why I clarified earlier that "I don't think it's unreasonable for the ubyte slice passed in to be sometimes unaligned to word boundaries like this," but maybe I should have emphasized that more.

The upshot is that the implementation that just casts ubyte[] to Element[] is invalid.

I mentioned that cast as the likely issue earlier, but what is the kosher D way to write such code and deal with alignment issues? I don't really deal with these casting and alignment issues much, so any pointer to other code that does this right would be helpful.

[smolt]

On ARM misalignment in mumurhash, I recalled it was discussed in the original PR and @jpf91 made suggestions that perhaps weren't implement correctly. See dlang/phobos#3916. The discussion on ARM alignment was good.

On std.random, it seems to be a stress case for ARM codegen by LLVM maybe because the stack usage is huge by individual function after inlining. When I played with watchOS (somewhere in the attic now), there were extra push and pops around calls when the stack usage by a function was huge. The pops were not handled in the exception landing pad and eventual function return when to wrong address. Maybe this is happening?

Maybe I have some time to catch up on LDC this weekend.

[dnadlinger]

but what is the kosher D way to write such code and deal with alignment issues?

I don't know of any better way than doing it manually, i.e. reading off data[0 .. Element.sizeof] manually and then casting the value to Element. You could also do it the C way and manually piece together the 32 bit integer from the appropriately shifted 8 bit values. Hm, thinking about it, I think there is a read function in std.bitmanip for endian-aware conversion you might be able to re-use for this.

[kinke]

but what is the kosher D way to write such code and deal with alignment issues?

The kosher way is to always keep alignment in mind when casting pointers (or accessing fields in packed structs etc.), but hardly anyone does as long as no errors pop up.

A quickfix would be guarding the Element-chunk loop via if ((cast(size_t) (data.ptr + bufferLeeway)) & (Element.sizeof - 1) == 0) (just checking whether the start address is a multiple of Element.sizeof, which must be a power of 2) as I already suggested and falling back to copying the bytes in the unaligned case. A more elaborate variant would check whether the alignment of data.ptr + bufferLeeway is suitable for 64-bit longs and use Element = ulong then, otherwise check if it's at least a multiple of 4 for Element = uint, maybe even another thingy for 16-bit shorts, and only then fall back to copying the bytes.

And yet another variant I already suggested would be introducing a new LDC intrinsic for arbitrary unaligned loads (afaik, we only have such a thing for unaligned SIMD vector loads - edit: here) and use that in the unaligned case. I guess that takes care of shifting and or'ing for architectures not supporting unaligned loads directly.

Edit: Looking at the code again, Element is actually the full 128-bit type/chunk (ulong[2] / uint[4]). What I meant by Element above is a scalar element, i.e., ulong / uint, defining the alignment requirements.

[kinke]

Here's a highly experimental hack. No idea about the performance impact and whether it actually works on ARM etc.; I just made sure the tests still work when using the unaligned code path with x86.

Amusing side note: the code in question containing the cast from ubyte[] to Element[] is actually @safe and doesn't even produce a warning. ;)

[dnadlinger]

I haven't looked at your changes in any detail yet, but you will definitely want to keep the upstream people in the loop to make things easier.

I also imagine there might be other (C) MurmurHash3 implementations for ARM dealing with the problem already. In particular, it might make sense to keep the current code for archs where unaligned loads are reasonably fast (x86).

[gchatelet]

Sorry for the late reply and thx for putting me in the loop.
I remember murmurhash PR to have taken quite a long time to submit and I couldn't test it on ARM or platform with bad/unsupported unaligned loads, so I just went on with what I had - adding some tests to catch the failure when it happens.
I wanted to create a version for "poorly supported unaligned read platform" but there didn't seem to be a version I could test against back then (not sure one exists nowadays either). I recommend creating one, the problem will keep on happening for other hashes as well.

The put(ubyte[]) interface is already quite slow compared to the plain Element interface, it would totally hurt performance to bit shift/mask on x86.

One thing I don't like about D's cast is that it sometimes reinterpret_cast and sometimes it static_cast but you don't really know if the operation is cheap or not. I was under the impression that slice cast would handle the misalignment depending on the platform but it seems it doesn't.