C undefined behavior. Strict aliasing rule, or incorrect alignment? [duplicate]

Question

I can't explain the execution behavior of this program:

#include <string> 
#include <cstdlib> 
#include <stdio.h>

typedef char u8;
typedef unsigned short u16;

size_t f(u8 *keyc, size_t len)
{
    u16 *key2 = (u16 *) (keyc + 1);
    size_t hash = len;
    len = len / 2;

    for (size_t i = 0; i < len; ++i)
        hash += key2[i];
    return hash;
}

int main()
{
    srand(time(NULL));
    size_t len;
    scanf("%lu", &len);
    u8 x[len];
    for (size_t i = 0; i < len; i++)
        x[i] = rand();

    printf("out %lu\n", f(x, len));
}

So, when it is compiled with -O3 with gcc, and run with argument 25, it raises a segfault. Without optimizations it works fine. I've disassembled it: it is being vectorized, and the compiler assumes that the key2 array is aligned at 16 bytes, so it uses movdqa. Obviously it is UB, although I can't explain it. I know about the strict aliasing rule and it is not this case (I hope), because, as far as I know, the strict aliasing rule doesn't work with chars. Why does gcc assume that this pointer is aligned? Clang works fine too, even with optimizations.

EDIT

I changed unsigned char to char, and removed const, it still segfaults.

EDIT2

I know that this code is not good, but it should work ok, as far as I know about the strict aliasing rule. Where exactly is the violation?

Answer 1

The code indeed breaks the strict aliasing rule. However, there is not only an aliasing violation, and the crash doesn't happen because of the aliasing violation. It happens because the unsigned short pointer is incorrectly aligned; even the pointer conversion itself is undefined if the result is not suitably aligned.

C11 (draft n1570) Appendix J.2:

1 The behavior is undefined in the following circumstances:

....

• Conversion between two pointer types produces a result that is incorrectly aligned (6.3.2.3).

With 6.3.2.3p7 saying

[...] If the resulting pointer is not correctly aligned [68] for the referenced type, the behavior is undefined. [...]

unsigned short has alignment requirement of 2 on your implementation (x86-32 and x86-64), which you can test with

_Static_assert(_Alignof(unsigned short) == 2, "alignof(unsigned short) == 2");

However, you're forcing the u16 *key2 to point to an unaligned address:

u16 *key2 = (u16 *) (keyc + 1);  // we've already got undefined behaviour *here*!

There are countless programmers that insist that unaligned access is guaranteed to work in practice on x86-32 and x86-64 everywhere, and there wouldn't be any problems in practice - well, they're all wrong.

Basically what happens is that the compiler notices that

for (size_t i = 0; i < len; ++i)
     hash += key2[i];

can be executed more efficiently using the SIMD instructions if suitably aligned. The values are loaded into the SSE registers using MOVDQA, which requires that the argument is aligned to 16 bytes:

When the source or destination operand is a memory operand, the operand must be aligned on a 16-byte boundary or a general-protection exception (#GP) will be generated.

For cases where the pointer is not suitably aligned at start, the compiler will generate code that will sum the first 1-7 unsigned shorts one by one, until the pointer is aligned to 16 bytes.

Of course if you start with a pointer that points to an odd address, not even adding 7 times 2 will land one to an address that is aligned to 16 bytes. Of course the compiler will not even generate code that will detect this case, as "the behaviour is undefined, if conversion between two pointer types produces a result that is incorrectly aligned" - and ignores the situation completely with unpredictable results, which here means that the operand to MOVDQA will not be properly aligned, which will then crash the program.

---

It can be easily proven that this can happen even without violating any strict aliasing rules. Consider the following program that consists of 2 translation units (if both f and its caller are placed into one translation unit, my GCC is smart enough to notice that we're using a packed structure here, and doesn't generate code with MOVDQA):

translation unit 1:

#include <stdlib.h>
#include <stdint.h>

size_t f(uint16_t *keyc, size_t len)
{
    size_t hash = len;
    len = len / 2;

    for (size_t i = 0; i < len; ++i)
        hash += keyc[i];
    return hash;
}

translation unit 2

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <inttypes.h>

size_t f(uint16_t *keyc, size_t len);

struct mystruct {
    uint8_t padding;
    uint16_t contents[100];
} __attribute__ ((packed));

int main(void)
{
    struct mystruct s;
    size_t len;

    srand(time(NULL));
    scanf("%zu", &len);

    char *initializer = (char *)s.contents;
    for (size_t i = 0; i < len; i++)
       initializer[i] = rand();

    printf("out %zu\n", f(s.contents, len));
}

Now compile and link them together:

% gcc -O3 unit1.c unit2.c
% ./a.out
25
zsh: segmentation fault (core dumped)  ./a.out

Notice that there is no aliasing violation there. The only problem is the unaligned uint16_t *keyc.

With -fsanitize=undefined the following error is produced:

unit1.c:10:21: runtime error: load of misaligned address 0x7ffefc2d54f1 for type 'uint16_t', which requires 2 byte alignment
0x7ffefc2d54f1: note: pointer points here
 00 00 00  01 4e 02 c4 e9 dd b9 00  83 d9 1f 35 0e 46 0f 59  85 9b a4 d7 26 95 94 06  15 bb ca b3 c7
              ^