Possible to interleave &mut and & safely?

[joshlf]

I'm working on a linked list implementation for an embedded kernel. We have the following Thread structure, which will be a member of a list:

struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    t: T,
}

struct Thread {
    stack: [u8; STACK_SIZE],
    id: u32,
    ...
}

The stack is the thread's stack, which will be used to hold arbitrary Rust values, which might include &mut references to other values in the stack (i.e., it might be self-referential). (While pinning is obviously a concern, that's not what this issue is about.)

In addition to self-references in the stack, we also need to be able to inspect other fields in Thread from inside the scheduler.

Here's an example - possibly problematic - sequence of events:

1. Some code runs in the thread which writes a &mut reference to the stack that also refers to the stack.
2. The thread yields control, which hands control over to the scheduler
3. The scheduler obtains a &Node<Thread> reference to the currently-running thread and reads its id field

While, in (3), we haven't read data from stack, I presume that it's still considered UB to have a &Node<Thread> while other &mut references exist which point into the stack, which overlaps with the referent of the &Node<Thread>?

My first thought was to just wrap the whole thing in UnsafeCell so that the Node API doesn't provide &Threads, but instead provides &UnsafeCell<Thread>s. But IIUC that doesn't solve the problem - it's still illegal to have &UnsafeCell<T> and &mut T overlap.

My next thought was to just use raw pointers and never synthesize & references.

Concretely, my questions are the following. All of them are in the context of &mut references existing which refer to stack.

• Given a NonNull<Node<Thread>>, is it sound to perform pointer arithmetic to obtain a NonNull<u32> and dereference it? Specifically, is it problematic that the original NonNull<Node<Thread>> refers to the whole Thread, including the stack?
• Is there any way to provide a non-raw-pointer API which provides access to the inner T in a Node<T> which would play nicely with this use case?

[CAD97]

Even in the absence of reads, it's exactly the "pinning problem," or well, the aliasing part of it, not the stable address part. The stack bytes will need to only ever be &-reborrowed behind UnsafePinned/UnsafeAlias to prevent any &-retags from invalidating active interior &mut-borrows.

The other options are only using raw pointers, such that retags don't occur, or using a type with identical layout which does not cover the stack bytes, only the "header" fields that matter to the kernel, not the managed thread. (And in the models that only have type driven retagging, not field driven "precise" retagging, this practice can improve the optimization potential, at the expense of more typing effort.)

[CAD97]

If Thread manages memory allocated to an AM which is not the managing Rust AM, then things change and get Interesting™. At the least UnsafeCell is still necessary because the value in the bytes is changing, but the "rehydration" style argument like arguing that "the derived &mut are only ever used during Future::poll" becomes more plausible to then justify (assuming the foreign AM indeed does only run while &mut access is held and given to it). Then what matters is whatever shared FFI lowering is being used to communicate between the two AMs, and a general answer becomes near impossible to provide.

[joshlf]

using a type with identical layout which does not cover the stack bytes, only the "header" fields that matter to the kernel, not the managed thread

I considered this, but worried that I might run into provenance issues since, at some point in the future, I'd need to take a *ThreadHeader and "grow" it to be a *Thread, which might not have provenance for the trailing parts of Thread (at least in a world with sub-object provenance - is that still on the table?).

[CAD97]

The "&Header problem" is #256, and is still formally an open question. SB does not support such (and likely cannot), but TB does. Given that support is all but required in order to properly support extern type as a feature, I personally think it extremely likely that the eventually finalized model will support "lazy retagging" in a way similar to TB, even though it could maybe be limited to extern type tails, to make the issues around how these extended retags are handled (what retag flavor is done).

However, that potentially doesn't even matter for you here. Restricted provenance only ever applies once retags are involved; casting from Arc<HeaderAnd<Data>> to Arc<HeaderAnd<()>>, using dereferenced &HeaderAnd<()>, then casting the Arc back to Arc<HeaderAnd<Data>> preserves the original owning pointer provenance directly¹. It's still unsafe to do so, since if the last Arc dropped is the wrong type, you're deallocating the wrong thing, but it's at least possible to do soundly.

Footnotes

1. This technically relies on implementation details (Arc could store &'unsafe Inner instead of NonNull<Inner>), but these details are extremely unlikely to change. ↩

[RalfJung]

But IIUC that doesn't solve the problem - it's still illegal to have &UnsafeCell and &mut T overlap.

Not quite; RefCell::borrow_mut() in fact lets you create overlapping &mut T and &UnsafeCell<T>. As long as the &UnsafeCell<T> is not used to read or write the T, it is fine for the two to co-exist.

---

But also if that stack is the actual stack that Rust code in the same AM uses, then you have much bigger problems, entirely unrelated to the aliasing model and references. ;) First of all, it should be MaybeUninit<u8> as surely the stack can contain provenance and uninit memory. But worse, Rust assumes local variables to live in a unique allocation that is disjoint from all other allocations; you can't have that be true while also having some other allocation claim that it contains that same stack memory.

In the end this is similar to what happens in the global allocator: there need to be explicit transition points where the memory that stores the stack gets removed from the allocation that holds Thread, and instead becomes the backing store of stack variables, and then later one can transition back. At any point in time, the memory can only be in one of these states, and all pointers used to access the memory must be coherent with that state.

[joshlf]

In the end this is similar to what happens in the global allocator: there need to be explicit transition points where the memory that stores the stack gets removed from the allocation that holds Thread, and instead becomes the backing store of stack variables, and then later one can transition back. At any point in time, the memory can only be in one of these states, and all pointers used to access the memory must be coherent with that state.

Does Rust expose operations that instruct it to perform these transitions? How do allocators accomplish this?

[RalfJung]

Global allocators are registered specifically with #[global_allocator] and go through "magic shims" that add a bunch of attributes in the LLVM IR and that block inlining. I am not sure if this is 100% watertight since LLVM hasn't fully documented their model here, but it's at least something. Also see the discussion in #442.

If you want to do this entirely yourself, I think you need inline assembly "barriers" of sorts to clearly tell the compiler "there's some reorganization of the AM state going on here that I am not writing out in Rust code". We'd have to discuss the concrete case in more detail to say anything specific (and I don't currently have the time to really dig into the details, sorry).

[CAD97]

How do allocators accomplish this?

Mostly vibes, tbqh.

However, the vibes mostly work out. The magic layer happens at #[global_allocator], which "launders" pointers across the allocation API. Custom allocators don't have anything special going on; they're just code.

But, as far as I'm aware, the way to formally justify a #[global_allocator] existing in the same AM as code using global allocation is entirely an unsolved problem.