What do Send and Sync mean?

A while ago I wrote Diplomatic Bag as a way to deal with !Send types while inside a multithreaded Tokio runtime, where it's really helpful if everything is Send. It does this by spawning a globally shared worker thread and all operations on the types are performed on that thread, the user is just given a handle. While writing that I hit an existential question of what I was actually allowed to do with !Send types, and equivalently Sync types (I'm happy with T: Sync <=> &T: Send).

From the 'nomicon:

A type is Send if it is safe to send it to another thread.

Following the letter of that statement, the worker thread can have a map of handles to values and allow those handles to send closures over channels to act on those objects. However, all the values must have the 'static lifetime as their lifetime can't be lexically related to the handles.

Following more of the spirit of that statement, the handle could be the bytes of the type hidden behind ManuallyDrop. Now lifetimes work as expected, but the value may be living in another thread's stack frame. The worker thread will see references to it, that will look no different than if it was on the heap. You also have to occasionally pass the bytes over a channel to and from the worker thread but that will just look like the value has moved (Pin could be interesting but I don't think it matters).

Breaking things further, as long as the operation on a different thread doesn't know anything about the type then nothing it could do could break the !Send-ness of the type? This is most easily demonstrated in this bit of code which turns a Handle<Result<T, E>> into a Result<Handle<T>, Handle<E>>, all on whatever thread the Handle happens to be on. I think this is safe because Result doesn't introduce any !Send-ness but this is stretching things.

At the extreme, a !Send type could have some methods on it that are safe to call from another thread because they don't touch whatever part of the value makes it !Send. That makes me wonder if send-ability of values is even the right way to model this.

So, what is unsafe code allowed to do with !Send types?

Some previous discussion happened on Reddit here.

Just my personal view / interpretation, but all that you’re saying sounds very reasonable.

This sounds sound to me because, similar to other methods you offer like as_ref, it’s an operation that doesn’t call any unknown/custom code that might rely on the : !Send bound. My interpretation is that doing the Handle<Result<T, E>> to Result<Handle<T>, Handle<E>> conversion would be legal on the worker thread. But doing it on any other thread can’t make any difference whatsoever since we know all the behavior of doing the case-distinction and re-wrapping of the Result type, so it’s allowed on any thread and just an optimization over the naive „do it on the worker thread“ approach.

So this is the generalized statement on why the Result example is sound. It’s important to note that it’s possible to drop a value of any type, but dropping a !Send type on the wrong thread it most definitely unsound. So as long as you also exclude any dropping, then yes this should be true. Note furthermore that without knowing anything about a type, traits like Any, or in the future things like specialization can allow untrusted code to still acquire specific knowledge about the type anyways and violate the !Sendness. So don’t try to formalize this observation into any kind of API where a user would just need to provide some fully-generic function for interaction purposes and then that’s executed on a different thread than where the !Send value came from.

I think that this can also be modeled with the current Send trait. You’d need to explain more concretely what exactly you mean by “call from another thread”, whether this is about moving the value over to another thread and calling a by-value method on it or about calling a by-reference (potentially mutable reference) method / function / operation / whatever on a different thread.

A type that wants to allow certain forms of interactions can offer some API that creates reference-like values that implement Send, or it can offer a Sync newtype and an API creating actual references to that through some transmute / etc. In either case only offering a subset of methods on that wrapper or newtype, respectively.

Regarding a by-value interaction, there’s always the problem that once you’ve moved the value out of its thread, you cannot easily drop it anymore. Your DiplomaticBag seems to solve this by keeping a single, global thread around forever, so there’s always a way to bring the value back to it’s original thread before dropping it. But I don’t see how to give any more granular control on this other than the current Sync/Send threads.

1 Like

Ah, maybe I misunderstood you on this one in my previous response. I’d be curious if you can come up with any other model that could help here. (Not necessarily a very detailed or complete model, and perhaps limited so one of a few of your own examples).

By the way, after looking at your crate, I’m wondering why BaggageHandler has a lifetime parameter. And also why there isn’t a general public run<R: Send>(f: impl Send+FnOnce(BaggageHandler) -> R) -> R kind of top level function, only DiplomaticBag::and_then which requires that you already have a DiplomaticBag at hand.

Also, the Drop implementation could probably be optimized with mem::needs_drop.

Another useful thing might be an optimization (to the implementation of try_run) that could check if the current thread is already the worker thread for DiplomaticBags, which could – if I’m not mistaken – enable some usecases where DiplomaticBags are used recursively and prevent some deadlock settings. I haven’t tested it but if you’re currently doing things to a DiplomaticBag you created inside of an .and_then() call, like equality testing, dropping, etc… then that will deadlock, right?

I'll have a think about other models. The biggest thing is that it would be nice to be able to implement those transpose functions without any unsafe, or at least provide something that would allow a user to implement their own versions for arbitrary containers.

BaggageHandler has a lifetime parameter soley because I was getting paranoid while writing it. It not being Send is definitely enough.
I'm not sure why run and try_run aren't public, I think the answer is actually just that I didn't need them.

I didn't know about mem::needs_drop!

I hadn't noticed that deadlock possibility, you're right. Although, you should be able to avoid it by using the BaggageHandler.

1 Like

So, I haven't dug into the details of the code here, but I can try to shed a bit of light on how we formally modeled Send and Sync in RustBelt, for the purpose of proving correctness of these trait bounds.

