"Dropping" mutable references to make their memory usable from outside again

[ais523]

I'm interested in being able to write code that looks something like this:

fn drop_static_mut<T>(_r: &'static mut T) {
}
fn drop_then_write(r: &'static mut i32, p: *mut i32) {
    drop_static_mut(r);
    unsafe { *p = 5; }
}

pub fn main() {
    let r = Box::leak(Box::new(1i32));
    let p = r as *mut i32;
    drop_then_write(r, p);
}

You can't actually drop mutable references in current Rust (as any attempt to pass them to a function reborrows rather than moving), but drop_static_mut effectively accomplishes something very similar: because it borrows the &'static mut for the rest of its 'static lifetime and then lets the reborrow go out of scope, it proves that there will be no further use of that reference or any reference it was reborrowed from (because they were all reborrowed in a way that can never end). Something similar can be done with any concrete lifetime 'a – a lifetimed equivalent of drop_static_mut that takes &'a mut T rather than &'static mut T proves that there will be no further use of that reference or any reference it was reborrowed from until the end of lifetime 'a (which in turn means that any such references with a lifetime of 'a or shorter will never be used again).

The motivation behind this is that I've been trying to produce a competitor to/evolution of allocator_api that contains almost no unsafe code, and was wondering what (from the Rust point of view) the type of an allocation from the system allocator would be. I eventually decided that it is an existing Rust type, &'static mut MaybeUninit<T>: it has almost all the same properties that a mutable reference does (the memory can only be accessed via the allocation and will not be read or written otherwise, which is one of the main behaviours of a mutable reference, and the MaybeUninit turns off any validity requirements), and if you use a view in which "freeing the reference gives it back to the memory allocator, which can later give the same reference out again as an allocation", the reference itself persists until the end of the program (thus 'static) – it's transferred back and forth between the program and memory allocator but its lifetime never actually ends.

However, one problem with this is that some allocators need to be able to rearrange the allocations they give out, e.g. by coalescing two allocations and returning them as a single allocation. I'm looking into the possibility that they might be able to do this by "dropping" the references that represent the allocations they want to merge, and creating a new one in the memory they occupied (that they now know that they have full control of because the dropped reference, and everything that it was recursively reborrowed from, will provably never be used again).

As far as I can tell, the parts of the Stacked Borrows and Tree Borrows algorithms that simulate the Rust aspect of borrows are OK with this sort of code, because they don't consider mutable references that are never read or written again to apply their "you can't read or write this memory except through this reference" condition. However, the Rust compiler wants to be able to make use of LLVM's noalias assertion, which promises that the addresses covered by a pointer are, during the body of a function, never written to without using that pointer or a pointer derived from it – so they each add an extra rule, that references passed into a function are "protected" and don't allow conflicting writes even if they are never used again, in order to be compatible with noalias – and that "protection" rule causes code like the code I wrote above to currently be considered UB.

I'm therefore wondering whether it might make sense to weaken the definition of protectors (and, at the same time, weaken the definition of noalias in LLVM so that it can continue to be used to compile Rust code, or add an alternative metadatum that is like noalias but weaker). The weaker noalias definition I've been considering is "if a weaker-noalias pointer is passed as a function argument, the data it references will not be written, except via that pointer or a pointer based on it, until the last use of that pointer or pointers based on it" (the italicised portion replaces "end of the function"). In practice, LLVM mostly wants to use its "noalias" metadata to prove that, if it writes through a pointer, the value it writes will still be there the next time that the pointer is used, so I'm hoping that a change like this wouldn't lead to too many missed optimisations. (I can't think of any optimisations that would be missed in safe Rust code as a result – although it is possible that it might lead to some missed optimisations in C, if weaker-noalias is used to model restrict and the function has both restrict and non-restrict arguments.)

The alternative is likely making the system allocator "magical" by allowing it to break the noalias rules, but I don't like that from an opsem point of view (because it would mean that either you have opsem special cases, or you use intentional UB in the knowledge that the optimiser probably can't make use of it to do something undesired). This is the solution used by C, where essentially the same problem can occur in code that looks like this:

long *free_restrict_then_write(short *restrict p) {
    *p = 2;
    free(p);
    long *q = malloc(sizeof (long));
    *q = 3;
    return q;
}

It is possible that malloc will return memory that overlaps the memory that p occupied, meaning that the write through q breaks the restrict promise if you interpret it as being based on memory locations. In C, this code is legal because *p and *q are considered to be different objects even if they occupy the same memory, because the free call ends the object's lifetime and the malloc call creates a new object with a new lifetime (and the restrict promise is based on objects rather than addresses). However, that means that the code can suddenly become UB if you replace malloc and free with non-standard-ilbrary functions that do the same thing (because then the object's lifetime may not have been ended properly). So I don't like the C solution to the same problem because it doesn't compose very well. (That said, if there is magic available to make C compilers work, might there be a way to make it available to Rust programs more generally? Some sort of "noalias ends here" annotation would solve the problem in a fairly clean way, although it would have to be able to affect the entire stack of reference reborrows rather than being function-local.) Another problem with this approach is that it only works in the 'static case, not with general lifetimes 'a (which makes it hard to "chain" allocators, i.e. an "inside" allocator uses an "outside" allocator to obtain the memory that it allocates from).

