Using read-copy-update

This article is part of the LWN Porting Drivers to 2.6 series. Read-copy-update (RCU) is a mutual exclusion technique which can operate without locking most of the time. It can yield significant performance benefits when the data to be protected is accessed via a pointer, is read frequently, changed rarely, and references to the structure are not held while a kernel thread sleeps. The core idea behind RCU is that, when the data requires updating, a pointer to a new structure containing the new data can be stored immediately. The old structure containing the outdated data can then be freed at leisure, after it is certain that no process in the system holds a reference to that structure. For details on the ideas behind RCU, see this LWN article, or (for many details) this paper. Just don't ask SCO, even though they claim to own the technique. The first step in using RCU within a subsystem is to define a structure containing the data to be protected. Often that structure already exists; for example, RCU has been retrofitted into the dentry cache (using struct dentry), the network routing cache (struct rtable), and several other, similar contexts. The structures need to be allocated dynamically and accessed via a pointer - RCU cannot be used with static structures. Code which reads data structures protected by RCU need only take a couple of simple precautions: A call to rcu_read_lock() should be made before accessing the data, and rcu_read_unlock() should be called afterward. This call disables preemption (and does nothing else) - a fast but necessary operation for RCU to work properly. These calls (along with the rest of the RCU definitions) are found in <linux/rcupdate.h>. The code must not sleep while the "RCU read lock" is held. Thus, code which reads an RCU-protected data structure will look something like: struct my_stuff *stuff; rcu_read_lock(); stuff = find_the_stuff(args...); do_something_with(stuff); /* Cannot sleep */ do_something_else_with(stuff); /* ditto */ rcu_read_unlock(); The write side of RCU is a little more complicated, but not that difficult. To update a data structure, the code starts by allocating a new copy of that structure, and filling in the new information. The code should then replace the pointer to the outdated structure with the new one, keeping a copy of the old pointer. After this operation, kernel code running on any other processor will find the new version of the structure. The old one cannot yet be freed, however, since it is possible that another processor is still using it. The code should arrange to dispose of the old structure when it is known that it cannot be referenced anywhere else in the system. That is done through a call to call_rcu(): void call_rcu(struct rcu_head *head, void (*func)(void *arg), void *arg); The calling code must provide an rcu_head structure, but need not initialize it in any way. Usually, that structure is embedded within the larger structure protected by RCU. The function func will be called when the structure can be safely freed, with arg as its one argument. All that func need do, normally, is call something like kfree() to free up the structure. The RCU algorithm works by waiting until every processor in the system has scheduled at least once. Since the rules require that references to RCU-protected structures cannot be held over sleeps, no processor can possibly hold a reference to an old structure after it has scheduled. When all processors have scheduled (after the pointer change), references to the old structure can not exist, and the structure can be freed. For what it's worth, the RCU code exports the "wait for everybody to schedule" functionality, should it be useful elsewhere. To perform this wait, one need only make a call to synchronize_kernel(). Post a comment   Using read-copy-update (Posted Jul 11, 2003 14:41 UTC (Fri) by goatbar) (Post reply) What happens if a different processor updates the stucture before before the one scheduled to be deleted is deleted. It must keep a queue of these sturctures to delete, right? RCU seems like a nice and simple algorithm.   Using read-copy-update (Posted Jan 16, 2004 23:26 UTC (Fri) by PaulMcKenney) (Post reply) Yep, RCU maintains a per-CPU queue of callbacks registered by call_rcu(), which in this case would be equivalent to a per-CPU queue of items to be deleted.