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").

[gnzlbg]

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

C does not have an equivalent of repr(align), so yes, malloc can assume that. EDIT: C11 added _Alignas to C, but yes, malloc doesn't know anything about the alignment of a type. It still can be used, but the user needs to check whether the allocation is properly aligned.

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

The docs are quite clear IMO:

The allocated space is suitably aligned (after possible pointer coercion) for storage of any type of object.

Anything more concrete than that will be target specific, and those details are outside jemalloc's control - if jemalloc wants to replace the system allocator in a target, it needs to comply with the ABI there. If it were to guarantee more, e.g., all allocations are 16byte aligned, it wouldn't work on platforms using the SysV i386 ABI.

[RalfJung]

Well, with _Alignas that statement from the jemalloc docs is wrong, isn't it?

And for users to manually do the alignment, getting something more concrete would be useful. And also for Rust! Currently you are deducing a whole lot of things from a few words in the spec. I have zero confidence that this is the only way to read the spec. So something like:

"for size >= alignof(max_align_t) we guarantee an alignment of alignof(max_align_t); for smaller sizes we guarantee an alignment of the size rounded down to the next power of two."

would IMO be prudent to ask from the jemalloc devs. Or else we'll find ourselves with more bugs when someone interprets all this slightly differently.

[gnzlbg]

I don't know how useful would that be: malloc only needs to comply with the C standard. Parts of it are implementation-defined, and what those are defined to is often specified by the system ABI.

That's the only thing the global allocator can rely on. On most platforms, the system allocator - which is the default global allocator for Rust programs - is not jemalloc - it is the one from glibc, musl, microsoft, apple, google, mozilla, etc. In some platforms, like FreeBSD, the system allocator is jemalloc, but even there we can't exploit that knowledge because users can just MY_DYNAMIC_LINKER=my_other_alloc ./my_rust_program and now the global allocator is a different one. That's an use case we support.

So even if jemalloc were to offer extra guarantees here, Rust's system allocator cannot make use of them.

The only places were we can can exploit jemalloc's specific guarantees, is when using crates like jemallocator, to explicitly hardcode the allocator to a particular one. As in, if that allocator is not linked, you get a linker error or similar. But even there, it makes sense to stick to what C and the platform ABI guarantees, because jemalloc is free to break anything else in the next version.

[RalfJung]

I don't know how useful would that be

Well it would save us this entire discussion. If that doesn't demonstrate its usefulness I don't know what does.^^

I don't know what the "system allocator" is for Linux, but the one in glibc actually guarantees a 16-byte alignment on 64bit systems for all allocations. So by that standard jemalloc would just be incorrect.

[gnzlbg]

I don't know what the "system allocator" is for Linux, but the one in glibc actually guarantees a 16-byte alignment on 64bit systems for all allocations. So by that standard jemalloc would just be incorrect.

The platform ABI guarantees that. What the malloc implementations guarantee is irrelevant. If glibc were to guarantee that all addresses are 32-byte aligned, there is no way in which we could exploit that information in the implementation of the system allocator, because the platform only requires 16-byte alignment, and it is valid to pick any allocator at run-time that satisfies that.

[RalfJung]

So there a document somewhere saying "for x86-64 bit, 16-byte alignment is guaranteed"? But that document contains an exception for small sizes, making jemallocs behavior legal?

[gnzlbg]

Yes, there are documents containing the rules of what's legal, at least for Linux x86_64.

Those document allow an exception for small sizes. One API that uses those is posix_memalign, which requires the alignment to be at least sizeof(void*), which is 8 on x86_64, and which allows you to allocate 9 bytes, with a smaller alignment.

But that document contains an exception for small sizes, making jemallocs behavior legal?

I still have no idea what jemalloc has to do with any of this - your original question is about std::alloc::System, and that has nothing to do with jemalloc. But yes, jemalloc exploits this behavior, to be able to satisfy 1 byte request, and return addresses that are 1 byte aligned. Otherwise each 1 byte request would consume 16 bytes of memory within a memory page.

[SimonSapin]

@RalfJung A document that could be relevant is the C standard. Unfortunately, as mentioned in the commit message for 21d8992, it is rather tautological on this topic:

The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement

A fundamental alignment is represented by an alignment less than or equal to the greatest alignment supported by the implementation in all contexts, which is equal to _Alignof (max_align_t).

