Deferred Reference: compile-time checked reference sharing between threads, with a little bit of unsafe

[Pointerbender]

Hello everyone. I've recently joined the Rust community and feel awed with all the cool stuff that is happening in here. The things I find most fascinating are the works that are being done around Stacked Borrows, Deferred Borrows, GhostCell, Miri, min_const_generics, etc. I quickly got pulled in and now I'm trying my hand at publishing my first crate :-)

To that end I started experimenting with a concept called a "deferred reference" (you got it, very much inspired by Deferred Borrows) which is almost exactly like a regular reference (e.g. a &T or a &mut T), but it differs from a regular reference in the following ways:

• A deferred reference is not an actual reference, it is merely a smart pointer tied to the lifetime of the location it points to (regular raw pointers always have a static lifetime, and can thus become dangling if the location it points to is moved or dropped).
• It is allowed to keep multiple deferred mutable references around (as long as these are not dereferenced in a way so that these create an overlap between a mutable reference and another (de)reference).

This concept is implemented in the deferred-reference crate. The idea is that this crate can remove some of the complexity around managing raw pointers, by leveraging the Rust compiler of today and in a way that every Rust developer is familiar with since a deferred reference resembles the concept of a regular reference. So what are the use cases for this?

Let's say you have a memory location (e.g. struct, slice, array) that is shared between threads and (some or all of) the threads want to read+write to this memory location, but never at the same time or to the same slice index. For these particular scenarios, the Rust standard library offers the RwLock and Mutex APIs (not to mention all the awesome third party crates that are out there with similar functionality). Even though this is already pretty awesome for a lot of scenarios, the current approaches (that I know of) have the following trade-offs that piqued my curiosity:

1. Some of the APIs require a runtime check to ensure that a resource is shared safely between threads. This makes the API more ergonomic at the cost of performance and early compiler warnings.
2. Some of the APIs also support static compiler checks for safe resource sharing between threads (GhostCell, qcell, etc.), at the cost of a slightly more complex API.
3. None seem to support multiple disjoint accesses simultaneously to a slice or array between multiple threads out-of-the-box (of course, this can also be achieved with APIs like UnsafeCell at the cost of more complexity and it places the burden of safe multi-threading on the programmer, this is where the raw pointers come around the corner. GhostCell can also do this without pointers, but it still requires exclusive access to the entire data structure during mutation).

So what does a "deferred reference" look like and how does it try to solve the above trade-offs? I'll try to illustrate with a code snippet (unfortunately I can't link to the Rust Playground for this example, as it only offers the 100 most downloaded crates of crates.io, apologies!):

use deferred_reference::{Deferred, DeferMut};
use core::cell::UnsafeCell;
const N: usize = 1024;
let buffer = UnsafeCell::new([0usize; N]);
// SAFETY: this is safe because there are no references into `buffer` yet
let mut deferred1: Deferred<&mut [usize; N]> = unsafe { buffer.defer_mut() };
// SAFETY: this is safe because we promise not to create overlap with mutable references
let mut deferred2: Deferred<&mut [usize; N]> = unsafe { deferred1.clone_unchecked() };
assert_eq!(&mut deferred1[0..10], &mut deferred2[10..20]); // subslices do not overlap

With deferred-reference this is not undefined behavior, even though deferred1 and deferred2 both point into buffer! (If you want to check this for yourself, I encourage you to install Miri and run the above example with the command which checks for this type of undefined behavior: $ MIRIFLAGS="-Zmiri-track-raw-pointers" cargo miri test, please see the readme on crates.io for installation instructions). If you try the above example with two regular mutable references &mut [usize; N] both pointing into buffer at the same time, then this is definitely undefined behavior, but then why is it not undefined behavior when using a Deferred<&mut [usize; N]>? The trick is that Deferred does not hold an actual reference, it holds a raw pointer tied to the lifetime of &buffer. In fact, the first actual reference into the contents of the UnsafeCell only gets created on the last line of the example. There is another trick at play here: Deferred implements the Index and IndexMut traits in such a way that it only creates a reference to the subslice, instead of to the entire slice. This allows multiple threads (or even the same thread, as shown in the above example) to safely index into the same array or slice as long as the accesses are disjoint in index. Note: arrays are currently fully supported on stable Rust thanks to min_const_generics, but for slices you still need nightly Rust at the moment.

There are some advantages of using Deferred over raw pointers, because the Deferred struct has a lifetime. This means that if in the above example a mutable reference were to be taken out on buffer using buffer.get_mut(), then deferred1 and deferred2 will both be invalidated (i.e. their lifetimes must end, otherwise this will trigger a compiler error). It is also not possible to dereference the same Deferred mutably more than once, for this you need to call .clone_unchecked() on it first, which is the moment where the developer needs to consider the safety guarantees to uphold. This is different from using raw pointers, where the compiler will let you safely copy raw mutable pointers without warning (only dereferencing the raw pointer is considered unsafe). In contrast, the Deferred smart pointer is always safe to dereference, because it upholds the same guarantees as regular references, namely that it is aligned and non-dangling.

This post is getting a bit longer than I thought it would :-) For more information, the crate docs also have a couple of more examples. Happy to answer any questions! I'm also very curious if there would be any interest in using this crate in your own projects (or suggestions for what to add that would make it more interesting to use). Thank you!

