Constants can contain references that are not Sync

[jDomantas]

This compiles (playground):

#![feature(negative_impls)]

#[derive(Debug)]
struct Foo {
    value: u32,
}

impl !std::marker::Sync for Foo {}

fn inspect() {
    let foo: &'static Foo = &Foo { value: 1 };
    println!(
        "I am in thread {:?}, address: {:p}",
        std::thread::current().id(),
        foo as *const Foo,
    );
}

fn main() {
    let handle = std::thread::spawn(inspect);
    inspect();
    handle.join().unwrap();
}

And prints this (addresses vary, but always the same):

I am in thread ThreadId(0), address: 0x5590409f7adc
I am in thread ThreadId(1), address: 0x5590409f7adc

Which shows that two threads get the same 'static reference to non-Sync struct.

The problem is that promotion to static does not check if the type is Sync, while doing it manually does (this does not compile):

static PROMOTED: Foo = Foo { value: 1 };
let foo = &PROMOTED;

Reading the RFC, it seems that the relevant condition is about containing UnsafeCell, but does not account for other !Sync types, which are also not supposed to be shared across treads.

[hanna-kruppe]

cc @eddyb

[eddyb]

If you can make the constant, and it's immutable, I'm not sure what you can do with it that's unsound - only unsafe code relying on it not being possible for one reason or another.

Rvalue promotion is like const with a reference in it, not like static. Actually, static itself could be relaxed too when interior mutability is not involved.

I'm tempted to close as "working as intended", unless there is more code to look at, which gets broken in one way or another by this capability.

[eddyb]

cc @nikomatsakis

[hanna-kruppe]

