RCU

Introduction

RCU (Read-Copy-Update) is, fundamentally, a paradigm of multithreaded operation (and not a set of APIs.) The core ideas are:

  • longer, complicated updates to structures are made only on private, “invisible” copies. Other threads, when they access the structure, see an older (but consistent) copy.
  • once done, the updated copy is swapped in in a single operation so that other threads see either the old or the new data but no inconsistent state between.
  • the old instance is only released after making sure that it is impossible any other thread might still be reading it.

For more information, please search for general or Linux kernel RCU documentation; there is no way this doc can be comprehensive in explaining the interactions:

RCU, the TL;DR

  1. data structures are always consistent for reading. That’s the “R” part.
  2. reading never blocks / takes a lock.
  3. rcu_read_lock is not a lock in the traditional sense. Think of it as a “reservation”; it notes what the oldest possible thing the thread might be seeing is, and which thus can’t be deleted yet.
  4. you create some object, finish it up, and then publish it.
  5. publishing is an atomic_* call with memory_order_release, which tells the compiler to make sure prior memory writes have completed before doing the atomic op.
  6. ATOMLIST_* add operations do the memory_order_release for you.
  7. you can’t touch the object after it is published, except with atomic ops.
  8. because you can’t touch it, if you want to change it you make a new copy, work on that, and then publish the new copy. That’s the “CU” part.
  9. deleting the object is also an atomic op.
  10. other threads that started working before you published / deleted an object might not see the new object / still see the deleted object.
  11. because other threads may still see deleted objects, the free() needs to be delayed. That’s what rcu_free() is for.

When (not) to use RCU

RCU is designed for read-heavy workloads where objects are updated relatively rarely, but frequently accessed. Do not indiscriminately replace locking by RCU patterns.

The “copy” part of RCU implies that, while updating, several copies of a given object exist in parallel. Even after the updated copy is swapped in, the old object remains queued for freeing until all other threads are guaranteed to not be accessing it anymore, due to passing a sequence point. In addition to the increased memory usage, there may be some bursted (due to batching) malloc contention when the RCU cleanup thread does its thing and frees memory.

Other useful patterns

In addition to the full “copy object, apply changes, atomically update” approach, there are 2 “reduced” usage cases that can be done:

  • atomically updating single pieces of a particular object, e.g. some flags or configuration piece
  • straight up read-only / immutable objects

Both of these cases can be considered RCU “subsets”. For example, when maintaining an atomic list of items, but these items only have a single integer value that needs to be updated, that value can be atomically updated without copying the entire object. However, the object still needs to be free’d through rcu_free() since reading/updating and deleting might be happening concurrently. The same applies for immutable objects; deletion might still race with reading so they need to be free’d through RCU.

FRR API

Before diving into detail on the provided functions, it is important to note that the FRR RCU API covers the cleanup part of RCU, not the read-copy-update paradigm itself. These parts are handled by standard C11 atomic operations, and by extension through the atomic data structures (ATOMLIST, ATOMSORT & co.)

The rcu_* functions only make sense in conjunction with these RCU access patterns. If you’re calling the RCU API but not using these, something is wrong. The other way around is not necessarily true; it is possible to use atomic ops & datastructures with other types of locking, e.g. rwlocks.

void rcu_read_lock()
void rcu_read_unlock()

These functions acquire / release the RCU read-side lock. All access to RCU-guarded data must be inside a block guarded by these. Any number of threads may hold the RCU read-side lock at a given point in time, including both no threads at all and all threads.

The functions implement a depth counter, i.e. can be nested. The nested calls are cheap, since they only increment/decrement the counter. Therefore, any place that uses RCU data and doesn’t have a guarantee that the caller holds RCU (e.g. lib/ code) should just have its own rcu_read_lock/rcu_read_unlock pair.

At the “root” level (e.g. un-nested), these calls can incur the cost of one syscall (to futex()). That puts them on about the same cost as a mutex lock/unlock.

The thread_master code currently always holds RCU everywhere, except while doing the actual poll() syscall. This is both an optimization as well as an “easement” into getting RCU going. The current implementation contract is that any struct thread * callback is called with a RCU holding depth of 1, and that this is owned by the thread so it may (should) drop and reacquire it when doing some longer-running work.

Warning

The RCU read-side lock must be held continuously for the entire time any piece of RCU data is used. This includes any access to RCU data after the initial atomic_load. If the RCU read-side lock is released, any RCU-protected pointers as well as the data they refer to become invalid, as another thread may have called rcu_free() on them.

struct rcu_head
struct rcu_head_close
struct rcu_action