Do people have insights into what the best (non-undefined-behaviour) way to write this sort of code in current Rust is, or whether changes to Rust and/or LLVM might be useful to make such code possible to write?

[RalfJung]

I'm interested in being able to write code that looks something like this:

I'm afraid such code is UB under the LLVM semantics for the code we'd like to generate for &mut arguments as in drop_then_write: these arguments are decorated with noalias dereferenceable. Note that it's the combination of both of these that causes the problem here; with just noalias your code would still be well-defined.

So, I don't think there's any chance we can allow such code -- sorry.

I can't think of any optimisations that would be missed in safe Rust code as a result

Removing dereferenceable means we can no longer hoist accesses out of loops or across unknown function calls. The entire point of protectors being as strict as they are is to allow such optimizations. The proposed change would therefore remove most of the nice optimizations that the aliasing model currently provides.

In Tree Borrows terms, what you are asking for seems to amount to entirely removing protectors. Most of the simple optimizations we have proven rely on protectors. So again, we'd lose most of these optimizations.

[RalfJung]

Also, I can't follow your C example -- but there's nothing magical about the system allocator. p and q don't alias even if they happen to have the same address because they have entirely different provenance. Aliasing, as it turns out, has very little to do with whether addresses are equal. (For instance, restrict also allows pointers to be equal if they only end up being used at different offsets, or if they are both only read.)

Maybe I missed some part of your explanation. It would be helpful if you could condense this down a bit so one doesn't have to read an entire essay. :)

Note that there is no Rust code that matches your C example, since C restrict corresponds to LLVM noalias but Rust references are LLVM noalias dereferenceable. So its relevance to Rust is also not entirely clear to me. Your comment seems to entirely neglect the role of dereferenceable and that is causing several misunderstandings.

[RalfJung]

