We call posix_memalign with a too small alignment

[RalfJung]

The man page for posix_memalign says

The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of sizeof(void *). If size is 0, then the value placed in *memptr is either NULL, or a unique pointer value that can later be successfully passed to free(3).

And yet Miri found libstd calling this function with an alignment of 4 on a 64bit-platform. This happens when size=2, align=4. The fact that size<align makes it enter the code path for posix_memalign.

rust/src/libstd/sys/unix/alloc.rs

Line 9 in 0af8e87

if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {

[nagisa]

The only reason I can imagine for && layout.align() <= layout.size() to exist there is a buggy implementation of malloc. This check is only meaningful if a buggy implementation returns not an allocation suitably aligned for any built-in type (on x86_4 – 16-bytes) but rather an allocation aligned for the particular request?

[nagisa]

A lack of comment is disturbing here. If git history does not reveal any such issue, then we should just remove that check entirely.

[RalfJung]

That extra check was introduced by 21d8992 to fix #45955.

[RalfJung]

I have opened jemalloc/jemalloc#1533 in jemalloc to get clarification from them about their alignment guarantees. It would be nice if someone with more knowledge could chime in, in particular knowledge about where exactly that value of 16 for MIN_ALIGN on x86-64 comes from.

Cc @SimonSapin @gnzlbg @alexcrichton

[SimonSapin]

Possibly from here:

https://www.gnu.org/software/libc/manual/html_node/Aligned-Memory-Blocks.html#Aligned-Memory-Blocks

The address of a block returned by malloc or realloc in GNU systems is always a multiple of eight (or sixteen on 64-bit systems).

[gnzlbg]

@RalfJung C has max_align_t. Per C11 6.2.8p2 types with an alignment smaller than max_align_t are supported in all contexts. AFAICT this includes the memory returned by any memory allocation function - not only malloc, but also posix_memalign.

The largest scalar type of C implementations needs to be supported in all contexts. On most platforms, this type is often long double which the SysV64 Application Binary Interface requires it to have an alignment of 16, so on these particular platforms, max_align_t will have an alignment requirement of 16 bytes.

On these platforms, all memory allocation functions need to return memory aligned to a 16 byte boundary when called with a size >= sizeof(long double) to be able to support the largest scalar type provided by the C implementation. Otherwise malloc(sizeof(scalar)) would return memory not suitable for storing a scalar type. However, if the memory allocation is smaller than the size of the largest scalar type, then it would be illegal to store it there, so the memory returned needs to only be properly aligned to be able to store the largest scalar type that would fit in that particular size. In practice, this means that for sizes up to max_align_t, the alignment of the returned memory equals the size of the allocation rounded to the previous power of two (e.g. in a 5 byte allocation, you can at most fit a 32-bit scalar, so the allocation only needs 4 byte of alignment). And for sizes larger than max_align_t, the alignment is at least max_align_t (this allows storing, e.g., an array of long doubles).

In practice, the fastest thing you can do, is calling malloc if align <= max_align_t && align <= size, because if align <= size malloc will return an alignment of at least size rounded to the previous power of two, which is always satisfied (remember that align must be a power of two, so if its smaller than size, it is at least the previous one). malloc will do this without having to branch on any user provided alignment argument. That's precisely what that code is doing.

The else branch is calling a "generic" aligned_malloc which should be able to handle any user-specified alignment. The implementation of aligned_malloc based on posix_memalign:

rust/src/libstd/sys/unix/alloc.rs

Line 83 in 9ebf478

let ret = libc::posix_memalign(&mut out, layout.align(), layout.size());

appears to have the bug you mention, and should probably call posix_memalign(ptr, max(requested, size_of::<*const ()>()), size) or similar.

I suspect that the implementation of posix_memalign provided by jemalloc, which we use here:

rust/src/rustc/rustc.rs

Line 19 in 6d59933

jemalloc_sys::posix_memalign;

doesn't have this issue, because it probably just forwards the call to mallocx, which supports alignment smaller than sizeof(void*).

[RalfJung]

In practice, the fastest thing you can do, is calling malloc if align <= max_align_t && align <= size, because if align <= size malloc will return an alignment of at least size rounded to the previous power of two, which is always satisfied (remember that align must be a power of two, so if its smaller than size, it is at least the previous one). malloc will do this without having to branch on any user provided alignment argument. That's precisely what that code is doing.

So basically on the C side, one assumes that malloc is not used with types that use the C equivalent of repr(align)?

With that assumption, I agree it is enough for malloc to guarantee an alignment of size rounded down to the next power of two. (I think your post originally said "up", but now it says "down" so I guess we agree.) That's what I will make Miri do and our implementation indeed handles that case just fine.

The bug in the way we call posix_memalign is fixed by #62296.

Still, it would be nice not to be able to reason about "in practice", but get some commitment from jemalloc -- see jemalloc/jemalloc#1533.

And finally, this only concerns malloc on Unixes. Does anyone know what the situation looks like with HeapAlloc on Windows? libstd currently assumes even small allocations to be aligned there, and https://support.microsoft.com/en-us/help/286470/how-to-use-pageheap-exe-in-windows-xp-windows-2000-and-windows-server agrees with that (Ctrl-F "on 64-bit platforms").