Rust and UB [LWN.net]

Rust and UB

Posted Aug 14, 2024 22:34 UTC (Wed) by pbonzini (subscriber, #60935)
In reply to: Rust and UB by josh
Parent article: Standards for use of unsafe Rust in the kernel

I think there is one exception to this, which is synchronization code where you only control one side.

Consider any kind of synchronization primitive (such as futexes, or a ring buffer) that span kernel and userspace, you cannot for example ensure that the other side accesses data with something that resembles an atomic read/write. In theory that would be a data race and undefined behavior in the Rust code. In practice you make some, more or less reasonable, assumptions on what the compiler and processor do, and assume that this bounds the kind of cross-process-induced undefined behavior that can actually happen.

For example, you may assume that the compiler won't perform optimizations that assume that it can see all possible accesses to AtomicXYZ (it clearly does not, since some accesses happen outside Linux). So if you write code that validates indices read from atomic references, the compiler won't try to infer that these bounds checks are dead.

You may also have to assume that in the case of data races involving integer atomics (as opposed to pointers), the undefined behavior is limited to seeing data that neither side has ever written, for example leaving a mix of the old and the new value in memory. This is beyond what Rust guarantees, but you can make more or less handwavy arguments that this is the same as if a malicious userspace wrote random data without causing data races. The latter case is not UB and constrains the kind of optimization that the compiler can perform, so that in the end input validation (see previous point) will catch the invalid data before reaching the unsafe-safe boundary.

You may also have to make assumptions on what volatile reads and writes really are (possibly including reads and writes from asm! blocks), and the behavior you get when you access volatile memory in ways that would technically be data races according to the Rust memory model.

The above is true of two processes, or of a VMM and a virtual machine guest, or of a device on the same memory bus as Linux. But it's even true of Rust and C code within Linux, because the C code isn't using atomic load and store primitives, and therefore you cannot really escape thinking through this. (In practice it's not going to be a problem, but it shows that the "clean slate" approach doesn't work 100%).

But at least, this kind of reasoning only needs to be applied to unsafe code that uses *mut pointers or UnsafeCell.

Rust and UB

Posted Aug 15, 2024 6:33 UTC (Thu) by ralfj (subscriber, #172874) [Link] (9 responses)

Cross-process (or "cross-privilege-boundary") atomics are a nasty case, but roughly speaking the way they can be implemented without having UB (even in theory) is to ensure that "your side" always uses atomic accesses. If the other process uses non-atomics to access the same memory, then there is UB, but the UB is limited to the other process. When this occurs between kernel and userspace, process isolation ensures that UB in userspace cannot "taint" the kernel, so it's fine.

But this is not an example of "causing UB and getting away with it".

(For Linux specifically, things are more complicated because Rust uses the C++ memory model but Linux implements its own concurrency model, the LKMM. That one *is* technically UB in Rust, just like it is technically UB in C. But this has nothing to do with having synchronization span kernel and userspace.)

Rust and UB

Posted Aug 15, 2024 10:57 UTC (Thu) by pbonzini (subscriber, #60935) [Link] (8 responses)

Hi Ralf! Yes, I agree that this is an edge case and in general in Rust you shouldn't even *think* of "getting away with it". However:

> roughly speaking the way they can be implemented without having UB (even in theory) is to ensure that "your side" always uses atomic accesses.

I disagree that this is true, neither in practice nor in theory. Within a single process it is UB on the read side if the other side does a non-atomic write, and that's for good reasons, because for example the write could be torn. Torn writes of a pointer for example can lead to invalid memory accesses, which is quite clearly UB(*), and I don't see why it would be different across processes.

What you can expect in practice, is that the behavior will not be worse than dealing with garbage that was stored with atomic writes; if you validate your inputs you'll be fine. But I'm not sure that's true in theory, at least as things stand now.

(*) converting the AtomicUsize to a reference is unsafe, so Rust does maintain the promise that all UB can only happen within unsafe regions.

> (For Linux specifically, things are more complicated because Rust uses the C++ memory model but Linux implements its own concurrency model, the LKMM. That one *is* technically UB in Rust, just like it is technically UB in C. But this has nothing to do with having synchronization span kernel and userspace.)

In QEMU (written in C though Rust is coming), we use Linux-like wrappers for the C memory model. It turns out to be usable and just as optimized as the Linux primitives. So it would be possible to write Rust code using the Rust memory model, and to make the Rust memory model friendly enough to Linux kernel programmers.

However, we do have a couple tricks under our sleeve, where we "know" that some reorderings cannot happen at the processor level, and therefore use compiler fences instead of thread fences. For example instead, of the ill-fated Consume load, we use a Relaxed load followed by an Acquire compiler barrier. And before/after any RMW atomic, on x86 we use SeqCst compiler fences instead of a thread fence, not unlike smp_mb__before_atomic() in Linux. Those probably would *also* be technically UB...

I have long planned to write an article on the C/C++/Rust memory model for Linux kernel programmers, but never made the plan concrete. :(

Rust and UB

Posted Aug 15, 2024 15:53 UTC (Thu) by pbonzini (subscriber, #60935) [Link]

> Those probably would *also* be technically UB...

Mulling more about it—definitely not UB, and I think the synchronizes-with edges are also in place so it may be safe both in theory and in practice.

Rust and UB

Posted Aug 15, 2024 23:50 UTC (Thu) by tialaramex (subscriber, #21167) [Link] (1 responses)

In practice the LInux kernel cannot assume whatever nonsense it got from userspace is really a pointer.

At best it's an address, a large integer. So, we've got an address. We check this address meets all our rules (it's in the right part of the memory etc.) and then I think Aria's ptr::with_addr lets us turn a (copy of a) pointer we kept for this purpose (e.g. pointing into the userspace memory of the process that called us) into a pointer to the specific address requested. If so that's not Undefined Behaviour.

Rust and UB

Posted Aug 16, 2024 0:25 UTC (Fri) by quotemstr (subscriber, #45331) [Link]

And if kernel pointers were given to userspace, it'd be an KASLR break anyway.

Rust and UB

Posted Aug 16, 2024 8:27 UTC (Fri) by ralfj (subscriber, #172874) [Link] (4 responses)

Hi. :)

> Within a single process it is UB on the read side if the other side does a non-atomic write,

Yes, I am well aware. I was talking about the multi-process situation.

I don't think we have a formal (in the mathematical sense) model that accurately captures the multi-process situation. For the specific case of read-write races, we do have memory models that make read-write races return "poison"/"undef" on the reader side, without causing full UB (https://dl.acm.org/doi/10.1145/3591297), so if the kernel side uses atomics and also "freezes" all its reads (as in https://github.com/rust-lang/rfcs/pull/3605 -- so unfortunately not yet available in Rust), it would be protected against UB even in a theoretical sense. In practice, even without "freeze" it seems hard to imagine how an atomic read racing with a non-atomic write returns anything worse than a strange bit pattern. Obviously if the relevant data is a pointer you blindly trust, things go wrong, but in the situation we were talking about where there's privilege separation between the two parties, there cannot be any pointers that the privileged side blindly trusts, so I was implicitly excluding that case.

If this is a write-write race, then we don't have any theoretical model I am aware of that would help us. But in practice, if you are the side doing the atomic write, I don't see how you could possibly suffer from UB if there is a racing non-atomic write, provided that you never trust the data you read from this memory (which indeed the kernel cannot trust anyway).

> In QEMU (written in C though Rust is coming), we use Linux-like wrappers for the C memory model. It turns out to be usable and just as optimized as the Linux primitives.

Oh, interesting. I was not aware the C memory model is already used in the Linux kernel. So to make sure we are talking about the same thing, you are using the operations from the C "atomics" library (https://en.cppreference.com/w/c/atomic), and no volatile accesses or inline assembly?

Are you following some sort of discipline where every location in memory can be used either with the LKMM or the C model, or are you mixing both of them on the same location? Mixing both on the same location seems extremely risky to me. Even if memory is "partitioned" into regions governed by the C memory model and regions governed by the LKMM, there are some very non-trivial interactions going on -- the happens-before relationships of the two models must be sufficiently compatible with each other. Theoretically speaking, this is a really hard problem. In practice, it probably works because there are not so many different lowering schemes one can use for the basic atomic operations.

> However, we do have a couple tricks under our sleeve, where we "know" that some reorderings cannot happen at the processor level, and therefore use compiler fences instead of thread fences. For example instead, of the ill-fated Consume load, we use a Relaxed load followed by an Acquire compiler barrier. And before/after any RMW atomic, on x86 we use SeqCst compiler fences instead of a thread fence, not unlike smp_mb__before_atomic() in Linux. Those probably would *also* be technically UB...

Yeah okay that's not the C memory model. ;) Even if the processor can't do such reorderings, the compiler can. So I see no way to ever justify using compiler fences instead of thread fences in a principled way. I would expect that on strongly ordered hardware like x86, most thread fences anyway compile to NOPs?

Rust and UB

Posted Aug 16, 2024 11:16 UTC (Fri) by pbonzini (subscriber, #60935) [Link] (3 responses)

> it seems hard to imagine how an atomic read racing with a non-atomic write returns anything worse than a strange bit pattern

Agreed. It would be nice to have a formal promise for that, as it's UB with the current models. But if not I think it's possible for Linux to live with *this* specific UB.

> to make sure we are talking about the same thing, you are using the operations from the C "atomics" library (https://en.cppreference.com/w/c/atomic), and no volatile accesses or inline assembly?

Yes—but not in Linux, only in QEMU. QEMU is in user space and uses the C memory model, but historically most people involved were more familiar with Linux atomics. We limit ourselves to a restricted API (consisting of relaxed load, relaxed store, acquire load, release store, SeqCst read-modify-write operations, and acquire/release/full fences) that mostly resembles the Linux API but is implemented on top of C atomics. Maybe something like that could be used as a starting point to bridge LKMM and Rust memory models. As you say there would be some handwaving on how compatible the happens-before relationships are; assuming that the Rust and C worlds are separate enough, maybe you can treat them similar to kernel–userspace or inter-process cases.

> Even if the processor can't do such reorderings, the compiler can. So I see no way to ever justify using compiler fences instead of thread fences in a principled way.

My understanding is that compiler fences can be used instead of thread fences if you know that two threads only ever run on the same physical CPUs. So, as far as the compiler is concerned, they should block the same optimizations as thread fences, generating the same code apart from the fence instructions themselves. The assumptions that are made on generated instructions might be dubious in terms of portability, but they're fine with respect to data races and hence UB.

> I would expect that on strongly ordered hardware like x86, most thread fences anyway compile to NOPs?

The main exception is SeqCst fences after SeqCst RMW operation. Those are unnecessary and pretty expensive (a few tens of cycles) even on x86, and we have a couple in really hot places. I think only Arm needs a processor fence instead, for some unobvious reason related to the semantics of LDAR instructions (which are stronger than just acquire) and to the code that's generated for SeqCst RMW operations.

Rust and UB

Posted Aug 17, 2024 10:14 UTC (Sat) by ralfj (subscriber, #172874) [Link] (2 responses)

> Yes—but not in Linux, only in QEMU. QEMU is in user space and uses the C memory model, but historically most people involved were more familiar with Linux atomics.

Thanks for clarifying!

> My understanding is that compiler fences can be used instead of thread fences if you know that two threads only ever run on the same physical CPUs. So, as far as the compiler is concerned, they should block the same optimizations as thread fences, generating the same code apart from the fence instructions themselves. The assumptions that are made on generated instructions might be dubious in terms of portability, but they're fine with respect to data races and hence UB.

Interesting. According to the standard, the only thing compiler fences do is perform synchronization with signal handlers running in the current thread. (Signal handlers are "almost" separate threads in the C++ memory model, except that compiler fences suffices to synchronize with them.)

I'm not enough of an expert in this to say whether that model can be extended to "other threads running on the same physical CPU core" without causing problems.

> The main exception is SeqCst fences after SeqCst RMW operation. Those are unnecessary and pretty expensive (a few tens of cycles) even on x86, and we have a couple in really hot places. I think only Arm needs a processor fence instead, for some unobvious reason related to the semantics of LDAR instructions (which are stronger than just acquire) and to the code that's generated for SeqCst RMW operations.

If those fences can always be compiled to NOPs (presumably with some restriction on what happens between the RMW and the fence), that *sounds* like something that the codegen backend of a compiler should take care of. Backends can do optimizations that programmers cannot do if those optimizations are done sufficiently late during compilation that the program can already be considered to run with a lower-level memory model.

Rust and UB

Posted Aug 17, 2024 17:32 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (1 responses)

> that *sounds* like something that the codegen backend of a compiler should take care of

Indeed, but neither GCC nor LLVM even try, as far as I am aware of.

I will check my sources more on the compiler fence vs thread fence issue.

Rust and UB

Posted Aug 20, 2024 6:35 UTC (Tue) by ralfj (subscriber, #172874) [Link]

Then I hope someone will invest in improving the compilers here. :) I'm not enough of an expert for these low-level parts to judge how much performance they are leaving on the table. But this is simply not something that can be reliably fixed at higher levels of abstraction.

Do you know if there's a bug report against GCC and LLVM discussing the correctness and feasibility of such optimizations?