The motivation behind this is that I've been trying to produce a competitor to/evolution of allocator_api that contains almost no unsafe code, and was wondering what (from the Rust point of view) the type of an allocation from the system allocator would be. I eventually decided that it is an existing Rust type, &'static mut MaybeUninit: it has almost all the same properties that a mutable reference does (the memory can only be accessed via the allocation and will not be read or written otherwise, which is one of the main behaviours of a mutable reference, and the MaybeUninit turns off any validity requirements), and if you use a view in which "freeing the reference gives it back to the memory allocator, which can later give the same reference out again as an allocation", the reference itself persists until the end of the program (thus 'static) – it's transferred back and forth between the program and memory allocator but its lifetime never actually ends.

I think this is a flawed mental model. If this is the native AM allocator we are talking about, the lifetime of the memory does end the moment its provenance gets destroyed. It doesn't matter that there are still pages mapped at those addresses; as far as the AM is concerned, this memory is gone forever.

Furthermore, the allocator usually has its own pointers to the memory it is managing, and will happily use those. So if we say that provenance never changes and we erase all abstraction boundaries, then these pointers are not unique. This is not just a theoretical problem; Box<T, Alloc> does not get noalias for custom Alloc because of exactly this problem.

Also see #442, which is about custom global allocators, which are an entirely separate beast from custom per-data-structure allocators (the latter being entirely a library concept so far, though there's discussion somewhere about making them opsem-magic as well).

[ais523]

A summary of what I want (adapted based on your feedback, and still probably not perfectly specified):

• From the Rust opsem point of view: I want to make protectors weaker (without removing them entirely, and hopefully without losing significant optimisation potential). Specifically, the rule I currently think best is "protectors cannot be broken in a way that would involve meaningfully reading a byte of protected memory without writing it first" (i.e. "you have to treat protected memory like uninitialised memory" in addition to the non-protector-based Stacked/Tree Borrows rules).
• From the LLVM point of view, I think (but am not completely sure) that this is equivalent to: do not use information based on borrow UB to justify moving a read or write from before an atomic write or opaque function call to after it, unless there is an additional read/write through the same reference after the call.

Are there important protector-based optimisations that would fail to work even with this weakening? (I'm aware that "reread a value after a function call rather than caching it / write a value after a function call rather than before" would break, but suspect that those are not very useful in practice, and can't think of any other ones that would break.)

I agree that "dereferenceable" is relevant here. I initially thought it was irrelevant because the LLVM LangRef frequently uses the term "memory location" and never defines it, and this caused me to misunderstand the definition of noalias: I was using a mental model of pointers as having two components (address and provenance), but some experiments with clang and LLVM imply that its model has three components (address, object/allocation ID, provenance) and its noalias definition is effectively "accesses with the same address and object ID as a noalias pointer must also have the same provenance or a child provenance, unless the memory is not written". That said, I don't think this is an obstacle in practice: LLVM has two different ways to write dereferenceability metadata, and using the "dereferenceable" option to llvm.assume (rather than the dereferenceable attribute on a function argument) is compatible with this definition and allows almost as many optimisations (the optimisations are only disabled in cases where the code either calls a free-equivalent or uses atomics in a way that might synchronize with free in another thread, and LLVM attempts to trace calls to free and uses of atomics across function calls in order to apply the optimisation as much as possible).

This is not just a theoretical problem; Box<T, Alloc> does not get noalias for custom Alloc because of exactly this problem.

This sort of thing is part of the motivation for wanting this change in the first place – I was aware of this problem, then rediscovered it while trying to work on allocator APIs (because it makes it impossible to do just about anything allocator-related in safe Rust, given that safe Rust references are noalias dereferenceable at the moment). There are a number of other motivations, too (which I can go into more detail about if people are interested, but probably aren't relevant if the change would lose too much optimisation power to be acceptable).

[RalfJung]

From the LLVM point of view, I think (but am not completely sure) that this is equivalent to: do not use information based on borrow UB to justify moving a read or write from before an atomic write or opaque function call to after it, unless there is an additional read/write through the same reference after the call.

I think these are important optimizations we want to keep -- this is a huge part of the motivation for why protectors exist in the first place. It's not a good trade-off to weaken the rules for references everywhere for such a rather niche usecase (that doesn't fit the usual shape of a "borrow" in the first place, so arguably using references here is more of a hack than a principled solution).

You will eventually be able to use MaybeDangling<&mut T> to get a mutable reference that has no aliasing requirements whatsoever (see rust-lang/rust#118166). Until then, use a newtype around NonNull<T>.

I was using a mental model of pointers as having two components (address and provenance), but some experiments with clang and LLVM imply that its model has three components (address, object/allocation ID, provenance)

I have no idea what you mean by this. The "allocation ID" is part of the provenance, but it is not the only part.

That said, I don't think this is an obstacle in practice: LLVM has two different ways to write dereferenceability metadata, and using the "dereferenceable" option to llvm.assume (rather than the dereferenceable attribute on a function argument) is compatible with this definition and allows almost as many optimisations

The variant with llvm.assume is often referred to as "dereferenceable on entry" (which has come up multiple times in past discussions). I didn't know LLVM actually has a way of encoding that, thanks for pointing this out. However, for references we almost certainly want "dereferenceable for entire scope", because that makes code motion optimizations a lot easier.