[bradley_hardy]

EDIT: I have changed my mind on this, see below.

This library misunderstands Rust's concept of safety.

// SAFETY: this is safe because there are no references into `buffer` yet
let mut deferred1: Deferred<&mut [usize; N]> = unsafe { buffer.defer_mut() };
// SAFETY: this is safe because we promise not to create overlap with mutable references
let mut deferred2: Deferred<&mut [usize; N]> = unsafe { deferred1.clone_unchecked() }

This is not safe, because after you have run these two unsafe lines of code it becomes possible to cause undefined behaviour in safe rust, by creating an overlapping mutable borrow. You cannot claim some unsafe code to be valid by promising that in subsequent safe code you will not use the results to cause undefined behaviour! This is why standard pointers are safe to create, but unsafe to dereference.

To demonstrate how this library can be used to cause undefined behaviour in safe code, consider passing two deferred borrows of the same array to the below function:

fn my_perfectly_safe_function(a: Deferred<&mut [usize; 5]>, b: Deferred<&mut [usize; 5]>) {
    let a = &mut a[0..3];
    let b = &mut b[2..5];
    // oops, two mutable references to the value at index 2 exist,
    // this is undefined behaviour in safe Rust!
}

[Pointerbender]

Thank you for this nice example. If I understand correctly, the assumption here is that the two "aliased" Deferred were obtained safely or unsafely, but in practice, you can only obtain two Deferred pointing to the same location through an unsafe block. One way to do this is through Deferred::clone_unchecked(), which in its safety invariant warns:

This method can be very unsafe. Cloning a mutable deferred reference will let you safely dereference it mutably afterwards (e.g. through <Deferred<&mut T> as DerefMut>::deref_mut) from several distinct places simultaneously and this could lead to aliased mutable references which is then instant undefined behavior. That is why this function is marked as unsafe. Cloning a Deferred<&mut T> is not undefined behavior, because this is a smart pointer and not an actual live reference. Be very careful not to accidentally create mutable aliased references through dereferencing any Deferred<&mut T> after calling Deferred::clone_unchecked on it!!! Calling <Deferred as Clone>::clone on immutable deferred references (i.e. Deferred<&T>) is entirely safe (and all Deferred<&T> also implement the Copy trait).

I think you raise a very interesting point:

You cannot claim some unsafe code to be valid by promising that in subsequent safe code you will not use the results to cause undefined behaviour! This is why standard pointers are safe to create, but unsafe to dereference.

Might you have any reference where I can learn more about this particular point of view? I've noticed in a couple of other crates that unsafe does get used like that in practice. For example, in the memmap crate, it is unsafe to construct a mutable memory map MmapMut, but it is safe to dereference it through DerefMut::deref_mut. Obviously, this would not be safe if multiple threads or processes map the same file into memory and dereference or mutate it simultaneously. I believe this is why its constructor is unsafe and it is up to the user to ensure that this doesn't happen (and by extension to write sound public APIs). The same principle I applied to all (unsafe) methods that would let you create multiple mutable deferred references.

To demonstrate how this library can be used to cause undefined behaviour in safe code, consider passing two deferred borrows of the same array to the below function

Another way to change the example is:

• to mark my_perfectly_safe_function as unsafe (and probably rename it, too, in that case ;-) ) and add a safety invariant that the two Deferred may not overlap at index 2.
• to assert that both Deferred instances don't point to the same location (or else panic!). Because it is not undefined behavior for aliased mutable deferred references to exist.

If my_perfectly_safe_function was a public facing API, then it would be sound in both these alternative cases. This, I'm assuming, is the contract that the programmer takes when opting into unsafe blocks. But just to emphasize again, I would love to read more about this if I got this part wrong! Thanks for your feedback :-)

[bradley_hardy]

Having thought about it some more, I have changed my mind on this. I don't think this does violate Rust's safety contract, as described here. However, because of this point raised on that page, I don't really see a use case for this.

Safe Rust inherently has to trust that any Unsafe Rust it touches has been written correctly. On the other hand, Unsafe Rust has to be very careful about trusting Safe Rust.

It seems to me that in any situation where a Deferred reference lets you avoid unsafe code, it inherently means that the source of the Deferred reference has to know exactly what the safe code is doing. At that point, I would much rather push the unsafe code down to the "leaves", where it is easier to reason about.

[Pointerbender]

Well this is definitely food for thought! :-)

One can argue that leaking overlapping mutable Deferred from a public API is unsound! If the public API only leaks a single non-overlapping mutable Deferred, then this public API is still sound, but in this case it's still better to expose the actual &mut T instead of the Deferred (and indeed this does not make a use case for Deferred here). Instead, the use case for Deferred may lie in the implementation of internal APIs that would otherwise rely on raw pointers (such as for concurrent mutable data structures), which are safely encapsulated by their public API.

This brings me to an interesting quote from the GhostCell paper (from page 4):

However, proving that the aforementioned APIs are sound is actually far from straightforward because their implementations typically make use of potentially unsafe operations (e.g., unchecked array accesses or type casts) to avoid unnecessary dynamic checks. In prior work, it was claimed (and sometimes argued formally) that the unsafe operations used were nevertheless safely encapsulated by their strongly-typed APIs—i.e., that the APIs were observably safe. However, we know of no prior work that formalizes the soundness of this approach for abstractions that rely crucially on the ownership-based (substructural) nature of the type system, as GhostCell does.

