Merge tag 'pull-loongarch-20241016' of https://gitlab.com/gaosong/qemu into staging
[qemu/armbru.git] / docs / devel / rcu.rst
blobdd07c1d9195b0885aa0621e8e1428e11e4d95580
1 Using RCU (Read-Copy-Update) for synchronization
2 ================================================
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
7 extremely fast.
9 RCU supports concurrency between a single writer and multiple readers,
10 thus it is not used alone.  Typically, the write-side will use a lock to
11 serialize multiple updates, but other approaches are possible (e.g.,
12 restricting updates to a single task).  In QEMU, when a lock is used,
13 this will often be the "iothread mutex", also known as the "big QEMU
14 lock" (BQL).  Also, restricting updates to a single task is done in
15 QEMU using the "bottom half" API.
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
19 for the execution of all *currently running* critical sections before
20 proceeding, or before asynchronously executing a callback.
22 The key point here is that only the currently running critical sections
23 are waited for; critical sections that are started **after** the beginning
24 of the wait do not extend the wait, despite running concurrently with
25 the updater.  This is the reason why RCU is more scalable than,
26 for example, reader-writer locks.  It is so much more scalable that
27 the system will have a single instance of the RCU mechanism; a single
28 mechanism can be used for an arbitrary number of "things", without
29 having to worry about things such as contention or deadlocks.
31 How is this possible?  The basic idea is to split updates in two phases,
32 "removal" and "reclamation".  During removal, we ensure that subsequent
33 readers will not be able to get a reference to the old data.  After
34 removal has completed, a critical section will not be able to access
35 the old data.  Therefore, critical sections that begin after removal
36 do not matter; as soon as all previous critical sections have finished,
37 there cannot be any readers who hold references to the data structure,
38 and these can now be safely reclaimed (e.g., freed or unref'ed).
40 Here is a picture::
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.
54 Note how thread 3 is still executing its critical section when thread 2
55 starts reclaiming data.  This is possible, because the old version of the
56 data structure was not accessible at the time thread 3 began executing
57 that critical section.
60 RCU API
61 -------
63 The core RCU API is small:
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.
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.
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.
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``.
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.
91         The ``foo`` struct needs to have an ``rcu_head`` structure added,
92         perhaps as follows::
94             struct foo {
95                 struct rcu_head rcu;
96                 int a;
97                 char b;
98                 long c;
99             };
101         so that the reclaimer function can fetch the ``struct foo`` address
102         and free it::
104             call_rcu1(&foo.rcu, foo_reclaim);
106             void foo_reclaim(struct rcu_head *rp)
107             {
108                 struct foo *fp = container_of(rp, struct foo, rcu);
109                 g_free(fp);
110             }
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.
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``.
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::
125             g_free_rcu(&foo, rcu);
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.
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.
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.
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.
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.
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.
164 The following APIs must be used before RCU is used in a thread:
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.
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.
177 Note that these APIs are relatively heavyweight, and should **not** be
178 nested.
180 Convenience macros
181 ------------------
183 Two macros are provided that automatically release the read lock at the
184 end of the scope.
186 ``RCU_READ_LOCK_GUARD()``
187          Takes the lock and will release it at the end of the block it's
188          used in.
190 ``WITH_RCU_READ_LOCK_GUARD()  { code }``
191          Is used at the head of a block to protect the code within the block.
193 Note that a ``goto`` out of the guarded block will also drop the lock.
195 Differences with Linux
196 ----------------------
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.
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.
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``.
212 RCU Patterns
213 ------------
215 Many patterns using read-writer locks translate directly to RCU, with
216 the advantages of higher scalability and deadlock immunity.
218 In 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
220 sound like a very strict restriction, however:
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
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.
230 Here are some frequently-used RCU idioms that are worth noting.
233 RCU list processing
234 ^^^^^^^^^^^^^^^^^^^
236 TBD (not yet used in QEMU)
239 RCU reference counting
240 ^^^^^^^^^^^^^^^^^^^^^^
242 Because grace periods are not allowed to complete while there is an RCU
243 read-side critical section in progress, the RCU read-side primitives
244 may be used as a restricted reference-counting mechanism.  For example,
245 consider the following code fragment::
247     rcu_read_lock();
248     p = qatomic_rcu_read(&foo);
249     /* do something with p. */
250     rcu_read_unlock();
252 The RCU read-side critical section ensures that the value of ``p`` remains
253 valid until after the ``rcu_read_unlock()``.  In some sense, it is acquiring
254 a reference to ``p`` that is later released when the critical section ends.
255 The write side looks simply like this (with appropriate locking)::
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);
264 If the processing cannot be done purely within the critical section, it
265 is possible to combine this idiom with a "real" reference count::
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);
274 The write side can be like this::
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);
283 or with ``call_rcu``::
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);
291 In both cases, the write side only performs removal.  Reclamation
292 happens when the last reference to a ``foo`` object is dropped.
293 Using ``synchronize_rcu()`` is undesirably expensive, because the
294 last reference may be dropped on the read side.  Hence you can
295 use ``call_rcu()`` instead::
297      foo_unref(struct foo *p) {
298         if (qatomic_fetch_dec(&p->refcount) == 1) {
299             call_rcu(foo_destroy, p, rcu);
300         }
301     }
304 Note that the same idioms would be possible with reader/writer
305 locks::
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);
314     ------------------------------------------------------------------
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);
325 ``foo_unref`` could use a mechanism such as bottom halves to move deallocation
326 out of the write-side critical section.
329 RCU resizable arrays
330 ^^^^^^^^^^^^^^^^^^^^
332 Resizable arrays can be used with RCU.  The expensive RCU synchronization
333 (or ``call_rcu``) only needs to take place when the array is resized.
334 The two items to take care of are:
336 - ensuring that the old version of the array is available between removal
337   and reclamation;
339 - avoiding mismatches in the read side between the array data and the
340   array size.
342 The first problem is avoided simply by not using ``realloc``.  Instead,
343 each resize will allocate a new array and copy the old data into it.
344 The second problem would arise if the size and the data pointers were
345 two members of a larger struct::
347     struct mystuff {
348         ...
349         int data_size;
350         int data_alloc;
351         T   *data;
352         ...
353     };
355 Instead, we store the size of the array with the array itself::
357     struct arr {
358         int size;
359         int alloc;
360         T   data[];
361     };
362     struct arr *global_array;
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;
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));
381             /* Removal phase.  */
382             old_array = global_array;
383             qatomic_rcu_set(&global_array, new_array);
384             synchronize_rcu();
386             /* Reclamation phase.  */
387             free(old_array);
388         }
391 References
392 ----------
394 * The `Linux kernel RCU documentation <https://docs.kernel.org/RCU/>`__