It seems in pretty clear violation of the Sync contract. While unsoundness seems unlikely in practice (you'd need a set up where the non-Sync values are used as "tokens" for something thread-local or thread-unsafe), at least in theory unsafe code should really be allowed to rely on non-Sync data being truly not shared across threads.

Edit: Hmmm come to think of it, this is complicated by the fact that Sync is an "at any given time thing", since Mutex and the like can make things Sync. Still seems bad to muddy the waters here.

cc @RalfJung

[nikomatsakis]

For better or worse (worse, I guess), this also builds:

#![feature(optin_builtin_traits)]

#[derive(Debug)]
struct Foo {
    value: u32,
}

impl !std::marker::Sync for Foo {}

const F: &'static Foo = &Foo { value: 1 };

fn main() {
}

[RalfJung]

Yeah I think this is a problem.

I imagine some (rather silly) pseudo-code like this, based on @rkruppe's idea of using Foo as a "token":

struct Event {
  address: usize,
  kind: EventKind
}

enum EventKind { Acquire, Release }

// A global event registry thing
static mut EVENT_LIST : Mutex<Vec<Event>> = Mutex::new(Vec::new());

fn add_event(e: Event) {
  unsafe { EVENT_LIST.lock().push(e) }
}

fn get_events() -> Vec<Event> {
  unsafe { EVENT_LIST.lock().clone() }
}

// Now comes the bad code
struct Foo(u32);

impl !Sync for Foo {}

impl Foo {
  fn acquire_release(&self) {
    add_event(Event { address: self as *const _ as usize, EventKind::Acquire });
    add_event(Event { address: self as *const _ as usize, EventKind::Release });
  }
}

const F: &'static Foo = &Foo(0);

fn main() {
  std::thread::spawn(|| F.acquire_release());
  F.acquire_release();
}

Playground version

Given that Foo is non-Sync, which guarantees that all pointers to the same &Foo live in the same thread, I think unsafe code should be allowed to rely (for UB) on the fact that the event list will never, ever contain something like (a, Acquire) (a, Acquire) (a, Release) (a, Release) for any address a. However, the code above could actually have exactly that outcome, with a being the value of F.

EDIT: See here for further elaboration.

[eddyb]

Given that Foo is non-Sync, which guarantees that all pointers to the same &Foo live in the same thread

Do we guarantee this anywhere? My expectation is that the fields of such an abstraction must be private, and that means you can only create the problematic global references in the same module.
And you might want those references, for a small set of special values that are valid cross-thread.

As another example, there are non-Send types in the compiler with special const values that happen to usable everywhere, regardless of thread-local state (e.g. Span's DUMMY_SP)

[RalfJung]

Do we guarantee this anywhere? My expectation is that the fields of such an abstraction must be private, and that means you can only create the problematic global references in the same module.

I think my Foo above is a counterexample. The only field does not matter at all, it can be public. It could also be entirely removed, just making it a unit struct.

As another example, there are non-Send types in the compiler with special const values that happen to usable everywhere, regardless of thread-local state (e.g. Span's DUMMY_SP)

That's a different thing. Even types that are not in general Send can have elements that are Send -- just like Vec has an element that is Copy.

[RalfJung]

So the conclusion from the unsafe code guidelines meeting yesterday (as far as I understood) is that we want to disallow this. Rvalue promotion should be thought of as implicitly generating additional statics, but with loser guarantees about address uniqueness. All restrictions of static apply, including the type having to be Sync. The open question is if we can do this breaking change, it is not clear how much code relies on this. There will be a crater run.

[arielb1]

With my current understanding of the semantics, there's nothing wrong with several different zero-sized values having the same address.

#![feature(optin_builtin_traits)]

struct NotSync;
impl !Sync for NotSync {}

fn main() {
    let mut u = NotSync;
    let mut v = NotSync;
    println!("{:?}", &mut u as *mut NotSync);
    println!("{:?}", &mut v as *mut NotSync);
}

[hanna-kruppe]

I think that's true, but this issue applies to non-ZSTs as well.

[arielb1]

@rkruppe

Sure. Missed that.

[RalfJung]

Right, this is not at all about addresses. Even ZSTs may not be duplicated as that may violate uniqueness guarantees, also see rust-lang/rust-memory-model#44. I see sending ZSTs across thread boundaries as similar.

[RalfJung]

Yeah so this is still open... how hard would it be to fix? @oli-obk @eddyb

[eddyb]

(unrelatedly, I made a comment somewhere else: #53851 (comment))

@RalfJung You would probably copy is_freeze and is_freeze_raw, to make is_sync, then use that the same way is_freeze is used, during promotion (both in rustc_passes and rustc_mir).

Note that it's slightly harder than the check for statics because we report that as an error, while for promotion, we need to make decisions (whether to promote or not) off of T: Sync, without erroring.

[RalfJung]

@eddyb Trying that now, let's see if that works.

[RalfJung]

@eddyb not sure what is going on, but it doesn't work... see RalfJung@623fa51. The newly added test fails to fail to compile (as in, it compiles). How can that be?

[eddyb]

@RalfJung The codepaths you changed are for unknown values of those types. You also need to handle ADT constructors, which is_freeze / needs_drop don't touch right now directly.

[RalfJung]

Actually promotion is far from the only problem as @eddyb pointed out...

struct Bar(i32);
impl !Sync for Bar {}

const C: &'static Bar = &Bar(40);

fn main() {}

We can have consts with non-Sync references that are shared with all threads. Ouch.

[eddyb]

Yeah, I'm surprised we didn't bring that up, since it's how the RFC defines rvalue promotion.

I believe the only reason static ever required Sync was interior mutability - we likely would've made it Sync | Freeze had we thought about it more.

That is, we were worried about synchronizing mutation, not address equality (which we treated as generally unguaranteed).

[RalfJung]

I think Sync is exactly the right choice for static and I am happy that's what we got. Logically speaking, a static is some piece of state that every thread can get a shared ref to any time. Sync is exactly the property saying "sharing those shared refs across threads is fine". Freeze does not imply Sync. Not once you accept that people can have arbitrary invariants on their types that we do not know anything about.

The reason promotion also cares about Freeze is because of the observable effects of merging different allocations into one. That is an altogether entirely different concern than synchronization across threads. It is a purely operational concern, and Freeze is a very operational statement (about the underlying representation of the type being impossible to change behind a shared ref).

[eddyb]

It has nothing to do with merging, and everything to do with not changing runtime semantics. You can only be sure the data isn't written to if you have &T where T: Freeze.

[RalfJung]

I think you are saying the same thing as me. Runtime semantics get changed when two allocations that start having the same content get merged (deduplicated) and one gets written to.

[RalfJung]

I have a proposed fix at #54424

[Dylan-DPC-zz]

Marked p-medium as per our prioritisation discussion

[taiki-e]

This is currently marked requires-nightly, but can be reproduced without nightly: playground

#[derive(Debug)]
struct Foo {
    value: u32,
}

// stable negative impl trick from https://crates.io/crates/negative-impl
// see https://github.com/taiki-e/pin-project/issues/102#issuecomment-540472282 for details.
struct Wrapper<'a, T>(::std::marker::PhantomData<&'a ()>, T);
unsafe impl<T> Sync for Wrapper<'_, T> where T: Sync {}
unsafe impl<'a> std::marker::Sync for Foo where Wrapper<'a, *const ()>: Sync {}
fn _assert_sync<T: Sync>() {}

fn inspect() {
    let foo: &'static Foo = &Foo { value: 1 };
    println!(
        "I am in thread {:?}, address: {:p}",
        std::thread::current().id(),
        foo as *const Foo,
    );
}

fn main() {
    // _assert_sync::<Foo>(); // uncomment this causes compile error "`*const ()` cannot be shared between threads safely"

    let handle = std::thread::spawn(inspect);
    inspect();
    handle.join().unwrap();
}

@rustbot label: -requires-nightly

[bstrie]

Now that it's been revealed that this is possible (if roundabout) on stable, should the priority on this be increased? What would it take to at least begin emitting warnings here, to prevent new code from taking advantage of this and making it even more painful to fix in the future?

[tgross35]

Is this something that could be tied to editions? If so, a timeline like this might be reasonable:

1. warn-by-default asap
2. deny-by-default 2023Q3/Q4
3. forbid with 2024 edition

The latest crater run from Ralf's PR #54424 indicated 18 regressions, but that's 4 year out of date at this point so occurrences could have gone either way.

[RalfJung]

It's not even that roundabout, see #67601 ``` pub const FOO: &'static *const u32 = &(&BAR as _); pub const BAR: u32 = 0; ``` This is part of the broad set of questions around observing pointer identity of consts. At least so far the only way I know of to observe this issue is to compare addresses. Basically we should have a lot of instances of this !Sync (but Freeze) type, one for each use, but they all get deduplicated. Maybe we just have to find a way to rationalize this... I don't have a lot of confidence that we can land a fix here. Making it a hard error only on sone editions does not really help: when I write a !Sync type I still have to consider users on old editions, and have to ensure my type is sound for them. Is there a known example in the wild of a crate that makes pointer identity arguments for !Sync types, a type that is broken by this issue?

[RalfJung]

Another approach to solving this problem would be trying to rationalize it -- what are the proof obligations for unsafe code authors to ensure that this rustc behavior does not cause unsoundness? If we change my example here to cause actual UB from these shared !Sync values, where does the soundness argument go wrong?

I feel like there are two ingredients to this:

• const behave exactly as-if they were inlined in every use site. This means the resulting value satisfies its safety invariant in all threads, since we know that it could just be re-computed in each thread and produce the same result as the precomputed result we inserted. This relies on const-eval being deterministic, and hence might interact poorly with CTFE heap allocation. (The entire "inlining" explanation could be tricky to justify with CTFE heap allocations.)
• For the case of my example, that can only be a sound API if Foo's field is private. Therefore, the inlined code could not actually have been written in the user crates. Therefore, there is a proof obligation with every const you declare in a module that has access to private fields: the final value of that const must satisfy its safety invariant for all threads. (That is in contrast to the usual requirement that a value must satisfy its safety invariant in the current thread. Of course, there is no current thread at compile-time, so that would not even be an option.) To attach a safety invariant to Foo: !Sync, the "shared" safety invariant of Foo must be thread-dependent. However, if the module exposes Foo(0) as a const, then Foo(0) must satisfy its safety invariant in all threads, and therefore for each thread one can obtain a shared reference to that value that satisfies its safety invariant -- which is in contradiction to that invariant being thread-dependent. Therefore the module is already unsound.

Basically: !Sync is not defined as "cannot ever have shared references to the same object in different threads". It is not defined at all; Sync is defined as "shared safety invariant is thread-independent". !Sync just means this property doesn't hold, but on its own it grants no extra powers. It's the adjusted (thread-dependent) shared safety invariant that grants powers! But those powers come with responsibilities and doing negative reasoning doesn't work, you still have to constructively justify everything you do. If you do that I don't think you can construct an unsoundness from my example.

I think I am less worried about this issue now and I am not even sure any more if it is a soundness issue. However, I am worried how it might interact with CTFE heap allocations.

[LegionMammal978]

The way I like to think about it is that "all pointers to the same &T where T: !Sync live in the same thread" has never been a universal invariant. Otherwise

pub struct Wrapper(pub *const i32);
unsafe impl Sync for Wrapper {}

would be unsound, since Wrapper could be used to get the same &*const i32 in different threads, even though *const i32: !Sync.

---

Instead, the actual invariant is, "once a &T is created on one thread, no one can safely move it to another thread using language features". If an interface controls a particular !Sync object that should only be accessible from one thread, then it's additionally responsible for making sure that:

1. The interface exposes no operation allowing users to safely access the object directly, except from the correct thread. For instance, it doesn't publicly expose a SyncWrapper(pub Object).
2. The interface exposes no (internally unsafe) operation allowing users to safely copy an &Object to any other thread. For instance, it doesn't publicly expose a SendWrapper(pub &Object).
3. Nothing inside the interface accesses the object directly on another thread.
4. Nothing inside the interface unsafely copies an &Object to another thread.

Conversely, if any of these responsibilities are not upheld, then there's no automatic UB or unsoundness: it just means that the object can no longer be treated as only being accessible from one thread. For instance, if you receive a &*const i32 from somewhere, then clearly it might be shared between multiple threads, in the absence of any other contextual protection.

---

The big question is, if a span of code is able to safely construct an object using language features, then should it be able to safely directly access it from multiple threads? If so, then an interface that wants to uphold responsibility 1 cannot allow its objects to be publicly constructed. If not, then such an interface can allow its objects to be publicly constructed. The importance of this issue is that this is the only language 'feature' that would allow safe direct access to the same object from multiple threads, without going through references. (The confusion here is that this is more about responsibility 1 than responsibility 2. We aren't really copying around references here, so much as creating multiple references directly, given access to the same underlying object from multiple threads.)

In @RalfJung's example, I don't think it's necessarily true that "that can only be a sound API if Foo's field is private". Suppose that Foo's field is public, and this issue is fixed. Then, even if outside users create as many Foo objects as they want, they will all have different addresses, so acquire_release() will always form valid pairs in the event list, relative to a single address. It's only if this is not considered an issue, and if it's considered safe to directly access a constructed object from multiple threads, that Foo's field must be private for the API to be sound. So the justification given seems to be begging the question a bit, in my view.

[LegionMammal978]

Also, I'd like to note that there's a big class of Freeze + !Sync types that don't involve external lists, and those are "remote Cells" that control access to an object at another address. To give a trivial example, one could write a Freeze CellWrapper type, such that a CellWrapper<'a, T> can be safely constructed from an &'a mut T, implementing the same operations as an &'a Cell<T>:

#![feature(negative_impls)]
use std::{mem, ptr::addr_of};

pub struct CellWrapper<'a, T>(pub &'a mut T);
impl<T> !Sync for CellWrapper<'_, T> {}

impl<T> CellWrapper<'_, T> {
    pub fn set(&self, val: T) {
        drop({
            // SAFETY: Since `Self: !Sync` and we don't unsafely share `self`,
            // `self.0` is unique for the duration of this block.
            let r: &mut T = unsafe { addr_of!(self.0).read() };
            mem::replace(r, val)
        });
    }

    // And so on for the rest of the `Cell<T>` API.
}

Clearly, allowing shared references to the same CellWrapper<'a, T> on multiple threads would be disastrous. But it's also clear that making its field public is completely harmless on its own accord, since &mut T already provides the necessary guarantees. It's only if we infer that public construction implies public cross-thread access that we end up with a problem.

[RalfJung]

In @RalfJung's example, I don't think it's necessarily true that "that can only be a sound API if Foo's field is private".

Oh you are right, somehow I thought the value of the field was relevant. But the field only exists to make this type non-zero-sized. (Here's an actually compiling version of the example.)

So... the safety invariant for shared Foo would be something like: the address that this Foo lives at is associated with the thread that holds the shared reference (the thread exclusively owns the right to add events with that address to the event stream), and right now, in the event stream, this address is not acquired (i.e., the even stream contains the same number of acquire and release, and any prefix of the stream contains either one more acquire than release or the same number of acquire and release).

acquire_release is safe since it runs in the thread that "owns" the address of the Foo, so it can rely on that thread's ownership of this address for event purposes for the entire duration of the call. Temporarily bringing the acquire and release count out of sync is hence fine.

The axiom that from &mut Foo we can get &Foo is satisfied, since for that transition we can take the exclusive ownership of the mutable reference to trade it against the current-thread ownership of the address in the event stream. (So we have some event stream invariant which is: all addresses are either unclaimed, or they are currently claimed by some thread and we own the memory at that address. When we have an &mut Foo, we know it has to be unclaimed as otherwise the address would be owned twice which is impossible. [This is all fairly standard separation logic reasoning, I apologize for just dumping that here.]) This is all actually more complicated since there are lifetimes involved, but I think it should work. (Really, addresses are either unclaimed or "claimed by some thread for some lifetime".)

Okay then, what happens when the &'static Foo is created? Const-eval creates a Foo somewhere and then needs to use the "&mut Foo to &Foo" axiom to justify creating the shared reference... but that axiom is always executed in some thread! Const-eval doesn't run in a thread, or if it did then it'd have to ensure that the final value can only be used from that thread. Really we should have required that the value of a const is Send, justifying that the one value we compute can be "sent" to all threads.

Absent that, we need the concept of whether a value is valid in "no thread", i.e. the safety invariant is predicated not on a ThreadId but an Option<ThreadId> where None indicates the compile-time world where no threads exist yet. The "&mut Foo to &Foo" then also has to hold for the None thread, which fails. However, there is a special magic exception where if a type is !Freeze then the "&mut T to &T" axiom doesn't have to hold for the None thread, and that's how all the interior mutable types work.

Ugh, this is not very satisfying. :/

[LegionMammal978]

Oh you are right, somehow I thought the value of the field was relevant. But the field only exists to make this type non-zero-sized.

Ah, I thought you were referring to the rules for infallible promotion. If a type has public fields, then an external user can create a static-promoted instance of it. But if a type has private fields and can only be created with a pub const fn call, then an external user cannot create a static-promoted instance of it, and this bug does not apply.

Okay then, what happens when the &'static Foo is created? Const-eval creates a Foo somewhere and then needs to use the "&mut Foo to &Foo" axiom to justify creating the shared reference... but that axiom is always executed in some thread!

I don't see how &mut Foo → &Foo is relevant here? There's no &mut reference created in this example. Instead, this seems closer to &binding Foo → &Foo. That is, const-eval is translating const F: &'static Foo = &Foo(0); into the moral equivalent of:

const F: &'static Foo = {
    static FOO: Foo = Foo(0); // doesn't actually compile, since `Foo: !Sync`
    &FOO // also doesn't actually compile, since consts can't refer to statics
};

Most bindings (let bindings, argument bindings, pattern bindings, owned captures, etc.) are "owned" by a particular execution of a scope, which belongs to a particular thread. A &binding T can only be created inside this scope, so &binding T → &T is always safe, trading the scope-ownership for the thread-ownership. (Here, I'm considering borrowed closure/coroutine captures as just syntax sugar for references created when the closure/coroutine instance is created.)

However, static bindings are the exception to this rule, being accessible by &binding from any thread. Thus, since &binding T → &T is still a safe operation, but &binding T has no scope-ownership, &T cannot imply any kind of thread-ownership in general. This is why we require T: Sync to create a static binding. But with this bug, const-eval is allowed to create an internal &binding T safely accessible from any thread, breaking &T's thread-ownership that one would expect from T: !Sync.

[RalfJung]

Ah, I thought you were referring to the rules for infallible promotion. If a type has public fields, then an external user can create a static-promoted instance of it. But if a type has private fields and can only be created with a pub const fn call, then an external user cannot create a static-promoted instance of it, and this bug does not apply.

Sadly const fn calls do get promoted in const/static initializer bodies. (Cc #80619)

Otherwise, maybe there'd be some trick hiding here to rationalize the current behavior...

I don't see how &mut Foo → &Foo is relevant here?

It is relevant insofar as in my model (RustBelt), that is the only way to create a shared reference. It always starts with a mutable reference that is then used to initialize "sharing for a given lifetime". The usual problem when defining an invariant is to ensure that the initial state satisfies the invariant; in this case, that lemma represents the initial state.

So in my model, when you have let x = ...; &x, what logically happens is &(*&mut x). x never actually gets mutated of course, but given that &mut T → &T is possible, it is convenient to only have a single way of creating a shared reference, rather than two.

[LegionMammal978]

So in my model, when you have let x = ...; &x, what logically happens is &(*&mut x). x never actually gets mutated of course, but given that &mut T → &T is possible, it is convenient to only have a single way of creating a shared reference, rather than two.

Given that you can take multiple shared references to a binding at the same time, isn't that only a valid transformation given Tree Borrows–like mutable references, which aren't active until written to? And in that case, won't &mut T no longer imply exclusivity just by its existence?

[RalfJung]

The idea is that these multiple shared references all derive from a single root reference, even if that reference may not be visible in the source. The moment this transition happens is purely a "ghost step" in the proof; it doesn't have to coincide with retagging in Stacked/Tree borrows.