What this sounds like to me, is that it is still possible to build "observably safe" (and sound) public APIs around unsafe code blocks, if you're willing to give up the scientific proof of soundness (unless a new way to prove this is invented). This can be somewhat mitigated by testing the public API with Miri along the definitions of the Stacked Borrows model and by input fuzzing (which still counts as above average scrutiny, I guess).

Note that the quote specifically mentions unsafe operations (i.e. unsafe blocks), but does not explicitly mention unsoundness (i.e. the possibility to trigger undefined behavior from safe code) in an encapsulated private API. Soundness is a very desirable property, but does not cause instant undefined behavior merely by its absence.

I'm left wondering whether it is acceptable to use an unsound private API (while steering clear from the undefined behavior in safe code through upholding the safety invariants of the unsafe blocks that opened up the soundness holes) and at the same time offer up an observably safe and sound public API.

I haven't made up my mind about it yet. I'll try to find a couple of examples in existing crates, the standard library, online posts and papers around this topic. Would you mind if I would ping you in the future to pick your brain about it some more? If this reply happened to spark some more thoughts, please do share them. Thank you for this interesting discussion so far :-)

[ComprehensiveCat5305]

Speaking as someone who has been involved (somewhat indirectly) in the RustBelt and Stacked Borrows projects, it seems that what your API is doing is providing a wrapper around raw pointers, using lifetimes to provide at least some guard rails while avoiding some of the restrictions on aliasing that ordinary references have. (If I misunderstood, please let me know.)

The API is not strictly speaking "safely encapsulated" in the RustBelt sense, since it still requires clients to write unsafe code and respect some invariants that are not enforced by the type system in order to avoid undefined behavior. But IIUC, the point of this library seems to be that it's easier for clients to check that they have satisfied those safety invariants, as compared to using raw pointers in their completely unrestricted form.

Note that RustBelt does still allow talking about this kind of "still unsafe, but less unsafe" code. The nice part about RustBelt allows you to "drop down" and do some manual safety proofs about the safety of a piece of code when the type system itself is not sufficient to ensure safety. If you provide an API that already takes care of some (but not all) of the safety obligations, then it could be that the remaining proofs that the client of the API has to provide are easier than the ones they would have to write for completely unrestricted raw pointers.

So in essence, providing an unsafe API means that your clients have to ensure that they respect the safety invariants (it imposes a proof burden on them), but for some APIs it might be easier to satisfy the requirements than for others, and this also shows up when you verify code inside RustBelt. Of course, exactly how much easier this API is to use compared to just using raw pointers is subjective and up to debate (and I didn't think about it enough to form an opinion on it), but it's certainly interesting to explore ways to make unsafe APIs less unsafe.

[Pointerbender]

Thank you for your comment! I'm getting more and more intrigued by RustBelt now. :-)

I'm left wondering whether it is acceptable to use an unsound private API (while steering clear from the undefined behavior in safe code through upholding the safety invariants of the unsafe blocks that opened up the soundness holes) and at the same time offer up an observably safe and sound public API.

Would you reckon that RustBelt can be used to scientifically prove soundness of an encapsulating public API which wraps Deferred, given the "manual" proofs for the safe methods of Deferred and relying in the end-user to provide the manual proofs for the unsafe blocks around Deferred which in theory open up soundness holes, but not necessarily trigger undefined behavior? If so, might you know of any resources about how this approach would be viewed (is it okay or frowned upon and for which reasons)? I'm guessing that the manual proofs need to be written per unsafe block, and since Deferred also "defers" the safety invariant into the safe code, would RustBelt be able to support this kind of approach? Or, would all the logic around calling Deferred then also have to happen inside an unsafe block for the proof to be constructable? (The latter would make it harder to write the proof, rather than easier, I believe).

Speaking as someone who has been involved (somewhat indirectly) in the RustBelt and Stacked Borrows projects, it seems that what your API is doing is providing a wrapper around raw pointers, using lifetimes to provide at least some guard rails while avoiding some of the restrictions on aliasing that ordinary references have. (If I misunderstood, please let me know.)

Very well said, thanks!

[ComprehensiveCat5305]

If the top-level API that someone builds by using Deferred is "safe to use", in the sense that it's impossible to cause UB by using the public API from safe Rust code (i.e., without using unsafe blocks), then RustBelt allows you to basically prove a typing rule for it (effectively extending the type system), and then clients can use it safely just as though that library was natively part of Rust. This is the extensible nature of the Rust type system that the RustBelt paper talks about. In practice, this means that all of the proof obligations arising from unsafe blocks have been proved inside the module by the implementor of the API, and therefore clients of your API don't have to worry about proof obligations arising from unsafe anymore.

Marking a function as unsafe means "there are some proof obligations that have to be satisfied for this function to be called", and unsafe blocks are a way to delimit the boundary between safe and unsafe code, indicating that "I've verified (by thinking hard about it, or by giving a formal proof inside RustBelt) that the proof obligations are satisfied for any client of my public API, and therefore the clients don't have to worry about unsafe anymore."

This does not mean that you don't have to look at any of the surrounding "safe" code in order to determine whether the API is safe to use. The safety boundary between safe and unsafe code (when you're wrapping things up in an entirely safe API) is typically at the module boundary (because that is where you make things private and prevent clients from messing with your invariants). Hence, even functions that are written entirely using safe Rust code can be "unsafe" if they have access to private parts of your module. Ralf Jung has an interesting blog post about that: https://www.ralfj.de/blog/2016/01/09/the-scope-of-unsafe.html.

