What memory is the Global allocator allowed to access

[jwong101]

Consider the following code:

#[no_mangle]
pub fn src(mut x: Vec<&mut u8>) -> u8 {
    let mut y = 0;
    {
    let mut x = std::mem::take(&mut x);
    // needed for the optimization otherwise LLVM gets confused with the potential reallocation
    unsafe { std::hint::assert_unchecked(x.len() < x.capacity()); }
    x.push(&mut y);
    // x gets deallocated here and `GlobalAlloc` can potentially use the pointer to `y`
    }
    y
}

Right now src() gets optimized to return 0 unconditionally after freeing the memory backing x. Furthermore, the write of the mutable reference gets optimized out, since the compiler assumes that deallocator doesn't access the freed memory block w/o first overwriting it.

I believe you could justify these semantics if you specify that alloc::dealloc overwrites the underlying buffer with undef/poison before providing it to the global allocator, however this should probably be documented in the docs (unless it's "obvious" that the Global allocator can't do that, since that's probably an expectation that most people would have).

Furthermore, consider the example from rust-lang/rust#130853. I'm not sure how to justify the original transformation w/ Stacked or Tree borrows, however, I was wondering if the following is justifiable:

// use a mutable reference to prevent the MIR opt from happening
#[no_mangle]
pub fn src(x: &mut &u8) -> impl Sized {
    let y = **x;
    let mut z = Box::new(0);
    // a bunch of code that operates on the `Box`, however, 
    // nothing else can potentially access the underlying `u8`
    // that's behind the double reference besides the `__rust_alloc` call.
    

    // optimizable to `true`?
    **x == y
}

Currently, LLVM doesn't do the second optimization. However, it does perform it if you manually set System to be the global allocator: https://rust.godbolt.org/z/a77PWjeKE ¹. This is due to this line, which is used by their GVN pass.

TLDR: is the implementor of the global allocator required to not modify references that are "visible"² in code that invokes the global allocator methods? I realize that that definition is kinda scuffed, but that's how LLVM explains their assumptions of malloc/calloc/free:

inaccessiblemem: This refers to accesses to memory which is not accessible by the current module (before return from the function – an allocator function may return newly accessible memory while only accessing inaccessible memory itself). Inaccessible memory is often used to model control dependencies of intrinsics.

The default access kind (specified without a location prefix) applies to all locations that haven’t been specified explicitly, including those that don’t currently have a dedicated location kind (e.g. accesses to globals or captured pointers).

Footnotes

1. You also get the malloc -> calloc transformation for types other than these hardcoded ones if you set System to be the global allocator manually. ↩

2. This probably means that allocator methods aren't allowed to be inlined if the optimizer wants to make assumptions about code that invokes them. ↩

[RalfJung]

That's a good observation!

I believe you could justify these semantics if you specify that alloc::dealloc overwrites the underlying buffer with undef/poison before providing it to the global allocator

Yes I would say this is what happens.

is the implementor of the global allocator required to not modify references that are "visible"2 in code that invokes the global allocator methods?

malloc is a special magic intrinsic that always returns fresh memory that was not part of the Rust-reachable memory at all before. This same does not apply to all global allocators; a user-defined global allocator can return memory from some other allocation it got somehow, and this memory is then "carved out" from the allocation it was previously in, and made into a new allocation. Though maybe we can reasonably apply the restriction that the memory that his is "carved out" from must not be stack memory?

[VorpalBlade]

malloc is a special magic intrinsic that always returns fresh memory that was not part of the Rust-reachable memory at all before.

So what happens if you implement malloc in Rust, perhaps part of relibc or some other libc implemented in Rust? How should it return memory not part of Rust reachable memory?

Or what happens in a kernel where there you allocate pages from physical RAM, mapping them into virtual memory? Or in embedded where there isn't even an MMU?

To me it seems quite suspect in a systems programming language to treat any function as magic that isn't implemented by the compiler itself. (I.e. anything that isn't a lang item, or possibly things from compiler-builtins, many (most?) of the latter don't even have special opsem semantics but are about things like softfloat).

[RalfJung]

So what happens if you implement mamloc in Rust, perhaps part of relibc or some other libc implemented in Rust? How should it return memory not part of Rust reachable memory?

Yeah that's a good question. I think generally the answer is, that's basically an FFI call, so these are two independent instances of the Rust Abstract Machine that each have their own idea of what memory is "Rust memory".

(Note that this is specifically about malloc, not about #[global_allocator]!)

Or what happens in a kernel where there you allocate pages from physical RAM, mapping them into virtual memory? Or in embedded where there isn't even an MMU?

Not sure how that's related to this discussion. The only times anything special happens is when you call malloc or when you call alloc::alloc::alloc (or more specifically, the underlying __rust_alloc symbol). The way these two calls are special is not the same. Similar things apply to the other functions of the allocator (realloc, __rust_realloc, free, __rust_dealloc, ...). Everything else is just a normal function call.

I don't think it is useful to expand the scope of this issue to "everything related to allocation ever", as that's a lot of stuff. So lets focus on the special magic allocation functions that your post discusses.

To me it seems quite suspect in a systems programming language to treat any function as magic that isn't implemented by the compiler itself.

We inherited this from C, so please redirect these comments to the responsible parties. ;) The reason they did this, of course, is that it's good for optimizations, and many people would complain loudly if we stopped doing these optimizations.
Our life would surely be easier if malloc was just a normal function, but alas, it is not, so we have to do the best that we can with this situation.

[VorpalBlade]

Yeah that's a good question. I think generally the answer is, that's basically an FFI call, so these are two independent instances of the Rust Abstract Machine that each have their own idea of what memory is "Rust memory".

That can be defensible if we have two separate cdylib or cstaticlibs. What if they are all part of the same cargo compilation (or in the extreme case, the same crate)? How do you draw the border between the AM instances? Presumably both could share access to some resources then without going through the alloc interface. Is that UB?

Let's consider a concrete example. In a piece of embedded code you have a static memory block that you satisfy your dynamic allocations from. You use this directly sometimes from Rust, but you have a C dependency and you want to provide a malloc compatibility layer for that piece of C code. Is this OK from an opsem perspective? What if some rust code allocated via this malloc in Rust as well?

[RalfJung]

That can be defensible if we have two separate cdylib or cstaticlibs. What if they are all part of the same cargo compilation (or in the extreme case, the same crate)? How do you draw the border between the AM instances? Presumably both could share access to some resources then without going through the alloc interface. Is that UB?

How would you even do that? I don't know when exactly the special malloc rules in LLVM kick in, but I am fairly sure it's not just "any function called malloc". AFAIK it has to be a malloc symbol imported from the outside and marked with particular attributes, which precludes the possibility of it being in the same crate.

The only thing that could become a problem here is if LLVM later decides to inline this symbol during LTO. I don't know LLVM enough to know what it will and won't do here.

And yes, sharing of resources between the allocator and the rest of the program is extremely limited. LLVM sadly does not document exactly how, so we'll have to figure that out.

[RalfJung]

#442 is already discussing the special semantics of the __rust allocator symbols, so we should limit this discussion to malloc. Before we can give any precise guidance here, someone has to figure out what exactly LLVM does and does not do. Cc @nikic

[RalfJung]

In fact, this issue is a mess because you mixed up two questions that are unfortunately independent -- the first part of your question is part of #442, the second part is specifically about malloc (as witnessed by the fact that you have to set the global allocator to System). You framed the question as if both of these are about "the global allocator" but that's not the case. So we should close this issue because it will otherwise be eternally confusing everyone as we are trying to disentangle these questions.

Please open a new issue specifically for malloc, and redirect discussion about #[global_allocator]/__rust_alloc to #442.

[RalfJung]

I opened an issue for malloc: #535