Bug: Unaligned accesses are undefined behavior

[julianhartmer]

Strictly speaking, the C standard does not guarantee unaligned memory accesses to work. So any time sizeof (vec) is bigger than sizeof (size_t), accessing vec is undefined. sizeof (size_t) is guaranteed to be at least 16.

While this may not be a problem when targeting desktop machines, this may problematic when using the library in embedded systems.

To resolve this, I suggest declaring a struct that to ensure alignment or, if a struct declaration is not wanted, to ensure alignment manually.

• C standard: std.org/jtc1/sc22/wg14/www/docs/n1570.pdf, page 66, 6.2.8.1
• For discussion of impact of unaligned memory accesses: https://www.kernel.org/doc/Documentation/unaligned-memory-access.txt

[eteran]

Interesting, I think it's even more complex than you mention because if the size of the elements are a multiple of the size of size_t then it's probably OK.

I don't think a struct is the solution as that would be a fundamental design change, but I'll certainly look into alignment. I think a constant derived from the size of the type can be included in the "pre buffer padding" to deal with this.

[eteran]

More thoughts on this...

malloc is (i believe) required to return pointers which are suitably aligned to store "any kind of variable".

In other words, size_t *p = malloc(N); is always guaranteed to be suitably aligned to store a size_t (let's assume that N is guaranteed to be >= sizeof(size_t)

The question is then, if p is guaranteed to be aligned safely for a size_t... wouldn't p[-1] and p[-2] also be suitably aligned? I think it might be.

Can you give any more details about circumstances where it wouldn't be?

[julianhartmer]

This is a complicated debate and I am also trying to wrap my head around this problem, so bear with me.

malloc is (i believe) required to return pointers which are suitably aligned to store "any kind of variable".

I think so too. The malloc man page says: "The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type". Otherwise, I do not see how malloc would be safe for allocation of objects with arbitrary data types. Sorry if I butchered this sentence, English is my second language.

if the size of the elements are a multiple of the size of size_t then it's probably OK

I think the opposite is true. For example, lets take uint32_t and uint64_t. uint32_t is 4 byte and thus the address is aligned if and only if the last 4 bits of the address are 0. An address is aligned with regards to uint64_t if and only if the last 8 bits of the address are 0. This means, every uint64_t address is also a valid uint32_t address, but not vice-versa.

To come back to our problem, the address of the first member is calculated from the address returned by malloc. We agree that malloc should return an address which is aligned to all possible data types, so let's just assume the address is 0. The address of the first element in the array is now 0 + 2 * sizeof (size_t). Assuming size_t is 4, this address ends up as 8. So the address of element is aligned to 8 bytes (and also 4, 2 and 1), but not to 16, 32 bytes etc.

Please note that this is all assuming that sizeof (X) is always a power of 2, which may not even be the case.

Assuming all of my previous points stand (correct me if I am wrong), we have to pad the address of the first element manually to ensure its alignment, especially if the data type is bigger than 2 * sizeof (size_t). This is even more complicated when considering my pull request.

To solve this, there are two options:

1. Calculating the padding in macros using sizeof (size_t) and sizeof (type).
2. Implement a macro that declares a struct which contains the data type of the elements. This way, the compiler takes care of alignment by padding the struct.

The first one is possible, but sacrifices readability of the code, the second one might not even be possible.

[eteran]

Interesting, I think you may be correct. I was thinking in terms of the alignment of the size_t fields that are BEHIND the user pointer, but forgot that I also need to consider the alignment of the pointer we pass to the user, I can certainly make it so this is effectively guaranteed to be appropriately aligned. I'll think about how i think this can be best addressed.

Good find! 👍🏻

[julianhartmer]

I am working on a PR to follow the first solution. I am looking forward to all the required macro magic :smile:

[eteran]

Nice, I think it MAY be "not too bad" once it's all figured out

[eteran]

A thought that may be "good enough" for all practical use cases. Since the 3 objects of meta-data start at offset 0, and we're looking to just make sure that the first data object starts properly aligned. Maybe we can do something like this:

#ifndef CVECTOR_DATA_ALIGNMENT
#define CVECTOR_DATA_ALIGNMENT 32 /* a pretty safe bet since C11's max_align_t is typically 8 or 16
#endif

And then we just calculate the offset of the data from the base as sizeof(size_t) * 2 + sizeof(cvector_elem_destructor_t) rounded up to a multiple of CVECTOR_DATA_ALIGNMENT.

And if a user REALLY wants a bigger alignment requirement, they can just specify #define CVECTOR_DATA_ALIGNMENT 128 before including the header.

What do you think?

[eteran]

I believe that the alignment issue is resolved by another PR which uses a struct to represent the meta-data. Please reopen the issue/PR if you still have concerns.