Rust and UB [LWN.net]

Rust and UB

Posted Aug 15, 2024 10:57 UTC (Thu) by pbonzini (subscriber, #60935)
In reply to: Rust and UB by ralfj
Parent article: Standards for use of unsafe Rust in the kernel

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 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?