docs/devel/rcu.rst

1 Using RCU (Read-Copy-Update) for synchronization
4 Read-copy update (RCU) is a synchronization mechanism that is used to
5 protect read-mostly data structures.  RCU is very efficient and scalable
6 on the read side (it is wait-free), and thus can make the read paths
10 thus it is not used alone.  Typically, the write-side will use a lock to
17 RCU is fundamentally a "wait-to-finish" mechanism.  The read side marks
18 sections of code with "critical sections", and the update side will wait
26 for example, reader-writer locks.  It is so much more scalable that
43     -------------------    ------------------------    -------------------
61 -------
66         Used by a reader to inform the reclaimer that the reader is
67         entering an RCU read-side critical section.
70         Used by a reader to inform the reclaimer that the reader is
71         exiting an RCU read-side critical section.  Note that RCU
72         read-side critical sections may be nested and/or overlapping.
75         Blocks until all pre-existing RCU read-side critical sections
83         the updater is protected by the BQL), you can use ``call_rcu``.
86         This function invokes ``func(head)`` after all pre-existing RCU
87         read-side critical sections on all threads have completed.  This
116 ``void call_rcu(T *p, void (*func)(T *p), field-name);``
120 ``void g_free_rcu(T *p, field-name);``
121         This is a special-case version of ``call_rcu`` where the callback
134         data-dependent or need no ordering.  This is almost always the
135         case when using RCU, because read-side critical sections typically
140         RCU read-side critical sections must use ``qatomic_rcu_read()`` to
141         read data, unless concurrent writes are prevented by another
144         Furthermore, RCU read-side critical sections should traverse the
156         case when initializing a new copy of the RCU-protected data
160         order as reads in the RCU read-side critical sections (or if
174         either manually or by using the
181 ------------------
196 ----------------------
198 - Waiting on a mutex is possible, though discouraged, within an RCU critical
200   programming; not allowing this would prevent upgrading an RCU read-side
203 - ``qatomic_rcu_read`` and ``qatomic_rcu_set`` replace ``rcu_dereference`` and
206 - ``call_rcu`` is a macro that has an extra argument (the name of the first
213 ------------
215 Many patterns using read-writer locks translate directly to RCU, with
222 - the updater does not mean "everything that writes to a data structure",
226 - in some cases, creating a new version of a data structure may actually
230 Here are some frequently-used RCU idioms that are worth noting.
243 read-side critical section in progress, the RCU read-side primitives
244 may be used as a restricted reference-counting mechanism.  For example,
252 The RCU read-side critical section ensures that the value of ``p`` remains
255 The write side looks simply like this (with appropriate locking)::
274 The write side can be like this::
291 In both cases, the write side only performs removal.  Reclamation
294 last reference may be dropped on the read side.  Hence you can
298         if (qatomic_fetch_dec(&p->refcount) == 1) {
314     ------------------------------------------------------------------
326 out of the write-side critical section.
336 - ensuring that the old version of the array is available between removal
339 - avoiding mismatches in the read side between the array data and the
342 The first problem is avoided simply by not using ``realloc``.  Instead,
364     read side:
367         x = i < array->size ? array->data[i] : -1;
371     write side (running under a lock):
372         if (global_array->size == global_array->alloc) {
375                                  global_array->alloc * 2 * sizeof(T));
376             new_array->size = global_array->size;
377             new_array->alloc = global_array->alloc * 2;
378             memcpy(new_array->data, global_array->data,
379                    global_array->alloc * sizeof(T));
392 ----------