10.3.3.2 RCU has Publish-Subscribe and Version-Maintenance APIs

Fortunately, the RCU publish-subscribe and version-maintenance primitives shown in the following table apply to all of the variants of RCU discussed above. This commonality can in some cases allow more code to be shared, which certainly reduces the API proliferation that would otherwise occur. The original purpose of the RCU publish-subscribe APIs was to bury memory barriers into these APIs, so that Linux kernel programmers could use RCU without needing to become expert on the memory-ordering models of each of the 20+ CPU families that Linux supports [Spr01].


Table: RCU Publish-Subscribe and Version Maintenance APIs
Category Primitives Availability Overhead
List traversal list_for_each_entry_rcu() 2.5.59 Simple instructions (memory barrier on Alpha)
List update list_add_rcu() 2.5.44 Memory barrier
  list_add_tail_rcu() 2.5.44 Memory barrier
  list_del_rcu() 2.5.44 Simple instructions
  list_replace_rcu() 2.6.9 Memory barrier
  list_splice_init_rcu() 2.6.21 Grace-period latency
Hlist traversal hlist_for_each_entry_rcu() 2.6.8 Simple instructions (memory barrier on Alpha)
  hlist_add_after_rcu() 2.6.14 Memory barrier
  hlist_add_before_rcu() 2.6.14 Memory barrier
  hlist_add_head_rcu() 2.5.64 Memory barrier
  hlist_del_rcu() 2.5.64 Simple instructions
  hlist_replace_rcu() 2.6.15 Memory barrier
Pointer traversal rcu_dereference() 2.6.9 Simple instructions (memory barrier on Alpha)
Pointer update rcu_assign_pointer() 2.6.10 Memory barrier


The first pair of categories operate on Linux struct list_head lists, which are circular, doubly-linked lists. The list_for_each_entry_rcu() primitive traverses an RCU-protected list in a type-safe manner, while also enforcing memory ordering for situations where a new list element is inserted into the list concurrently with traversal. On non-Alpha platforms, this primitive incurs little or no performance penalty compared to list_for_each_entry(). The list_add_rcu(), list_add_tail_rcu(), and list_replace_rcu() primitives are analogous to their non-RCU counterparts, but incur the overhead of an additional memory barrier on weakly-ordered machines. The list_del_rcu() primitive is also analogous to its non-RCU counterpart, but oddly enough is very slightly faster due to the fact that it poisons only the prev pointer rather than both the prev and next pointers as list_del() must do. Finally, the list_splice_init_rcu() primitive is similar to its non-RCU counterpart, but incurs a full grace-period latency. The purpose of this grace period is to allow RCU readers to finish their traversal of the source list before completely disconnecting it from the list header - failure to do this could prevent such readers from ever terminating their traversal.

Quick Quiz 10.31: Why doesn't list_del_rcu() poison both the next and prev pointers? End Quick Quiz

The second pair of categories operate on Linux's struct hlist_head, which is a linear linked list. One advantage of struct hlist_head over struct list_head is that the former requires only a single-pointer list header, which can save significant memory in large hash tables. The struct hlist_head primitives in the table relate to their non-RCU counterparts in much the same way as do the struct list_head primitives.

The final pair of categories operate directly on pointers, and are useful for creating RCU-protected non-list data structures, such as RCU-protected arrays and trees. The rcu_assign_pointer() primitive ensures that any prior initialization remains ordered before the assignment to the pointer on weakly ordered machines. Similarly, the rcu_dereference() primitive ensures that subsequent code dereferencing the pointer will see the effects of initialization code prior to the corresponding rcu_assign_pointer() on Alpha CPUs. On non-Alpha CPUs, rcu_dereference() documents which pointer dereferences are protected by RCU.

Quick Quiz 10.32: Normally, any pointer subject to rcu_dereference() must always be updated using rcu_assign_pointer(). What is an exception to this rule? End Quick Quiz

Quick Quiz 10.33: Are there any downsides to the fact that these traversal and update primitives can be used with any of the RCU API family members? End Quick Quiz

Paul E. McKenney 2011-12-16