Read-copy-update (RCU) - What are they and how they can be used

Very good explanation about RCUs at wikepidia with heading Read-Copy-Update.

RCU locks are replacement for Read-write spin locks. But they are very fast for read operations. It has similar overhead as write locks for add operations and little bit additional overhead in case of 'delete' operations. Networking applications typically maintain multiple context blocks (records) in data structure such as hash lists, linked lists, arrays etc.. . In many cases, these data structure are searched to find out the matching record on per packet basis. Records are created and removed infrequently. RCUs are best way to protect these kinds of data structures in Multicore SMP environments.

Read operation in RW locks in SMP Environments is heavy due to high number of instructions in these functions. Hence these functions take more CPU cycles even when there is no lock contention. That is why, RCUs are preferred.

There are mainly five API functions in RCU:

1. rcu_read_lock
2. rcu_read_unlock
3. rcu_assign_ptr
4. rcu_dereference
5. call_rcu/synchronize_rcu

rcu_read_lock and rcu_read_unlock are used while searching for a record in any data structure (linked list, arrays etc..). While searching for a record, yet time you may need to go through the list via next/prev pointers in linked list. These pointers must be dereferenced using rcu_dereference. Typically the pointers which are modified with rcu_assign_ptr in add and delete operations need to be dereferenced while traversing the list. These two functions are mainly to take care of weak order processors which execute instructions out-of-order and also write into the memory locations out-of-order. If you really look at body of these functions, they execute memory barrier instructions. Many RCU implementation also don't have many instructions in rcu_read_lock and rcu_read_unlock. In Linux, RCU read lock mostly disables preemption (If preemption is enabled). Writer task is expected to use normal spin locks to protect the data structure from other writers. Write task can involve either addition or deletion of record in and out of data structures. If readers can be in softirq, it is necessary that writes use 'bh' version of spin locks.

RCUs read operation depends on the fact that any word assignment to a memory location is atomic which is true in all processors. Reason for having memory barrier operation in rcu_assign_ptr is to ensure that value assigned appears on the cache/memory before any dereferencing happens by other cores.

Whenever writer removes the records from application data structure, it needs to call synchronize_rcu or call_rcu. call_rcu is asynchronous mechanism and is used by application when it needs to get control after all cores complete their current scheduling cycle, which means that the record is not being accessed by any core. call_rcu takes a function pointer and a callback argument. This callback function is called after all cores complete its current scheduling cycle. Application callback can take further action such as freeing the record. If the record is being referred by pointers by some other application records, then this callback function can't free the memory until all references are removed. In those cases, reference count need to be maintained by records in addition to RCUs.