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