Soundness of Manual Scope Control with transmute and AcqRel under Stacked Borrows

help
1

Hi everyone,

I'm using transmute to extend a &'a mut T to 'static for linking into a list, while manually enforcing its destruction before 'a ends. I'd like to verify if this is sound under Stacked Borrows (SB).

pub unsafe fn cheat<'a>(self: MyBox<'a, T>) -> MyBox<'static, T> {
    // Prevent reordering across the lifetime transformation
    std::sync::atomic::compiler_fence(std::sync::atomic::Ordering::AcqRel);
    unsafe { std::mem::transmute(self) }
}

Safety Invariants:
Must be removed from the List before 'a ends and cannot be moved out of the scope of 'a.

My Reasoning:

  • Tag Preservation: transmute preserves the original Pointer Tag (Tag_r) without triggering Retag. In the SB model, both the original reference and the 'static alias are seen as the same Tag_r acting on the same Unique stack item.
  • Ordering (The "Two Variables" Problem): Since the compiler might treat the original reference and the 'static alias as two entirely unrelated variables (due to noalias and the broken provenance chain), it could reorder their operations. The AcqRel fence prevents this by ensuring that original accesses (Release) do not sink below the conversion and new alias accesses (Acquire) do not hoist above it.
  • Trace Validity: SB tracks the execution trace. Since no access via Tag_r occurs after EndRegion('a) (due to the safety invariants), the model should remain valid despite the type-level 'static annotation.

Does this reuse of Tag_r combined with a compiler_fence provide sufficient protection against UB in SB or LLVM's alias analysis?

Thanks!

2

IIRC, fields are recursively retagged. If moving a MyBox<'a, T> triggers a retag (such as if it has a field of type &mut _ or Box<_>), then passing self into transmute moves the self value and therefore retags it. (Don't bother trying to evade the retag, it shouldn't impact the correctness of your code, unless you're doing something immensely strange that you probably shouldn't do.)

How is the provenance chain broken? The value returned by cheat has the provenance of its input (or provenance derived from its input via a retag). Even if that were not the case, compiler_fence is entirely pointless here, since it only matters for concurrent code (sort of including signal handlers, even if they aren't multithreaded).

3

Yes, you are right

I’ve reconsidered, and I believe the core issue lies here: The provenance chain is indeed not broken in the physical sense—the value returned by cheat still carries the same Pointer Tag (Tag_r) or a tag derived from it. In the Stacked Borrows (SB) model, this remains a valid continuation of the borrow stack.

However, the problem arises at the rustc/LLVM level. From the perspective of the Rust compiler's static analysis, deriving a 'static lifetime from a significantly shorter lifetime 'a is logically impossible under the language's safety invariants.

Because of this logical contradiction, the compiler might apply Alias Analysis optimizations based on the assumption that these two references cannot point to the same memory location. This is purely a rustc / optimization-level concern rather than an SB concern. If the compiler assumes they are disjoint, it may perform aggressive instruction reordering or subexpression elimination. Therefore, the use of a barrier (like a fence) and strict safety invariants is intended to suppress these incorrect assumptions that the compiler might otherwise make due to the 'disguised' lifetime.

4

I assure you that it will not. See e.g. extend_mut, which is sound. Or yoke, which also performs lifetime extension. Lifetime-erasing a non-'static reference to a 'static lifetime is not altogether uncommon, though it is still extremely unsafe because you must ensure that you do not expose the lifetime-extended reference to untrusted code, which might not be aware of the fact that the lifetime is fake.

5

To further elaborate:

The "sole" requirement (a difficult one to meet, though) is that you ensure that nobody uses the lifetime-extended reference after its referent[1] has been invalidated (where "invalidated" can be somewhat circularly taken as meaning "had anything done to it which invalidates the provenance of the reference to it". In particular, this includes writing to the referent via a pointer not derived from the reference, moving the referent (if it's !Copy), deallocating or destructing the referent, etc).

Note that the compiler is allowed to insert "fake reads" to a reference at any time it's in use, meaning that references must always be valid for reads (and mutable references must always be valid for writes) while they are in use. Most of the time, "in use" means "from when it's first created to when it's last used", though references passed as arguments to a function should be considered to be "used" during the whole execution of that function. That is, references passed as arguments are assumed to be valid for the entirety of the function body. This edge case is sufficient to complicate the destructors of self-referential structs; a self-referential struct contains both the referent and a self-reference to it, and if you naively just drop the backing data, that would leave the self-reference (which was contained in an argument to the destructor function) momentarily dangling (that is, it would be a reference with invalid provenance). To prevent that from causing UB, a common approach is to wrap self-references in MaybeUninit to remove the validity requirements on the self-reference except at the times the self-reference is explicitly used. (Someday, there will be a MaybeDangling type for this purpose.)

The Rustonomicon's writing on the subject might also be useful.

  1. Could also be called its "pointee", or the reference's backing data. ↩︎

6

I am concerned about fake reads and fake writes. Let’s break them down:

Regarding Fake Reads: What is the actual purpose of a fake (speculative) read? If the data retrieved from such a read is eventually stored in a variable visible to the program logic, then it is not a 'fake' read—it is a standard execution flow issue tied to happens-before relationships, corresponding to a specific line of code.

Conversely, if the read data is never stored and remains invisible to the program logic, what is the actual harm? Why should we worry about a read that the program cannot observe?

Regarding Fake Writes: My concern is similar. If a write is 'fake' (speculative or reordered), but its effects are never committed to a state that other parts of the program can observe, it shouldn't impact correctness. However, if the compiler or hardware predicts a write or moves a store, could it cause a race condition or invalidate a cache line that other threads or subsequent operations depend on?

I need clarification on why these 'invisible' operations are considered a threat to soundness if they don't manifest in the observable program state.

7

The simple explanation is that the existence of a dangling reference is insta-UB, even you never try to read or write from it. ("Fake reads" and "fake writes" is merely one way to visualize the implications of that.) This has very little to do with happens-before relationships or speculative reads. Once you violate the contract with the compiler (by executing UB), all bets are off. This isn't about observable program state, just the rules for writing a valid Rust program, and the Rust language has the prerogative to define what's UB, no matter how arbitrary the rules seem to us.[1]

Of course, one could still criticize Rust if it had some absurd UB rules. If you're questioning the motivation for the compiler to declare dangling references to be UB, then sure, the finer details of optimizations would be relevant (e.g. moving invariant accesses[2] out of loop bodies probably depends on references being dereferenceable, and the way it reorders accesses might look like "fake reads" being inserted). When atomics are involved, the compiler is obligated to preserve the semantics of atomic orderings.

In my opinion as a user of Rust rather than a compiler dev, those details don't really matter. If your program has no UB, then the compiler has a responsibility to correctly compile your code, so you can trust it to only apply optimizations that don't change the semantics of your program. If your program has UB, then reasoning about what the compiler or hardware does is very likely futile. Behind-the-curtain details can give context to Rust's rules, which might help one understand and remember the rules, but I've written plenty of advanced unsafe without needing to think about what happens behind the curtain.

  1. Though, even if your code has no UB, the "fake reads" can still mess with volatile accesses. Volatile memory has to be accessed via raw pointers and should never be put behind a reference, in order to ensure that no spurious accesses occur. I can't think of other UB-free edge cases off the top of my head. ↩︎

  2. That is, accesses which don't "vary" with the loop index, and don't change across iterations. Doing them once, before the start of the loop, may have an equivalent effect. ↩︎

1 Like
8

Consider this specific example:

pub fn example(ptr: &mut i32) -> &i32 {
    let reborrow = &*ptr;
    reborrow
}

This is perfectly safe code. However, if the compiler were allowed to arbitrarily insert a 'fake read' using the original mutable reference:

pub fn example(ptr: &mut i32) -> &i32 {
    let reborrow = &*ptr;
    let _ = fake_read(ptr); 
    reborrow
}

Then this would become UB, because you cannot access a parent mutable reference while an active child immutable reborrow exists. This 'fake_read' would be something the compiler inserted. If it weren't there, I would not have accessed ptr after creating reborrow.

The key point is that the insertion of 'fake reads' cannot be truly random or arbitrary; the compiler cannot just do whatever it wants.

We need precise rules to predict whether a 'fake_read' will actually occur. If we simply say it 'can happen at any moment,' then even the most basic safe code would be considered potentially UB

9

Yeah, saying it can happen "at any time it's in use" was going too far. There are a bunch of situations that prevent fake reads from being inserted, and TIL there are even some at the LLVM level. The idea of dereferenceable is that loading from a dereferenceable pointer should never trap. But apparently its interactions with noalias mean that there are times that even LLVM isn't allowed to load from a dereferenceable pointer. (And by "not allowed" I mean that the compiler isn't allowed to introduce UB into a previously UB-free program.)

My impression, though, is then that if the compiler "knows" that it "should" be allowed to insert a fake read to a reference, then it could.

I'm digging around for information about this, and so far I've turned up:

It seems like the fake reads (and/or writes) inserted by Rust's front-end are probably always at the start of functions? Though backend LLVM optimizations like LICM can also end up hoisting reads from pointers marked dereferenceable, which results in something akin to a fake read.

In particular, it seems like Miri models the dereferenceable attribute through a mixture of fake reads (and, for mutable references, fake writes) on entry to functions as well as "strong protectors" that, for the duration of a function call, protect references passed as function arguments from being invalidated.

This is starting to get into implementation details of the compiler, though. I'm fairly sure that Rust's documented aliasing rules are strictly stronger than the rules that are actually implemented in optimizations and checks, so following the aliasing rules should be sufficient to imply that any fake reads which end up being inserted by the compiler as part of its optimizations or checks should be sound.