Should Rust assume that there are unknown threads of execution?

[gnzlbg]

@Amanieu provided the following example here, where the Channel should be placed in inter-process shared memory:

// Single-producer single-consumer channel with a capacity of 1
pub struct Channel<T: Copy> {
    control: AtomicBool,
    data: UnsafeCell<T>,
}

// I'm keeping the code simple here by having both read() and write()
// available on Channel. A real implementation would split the ends into
// a ReadChannel and WriteChannel to ensure only a single producer/consumer.
impl<T: Copy> Channel<T> {
    pub fn read(&self) -> T {
        // Wait for the channel to be full
        while !self.control.load(Ordering::Acquire) {}
        
        // Read the data
        let data = unsafe { *self.data.get() };
        
        // Mark the channel as empty
        self.control.store(false, Ordering::Release);
        data
    }

    pub fn write(&self, data: T) {
        // Wait for the channel to be empty
        while self.control.load(Ordering::Acquire) {}
        
        // Write the data
        unsafe {
            *self.data.get() = data;
        }
        
        // Mark the channel as full
        self.control.store(true, Ordering::Release);
    }
}

• If Rust proves that the Rust process is single-threaded, is it a sound optimization to replace the atomic loads/stores of the AtomicBool by non-atomic memory accesses ? If that optimization is sound, a different process attempting to access the bool introduces a data-race and the behavior is undefined.

• What assumptions does LLVM do?

---

Note: replacing the atomic loads and stores with volatile atomic loads and stores would ensure that the example above is correct independently of the answer to these questions.

[Amanieu]

The illusion that Rust has a global view of the system goes out of the window the moment it makes an FFI call. This happens long before main is even called, in the libstd initialization code. And even then, there is the possibility of injecting arbitrary code into a process through LD_PRELOAD.

Even without these, Rust cannot make any assumptions about what an FFI call which returns a shared memory region might do. For all Rust knows the other end of the shared memory region could be C code within the same process (add a #[repr(C)] to Channel if it makes you feel better).

[Diggsey]

On windows, there's also CreateRemoteThread which you can use to create a thread in another process.

[HadrienG2]

@Amanieu Rust already assumes that FFI calls cannot do certain things. For example, we assume that an FFI function won't randomly read and write our entire address space, as tolerating this behavior would make almost any optimization of Rust memory accesses externally observable, and therefore invalid under an as-if rule of optimization legality. This is in spite of the fact that a function implemented using, say, x86 assembly, could perfectly do such a thing.

I think that assuming a global view of concurrency in the application would be consistent with this prior decision of disallowing certain behavior from FFI entitites for the sake of enabling more optimizations on the Rust side.

Conversely, I think that not assuming such a global view of concurrency would greatly harm rustc's future ability to optimize concurrency primitives such as atomics, by effectively making atomic as pessimistic as volatile ("assume that all reads and writes are externally observable") as soon as there is any remote possibility of memory sharing with the outside world. Which happens as soon as a pointer to a memory region has ever been sent to opaque FFI for any purpose, even if that was just a printf call.

As an alternative, we could have both maximal optimization capabilities in Rust code and enable FFI concurrency / interprocess communication by having both non-volatile atomics (for intra-process / pure Rust communication) and volatile atomics (for FFI threads, MMIO and interprocess communication). This is the direction which I would personally advocate.

As an aside, there is prior art for differentiating intra-process and inter-process synchronization at the operating system level. For example, this is the main semantic difference between Windows's Mutex and CriticalSection APIs (which in turn allows CriticalSection to be much simpler and faster in the common case than Mutex).

[Amanieu]

Which happens as soon as a pointer to a memory region has ever been sent to opaque FFI for any purpose, even if that was just a printf call.

Note that LLVM has an attribute specifically for this, nocapture, which indicates that a pointer passed into the function is not used after the function has returned. There is also the noalias attribute which, when applied to the return value, indicates that the returned pointer is unique (i.e. like a pointer returned from malloc).

Also consider that thread creation itself is an FFI call, where the thread closure is passed in as an argument. For this FFI call, any memory referred to by the thread closure must clearly be externally observable, yet there is no way for rustc to know this just from the signature of the call.

My point is that, unless specifically marked with attributes, any memory whose address is passed to or from an FFI call should be assumed to be externally accessible. And indeed this is how LLVM currently works.

[gnzlbg]

@Amanieu

Sorry for not being more specific, your observations that unknown function calls can do many things that could prevent the compiler from applying any optimizations are correct. Trying to be more specific, another potential way of specifying a shared memory region would be to encode a pointer to it in a static variable:

#![no_core] #![no_std] #![no_main]

extern "C" {
    static FOO: Channel<T>;
}

#[no_mangle] fn main() { ... }

Do you think it is legal for a Rust compiler to optimize the atomic accesses of the channel to non-atomic ones if it can prove from just looking at the Rust program that it has not been possible for other threads of execution to be created ?

[Amanieu]

In your code example the channel is an extern "C". This means that it may be accessed from outside the current compilation unit, which in turn means that the compiler must conservatively assume that it could be accessed from anywhere, even another thread.

Do you think it is legal for a Rust compiler to optimize the atomic accesses of the channel to non-atomic ones if it can prove from just looking at the Rust program that it has not been possible for other threads of execution to be created ?

How can the compiler even prove that no threads are created? The only case where this optimization is valid is on platforms that support neither threading nor signals, e.g. emscripten.

[gnzlbg]

which in turn means that the compiler must conservatively assume that it could be accessed from anywhere, even another thread.

If such other threads exist. If they don't, then that does not hold.

How can the compiler even prove that no threads are created?

You mention that creating a thread requires an unknown function call. If the program contains no unknown function calls, then no threads are created by that program.

[bjorn3]

If the program contains no unknown function calls, then no threads are created by that program.

All programs without unknown function calls always either exit without doing anything but consuming CPU, or they crash. Either way they are not very useful. Even something as simple as printing something to stdout requires an unknown function call to libc. Even if libc is visible to LTO, it still requires inline asm.

[gnzlbg]

All programs without unknown function calls always either exit without doing anything but consuming CPU, or they crash.

#![no_core] #![no_std] #![no_main] #![no_entry] ...

extern "C" {
    static FOO: Channel<i32>;
}

#[no_mangle] 
fn main() {
    FOO.write(0);
    loop {
        if FOO.read() == 42 { 
             println!("Hello world");
        }
    }
 }

That program calls unknown functions, but it doesn't do so before interfacing with shared memory, so it could not have spawned a second thread that modifies FOO to set it to 42.

Can the compiler optimize that program to: fn main() { loop {} } ?

[Amanieu]

No because external C code may run before main (via static constructors, LD_PRELOAD, etc), and this code may modified the publicly visible Channel.

[gnzlbg]

No because external C code may run before main (via static constructors, LD_PRELOAD, etc), and this code may modified the publicly visible Channel.

So you are saying that this code can spawn threads that remain active after main starts, and such code can modify Channel after main initializes it ?

How is this code represented in the abstract machine ? (e.g. how should miri implement what this code does?)

[Lokathor]

It seems natural to assume that any unknown code that runs before the rust main (via any mechanism) can do anything at all that code can do, including spawn threads.

[HadrienG2]

Compiler abstract machines have somewhat supernatural characteristics though, as that is needed to permit code optimization.

[bjorn3]

So you are saying that this code can spawn threads that remain active after main starts, and such code can modify Channel after main initializes it ?

In this case an unknown function did get called before calling main. The function _start from libc is an unknown function which is the actual caller of main.