path: root/doc/developer/rcu.rst

.. highlight:: c

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 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:

* https://en.wikipedia.org/wiki/Read-copy-update
* https://www.kernel.org/doc/html/latest/kernel-hacking/locking.html#avoiding-locks-read-copy-update
* https://lwn.net/Articles/262464/
* http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf
* http://lse.sourceforge.net/locking/rcupdate.html

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 ``atomic_*`` call with ``memory_order_release``, which
   tells the compiler to make sure prior memory writes have completed before
   doing the atomic op.
#. ``ATOMLIST_*`` ``add`` operations do the ``memory_order_release`` for you.
#. 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 :c:func:`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 :c:func:`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.

.. c:function:: void rcu_read_lock()
.. c:function:: 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 :c:func:`rcu_free` on
      them.

.. c:struct:: rcu_head
.. c:struct:: rcu_head_close
.. c: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 :c:func:`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.

.. c:function:: 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 :c:func:`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
   :c:func:`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.

.. c:function:: 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 :c:func:`rcu_free`, except it calls ``close`` instead of
   ``free``.

Internals
^^^^^^^^^

.. c: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.

.. c:function:: struct rcu_thread *rcu_thread_prepare(void)
.. c:function:: void rcu_thread_unprepare(struct rcu_thread *rcu_thread)
.. c:function:: 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.

.. c:function:: 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``.