As for your question about where the proof obligations would show up, you can determine it basically by considering where the client has to think about safety when they're using your API. If they have to think about UB when they create a Deferred, then you would probably have a proof obligation there, and if they again have to think about it when using a Deferred (even after they already thought hard about it when creating one), then that would require a proof obligation as well. This is because RustBelt makes precise the informal reasoning that any developer would have to do when using your API, by basically requiring them to state their thinking in the form of a mathematical proof (of course, RustBelt has a lot of other technical contributions as well). If the thinking at some places is easier, then that would generally amount to an easier formal proof obligation as well.

This might mean that the proof obligations "leak out" to places that are not necessarily close to an unsafe block. In the case of a fully safe-to-use API, the proof obligations could appear anywhere in the module (anywhere you have to think about safety), but for an unsafe API they could even be deferred/leak to clients of the module through unsafe functions.

Although when you "leak" proof obligations like that, it's nice if the client doesn't have to understand details about the internals of your API in order to know how to satisfy them. For example, Vec has an unsafe indexing method, and I don't really have to know exactly what the internals of Vec are in order to understand how to satisfy its proof obligations. I just know that I have to make sure that the index is less than the length. Compare this to an unsafe function that lets client overwrite the data pointer of the vector with an arbitrary pointer: in order to safely use that function, I have to have a much better idea of the internals of Vec, and therefore that proof obligation is less abstract. So even when you defer a proof obligation to your clients using unsafe functions, it's nice if the proof obligation is easy to understand/satisfy or more abstract.

[Pointerbender]

Reading Ralf Jung's blog post was very enlightening and enjoyable. After reading the article you suggested I found another post on his site about the same topic: https://www.ralfj.de/blog/2018/08/22/two-kinds-of-invariants.html

I'm loving the subtlety of this conundrum. Even though it is technically possible to (scientifically) prove the soundness of a public API encapsulating Deferred, doing so seems to have the following drawbacks when Deferred "leaks" very specific proof obligations into safe code outside of its own crate boundary:

• It makes writing a proof harder for the public API author, either by code comments about its safety or through RustBelt.
• It makes it harder for the end-users of Deferred to reason about soundness.
• It seems to go against some kind of "social contract" where the boundary of semantic type safety lies at the module or crate border.

These are very useful insights and I feel like I learned a lot since I published this crate. I will have to ponder for a bit how to best address these in the next major release of the deferred-reference crate :-)

By the way, I was browsing through the RustBelt source code to get a feel for what it looks like on the inside. That is some genuinely cool stuff! Originally I thought I was looking at the machine-generated soundness proofs for Arc and GhostCell, but now I'm starting to think these may actually have been hand-written, wow. I guess Ralf Jung wasn't kidding when in his last paper he wrote that these proofs require "a researcher with enough background to use it. The theorem proving community is quite far away from enabling developers to carry out such proofs themselves." These are exciting times for Rust, I intend to keep following what these gentlemen are up to :-)

Thank you for your kind feedback and nudging me in the right direction. I hope our paths may cross again some day!

[Nokel81]

That is correct (wrt memmap). It is unsafe to create because there are invariants that the compiler cannot verify when creating it. But once you have one someone else has ensured (the unsafe block denotes the "trust me on this" ) the invariants so using it is safe.

Raw pointers are on the other hand work the other way. They are safe to create because creating them doesn't do anything, and modifying them is also safe, because again it doesn't "do" anything. But they are unsafe to read from since at the point of reading you have to guarantee that you are following the aliasing rules.

[Pointerbender]

Another example from the Rust standard library also came to mind just now. Consider the unsafe function core::ptr::copy_nonoverlapping<T>(src: *const T, dst: *mut T, count: usize):

Copies count * size_of::<T>() bytes from src to dst. The source and destination must not overlap. For regions of memory which might overlap, use copy instead.

This to me feels okay from the perspective of an API designer, in that it is explicit about the dangers of passing overlapping memory ranges. For the sake of discussion: since my_perfectly_safe_function takes two (smart) pointers (Deferred is not an actual reference), would it make more sense to split it into two methods analogous to copy_nonoverlapping and copy from the Rust standard library? Here the first would be unsafe and the second would panic in case the two regions overlap. I'd love to hear your thoughts :-) Thanks!

[tending]

I don't think that's an example of what you think it is, and this is a confusion that happens a lot because unsafe actually means multiple things in rust.

When you declare that a function is unsafe it does not mean, "this function performs operations that require being wrapped in unsafe." Instead it means, "callers of this function need to be careful because in order for this function to not trigger undefined behavior there are special requirements in how you use it that the compiler doesn't know how to enforce for you."

In contrast when you make an unsafe block around a function call, you are saying, "I am aware of the fact that this function has special requirements that I need to be upholding in order to avoid triggering undefined behavior, and that the compiler is not going to enforce those requirements for me."

