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¶
- data structures are always consistent for reading. That’s the “R” part.
- reading never blocks / takes a lock.
- 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.
- you create some object, finish it up, and then publish it.
- publishing is an
memory_order_release, which tells the compiler to make sure prior memory writes have completed before doing the atomic op.
addoperations do the
- you can’t touch the object after it is published, except with atomic ops.
- 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.
- deleting the object is also an atomic op.
- other threads that started working before you published / deleted an object might not see the new object / still see the deleted object.
- because other threads may still see deleted objects, the
free()needs to be delayed. That’s what
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
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.
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.)
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.
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.
thread_mastercode 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.
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_headstructures 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_headembedded in it. If there is more than one cleanup operation to be done (e.g. closing a file descriptor), more than one
rcu_headmay be embedded.
It is not possible to reuse a
rcu_head. It is owned by the RCU code as soon as
rcu_*is called on it.
_closevariant carries an extra
int fdfield 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_actionstructure. 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.
rcu_actionstructure is an implementation detail. Using
rcu_closewill set it up correctly without further code needed.
rcu_headmay be put in an union with other data if the other data is only used during “life” of the data, since the
rcu_headis 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.
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
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.
mtypeis the libfrr
MTYPE_FOOallocation type to pass to
fieldmust be the name of a
struct rcu_headmember field in
ptr. The offset of this field (which must be constant) is used to reduce the memory size of
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_headto 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.
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
Per-thread state maintained by the RCU code, set up by the following functions. A pointer to a thread’s own
rcu_threadis saved in thread-local storage.
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_pthreadcode 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.
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
atomic_storeinstead. (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_rcublocks 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_callcan 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