xref: /openbmc/qemu/docs/devel/rcu.rst (revision 646b5378)
1Using RCU (Read-Copy-Update) for synchronization
2================================================
3
4Read-copy update (RCU) is a synchronization mechanism that is used to
5protect read-mostly data structures.  RCU is very efficient and scalable
6on the read side (it is wait-free), and thus can make the read paths
7extremely fast.
8
9RCU supports concurrency between a single writer and multiple readers,
10thus it is not used alone.  Typically, the write-side will use a lock to
11serialize multiple updates, but other approaches are possible (e.g.,
12restricting updates to a single task).  In QEMU, when a lock is used,
13this will often be the "iothread mutex", also known as the "big QEMU
14lock" (BQL).  Also, restricting updates to a single task is done in
15QEMU using the "bottom half" API.
16
17RCU is fundamentally a "wait-to-finish" mechanism.  The read side marks
18sections of code with "critical sections", and the update side will wait
19for the execution of all *currently running* critical sections before
20proceeding, or before asynchronously executing a callback.
21
22The key point here is that only the currently running critical sections
23are waited for; critical sections that are started **after** the beginning
24of the wait do not extend the wait, despite running concurrently with
25the updater.  This is the reason why RCU is more scalable than,
26for example, reader-writer locks.  It is so much more scalable that
27the system will have a single instance of the RCU mechanism; a single
28mechanism can be used for an arbitrary number of "things", without
29having to worry about things such as contention or deadlocks.
30
31How is this possible?  The basic idea is to split updates in two phases,
32"removal" and "reclamation".  During removal, we ensure that subsequent
33readers will not be able to get a reference to the old data.  After
34removal has completed, a critical section will not be able to access
35the old data.  Therefore, critical sections that begin after removal
36do not matter; as soon as all previous critical sections have finished,
37there cannot be any readers who hold references to the data structure,
38and these can now be safely reclaimed (e.g., freed or unref'ed).
39
40Here is a picture::
41
42        thread 1                  thread 2                  thread 3
43    -------------------    ------------------------    -------------------
44    enter RCU crit.sec.
45           |                finish removal phase
46           |                begin wait
47           |                      |                    enter RCU crit.sec.
48    exit RCU crit.sec             |                           |
49                            complete wait                     |
50                            begin reclamation phase           |
51                                                       exit RCU crit.sec.
52
53
54Note how thread 3 is still executing its critical section when thread 2
55starts reclaiming data.  This is possible, because the old version of the
56data structure was not accessible at the time thread 3 began executing
57that critical section.
58
59
60RCU API
61-------
62
63The core RCU API is small:
64
65``void rcu_read_lock(void);``
66        Used by a reader to inform the reclaimer that the reader is
67        entering an RCU read-side critical section.
68
69``void rcu_read_unlock(void);``
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.
73
74``void synchronize_rcu(void);``
75        Blocks until all pre-existing RCU read-side critical sections
76        on all threads have completed.  This marks the end of the removal
77        phase and the beginning of reclamation phase.
78
79        Note that it would be valid for another update to come while
80        ``synchronize_rcu`` is running.  Because of this, it is better that
81        the updater releases any locks it may hold before calling
82        ``synchronize_rcu``.  If this is not possible (for example, because
83        the updater is protected by the BQL), you can use ``call_rcu``.
84
85``void call_rcu1(struct rcu_head * head, void (*func)(struct rcu_head *head));``
86        This function invokes ``func(head)`` after all pre-existing RCU
87        read-side critical sections on all threads have completed.  This
88        marks the end of the removal phase, with func taking care
89        asynchronously of the reclamation phase.
90
91        The ``foo`` struct needs to have an ``rcu_head`` structure added,
92        perhaps as follows::
93
94            struct foo {
95                struct rcu_head rcu;
96                int a;
97                char b;
98                long c;
99            };
100
101        so that the reclaimer function can fetch the ``struct foo`` address
102        and free it::
103
104            call_rcu1(&foo.rcu, foo_reclaim);
105
106            void foo_reclaim(struct rcu_head *rp)
107            {
108                struct foo *fp = container_of(rp, struct foo, rcu);
109                g_free(fp);
110            }
111
112        ``call_rcu1`` is typically used via either the ``call_rcu`` or
113        ``g_free_rcu`` macros, which handle the common case where the
114        ``rcu_head`` member is the first of the struct.
115
116``void call_rcu(T *p, void (*func)(T *p), field-name);``
117        If the ``struct rcu_head`` is the first field in the struct, you can
118        use this macro instead of ``call_rcu1``.
119
120``void g_free_rcu(T *p, field-name);``
121        This is a special-case version of ``call_rcu`` where the callback
122        function is ``g_free``.
123        In the example given in ``call_rcu1``, one could have written simply::
124
125            g_free_rcu(&foo, rcu);
126
127``typeof(*p) qatomic_rcu_read(p);``
128        ``qatomic_rcu_read()`` is similar to ``qatomic_load_acquire()``, but
129        it makes some assumptions on the code that calls it.  This allows a
130        more optimized implementation.
131
132        ``qatomic_rcu_read`` assumes that whenever a single RCU critical
133        section reads multiple shared data, these reads are either
134        data-dependent or need no ordering.  This is almost always the
135        case when using RCU, because read-side critical sections typically
136        navigate one or more pointers (the pointers that are changed on
137        every update) until reaching a data structure of interest,
138        and then read from there.
139
140        RCU read-side critical sections must use ``qatomic_rcu_read()`` to
141        read data, unless concurrent writes are prevented by another
142        synchronization mechanism.
143
144        Furthermore, RCU read-side critical sections should traverse the
145        data structure in a single direction, opposite to the direction
146        in which the updater initializes it.
147
148``void qatomic_rcu_set(p, typeof(*p) v);``
149        ``qatomic_rcu_set()`` is similar to ``qatomic_store_release()``,
150        though it also makes assumptions on the code that calls it in
151        order to allow a more optimized implementation.
152
153        In particular, ``qatomic_rcu_set()`` suffices for synchronization
154        with readers, if the updater never mutates a field within a
155        data item that is already accessible to readers.  This is the
156        case when initializing a new copy of the RCU-protected data
157        structure; just ensure that initialization of ``*p`` is carried out
158        before ``qatomic_rcu_set()`` makes the data item visible to readers.
159        If this rule is observed, writes will happen in the opposite
160        order as reads in the RCU read-side critical sections (or if
161        there is just one update), and there will be no need for other
162        synchronization mechanism to coordinate the accesses.
163
164The following APIs must be used before RCU is used in a thread:
165
166``void rcu_register_thread(void);``
167        Mark a thread as taking part in the RCU mechanism.  Such a thread
168        will have to report quiescent points regularly, either manually
169        or through the ``QemuCond``/``QemuSemaphore``/``QemuEvent`` APIs.
170
171``void rcu_unregister_thread(void);``
172        Mark a thread as not taking part anymore in the RCU mechanism.
173        It is not a problem if such a thread reports quiescent points,
174        either manually or by using the
175        ``QemuCond``/``QemuSemaphore``/``QemuEvent`` APIs.
176
177Note that these APIs are relatively heavyweight, and should **not** be
178nested.
179
180Convenience macros
181------------------
182
183Two macros are provided that automatically release the read lock at the
184end of the scope.
185
186``RCU_READ_LOCK_GUARD()``
187         Takes the lock and will release it at the end of the block it's
188         used in.
189
190``WITH_RCU_READ_LOCK_GUARD()  { code }``
191         Is used at the head of a block to protect the code within the block.
192
193Note that a ``goto`` out of the guarded block will also drop the lock.
194
195Differences with Linux
196----------------------
197
198- Waiting on a mutex is possible, though discouraged, within an RCU critical
199  section.  This is because spinlocks are rarely (if ever) used in userspace
200  programming; not allowing this would prevent upgrading an RCU read-side
201  critical section to become an updater.
202
203- ``qatomic_rcu_read`` and ``qatomic_rcu_set`` replace ``rcu_dereference`` and
204  ``rcu_assign_pointer``.  They take a **pointer** to the variable being accessed.
205
206- ``call_rcu`` is a macro that has an extra argument (the name of the first
207  field in the struct, which must be a struct ``rcu_head``), and expects the
208  type of the callback's argument to be the type of the first argument.
209  ``call_rcu1`` is the same as Linux's ``call_rcu``.
210
211
212RCU Patterns
213------------
214
215Many patterns using read-writer locks translate directly to RCU, with
216the advantages of higher scalability and deadlock immunity.
217
218In general, RCU can be used whenever it is possible to create a new
219"version" of a data structure every time the updater runs.  This may
220sound like a very strict restriction, however:
221
222- the updater does not mean "everything that writes to a data structure",
223  but rather "everything that involves a reclamation step".  See the
224  array example below
225
226- in some cases, creating a new version of a data structure may actually
227  be very cheap.  For example, modifying the "next" pointer of a singly
228  linked list is effectively creating a new version of the list.
229
230Here are some frequently-used RCU idioms that are worth noting.
231
232
233RCU list processing
234^^^^^^^^^^^^^^^^^^^
235
236TBD (not yet used in QEMU)
237
238
239RCU reference counting
240^^^^^^^^^^^^^^^^^^^^^^
241
242Because grace periods are not allowed to complete while there is an RCU
243read-side critical section in progress, the RCU read-side primitives
244may be used as a restricted reference-counting mechanism.  For example,
245consider the following code fragment::
246
247    rcu_read_lock();
248    p = qatomic_rcu_read(&foo);
249    /* do something with p. */
250    rcu_read_unlock();
251
252The RCU read-side critical section ensures that the value of ``p`` remains
253valid until after the ``rcu_read_unlock()``.  In some sense, it is acquiring
254a reference to ``p`` that is later released when the critical section ends.
255The write side looks simply like this (with appropriate locking)::
256
257    qemu_mutex_lock(&foo_mutex);
258    old = foo;
259    qatomic_rcu_set(&foo, new);
260    qemu_mutex_unlock(&foo_mutex);
261    synchronize_rcu();
262    free(old);
263
264If the processing cannot be done purely within the critical section, it
265is possible to combine this idiom with a "real" reference count::
266
267    rcu_read_lock();
268    p = qatomic_rcu_read(&foo);
269    foo_ref(p);
270    rcu_read_unlock();
271    /* do something with p. */
272    foo_unref(p);
273
274The write side can be like this::
275
276    qemu_mutex_lock(&foo_mutex);
277    old = foo;
278    qatomic_rcu_set(&foo, new);
279    qemu_mutex_unlock(&foo_mutex);
280    synchronize_rcu();
281    foo_unref(old);
282
283or with ``call_rcu``::
284
285    qemu_mutex_lock(&foo_mutex);
286    old = foo;
287    qatomic_rcu_set(&foo, new);
288    qemu_mutex_unlock(&foo_mutex);
289    call_rcu(foo_unref, old, rcu);
290
291In both cases, the write side only performs removal.  Reclamation
292happens when the last reference to a ``foo`` object is dropped.
293Using ``synchronize_rcu()`` is undesirably expensive, because the
294last reference may be dropped on the read side.  Hence you can
295use ``call_rcu()`` instead::
296
297     foo_unref(struct foo *p) {
298        if (qatomic_fetch_dec(&p->refcount) == 1) {
299            call_rcu(foo_destroy, p, rcu);
300        }
301    }
302
303
304Note that the same idioms would be possible with reader/writer
305locks::
306
307    read_lock(&foo_rwlock);         write_mutex_lock(&foo_rwlock);
308    p = foo;                        p = foo;
309    /* do something with p. */      foo = new;
310    read_unlock(&foo_rwlock);       free(p);
311                                    write_mutex_unlock(&foo_rwlock);
312                                    free(p);
313
314    ------------------------------------------------------------------
315
316    read_lock(&foo_rwlock);         write_mutex_lock(&foo_rwlock);
317    p = foo;                        old = foo;
318    foo_ref(p);                     foo = new;
319    read_unlock(&foo_rwlock);       foo_unref(old);
320    /* do something with p. */      write_mutex_unlock(&foo_rwlock);
321    read_lock(&foo_rwlock);
322    foo_unref(p);
323    read_unlock(&foo_rwlock);
324
325``foo_unref`` could use a mechanism such as bottom halves to move deallocation
326out of the write-side critical section.
327
328
329RCU resizable arrays
330^^^^^^^^^^^^^^^^^^^^
331
332Resizable arrays can be used with RCU.  The expensive RCU synchronization
333(or ``call_rcu``) only needs to take place when the array is resized.
334The two items to take care of are:
335
336- ensuring that the old version of the array is available between removal
337  and reclamation;
338
339- avoiding mismatches in the read side between the array data and the
340  array size.
341
342The first problem is avoided simply by not using ``realloc``.  Instead,
343each resize will allocate a new array and copy the old data into it.
344The second problem would arise if the size and the data pointers were
345two members of a larger struct::
346
347    struct mystuff {
348        ...
349        int data_size;
350        int data_alloc;
351        T   *data;
352        ...
353    };
354
355Instead, we store the size of the array with the array itself::
356
357    struct arr {
358        int size;
359        int alloc;
360        T   data[];
361    };
362    struct arr *global_array;
363
364    read side:
365        rcu_read_lock();
366        struct arr *array = qatomic_rcu_read(&global_array);
367        x = i < array->size ? array->data[i] : -1;
368        rcu_read_unlock();
369        return x;
370
371    write side (running under a lock):
372        if (global_array->size == global_array->alloc) {
373            /* Creating a new version.  */
374            new_array = g_malloc(sizeof(struct arr) +
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));
380
381            /* Removal phase.  */
382            old_array = global_array;
383            qatomic_rcu_set(&global_array, new_array);
384            synchronize_rcu();
385
386            /* Reclamation phase.  */
387            free(old_array);
388        }
389
390
391References
392----------
393
394* The `Linux kernel RCU documentation <https://docs.kernel.org/RCU/>`__
395