The cornerstone of RustBelt is the idea that every type comes with an invariant saying what shape the data needs to have to be a valid inhabitant of the type, and what things need to be owned. (This is what I usually call the safety invariant.) One peculiar aspect of Rust is that the invariant actually goes a bit further than that: a normal invariant would answer questions of the form "are these bytes a valid inhabitant of this type?". Rust has ownership, so the question extends to "are these bytes a valid inhabitant of this type, given these owned resources?". ("owned resources" here mostly mean memory, i.e., invariants can demand that one needs to own or borrow certain memory regions. But other things can be owned, too.) Safety invariants in Rust then go even further and actually answer questions of the form "given these owned resources, are these bytes valid inhabitants of this type in this thread?". For example, the invariant of Rc will say that for some bytes to be a valid Rc in some thread identified by thread ID t, it must be the case that thread t currently has the right to read and write this memory freely without fearing interference from other thread. We premuse here a mechanism whereby ownership can be tied to a particualr thread ID t, so that all code running in that thread can access this ownership without any particular function / module being the sole owner.

This is in contrast to Box which demands that the underlying memory be locally, fully, exclusively owned by whoever claims to have a valid value of type Box. The difference becomes clear when you consider giving that ownership away: a Box can be given away since you own it; with an Rc that's harder because the thread owns it, so it is not exclusively yours and hence it is not yours to give away.

Now Send is defined simply as: a type is Send if its invariant does not care about the thread ID t. As a consequence, Box is Send but Rc is not. (These are now theorems we can prove.)

For Sync, the situation is similar: types in Rust actually have two safety invariants, one for when they are exclusively owned and one for when they are shared. The sharing invariant can depend on the thread ID t the same way the ownership invariant can. Sync means that the sharing invariant ignores t.

So, what does this mean for unsafe code? Well, whenever unsafe code calls "external" code fn foo(x: T), it needs to prove that the safety invariant of T is satisfied by the data in x in the thread where the call happens. If T: Send, this is equivalent to saying "the safety invariant is satisfied in any thread", since we know that the invariant does not care about the thread ID. But if T: ?Send, then you need to have some argument why this data is valid at type T in this thread. Usually, this argument will be based on "some external code gave x to me in that thread, so I may assume it satisfies the invariant in that thread".


As a small addendum, the reason DiplomaticBag style manipulation may be sound (not asserting it is or isn't), is that while validity invariants must always be true, (I believe) no validity invariants care about threads, only safety invariants. Safety invariants are about how the value is used, not how the value is, so may be temporarily broken by unsafe code with special knowledge.

Thus, it is potentially sound to "violate" safety invariants, so long as you don't actually violate the safety contract. Concretizing that a bit more, it is potentially sound to move !Send values between threads, iff they are not used in threads other than the thread that is allowed to use it.

And coming to the specific question in the OP: it is possible, given a known wrapper type that is itself Send, wrapping a !Send type, it is theoretically possible (again, not asserting this case is or is not UB, because I don't have that confidence currently) to manipulate the wrapper in a "nonnative" thread, again, so long as the !Send part does not have its safety invariants broken, i.e. is not "used" outside of its preferred thread.

The problem in a generic context comes from actually preventing the !Send type from being "used" in a different thread, if it's exposed at all to different threads. The only valid thing you can do to the type is move it around; anything else that potentially runs user code, including dropping the value, is forbidden. Basically, you're working with void*C.

(Switching to opinion, and no longer asserting any amount of correctness beyond personal, flawed belief:)

It is almost certainly unsound to provide a simple way to apply generic transforms to wrapper types off of the owning thread. There are just too many ways for a consumer to potentially regain knowledge about the type in a safe-if-you-didn't-exist way that would break your system.

However, it might be possible to provide an API that allows for<T: ?Sized> Fn(...) -> ... to work, provided you don't feed in Wrapped: !Send directly, but rather MyReprTransparentWrapper<Wrapped> instead. I don't know if it would be sound, but I think there's potential it could be. But note the ?Sized bound; this requires the value to always be behind an indirection. Using for<T: Sized> would be unsound, because the value could be dropped -- though again, perhaps adding a ManuallyDrop layer in there would allow dropping to just be a logic error and leak? I'm very unsure of everything after the <hr/>.

Yes, that is definitely sound. If you get an: x: T in some thread, then you may do whatever you want with the underlying bytes as long as you only treat them as raw bytes. It is only when you actually pass that data to some other function that expects an x: T that you have to prove the safety invariant, so that last step has to happen in the same thread where you originally got hold of the x, and the bytes must be wholly unchanged. (In some sense you never moved x: T to another thread, since those bytes never were identifies as having type T in that other thread.)

Not really, unsized locals exist at least as an unstable feature. Please don't ascribe extra semantics to existing traits that are not documented: Sized is about sizedness, it has absolutely nothing to do with indirection.

1 Like

Sorry for taking so long to reply to this, and thanks for all the help.

I'm now much happier that what I'm doing is safe, although I'll open an issue in the UCG repo to see if I can get that agreed a bit more formally. One thing that worries me is that I believe Send and Sync could reasonably be validity invariants, it doesn't seem crazy to assume that the compiler might be able to do some optimisations if it can assume some memory will never be accessed by a different thread. (I don't think that's true at the moment but could be in the future)

I've also convinced myself that there's no way to provide a safe API for unwrapping arbitrary wrappers (without some kind of higher-kinded types), because to unwrap it you'd have to give someone the raw wrapper, at which point they can access the T in safe code and it all goes boom.

EDIT: Scratch that comment about validity invariants, you'd end up with some types that are neither !Send or Send, which would be unfortunate (e.g. types that can be accessed from exactly 2 threads).

The UCG issue is here: `Send` and `Sync` · Issue #293 · rust-lang/unsafe-code-guidelines · GitHub

The compiler does do such optimizations, but it has nothing to do with Send/Sync. :wink: The optimizations are based on "data races are UB". Send/Sync then exist to ensure that safe code never hits that UB.