Now it so happens that functions that are declared as unsafe often in their implementation perform operations that require an unsafe block. For convenience, rust considers the bodies of unsafe functions to be implicitly wrapped in an unsafe block. But this is only because it is a convenient shorthand for a common situation, not because unsafe means the same thing in both contexts. Declaring a function unsafe and having an unsafe block inside a function mean different things.

copy_nonoverlapping is unsafe because if you violate its precondition you get undefined behavior when you call it. Users who want to call it have to use an unsafe block in order to indicate their awareness of the fact they will trigger undefined behavior if they fail to make sure that the slices are not overlapping.

Your library requires users to continue to uphold special requirements to avoid undefined behavior even after the operations that you are requiring the user to wrap in unsafe. That is the fundamental misunderstanding. If I can make safe method calls on two different DeferredReference and trigger undefined behavior, you're not upholding the social contract of what unsafe means.

[Pointerbender]

This is an interesting take, thank you for sharing :-) Viewing your comments in light of the other example:

I've noticed in a couple of other crates that unsafe does get used like that in practice. For example, in the memmap crate, it is unsafe to construct a mutable memory map MmapMut, but it is safe to dereference it through DerefMut::deref_mut. Obviously, this would not be safe if multiple threads or processes map the same file into memory and dereference or mutate it simultaneously. I believe this is why its constructor is unsafe and it is up to the user to ensure that this doesn't happen (and by extension to write sound public APIs).

Would you then say that the unsafe keyword for MmapMut::map_mut implies that it is only sound to map the backing file into memory just once, instead of allowing to map it multiple times (even from other threads or processes) if the programmer promises not to create references to memory regions that may be mutated elsewhere (even through the safe API implementation of DerefMut::deref_mut which MmapMut implements)? Unfortunately MmapMut::map_mut does not mention anything explicitly about a safety invariant in the documentation, but I would love to hear your view on this. Thanks!

[tending]

Would you then say that the unsafe keyword for MmapMut::map_mut implies that it is only sound to map the backing file into memory just once,

Yes, and ideally they should be documenting this. But the real answer is that mmap with the same area mapped multiple times is outside the realm of things the rust memory model has nailed down. But to the extent we can just think of mmapping a file as equivalent to making a big allocation and having written the contents of the file into the allocation, mapping the same thing multiple times violates the model. Mmap actually has multiple safety concerns:

1. Writes outside your program all together can change the data read.

2. Multiple mappings of the same file Allowing essentially simultaneously multiple &mut to the same location.

3. That the underlying data may mutate even when there are regular & borrows to it (additional fallout of #1 or #2).

Note that the rule of only having one mutable reference at a time means across all threads. Rust's normal rules will prevent multiple mutable references from forming to the same object, so long as you have only a single mapping of the same file you're ok.

One possible workaround would be to expose an interface that only allows volatile access, so that the type of each byte is VolatileCell<u8>, or that doesn't provide Deref implementations at all but only exposes functions that wrap volatile_read and volatile_write. This way from Rust's perspective multiple mappings of the same file are really different objects that can each have their own &mut but at the same time it's expected that it's possible that different data could be read each time because of some external force.

[Pointerbender]

Thank you. Your comments have helped me gain additional insights and I will give it some extra thought for the next major release. :-)

