userspace-rcu (URCU)

The library includes several high-performance structures that do not strictly rely on RCU for their core mechanics, but offer different synchronization guarantees:

Stacks

• urcu/wfstack.h: Provides wait-free push and wait-free pop_all. Supports both blocking and non-blocking pop and traversal. Note: Requires external synchronization techniques to handle the ABA problem during pop.
• urcu/lfstack.h: Provides lock-free push and lock-free pop, along with wait-free pop_all and wait-free traversal. (Note: This deprecates urcu/rculfstack.h). Requires external synchronization to handle ABA.

Queues

• urcu/wfcqueue.h: Concurrent queue with wait-free enqueue. Supports blocking/non-blocking dequeue, splice (moving all elements from one queue to another), and traversal. Uses mutual exclusion for dequeue, splice (from source), and traversal. (Note: This deprecates urcu/wfqueue.h).
• urcu/rculfqueue.h: RCU-based queue with lock-free enqueue and lock-free dequeue. Uses RCU to provide existence guarantees.

The urcu library provides several concurrent data structures categorized by their synchronization requirements and performance characteristics. When choosing a structure, consider whether you need RCU-based read traversals, lock-free/wait-free properties, or specific structures like hash tables.

RCU-based Lists

• urcu/list.h: Standard doubly-linked list. Requires mutual exclusion for both updates and reads.
• urcu/rculist.h: Doubly-linked list that allows RCU read traversals. Requires mutual exclusion for updates, but reads can be performed without locks.
• urcu/hlist.h: Doubly-linked list with a single-pointer head (useful for hash tables). Requires mutual exclusion for updates and reads. Tail lookup is $O(n)$.
• urcu/rcuhlist.h: Doubly-linked list with a single-pointer head. Allows RCU read traversals. Requires mutual exclusion for updates. Tail lookup is $O(n)$.

RCU provides two main ways to wait for grace periods (the time during which all pre-existing read-side critical sections have completed):

Blocking Wait

Use synchronize_rcu() to block the current thread until every pre-existing RCU read-side critical section has completed. Note that this is not a reader-writer lock; it does not necessarily wait for critical sections that have not yet started.

Polling Wait

If you need to check for completion without blocking, use the polling API. This requires the caller to be a registered RCU read-side thread (and for the QSBR flavor, the caller must be online).

1. Call start_poll_synchronize_rcu() to obtain a struct urcu_gp_poll_state handle.
2. Periodically call poll_state_synchronize_rcu(state) with that handle. It returns true if the grace period has completed, and false otherwise.

// Polling example
struct urcu_gp_poll_state state = start_poll_synchronize_rcu();
while (!poll_state_synchronize_rcu(state)) {
    // Do other work or sleep
}

Userspace RCU provides several flavors of the RCU implementation. The API members for a specific flavor are prefixed with urcu_<flavor>_. Choose the one that best fits your performance and intrusiveness requirements:

Regardless of the flavor chosen, the core RCU lifecycle follows these patterns:

1. Thread Registration

Every thread that performs reader critical sections must register with the library:

• Call urcu_<flavor>_register_thread() before entering critical sections.
• Call urcu_<flavor>_unregister_thread() before the thread exits.

2. Reading (Reader Critical Section)

Protect reads using lock/unlock pairs. Inside the lock, use rcu_dereference() to safely access protected pointers:

// Example pattern
urcu_<flavor>_read_lock();
// ... perform reads using rcu_dereference(ptr) ...
urcu_<flavor>_read_unlock();

3. Writing (Updating Data)

Updates are performed by assigning new pointers and then waiting for the grace period to end:

• Use rcu_assign_pointer() or rcu_xchg_pointer() to update pointers.
• Call urcu_<flavor>_synchronize_rcu() to wait for the grace period. Once this returns, the old values are safe to reclaim.

Polling Alternative: Instead of blocking in synchronize_rcu(), you can poll for completion:

1. Call urcu_<flavor>_start_poll_synchronize_rcu() to start polling.
2. Periodically call urcu_<flavor>_poll_state_synchronize_rcu(). It returns true when the grace period is complete, false otherwise.