• OPWIntro-RCU

There are a number of possible projects surrounding RCU, with varying levels and types of challenges. Here they are!

But first, what is RCU? Here are a few references that can help you get started quickly:

1. Structured Deferral: Synchronization via Procrastination (Conceptual overview.)

2. What Is RCU? (Another conceptual overview, but in slide form.)

3. The RCU API, 2010 Edition (API overview.)

4. Nascent RCU design documentation, tarball of HTML

5. Lots more information on RCU

6. And last but not least, the location of the -rcu tree: git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git. The commits intended for the next merge window are at rcu/next, and the latest development is at rcu/dev.

Automatically Locate RCU Abuses

Create Coccinelle scripts or use other tools to automatically detect abuses of RCU, and provide fixes for any bugs found. Candidate bugs include:

1. Mismatch between read-side protection and grace period. For example, using rcu_read_lock() to protect readers but synchronize_rcu_sched() to defer freeing removed data.
2. Making use of an RCU-protected pointer after passing it to call_rcu() or similar function. This is a form of use-after-free bug.
3. Uses of rcu_dereference() (and friends) whose return value is never dereferenced should be converted to rcu_access_pointer(). For example, "if (rcu_dereference(p) == NULL)" should be converted to "if (rcu_access_pointer(p) == NULL)". Perhaps better, as Josh Triplett suggests, would be to create something like rcu_pointer_eq() to compare an RCU-protected pointer to some other pointer, including of course a NULL pointer. The friends of rcu_dereference() include rcu_dereference_check(), rcu_dereference_bh(), rcu_dereference_bh_check(), rcu_dereference_raw(), rcu_dereference_sched(), rcu_dereference_sched_check(), srcu_dereference(), and srcu_dereference_check(). Note that comparison to non-NULL pointers are subject to a more complex set of rules, so it is best to start with comparisons to NULL pointers.
4. Dereferencing an RCU-protected pointer outside of the RCU read-side critical section that it was obtained in, unless it was protected by a reference count, lock, or some such before exiting the RCU read-side critical section.
5. Uses of rcu_assign_pointer(whatever, NULL) should change to RCU_INIT_POINTER(whatever, NULL).
6. Other types of bugs gleaned from bugzilla, from bug-fix commits, or from finding bugs in code.

Inline __rcu_read_lock()

The "_ _rcu_read_lock()" function is currently located in kernel/rcu/update.c is an ideal candidate for inlining. Except for one thing, namely that exporting include/linux/sched.h's task_struct to every file that needs "_ _rcu_read_lock()" results in very ugly circular include-file dependencies. The goal is therefore to get rid of these circular dependencies. There are two known approaches:

1. Replace a few key inline functions with C-preprocessor macros. These functions are identified by doing randconfig builds of the kernel and fixing issues as they arise.
2. Split the data structure definitions out into a parallel set of include files. This approach is in some sense cleaner than replacing inline functions with C-preprocessor macros, but requires careful handling of conflicting patches that are affected by the wholesale changes.

The maintainer of include/linux/sched.h has indicated a clear preference for the first approach, so the second approach is included only for completeness.

Add kmem_cache_free_rcu() [DONE]

Add a kmem_cache_free_rcu() function that invokes kmem_cache_free() on the referenced structure after an RCU grace period elapses. Use kmem_cache_free_rcu() to remove the various mini-functions that look like the following:

• static void epi_rcu_free(struct rcu_head *head) {
  • struct epitem *epi = container_of(head, struct epitem, rcu); kmem_cache_free(epi_cache, epi);
  }

Then code of the form:

• call_rcu(&epi->rcu, epi_rcu_free);

Would change to something like:

• kmem_cache_free_rcu(&epi->rcu, epi_cache);

There are some strict constraints. First, this change is not permitted to change the size of the rcu_head structure. One way to avoid such a size change is to create an RCU-protected hash table that contains entries for slabs that have ever been passed to kmem_cache_free_rcu(). Each entry in this hash table would need to contain the offset of the rcu_head structure within the enclosing structure.

Note that a given structure could in theory have multiple rcu_head structures, but this is rare in practice. One acceptable option is to complain and leak callbacks in this case. Another acceptable option is to correctly handle this case. Approaches that result in inexplicable crashes need not apply.

This task has the unusual property that it is a substantive change that requires relatively little knowledge of RCU, but that also has the potential for a reasonable number of other patches.

Validate RCU Algorithms

Use tools such as Promela/spin or goto-cc/goto-instrument/satabs to validate (or invalidate, as the case may be) some of RCU's more involved algorithms. In the case of invalidation, fixes would of course be quite welcome.

Automate Testing of RCU CPU Stall Warnings

One of rcutorture's many shortcomings is that it does not do much to automatically test RCU CPU stall warnings, which are described in Documentation/RCU/stallwarn.txt. Add automated testing to either kernel/rcu/torture.c or make some other tool that creates CPU stalls and verifies that RCU complains appropriately.

Port RCU's KVM Scripts

There is a set of scripts in tools/testing/selftests/rcutorture that automatically build, boot, and test kernels for a number of RCU configurations. An initial version of these is in mainline, but the current version may be found at git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git on branch rcu/dev.

These scripts currently run on x86, x86_64, and powerpc (the latter less well than the former two). Port these scripts to some other architecture, for example, ARM.

Miscellaneous Fixes to RCU

1. Remove "extern" from function declarations in include/linux/*rcu*.h and kernel/rcu/*.h files. [DONE]

2. Protect uses of ->jiffies_stall with ACCESS_ONCE(). [DONE]

3. Review torture_shuffle_tasks() in kernel/torture.c. If it turns out to be able to pass all-zero cpumasks to set_cpus_allowed_ptr(), fix this bug. [DONE]

4. Check to see whether the rcu_data structure's ->preemptible field is unused. If so, remove it. [DONE]

5. Exercise RCU's debugfs tracing, and fix any bugs in either the implementation or the documentation. The debugfs tracing is normally located in /sys/kernel/debug/rcu, and the documentation is in Documentation/RCU/trace.txt.
6. Add event tracing to dyntick_save_progress_counter() in the case where it returns 1. See calls to trace_rcu_fqs() in rcu_implicit_dynticks_qs() for a template. [DONE]
7. Look for and fix any kernel/rcu/rcutorture.c printing that is subject to buffer overflow (but note that Gang Chen already fixed the SRCU printing).
8. Compare the dmesg output of rcutorture runs to Documentation/RCU/torture.txt and fix any mismatches.
9. There is a variable named rcu_state and a structure named rcu_state. This confuses the sparse static-analysis tool. Change the two occurrences of "static struct rcu_state *rcu_state =" in kernel/rcu/tree_plugin.h to be something like "static struct rcu_state *rcu_state_p =", then fix the resulting build errors. (This will make the next step easier to carry out.)
10. In kernel/rcu/tree_plugin.h, there are alternative definitions of several functions under CONFIG_TREE_PREEMPT_RCU, with the only difference begin that one uses rcu_preempt_state and the other uses rcu_sched_state. Such functions can use the newish rcu_state pointer, so that there is a single definition living in kernel/rcu/tree.c. Sometimes you have to look carefully to see these functions, with one example being rcu_sched_force_quiescent_state(). A more easily visible example is kfree_call_rcu(). Identify these functions and consolidate them.