RCU mistakes

By Jonathan Corbet
December 15, 2009

Thomas Gleixner has set himself the task of getting rid of the messy rwlock called tasklist_lock; in many cases, the solution is to use read-copy-update (RCU) instead. In the process, he found some problems with how some code uses RCU. They merit a quick look, since these problems may occur elsewhere, and may reflect an outdated understanding of how RCU works.

The core idea behind RCU is to delay the freeing of obsoleted, globally-visible data until it is known that no users of that data exist. Traditionally, this has been accomplished by (1) requiring that all uses of RCU-protected data be in atomic code, and (2) not freeing any old data until every CPU in the system has scheduled at least once after that data was replaced by an updated copy. Since atomic code cannot schedule, this set of rules is sufficient to know that no references to the old data exist.

Needless to say, code working with RCU-protected data must have preemption disabled - otherwise the processor could schedule while a reference to that data still exists. So the rcu_read_lock() primitive has traditionally disabled preemption. Based on the code Thomas found, that seems to have led to the conclusion that disabling preemption is sufficient for code using RCU.

The problem is that newer forms of RCU use a more sophisticated batching mechanism to track references to RCU-protected data. This change was necessary to make RCU scale better, especially in situations (realtime, for example) where disabling preemption is undesirable. When using hierarchical (or "tree") RCU, code which simply disables preemption before accessing RCU-protected data will have ugly race conditions. So it's important to always use rcu_read_lock() when working with such data. Unfortunately, this is a hard rule to enforce in an automated way, so programmers will simply have to remember it.

Index entries for this article
Kernel	Read-copy-update

RCU mistakes

Posted Dec 17, 2009 7:05 UTC (Thu) by alonz (subscriber, #815) [Link]

I wonder—would it be a good idea to annotate RCU-protected data structures, so that (e.g.) sparse would be able to verify their correct usage?

Alternatively, are frameworks like Coccinelle powerful enough to detect such mismatches?

RCU mistakes, four years on

Posted Dec 17, 2009 18:03 UTC (Thu) by PaulMcKenney (✭ supporter ✭, #9624) [Link]

First, thank you for calling attention to this! The idea that disabling of preemption could stand in for rcu_read_lock() is disturbingly widespread.

Disabling preemption was indeed a legal substitute for rcu_read_lock() — in 2.6.11 and earlier. This ended back in 2005 (2.6.12-rc4) with the deprecation of synchronize_kernel() in favor of synchronize_sched() and synchronize_rcu(). As you say, this change was motivated by real-time-response considerations.

However, it was not until 2007, with the appearance of preemptible RCU in 2.6.25, that failure would appear in mainline due to (incorrectly) substituting preempt_disable() for rcu_read_lock(). The theory was that these were found and fixed by the -rt effort, but clearly we did miss some.

I have therefore started working on lockdep extensions to allow automatic detection of this sort of RCU abuse, inspired by earlier patches from Peter Zijlstra and Thomas Gleixner. This patchset contains a crude (and buggy) first step in this direction.

A list of what RCU read-side primitives go with which RCU update primitives may be found in Documentation/RCU/whatisRCU.txt, search for “FULL LIST OF RCU APIs” and scroll down a bit.