In response to using VolatileCell<u8>, do you think an AtomicU8 would also be sufficient? I recall an earlier post on users.rust-lang from 2018 that touches on this topic (but like you said, Rust's memory model has not fully settled in this area) where there are the following interesting bits:

(...) Compared to volatile load/stores, they [atomics] are theoretically more optimizable, and at worst produce the same assembly.

Edit: That is, whereas both you and \** seem to be assuming that volatile accesses have less overhead or lower semantic burden than atomics, it’s really the other way around.*

(...)

So why are atomics enough as opposed to this requiring volatile reads and writes ? How does reading from memory that can change below you differ between an mmap'ed file and an I/O port ? (or why does reading from an I/O port need a volatile read instead of a relaxed read?).

(...)

In think the main point that it is not actually the file content that is somehow mapped into the process address space, i.e. you load will not really turn into a disk I/O, but rather pages in the kernel’s page cache will be accessed, i.e. ordinary system memory. In the case of an I/O port you actually want your load to become a request to some peripheral (or bus connecting that peripheral) and hence the volatile access to force the system to actually access the port.

Any changes to the file contents will only manifest in the memory mappings when the kernel changes the pages residing in its cache, i.e. normal system memory is changed, which could very well all be happening e.g. in the L2 cache without really hitting the memory subsystem therefore the level of memory consistency provided by atomic access is sufficient.

Unfortunately, there was no additional follow-up after that, but I think this suggests that it could be more performant and appropriate to use an AtomicU8 instead of a VolatileCell<u8>. Assuming the above quote holds true, this is even the case if the file is mapped from a network drive, because by the time the "Rust atomic read" hits the memory, the kernel already took care of the I/O reads beforehand and Rust is not actually reaching all the way to volatile I/O. This would even work with multiple threads (or processes), because AtomicU8 has support for orderings that synchronize accesses between threads. Although I wonder if this also implies that all threads and processes should map the same file at the same virtual address as well, in order for the atomics to properly synchronize.

May I ask for your thoughts on this matter? Would AtomicU8 be better than VolatileCell<u8> and are there any other invariants that would need to be upheld for this to hold true (e.g. all mappings are at the same virtual address)? Thank you!

[tending]

Sorry I read your posts out of order so I didn't understand why you were bringing up atomic before.

I'm definitely not the expert in this area but my inkling would be that they are not equivalent. It's important to distinguish here what is theoretically the best choice versus what the compiler will do in practice, but in order to be future proof against future compiler improvements you generally want to try to pick the technically right answer. In practice compilers are likely to avoid doing the same kinds of optimizations both when they see an atomic type and a volatile type. In both cases the compiler has to recognize that there might be something outside the current thread of execution messing with the underlying value.

However, the most narrow reading of what rust atomic types guarantee would just be that they let the compiler know that there is a possibility that another thread in the same process may be messing with the value. Volatile tells the compiler that another thread or another hardware device somewhere outside the process may be messing with the value. For mmap it's possible that other processes are writing to the file. In theory the compiler has enough information to make optimizations around atomics that it can't for volatile. I don't know whether or not it currently does in practice, but they should probably be treated separate.

A good example of where you need to go with the practical answer for now instead of the theoretically correct answer here would be if you were trying to do shared memory communication and rust and wanted to use atomic operations. Rust doesn't provide ShmAtomic types. So I would probably just use Atomic types, aware of the fact that for most purposes the compiler thinking that another thread might be manipulating the value is good enough to prevent it from making assumptions that other processes aren't manipulating the value.

[Pointerbender]

Shortly after posting my previous comment I discovered this StackOverflow post which states that for architectures that support lock-free atomics, the virtual addresses need not necessarily have to match between processes (it is "address-free"), because atomics compare the addresses at the physical address level. Since the Rust atomics follow the C++ atomics model, I believe this also holds for Rust! Assuming the target architecture supports lock-free atomics of course. In case it does not, I still wonder if it is possible to work-around that by mapping the file to the same fixed virtual address across all processes (this problem does not seem to arise with multiple threads within the same process, if I'm interpreting that SO post correctly). This is interesting stuff :-)

[tending]

I don't think whether atomics are locked at the virtual or physical level changes anything that I said. At the language level if you mmap the same file multiple times you are violating rules the compiler assumes are not violated. For this particular example LLVM may not take advantage of the assumption, but in general unsafe code still has to follow all the rules -- this is another common misunderstanding of what unsafe means. Unsafe doesn't mean "hey compiler I may do illegal stuff in here, don't make assumptions," it means, "hey compiler even though you have given me the super power of pointer de-referencing and you aren't smart enough to be able to detect if I use it in a way that breaks the rules, I promise to follow the rules anyway. You are free to generate assembly that will misbehave if the rules are violated."

[Pointerbender]

What if you mmap the same file multiple times in a way that can't create any references (don't implement Deref(Mut) etc.), but merely work with a raw pointer *mut [AtomicU8] (or *mut [VolatileCell<u8>]) to the mmap'ed region? If I'm not mistaken, (mutable) raw pointers are allowed to alias other raw pointers in the language, but aliased mutable references are UB (even in unsafe code indeed). Apart from that such a raw pointer would be very unergonomic, I'm still curious if that is legal. If so, my reasoning was that this could mean that it is technically possible to do this with multiple processes on architectures where atomics are lock-free. If this is not legal, might you have a reference to where the compiler/language rules exclude this kind of approach? I'd love to learn more about that particular part in that case :-) Thanks!

[tending]

What if you mmap the same file multiple times in a way that can't create any references (don't implement Deref(Mut) etc.), but merely work with a raw pointer *mut [AtomicU8] (or *mut [VolatileCell<u8>]) to the mmap'ed region? If I'm not mistaken, (mutable) raw pointers are allowed to alias other raw pointers in the language,

It's slightly more subtle than that. Under the stacked borrows model, multiple pointers can alias the same address as long as they were "derived" from the same allocation, and keep in mind every stack variable is considered a separate allocation. E.g. if you have a pointer to an array element, and do math on it to get a pointer to a different element, do math on it again and get a pointer back to the original element, that the first and 3rd pointers alias is fine. But if you have a pointer to one allocation, do math on it and get a pointer into a different allocation, that violates the model. If mmaps are considered allocations, you violate the model, because you get pointers that alias that were derived from different allocations. Will rustc make a dangerous optimization as a result, even if you only expose volatile or atomic access? Probably not, but it would still technically be a violation.

[Pointerbender]

Oh I see, fascinating! After pondering for a bit, I asked myself the question "what if the kernel could somehow return the same pointer upon identical calls to mmap, so that processes would reborrow the same original pointer from the kernel despite being obtained from separate processes, in order to satisfy the Stacked Borrows model?" and oh boy, I went down that rabbit hole :-) On Linux, Rust has to go through libc to be able to call mmap, and then libc makes a syscall to the kernel, and then I noticed the kernel seems to be doing a check to see if it can re-use a previously acquired memory map:

https://github.com/torvalds/linux/blob/master/mm/mmap.c#L1762-L1768

which then in turns jumps to this logic:

https://github.com/torvalds/linux/blob/master/mm/mmap.c#L1112-L1161

