Paul E. McKenney's Journal - LiveJournal.com
First, let me paraphrase something from my LiveJournal profile: These posts are my own, and in particular do not necessarily reflect my employer's positions, strategies, or opinions. With that said, some say that the current geopolitical outlook is grim. And far be it from me to minimize the present-day geopolitical problems, nor am I at all interested in comparing them to their counterparts in…
In order to save mass-storage space and to reduce boot times, rcutorture runs out of a tiny initrd filesystem that consists only of a root directory and a statically linked init program based on nolibc . This init program binds itself to a randomly chosen CPU, spins for a short time, sleeps for a short time, and repeats, the point being to inject at least a little userspace execution for the…
The v2023.06.11a release of Is Parallel Programming Hard, And, If So, What Can You Do About It? is now available! The double-column version is also available from arXiv.org . This release contains a new section on thermal throttling (along with a new cartoon), improvements to the memory-ordering chapter (including intuitive subsets of the Linux-kernel memory model), fixes to the…
Under Construction A correspondent closed out 2022 by sending me an off-list email asking whether or not a pair of Rust crates ( rcu_clean and left_right ) were really implementations of read-copy update ( RCU ), with an LWN commenter throwing in crossbeam 's epoch crate for good measure. At first glance, this is a pair of simple yes/no questions that one should be able to answer off the cuff.…
A previous post in this series showed how you can use the --bootargs parameter and .boot files to supply kernel boot parameters to the kernels under test. This works, but it turns out that there is another way, which is often the case with the Linux kernel. This other way is Masami Hiramatsu's bootconfig facility, which is nicely documented in detail here . This blog post is a how-to guide on…
A few years ago, I posted on the challenges of maintaining low weight as one ages. I have managed to stay near my target weight, with the occasional excursion in either direction, though admittedly more often up than down. My suspicion that maintaining weight would prove 90% as difficult as losing it has proven to be all too well founded. As has the observation that exercise is inherently damaging…
I had the privilege of presenting Unraveling Fence & RCU Mysteries (C++ Concurrency Fundamentals) to the CPP Summit . As the title suggests, this covered RCU from a C++ viewpoint. At the end, there were several excellent questions: How does the rcu_synchronize() wait-for-readers operation work? But the rcu_domain class contains lock() and unlock() member functions!!! Lockless things make me…
The v2022.09.25a release of Is Parallel Programming Hard, And, If So, What Can You Do About It? is now available! The double-column version is also available from arXiv.org . This version boasts an expanded index and API index, and also adds a number of improvements, perhaps most notably boldface for the most pertinent pages for a given index entry, courtesy of Akira Yokosawa. Akira also further…
I had the honor of attending this workshop , however, this is not a full report. Instead, I am reporting on what I learned and how it relates to my So You Want to Rust the Linux Kernel? blog series that I started in 2021, and of which this post is a member. I will leave more complete coverage of a great many interesting sessions to others (for example, here , here , and here ), who are probably…
The September 2022 issue of the Communications of the ACM features an entertaining pair of point/counterpoint articles, with William Dally advocating for concurrent computational models that more accurately model both energy costs and latency here and Uzi Vishkin advocating for incremental modifications to the existing Parallel Random Access Machine (PRAM) model here . Some cynics might summarize…
Daniel Vetter put together a pair of intriguing blog posts entitled Locking Engineering Principles and Locking Engineering Hierarchy . These appear to be an attempt to establish a set of GPU-wide or perhaps even driver-tree-wide concurrency coding conventions. Which would normally be none of my business. After all, to establish such conventions, Daniel needs to negotiate with the driver…
RCU is a specialized synchronization mechanism, and is typically used where there are far more readers ( rcu_read_lock() , rcu_read_unlock() , rcu_dereference() , and so on) than there are updaters ( synchronize_rcu() , call_rcu() , rcu_assign_pointer() , and so on). But does the Linux kernel really make heavier use of RCU's read-side primitives than of its update-side primitives? One way to…
It is just as easy to ask why RCU wouldn't be watching all the time. After all, you never know when you might need to synchronize! Unfortunately, an eternally watchful RCU is impractical in the Linux kernel due to energy-efficiency considerations. The problem is that if RCU watches an idle CPU, RCU needs that CPU to execute instructions. And making an idle CPU unnecessarily execute instructions…
It is past time for another release of Is Parallel Programming Hard, And, If So, What Can You Do About It? . But first, what is the difference between an edition and a release? The main difference is the level of validation. For example, during the several months leading up to the second edition, I read the entire book, fixing issues as I found them. So where an edition is a completed work, a…
The CONFIG_RCU_FAST_NO_HZ Kconfig option was added many years ago to improve energy efficiency for systems having significant numbers of short bursts of idle time. Prior to the addition of CONFIG_RCU_FAST_NO_HZ , RCU would insist on keeping a given idle CPU's scheduling-clock tick enabled until all of that CPU's RCU callbacks had been invoked. On certain types of battery-powered embedded systems,…
Several people have expressed interest in how I go about creating the topic branches in the -rcu tree. So when I created branches earlier this week, I actually kept track. But why bother with topic branches? In my case, reason is to allow anyone reviewing RCU patches to focus on a particular topic and to be able to keep that topic “in cache” while reviewing all of that topic's patches.…
This blog post discusses a few alternative Rust-language memory models. I hope that this discussion is of value to the Rust community, but in the end, it is their language, so it is also their choice of memory model. This discussion takes the Rust fearless-concurrency viewpoint, tempered by discussions I have observed and participated in while creating this blog series . Different members of that…
Suppose that you had a state machine implemented by NMI handlers, and that some of the transitions in this state machine need to wait for an RCU grace period to elapse. How could these state transitions be implemented? Before we start, let's dispense with a couple of silly options. First, we clearly are not going to invoke synchronize_rcu() from within an NMI handler. This function can sleep, and…
You would like to do some formal verification of C code? Or you would like a challenge for your formal-verification tool? Either way, here you go! Stupid RCU Tricks: rcutorture Catches an RCU Bug , also known as Verification Challenge 1. Verification Challenge 2: RCU NO_HZ_FULL_SYSIDLE . Verification Challenge 3: cbmc . Verification Challenge 4: Tiny RCU . Verification Challenge 5: Uses of RCU .…
These recommendations assume that the initial Linux-kernel targets for Rust developers are device drivers that do not have unusual performance and scalability requirements, meaning that wrappering of small C-language functions is tolerable. (Please note that most device drivers fit into this category.) It also assumes that the main goal is to reduce memory-safety bugs, although other bugs might be…
We have taken a quick trip through history, through a number of the differences between the Linux kernel and the C/C++ memory models, sequence locks, RCU, ownership, zombie pointers, and KCSAN. I give a big "thank you" to everyone who has contributed to this discussion, both publicly and privately. It has been an excellent learning experience for me, and I hope that it has also been helpful to all…
Given the data-race-freedom guarantees of Rust's non- unsafe code, one might reasonably argue that there is no point in the Kernel Concurrency Sanitizer (KCSAN) analyzing such code. However, the Linux kernel is going to need unsafe Rust code, and although there has been significant progress in formal verification of such code, one of the leading researchers in this area says “ we hope to…
Some of the previous posts in this series have been said to be quite difficult, so I figured I owed you all an easy one. And the zombie-pointer problem really does have a trivial solution, at least in the context of the Linux kernel. In other environments, all bets are off. But first, what on earth is a zombie pointer? To answer that question, let's start with a last-in-first-out (LIFO) stack. We…
Rust concurrency makes heavy use of ownership and borrowing. The purpose of this post is not to give an exposition of Rust's capabilities and limitations in this area, but rather to give a series of examples of ownership in the Linux kernel. The first example involves Linux-kernel per-CPU variables. In some cases, such variables are protected by per-CPU locks, for example, a number of fields in…
Read-copy update (RCU) vaguely resembles a reader-writer lock [1], but one in which readers do not exclude writers. This change in semantic permits RCU readers to be exceedingly fast and scalable. In fact, in the most aggressive case, rcu_read_lock() and rcu_read_unlock() generate no code, and rcu_dereference() emits but a single load instruction. This most aggressive case is achieved in…