max_align_t which is an object type whose alignment is as great as is supported by the implementation in all contexts

The standard does not give any numeric value. Like many other aspects of C, it looks like the actual value of _Alignof (max_align_t) is implementation-defined.

[RalfJung]

I still have no idea what jemalloc has to do with any of this - your original question is about std::alloc::System, and that has nothing to do with jemalloc.

When using jemalloc, System becomes jemalloc. That's how #45955 happened.

Those document allow an exception for small sizes.

Do you have a reference for something that concretely calls out an exception for small types? The C standard only does this very indirectly, as you showed.

[gnzlbg]

When using jemalloc, System becomes jemalloc. That's how #45955 happened.

That was a bug in our implementation of system that applies to pretty much all allocators, not only jemalloc.

Do you have a reference for something that concretely calls out an exception for small types?

C18 (C17 draft) says (emphasis mine):

6.2.8 Alignment of objects

2 A fundamental alignment is a valid alignment less than or equal to _Alignof (max_align_t).

max_align_t is an object type whose alignment is the greatest fundamental alignment

7.22.3 Memory management functions

1 [...] The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated).

Since the alignment of an object is a power of two that is always smaller than or equal to the object size, rounding down the alignment of an allocation to the previous power of two always produces an allocation properly aligned for every type that can fit it.

That holds for all allocations, so there is no exception for that. That's the rule.

Since that would mean that large allocations must be unreasonably aligned, the standard does provide an exception for allocations of size larger than than _Alignof(max_type_t). These only need to be aligned at an _Alignof(max_type_t) boundary.

If you believe this is incorrect, please show a counter-example for which this doesn't work.

[RalfJung]

That was a bug in our implementation of system that applies to pretty much all allocators, not only jemalloc.

AFAIK it is a normal way of using jemalloc to make it override the malloc symbol? Don't we still do that in rustc, or when using "jemallocator"?

If you believe this is incorrect, please show a counter-example for which this doesn't work.

I don't say it is incorrect, I say it is awfully indirect. It's like reading tea leaves. I am looking for a clear definite statement. That doesn't seem to exist though. :(

There clearly is some kind of "non-continuity" where all allocations are aligned MIN_ALIGN except for small ones. Or vice versa, all allocations are aligned "size rounded down to power of 2" except for big ones. You are convincingly deriving that non-continuity from standard wording. I don't say you are wrong, but this feels like interpreting ancient scripture. A clear spec looks different.

Also, an object of size 2 with alignment requirement 4 is "fundamental" according to your definition, and yet rounding down the size to the next power of 2 does not give the right alignment. So your rule does have exceptions, namely types marked _Align.

[gnzlbg]

an object of size 2 with alignment requirement 4 is "fundamental

Can you show such an object in C and/or Rust ?

AFAIK it is a normal way of using jemalloc to make it override the malloc symbol?

It's probably the most common way of switching allocators.

Don't we still do that in rustc, or when using "jemallocator"?

What jemallocator does is it requires jemalloc to be linked to your binary, allowing (and making use of) jemalloc-specific APIs. If you do this, when using Jemallocator directly (not std::alloc::System), you can obviously rely on assumptions that only hold for jemalloc. But std::alloc::System cannot do that because, then it wouldn't work with other allocators.

[RalfJung]

The goal is not to rely on assumptions that only hold for jemalloc. The goal is to make sure that we do not make assumptions that don't hold for jemalloc.

Because that's what we used to do, before #45955 got fixed. We were assuming something that was true for system malloc but not for jemalloc: that all allocations, no matter the size, are MIN_ALIGN aligned.

To make sure we don't do that again, I want to be sure that all assumptions we are making hold for jemalloc. That's why I'd like jemalloc to spell out what we can assume.

[RalfJung]

Can you show such an object in C and/or Rust ?

Ah I forgot about the stride vs. size thing. So such an object does not exist. But such a Layout exists, and it is something we want to support in our allocator API (we even have a test for that).

And we do have objects with align > size, namely all ZST.

[gnzlbg]

Yeah, I agree. The only cases for which the "round to the previous power of two approach" doesn't work is for ZSTs, and types (or allocations) with align > size. Since those just cannot happen in C, the C standard doesn't mention them as exceptions. That is, we can only call malloc when that holds, and if it that doesn't hold, we need to call a different API that supports the align > size case.