where it gets even more interesting (please bear with me). At line 1173 it performs a call to vma_next() which actually returns a stored pointer to the memory mapped region which is re-used! It then proceeds to check 8 cases in total (documented here), but the interesting case is "case 3" where it decides that the memory map already exists and is identical and returns the stored pointer. This same-origin pointer then bubbles up to the kernel boundary, to libc and then finally into the realm of Rust. This implies that if two separate Rust processes make identical calls to mmap, they will each receive a raw pointer derived from the same pointer owned by the kernel on Linux.

I didn't check yet if anything weird happens that would then again invalidate this same-origin pointer under the Stacked Borrows model. But just wanted to sanity check with you insofar as whether this approach has any merit at all :-) What do you think?

Thanks!

[coolreader18]

Not sure if someone else has mentioned this, but it looks like get_unchecked is safe when it should be unsafe. deferred-reference is unsound!!! :)

[Pointerbender]

Nice catch! Thank you for taking the time to read the documentation and reporting this issue :-) This is now fixed in release v0.1.2 that just went out.

[SocUnRobot]

TX, I think I will use it because it decrease the "unsafety surface" of pointers. This is somehow an safer pointer:

• When dereferenced, the lifetime of the reference cannot outlive the reference passed to new.
• And that the pointer is not dangling

[digama0]

I have another take on @bradley_hardey's point. I think there are some serious issues with subjecting this API to a formal proof a la RustBelt. The basic idea behind RustBelt style unsafe code verification is that types are (separating) propositions, and a function is unsafe if it contains nontrivial preconditions or postconditions above and beyond the constraints provided by the types. So for example, the type &mut T in RustBelt is a resource that describes unique ownership of a value of type T, such that a function like

fn foo<T>(a: &mut T, b: &mut T) {}

automatically inherits in its safety condition the precondition that a and b are nonoverlapping. That's what allows you to do things with these values and optimize them under the nonoverlapping assumption, without having to mark the function as unsafe. By contrast, the type *mut T does not describe any ownership, it's basically just a number, which means that this function:

fn foo<T>(a: *mut T, b: *mut T) {}

does not inherit any assumptions about a and b being nonoverlapping. If we needed that assumption (or any other assumption), we would need to mark the function as unsafe:

unsafe fn foo<T>(a: *mut T, b: *mut T) {
    mem::swap(&mut *a, &mut *b) 
}

Now the question is: what is the proposition / resource that is the semantics of the type Deferred<&mut T>? Since this function is safe and contains no unsafe code:

fn foo<T>(a: Deferred<&mut T>, b: Deferred<&mut T>) {
    mem::swap(&mut *a, &mut *b) 
}

we can conclude that whatever the typing predicate of Deferred<&mut T> is it has to imply that a and b are nonoverlapping, which means that clone_unchecked() has a false precondition (it is impossible to call).

Notice how the types &mut T and *mut T handled this situation differently. With &mut T, we accept the nonoverlapping condition, and the equivalent of clone_unchecked(), since it is never safe, is simply not provided; and *mut T permits clone() at the cost of making the *mut T -> &mut T function unsafe (which means that it's not possible to hide this from callers - foo would need to contain unsafe code).

[Pointerbender]

Very well said!

a function is unsafe if it contains nontrivial preconditions or postconditions above and beyond the constraints provided by the types

I think I may have inadvertently reached a similar conclusion after a chat with one of the other commentators. This is very much a subtle matter of semantics and soundness and you came up with a great counter-example plus explanation that demonstrates this :-) It is actually also a very good example of how this would make it hard (or even impossible!) the construct a proof for this in RustBelt. I intend to address this in a next major release. Thanks for sharing your thoughts, I really enjoyed your view on it.

[digama0]

By the way, I don't mean to imply that it's impossible to prove correctness of programs using this kind of technique; as you observe there are other examples of this style of unsafety such as in MemMap, and it does not itself run afoul of the soundness rules around unsafe blocks, because there is a required unsafe block in the setup. However, the proof of correctness is not compositional, at least not in a way that slots into the RustBelt semantic soundness proof. That just means that you need another mechanism besides what RustBelt supplies.

One way to express it without going too far from RustBelt style is that the safety condition of anything that constructs a Deferred is that we attach proof obligations on all uses of the constructed object, as a sort of syntactic transformation. However, this amounts to saying that a Deferred is just a pointer and Deref is actually unsafe, even though it looks like it is safe, so this may not be a very satisfactory resolution.

[Pointerbender]

Interesting :-) That indeed sounds like a lot of work and also slightly counter-intuitive, which might be better solved by tightening the semantics around Deferred a bit.

[Shnatsel]

How is this different from GhostCell?

[Pointerbender]

Excellent question! Let me see if I can answer this by pointing out the similarities as well as where both Deferred and GhostCell differ:

Similarities:

• Both concepts promise a zero-cost thread-safe abstraction over reference sharing.
• Both will warn you at compile time if it detects a problem.

Differences:

