The RCU-protected list API

URCU provides two types of RCU-protected lists that are derived from the GNU libc implementation. One set is circular and doubly linked and the other set is linear but still doubly linked. In both cases, insertion and deletion are O(1) operations even given only a pointer to the item in question.

The circular lists use the cds_list_head structure for both the list header and for list elements. This structure is embedded within the data structure to be included in the list. A given data structure can be placed on multiple lists by having multiple cds_list_head structure embedded within it. This same cds_list_head structure can be used both for RCU-protected lists and for lists protected by other synchronization mechanisms.

The circular lists are best for a great many situations, but if you are creating a large hash table, the cds_list_head structure's pair of pointers can consume excessive amounts of storage. This use case is better served by linear lists that have smaller header structures. The linear lists use the cds_hlist_head structure for the list header and the the cds_hlist_node structure for the list elements. Similar to the circular list, the cds_hlist_node structure is normally embedded within the data structure to be included in the list.

The APIs for these two types of lists should be reasonably familiar, so they are listed below with minimal explanation. The first list is for the circular lists, and the second one for the linear lists. In all cases, unless otherwise noted, the caller must take whatever action is required to ensure exclusive access by updaters and non-RCU readers to the list and elements in question, for example, by holding appropriate locks.

The operations on circular cds_list_head lists are:

1. CDS_INIT_LIST_HEAD(ptr): Initialize a cds_list_head structure from executable code.
2. CDS_LIST_HEAD_INIT(name): Initializer for a cds_list_head structure declaration. Example use:
   struct cds_list_head my_list = CDS_LIST_HEAD_INIT(my_list);
3. CDS_LIST_HEAD(name): Declare and initialize a cds_list_head structure as either a global variable or an on-stack variable.
4. void cds_list_add(struct cds_list_head *newp, struct cds_list_head *head): Add element newp to the head of list head.
5. void cds_list_add_tail(struct cds_list_head *newp, struct cds_list_head *head): Add element newp to the tail of list head.
6. void cds_list_del(struct cds_list_head *elem): Delete element elem from whatever list it is part of. It is legal to call this function on an element that is not part of a list only if that element has been properly initialized.
7. void cds_list_del_init(struct cds_list_head *elem): Similar to cds_list_del(), but initialize the element after deleting it.
8. int cds_list_empty(struct cds_list_head *head): Return true if list head is empty.
9. cds_list_entry(ptr, type, member): Given a pointer ptr to a cds_list_head structure that is embedded in a structure of type type as field member, return a pointer to the enclosing structure.
10. cds_list_first_entry(ptr, type, member): Given a pointer ptr to a cds_list_head structure, and given that the list elements are embedded in a structure of type type as field member, return a pointer to the enclosing structure for the first element in the list.
11. cds_list_for_each_entry(pos, head, member): Iterate over list head using pointer pos (which is of the type of the enclosing structure), where the cds_list_head are field member within the enclosing structure. In short, pos references each element of the list on each pass through the loop. This macro expands to a for loop, and must therefore be immediately followed by a statement or a statement block.
12. cds_list_for_each_entry_reverse(pos, head, member): Similar to cds_list_for_each_entry(), but iterating over the list in reverse order.
13. cds_list_for_each(pos, head): Iterate pointer pos over the cds_list_head structures in the list headed by head.
14. cds_list_for_each_safe(pos, p, head): Similar to cds_list_for_each(), but pre-traversing the ->next pointer so that the body of the loop can safely delete the current element.
15. cds_list_for_each_prev(pos, head): Similar to cds_list_for_each(), but starting the traversal at the element preceding head and preceding in reverse order.
16. cds_list_for_each_prev_safe(pos, p, head): Similar to cds_list_for_each_prev(), but pre-traversing the ->prev pointer so that the body of the loop can safely delete the current element.
17. void cds_list_move(struct cds_list_head *elem, struct cds_list_head *head): Move element elem from whatever list it is in and then add it as the first element of head.
18. void cds_list_replace(struct cds_list_head *old, struct cds_list_head *_new): Remove element old from whatever list it was in and replacing it with new.
19. void cds_list_replace_init(struct cds_list_head *old, struct cds_list_head *_new): Similar to cds_list_replace(), but initializing old.
20. void cds_list_splice(struct cds_list_head *add, struct cds_list_head *head): Splice the list headed by add into the beginning of the list headed by head.

