- P0124R7: Linux-Kernel Memory Model: A C++ standards-committee working paper comparing the C/C++ memory model to LKMM.
- Linux Weekly News series on LKMM (Part 1 and Part 2).
- The infamous ASPLOS'18 paper entitled Frightening Small Children and Disconcerting Grown-ups: Concurrency in the Linux Kernel (non-paywalled), with a title-based tip of the hat to the irrepressible Mel Gorman.
- Chapter 15 of perfbook ("Advanced Synchronization: Memory Ordering").
- The Linux kernel's tools/memory-model directory, featuring an executable version of LKMM.
For all of these references, I give a big "Thank You!!!" to my co-authors.
LKMM is not the most complex memory model out there, but neither is it the simplest. In addition, it is in some ways more strict than the C/C++ memory models, which means that strict adherence to coding guidelines is required in order to prevent compiler optimizations from breaking Linux-kernel code. Many of these optimizations are not localized, but are instead scattered hither and yon throughout the compilers, including throughout the compiler backends. The optimizations in the backends are a special challenge to Rust, which seems to take the approach of layering safety on top of (or perhaps within) the compiler frontend. Later posts in this series will look at several pragmatic options available to Rust Linux-kernel code.
There is one piece of good news: Compilers are forbidden from introducing data races into code, at least not into code that is free of undefined behavior.
With all of that out of the way, let's look at Rust's options for dealing with Linux-kernel atomics and barriers and locks.
The first approach is to carefully read the P0124R7: Linux-Kernel Memory Model working paper and even more carefully follow its advice in selecting C/C++ primitives that best match Linux-kernel atomics, barriers, and locks. This approach works well for data whose definition and use is confined to Rust code, and with sufficient care and ongoing attention can also work for atomic operations and memory barriers involving data shared with C code. However, expecting Rust locking primitives to interoperate with Linux-kernel locking primitives might not be a strategy to win. It seems wise to make direct use of the existing Linux-kernel locking primitives, keeping in mind that this means properly wrappering them in order to make Rust ownership work properly. Those who doubt the wisdom of wrappering the C-language Linux-kernel locking primitives should consider the following:
- Linux-kernel locks are complex and highly optimized. Keeping two implementations is an excellent way to inject profound bugs into the Linux kernel.
- Linux-kernel locks are deeply entwined with the lockdep lock dependency checker. The data structures implementing each lock class would need to be shared between C and Rust code, which is another excellent way to inject bugs.
- On some architectures, Linux-kernel locks must interact with memory-mapped I/O (MMIO) accesses. Any Rust-language implementation of Linux-kernel locks must therefore be architecture-dependent and must know quite a bit about Linux-kernel MMIO.
As described in later sections, it might be useful to promote READ_ONCE() to smp_load_acquire() instead of implementing it as a volatile load. It might also be useful to promote WRITE_ONCE() to smp_store_release() instead of implementing it as a volatile store, depending on what sort of data-race analysis Rust provides for unsafe code. There is some C/C++ work in flight towards providing better definitions for volatile operations, but it is still early days for this work.
If READ_ONCE() and WRITE_ONCE() are instead to be implemented as volatile operations in Rust, please take care to check the individual architectures that are affected. DEC Alpha requires a full memory-barrier instruction at the end of READ_ONCE(), Itanium requires promotion of volatile loads to acquire loads (but this is carried out by the compiler), and ARMv8 requires READ_ONCE() to be promoted to acquire (but only in CONFIG_LTO=y builds).
Device drivers make heavy use of volatile accesses and memory barriers for MMIO accesses, and Linux-kernel device drivers are no exception. As noted earlier, some architectures require that these accesses interact with locking primitives. Furthermore, there are many device-specific special cases surrounding device control in general and MMIO in particular. Therefore, Rust-language device drivers should access the existing Linux-kernel C-language primitives rather than creating their own, especially to start with. There might well be exceptions to this rule, for example, Rust might be applied to a device driver that is only used by architectures that do not require interaction with locking primitives. But if you write driver containing Rust-language MMIO primitives, please carefully and prominently document the resulting architecture restrictions.
This suggests another approach, namely not bothering implementing any of these primitives in Rust, but rather to make direct use of the Linux-kernel implementations, as suggested earlier for locking and MMIO primitives. And again, this requires wrappering them for use by Rust code. However, such wrappering introduces another level of function call, potentially for tiny functions. Although it is expected that LTO will successfully inline tiny functions, not all of the world is yet ready for LTO. In the meantime, where feasible, developers should avoid invoking tiny C functions from Rust-language fastpaths.
This being the real world, we should expect that the Rust/C determination will need to be made on a case-by-case basis, with many devils in the details.
October 13, 2021: Add explicit justification for wrappering the Linux kernel's C-language locks and add a few observations about MMIO accesses