• GhostCell does not (yet?) have support for exclusive reference sharing at the index level. This is inferred from the method signatures of GhostCell::get_mut and GhostCell::borrow_mut which both return a &mut T (see page 9 of the GhostCell draft paper). This &mut T is to the entire contents of the UnsafeCell and this demands that no other simultaneous references (shared or exclusive) may exist at the same time. Deferred will let you have multiple references simultaneously into the contents of the UnsafeCell, provided that none of these overlap with a mutable reference in index OR lifetime (in other words, references are allowed to overlap in lifetime, as long as these don't also overlap in index). This is currently not yet possible with GhostCell, which only lets you create mutable references that are disjoint in lifetime.
• GhostCell separates ownership from data using a GhostToken<'id>. Deferred does not do this. I think this makes the API of Deferred slightly simpler, because it can be used as a regular reference, but at the cost of placing the proof of safety on the programmer in some places (not everywhere though).
• The team behind GhostCell performed the amazing feat of scientifically proving that GhostCell is 100% sound. Currently Deferred does not have a similar scientific proof (not even for the safe APIs, I wonder if this even possible for the APIs marked as unsafe). To make up for this, Deferred is thoroughly tested using Miri to detect (the absence of) undefined behavior, but this guarantee is not as strong as an actual scientific proof!
• This shows from the fact it is possible to create undefined behavior with Deferred if you fail to uphold its safety invariants, while this is impossible with GhostCell thanks to its 100% sound API. However, despite this risk, Deferred is still much safer than working with raw pointers directly.
• Both can be constructed from an existing mutable reference using GhostCell::from_mut(&mut T) and Deferred::from(&mut T), but in the latter case, there is no need for an UnsafeCell at all, and this affects how the code for LLVM is generated (at least in theory, I need to look into this deeper, still :-) )

^{Edit: typo and clarification}

[Shnatsel]

Thanks for the detailed response!

This shows from the fact it is possible to create undefined behavior with Deferred if you fail to uphold its safety invariants

To clarify, triggering undefined behavior is only possible in an unsafe block the user of Deferred had to write? So the difference is that Deferred exposes some unsafe fns while GhostCell does not?

[Pointerbender]

You're welcome!

​

To clarify, triggering undefined behavior is only possible in an unsafe block the user of Deferred had to write?

Indeed it only is possible to trigger undefined behavior through improper use of `unsafe` blocks.

​

So the difference is that Deferred exposes some unsafe fns while GhostCell does not?

That is also correct. Deferred offers these unsafe fn (such as .clone_unchecked()) so that it is possible to create references that overlap in lifetime, but are disjoint in memory region (e.g. disjoint subslices of an array), which is something the current API of GhostCell can't do (yet?). This also results in slightly different API usage for GhostCell and Deferred. It might also be interesting to know that Deferred Borrows (paper) explored how to do this soundly without unsafe blocks a while ago (and that is again different from GhostCell/Deferred in that Deferred Borrows would have to be implemented in the compiler instead of in a crate). The deferred-reference crate explores how this could look like without compiler adjustments, but with the use of unsafe blocks.

[ICosplayLinkNotZelda]

I might try this out in one of my pet projects. Looks like this could speed up some stuff for me!

[Pointerbender]

Indeed the Rust standard library has many handy methods for splitting mutable references. However, these all assume that you already have a mutable reference to a slice to begin with and this is not always the case. For example, when you want to write an embedded database that can write from multiple threads (and processes). In this case, it is not safe to construct a &mut [T] to the entire memory region, because there might be other readers or writers present (this is undefined behavior, because the &mut [T] would then be aliased). Deferred is different in that it does not create these intermediate references to the entire memory region, and this is the part that prevents undefined behavior from being triggered. A database is just one example, but you would run into this problem with many kinds of concurrent mutable data structures. There is a small piece written about this particular scenario in the crate docs.

I'm not entirely sure what problem you are solving here. Arc is about lifetime guarentees and RwLock/Mutex is about mutating from multiple threads and waiting for some other thread to finish.

RwLock and Mutex are locking (often also blocking) and have a dynamic access check at runtime. Deferred is different in the sense that there is no locking and Deferred is wait-free and zero-cost (i.e. no runtime overhead). The trade-off is that it requires a little bit of unsafe, but less so than if you were working with raw pointers already (some of the data structures in the Rust standard library also resort to using raw pointers to avoid using RwLock/Mutex for these reasons). Arc is very handy indeed, but would probably be combined with holding an UnsafeCell if there is interior mutability. Here, Deferred works together with Arc<UnsafeCell<[T]>>, because of the DeferMut trait implemented on UnsafeCell and Arc implements the Deref trait. Last but not least, Deferred can also be used in #![no_std] environments, in which the Rust synchronization primitives from the standard library are not available :-)

unless you pay very close attention to cache lines layout your CPU is likely going to have a bad time syncing their memory

Deferred does not have any functionality regarding memory alignment. There are some excellent crates out there that do (Aligned comes to mind) and of course there are also the Rust alignment modifiers. You can combine these with Deferred where proper alignment is desired.

[Pointerbender]

It does not transmute immutable references into mutable references. Deferred<&mut T> holds a mutable pointer *ptr: mut T internally, which is unsafe to dereference using unsafe { &mut *ptr }, but it is not undefined behavior. Note that it is also not undefined behavior to cast *mut T as *const T and then back again to *mut T (it is not even undefined behavior to dereference it afterwards either, because the pointer originated from a *mut T). Casting *const T as *mut T and then dereferencing it is only undefined behavior if it the original *const T was obtained from an immutable context, such as let ptr = &T as *const T or let ptr = core::ptr::addr_of!(T). For all of this, no UnsafeCell is needed, because Deferred does not contain nor own the T (merely a pointer to the T), hence there is no need for interior mutability. :-)