In addition, the following RCU-protected operations may also be used on circular cds_list_head lists:

1. void cds_list_add_rcu(struct cds_list_head *newp, struct cds_list_head *head): Add element newp to the head of list head, allowing for concurrent RCU readers. Threads invoking this function need not be registered as RCU readers.
2. void cds_list_del_rcu(struct cds_list_head *elem): Similar to cds_list_del(), but allow concurrent RCU readers. Threads invoking this function need not be registered as RCU readers.
3. void cds_list_replace_rcu(struct cds_list_head *old, struct cds_list_head *_new): Similar to cds_list_replace(), but allowing concurrent RCU readers. Threads invoking this function need not be registered as RCU readers.
4. cds_list_for_each_entry_rcu(pos, head, member): Similar to cds_list_for_each_entry(), but allowing for concurrent RCU updaters. Note that the calling thread must be registered as an RCU reader and furthermore must be in an RCU read-side critical section.
5. cds_list_for_each_rcu(pos, head): Similar to cds_list_for_each(), but allowing concurrent RCU readers. Note that the calling thread must be registered as an RCU reader and furthermore must be in an RCU read-side critical section.

The operations on linear cds_hlist_head lists are:

1. void CDS_INIT_HLIST_HEAD(struct cds_hlist_head *ptr): Initialize a cds_hlist_head structure from executable code.
2. void cds_hlist_add_head(struct cds_hlist_node *newp, struct cds_hlist_head *head): Add element newp to the head of list head.
3. void cds_hlist_del(struct cds_hlist_node *elem): Delete element elem from whatever list it is in.
4. cds_hlist_entry(ptr, type, member): Given a pointer ptr to a cds_hlist_node structure that is embedded in a structure of type type as field member, return a pointer to the enclosing structure.
5. cds_hlist_for_each_entry(entry, pos, head, member): Iterate pointer entry over the enclosing structures of the list pointed to by head, where the cds_hlist_node structures are embedded in the enclosing structures as field member. The pos argument is used internally, and must be of type cds_hlist_node. This macro expands to a for statement, so it must be immediately followed by either a statement or a statement block.
6. cds_hlist_for_each_entry_2(entry, head, member): Iterate pointer entry over the enclosing structures of the list pointed to by head, where the cds_hlist_node structures are embedded in the enclosing structures as field member. This macro expands to a for statement, so it must be immediately followed by either a statement or a statement block.
7. cds_hlist_for_each_entry_safe(entry, pos, p, head, member): Similar to cds_hlist_for_each_entry(), but allowing the current element to be deleted and freed by the body of the loop.
8. cds_hlist_for_each_entry_safe_2(entry, p, head, member): Similar to cds_hlist_for_each_entry_2(), but allowing the current element to be deleted and freed by the body of the loop.

In addition, the following RCU-protected operations may also be used on linear cds_hlist_head lists:

1. void cds_hlist_add_head_rcu(struct cds_hlist_node *newp, struct cds_hlist_head *head): Similar to cds_hlist_add_head(), but allowing concurrent RCU readers. Threads invoking this function need not be registered as RCU readers.
2. void cds_hlist_del_rcu(struct cds_hlist_node *elem): Similar to cds_hlist_del(), but allowing concurrent RCU readers. Threads invoking this function need not be registered as RCU readers.
3. cds_hlist_for_each_entry_rcu(entry, pos, head, member): Similar to cds_hlist_for_each_entry(), but allowing concurrent readers.
4. cds_hlist_for_each_entry_rcu_2(entry, head, member): Similar to cds_hlist_for_each_entry_2(), but allowing concurrent readers.

Of course, parallel operations on a single list do not scale well, at least in the absence of a very large fraction of RCU readers. Therefore, the usual approach is to have a large number of lists, each of which may be operated on independently. One organized way to do this is to group lists into hash tables, which are covered in a separate article.