The rcu_head structures are small (16-byte) bits that contain the queueing machinery for the RCU sweeper/cleanup mechanisms.

Any piece of data that is cleaned up by RCU needs to have a matching rcu_head embedded in it. If there is more than one cleanup operation to be done (e.g. closing a file descriptor), more than one rcu_head may be embedded.

Warning

It is not possible to reuse a rcu_head. It is owned by the RCU code as soon as rcu_* is called on it.

The _close variant carries an extra int fd field to store the fd to be closed.

To minimize the amount of memory used for rcu_head, details about the RCU operation to be performed are moved into the rcu_action structure. It contains e.g. the MTYPE for rcu_free() calls. The pointer to be freed is stored as an offset relative to the rcu_head, which means it must be embedded as a struct field so the offset is constant.

The rcu_action structure is an implementation detail. Using rcu_free or rcu_close will set it up correctly without further code needed.

The rcu_head may be put in an union with other data if the other data is only used during “life” of the data, since the rcu_head is used only for the “death” of data. But note that other threads may still be reading a piece of data while a thread is working to free it.

void rcu_free(struct memtype *mtype, struct X *ptr, field)

Free a block of memory after RCU has ensured no other thread can be accessing it anymore. The pointer remains valid for any other thread that has called rcu_read_lock() before the rcu_free call.

Warning

In some other RCU implementations, the pointer remains valid to the calling thread if it is holding the RCU read-side lock. This is not the case in FRR, particularly when running single-threaded. Enforcing this rule also allows static analysis to find use-after-free issues.

mtype is the libfrr MTYPE_FOO allocation type to pass to XFREE().

field must be the name of a struct rcu_head member field in ptr. The offset of this field (which must be constant) is used to reduce the memory size of struct rcu_head.

Note

rcu_free (and rcu_close) calls are more efficient if they are put close to each other. When freeing several RCU’d resources, try to move the calls next to each other (even if the data structures do not directly point to each other.)

Having the calls bundled reduces the cost of adding the rcu_head to the RCU queue; the RCU queue is an atomic data structure whose usage will require the CPU to acquire an exclusive hold on relevant cache lines.

void rcu_close(struct rcu_head_close *head, int fd)

Close a file descriptor after ensuring no other thread might be using it anymore. Same as rcu_free(), except it calls close instead of free.

Internals

struct rcu_thread

Per-thread state maintained by the RCU code, set up by the following functions. A pointer to a thread’s own rcu_thread is saved in thread-local storage.

struct rcu_thread *rcu_thread_prepare(void)
void rcu_thread_unprepare(struct rcu_thread *rcu_thread)
void rcu_thread_start(struct rcu_thread *rcu_thread)

Since the RCU code needs to have a list of all active threads, these functions are used by the frr_pthread code to set up threads. Teardown is automatic. It should not be necessary to call these functions.

Any thread that accesses RCU-protected data needs to be registered with these functions. Threads that do not access RCU-protected data may call these functions but do not need to.

Note that passing a pointer to RCU-protected data to some library which accesses that pointer makes the library “access RCU-protected data”. In that case, either all of the library’s threads must be registered for RCU, or the code must instead pass a (non-RCU) copy of the data to the library.

void rcu_shutdown(void)

Stop the RCU sweeper thread and make sure all cleanup has finished.

This function is called on daemon exit by the libfrr code to ensure pending RCU operations are completed. This is mostly to get a clean exit without memory leaks from queued RCU operations. It should not be necessary to call this function as libfrr handles this.

FRR specifics and implementation details

The FRR RCU infrastructure has the following characteristics:

  • it is Epoch-based with a 32-bit wrapping counter. (This is somewhat different from other Epoch-based approaches which may be designed to only use 3 counter values, but works out to a simple implementation.)
  • instead of tracking CPUs as the Linux kernel does, threads are tracked. This has exactly zero semantic impact, RCU just cares about “threads of execution”, which the kernel can optimize to CPUs but we can’t. But it really boils down to the same thing.
  • there are no rcu_dereference and rcu_assign_pointer - use atomic_load and atomic_store instead. (These didn’t exist when the Linux RCU code was created.)
  • there is no synchronize_rcu; this is a design choice but may be revisited at a later point. synchronize_rcu blocks a thread until it is guaranteed that no other threads might still be accessing data structures that they may have access to at the beginning of the function call. This is a blocking design and probably not appropriate for FRR. Instead, rcu_call can be used to have the RCU sweeper thread make a callback after the same constraint is fulfilled in an asynchronous way. Most needs should be covered by rcu_free and rcu_close.