요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
1
=================================
2
A Tour Through RCU's Requirements
3
=================================
5
Copyright IBM Corporation, 2015
7
Author: Paul E. McKenney
9
The initial version of this document appeared in the
10
`LWN <https://lwn.net/>`_ on those articles:
11
`part 1 <https://lwn.net/Articles/652156/>`_,
12
`part 2 <https://lwn.net/Articles/652677/>`_, and
13
`part 3 <https://lwn.net/Articles/653326/>`_.
15
Introduction
16
------------
18
Read-copy update (RCU) is a synchronization mechanism that is often used
19
as a replacement for reader-writer locking. RCU is unusual in that
20
updaters do not block readers, which means that RCU's read-side
21
primitives can be exceedingly fast and scalable. In addition, updaters
22
can make useful forward progress concurrently with readers. However, all
23
this concurrency between RCU readers and updaters does raise the
24
question of exactly what RCU readers are doing, which in turn raises the
25
question of exactly what RCU's requirements are.
27
This document therefore summarizes RCU's requirements, and can be
28
thought of as an informal, high-level specification for RCU. It is
29
important to understand that RCU's specification is primarily empirical
30
in nature; in fact, I learned about many of these requirements the hard
31
way. This situation might cause some consternation, however, not only
32
has this learning process been a lot of fun, but it has also been a
33
great privilege to work with so many people willing to apply
34
technologies in interesting new ways.
36
All that aside, here are the categories of currently known RCU
37
requirements:
39
#. `Fundamental Requirements`_
40
#. `Fundamental Non-Requirements`_
41
#. `Parallelism Facts of Life`_
42
#. `Quality-of-Implementation Requirements`_
43
#. `Linux Kernel Complications`_
44
#. `Software-Engineering Requirements`_
45
#. `Other RCU Flavors`_
46
#. `Possible Future Changes`_
48
This is followed by a summary_, however, the answers to
49
each quick quiz immediately follows the quiz. Select the big white space
50
with your mouse to see the answer.
52
Fundamental Requirements
53
------------------------
55
RCU's fundamental requirements are the closest thing RCU has to hard
56
mathematical requirements. These are:
58
#. `Grace-Period Guarantee`_
59
#. `Publish/Subscribe Guarantee`_
60
#. `Memory-Barrier Guarantees`_
61
#. `RCU Primitives Guaranteed to Execute Unconditionally`_
62
#. `Guaranteed Read-to-Write Upgrade`_
64
Grace-Period Guarantee
65
~~~~~~~~~~~~~~~~~~~~~~
67
RCU's grace-period guarantee is unusual in being premeditated: Jack
68
Slingwine and I had this guarantee firmly in mind when we started work
69
on RCU (then called “rclock”) in the early 1990s. That said, the past
70
two decades of experience with RCU have produced a much more detailed
71
understanding of this guarantee.
73
RCU's grace-period guarantee allows updaters to wait for the completion
74
of all pre-existing RCU read-side critical sections. An RCU read-side
75
critical section begins with the marker rcu_read_lock() and ends
76
with the marker rcu_read_unlock(). These markers may be nested, and
77
RCU treats a nested set as one big RCU read-side critical section.
78
Production-quality implementations of rcu_read_lock() and
79
rcu_read_unlock() are extremely lightweight, and in fact have
80
exactly zero overhead in Linux kernels built for production use with
81
``CONFIG_PREEMPTION=n``.
83
This guarantee allows ordering to be enforced with extremely low
84
overhead to readers, for example:
86
::
88
1 int x, y;
89
2
90
3 void thread0(void)
91
4 {
92
5 rcu_read_lock();
93
6 r1 = READ_ONCE(x);
94
7 r2 = READ_ONCE(y);
95
8 rcu_read_unlock();
96
9 }
97
10
98
11 void thread1(void)
99
12 {
100
13 WRITE_ONCE(x, 1);
101
14 synchronize_rcu();
102
15 WRITE_ONCE(y, 1);
103
16 }
105
Because the synchronize_rcu() on line 14 waits for all pre-existing
106
readers, any instance of thread0() that loads a value of zero from
107
``x`` must complete before thread1() stores to ``y``, so that
108
instance must also load a value of zero from ``y``. Similarly, any
109
instance of thread0() that loads a value of one from ``y`` must have
110
started after the synchronize_rcu() started, and must therefore also
111
load a value of one from ``x``. Therefore, the outcome:
113
::
115
(r1 == 0 && r2 == 1)
117
cannot happen.
119
+-----------------------------------------------------------------------+
120
| **Quick Quiz**: |
121
+-----------------------------------------------------------------------+
122
| Wait a minute! You said that updaters can make useful forward |
123
| progress concurrently with readers, but pre-existing readers will |
124
| block synchronize_rcu()!!! |
125
| Just who are you trying to fool??? |
126
+-----------------------------------------------------------------------+
127
| **Answer**: |
128
+-----------------------------------------------------------------------+
129
| First, if updaters do not wish to be blocked by readers, they can use |
130
| call_rcu() or kfree_rcu(), which will be discussed later. |
131
| Second, even when using synchronize_rcu(), the other update-side |
132
| code does run concurrently with readers, whether pre-existing or not. |
133
+-----------------------------------------------------------------------+
135
This scenario resembles one of the first uses of RCU in
136
`DYNIX/ptx <https://en.wikipedia.org/wiki/DYNIX>`__, which managed a
137
distributed lock manager's transition into a state suitable for handling
138
recovery from node failure, more or less as follows:
140
::
142
1 #define STATE_NORMAL 0
143
2 #define STATE_WANT_RECOVERY 1
144
3 #define STATE_RECOVERING 2
145
4 #define STATE_WANT_NORMAL 3
146
5
147
6 int state = STATE_NORMAL;
148
7
149
8 void do_something_dlm(void)
150
9 {
151
10 int state_snap;
152
11
153
12 rcu_read_lock();
154
13 state_snap = READ_ONCE(state);
155
14 if (state_snap == STATE_NORMAL)
156
15 do_something();
157
16 else
158
17 do_something_carefully();
159
18 rcu_read_unlock();
160
19 }
161
20
162
21 void start_recovery(void)
163
22 {
164
23 WRITE_ONCE(state, STATE_WANT_RECOVERY);
165
24 synchronize_rcu();
166
25 WRITE_ONCE(state, STATE_RECOVERING);
167
26 recovery();
168
27 WRITE_ONCE(state, STATE_WANT_NORMAL);
169
28 synchronize_rcu();
170
29 WRITE_ONCE(state, STATE_NORMAL);
171
30 }
173
The RCU read-side critical section in do_something_dlm() works with
174
the synchronize_rcu() in start_recovery() to guarantee that
175
do_something() never runs concurrently with recovery(), but with
176
little or no synchronization overhead in do_something_dlm().
178
+-----------------------------------------------------------------------+
179
| **Quick Quiz**: |
180
+-----------------------------------------------------------------------+
181
| Why is the synchronize_rcu() on line 28 needed? |
182
+-----------------------------------------------------------------------+
183
| **Answer**: |
184
+-----------------------------------------------------------------------+
185
| Without that extra grace period, memory reordering could result in |
186
| do_something_dlm() executing do_something() concurrently with |
187
| the last bits of recovery(). |
188
+-----------------------------------------------------------------------+
190
In order to avoid fatal problems such as deadlocks, an RCU read-side
191
critical section must not contain calls to synchronize_rcu().
192
Similarly, an RCU read-side critical section must not contain anything
193
that waits, directly or indirectly, on completion of an invocation of
194
synchronize_rcu().
196
Although RCU's grace-period guarantee is useful in and of itself, with
197
`quite a few use cases <https://lwn.net/Articles/573497/>`__, it would
198
be good to be able to use RCU to coordinate read-side access to linked
199
data structures. For this, the grace-period guarantee is not sufficient,
200
as can be seen in function add_gp_buggy() below. We will look at the
201
reader's code later, but in the meantime, just think of the reader as
202
locklessly picking up the ``gp`` pointer, and, if the value loaded is
203
non-\ ``NULL``, locklessly accessing the ``->a`` and ``->b`` fields.
205
::
207
1 bool add_gp_buggy(int a, int b)
208
2 {
209
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
210
4 if (!p)
211
5 return -ENOMEM;
212
6 spin_lock(&gp_lock);
213
7 if (rcu_access_pointer(gp)) {
214
8 spin_unlock(&gp_lock);
215
9 return false;
216
10 }
217
11 p->a = a;
218
12 p->b = a;
219
13 gp = p; /* ORDERING BUG */
220
14 spin_unlock(&gp_lock);
221
15 return true;
222
16 }
224
The problem is that both the compiler and weakly ordered CPUs are within
225
their rights to reorder this code as follows:
227
::
229
1 bool add_gp_buggy_optimized(int a, int b)
230
2 {
231
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
232
4 if (!p)
233
5 return -ENOMEM;
234
6 spin_lock(&gp_lock);
235
7 if (rcu_access_pointer(gp)) {
236
8 spin_unlock(&gp_lock);
237
9 return false;
238
10 }
239
11 gp = p; /* ORDERING BUG */
240
12 p->a = a;
241
13 p->b = a;
242
14 spin_unlock(&gp_lock);
243
15 return true;
244
16 }
246
If an RCU reader fetches ``gp`` just after ``add_gp_buggy_optimized``
247
executes line 11, it will see garbage in the ``->a`` and ``->b`` fields.
248
And this is but one of many ways in which compiler and hardware
249
optimizations could cause trouble. Therefore, we clearly need some way
250
to prevent the compiler and the CPU from reordering in this manner,
251
which brings us to the publish-subscribe guarantee discussed in the next
252
section.
254
Publish/Subscribe Guarantee
255
~~~~~~~~~~~~~~~~~~~~~~~~~~~
257
RCU's publish-subscribe guarantee allows data to be inserted into a
258
linked data structure without disrupting RCU readers. The updater uses
259
rcu_assign_pointer() to insert the new data, and readers use
260
rcu_dereference() to access data, whether new or old. The following
261
shows an example of insertion:
263
::
265
1 bool add_gp(int a, int b)
266
2 {
267
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
268
4 if (!p)
269
5 return -ENOMEM;
270
6 spin_lock(&gp_lock);
271
7 if (rcu_access_pointer(gp)) {
272
8 spin_unlock(&gp_lock);
273
9 return false;
274
10 }
275
11 p->a = a;
276
12 p->b = a;
277
13 rcu_assign_pointer(gp, p);
278
14 spin_unlock(&gp_lock);
279
15 return true;
280
16 }
282
The rcu_assign_pointer() on line 13 is conceptually equivalent to a
283
simple assignment statement, but also guarantees that its assignment
284
will happen after the two assignments in lines 11 and 12, similar to the
285
C11 ``memory_order_release`` store operation. It also prevents any
286
number of “interesting” compiler optimizations, for example, the use of
287
``gp`` as a scratch location immediately preceding the assignment.
289
+-----------------------------------------------------------------------+
290
| **Quick Quiz**: |
291
+-----------------------------------------------------------------------+
292
| But rcu_assign_pointer() does nothing to prevent the two |
293
| assignments to ``p->a`` and ``p->b`` from being reordered. Can't that |
294
| also cause problems? |
295
+-----------------------------------------------------------------------+
296
| **Answer**: |
297
+-----------------------------------------------------------------------+
298
| No, it cannot. The readers cannot see either of these two fields |
299
| until the assignment to ``gp``, by which time both fields are fully |
300
| initialized. So reordering the assignments to ``p->a`` and ``p->b`` |
301
| cannot possibly cause any problems. |
302
+-----------------------------------------------------------------------+
304
It is tempting to assume that the reader need not do anything special to
305
control its accesses to the RCU-protected data, as shown in
306
do_something_gp_buggy() below:
308
::
310
1 bool do_something_gp_buggy(void)
311
2 {
312
3 rcu_read_lock();
313
4 p = gp; /* OPTIMIZATIONS GALORE!!! */
314
5 if (p) {
315
6 do_something(p->a, p->b);
316
7 rcu_read_unlock();
317
8 return true;
318
9 }
319
10 rcu_read_unlock();
320
11 return false;
321
12 }
323
However, this temptation must be resisted because there are a
324
surprisingly large number of ways that the compiler (or weak ordering
325
CPUs like the DEC Alpha) can trip this code up. For but one example, if
326
the compiler were short of registers, it might choose to refetch from
327
``gp`` rather than keeping a separate copy in ``p`` as follows:
329
::
331
1 bool do_something_gp_buggy_optimized(void)
332
2 {
333
3 rcu_read_lock();
334
4 if (gp) { /* OPTIMIZATIONS GALORE!!! */
335
5 do_something(gp->a, gp->b);
336
6 rcu_read_unlock();
337
7 return true;
338
8 }
339
9 rcu_read_unlock();
340
10 return false;
341
11 }
343
If this function ran concurrently with a series of updates that replaced
344
the current structure with a new one, the fetches of ``gp->a`` and
345
``gp->b`` might well come from two different structures, which could
346
cause serious confusion. To prevent this (and much else besides),
347
do_something_gp() uses rcu_dereference() to fetch from ``gp``:
349
::
351
1 bool do_something_gp(void)
352
2 {
353
3 rcu_read_lock();
354
4 p = rcu_dereference(gp);
355
5 if (p) {
356
6 do_something(p->a, p->b);
357
7 rcu_read_unlock();
358
8 return true;
359
9 }
360
10 rcu_read_unlock();
361
11 return false;
362
12 }
364
The rcu_dereference() uses volatile casts and (for DEC Alpha) memory
365
barriers in the Linux kernel. Should a |high-quality implementation of
366
C11 memory_order_consume [PDF]|_
367
ever appear, then rcu_dereference() could be implemented as a
368
``memory_order_consume`` load. Regardless of the exact implementation, a
369
pointer fetched by rcu_dereference() may not be used outside of the
370
outermost RCU read-side critical section containing that
371
rcu_dereference(), unless protection of the corresponding data
372
element has been passed from RCU to some other synchronization
373
mechanism, most commonly locking or reference counting
374
(see ../../rcuref.rst).
376
.. |high-quality implementation of C11 memory_order_consume [PDF]| replace:: high-quality implementation of C11 ``memory_order_consume`` [PDF]
377
.. _high-quality implementation of C11 memory_order_consume [PDF]: http://www.rdrop.com/users/paulmck/RCU/consume.2015.07.13a.pdf
379
In short, updaters use rcu_assign_pointer() and readers use
380
rcu_dereference(), and these two RCU API elements work together to
381
ensure that readers have a consistent view of newly added data elements.
383
Of course, it is also necessary to remove elements from RCU-protected
384
data structures, for example, using the following process:
386
#. Remove the data element from the enclosing structure.
387
#. Wait for all pre-existing RCU read-side critical sections to complete
388
(because only pre-existing readers can possibly have a reference to
389
the newly removed data element).
390
#. At this point, only the updater has a reference to the newly removed
391
data element, so it can safely reclaim the data element, for example,
392
by passing it to kfree().
394
This process is implemented by remove_gp_synchronous():
396
::
398
1 bool remove_gp_synchronous(void)
399
2 {
400
3 struct foo *p;
401
4
402
5 spin_lock(&gp_lock);
403
6 p = rcu_access_pointer(gp);
404
7 if (!p) {
405
8 spin_unlock(&gp_lock);
406
9 return false;
407
10 }
408
11 rcu_assign_pointer(gp, NULL);
409
12 spin_unlock(&gp_lock);
410
13 synchronize_rcu();
411
14 kfree(p);
412
15 return true;
413
16 }
415
This function is straightforward, with line 13 waiting for a grace
416
period before line 14 frees the old data element. This waiting ensures
417
that readers will reach line 7 of do_something_gp() before the data
418
element referenced by ``p`` is freed. The rcu_access_pointer() on
419
line 6 is similar to rcu_dereference(), except that:
421
#. The value returned by rcu_access_pointer() cannot be
422
dereferenced. If you want to access the value pointed to as well as
423
the pointer itself, use rcu_dereference() instead of
424
rcu_access_pointer().
425
#. The call to rcu_access_pointer() need not be protected. In
426
contrast, rcu_dereference() must either be within an RCU
427
read-side critical section or in a code segment where the pointer
428
cannot change, for example, in code protected by the corresponding
429
update-side lock.
431
+-----------------------------------------------------------------------+
432
| **Quick Quiz**: |
433
+-----------------------------------------------------------------------+
434
| Without the rcu_dereference() or the rcu_access_pointer(), |
435
| what destructive optimizations might the compiler make use of? |
436
+-----------------------------------------------------------------------+
437
| **Answer**: |
438
+-----------------------------------------------------------------------+
439
| Let's start with what happens to do_something_gp() if it fails to |
440
| use rcu_dereference(). It could reuse a value formerly fetched |
441
| from this same pointer. It could also fetch the pointer from ``gp`` |
442
| in a byte-at-a-time manner, resulting in *load tearing*, in turn |
443
| resulting a bytewise mash-up of two distinct pointer values. It might |
444
| even use value-speculation optimizations, where it makes a wrong |
445
| guess, but by the time it gets around to checking the value, an |
446
| update has changed the pointer to match the wrong guess. Too bad |
447
| about any dereferences that returned pre-initialization garbage in |
448
| the meantime! |
449
| For remove_gp_synchronous(), as long as all modifications to |
450
| ``gp`` are carried out while holding ``gp_lock``, the above |
451
| optimizations are harmless. However, ``sparse`` will complain if you |
452
| define ``gp`` with ``__rcu`` and then access it without using either |
453
| rcu_access_pointer() or rcu_dereference(). |
454
+-----------------------------------------------------------------------+
456
In short, RCU's publish-subscribe guarantee is provided by the
457
combination of rcu_assign_pointer() and rcu_dereference(). This
458
guarantee allows data elements to be safely added to RCU-protected
459
linked data structures without disrupting RCU readers. This guarantee
460
can be used in combination with the grace-period guarantee to also allow
461
data elements to be removed from RCU-protected linked data structures,
462
again without disrupting RCU readers.
464
This guarantee was only partially premeditated. DYNIX/ptx used an
465
explicit memory barrier for publication, but had nothing resembling
466
rcu_dereference() for subscription, nor did it have anything
467
resembling the dependency-ordering barrier that was later subsumed
468
into rcu_dereference() and later still into READ_ONCE(). The
469
need for these operations made itself known quite suddenly at a
470
late-1990s meeting with the DEC Alpha architects, back in the days when
471
DEC was still a free-standing company. It took the Alpha architects a
472
good hour to convince me that any sort of barrier would ever be needed,
473
and it then took me a good *two* hours to convince them that their
474
documentation did not make this point clear. More recent work with the C
475
and C++ standards committees have provided much education on tricks and
476
traps from the compiler. In short, compilers were much less tricky in
477
the early 1990s, but in 2015, don't even think about omitting
478
rcu_dereference()!
480
Memory-Barrier Guarantees
481
~~~~~~~~~~~~~~~~~~~~~~~~~
483
The previous section's simple linked-data-structure scenario clearly
484
demonstrates the need for RCU's stringent memory-ordering guarantees on
485
systems with more than one CPU:
487
#. Each CPU that has an RCU read-side critical section that begins
488
before synchronize_rcu() starts is guaranteed to execute a full
489
memory barrier between the time that the RCU read-side critical
490
section ends and the time that synchronize_rcu() returns. Without
491
this guarantee, a pre-existing RCU read-side critical section might
492
hold a reference to the newly removed ``struct foo`` after the
493
kfree() on line 14 of remove_gp_synchronous().
494
#. Each CPU that has an RCU read-side critical section that ends after
495
synchronize_rcu() returns is guaranteed to execute a full memory
496
barrier between the time that synchronize_rcu() begins and the
497
time that the RCU read-side critical section begins. Without this
498
guarantee, a later RCU read-side critical section running after the
499
kfree() on line 14 of remove_gp_synchronous() might later run
500
do_something_gp() and find the newly deleted ``struct foo``.
501
#. If the task invoking synchronize_rcu() remains on a given CPU,
502
then that CPU is guaranteed to execute a full memory barrier sometime
503
during the execution of synchronize_rcu(). This guarantee ensures
504
that the kfree() on line 14 of remove_gp_synchronous() really
505
does execute after the removal on line 11.
506
#. If the task invoking synchronize_rcu() migrates among a group of
507
CPUs during that invocation, then each of the CPUs in that group is
508
guaranteed to execute a full memory barrier sometime during the
509
execution of synchronize_rcu(). This guarantee also ensures that
510
the kfree() on line 14 of remove_gp_synchronous() really does
511
execute after the removal on line 11, but also in the case where the
512
thread executing the synchronize_rcu() migrates in the meantime.
514
+-----------------------------------------------------------------------+
515
| **Quick Quiz**: |
516
+-----------------------------------------------------------------------+
517
| Given that multiple CPUs can start RCU read-side critical sections at |
518
| any time without any ordering whatsoever, how can RCU possibly tell |
519
| whether or not a given RCU read-side critical section starts before a |
520
| given instance of synchronize_rcu()? |
521
+-----------------------------------------------------------------------+
522
| **Answer**: |
523
+-----------------------------------------------------------------------+
524
| If RCU cannot tell whether or not a given RCU read-side critical |
525
| section starts before a given instance of synchronize_rcu(), then |
526
| it must assume that the RCU read-side critical section started first. |
527
| In other words, a given instance of synchronize_rcu() can avoid |
528
| waiting on a given RCU read-side critical section only if it can |
529
| prove that synchronize_rcu() started first. |
530
| A related question is “When rcu_read_lock() doesn't generate any |
531
| code, why does it matter how it relates to a grace period?” The |
532
| answer is that it is not the relationship of rcu_read_lock() |
533
| itself that is important, but rather the relationship of the code |
534
| within the enclosed RCU read-side critical section to the code |
535
| preceding and following the grace period. If we take this viewpoint, |
536
| then a given RCU read-side critical section begins before a given |
537
| grace period when some access preceding the grace period observes the |
538
| effect of some access within the critical section, in which case none |
539
| of the accesses within the critical section may observe the effects |
540
| of any access following the grace period. |
541
| |
542
| As of late 2016, mathematical models of RCU take this viewpoint, for |
543
| example, see slides 62 and 63 of the `2016 LinuxCon |
544
| EU <http://www2.rdrop.com/users/paulmck/scalability/paper/LinuxMM.201 |
545
| 6.10.04c.LCE.pdf>`__ |
546
| presentation. |
547
+-----------------------------------------------------------------------+
549
+-----------------------------------------------------------------------+
550
| **Quick Quiz**: |
551
+-----------------------------------------------------------------------+
552
| The first and second guarantees require unbelievably strict ordering! |
553
| Are all these memory barriers *really* required? |
554
+-----------------------------------------------------------------------+
555
| **Answer**: |
556
+-----------------------------------------------------------------------+
557
| Yes, they really are required. To see why the first guarantee is |
558
| required, consider the following sequence of events: |
559
| |
560
| #. CPU 1: rcu_read_lock() |
561
| #. CPU 1: ``q = rcu_dereference(gp); /* Very likely to return p. */`` |
562
| #. CPU 0: ``list_del_rcu(p);`` |
563
| #. CPU 0: synchronize_rcu() starts. |
564
| #. CPU 1: ``do_something_with(q->a);`` |
565
| ``/* No smp_mb(), so might happen after kfree(). */`` |
566
| #. CPU 1: rcu_read_unlock() |
567
| #. CPU 0: synchronize_rcu() returns. |
568
| #. CPU 0: ``kfree(p);`` |
569
| |
570
| Therefore, there absolutely must be a full memory barrier between the |
571
| end of the RCU read-side critical section and the end of the grace |
572
| period. |
573
| |
574
| The sequence of events demonstrating the necessity of the second rule |
575
| is roughly similar: |
576
| |
577
| #. CPU 0: ``list_del_rcu(p);`` |
578
| #. CPU 0: synchronize_rcu() starts. |
579
| #. CPU 1: rcu_read_lock() |
580
| #. CPU 1: ``q = rcu_dereference(gp);`` |
581
| ``/* Might return p if no memory barrier. */`` |
582
| #. CPU 0: synchronize_rcu() returns. |
583
| #. CPU 0: ``kfree(p);`` |
584
| #. CPU 1: ``do_something_with(q->a); /* Boom!!! */`` |
585
| #. CPU 1: rcu_read_unlock() |
586
| |
587
| And similarly, without a memory barrier between the beginning of the |
588
| grace period and the beginning of the RCU read-side critical section, |
589
| CPU 1 might end up accessing the freelist. |
590
| |
591
| The “as if” rule of course applies, so that any implementation that |
592
| acts as if the appropriate memory barriers were in place is a correct |
593
| implementation. That said, it is much easier to fool yourself into |
594
| believing that you have adhered to the as-if rule than it is to |
595
| actually adhere to it! |
596
+-----------------------------------------------------------------------+
598
+-----------------------------------------------------------------------+
599
| **Quick Quiz**: |
600
+-----------------------------------------------------------------------+
601
| You claim that rcu_read_lock() and rcu_read_unlock() generate |
602
| absolutely no code in some kernel builds. This means that the |
603
| compiler might arbitrarily rearrange consecutive RCU read-side |
604
| critical sections. Given such rearrangement, if a given RCU read-side |
605
| critical section is done, how can you be sure that all prior RCU |
606
| read-side critical sections are done? Won't the compiler |
607
| rearrangements make that impossible to determine? |
608
+-----------------------------------------------------------------------+
609
| **Answer**: |
610
+-----------------------------------------------------------------------+
611
| In cases where rcu_read_lock() and rcu_read_unlock() generate |
612
| absolutely no code, RCU infers quiescent states only at special |
613
| locations, for example, within the scheduler. Because calls to |
614
| schedule() had better prevent calling-code accesses to shared |
615
| variables from being rearranged across the call to schedule(), if |
616
| RCU detects the end of a given RCU read-side critical section, it |
617
| will necessarily detect the end of all prior RCU read-side critical |
618
| sections, no matter how aggressively the compiler scrambles the code. |
619
| Again, this all assumes that the compiler cannot scramble code across |
620
| calls to the scheduler, out of interrupt handlers, into the idle |
621
| loop, into user-mode code, and so on. But if your kernel build allows |
622
| that sort of scrambling, you have broken far more than just RCU! |
623
+-----------------------------------------------------------------------+
625
Note that these memory-barrier requirements do not replace the
626
fundamental RCU requirement that a grace period wait for all
627
pre-existing readers. On the contrary, the memory barriers called out in
628
this section must operate in such a way as to *enforce* this fundamental
629
requirement. Of course, different implementations enforce this
630
requirement in different ways, but enforce it they must.
632
RCU Primitives Guaranteed to Execute Unconditionally
633
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
635
The common-case RCU primitives are unconditional. They are invoked, they
636
do their job, and they return, with no possibility of error, and no need
637
to retry. This is a key RCU design philosophy.
639
However, this philosophy is pragmatic rather than pigheaded. If someone
640
comes up with a good justification for a particular conditional RCU
641
primitive, it might well be implemented and added. After all, this
642
guarantee was reverse-engineered, not premeditated. The unconditional
643
nature of the RCU primitives was initially an accident of
644
implementation, and later experience with synchronization primitives
645
with conditional primitives caused me to elevate this accident to a
646
guarantee. Therefore, the justification for adding a conditional
647
primitive to RCU would need to be based on detailed and compelling use
648
cases.
650
Guaranteed Read-to-Write Upgrade
651
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
653
As far as RCU is concerned, it is always possible to carry out an update
654
within an RCU read-side critical section. For example, that RCU
655
read-side critical section might search for a given data element, and
656
then might acquire the update-side spinlock in order to update that
657
element, all while remaining in that RCU read-side critical section. Of
658
course, it is necessary to exit the RCU read-side critical section
659
before invoking synchronize_rcu(), however, this inconvenience can
660
be avoided through use of the call_rcu() and kfree_rcu() API
661
members described later in this document.
663
+-----------------------------------------------------------------------+
664
| **Quick Quiz**: |
665
+-----------------------------------------------------------------------+
666
| But how does the upgrade-to-write operation exclude other readers? |
667
+-----------------------------------------------------------------------+
668
| **Answer**: |
669
+-----------------------------------------------------------------------+
670
| It doesn't, just like normal RCU updates, which also do not exclude |
671
| RCU readers. |
672
+-----------------------------------------------------------------------+
674
This guarantee allows lookup code to be shared between read-side and
675
update-side code, and was premeditated, appearing in the earliest
676
DYNIX/ptx RCU documentation.
678
Fundamental Non-Requirements
679
----------------------------
681
RCU provides extremely lightweight readers, and its read-side
682
guarantees, though quite useful, are correspondingly lightweight. It is
683
therefore all too easy to assume that RCU is guaranteeing more than it
684
really is. Of course, the list of things that RCU does not guarantee is
685
infinitely long, however, the following sections list a few
686
non-guarantees that have caused confusion. Except where otherwise noted,
687
these non-guarantees were premeditated.
689
#. `Readers Impose Minimal Ordering`_
690
#. `Readers Do Not Exclude Updaters`_
691
#. `Updaters Only Wait For Old Readers`_
692
#. `Grace Periods Don't Partition Read-Side Critical Sections`_
693
#. `Read-Side Critical Sections Don't Partition Grace Periods`_
695
Readers Impose Minimal Ordering
696
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
698
Reader-side markers such as rcu_read_lock() and
699
rcu_read_unlock() provide absolutely no ordering guarantees except
700
through their interaction with the grace-period APIs such as
701
synchronize_rcu(). To see this, consider the following pair of
702
threads:
704
::
706
1 void thread0(void)
707
2 {
708
3 rcu_read_lock();
709
4 WRITE_ONCE(x, 1);
710
5 rcu_read_unlock();
711
6 rcu_read_lock();
712
7 WRITE_ONCE(y, 1);
713
8 rcu_read_unlock();
714
9 }
715
10
716
11 void thread1(void)
717
12 {
718
13 rcu_read_lock();
719
14 r1 = READ_ONCE(y);
720
15 rcu_read_unlock();
721
16 rcu_read_lock();
722
17 r2 = READ_ONCE(x);
723
18 rcu_read_unlock();
724
19 }
726
After thread0() and thread1() execute concurrently, it is quite
727
possible to have
729
::
731
(r1 == 1 && r2 == 0)
733
(that is, ``y`` appears to have been assigned before ``x``), which would
734
not be possible if rcu_read_lock() and rcu_read_unlock() had
735
much in the way of ordering properties. But they do not, so the CPU is
736
within its rights to do significant reordering. This is by design: Any
737
significant ordering constraints would slow down these fast-path APIs.
739
+-----------------------------------------------------------------------+
740
| **Quick Quiz**: |
741
+-----------------------------------------------------------------------+
742
| Can't the compiler also reorder this code? |
743
+-----------------------------------------------------------------------+
744
| **Answer**: |
745
+-----------------------------------------------------------------------+
746
| No, the volatile casts in READ_ONCE() and WRITE_ONCE() |
747
| prevent the compiler from reordering in this particular case. |
748
+-----------------------------------------------------------------------+
750
Readers Do Not Exclude Updaters
751
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
753
Neither rcu_read_lock() nor rcu_read_unlock() exclude updates.
754
All they do is to prevent grace periods from ending. The following
755
example illustrates this:
757
::
759
1 void thread0(void)
760
2 {
761
3 rcu_read_lock();
762
4 r1 = READ_ONCE(y);
763
5 if (r1) {
764
6 do_something_with_nonzero_x();
765
7 r2 = READ_ONCE(x);
766
8 WARN_ON(!r2); /* BUG!!! */
767
9 }
768
10 rcu_read_unlock();
769
11 }
770
12
771
13 void thread1(void)
772
14 {
773
15 spin_lock(&my_lock);
774
16 WRITE_ONCE(x, 1);
775
17 WRITE_ONCE(y, 1);
776
18 spin_unlock(&my_lock);
777
19 }
779
If the thread0() function's rcu_read_lock() excluded the
780
thread1() function's update, the WARN_ON() could never fire. But
781
the fact is that rcu_read_lock() does not exclude much of anything
782
aside from subsequent grace periods, of which thread1() has none, so
783
the WARN_ON() can and does fire.
785
Updaters Only Wait For Old Readers
786
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
788
It might be tempting to assume that after synchronize_rcu()
789
completes, there are no readers executing. This temptation must be
790
avoided because new readers can start immediately after
791
synchronize_rcu() starts, and synchronize_rcu() is under no
792
obligation to wait for these new readers.
794
+-----------------------------------------------------------------------+
795
| **Quick Quiz**: |
796
+-----------------------------------------------------------------------+
797
| Suppose that synchronize_rcu() did wait until *all* readers had |
798
| completed instead of waiting only on pre-existing readers. For how |
799
| long would the updater be able to rely on there being no readers? |
800
+-----------------------------------------------------------------------+
801
| **Answer**: |
802
+-----------------------------------------------------------------------+
803
| For no time at all. Even if synchronize_rcu() were to wait until |
804
| all readers had completed, a new reader might start immediately after |
805
| synchronize_rcu() completed. Therefore, the code following |
806
| synchronize_rcu() can *never* rely on there being no readers. |
807
+-----------------------------------------------------------------------+
809
Grace Periods Don't Partition Read-Side Critical Sections
810
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
812
It is tempting to assume that if any part of one RCU read-side critical
813
section precedes a given grace period, and if any part of another RCU
814
read-side critical section follows that same grace period, then all of
815
the first RCU read-side critical section must precede all of the second.
816
However, this just isn't the case: A single grace period does not
817
partition the set of RCU read-side critical sections. An example of this
818
situation can be illustrated as follows, where ``x``, ``y``, and ``z``
819
are initially all zero:
821
::
823
1 void thread0(void)
824
2 {
825
3 rcu_read_lock();
826
4 WRITE_ONCE(a, 1);
827
5 WRITE_ONCE(b, 1);
828
6 rcu_read_unlock();
829
7 }
830
8
831
9 void thread1(void)
832
10 {
833
11 r1 = READ_ONCE(a);
834
12 synchronize_rcu();
835
13 WRITE_ONCE(c, 1);
836
14 }
837
15
838
16 void thread2(void)
839
17 {
840
18 rcu_read_lock();
841
19 r2 = READ_ONCE(b);
842
20 r3 = READ_ONCE(c);
843
21 rcu_read_unlock();
844
22 }
846
It turns out that the outcome:
848
::
850
(r1 == 1 && r2 == 0 && r3 == 1)
852
is entirely possible. The following figure show how this can happen,
853
with each circled ``QS`` indicating the point at which RCU recorded a
854
*quiescent state* for each thread, that is, a state in which RCU knows
855
that the thread cannot be in the midst of an RCU read-side critical
856
section that started before the current grace period:
858
.. kernel-figure:: GPpartitionReaders1.svg
860
If it is necessary to partition RCU read-side critical sections in this
861
manner, it is necessary to use two grace periods, where the first grace
862
period is known to end before the second grace period starts:
864
::
866
1 void thread0(void)
867
2 {
868
3 rcu_read_lock();
869
4 WRITE_ONCE(a, 1);
870
5 WRITE_ONCE(b, 1);
871
6 rcu_read_unlock();
872
7 }
873
8
874
9 void thread1(void)
875
10 {
876
11 r1 = READ_ONCE(a);
877
12 synchronize_rcu();
878
13 WRITE_ONCE(c, 1);
879
14 }
880
15
881
16 void thread2(void)
882
17 {
883
18 r2 = READ_ONCE(c);
884
19 synchronize_rcu();
885
20 WRITE_ONCE(d, 1);
886
21 }
887
22
888
23 void thread3(void)
889
24 {
890
25 rcu_read_lock();
891
26 r3 = READ_ONCE(b);
892
27 r4 = READ_ONCE(d);
893
28 rcu_read_unlock();
894
29 }
896
Here, if ``(r1 == 1)``, then thread0()'s write to ``b`` must happen
897
before the end of thread1()'s grace period. If in addition
898
``(r4 == 1)``, then thread3()'s read from ``b`` must happen after
899
the beginning of thread2()'s grace period. If it is also the case
900
that ``(r2 == 1)``, then the end of thread1()'s grace period must
901
precede the beginning of thread2()'s grace period. This mean that
902
the two RCU read-side critical sections cannot overlap, guaranteeing
903
that ``(r3 == 1)``. As a result, the outcome:
905
::
907
(r1 == 1 && r2 == 1 && r3 == 0 && r4 == 1)
909
cannot happen.
911
This non-requirement was also non-premeditated, but became apparent when
912
studying RCU's interaction with memory ordering.
914
Read-Side Critical Sections Don't Partition Grace Periods
915
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
917
It is also tempting to assume that if an RCU read-side critical section
918
happens between a pair of grace periods, then those grace periods cannot
919
overlap. However, this temptation leads nowhere good, as can be
920
illustrated by the following, with all variables initially zero:
922
::
924
1 void thread0(void)
925
2 {
926
3 rcu_read_lock();
927
4 WRITE_ONCE(a, 1);
928
5 WRITE_ONCE(b, 1);
929
6 rcu_read_unlock();
930
7 }
931
8
932
9 void thread1(void)
933
10 {
934
11 r1 = READ_ONCE(a);
935
12 synchronize_rcu();
936
13 WRITE_ONCE(c, 1);
937
14 }
938
15
939
16 void thread2(void)
940
17 {
941
18 rcu_read_lock();
942
19 WRITE_ONCE(d, 1);
943
20 r2 = READ_ONCE(c);
944
21 rcu_read_unlock();
945
22 }
946
23
947
24 void thread3(void)
948
25 {
949
26 r3 = READ_ONCE(d);
950
27 synchronize_rcu();
951
28 WRITE_ONCE(e, 1);
952
29 }
953
30
954
31 void thread4(void)
955
32 {
956
33 rcu_read_lock();
957
34 r4 = READ_ONCE(b);
958
35 r5 = READ_ONCE(e);
959
36 rcu_read_unlock();
960
37 }
962
In this case, the outcome:
964
::
966
(r1 == 1 && r2 == 1 && r3 == 1 && r4 == 0 && r5 == 1)
968
is entirely possible, as illustrated below:
970
.. kernel-figure:: ReadersPartitionGP1.svg
972
Again, an RCU read-side critical section can overlap almost all of a
973
given grace period, just so long as it does not overlap the entire grace
974
period. As a result, an RCU read-side critical section cannot partition
975
a pair of RCU grace periods.
977
+-----------------------------------------------------------------------+
978
| **Quick Quiz**: |
979
+-----------------------------------------------------------------------+
980
| How long a sequence of grace periods, each separated by an RCU |
981
| read-side critical section, would be required to partition the RCU |
982
| read-side critical sections at the beginning and end of the chain? |
983
+-----------------------------------------------------------------------+
984
| **Answer**: |
985
+-----------------------------------------------------------------------+
986
| In theory, an infinite number. In practice, an unknown number that is |
987
| sensitive to both implementation details and timing considerations. |
988
| Therefore, even in practice, RCU users must abide by the theoretical |
989
| rather than the practical answer. |
990
+-----------------------------------------------------------------------+
992
Parallelism Facts of Life
993
-------------------------
995
These parallelism facts of life are by no means specific to RCU, but the
996
RCU implementation must abide by them. They therefore bear repeating:
998
#. Any CPU or task may be delayed at any time, and any attempts to avoid
999
these delays by disabling preemption, interrupts, or whatever are
1000
completely futile. This is most obvious in preemptible user-level
1001
environments and in virtualized environments (where a given guest
1002
OS's VCPUs can be preempted at any time by the underlying
1003
hypervisor), but can also happen in bare-metal environments due to
1004
ECC errors, NMIs, and other hardware events. Although a delay of more
1005
than about 20 seconds can result in splats, the RCU implementation is
1006
obligated to use algorithms that can tolerate extremely long delays,
1007
but where “extremely long” is not long enough to allow wrap-around
1008
when incrementing a 64-bit counter.
1009
#. Both the compiler and the CPU can reorder memory accesses. Where it
1010
matters, RCU must use compiler directives and memory-barrier
1011
instructions to preserve ordering.
1012
#. Conflicting writes to memory locations in any given cache line will
1013
result in expensive cache misses. Greater numbers of concurrent
1014
writes and more-frequent concurrent writes will result in more
1015
dramatic slowdowns. RCU is therefore obligated to use algorithms that
1016
have sufficient locality to avoid significant performance and
1017
scalability problems.
1018
#. As a rough rule of thumb, only one CPU's worth of processing may be
1019
carried out under the protection of any given exclusive lock. RCU
1020
must therefore use scalable locking designs.
1021
#. Counters are finite, especially on 32-bit systems. RCU's use of
1022
counters must therefore tolerate counter wrap, or be designed such
1023
that counter wrap would take way more time than a single system is
1024
likely to run. An uptime of ten years is quite possible, a runtime of
1025
a century much less so. As an example of the latter, RCU's
1026
dyntick-idle nesting counter allows 54 bits for interrupt nesting
1027
level (this counter is 64 bits even on a 32-bit system). Overflowing
1028
this counter requires 2\ :sup:`54` half-interrupts on a given CPU
1029
without that CPU ever going idle. If a half-interrupt happened every
1030
microsecond, it would take 570 years of runtime to overflow this
1031
counter, which is currently believed to be an acceptably long time.
1032
#. Linux systems can have thousands of CPUs running a single Linux
1033
kernel in a single shared-memory environment. RCU must therefore pay
1034
close attention to high-end scalability.
1036
This last parallelism fact of life means that RCU must pay special
1037
attention to the preceding facts of life. The idea that Linux might
1038
scale to systems with thousands of CPUs would have been met with some
1039
skepticism in the 1990s, but these requirements would have otherwise
1040
have been unsurprising, even in the early 1990s.
1042
Quality-of-Implementation Requirements
1043
--------------------------------------
1045
These sections list quality-of-implementation requirements. Although an
1046
RCU implementation that ignores these requirements could still be used,
1047
it would likely be subject to limitations that would make it
1048
inappropriate for industrial-strength production use. Classes of
1049
quality-of-implementation requirements are as follows:
1051
#. `Specialization`_
1052
#. `Performance and Scalability`_
1053
#. `Forward Progress`_
1054
#. `Composability`_
1055
#. `Corner Cases`_
1057
These classes is covered in the following sections.
1059
Specialization
1060
~~~~~~~~~~~~~~
1062
RCU is and always has been intended primarily for read-mostly
1063
situations, which means that RCU's read-side primitives are optimized,
1064
often at the expense of its update-side primitives. Experience thus far
1065
is captured by the following list of situations:
1067
#. Read-mostly data, where stale and inconsistent data is not a problem:
1068
RCU works great!
1069
#. Read-mostly data, where data must be consistent: RCU works well.
1070
#. Read-write data, where data must be consistent: RCU *might* work OK.
1071
Or not.
1072
#. Write-mostly data, where data must be consistent: RCU is very
1073
unlikely to be the right tool for the job, with the following
1074
exceptions, where RCU can provide:
1076
a. Existence guarantees for update-friendly mechanisms.
1077
b. Wait-free read-side primitives for real-time use.
1079
This focus on read-mostly situations means that RCU must interoperate
1080
with other synchronization primitives. For example, the add_gp() and
1081
remove_gp_synchronous() examples discussed earlier use RCU to
1082
protect readers and locking to coordinate updaters. However, the need
1083
extends much farther, requiring that a variety of synchronization
1084
primitives be legal within RCU read-side critical sections, including
1085
spinlocks, sequence locks, atomic operations, reference counters, and
1086
memory barriers.
1088
+-----------------------------------------------------------------------+
1089
| **Quick Quiz**: |
1090
+-----------------------------------------------------------------------+
1091
| What about sleeping locks? |
1092
+-----------------------------------------------------------------------+
1093
| **Answer**: |
1094
+-----------------------------------------------------------------------+
1095
| These are forbidden within Linux-kernel RCU read-side critical |
1096
| sections because it is not legal to place a quiescent state (in this |
1097
| case, voluntary context switch) within an RCU read-side critical |
1098
| section. However, sleeping locks may be used within userspace RCU |
1099
| read-side critical sections, and also within Linux-kernel sleepable |
1100
| RCU `(SRCU) <Sleepable RCU_>`__ read-side critical sections. In |
1101
| addition, the -rt patchset turns spinlocks into a sleeping locks so |
1102
| that the corresponding critical sections can be preempted, which also |
1103
| means that these sleeplockified spinlocks (but not other sleeping |
1104
| locks!) may be acquire within -rt-Linux-kernel RCU read-side critical |
1105
| sections. |
1106
| Note that it *is* legal for a normal RCU read-side critical section |
1107
| to conditionally acquire a sleeping locks (as in |
1108
| mutex_trylock()), but only as long as it does not loop |
1109
| indefinitely attempting to conditionally acquire that sleeping locks. |
1110
| The key point is that things like mutex_trylock() either return |
1111
| with the mutex held, or return an error indication if the mutex was |
1112
| not immediately available. Either way, mutex_trylock() returns |
1113
| immediately without sleeping. |
1114
+-----------------------------------------------------------------------+
1116
It often comes as a surprise that many algorithms do not require a
1117
consistent view of data, but many can function in that mode, with
1118
network routing being the poster child. Internet routing algorithms take
1119
significant time to propagate updates, so that by the time an update
1120
arrives at a given system, that system has been sending network traffic
1121
the wrong way for a considerable length of time. Having a few threads
1122
continue to send traffic the wrong way for a few more milliseconds is
1123
clearly not a problem: In the worst case, TCP retransmissions will
1124
eventually get the data where it needs to go. In general, when tracking
1125
the state of the universe outside of the computer, some level of
1126
inconsistency must be tolerated due to speed-of-light delays if nothing
1127
else.
1129
Furthermore, uncertainty about external state is inherent in many cases.
1130
For example, a pair of veterinarians might use heartbeat to determine
1131
whether or not a given cat was alive. But how long should they wait
1132
after the last heartbeat to decide that the cat is in fact dead? Waiting
1133
less than 400 milliseconds makes no sense because this would mean that a
1134
relaxed cat would be considered to cycle between death and life more
1135
than 100 times per minute. Moreover, just as with human beings, a cat's
1136
heart might stop for some period of time, so the exact wait period is a
1137
judgment call. One of our pair of veterinarians might wait 30 seconds
1138
before pronouncing the cat dead, while the other might insist on waiting
1139
a full minute. The two veterinarians would then disagree on the state of
1140
the cat during the final 30 seconds of the minute following the last
1141
heartbeat.
1143
Interestingly enough, this same situation applies to hardware. When push
1144
comes to shove, how do we tell whether or not some external server has
1145
failed? We send messages to it periodically, and declare it failed if we
1146
don't receive a response within a given period of time. Policy decisions
1147
can usually tolerate short periods of inconsistency. The policy was
1148
decided some time ago, and is only now being put into effect, so a few
1149
milliseconds of delay is normally inconsequential.
1151
However, there are algorithms that absolutely must see consistent data.
1152
For example, the translation between a user-level SystemV semaphore ID
1153
to the corresponding in-kernel data structure is protected by RCU, but
1154
it is absolutely forbidden to update a semaphore that has just been
1155
removed. In the Linux kernel, this need for consistency is accommodated
1156
by acquiring spinlocks located in the in-kernel data structure from
1157
within the RCU read-side critical section, and this is indicated by the
1158
green box in the figure above. Many other techniques may be used, and
1159
are in fact used within the Linux kernel.
1161
In short, RCU is not required to maintain consistency, and other
1162
mechanisms may be used in concert with RCU when consistency is required.
1163
RCU's specialization allows it to do its job extremely well, and its
1164
ability to interoperate with other synchronization mechanisms allows the
1165
right mix of synchronization tools to be used for a given job.
1167
Performance and Scalability
1168
~~~~~~~~~~~~~~~~~~~~~~~~~~~
1170
Energy efficiency is a critical component of performance today, and
1171
Linux-kernel RCU implementations must therefore avoid unnecessarily
1172
awakening idle CPUs. I cannot claim that this requirement was
1173
premeditated. In fact, I learned of it during a telephone conversation
1174
in which I was given “frank and open” feedback on the importance of
1175
energy efficiency in battery-powered systems and on specific
1176
energy-efficiency shortcomings of the Linux-kernel RCU implementation.
1177
In my experience, the battery-powered embedded community will consider
1178
any unnecessary wakeups to be extremely unfriendly acts. So much so that
1179
mere Linux-kernel-mailing-list posts are insufficient to vent their ire.
1181
Memory consumption is not particularly important for in most situations,
1182
and has become decreasingly so as memory sizes have expanded and memory
1183
costs have plummeted. However, as I learned from Matt Mackall's
1184
`bloatwatch <http://elinux.org/Linux_Tiny-FAQ>`__ efforts, memory
1185
footprint is critically important on single-CPU systems with
1186
non-preemptible (``CONFIG_PREEMPTION=n``) kernels, and thus `tiny
1187
RCU <https://lore.kernel.org/r/[email protected]>`__
1188
was born. Josh Triplett has since taken over the small-memory banner
1189
with his `Linux kernel tinification <https://tiny.wiki.kernel.org/>`__
1190
project, which resulted in `SRCU <Sleepable RCU_>`__ becoming optional
1191
for those kernels not needing it.
1193
The remaining performance requirements are, for the most part,
1194
unsurprising. For example, in keeping with RCU's read-side
1195
specialization, rcu_dereference() should have negligible overhead
1196
(for example, suppression of a few minor compiler optimizations).
1197
Similarly, in non-preemptible environments, rcu_read_lock() and
1198
rcu_read_unlock() should have exactly zero overhead.
1200
In preemptible environments, in the case where the RCU read-side
1201
critical section was not preempted (as will be the case for the
1202
highest-priority real-time process), rcu_read_lock() and
1203
rcu_read_unlock() should have minimal overhead. In particular, they
1204
should not contain atomic read-modify-write operations, memory-barrier
1205
instructions, preemption disabling, interrupt disabling, or backwards
1206
branches. However, in the case where the RCU read-side critical section
1207
was preempted, rcu_read_unlock() may acquire spinlocks and disable
1208
interrupts. This is why it is better to nest an RCU read-side critical
1209
section within a preempt-disable region than vice versa, at least in
1210
cases where that critical section is short enough to avoid unduly
1211
degrading real-time latencies.
1213
The synchronize_rcu() grace-period-wait primitive is optimized for
1214
throughput. It may therefore incur several milliseconds of latency in
1215
addition to the duration of the longest RCU read-side critical section.
1216
On the other hand, multiple concurrent invocations of
1217
synchronize_rcu() are required to use batching optimizations so that
1218
they can be satisfied by a single underlying grace-period-wait
1219
operation. For example, in the Linux kernel, it is not unusual for a
1220
single grace-period-wait operation to serve more than `1,000 separate
1221
invocations <https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response>`__
1222
of synchronize_rcu(), thus amortizing the per-invocation overhead
1223
down to nearly zero. However, the grace-period optimization is also
1224
required to avoid measurable degradation of real-time scheduling and
1225
interrupt latencies.
1227
In some cases, the multi-millisecond synchronize_rcu() latencies are
1228
unacceptable. In these cases, synchronize_rcu_expedited() may be
1229
used instead, reducing the grace-period latency down to a few tens of
1230
microseconds on small systems, at least in cases where the RCU read-side
1231
critical sections are short. There are currently no special latency
1232
requirements for synchronize_rcu_expedited() on large systems, but,
1233
consistent with the empirical nature of the RCU specification, that is
1234
subject to change. However, there most definitely are scalability
1235
requirements: A storm of synchronize_rcu_expedited() invocations on
1236
4096 CPUs should at least make reasonable forward progress. In return
1237
for its shorter latencies, synchronize_rcu_expedited() is permitted
1238
to impose modest degradation of real-time latency on non-idle online
1239
CPUs. Here, “modest” means roughly the same latency degradation as a
1240
scheduling-clock interrupt.
1242
There are a number of situations where even
1243
synchronize_rcu_expedited()'s reduced grace-period latency is
1244
unacceptable. In these situations, the asynchronous call_rcu() can
1245
be used in place of synchronize_rcu() as follows:
1247
::
1249
1 struct foo {
1250
2 int a;
1251
3 int b;
1252
4 struct rcu_head rh;
1253
5 };
1254
6
1255
7 static void remove_gp_cb(struct rcu_head *rhp)
1256
8 {
1257
9 struct foo *p = container_of(rhp, struct foo, rh);
1258
10
1259
11 kfree(p);
1260
12 }
1261
13
1262
14 bool remove_gp_asynchronous(void)
1263
15 {
1264
16 struct foo *p;
1265
17
1266
18 spin_lock(&gp_lock);
1267
19 p = rcu_access_pointer(gp);
1268
20 if (!p) {
1269
21 spin_unlock(&gp_lock);
1270
22 return false;
1271
23 }
1272
24 rcu_assign_pointer(gp, NULL);
1273
25 call_rcu(&p->rh, remove_gp_cb);
1274
26 spin_unlock(&gp_lock);
1275
27 return true;
1276
28 }
1278
A definition of ``struct foo`` is finally needed, and appears on
1279
lines 1-5. The function remove_gp_cb() is passed to call_rcu()
1280
on line 25, and will be invoked after the end of a subsequent grace
1281
period. This gets the same effect as remove_gp_synchronous(), but
1282
without forcing the updater to wait for a grace period to elapse. The
1283
call_rcu() function may be used in a number of situations where
1284
neither synchronize_rcu() nor synchronize_rcu_expedited() would
1285
be legal, including within preempt-disable code, local_bh_disable()
1286
code, interrupt-disable code, and interrupt handlers. However, even
1287
call_rcu() is illegal within NMI handlers and from idle and offline
1288
CPUs. The callback function (remove_gp_cb() in this case) will be
1289
executed within softirq (software interrupt) environment within the
1290
Linux kernel, either within a real softirq handler or under the
1291
protection of local_bh_disable(). In both the Linux kernel and in
1292
userspace, it is bad practice to write an RCU callback function that
1293
takes too long. Long-running operations should be relegated to separate
1294
threads or (in the Linux kernel) workqueues.
1296
+-----------------------------------------------------------------------+
1297
| **Quick Quiz**: |
1298
+-----------------------------------------------------------------------+
1299
| Why does line 19 use rcu_access_pointer()? After all, |
1300
| call_rcu() on line 25 stores into the structure, which would |
1301
| interact badly with concurrent insertions. Doesn't this mean that |
1302
| rcu_dereference() is required? |
1303
+-----------------------------------------------------------------------+
1304
| **Answer**: |
1305
+-----------------------------------------------------------------------+
1306
| Presumably the ``->gp_lock`` acquired on line 18 excludes any |
1307
| changes, including any insertions that rcu_dereference() would |
1308
| protect against. Therefore, any insertions will be delayed until |
1309
| after ``->gp_lock`` is released on line 25, which in turn means that |
1310
| rcu_access_pointer() suffices. |
1311
+-----------------------------------------------------------------------+
1313
However, all that remove_gp_cb() is doing is invoking kfree() on
1314
the data element. This is a common idiom, and is supported by
1315
kfree_rcu(), which allows “fire and forget” operation as shown
1316
below:
1318
::
1320
1 struct foo {
1321
2 int a;
1322
3 int b;
1323
4 struct rcu_head rh;
1324
5 };
1325
6
1326
7 bool remove_gp_faf(void)
1327
8 {
1328
9 struct foo *p;
1329
10
1330
11 spin_lock(&gp_lock);
1331
12 p = rcu_dereference(gp);
1332
13 if (!p) {
1333
14 spin_unlock(&gp_lock);
1334
15 return false;
1335
16 }
1336
17 rcu_assign_pointer(gp, NULL);
1337
18 kfree_rcu(p, rh);
1338
19 spin_unlock(&gp_lock);
1339
20 return true;
1340
21 }
1342
Note that remove_gp_faf() simply invokes kfree_rcu() and
1343
proceeds, without any need to pay any further attention to the
1344
subsequent grace period and kfree(). It is permissible to invoke
1345
kfree_rcu() from the same environments as for call_rcu().
1346
Interestingly enough, DYNIX/ptx had the equivalents of call_rcu()
1347
and kfree_rcu(), but not synchronize_rcu(). This was due to the
1348
fact that RCU was not heavily used within DYNIX/ptx, so the very few
1349
places that needed something like synchronize_rcu() simply
1350
open-coded it.
1352
+-----------------------------------------------------------------------+
1353
| **Quick Quiz**: |
1354
+-----------------------------------------------------------------------+
1355
| Earlier it was claimed that call_rcu() and kfree_rcu() |
1356
| allowed updaters to avoid being blocked by readers. But how can that |
1357
| be correct, given that the invocation of the callback and the freeing |
1358
| of the memory (respectively) must still wait for a grace period to |
1359
| elapse? |
1360
+-----------------------------------------------------------------------+
1361
| **Answer**: |
1362
+-----------------------------------------------------------------------+
1363
| We could define things this way, but keep in mind that this sort of |
1364
| definition would say that updates in garbage-collected languages |
1365
| cannot complete until the next time the garbage collector runs, which |
1366
| does not seem at all reasonable. The key point is that in most cases, |
1367
| an updater using either call_rcu() or kfree_rcu() can proceed |
1368
| to the next update as soon as it has invoked call_rcu() or |
1369
| kfree_rcu(), without having to wait for a subsequent grace |
1370
| period. |
1371
+-----------------------------------------------------------------------+
1373
But what if the updater must wait for the completion of code to be
1374
executed after the end of the grace period, but has other tasks that can
1375
be carried out in the meantime? The polling-style
1376
get_state_synchronize_rcu() and cond_synchronize_rcu() functions
1377
may be used for this purpose, as shown below:
1379
::
1381
1 bool remove_gp_poll(void)
1382
2 {
1383
3 struct foo *p;
1384
4 unsigned long s;
1385
5
1386
6 spin_lock(&gp_lock);
1387
7 p = rcu_access_pointer(gp);
1388
8 if (!p) {
1389
9 spin_unlock(&gp_lock);
1390
10 return false;
1391
11 }
1392
12 rcu_assign_pointer(gp, NULL);
1393
13 spin_unlock(&gp_lock);
1394
14 s = get_state_synchronize_rcu();
1395
15 do_something_while_waiting();
1396
16 cond_synchronize_rcu(s);
1397
17 kfree(p);
1398
18 return true;
1399
19 }
1401
On line 14, get_state_synchronize_rcu() obtains a “cookie” from RCU,
1402
then line 15 carries out other tasks, and finally, line 16 returns
1403
immediately if a grace period has elapsed in the meantime, but otherwise
1404
waits as required. The need for ``get_state_synchronize_rcu`` and
1405
cond_synchronize_rcu() has appeared quite recently, so it is too
1406
early to tell whether they will stand the test of time.
1408
RCU thus provides a range of tools to allow updaters to strike the
1409
required tradeoff between latency, flexibility and CPU overhead.
1411
Forward Progress
1412
~~~~~~~~~~~~~~~~
1414
In theory, delaying grace-period completion and callback invocation is
1415
harmless. In practice, not only are memory sizes finite but also
1416
callbacks sometimes do wakeups, and sufficiently deferred wakeups can be
1417
difficult to distinguish from system hangs. Therefore, RCU must provide
1418
a number of mechanisms to promote forward progress.
1420
These mechanisms are not foolproof, nor can they be. For one simple
1421
example, an infinite loop in an RCU read-side critical section must by
1422
definition prevent later grace periods from ever completing. For a more
1423
involved example, consider a 64-CPU system built with
1424
``CONFIG_RCU_NOCB_CPU=y`` and booted with ``rcu_nocbs=1-63``, where
1425
CPUs 1 through 63 spin in tight loops that invoke call_rcu(). Even
1426
if these tight loops also contain calls to cond_resched() (thus
1427
allowing grace periods to complete), CPU 0 simply will not be able to
1428
invoke callbacks as fast as the other 63 CPUs can register them, at
1429
least not until the system runs out of memory. In both of these
1430
examples, the Spiderman principle applies: With great power comes great
1431
responsibility. However, short of this level of abuse, RCU is required
1432
to ensure timely completion of grace periods and timely invocation of
1433
callbacks.
1435
RCU takes the following steps to encourage timely completion of grace
1436
periods:
1438
#. If a grace period fails to complete within 100 milliseconds, RCU
1439
causes future invocations of cond_resched() on the holdout CPUs
1440
to provide an RCU quiescent state. RCU also causes those CPUs'
1441
need_resched() invocations to return ``true``, but only after the
1442
corresponding CPU's next scheduling-clock.
1443
#. CPUs mentioned in the ``nohz_full`` kernel boot parameter can run
1444
indefinitely in the kernel without scheduling-clock interrupts, which
1445
defeats the above need_resched() strategem. RCU will therefore
1446
invoke resched_cpu() on any ``nohz_full`` CPUs still holding out
1447
after 109 milliseconds.
1448
#. In kernels built with ``CONFIG_RCU_BOOST=y``, if a given task that
1449
has been preempted within an RCU read-side critical section is
1450
holding out for more than 500 milliseconds, RCU will resort to
1451
priority boosting.
1452
#. If a CPU is still holding out 10 seconds into the grace period, RCU
1453
will invoke resched_cpu() on it regardless of its ``nohz_full``
1454
state.
1456
The above values are defaults for systems running with ``HZ=1000``. They
1457
will vary as the value of ``HZ`` varies, and can also be changed using
1458
the relevant Kconfig options and kernel boot parameters. RCU currently
1459
does not do much sanity checking of these parameters, so please use
1460
caution when changing them. Note that these forward-progress measures
1461
are provided only for RCU, not for `SRCU <Sleepable RCU_>`__ or `Tasks
1462
RCU`_.
1464
RCU takes the following steps in call_rcu() to encourage timely
1465
invocation of callbacks when any given non-\ ``rcu_nocbs`` CPU has
1466
10,000 callbacks, or has 10,000 more callbacks than it had the last time
1467
encouragement was provided:
1469
#. Starts a grace period, if one is not already in progress.
1470
#. Forces immediate checking for quiescent states, rather than waiting
1471
for three milliseconds to have elapsed since the beginning of the
1472
grace period.
1473
#. Immediately tags the CPU's callbacks with their grace period
1474
completion numbers, rather than waiting for the ``RCU_SOFTIRQ``
1475
handler to get around to it.
1476
#. Lifts callback-execution batch limits, which speeds up callback
1477
invocation at the expense of degrading realtime response.
1479
Again, these are default values when running at ``HZ=1000``, and can be
1480
overridden. Again, these forward-progress measures are provided only for
1481
RCU, not for `SRCU <Sleepable RCU_>`__ or `Tasks
1482
RCU`_. Even for RCU, callback-invocation forward
1483
progress for ``rcu_nocbs`` CPUs is much less well-developed, in part
1484
because workloads benefiting from ``rcu_nocbs`` CPUs tend to invoke
1485
call_rcu() relatively infrequently. If workloads emerge that need
1486
both ``rcu_nocbs`` CPUs and high call_rcu() invocation rates, then
1487
additional forward-progress work will be required.
1489
Composability
1490
~~~~~~~~~~~~~
1492
Composability has received much attention in recent years, perhaps in
1493
part due to the collision of multicore hardware with object-oriented
1494
techniques designed in single-threaded environments for single-threaded
1495
use. And in theory, RCU read-side critical sections may be composed, and
1496
in fact may be nested arbitrarily deeply. In practice, as with all
1497
real-world implementations of composable constructs, there are
1498
limitations.
1500
Implementations of RCU for which rcu_read_lock() and
1501
rcu_read_unlock() generate no code, such as Linux-kernel RCU when
1502
``CONFIG_PREEMPTION=n``, can be nested arbitrarily deeply. After all, there
1503
is no overhead. Except that if all these instances of
1504
rcu_read_lock() and rcu_read_unlock() are visible to the
1505
compiler, compilation will eventually fail due to exhausting memory,
1506
mass storage, or user patience, whichever comes first. If the nesting is
1507
not visible to the compiler, as is the case with mutually recursive
1508
functions each in its own translation unit, stack overflow will result.
1509
If the nesting takes the form of loops, perhaps in the guise of tail
1510
recursion, either the control variable will overflow or (in the Linux
1511
kernel) you will get an RCU CPU stall warning. Nevertheless, this class
1512
of RCU implementations is one of the most composable constructs in
1513
existence.
1515
RCU implementations that explicitly track nesting depth are limited by
1516
the nesting-depth counter. For example, the Linux kernel's preemptible
1517
RCU limits nesting to ``INT_MAX``. This should suffice for almost all
1518
practical purposes. That said, a consecutive pair of RCU read-side
1519
critical sections between which there is an operation that waits for a
1520
grace period cannot be enclosed in another RCU read-side critical
1521
section. This is because it is not legal to wait for a grace period
1522
within an RCU read-side critical section: To do so would result either
1523
in deadlock or in RCU implicitly splitting the enclosing RCU read-side
1524
critical section, neither of which is conducive to a long-lived and
1525
prosperous kernel.
1527
It is worth noting that RCU is not alone in limiting composability. For
1528
example, many transactional-memory implementations prohibit composing a
1529
pair of transactions separated by an irrevocable operation (for example,
1530
a network receive operation). For another example, lock-based critical
1531
sections can be composed surprisingly freely, but only if deadlock is
1532
avoided.
1534
In short, although RCU read-side critical sections are highly
1535
composable, care is required in some situations, just as is the case for
1536
any other composable synchronization mechanism.
1538
Corner Cases
1539
~~~~~~~~~~~~
1541
A given RCU workload might have an endless and intense stream of RCU
1542
read-side critical sections, perhaps even so intense that there was
1543
never a point in time during which there was not at least one RCU
1544
read-side critical section in flight. RCU cannot allow this situation to
1545
block grace periods: As long as all the RCU read-side critical sections
1546
are finite, grace periods must also be finite.
1548
That said, preemptible RCU implementations could potentially result in
1549
RCU read-side critical sections being preempted for long durations,
1550
which has the effect of creating a long-duration RCU read-side critical
1551
section. This situation can arise only in heavily loaded systems, but
1552
systems using real-time priorities are of course more vulnerable.
1553
Therefore, RCU priority boosting is provided to help deal with this
1554
case. That said, the exact requirements on RCU priority boosting will
1555
likely evolve as more experience accumulates.
1557
Other workloads might have very high update rates. Although one can
1558
argue that such workloads should instead use something other than RCU,
1559
the fact remains that RCU must handle such workloads gracefully. This
1560
requirement is another factor driving batching of grace periods, but it
1561
is also the driving force behind the checks for large numbers of queued
1562
RCU callbacks in the call_rcu() code path. Finally, high update
1563
rates should not delay RCU read-side critical sections, although some
1564
small read-side delays can occur when using
1565
synchronize_rcu_expedited(), courtesy of this function's use of
1566
smp_call_function_single().
1568
Although all three of these corner cases were understood in the early
1569
1990s, a simple user-level test consisting of ``close(open(path))`` in a
1570
tight loop in the early 2000s suddenly provided a much deeper
1571
appreciation of the high-update-rate corner case. This test also
1572
motivated addition of some RCU code to react to high update rates, for
1573
example, if a given CPU finds itself with more than 10,000 RCU callbacks
1574
queued, it will cause RCU to take evasive action by more aggressively
1575
starting grace periods and more aggressively forcing completion of
1576
grace-period processing. This evasive action causes the grace period to
1577
complete more quickly, but at the cost of restricting RCU's batching
1578
optimizations, thus increasing the CPU overhead incurred by that grace
1579
period.
1581
Software-Engineering Requirements
1582
---------------------------------
1584
Between Murphy's Law and “To err is human”, it is necessary to guard
1585
against mishaps and misuse:
1587
#. It is all too easy to forget to use rcu_read_lock() everywhere
1588
that it is needed, so kernels built with ``CONFIG_PROVE_RCU=y`` will
1589
splat if rcu_dereference() is used outside of an RCU read-side
1590
critical section. Update-side code can use
1591
rcu_dereference_protected(), which takes a `lockdep
1592
expression <https://lwn.net/Articles/371986/>`__ to indicate what is
1593
providing the protection. If the indicated protection is not
1594
provided, a lockdep splat is emitted.
1595
Code shared between readers and updaters can use
1596
rcu_dereference_check(), which also takes a lockdep expression,
1597
and emits a lockdep splat if neither rcu_read_lock() nor the
1598
indicated protection is in place. In addition,
1599
rcu_dereference_raw() is used in those (hopefully rare) cases
1600
where the required protection cannot be easily described. Finally,
1601
rcu_read_lock_held() is provided to allow a function to verify
1602
that it has been invoked within an RCU read-side critical section. I
1603
was made aware of this set of requirements shortly after Thomas
1604
Gleixner audited a number of RCU uses.
1605
#. A given function might wish to check for RCU-related preconditions
1606
upon entry, before using any other RCU API. The
1607
rcu_lockdep_assert() does this job, asserting the expression in
1608
kernels having lockdep enabled and doing nothing otherwise.
1609
#. It is also easy to forget to use rcu_assign_pointer() and
1610
rcu_dereference(), perhaps (incorrectly) substituting a simple
1611
assignment. To catch this sort of error, a given RCU-protected
1612
pointer may be tagged with ``__rcu``, after which sparse will
1613
complain about simple-assignment accesses to that pointer. Arnd
1614
Bergmann made me aware of this requirement, and also supplied the
1615
needed `patch series <https://lwn.net/Articles/376011/>`__.
1616
#. Kernels built with ``CONFIG_DEBUG_OBJECTS_RCU_HEAD=y`` will splat if
1617
a data element is passed to call_rcu() twice in a row, without a
1618
grace period in between. (This error is similar to a double free.)
1619
The corresponding ``rcu_head`` structures that are dynamically
1620
allocated are automatically tracked, but ``rcu_head`` structures
1621
allocated on the stack must be initialized with
1622
init_rcu_head_on_stack() and cleaned up with
1623
destroy_rcu_head_on_stack(). Similarly, statically allocated
1624
non-stack ``rcu_head`` structures must be initialized with
1625
init_rcu_head() and cleaned up with destroy_rcu_head().
1626
Mathieu Desnoyers made me aware of this requirement, and also
1627
supplied the needed
1628
`patch <https://lore.kernel.org/r/20100319013024.GA28456@Krystal>`__.
1629
#. An infinite loop in an RCU read-side critical section will eventually
1630
trigger an RCU CPU stall warning splat, with the duration of
1631
“eventually” being controlled by the ``RCU_CPU_STALL_TIMEOUT``
1632
``Kconfig`` option, or, alternatively, by the
1633
``rcupdate.rcu_cpu_stall_timeout`` boot/sysfs parameter. However, RCU
1634
is not obligated to produce this splat unless there is a grace period
1635
waiting on that particular RCU read-side critical section.
1637
Some extreme workloads might intentionally delay RCU grace periods,
1638
and systems running those workloads can be booted with
1639
``rcupdate.rcu_cpu_stall_suppress`` to suppress the splats. This
1640
kernel parameter may also be set via ``sysfs``. Furthermore, RCU CPU
1641
stall warnings are counter-productive during sysrq dumps and during
1642
panics. RCU therefore supplies the rcu_sysrq_start() and
1643
rcu_sysrq_end() API members to be called before and after long
1644
sysrq dumps. RCU also supplies the rcu_panic() notifier that is
1645
automatically invoked at the beginning of a panic to suppress further
1646
RCU CPU stall warnings.
1648
This requirement made itself known in the early 1990s, pretty much
1649
the first time that it was necessary to debug a CPU stall. That said,
1650
the initial implementation in DYNIX/ptx was quite generic in
1651
comparison with that of Linux.
1653
#. Although it would be very good to detect pointers leaking out of RCU
1654
read-side critical sections, there is currently no good way of doing
1655
this. One complication is the need to distinguish between pointers
1656
leaking and pointers that have been handed off from RCU to some other
1657
synchronization mechanism, for example, reference counting.
1658
#. In kernels built with ``CONFIG_RCU_TRACE=y``, RCU-related information
1659
is provided via event tracing.
1660
#. Open-coded use of rcu_assign_pointer() and rcu_dereference()
1661
to create typical linked data structures can be surprisingly
1662
error-prone. Therefore, RCU-protected `linked
1663
lists <https://lwn.net/Articles/609973/#RCU%20List%20APIs>`__ and,
1664
more recently, RCU-protected `hash
1665
tables <https://lwn.net/Articles/612100/>`__ are available. Many
1666
other special-purpose RCU-protected data structures are available in
1667
the Linux kernel and the userspace RCU library.
1668
#. Some linked structures are created at compile time, but still require
1669
``__rcu`` checking. The RCU_POINTER_INITIALIZER() macro serves
1670
this purpose.
1671
#. It is not necessary to use rcu_assign_pointer() when creating
1672
linked structures that are to be published via a single external
1673
pointer. The RCU_INIT_POINTER() macro is provided for this task.
1675
This not a hard-and-fast list: RCU's diagnostic capabilities will
1676
continue to be guided by the number and type of usage bugs found in
1677
real-world RCU usage.
1679
Linux Kernel Complications
1680
--------------------------
1682
The Linux kernel provides an interesting environment for all kinds of
1683
software, including RCU. Some of the relevant points of interest are as
1684
follows:
1686
#. `Configuration`_
1687
#. `Firmware Interface`_
1688
#. `Early Boot`_
1689
#. `Interrupts and NMIs`_
1690
#. `Loadable Modules`_
1691
#. `Hotplug CPU`_
1692
#. `Scheduler and RCU`_
1693
#. `Tracing and RCU`_
1694
#. `Accesses to User Memory and RCU`_
1695
#. `Energy Efficiency`_
1696
#. `Scheduling-Clock Interrupts and RCU`_
1697
#. `Memory Efficiency`_
1698
#. `Performance, Scalability, Response Time, and Reliability`_
1700
This list is probably incomplete, but it does give a feel for the most
1701
notable Linux-kernel complications. Each of the following sections
1702
covers one of the above topics.
1704
Configuration
1705
~~~~~~~~~~~~~
1707
RCU's goal is automatic configuration, so that almost nobody needs to
1708
worry about RCU's ``Kconfig`` options. And for almost all users, RCU
1709
does in fact work well “out of the box.”
1711
However, there are specialized use cases that are handled by kernel boot
1712
parameters and ``Kconfig`` options. Unfortunately, the ``Kconfig``
1713
system will explicitly ask users about new ``Kconfig`` options, which
1714
requires almost all of them be hidden behind a ``CONFIG_RCU_EXPERT``
1715
``Kconfig`` option.
1717
This all should be quite obvious, but the fact remains that Linus
1718
Torvalds recently had to
1719
`remind <https://lore.kernel.org/r/CA+55aFy4wcCwaL4okTs8wXhGZ5h-ibecy_Meg9C4MNQrUnwMcg@mail.gmail.com>`__
1720
me of this requirement.
1722
Firmware Interface
1723
~~~~~~~~~~~~~~~~~~
1725
In many cases, kernel obtains information about the system from the
1726
firmware, and sometimes things are lost in translation. Or the
1727
translation is accurate, but the original message is bogus.
1729
For example, some systems' firmware overreports the number of CPUs,
1730
sometimes by a large factor. If RCU naively believed the firmware, as it
1731
used to do, it would create too many per-CPU kthreads. Although the
1732
resulting system will still run correctly, the extra kthreads needlessly
1733
consume memory and can cause confusion when they show up in ``ps``
1734
listings.
1736
RCU must therefore wait for a given CPU to actually come online before
1737
it can allow itself to believe that the CPU actually exists. The
1738
resulting “ghost CPUs” (which are never going to come online) cause a
1739
number of `interesting
1740
complications <https://paulmck.livejournal.com/37494.html>`__.
1742
Early Boot
1743
~~~~~~~~~~
1745
The Linux kernel's boot sequence is an interesting process, and RCU is
1746
used early, even before rcu_init() is invoked. In fact, a number of
1747
RCU's primitives can be used as soon as the initial task's
1748
``task_struct`` is available and the boot CPU's per-CPU variables are
1749
set up. The read-side primitives (rcu_read_lock(),
1750
rcu_read_unlock(), rcu_dereference(), and
1751
rcu_access_pointer()) will operate normally very early on, as will
1752
rcu_assign_pointer().
1754
Although call_rcu() may be invoked at any time during boot,
1755
callbacks are not guaranteed to be invoked until after all of RCU's
1756
kthreads have been spawned, which occurs at early_initcall() time.
1757
This delay in callback invocation is due to the fact that RCU does not
1758
invoke callbacks until it is fully initialized, and this full
1759
initialization cannot occur until after the scheduler has initialized
1760
itself to the point where RCU can spawn and run its kthreads. In theory,
1761
it would be possible to invoke callbacks earlier, however, this is not a
1762
panacea because there would be severe restrictions on what operations
1763
those callbacks could invoke.
1765
Perhaps surprisingly, synchronize_rcu() and
1766
synchronize_rcu_expedited(), will operate normally during very early
1767
boot, the reason being that there is only one CPU and preemption is
1768
disabled. This means that the call synchronize_rcu() (or friends)
1769
itself is a quiescent state and thus a grace period, so the early-boot
1770
implementation can be a no-op.
1772
However, once the scheduler has spawned its first kthread, this early
1773
boot trick fails for synchronize_rcu() (as well as for
1774
synchronize_rcu_expedited()) in ``CONFIG_PREEMPTION=y`` kernels. The
1775
reason is that an RCU read-side critical section might be preempted,
1776
which means that a subsequent synchronize_rcu() really does have to
1777
wait for something, as opposed to simply returning immediately.
1778
Unfortunately, synchronize_rcu() can't do this until all of its
1779
kthreads are spawned, which doesn't happen until some time during
1780
early_initcalls() time. But this is no excuse: RCU is nevertheless
1781
required to correctly handle synchronous grace periods during this time
1782
period. Once all of its kthreads are up and running, RCU starts running
1783
normally.
1785
+-----------------------------------------------------------------------+
1786
| **Quick Quiz**: |
1787
+-----------------------------------------------------------------------+
1788
| How can RCU possibly handle grace periods before all of its kthreads |
1789
| have been spawned??? |
1790
+-----------------------------------------------------------------------+
1791
| **Answer**: |
1792
+-----------------------------------------------------------------------+
1793
| Very carefully! |
1794
| During the “dead zone” between the time that the scheduler spawns the |
1795
| first task and the time that all of RCU's kthreads have been spawned, |
1796
| all synchronous grace periods are handled by the expedited |
1797
| grace-period mechanism. At runtime, this expedited mechanism relies |
1798
| on workqueues, but during the dead zone the requesting task itself |
1799
| drives the desired expedited grace period. Because dead-zone |
1800
| execution takes place within task context, everything works. Once the |
1801
| dead zone ends, expedited grace periods go back to using workqueues, |
1802
| as is required to avoid problems that would otherwise occur when a |
1803
| user task received a POSIX signal while driving an expedited grace |
1804
| period. |
1805
| |
1806
| And yes, this does mean that it is unhelpful to send POSIX signals to |
1807
| random tasks between the time that the scheduler spawns its first |
1808
| kthread and the time that RCU's kthreads have all been spawned. If |
1809
| there ever turns out to be a good reason for sending POSIX signals |
1810
| during that time, appropriate adjustments will be made. (If it turns |
1811
| out that POSIX signals are sent during this time for no good reason, |
1812
| other adjustments will be made, appropriate or otherwise.) |
1813
+-----------------------------------------------------------------------+
1815
I learned of these boot-time requirements as a result of a series of
1816
system hangs.
1818
Interrupts and NMIs
1819
~~~~~~~~~~~~~~~~~~~
1821
The Linux kernel has interrupts, and RCU read-side critical sections are
1822
legal within interrupt handlers and within interrupt-disabled regions of
1823
code, as are invocations of call_rcu().
1825
Some Linux-kernel architectures can enter an interrupt handler from
1826
non-idle process context, and then just never leave it, instead
1827
stealthily transitioning back to process context. This trick is
1828
sometimes used to invoke system calls from inside the kernel. These
1829
“half-interrupts” mean that RCU has to be very careful about how it
1830
counts interrupt nesting levels. I learned of this requirement the hard
1831
way during a rewrite of RCU's dyntick-idle code.
1833
The Linux kernel has non-maskable interrupts (NMIs), and RCU read-side
1834
critical sections are legal within NMI handlers. Thankfully, RCU
1835
update-side primitives, including call_rcu(), are prohibited within
1836
NMI handlers.
1838
The name notwithstanding, some Linux-kernel architectures can have
1839
nested NMIs, which RCU must handle correctly. Andy Lutomirski `surprised
1840
me <https://lore.kernel.org/r/CALCETrXLq1y7e_dKFPgou-FKHB6Pu-r8+t-6Ds+8=va7anBWDA@mail.gmail.com>`__
1841
with this requirement; he also kindly surprised me with `an
1842
algorithm <https://lore.kernel.org/r/CALCETrXSY9JpW3uE6H8WYk81sg56qasA2aqmjMPsq5dOtzso=g@mail.gmail.com>`__
1843
that meets this requirement.
1845
Furthermore, NMI handlers can be interrupted by what appear to RCU to be
1846
normal interrupts. One way that this can happen is for code that
1847
directly invokes ct_irq_enter() and ct_irq_exit() to be called
1848
from an NMI handler. This astonishing fact of life prompted the current
1849
code structure, which has ct_irq_enter() invoking
1850
ct_nmi_enter() and ct_irq_exit() invoking ct_nmi_exit().
1851
And yes, I also learned of this requirement the hard way.
1853
Loadable Modules
1854
~~~~~~~~~~~~~~~~
1856
The Linux kernel has loadable modules, and these modules can also be
1857
unloaded. After a given module has been unloaded, any attempt to call
1858
one of its functions results in a segmentation fault. The module-unload
1859
functions must therefore cancel any delayed calls to loadable-module
1860
functions, for example, any outstanding mod_timer() must be dealt
1861
with via timer_shutdown_sync() or similar.
1863
Unfortunately, there is no way to cancel an RCU callback; once you
1864
invoke call_rcu(), the callback function is eventually going to be
1865
invoked, unless the system goes down first. Because it is normally
1866
considered socially irresponsible to crash the system in response to a
1867
module unload request, we need some other way to deal with in-flight RCU
1868
callbacks.
1870
RCU therefore provides rcu_barrier(), which waits until all
1871
in-flight RCU callbacks have been invoked. If a module uses
1872
call_rcu(), its exit function should therefore prevent any future
1873
invocation of call_rcu(), then invoke rcu_barrier(). In theory,
1874
the underlying module-unload code could invoke rcu_barrier()
1875
unconditionally, but in practice this would incur unacceptable
1876
latencies.
1878
Nikita Danilov noted this requirement for an analogous
1879
filesystem-unmount situation, and Dipankar Sarma incorporated
1880
rcu_barrier() into RCU. The need for rcu_barrier() for module
1881
unloading became apparent later.
1883
.. important::
1885
The rcu_barrier() function is not, repeat,
1886
*not*, obligated to wait for a grace period. It is instead only required
1887
to wait for RCU callbacks that have already been posted. Therefore, if
1888
there are no RCU callbacks posted anywhere in the system,
1889
rcu_barrier() is within its rights to return immediately. Even if
1890
there are callbacks posted, rcu_barrier() does not necessarily need
1891
to wait for a grace period.
1893
+-----------------------------------------------------------------------+
1894
| **Quick Quiz**: |
1895
+-----------------------------------------------------------------------+
1896
| Wait a minute! Each RCU callbacks must wait for a grace period to |
1897
| complete, and rcu_barrier() must wait for each pre-existing |
1898
| callback to be invoked. Doesn't rcu_barrier() therefore need to |
1899
| wait for a full grace period if there is even one callback posted |
1900
| anywhere in the system? |
1901
+-----------------------------------------------------------------------+
1902
| **Answer**: |
1903
+-----------------------------------------------------------------------+
1904
| Absolutely not!!! |
1905
| Yes, each RCU callbacks must wait for a grace period to complete, but |
1906
| it might well be partly (or even completely) finished waiting by the |
1907
| time rcu_barrier() is invoked. In that case, rcu_barrier() |
1908
| need only wait for the remaining portion of the grace period to |
1909
| elapse. So even if there are quite a few callbacks posted, |
1910
| rcu_barrier() might well return quite quickly. |
1911
| |
1912
| So if you need to wait for a grace period as well as for all |
1913
| pre-existing callbacks, you will need to invoke both |
1914
| synchronize_rcu() and rcu_barrier(). If latency is a concern, |
1915
| you can always use workqueues to invoke them concurrently. |
1916
+-----------------------------------------------------------------------+
1918
Hotplug CPU
1919
~~~~~~~~~~~
1921
The Linux kernel supports CPU hotplug, which means that CPUs can come
1922
and go. It is of course illegal to use any RCU API member from an
1923
offline CPU, with the exception of `SRCU <Sleepable RCU_>`__ read-side
1924
critical sections. This requirement was present from day one in
1925
DYNIX/ptx, but on the other hand, the Linux kernel's CPU-hotplug
1926
implementation is “interesting.”
1928
The Linux-kernel CPU-hotplug implementation has notifiers that are used
1929
to allow the various kernel subsystems (including RCU) to respond
1930
appropriately to a given CPU-hotplug operation. Most RCU operations may
1931
be invoked from CPU-hotplug notifiers, including even synchronous
1932
grace-period operations such as (synchronize_rcu() and
1933
synchronize_rcu_expedited()). However, these synchronous operations
1934
do block and therefore cannot be invoked from notifiers that execute via
1935
stop_machine(), specifically those between the ``CPUHP_AP_OFFLINE``
1936
and ``CPUHP_AP_ONLINE`` states.
1938
In addition, all-callback-wait operations such as rcu_barrier() may
1939
not be invoked from any CPU-hotplug notifier. This restriction is due
1940
to the fact that there are phases of CPU-hotplug operations where the
1941
outgoing CPU's callbacks will not be invoked until after the CPU-hotplug
1942
operation ends, which could also result in deadlock. Furthermore,
1943
rcu_barrier() blocks CPU-hotplug operations during its execution,
1944
which results in another type of deadlock when invoked from a CPU-hotplug
1945
notifier.
1947
Finally, RCU must avoid deadlocks due to interaction between hotplug,
1948
timers and grace period processing. It does so by maintaining its own set
1949
of books that duplicate the centrally maintained ``cpu_online_mask``,
1950
and also by reporting quiescent states explicitly when a CPU goes
1951
offline. This explicit reporting of quiescent states avoids any need
1952
for the force-quiescent-state loop (FQS) to report quiescent states for
1953
offline CPUs. However, as a debugging measure, the FQS loop does splat
1954
if offline CPUs block an RCU grace period for too long.
1956
An offline CPU's quiescent state will be reported either:
1958
1. As the CPU goes offline using RCU's hotplug notifier (rcutree_report_cpu_dead()).
1959
2. When grace period initialization (rcu_gp_init()) detects a
1960
race either with CPU offlining or with a task unblocking on a leaf
1961
``rcu_node`` structure whose CPUs are all offline.
1963
The CPU-online path (rcutree_report_cpu_starting()) should never need to report
1964
a quiescent state for an offline CPU. However, as a debugging measure,
1965
it does emit a warning if a quiescent state was not already reported
1966
for that CPU.
1968
During the checking/modification of RCU's hotplug bookkeeping, the
1969
corresponding CPU's leaf node lock is held. This avoids race conditions
1970
between RCU's hotplug notifier hooks, the grace period initialization
1971
code, and the FQS loop, all of which refer to or modify this bookkeeping.
1973
Note that grace period initialization (rcu_gp_init()) must carefully sequence
1974
CPU hotplug scanning with grace period state changes. For example, the
1975
following race could occur in rcu_gp_init() if rcu_seq_start() were to happen
1976
after the CPU hotplug scanning::
1978
CPU0 (rcu_gp_init) CPU1 CPU2
1979
--------------------- ---- ----
1980
// Hotplug scan first (WRONG ORDER)
1981
rcu_for_each_leaf_node(rnp) {
1982
rnp->qsmaskinit = rnp->qsmaskinitnext;
1983
}
1984
rcutree_report_cpu_starting()
1985
rnp->qsmaskinitnext |= mask;
1986
rcu_read_lock()
1987
r0 = *X;
1988
r1 = *X;
1989
X = NULL;
1990
cookie = get_state_synchronize_rcu();
1991
// cookie = 8 (future GP)
1992
rcu_seq_start(&rcu_state.gp_seq);
1993
// gp_seq = 5
1995
// CPU1 now invisible to this GP!
1996
rcu_for_each_node_breadth_first() {
1997
rnp->qsmask = rnp->qsmaskinit;
1998
// CPU1 not included!
1999
}
2001
// GP completes without CPU1
2002
rcu_seq_end(&rcu_state.gp_seq);
2003
// gp_seq = 8
2004
poll_state_synchronize_rcu(cookie);
2005
// Returns true!
2006
kfree(r1);
2007
r2 = *r0; // USE-AFTER-FREE!
2009
By incrementing ``gp_seq`` first, CPU1's RCU read-side critical section
2010
is guaranteed to not be missed by CPU2.
2012
Concurrent Quiescent State Reporting for Offline CPUs
2013
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2015
RCU must ensure that CPUs going offline report quiescent states to avoid
2016
blocking grace periods. This requires careful synchronization to handle
2017
race conditions
2019
Race condition causing Offline CPU to hang GP
2020
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2022
A race between CPU offlining and new GP initialization (gp_init()) may occur
2023
because rcu_report_qs_rnp() in rcutree_report_cpu_dead() must temporarily
2024
release the ``rcu_node`` lock to wake the RCU grace-period kthread::
2026
CPU1 (going offline) CPU0 (GP kthread)
2027
-------------------- -----------------
2028
rcutree_report_cpu_dead()
2029
rcu_report_qs_rnp()
2030
// Must release rnp->lock to wake GP kthread
2031
raw_spin_unlock_irqrestore_rcu_node()
2032
// Wakes up and starts new GP
2033
rcu_gp_init()
2034
// First loop:
2035
copies qsmaskinitnext->qsmaskinit
2036
// CPU1 still in qsmaskinitnext!
2038
// Second loop:
2039
rnp->qsmask = rnp->qsmaskinit
2040
mask = rnp->qsmask & ~rnp->qsmaskinitnext
2041
// mask is 0! CPU1 still in both masks
2042
// Reacquire lock (but too late)
2043
rnp->qsmaskinitnext &= ~mask // Finally clears bit
2045
Without ``ofl_lock``, the new grace period includes the offline CPU and waits
2046
forever for its quiescent state causing a GP hang.
2048
A solution with ofl_lock
2049
^^^^^^^^^^^^^^^^^^^^^^^^
2051
The ``ofl_lock`` (offline lock) prevents rcu_gp_init() from running during
2052
the vulnerable window when rcu_report_qs_rnp() has released ``rnp->lock``::
2054
CPU0 (rcu_gp_init) CPU1 (rcutree_report_cpu_dead)
2055
------------------ ------------------------------
2056
rcu_for_each_leaf_node(rnp) {
2057
arch_spin_lock(&ofl_lock) -----> arch_spin_lock(&ofl_lock) [BLOCKED]
2059
// Safe: CPU1 can't interfere
2060
rnp->qsmaskinit = rnp->qsmaskinitnext
2062
arch_spin_unlock(&ofl_lock) ---> // Now CPU1 can proceed
2063
} // But snapshot already taken
2065
Another race causing GP hangs in rcu_gpu_init(): Reporting QS for Now-offline CPUs
2066
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2068
After the first loop takes an atomic snapshot of online CPUs, as shown above,
2069
the second loop in rcu_gp_init() detects CPUs that went offline between
2070
releasing ``ofl_lock`` and acquiring the per-node ``rnp->lock``.
2071
This detection is crucial because:
2073
1. The CPU might have gone offline after the snapshot but before the second loop
2074
2. The offline CPU cannot report its own QS if it's already dead
2075
3. Without this detection, the grace period would wait forever for CPUs that
2076
are now offline.
2078
The second loop performs this detection safely::
2080
rcu_for_each_node_breadth_first(rnp) {
2081
raw_spin_lock_irqsave_rcu_node(rnp, flags);
2082
rnp->qsmask = rnp->qsmaskinit; // Apply the snapshot
2084
// Detect CPUs offline after snapshot
2085
mask = rnp->qsmask & ~rnp->qsmaskinitnext;
2087
if (mask && rcu_is_leaf_node(rnp))
2088
rcu_report_qs_rnp(mask, ...) // Report QS for offline CPUs
2089
}
2091
This approach ensures atomicity: quiescent state reporting for offline CPUs
2092
happens either in rcu_gp_init() (second loop) or in rcutree_report_cpu_dead(),
2093
never both and never neither. The ``rnp->lock`` held throughout the sequence
2094
prevents races - rcutree_report_cpu_dead() also acquires this lock when
2095
clearing ``qsmaskinitnext``, ensuring mutual exclusion.
2097
Scheduler and RCU
2098
~~~~~~~~~~~~~~~~~
2100
RCU makes use of kthreads, and it is necessary to avoid excessive CPU-time
2101
accumulation by these kthreads. This requirement was no surprise, but
2102
RCU's violation of it when running context-switch-heavy workloads when
2103
built with ``CONFIG_NO_HZ_FULL=y`` `did come as a surprise
2104
[PDF] <http://www.rdrop.com/users/paulmck/scalability/paper/BareMetal.2015.01.15b.pdf>`__.
2105
RCU has made good progress towards meeting this requirement, even for
2106
context-switch-heavy ``CONFIG_NO_HZ_FULL=y`` workloads, but there is
2107
room for further improvement.
2109
There is no longer any prohibition against holding any of
2110
scheduler's runqueue or priority-inheritance spinlocks across an
2111
rcu_read_unlock(), even if interrupts and preemption were enabled
2112
somewhere within the corresponding RCU read-side critical section.
2113
Therefore, it is now perfectly legal to execute rcu_read_lock()
2114
with preemption enabled, acquire one of the scheduler locks, and hold
2115
that lock across the matching rcu_read_unlock().
2117
Similarly, the RCU flavor consolidation has removed the need for negative
2118
nesting. The fact that interrupt-disabled regions of code act as RCU
2119
read-side critical sections implicitly avoids earlier issues that used
2120
to result in destructive recursion via interrupt handler's use of RCU.
2122
Tracing and RCU
2123
~~~~~~~~~~~~~~~
2125
It is possible to use tracing on RCU code, but tracing itself uses RCU.
2126
For this reason, rcu_dereference_raw_check() is provided for use
2127
by tracing, which avoids the destructive recursion that could otherwise
2128
ensue. This API is also used by virtualization in some architectures,
2129
where RCU readers execute in environments in which tracing cannot be
2130
used. The tracing folks both located the requirement and provided the
2131
needed fix, so this surprise requirement was relatively painless.
2133
Accesses to User Memory and RCU
2134
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2136
The kernel needs to access user-space memory, for example, to access data
2137
referenced by system-call parameters. The get_user() macro does this job.
2139
However, user-space memory might well be paged out, which means that
2140
get_user() might well page-fault and thus block while waiting for the
2141
resulting I/O to complete. It would be a very bad thing for the compiler to
2142
reorder a get_user() invocation into an RCU read-side critical section.
2144
For example, suppose that the source code looked like this:
2146
::
2148
1 rcu_read_lock();
2149
2 p = rcu_dereference(gp);
2150
3 v = p->value;
2151
4 rcu_read_unlock();
2152
5 get_user(user_v, user_p);
2153
6 do_something_with(v, user_v);
2155
The compiler must not be permitted to transform this source code into
2156
the following:
2158
::
2160
1 rcu_read_lock();
2161
2 p = rcu_dereference(gp);
2162
3 get_user(user_v, user_p); // BUG: POSSIBLE PAGE FAULT!!!
2163
4 v = p->value;
2164
5 rcu_read_unlock();
2165
6 do_something_with(v, user_v);
2167
If the compiler did make this transformation in a ``CONFIG_PREEMPTION=n`` kernel
2168
build, and if get_user() did page fault, the result would be a quiescent
2169
state in the middle of an RCU read-side critical section. This misplaced
2170
quiescent state could result in line 4 being a use-after-free access,
2171
which could be bad for your kernel's actuarial statistics. Similar examples
2172
can be constructed with the call to get_user() preceding the
2173
rcu_read_lock().
2175
Unfortunately, get_user() doesn't have any particular ordering properties,
2176
and in some architectures the underlying ``asm`` isn't even marked
2177
``volatile``. And even if it was marked ``volatile``, the above access to
2178
``p->value`` is not volatile, so the compiler would not have any reason to keep
2179
those two accesses in order.
2181
Therefore, the Linux-kernel definitions of rcu_read_lock() and
2182
rcu_read_unlock() must act as compiler barriers, at least for outermost
2183
instances of rcu_read_lock() and rcu_read_unlock() within a nested set
2184
of RCU read-side critical sections.
2186
Energy Efficiency
2187
~~~~~~~~~~~~~~~~~
2189
Interrupting idle CPUs is considered socially unacceptable, especially
2190
by people with battery-powered embedded systems. RCU therefore conserves
2191
energy by detecting which CPUs are idle, including tracking CPUs that
2192
have been interrupted from idle. This is a large part of the
2193
energy-efficiency requirement, so I learned of this via an irate phone
2194
call.
2196
Because RCU avoids interrupting idle CPUs, it is illegal to execute an
2197
RCU read-side critical section on an idle CPU. (Kernels built with
2198
``CONFIG_PROVE_RCU=y`` will splat if you try it.)
2200
It is similarly socially unacceptable to interrupt an ``nohz_full`` CPU
2201
running in userspace. RCU must therefore track ``nohz_full`` userspace
2202
execution. RCU must therefore be able to sample state at two points in
2203
time, and be able to determine whether or not some other CPU spent any
2204
time idle and/or executing in userspace.
2206
These energy-efficiency requirements have proven quite difficult to
2207
understand and to meet, for example, there have been more than five
2208
clean-sheet rewrites of RCU's energy-efficiency code, the last of which
2209
was finally able to demonstrate `real energy savings running on real
2210
hardware
2211
[PDF] <http://www.rdrop.com/users/paulmck/realtime/paper/AMPenergy.2013.04.19a.pdf>`__.
2212
As noted earlier, I learned of many of these requirements via angry
2213
phone calls: Flaming me on the Linux-kernel mailing list was apparently
2214
not sufficient to fully vent their ire at RCU's energy-efficiency bugs!
2216
Scheduling-Clock Interrupts and RCU
2217
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2219
The kernel transitions between in-kernel non-idle execution, userspace
2220
execution, and the idle loop. Depending on kernel configuration, RCU
2221
handles these states differently:
2223
+-----------------+------------------+------------------+-----------------+
2224
| ``HZ`` Kconfig | In-Kernel | Usermode | Idle |
2225
+=================+==================+==================+=================+
2226
| ``HZ_PERIODIC`` | Can rely on | Can rely on | Can rely on |
2227
| | scheduling-clock | scheduling-clock | RCU's |
2228
| | interrupt. | interrupt and | dyntick-idle |
2229
| | | its detection | detection. |
2230
| | | of interrupt | |
2231
| | | from usermode. | |
2232
+-----------------+------------------+------------------+-----------------+
2233
| ``NO_HZ_IDLE`` | Can rely on | Can rely on | Can rely on |
2234
| | scheduling-clock | scheduling-clock | RCU's |
2235
| | interrupt. | interrupt and | dyntick-idle |
2236
| | | its detection | detection. |
2237
| | | of interrupt | |
2238
| | | from usermode. | |
2239
+-----------------+------------------+------------------+-----------------+
2240
| ``NO_HZ_FULL`` | Can only | Can rely on | Can rely on |
2241
| | sometimes rely | RCU's | RCU's |
2242
| | on | dyntick-idle | dyntick-idle |
2243
| | scheduling-clock | detection. | detection. |
2244
| | interrupt. In | | |
2245
| | other cases, it | | |
2246
| | is necessary to | | |
2247
| | bound kernel | | |
2248
| | execution times | | |
2249
| | and/or use | | |
2250
| | IPIs. | | |
2251
+-----------------+------------------+------------------+-----------------+
2253
+-----------------------------------------------------------------------+
2254
| **Quick Quiz**: |
2255
+-----------------------------------------------------------------------+
2256
| Why can't ``NO_HZ_FULL`` in-kernel execution rely on the |
2257
| scheduling-clock interrupt, just like ``HZ_PERIODIC`` and |
2258
| ``NO_HZ_IDLE`` do? |
2259
+-----------------------------------------------------------------------+
2260
| **Answer**: |
2261
+-----------------------------------------------------------------------+
2262
| Because, as a performance optimization, ``NO_HZ_FULL`` does not |
2263
| necessarily re-enable the scheduling-clock interrupt on entry to each |
2264
| and every system call. |
2265
+-----------------------------------------------------------------------+
2267
However, RCU must be reliably informed as to whether any given CPU is
2268
currently in the idle loop, and, for ``NO_HZ_FULL``, also whether that
2269
CPU is executing in usermode, as discussed
2270
`earlier <Energy Efficiency_>`__. It also requires that the
2271
scheduling-clock interrupt be enabled when RCU needs it to be:
2273
#. If a CPU is either idle or executing in usermode, and RCU believes it
2274
is non-idle, the scheduling-clock tick had better be running.
2275
Otherwise, you will get RCU CPU stall warnings. Or at best, very long
2276
(11-second) grace periods, with a pointless IPI waking the CPU from
2277
time to time.
2278
#. If a CPU is in a portion of the kernel that executes RCU read-side
2279
critical sections, and RCU believes this CPU to be idle, you will get
2280
random memory corruption. **DON'T DO THIS!!!**
2281
This is one reason to test with lockdep, which will complain about
2282
this sort of thing.
2283
#. If a CPU is in a portion of the kernel that is absolutely positively
2284
no-joking guaranteed to never execute any RCU read-side critical
2285
sections, and RCU believes this CPU to be idle, no problem. This
2286
sort of thing is used by some architectures for light-weight
2287
exception handlers, which can then avoid the overhead of
2288
ct_irq_enter() and ct_irq_exit() at exception entry and
2289
exit, respectively. Some go further and avoid the entireties of
2290
irq_enter() and irq_exit().
2291
Just make very sure you are running some of your tests with
2292
``CONFIG_PROVE_RCU=y``, just in case one of your code paths was in
2293
fact joking about not doing RCU read-side critical sections.
2294
#. If a CPU is executing in the kernel with the scheduling-clock
2295
interrupt disabled and RCU believes this CPU to be non-idle, and if
2296
the CPU goes idle (from an RCU perspective) every few jiffies, no
2297
problem. It is usually OK for there to be the occasional gap between
2298
idle periods of up to a second or so.
2299
If the gap grows too long, you get RCU CPU stall warnings.
2300
#. If a CPU is either idle or executing in usermode, and RCU believes it
2301
to be idle, of course no problem.
2302
#. If a CPU is executing in the kernel, the kernel code path is passing
2303
through quiescent states at a reasonable frequency (preferably about
2304
once per few jiffies, but the occasional excursion to a second or so
2305
is usually OK) and the scheduling-clock interrupt is enabled, of
2306
course no problem.
2307
If the gap between a successive pair of quiescent states grows too
2308
long, you get RCU CPU stall warnings.
2310
+-----------------------------------------------------------------------+
2311
| **Quick Quiz**: |
2312
+-----------------------------------------------------------------------+
2313
| But what if my driver has a hardware interrupt handler that can run |
2314
| for many seconds? I cannot invoke schedule() from an hardware |
2315
| interrupt handler, after all! |
2316
+-----------------------------------------------------------------------+
2317
| **Answer**: |
2318
+-----------------------------------------------------------------------+
2319
| One approach is to do ``ct_irq_exit();ct_irq_enter();`` every so |
2320
| often. But given that long-running interrupt handlers can cause other |
2321
| problems, not least for response time, shouldn't you work to keep |
2322
| your interrupt handler's runtime within reasonable bounds? |
2323
+-----------------------------------------------------------------------+
2325
But as long as RCU is properly informed of kernel state transitions
2326
between in-kernel execution, usermode execution, and idle, and as long
2327
as the scheduling-clock interrupt is enabled when RCU needs it to be,
2328
you can rest assured that the bugs you encounter will be in some other
2329
part of RCU or some other part of the kernel!
2331
Memory Efficiency
2332
~~~~~~~~~~~~~~~~~
2334
Although small-memory non-realtime systems can simply use Tiny RCU, code
2335
size is only one aspect of memory efficiency. Another aspect is the size
2336
of the ``rcu_head`` structure used by call_rcu() and
2337
kfree_rcu(). Although this structure contains nothing more than a
2338
pair of pointers, it does appear in many RCU-protected data structures,
2339
including some that are size critical. The ``page`` structure is a case
2340
in point, as evidenced by the many occurrences of the ``union`` keyword
2341
within that structure.
2343
This need for memory efficiency is one reason that RCU uses hand-crafted
2344
singly linked lists to track the ``rcu_head`` structures that are
2345
waiting for a grace period to elapse. It is also the reason why
2346
``rcu_head`` structures do not contain debug information, such as fields
2347
tracking the file and line of the call_rcu() or kfree_rcu() that
2348
posted them. Although this information might appear in debug-only kernel
2349
builds at some point, in the meantime, the ``->func`` field will often
2350
provide the needed debug information.
2352
However, in some cases, the need for memory efficiency leads to even
2353
more extreme measures. Returning to the ``page`` structure, the
2354
``rcu_head`` field shares storage with a great many other structures
2355
that are used at various points in the corresponding page's lifetime. In
2356
order to correctly resolve certain `race
2357
conditions <https://lore.kernel.org/r/1439976106-137226-1-git-send-email-kirill.shutemov@linux.intel.com>`__,
2358
the Linux kernel's memory-management subsystem needs a particular bit to
2359
remain zero during all phases of grace-period processing, and that bit
2360
happens to map to the bottom bit of the ``rcu_head`` structure's
2361
``->next`` field. RCU makes this guarantee as long as call_rcu() is
2362
used to post the callback, as opposed to kfree_rcu() or some future
2363
“lazy” variant of call_rcu() that might one day be created for
2364
energy-efficiency purposes.
2366
That said, there are limits. RCU requires that the ``rcu_head``
2367
structure be aligned to a two-byte boundary, and passing a misaligned
2368
``rcu_head`` structure to one of the call_rcu() family of functions
2369
will result in a splat. It is therefore necessary to exercise caution
2370
when packing structures containing fields of type ``rcu_head``. Why not
2371
a four-byte or even eight-byte alignment requirement? Because the m68k
2372
architecture provides only two-byte alignment, and thus acts as
2373
alignment's least common denominator.
2375
The reason for reserving the bottom bit of pointers to ``rcu_head``
2376
structures is to leave the door open to “lazy” callbacks whose
2377
invocations can safely be deferred. Deferring invocation could
2378
potentially have energy-efficiency benefits, but only if the rate of
2379
non-lazy callbacks decreases significantly for some important workload.
2380
In the meantime, reserving the bottom bit keeps this option open in case
2381
it one day becomes useful.
2383
Performance, Scalability, Response Time, and Reliability
2384
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2386
Expanding on the `earlier
2387
discussion <Performance and Scalability_>`__, RCU is used heavily by
2388
hot code paths in performance-critical portions of the Linux kernel's
2389
networking, security, virtualization, and scheduling code paths. RCU
2390
must therefore use efficient implementations, especially in its
2391
read-side primitives. To that end, it would be good if preemptible RCU's
2392
implementation of rcu_read_lock() could be inlined, however, doing
2393
this requires resolving ``#include`` issues with the ``task_struct``
2394
structure.
2396
The Linux kernel supports hardware configurations with up to 4096 CPUs,
2397
which means that RCU must be extremely scalable. Algorithms that involve
2398
frequent acquisitions of global locks or frequent atomic operations on
2399
global variables simply cannot be tolerated within the RCU
2400
implementation. RCU therefore makes heavy use of a combining tree based
2401
on the ``rcu_node`` structure. RCU is required to tolerate all CPUs
2402
continuously invoking any combination of RCU's runtime primitives with
2403
minimal per-operation overhead. In fact, in many cases, increasing load
2404
must *decrease* the per-operation overhead, witness the batching
2405
optimizations for synchronize_rcu(), call_rcu(),
2406
synchronize_rcu_expedited(), and rcu_barrier(). As a general
2407
rule, RCU must cheerfully accept whatever the rest of the Linux kernel
2408
decides to throw at it.
2410
The Linux kernel is used for real-time workloads, especially in
2411
conjunction with the `-rt
2412
patchset <https://wiki.linuxfoundation.org/realtime/>`__. The
2413
real-time-latency response requirements are such that the traditional
2414
approach of disabling preemption across RCU read-side critical sections
2415
is inappropriate. Kernels built with ``CONFIG_PREEMPTION=y`` therefore use
2416
an RCU implementation that allows RCU read-side critical sections to be
2417
preempted. This requirement made its presence known after users made it
2418
clear that an earlier `real-time
2419
patch <https://lwn.net/Articles/107930/>`__ did not meet their needs, in
2420
conjunction with some `RCU
2421
issues <https://lore.kernel.org/r/[email protected]>`__
2422
encountered by a very early version of the -rt patchset.
2424
In addition, RCU must make do with a sub-100-microsecond real-time
2425
latency budget. In fact, on smaller systems with the -rt patchset, the
2426
Linux kernel provides sub-20-microsecond real-time latencies for the
2427
whole kernel, including RCU. RCU's scalability and latency must
2428
therefore be sufficient for these sorts of configurations. To my
2429
surprise, the sub-100-microsecond real-time latency budget `applies to
2430
even the largest systems
2431
[PDF] <http://www.rdrop.com/users/paulmck/realtime/paper/bigrt.2013.01.31a.LCA.pdf>`__,
2432
up to and including systems with 4096 CPUs. This real-time requirement
2433
motivated the grace-period kthread, which also simplified handling of a
2434
number of race conditions.
2436
RCU must avoid degrading real-time response for CPU-bound threads,
2437
whether executing in usermode (which is one use case for
2438
``CONFIG_NO_HZ_FULL=y``) or in the kernel. That said, CPU-bound loops in
2439
the kernel must execute cond_resched() at least once per few tens of
2440
milliseconds in order to avoid receiving an IPI from RCU.
2442
Finally, RCU's status as a synchronization primitive means that any RCU
2443
failure can result in arbitrary memory corruption that can be extremely
2444
difficult to debug. This means that RCU must be extremely reliable,
2445
which in practice also means that RCU must have an aggressive
2446
stress-test suite. This stress-test suite is called ``rcutorture``.
2448
Although the need for ``rcutorture`` was no surprise, the current
2449
immense popularity of the Linux kernel is posing interesting—and perhaps
2450
unprecedented—validation challenges. To see this, keep in mind that
2451
there are well over one billion instances of the Linux kernel running
2452
today, given Android smartphones, Linux-powered televisions, and
2453
servers. This number can be expected to increase sharply with the advent
2454
of the celebrated Internet of Things.
2456
Suppose that RCU contains a race condition that manifests on average
2457
once per million years of runtime. This bug will be occurring about
2458
three times per *day* across the installed base. RCU could simply hide
2459
behind hardware error rates, given that no one should really expect
2460
their smartphone to last for a million years. However, anyone taking too
2461
much comfort from this thought should consider the fact that in most
2462
jurisdictions, a successful multi-year test of a given mechanism, which
2463
might include a Linux kernel, suffices for a number of types of
2464
safety-critical certifications. In fact, rumor has it that the Linux
2465
kernel is already being used in production for safety-critical
2466
applications. I don't know about you, but I would feel quite bad if a
2467
bug in RCU killed someone. Which might explain my recent focus on
2468
validation and verification.
2470
Other RCU Flavors
2471
-----------------
2473
One of the more surprising things about RCU is that there are now no
2474
fewer than five *flavors*, or API families. In addition, the primary
2475
flavor that has been the sole focus up to this point has two different
2476
implementations, non-preemptible and preemptible. The other four flavors
2477
are listed below, with requirements for each described in a separate
2478
section.
2480
#. `Bottom-Half Flavor (Historical)`_
2481
#. `Sched Flavor (Historical)`_
2482
#. `Sleepable RCU`_
2483
#. `Tasks RCU`_
2484
#. `Tasks Trace RCU`_
2486
Bottom-Half Flavor (Historical)
2487
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2489
The RCU-bh flavor of RCU has since been expressed in terms of the other
2490
RCU flavors as part of a consolidation of the three flavors into a
2491
single flavor. The read-side API remains, and continues to disable
2492
softirq and to be accounted for by lockdep. Much of the material in this
2493
section is therefore strictly historical in nature.
2495
The softirq-disable (AKA “bottom-half”, hence the “_bh” abbreviations)
2496
flavor of RCU, or *RCU-bh*, was developed by Dipankar Sarma to provide a
2497
flavor of RCU that could withstand the network-based denial-of-service
2498
attacks researched by Robert Olsson. These attacks placed so much
2499
networking load on the system that some of the CPUs never exited softirq
2500
execution, which in turn prevented those CPUs from ever executing a
2501
context switch, which, in the RCU implementation of that time, prevented
2502
grace periods from ever ending. The result was an out-of-memory
2503
condition and a system hang.
2505
The solution was the creation of RCU-bh, which does
2506
local_bh_disable() across its read-side critical sections, and which
2507
uses the transition from one type of softirq processing to another as a
2508
quiescent state in addition to context switch, idle, user mode, and
2509
offline. This means that RCU-bh grace periods can complete even when
2510
some of the CPUs execute in softirq indefinitely, thus allowing
2511
algorithms based on RCU-bh to withstand network-based denial-of-service
2512
attacks.
2514
Because rcu_read_lock_bh() and rcu_read_unlock_bh() disable and
2515
re-enable softirq handlers, any attempt to start a softirq handlers
2516
during the RCU-bh read-side critical section will be deferred. In this
2517
case, rcu_read_unlock_bh() will invoke softirq processing, which can
2518
take considerable time. One can of course argue that this softirq
2519
overhead should be associated with the code following the RCU-bh
2520
read-side critical section rather than rcu_read_unlock_bh(), but the
2521
fact is that most profiling tools cannot be expected to make this sort
2522
of fine distinction. For example, suppose that a three-millisecond-long
2523
RCU-bh read-side critical section executes during a time of heavy
2524
networking load. There will very likely be an attempt to invoke at least
2525
one softirq handler during that three milliseconds, but any such
2526
invocation will be delayed until the time of the
2527
rcu_read_unlock_bh(). This can of course make it appear at first
2528
glance as if rcu_read_unlock_bh() was executing very slowly.
2530
The `RCU-bh
2531
API <https://lwn.net/Articles/609973/#RCU%20Per-Flavor%20API%20Table>`__
2532
includes rcu_read_lock_bh(), rcu_read_unlock_bh(), rcu_dereference_bh(),
2533
rcu_dereference_bh_check(), and rcu_read_lock_bh_held(). However, the
2534
old RCU-bh update-side APIs are now gone, replaced by synchronize_rcu(),
2535
synchronize_rcu_expedited(), call_rcu(), and rcu_barrier(). In addition,
2536
anything that disables bottom halves also marks an RCU-bh read-side
2537
critical section, including local_bh_disable() and local_bh_enable(),
2538
local_irq_save() and local_irq_restore(), and so on.
2540
Sched Flavor (Historical)
2541
~~~~~~~~~~~~~~~~~~~~~~~~~
2543
The RCU-sched flavor of RCU has since been expressed in terms of the
2544
other RCU flavors as part of a consolidation of the three flavors into a
2545
single flavor. The read-side API remains, and continues to disable
2546
preemption and to be accounted for by lockdep. Much of the material in
2547
this section is therefore strictly historical in nature.
2549
Before preemptible RCU, waiting for an RCU grace period had the side
2550
effect of also waiting for all pre-existing interrupt and NMI handlers.
2551
However, there are legitimate preemptible-RCU implementations that do
2552
not have this property, given that any point in the code outside of an
2553
RCU read-side critical section can be a quiescent state. Therefore,
2554
*RCU-sched* was created, which follows “classic” RCU in that an
2555
RCU-sched grace period waits for pre-existing interrupt and NMI
2556
handlers. In kernels built with ``CONFIG_PREEMPTION=n``, the RCU and
2557
RCU-sched APIs have identical implementations, while kernels built with
2558
``CONFIG_PREEMPTION=y`` provide a separate implementation for each.
2560
Note well that in ``CONFIG_PREEMPTION=y`` kernels,
2561
rcu_read_lock_sched() and rcu_read_unlock_sched() disable and
2562
re-enable preemption, respectively. This means that if there was a
2563
preemption attempt during the RCU-sched read-side critical section,
2564
rcu_read_unlock_sched() will enter the scheduler, with all the
2565
latency and overhead entailed. Just as with rcu_read_unlock_bh(),
2566
this can make it look as if rcu_read_unlock_sched() was executing
2567
very slowly. However, the highest-priority task won't be preempted, so
2568
that task will enjoy low-overhead rcu_read_unlock_sched()
2569
invocations.
2571
The `RCU-sched
2572
API <https://lwn.net/Articles/609973/#RCU%20Per-Flavor%20API%20Table>`__
2573
includes rcu_read_lock_sched(), rcu_read_unlock_sched(),
2574
rcu_read_lock_sched_notrace(), rcu_read_unlock_sched_notrace(),
2575
rcu_dereference_sched(), rcu_dereference_sched_check(), and
2576
rcu_read_lock_sched_held(). However, the old RCU-sched update-side APIs
2577
are now gone, replaced by synchronize_rcu(), synchronize_rcu_expedited(),
2578
call_rcu(), and rcu_barrier(). In addition, anything that disables
2579
preemption also marks an RCU-sched read-side critical section,
2580
including preempt_disable() and preempt_enable(), local_irq_save()
2581
and local_irq_restore(), and so on.
2583
Sleepable RCU
2584
~~~~~~~~~~~~~
2586
For well over a decade, someone saying “I need to block within an RCU
2587
read-side critical section” was a reliable indication that this someone
2588
did not understand RCU. After all, if you are always blocking in an RCU
2589
read-side critical section, you can probably afford to use a
2590
higher-overhead synchronization mechanism. However, that changed with
2591
the advent of the Linux kernel's notifiers, whose RCU read-side critical
2592
sections almost never sleep, but sometimes need to. This resulted in the
2593
introduction of `sleepable RCU <https://lwn.net/Articles/202847/>`__, or
2594
*SRCU*.
2596
SRCU allows different domains to be defined, with each such domain
2597
defined by an instance of an ``srcu_struct`` structure. A pointer to
2598
this structure must be passed in to each SRCU function, for example,
2599
``synchronize_srcu(&ss)``, where ``ss`` is the ``srcu_struct``
2600
structure. The key benefit of these domains is that a slow SRCU reader
2601
in one domain does not delay an SRCU grace period in some other domain.
2602
That said, one consequence of these domains is that read-side code must
2603
pass a “cookie” from srcu_read_lock() to srcu_read_unlock(), for
2604
example, as follows:
2606
::
2608
1 int idx;
2609
2
2610
3 idx = srcu_read_lock(&ss);
2611
4 do_something();
2612
5 srcu_read_unlock(&ss, idx);
2614
As noted above, it is legal to block within SRCU read-side critical
2615
sections, however, with great power comes great responsibility. If you
2616
block forever in one of a given domain's SRCU read-side critical
2617
sections, then that domain's grace periods will also be blocked forever.
2618
Of course, one good way to block forever is to deadlock, which can
2619
happen if any operation in a given domain's SRCU read-side critical
2620
section can wait, either directly or indirectly, for that domain's grace
2621
period to elapse. For example, this results in a self-deadlock:
2623
::
2625
1 int idx;
2626
2
2627
3 idx = srcu_read_lock(&ss);
2628
4 do_something();
2629
5 synchronize_srcu(&ss);
2630
6 srcu_read_unlock(&ss, idx);
2632
However, if line 5 acquired a mutex that was held across a
2633
synchronize_srcu() for domain ``ss``, deadlock would still be
2634
possible. Furthermore, if line 5 acquired a mutex that was held across a
2635
synchronize_srcu() for some other domain ``ss1``, and if an
2636
``ss1``-domain SRCU read-side critical section acquired another mutex
2637
that was held across as ``ss``-domain synchronize_srcu(), deadlock
2638
would again be possible. Such a deadlock cycle could extend across an
2639
arbitrarily large number of different SRCU domains. Again, with great
2640
power comes great responsibility.
2642
Unlike the other RCU flavors, SRCU read-side critical sections can run
2643
on idle and even offline CPUs. This ability requires that
2644
srcu_read_lock() and srcu_read_unlock() contain memory barriers,
2645
which means that SRCU readers will run a bit slower than would RCU
2646
readers. It also motivates the smp_mb__after_srcu_read_unlock() API,
2647
which, in combination with srcu_read_unlock(), guarantees a full
2648
memory barrier.
2650
Also unlike other RCU flavors, synchronize_srcu() may **not** be
2651
invoked from CPU-hotplug notifiers, due to the fact that SRCU grace
2652
periods make use of timers and the possibility of timers being
2653
temporarily “stranded” on the outgoing CPU. This stranding of timers
2654
means that timers posted to the outgoing CPU will not fire until late in
2655
the CPU-hotplug process. The problem is that if a notifier is waiting on
2656
an SRCU grace period, that grace period is waiting on a timer, and that
2657
timer is stranded on the outgoing CPU, then the notifier will never be
2658
awakened, in other words, deadlock has occurred. This same situation of
2659
course also prohibits srcu_barrier() from being invoked from
2660
CPU-hotplug notifiers.
2662
SRCU also differs from other RCU flavors in that SRCU's expedited and
2663
non-expedited grace periods are implemented by the same mechanism. This
2664
means that in the current SRCU implementation, expediting a future grace
2665
period has the side effect of expediting all prior grace periods that
2666
have not yet completed. (But please note that this is a property of the
2667
current implementation, not necessarily of future implementations.) In
2668
addition, if SRCU has been idle for longer than the interval specified
2669
by the ``srcutree.exp_holdoff`` kernel boot parameter (25 microseconds
2670
by default), and if a synchronize_srcu() invocation ends this idle
2671
period, that invocation will be automatically expedited.
2673
As of v4.12, SRCU's callbacks are maintained per-CPU, eliminating a
2674
locking bottleneck present in prior kernel versions. Although this will
2675
allow users to put much heavier stress on call_srcu(), it is
2676
important to note that SRCU does not yet take any special steps to deal
2677
with callback flooding. So if you are posting (say) 10,000 SRCU
2678
callbacks per second per CPU, you are probably totally OK, but if you
2679
intend to post (say) 1,000,000 SRCU callbacks per second per CPU, please
2680
run some tests first. SRCU just might need a few adjustment to deal with
2681
that sort of load. Of course, your mileage may vary based on the speed
2682
of your CPUs and the size of your memory.
2684
The `SRCU
2685
API <https://lwn.net/Articles/609973/#RCU%20Per-Flavor%20API%20Table>`__
2686
includes srcu_read_lock(), srcu_read_unlock(),
2687
srcu_dereference(), srcu_dereference_check(),
2688
synchronize_srcu(), synchronize_srcu_expedited(),
2689
call_srcu(), srcu_barrier(), and srcu_read_lock_held(). It
2690
also includes DEFINE_SRCU(), DEFINE_STATIC_SRCU(), and
2691
init_srcu_struct() APIs for defining and initializing
2692
``srcu_struct`` structures.
2694
More recently, the SRCU API has added polling interfaces:
2696
#. start_poll_synchronize_srcu() returns a cookie identifying
2697
the completion of a future SRCU grace period and ensures
2698
that this grace period will be started.
2699
#. poll_state_synchronize_srcu() returns ``true`` iff the
2700
specified cookie corresponds to an already-completed
2701
SRCU grace period.
2702
#. get_state_synchronize_srcu() returns a cookie just like
2703
start_poll_synchronize_srcu() does, but differs in that
2704
it does nothing to ensure that any future SRCU grace period
2705
will be started.
2707
These functions are used to avoid unnecessary SRCU grace periods in
2708
certain types of buffer-cache algorithms having multi-stage age-out
2709
mechanisms. The idea is that by the time the block has aged completely
2710
from the cache, an SRCU grace period will be very likely to have elapsed.
2712
Tasks RCU
2713
~~~~~~~~~
2715
Some forms of tracing use “trampolines” to handle the binary rewriting
2716
required to install different types of probes. It would be good to be
2717
able to free old trampolines, which sounds like a job for some form of
2718
RCU. However, because it is necessary to be able to install a trace
2719
anywhere in the code, it is not possible to use read-side markers such
2720
as rcu_read_lock() and rcu_read_unlock(). In addition, it does
2721
not work to have these markers in the trampoline itself, because there
2722
would need to be instructions following rcu_read_unlock(). Although
2723
synchronize_rcu() would guarantee that execution reached the
2724
rcu_read_unlock(), it would not be able to guarantee that execution
2725
had completely left the trampoline. Worse yet, in some situations
2726
the trampoline's protection must extend a few instructions *prior* to
2727
execution reaching the trampoline. For example, these few instructions
2728
might calculate the address of the trampoline, so that entering the
2729
trampoline would be pre-ordained a surprisingly long time before execution
2730
actually reached the trampoline itself.
2732
The solution, in the form of `Tasks
2733
RCU <https://lwn.net/Articles/607117/>`__, is to have implicit read-side
2734
critical sections that are delimited by voluntary context switches, that
2735
is, calls to schedule(), cond_resched(), and
2736
synchronize_rcu_tasks(). In addition, transitions to and from
2737
userspace execution also delimit tasks-RCU read-side critical sections.
2738
Idle tasks are ignored by Tasks RCU, and Tasks Rude RCU may be used to
2739
interact with them.
2741
Note well that involuntary context switches are *not* Tasks-RCU quiescent
2742
states. After all, in preemptible kernels, a task executing code in a
2743
trampoline might be preempted. In this case, the Tasks-RCU grace period
2744
clearly cannot end until that task resumes and its execution leaves that
2745
trampoline. This means, among other things, that cond_resched() does
2746
not provide a Tasks RCU quiescent state. (Instead, use rcu_softirq_qs()
2747
from softirq or rcu_tasks_classic_qs() otherwise.)
2749
The tasks-RCU API is quite compact, consisting only of
2750
call_rcu_tasks(), synchronize_rcu_tasks(), and
2751
rcu_barrier_tasks(). In ``CONFIG_PREEMPTION=n`` kernels, trampolines
2752
cannot be preempted, so these APIs map to call_rcu(),
2753
synchronize_rcu(), and rcu_barrier(), respectively. In
2754
``CONFIG_PREEMPTION=y`` kernels, trampolines can be preempted, and these
2755
three APIs are therefore implemented by separate functions that check
2756
for voluntary context switches.
2758
Tasks Rude RCU
2759
~~~~~~~~~~~~~~
2761
Some forms of tracing need to wait for all preemption-disabled regions
2762
of code running on any online CPU, including those executed when RCU is
2763
not watching. This means that synchronize_rcu() is insufficient, and
2764
Tasks Rude RCU must be used instead. This flavor of RCU does its work by
2765
forcing a workqueue to be scheduled on each online CPU, hence the "Rude"
2766
moniker. And this operation is considered to be quite rude by real-time
2767
workloads that don't want their ``nohz_full`` CPUs receiving IPIs and
2768
by battery-powered systems that don't want their idle CPUs to be awakened.
2770
Once kernel entry/exit and deep-idle functions have been properly tagged
2771
``noinstr``, Tasks RCU can start paying attention to idle tasks (except
2772
those that are idle from RCU's perspective) and then Tasks Rude RCU can
2773
be removed from the kernel.
2775
The tasks-rude-RCU API is also reader-marking-free and thus quite compact,
2776
consisting solely of synchronize_rcu_tasks_rude().
2778
Tasks Trace RCU
2779
~~~~~~~~~~~~~~~
2781
Some forms of tracing need to sleep in readers, but cannot tolerate
2782
SRCU's read-side overhead, which includes a full memory barrier in both
2783
srcu_read_lock() and srcu_read_unlock(). This need is handled by a
2784
Tasks Trace RCU that uses scheduler locking and IPIs to synchronize with
2785
readers. Real-time systems that cannot tolerate IPIs may build their
2786
kernels with ``CONFIG_TASKS_TRACE_RCU_READ_MB=y``, which avoids the IPIs at
2787
the expense of adding full memory barriers to the read-side primitives.
2789
The tasks-trace-RCU API is also reasonably compact,
2790
consisting of rcu_read_lock_trace(), rcu_read_unlock_trace(),
2791
rcu_read_lock_trace_held(), call_rcu_tasks_trace(),
2792
synchronize_rcu_tasks_trace(), and rcu_barrier_tasks_trace().
2794
Possible Future Changes
2795
-----------------------
2797
One of the tricks that RCU uses to attain update-side scalability is to
2798
increase grace-period latency with increasing numbers of CPUs. If this
2799
becomes a serious problem, it will be necessary to rework the
2800
grace-period state machine so as to avoid the need for the additional
2801
latency.
2803
RCU disables CPU hotplug in a few places, perhaps most notably in the
2804
rcu_barrier() operations. If there is a strong reason to use
2805
rcu_barrier() in CPU-hotplug notifiers, it will be necessary to
2806
avoid disabling CPU hotplug. This would introduce some complexity, so
2807
there had better be a *very* good reason.
2809
The tradeoff between grace-period latency on the one hand and
2810
interruptions of other CPUs on the other hand may need to be
2811
re-examined. The desire is of course for zero grace-period latency as
2812
well as zero interprocessor interrupts undertaken during an expedited
2813
grace period operation. While this ideal is unlikely to be achievable,
2814
it is quite possible that further improvements can be made.
2816
The multiprocessor implementations of RCU use a combining tree that
2817
groups CPUs so as to reduce lock contention and increase cache locality.
2818
However, this combining tree does not spread its memory across NUMA
2819
nodes nor does it align the CPU groups with hardware features such as
2820
sockets or cores. Such spreading and alignment is currently believed to
2821
be unnecessary because the hotpath read-side primitives do not access
2822
the combining tree, nor does call_rcu() in the common case. If you
2823
believe that your architecture needs such spreading and alignment, then
2824
your architecture should also benefit from the
2825
``rcutree.rcu_fanout_leaf`` boot parameter, which can be set to the
2826
number of CPUs in a socket, NUMA node, or whatever. If the number of
2827
CPUs is too large, use a fraction of the number of CPUs. If the number
2828
of CPUs is a large prime number, well, that certainly is an
2829
“interesting” architectural choice! More flexible arrangements might be
2830
considered, but only if ``rcutree.rcu_fanout_leaf`` has proven
2831
inadequate, and only if the inadequacy has been demonstrated by a
2832
carefully run and realistic system-level workload.
2834
Please note that arrangements that require RCU to remap CPU numbers will
2835
require extremely good demonstration of need and full exploration of
2836
alternatives.
2838
RCU's various kthreads are reasonably recent additions. It is quite
2839
likely that adjustments will be required to more gracefully handle
2840
extreme loads. It might also be necessary to be able to relate CPU
2841
utilization by RCU's kthreads and softirq handlers to the code that
2842
instigated this CPU utilization. For example, RCU callback overhead
2843
might be charged back to the originating call_rcu() instance, though
2844
probably not in production kernels.
2846
Additional work may be required to provide reasonable forward-progress
2847
guarantees under heavy load for grace periods and for callback
2848
invocation.
2850
Summary
2851
-------
2853
This document has presented more than two decade's worth of RCU
2854
requirements. Given that the requirements keep changing, this will not
2855
be the last word on this subject, but at least it serves to get an
2856
important subset of the requirements set forth.
2858
Acknowledgments
2859
---------------
2861
I am grateful to Steven Rostedt, Lai Jiangshan, Ingo Molnar, Oleg
2862
Nesterov, Borislav Petkov, Peter Zijlstra, Boqun Feng, and Andy
2863
Lutomirski for their help in rendering this article human readable, and
2864
to Michelle Rankin for her support of this effort. Other contributions
2865
are acknowledged in the Linux kernel's git archive.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
서론과 요구사항의 범위
1-51이 문서는 Paul E. McKenney가 2015년에 정리한 RCU의 경험적 요구사항이다. RCU는 읽기-쓰기 락과 비슷한 용도로 쓰이지만, 갱신자가 reader를 막지 않는다는 점이 다르다. 그 결과 read-side primitive는 매우 빠르고 확장성이 높으며, 적절히 설계한 갱신 경로는 reader가 지연되더라도 유용한 전진 진행성을 유지할 수 있다.
여기서 말하는 요구사항은 처음부터 완전한 형식 명세로 만들어진 것이 아니다. 실제 운영체제와 하드웨어에서 RCU를 구현하고 검증하면서 드러난 조건을 모은 고수준 명세다. 따라서 기본 보장, 보장하지 않는 것, 병렬 시스템의 현실, 구현 품질, Linux 특유의 제약, 소프트웨어 공학, 다른 RCU flavor와 향후 변경 가능성을 차례로 다룬다.
기본 보장과 비보장→병렬 시스템의 제약→구현 품질→Linux 커널 통합→진단과 RCU flavor→향후 변화
RCU의 의미론에서 실제 커널 운용 조건까지 범위를 확장한다.
=================================
A Tour Through RCU's Requirements
=================================
Copyright IBM Corporation, 2015
Author: Paul E. McKenney
The initial version of this document appeared in the
`LWN <https://lwn.net/>`_ on those articles:
`part 1 <https://lwn.net/Articles/652156/>`_,
`part 2 <https://lwn.net/Articles/652677/>`_, and
`part 3 <https://lwn.net/Articles/653326/>`_.
Introduction
------------
Read-copy update (RCU) is a synchronization mechanism that is often used
as a replacement for reader-writer locking. RCU is unusual in that
updaters do not block readers, which means that RCU's read-side
primitives can be exceedingly fast and scalable. In addition, updaters
can make useful forward progress concurrently with readers. However, all
this concurrency between RCU readers and updaters does raise the
question of exactly what RCU readers are doing, which in turn raises the
question of exactly what RCU's requirements are.
This document therefore summarizes RCU's requirements, and can be
thought of as an informal, high-level specification for RCU. It is
important to understand that RCU's specification is primarily empirical
in nature; in fact, I learned about many of these requirements the hard
way. This situation might cause some consternation, however, not only
has this learning process been a lot of fun, but it has also been a
great privilege to work with so many people willing to apply
technologies in interesting new ways.
All that aside, here are the categories of currently known RCU
requirements:
#. `Fundamental Requirements`_
#. `Fundamental Non-Requirements`_
#. `Parallelism Facts of Life`_
#. `Quality-of-Implementation Requirements`_
#. `Linux Kernel Complications`_
#. `Software-Engineering Requirements`_
#. `Other RCU Flavors`_
#. `Possible Future Changes`_
This is followed by a summary_, however, the answers to
each quick quiz immediately follows the quiz. Select the big white space
with your mouse to see the answer.
Grace-period 보장
52-253가장 근본적인 보장은 grace period가 시작되기 전에 이미 존재하던 모든 RCU read-side critical section이 끝날 때까지 기다린다는 것이다. 중첩된 read-side critical section은 가장 바깥쪽 구간 하나로 취급한다. `CONFIG_PREEMPTION=n` 커널에서는 `rcu_read_lock()`과 `rcu_read_unlock()`이 실제 명령을 만들지 않을 수도 있지만, 의미론적 경계는 그대로 유지된다.
문서의 litmus test에서 reader가 `x`를 읽고 이어 `y`를 읽는 동안 updater가 `x=1`, `synchronize_rcu()`, `y=1`을 수행한다. `r1=0`인데 `r2=1`인 결과는 금지된다. reader가 새 `y`를 보았다면 grace period 뒤까지 실행된 것이므로, grace period 전에 쓴 `x`도 보아야 한다. 이 보장은 updater 전체를 정지시키는 것이 아니라 파괴적 두 번째 단계를 기존 reader와 분리한다.
DYNIX/ptx 분산 락 관리자 예에서는 `STATE_NORMAL`, `STATE_WANT_RECOVERY`, `STATE_RECOVERING`, `STATE_WANT_NORMAL` 사이 전환에 두 번의 `synchronize_rcu()`가 필요하다. 첫 번째는 정상 작업과 복구 작업을 분리하고, 두 번째는 복구 종료 뒤 정상 작업 재개가 메모리 재정렬 때문에 복구 구간과 겹치지 않도록 한다.
`synchronize_rcu()`는 자신이 기다리는 RCU read-side critical section 안에서 직접 또는 간접으로 호출하면 안 된다. 또한 grace period만으로 새 객체를 게시할 수는 없다. `add_gp_buggy()`처럼 필드를 초기화한 뒤 평범한 포인터 대입으로 공개하면 compiler나 CPU가 공개를 초기화보다 앞당길 수 있어 reader가 쓰레기 값을 볼 수 있다.
구간의미
Phase 1객체를 자료구조에서 제거하거나 상태를 전환
Grace period전부터 존재한 모든 reader의 종료 대기
Phase 2메모리 해제 또는 되돌릴 수 없는 후처리
기존 reader가 파괴적 단계와 겹치지 않게 한다.
Updater: x = 1→Updater: synchronize_rcu()→Updater: y = 1→Reader: r1 = x; r2 = y→r1 = 0, r2 = 1 금지
reader가 grace period 뒤의 값을 보면서 grace period 전 값을 놓칠 수 없다.
Fundamental Requirements
------------------------
RCU's fundamental requirements are the closest thing RCU has to hard
mathematical requirements. These are:
#. `Grace-Period Guarantee`_
#. `Publish/Subscribe Guarantee`_
#. `Memory-Barrier Guarantees`_
#. `RCU Primitives Guaranteed to Execute Unconditionally`_
#. `Guaranteed Read-to-Write Upgrade`_
Grace-Period Guarantee
~~~~~~~~~~~~~~~~~~~~~~
RCU's grace-period guarantee is unusual in being premeditated: Jack
Slingwine and I had this guarantee firmly in mind when we started work
on RCU (then called “rclock”) in the early 1990s. That said, the past
two decades of experience with RCU have produced a much more detailed
understanding of this guarantee.
RCU's grace-period guarantee allows updaters to wait for the completion
of all pre-existing RCU read-side critical sections. An RCU read-side
critical section begins with the marker rcu_read_lock() and ends
with the marker rcu_read_unlock(). These markers may be nested, and
RCU treats a nested set as one big RCU read-side critical section.
Production-quality implementations of rcu_read_lock() and
rcu_read_unlock() are extremely lightweight, and in fact have
exactly zero overhead in Linux kernels built for production use with
``CONFIG_PREEMPTION=n``.
This guarantee allows ordering to be enforced with extremely low
overhead to readers, for example:
::
1 int x, y;
2
3 void thread0(void)
4 {
5 rcu_read_lock();
6 r1 = READ_ONCE(x);
7 r2 = READ_ONCE(y);
8 rcu_read_unlock();
9 }
10
11 void thread1(void)
12 {
13 WRITE_ONCE(x, 1);
14 synchronize_rcu();
15 WRITE_ONCE(y, 1);
16 }
Because the synchronize_rcu() on line 14 waits for all pre-existing
readers, any instance of thread0() that loads a value of zero from
``x`` must complete before thread1() stores to ``y``, so that
instance must also load a value of zero from ``y``. Similarly, any
instance of thread0() that loads a value of one from ``y`` must have
started after the synchronize_rcu() started, and must therefore also
load a value of one from ``x``. Therefore, the outcome:
::
(r1 == 0 && r2 == 1)
cannot happen.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Wait a minute! You said that updaters can make useful forward |
| progress concurrently with readers, but pre-existing readers will |
| block synchronize_rcu()!!! |
| Just who are you trying to fool??? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| First, if updaters do not wish to be blocked by readers, they can use |
| call_rcu() or kfree_rcu(), which will be discussed later. |
| Second, even when using synchronize_rcu(), the other update-side |
| code does run concurrently with readers, whether pre-existing or not. |
+-----------------------------------------------------------------------+
This scenario resembles one of the first uses of RCU in
`DYNIX/ptx <https://en.wikipedia.org/wiki/DYNIX>`__, which managed a
distributed lock manager's transition into a state suitable for handling
recovery from node failure, more or less as follows:
::
1 #define STATE_NORMAL 0
2 #define STATE_WANT_RECOVERY 1
3 #define STATE_RECOVERING 2
4 #define STATE_WANT_NORMAL 3
5
6 int state = STATE_NORMAL;
7
8 void do_something_dlm(void)
9 {
10 int state_snap;
11
12 rcu_read_lock();
13 state_snap = READ_ONCE(state);
14 if (state_snap == STATE_NORMAL)
15 do_something();
16 else
17 do_something_carefully();
18 rcu_read_unlock();
19 }
20
21 void start_recovery(void)
22 {
23 WRITE_ONCE(state, STATE_WANT_RECOVERY);
24 synchronize_rcu();
25 WRITE_ONCE(state, STATE_RECOVERING);
26 recovery();
27 WRITE_ONCE(state, STATE_WANT_NORMAL);
28 synchronize_rcu();
29 WRITE_ONCE(state, STATE_NORMAL);
30 }
The RCU read-side critical section in do_something_dlm() works with
the synchronize_rcu() in start_recovery() to guarantee that
do_something() never runs concurrently with recovery(), but with
little or no synchronization overhead in do_something_dlm().
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Why is the synchronize_rcu() on line 28 needed? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Without that extra grace period, memory reordering could result in |
| do_something_dlm() executing do_something() concurrently with |
| the last bits of recovery(). |
+-----------------------------------------------------------------------+
In order to avoid fatal problems such as deadlocks, an RCU read-side
critical section must not contain calls to synchronize_rcu().
Similarly, an RCU read-side critical section must not contain anything
that waits, directly or indirectly, on completion of an invocation of
synchronize_rcu().
Although RCU's grace-period guarantee is useful in and of itself, with
`quite a few use cases <https://lwn.net/Articles/573497/>`__, it would
be good to be able to use RCU to coordinate read-side access to linked
data structures. For this, the grace-period guarantee is not sufficient,
as can be seen in function add_gp_buggy() below. We will look at the
reader's code later, but in the meantime, just think of the reader as
locklessly picking up the ``gp`` pointer, and, if the value loaded is
non-\ ``NULL``, locklessly accessing the ``->a`` and ``->b`` fields.
::
1 bool add_gp_buggy(int a, int b)
2 {
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
4 if (!p)
5 return -ENOMEM;
6 spin_lock(&gp_lock);
7 if (rcu_access_pointer(gp)) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 p->a = a;
12 p->b = a;
13 gp = p; /* ORDERING BUG */
14 spin_unlock(&gp_lock);
15 return true;
16 }
The problem is that both the compiler and weakly ordered CPUs are within
their rights to reorder this code as follows:
::
1 bool add_gp_buggy_optimized(int a, int b)
2 {
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
4 if (!p)
5 return -ENOMEM;
6 spin_lock(&gp_lock);
7 if (rcu_access_pointer(gp)) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 gp = p; /* ORDERING BUG */
12 p->a = a;
13 p->b = a;
14 spin_unlock(&gp_lock);
15 return true;
16 }
If an RCU reader fetches ``gp`` just after ``add_gp_buggy_optimized``
executes line 11, it will see garbage in the ``->a`` and ``->b`` fields.
And this is but one of many ways in which compiler and hardware
optimizations could cause trouble. Therefore, we clearly need some way
to prevent the compiler and the CPU from reordering in this manner,
which brings us to the publish-subscribe guarantee discussed in the next
section.
Publish/subscribe 보장
254-479RCU로 객체를 안전하게 공개하려면 updater는 `rcu_assign_pointer()`를, reader는 `rcu_dereference()`를 사용한다. `rcu_assign_pointer()`는 객체의 초기화가 포인터 공개보다 먼저 보이도록 release 성격의 순서를 제공한다. 객체 내부 필드 `a`와 `b`의 초기화 순서는 서로 바뀌어도 괜찮지만, 둘 다 포인터보다 먼저 공개되어야 한다.
reader가 단순히 `p = gp`를 사용하면 compiler가 `gp`를 다시 읽어 서로 다른 객체의 필드를 섞을 수 있고, DEC Alpha처럼 약한 순서의 하드웨어에서는 의존성만으로 충분하지 않을 수 있다. `rcu_dereference()`는 volatile cast와 아키텍처별 장벽을 사용해 이 문제를 막는다. 장래에는 C/C++의 `memory_order_consume`이 충분히 구현될 경우 그 의미를 활용할 수 있다.
`rcu_dereference()`로 얻은 포인터는 가장 바깥 RCU read-side critical section을 벗어나면 안 된다. 락이나 reference count로 수명을 넘겨받은 경우만 예외다. 제거 경로는 먼저 포인터를 unpublish하고, 기존 reader를 기다린 뒤, 객체를 회수한다. `remove_gp_synchronous()`는 `gp_lock`, `rcu_access_pointer()`, `rcu_assign_pointer(gp, NULL)`, `synchronize_rcu()`, `kfree()` 순서를 보여 준다.
`rcu_access_pointer()`의 반환값은 역참조하면 안 되며, 갱신 락 아래에서 존재 여부만 확인할 때 적합하다. 실제 역참조는 RCU read-side critical section 안이거나 갱신 락으로 객체가 안정된 상태에서 `rcu_dereference()`를 사용해야 한다. accessor를 생략하면 오래된 값 재사용, load tearing, value speculation 같은 문제가 생길 수 있고 `__rcu`와 sparse가 이를 찾는 데 도움을 준다.
필드 초기화→rcu_assign_pointer()로 공개→rcu_dereference()로 구독→포인터 unpublish→synchronize_rcu()→kfree()
공개와 회수는 서로 다른 accessor와 grace period로 연결된다.
API허용되는 용도
rcu_assign_pointer()완전히 초기화된 객체 게시
rcu_dereference()보호 구간 안에서 포인터 역참조
rcu_access_pointer()락 아래에서 값 또는 NULL 여부 확인, 역참조 금지
RCU_INIT_POINTER()아직 공개되지 않은 구조 초기화
목적에 맞는 accessor를 선택한다.
Publish/Subscribe Guarantee
~~~~~~~~~~~~~~~~~~~~~~~~~~~
RCU's publish-subscribe guarantee allows data to be inserted into a
linked data structure without disrupting RCU readers. The updater uses
rcu_assign_pointer() to insert the new data, and readers use
rcu_dereference() to access data, whether new or old. The following
shows an example of insertion:
::
1 bool add_gp(int a, int b)
2 {
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
4 if (!p)
5 return -ENOMEM;
6 spin_lock(&gp_lock);
7 if (rcu_access_pointer(gp)) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 p->a = a;
12 p->b = a;
13 rcu_assign_pointer(gp, p);
14 spin_unlock(&gp_lock);
15 return true;
16 }
The rcu_assign_pointer() on line 13 is conceptually equivalent to a
simple assignment statement, but also guarantees that its assignment
will happen after the two assignments in lines 11 and 12, similar to the
C11 ``memory_order_release`` store operation. It also prevents any
number of “interesting” compiler optimizations, for example, the use of
``gp`` as a scratch location immediately preceding the assignment.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| But rcu_assign_pointer() does nothing to prevent the two |
| assignments to ``p->a`` and ``p->b`` from being reordered. Can't that |
| also cause problems? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| No, it cannot. The readers cannot see either of these two fields |
| until the assignment to ``gp``, by which time both fields are fully |
| initialized. So reordering the assignments to ``p->a`` and ``p->b`` |
| cannot possibly cause any problems. |
+-----------------------------------------------------------------------+
It is tempting to assume that the reader need not do anything special to
control its accesses to the RCU-protected data, as shown in
do_something_gp_buggy() below:
::
1 bool do_something_gp_buggy(void)
2 {
3 rcu_read_lock();
4 p = gp; /* OPTIMIZATIONS GALORE!!! */
5 if (p) {
6 do_something(p->a, p->b);
7 rcu_read_unlock();
8 return true;
9 }
10 rcu_read_unlock();
11 return false;
12 }
However, this temptation must be resisted because there are a
surprisingly large number of ways that the compiler (or weak ordering
CPUs like the DEC Alpha) can trip this code up. For but one example, if
the compiler were short of registers, it might choose to refetch from
``gp`` rather than keeping a separate copy in ``p`` as follows:
::
1 bool do_something_gp_buggy_optimized(void)
2 {
3 rcu_read_lock();
4 if (gp) { /* OPTIMIZATIONS GALORE!!! */
5 do_something(gp->a, gp->b);
6 rcu_read_unlock();
7 return true;
8 }
9 rcu_read_unlock();
10 return false;
11 }
If this function ran concurrently with a series of updates that replaced
the current structure with a new one, the fetches of ``gp->a`` and
``gp->b`` might well come from two different structures, which could
cause serious confusion. To prevent this (and much else besides),
do_something_gp() uses rcu_dereference() to fetch from ``gp``:
::
1 bool do_something_gp(void)
2 {
3 rcu_read_lock();
4 p = rcu_dereference(gp);
5 if (p) {
6 do_something(p->a, p->b);
7 rcu_read_unlock();
8 return true;
9 }
10 rcu_read_unlock();
11 return false;
12 }
The rcu_dereference() uses volatile casts and (for DEC Alpha) memory
barriers in the Linux kernel. Should a |high-quality implementation of
C11 memory_order_consume [PDF]|_
ever appear, then rcu_dereference() could be implemented as a
``memory_order_consume`` load. Regardless of the exact implementation, a
pointer fetched by rcu_dereference() may not be used outside of the
outermost RCU read-side critical section containing that
rcu_dereference(), unless protection of the corresponding data
element has been passed from RCU to some other synchronization
mechanism, most commonly locking or reference counting
(see ../../rcuref.rst).
.. |high-quality implementation of C11 memory_order_consume [PDF]| replace:: high-quality implementation of C11 ``memory_order_consume`` [PDF]
.. _high-quality implementation of C11 memory_order_consume [PDF]: http://www.rdrop.com/users/paulmck/RCU/consume.2015.07.13a.pdf
In short, updaters use rcu_assign_pointer() and readers use
rcu_dereference(), and these two RCU API elements work together to
ensure that readers have a consistent view of newly added data elements.
Of course, it is also necessary to remove elements from RCU-protected
data structures, for example, using the following process:
#. Remove the data element from the enclosing structure.
#. Wait for all pre-existing RCU read-side critical sections to complete
(because only pre-existing readers can possibly have a reference to
the newly removed data element).
#. At this point, only the updater has a reference to the newly removed
data element, so it can safely reclaim the data element, for example,
by passing it to kfree().
This process is implemented by remove_gp_synchronous():
::
1 bool remove_gp_synchronous(void)
2 {
3 struct foo *p;
4
5 spin_lock(&gp_lock);
6 p = rcu_access_pointer(gp);
7 if (!p) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 rcu_assign_pointer(gp, NULL);
12 spin_unlock(&gp_lock);
13 synchronize_rcu();
14 kfree(p);
15 return true;
16 }
This function is straightforward, with line 13 waiting for a grace
period before line 14 frees the old data element. This waiting ensures
that readers will reach line 7 of do_something_gp() before the data
element referenced by ``p`` is freed. The rcu_access_pointer() on
line 6 is similar to rcu_dereference(), except that:
#. The value returned by rcu_access_pointer() cannot be
dereferenced. If you want to access the value pointed to as well as
the pointer itself, use rcu_dereference() instead of
rcu_access_pointer().
#. The call to rcu_access_pointer() need not be protected. In
contrast, rcu_dereference() must either be within an RCU
read-side critical section or in a code segment where the pointer
cannot change, for example, in code protected by the corresponding
update-side lock.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Without the rcu_dereference() or the rcu_access_pointer(), |
| what destructive optimizations might the compiler make use of? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Let's start with what happens to do_something_gp() if it fails to |
| use rcu_dereference(). It could reuse a value formerly fetched |
| from this same pointer. It could also fetch the pointer from ``gp`` |
| in a byte-at-a-time manner, resulting in *load tearing*, in turn |
| resulting a bytewise mash-up of two distinct pointer values. It might |
| even use value-speculation optimizations, where it makes a wrong |
| guess, but by the time it gets around to checking the value, an |
| update has changed the pointer to match the wrong guess. Too bad |
| about any dereferences that returned pre-initialization garbage in |
| the meantime! |
| For remove_gp_synchronous(), as long as all modifications to |
| ``gp`` are carried out while holding ``gp_lock``, the above |
| optimizations are harmless. However, ``sparse`` will complain if you |
| define ``gp`` with ``__rcu`` and then access it without using either |
| rcu_access_pointer() or rcu_dereference(). |
+-----------------------------------------------------------------------+
In short, RCU's publish-subscribe guarantee is provided by the
combination of rcu_assign_pointer() and rcu_dereference(). This
guarantee allows data elements to be safely added to RCU-protected
linked data structures without disrupting RCU readers. This guarantee
can be used in combination with the grace-period guarantee to also allow
data elements to be removed from RCU-protected linked data structures,
again without disrupting RCU readers.
This guarantee was only partially premeditated. DYNIX/ptx used an
explicit memory barrier for publication, but had nothing resembling
rcu_dereference() for subscription, nor did it have anything
resembling the dependency-ordering barrier that was later subsumed
into rcu_dereference() and later still into READ_ONCE(). The
need for these operations made itself known quite suddenly at a
late-1990s meeting with the DEC Alpha architects, back in the days when
DEC was still a free-standing company. It took the Alpha architects a
good hour to convince me that any sort of barrier would ever be needed,
and it then took me a good *two* hours to convince them that their
documentation did not make this point clear. More recent work with the C
and C++ standards committees have provided much education on tricks and
traps from the compiler. In short, compilers were much less tricky in
the early 1990s, but in 2015, don't even think about omitting
rcu_dereference()!
Memory-barrier 보장
480-631RCU grace period는 네 방향의 강한 순서를 제공한다. 첫째, reader가 grace period보다 먼저 시작했으면 reader 종료와 `synchronize_rcu()` 반환 사이에 full barrier에 해당하는 순서가 있다. 둘째, reader가 `synchronize_rcu()` 반환 뒤에 끝났다면 synchronize 시작과 reader 시작 사이에도 같은 순서가 있다.
셋째, 기다리는 task가 같은 CPU에 머물면 그 CPU는 `synchronize_rcu()` 동안 full barrier를 실행한 것과 같은 효과를 얻는다. 넷째, task가 여러 CPU로 이동했다면 이동 경로에 속한 모든 CPU가 이 ordering에 참여한다. RCU가 reader가 grace period 뒤에 시작했다고 증명할 수 없으면 보수적으로 기존 reader로 간주해 기다린다.
이 관계는 `rcu_read_lock()` 명령 자체가 아니라 실제 메모리 access 사이에 정의된다. grace period 전 access가 critical section 안의 access를 관찰했다면, 그 critical section의 어떤 access도 grace period 뒤 access를 먼저 관찰해서는 안 된다. 이 강한 경계가 없으면 이전 reader와 이후 reader 양쪽 모두 use-after-free에 노출될 수 있다.
사용자는 내부에 어떤 barrier 명령이 배치되는지 의존하지 말고 API의 의미론에 의존해야 한다. Barrier는 기존 reader를 기다리는 일을 대신하지 않는다. 기다림과 ordering이 함께 있어야 회수 안전성이 성립한다.
경우보장
reader가 GP 전에 시작reader 종료 -> GP 반환 full ordering
reader가 GP 반환 뒤 종료GP 시작 -> reader 시작 full ordering
task가 같은 CPU 유지그 CPU에서 full barrier 효과
task가 CPU 사이 이동이동 경로의 CPU 모두 ordering에 참여
CPU와 task 이동 여부에 관계없이 전후 access를 잇는다.
Memory-Barrier Guarantees
~~~~~~~~~~~~~~~~~~~~~~~~~
The previous section's simple linked-data-structure scenario clearly
demonstrates the need for RCU's stringent memory-ordering guarantees on
systems with more than one CPU:
#. Each CPU that has an RCU read-side critical section that begins
before synchronize_rcu() starts is guaranteed to execute a full
memory barrier between the time that the RCU read-side critical
section ends and the time that synchronize_rcu() returns. Without
this guarantee, a pre-existing RCU read-side critical section might
hold a reference to the newly removed ``struct foo`` after the
kfree() on line 14 of remove_gp_synchronous().
#. Each CPU that has an RCU read-side critical section that ends after
synchronize_rcu() returns is guaranteed to execute a full memory
barrier between the time that synchronize_rcu() begins and the
time that the RCU read-side critical section begins. Without this
guarantee, a later RCU read-side critical section running after the
kfree() on line 14 of remove_gp_synchronous() might later run
do_something_gp() and find the newly deleted ``struct foo``.
#. If the task invoking synchronize_rcu() remains on a given CPU,
then that CPU is guaranteed to execute a full memory barrier sometime
during the execution of synchronize_rcu(). This guarantee ensures
that the kfree() on line 14 of remove_gp_synchronous() really
does execute after the removal on line 11.
#. If the task invoking synchronize_rcu() migrates among a group of
CPUs during that invocation, then each of the CPUs in that group is
guaranteed to execute a full memory barrier sometime during the
execution of synchronize_rcu(). This guarantee also ensures that
the kfree() on line 14 of remove_gp_synchronous() really does
execute after the removal on line 11, but also in the case where the
thread executing the synchronize_rcu() migrates in the meantime.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Given that multiple CPUs can start RCU read-side critical sections at |
| any time without any ordering whatsoever, how can RCU possibly tell |
| whether or not a given RCU read-side critical section starts before a |
| given instance of synchronize_rcu()? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| If RCU cannot tell whether or not a given RCU read-side critical |
| section starts before a given instance of synchronize_rcu(), then |
| it must assume that the RCU read-side critical section started first. |
| In other words, a given instance of synchronize_rcu() can avoid |
| waiting on a given RCU read-side critical section only if it can |
| prove that synchronize_rcu() started first. |
| A related question is “When rcu_read_lock() doesn't generate any |
| code, why does it matter how it relates to a grace period?” The |
| answer is that it is not the relationship of rcu_read_lock() |
| itself that is important, but rather the relationship of the code |
| within the enclosed RCU read-side critical section to the code |
| preceding and following the grace period. If we take this viewpoint, |
| then a given RCU read-side critical section begins before a given |
| grace period when some access preceding the grace period observes the |
| effect of some access within the critical section, in which case none |
| of the accesses within the critical section may observe the effects |
| of any access following the grace period. |
| |
| As of late 2016, mathematical models of RCU take this viewpoint, for |
| example, see slides 62 and 63 of the `2016 LinuxCon |
| EU <http://www2.rdrop.com/users/paulmck/scalability/paper/LinuxMM.201 |
| 6.10.04c.LCE.pdf>`__ |
| presentation. |
+-----------------------------------------------------------------------+
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| The first and second guarantees require unbelievably strict ordering! |
| Are all these memory barriers *really* required? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Yes, they really are required. To see why the first guarantee is |
| required, consider the following sequence of events: |
| |
| #. CPU 1: rcu_read_lock() |
| #. CPU 1: ``q = rcu_dereference(gp); /* Very likely to return p. */`` |
| #. CPU 0: ``list_del_rcu(p);`` |
| #. CPU 0: synchronize_rcu() starts. |
| #. CPU 1: ``do_something_with(q->a);`` |
| ``/* No smp_mb(), so might happen after kfree(). */`` |
| #. CPU 1: rcu_read_unlock() |
| #. CPU 0: synchronize_rcu() returns. |
| #. CPU 0: ``kfree(p);`` |
| |
| Therefore, there absolutely must be a full memory barrier between the |
| end of the RCU read-side critical section and the end of the grace |
| period. |
| |
| The sequence of events demonstrating the necessity of the second rule |
| is roughly similar: |
| |
| #. CPU 0: ``list_del_rcu(p);`` |
| #. CPU 0: synchronize_rcu() starts. |
| #. CPU 1: rcu_read_lock() |
| #. CPU 1: ``q = rcu_dereference(gp);`` |
| ``/* Might return p if no memory barrier. */`` |
| #. CPU 0: synchronize_rcu() returns. |
| #. CPU 0: ``kfree(p);`` |
| #. CPU 1: ``do_something_with(q->a); /* Boom!!! */`` |
| #. CPU 1: rcu_read_unlock() |
| |
| And similarly, without a memory barrier between the beginning of the |
| grace period and the beginning of the RCU read-side critical section, |
| CPU 1 might end up accessing the freelist. |
| |
| The “as if” rule of course applies, so that any implementation that |
| acts as if the appropriate memory barriers were in place is a correct |
| implementation. That said, it is much easier to fool yourself into |
| believing that you have adhered to the as-if rule than it is to |
| actually adhere to it! |
+-----------------------------------------------------------------------+
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| You claim that rcu_read_lock() and rcu_read_unlock() generate |
| absolutely no code in some kernel builds. This means that the |
| compiler might arbitrarily rearrange consecutive RCU read-side |
| critical sections. Given such rearrangement, if a given RCU read-side |
| critical section is done, how can you be sure that all prior RCU |
| read-side critical sections are done? Won't the compiler |
| rearrangements make that impossible to determine? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| In cases where rcu_read_lock() and rcu_read_unlock() generate |
| absolutely no code, RCU infers quiescent states only at special |
| locations, for example, within the scheduler. Because calls to |
| schedule() had better prevent calling-code accesses to shared |
| variables from being rearranged across the call to schedule(), if |
| RCU detects the end of a given RCU read-side critical section, it |
| will necessarily detect the end of all prior RCU read-side critical |
| sections, no matter how aggressively the compiler scrambles the code. |
| Again, this all assumes that the compiler cannot scramble code across |
| calls to the scheduler, out of interrupt handlers, into the idle |
| loop, into user-mode code, and so on. But if your kernel build allows |
| that sort of scrambling, you have broken far more than just RCU! |
+-----------------------------------------------------------------------+
Note that these memory-barrier requirements do not replace the
fundamental RCU requirement that a grace period wait for all
pre-existing readers. On the contrary, the memory barriers called out in
this section must operate in such a way as to *enforce* this fundamental
requirement. Of course, different implementations enforce this
requirement in different ways, but enforce it they must.
무조건 실행 primitive와 read-to-write 전환
632-677일반적인 RCU primitive는 호출되면 반드시 정해진 일을 수행하고 오류나 재시도를 요구하지 않는 것이 보장된다. 이는 처음부터 형식적으로 선언한 요구라기보다 오랜 구현과 사용 사례에서 역으로 확인된 실용적 계약이다. 조건부 primitive를 추가하려면 명확하고 강한 사용 사례가 필요하다.
RCU read-side critical section 안에서 updater용 락을 획득해 read-to-write로 전환하는 것은 허용된다. 단, `synchronize_rcu()`를 호출하기 전에 read-side critical section을 끝내야 한다. 기다리지 않는 `call_rcu()`나 `kfree_rcu()`는 이 제약을 피하는 대안이다.
이 전환은 updater끼리의 배타성은 제공해도 reader를 배제하지 않는다. 정상적인 RCU 갱신과 마찬가지로 reader는 계속 실행될 수 있다. 장점은 lookup 경로를 reader와 updater가 공유할 수 있다는 데 있다.
rcu_read_lock()→객체 lookup→update lock 획득→rcu_read_unlock()→갱신→필요하면 grace period 대기
read 보호에서 갱신 락으로 수명과 일관성 보호를 넘긴다.
RCU Primitives Guaranteed to Execute Unconditionally
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The common-case RCU primitives are unconditional. They are invoked, they
do their job, and they return, with no possibility of error, and no need
to retry. This is a key RCU design philosophy.
However, this philosophy is pragmatic rather than pigheaded. If someone
comes up with a good justification for a particular conditional RCU
primitive, it might well be implemented and added. After all, this
guarantee was reverse-engineered, not premeditated. The unconditional
nature of the RCU primitives was initially an accident of
implementation, and later experience with synchronization primitives
with conditional primitives caused me to elevate this accident to a
guarantee. Therefore, the justification for adding a conditional
primitive to RCU would need to be based on detailed and compelling use
cases.
Guaranteed Read-to-Write Upgrade
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As far as RCU is concerned, it is always possible to carry out an update
within an RCU read-side critical section. For example, that RCU
read-side critical section might search for a given data element, and
then might acquire the update-side spinlock in order to update that
element, all while remaining in that RCU read-side critical section. Of
course, it is necessary to exit the RCU read-side critical section
before invoking synchronize_rcu(), however, this inconvenience can
be avoided through use of the call_rcu() and kfree_rcu() API
members described later in this document.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| But how does the upgrade-to-write operation exclude other readers? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| It doesn't, just like normal RCU updates, which also do not exclude |
| RCU readers. |
+-----------------------------------------------------------------------+
This guarantee allows lookup code to be shared between read-side and
update-side code, and was premeditated, appearing in the earliest
DYNIX/ptx RCU documentation.
RCU가 보장하지 않는 ordering과 배타성
678-808`rcu_read_lock()`과 `rcu_read_unlock()`은 그 자체로 일반 메모리 access의 순서를 만들어 주지 않는다. 예시에서 reader가 `x`와 `y`를 읽고 updater가 반대 순서로 쓰는 경우 `r1=1`, `r2=0` 결과가 허용될 수 있다. 특정 compiler 재정렬까지 막으려면 `READ_ONCE()`와 `WRITE_ONCE()` 같은 도구를 별도로 사용해야 한다.
RCU reader는 updater를 배제하지 않는다. `rcu_read_lock()`은 grace period 종료를 지연시킬 뿐, 갱신 락을 가진 updater가 같은 객체를 바꾸는 것을 막지 않는다. 따라서 reader가 `x`를 확인한 직후 updater가 값을 바꾸면 reader의 `WARN_ON(!x)`가 발동할 수 있다. 일관성이 필요하면 spinlock, sequence lock, reference count 같은 별도 수단을 결합한다.
`synchronize_rcu()`는 호출 시점에 이미 존재하던 reader만 기다린다. 기다리는 도중 새 reader가 시작되는 것은 정상이며, 모든 reader가 동시에 사라지는 순간을 만들려고 하지 않는다. 설령 새 reader까지 모두 기다린다 해도 연속적으로 reader가 들어오는 workload에서는 그런 순간이 존재하지 않을 수 있다.
항목RCU의 동작
기존 reader 종료grace period가 기다림
새 reader 시작허용
reader와 updater 동시 실행허용
reader 내부 일반 access 순서별도 primitive 필요
일관된 snapshot락 등과 결합해야 함
RCU는 수명 분리를 제공하지만 일반 배타 락이 아니다.
Fundamental Non-Requirements
----------------------------
RCU provides extremely lightweight readers, and its read-side
guarantees, though quite useful, are correspondingly lightweight. It is
therefore all too easy to assume that RCU is guaranteeing more than it
really is. Of course, the list of things that RCU does not guarantee is
infinitely long, however, the following sections list a few
non-guarantees that have caused confusion. Except where otherwise noted,
these non-guarantees were premeditated.
#. `Readers Impose Minimal Ordering`_
#. `Readers Do Not Exclude Updaters`_
#. `Updaters Only Wait For Old Readers`_
#. `Grace Periods Don't Partition Read-Side Critical Sections`_
#. `Read-Side Critical Sections Don't Partition Grace Periods`_
Readers Impose Minimal Ordering
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Reader-side markers such as rcu_read_lock() and
rcu_read_unlock() provide absolutely no ordering guarantees except
through their interaction with the grace-period APIs such as
synchronize_rcu(). To see this, consider the following pair of
threads:
::
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(x, 1);
5 rcu_read_unlock();
6 rcu_read_lock();
7 WRITE_ONCE(y, 1);
8 rcu_read_unlock();
9 }
10
11 void thread1(void)
12 {
13 rcu_read_lock();
14 r1 = READ_ONCE(y);
15 rcu_read_unlock();
16 rcu_read_lock();
17 r2 = READ_ONCE(x);
18 rcu_read_unlock();
19 }
After thread0() and thread1() execute concurrently, it is quite
possible to have
::
(r1 == 1 && r2 == 0)
(that is, ``y`` appears to have been assigned before ``x``), which would
not be possible if rcu_read_lock() and rcu_read_unlock() had
much in the way of ordering properties. But they do not, so the CPU is
within its rights to do significant reordering. This is by design: Any
significant ordering constraints would slow down these fast-path APIs.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Can't the compiler also reorder this code? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| No, the volatile casts in READ_ONCE() and WRITE_ONCE() |
| prevent the compiler from reordering in this particular case. |
+-----------------------------------------------------------------------+
Readers Do Not Exclude Updaters
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Neither rcu_read_lock() nor rcu_read_unlock() exclude updates.
All they do is to prevent grace periods from ending. The following
example illustrates this:
::
1 void thread0(void)
2 {
3 rcu_read_lock();
4 r1 = READ_ONCE(y);
5 if (r1) {
6 do_something_with_nonzero_x();
7 r2 = READ_ONCE(x);
8 WARN_ON(!r2); /* BUG!!! */
9 }
10 rcu_read_unlock();
11 }
12
13 void thread1(void)
14 {
15 spin_lock(&my_lock);
16 WRITE_ONCE(x, 1);
17 WRITE_ONCE(y, 1);
18 spin_unlock(&my_lock);
19 }
If the thread0() function's rcu_read_lock() excluded the
thread1() function's update, the WARN_ON() could never fire. But
the fact is that rcu_read_lock() does not exclude much of anything
aside from subsequent grace periods, of which thread1() has none, so
the WARN_ON() can and does fire.
Updaters Only Wait For Old Readers
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
It might be tempting to assume that after synchronize_rcu()
completes, there are no readers executing. This temptation must be
avoided because new readers can start immediately after
synchronize_rcu() starts, and synchronize_rcu() is under no
obligation to wait for these new readers.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Suppose that synchronize_rcu() did wait until *all* readers had |
| completed instead of waiting only on pre-existing readers. For how |
| long would the updater be able to rely on there being no readers? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| For no time at all. Even if synchronize_rcu() were to wait until |
| all readers had completed, a new reader might start immediately after |
| synchronize_rcu() completed. Therefore, the code following |
| synchronize_rcu() can *never* rely on there being no readers. |
+-----------------------------------------------------------------------+
Grace period와 reader의 비분할성
809-991하나의 grace period는 앞뒤의 두 RCU read-side critical section을 반드시 분할하지 않는다. 첫 reader가 grace period 전에 끝나고 둘째 reader가 grace period가 끝나기 전에 시작하면 두 구간 모두 같은 grace period와 겹칠 수 있다. 문서의 `GPpartitionReaders1.svg`는 이 배치를 보여 준다.
두 reader 사이를 강제로 분할하려면 첫 grace period가 끝난 뒤 두 번째 grace period가 시작되었다는 관계가 필요하다. 이때 첫 reader는 첫 GP 전에, 둘째 reader는 두 번째 GP 뒤에 배치되도록 관찰 결과가 제한된다. 문서의 litmus test는 `r1`, `r2`, `r3`, `r4` 조합 중 모순되는 결과를 금지한다.
반대로 하나의 RCU read-side critical section이 앞뒤의 두 grace period를 반드시 분할하는 것도 아니다. reader가 첫 GP 시작 전부터 둘째 GP 종료 직전까지 길게 겹칠 수 있기 때문이다. `ReadersPartitionGP1.svg`의 핵심은 reader와 grace period의 포함 관계만으로 전역적인 partition을 가정해서는 안 된다는 것이다.
Reader 1 시작→Grace period 시작→Reader 1 종료→Reader 2 시작→Grace period 종료→Reader 2 종료
한 GP가 두 reader 구간과 모두 겹칠 수 있다.
Reader 시작→Grace period 1 시작/종료→Grace period 2 시작/종료→Reader 종료
한 reader가 두 GP와 모두 겹칠 수 있다.
Grace Periods Don't Partition Read-Side Critical Sections
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
It is tempting to assume that if any part of one RCU read-side critical
section precedes a given grace period, and if any part of another RCU
read-side critical section follows that same grace period, then all of
the first RCU read-side critical section must precede all of the second.
However, this just isn't the case: A single grace period does not
partition the set of RCU read-side critical sections. An example of this
situation can be illustrated as follows, where ``x``, ``y``, and ``z``
are initially all zero:
::
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(a, 1);
5 WRITE_ONCE(b, 1);
6 rcu_read_unlock();
7 }
8
9 void thread1(void)
10 {
11 r1 = READ_ONCE(a);
12 synchronize_rcu();
13 WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18 rcu_read_lock();
19 r2 = READ_ONCE(b);
20 r3 = READ_ONCE(c);
21 rcu_read_unlock();
22 }
It turns out that the outcome:
::
(r1 == 1 && r2 == 0 && r3 == 1)
is entirely possible. The following figure show how this can happen,
with each circled ``QS`` indicating the point at which RCU recorded a
*quiescent state* for each thread, that is, a state in which RCU knows
that the thread cannot be in the midst of an RCU read-side critical
section that started before the current grace period:
.. kernel-figure:: GPpartitionReaders1.svg
If it is necessary to partition RCU read-side critical sections in this
manner, it is necessary to use two grace periods, where the first grace
period is known to end before the second grace period starts:
::
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(a, 1);
5 WRITE_ONCE(b, 1);
6 rcu_read_unlock();
7 }
8
9 void thread1(void)
10 {
11 r1 = READ_ONCE(a);
12 synchronize_rcu();
13 WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18 r2 = READ_ONCE(c);
19 synchronize_rcu();
20 WRITE_ONCE(d, 1);
21 }
22
23 void thread3(void)
24 {
25 rcu_read_lock();
26 r3 = READ_ONCE(b);
27 r4 = READ_ONCE(d);
28 rcu_read_unlock();
29 }
Here, if ``(r1 == 1)``, then thread0()'s write to ``b`` must happen
before the end of thread1()'s grace period. If in addition
``(r4 == 1)``, then thread3()'s read from ``b`` must happen after
the beginning of thread2()'s grace period. If it is also the case
that ``(r2 == 1)``, then the end of thread1()'s grace period must
precede the beginning of thread2()'s grace period. This mean that
the two RCU read-side critical sections cannot overlap, guaranteeing
that ``(r3 == 1)``. As a result, the outcome:
::
(r1 == 1 && r2 == 1 && r3 == 0 && r4 == 1)
cannot happen.
This non-requirement was also non-premeditated, but became apparent when
studying RCU's interaction with memory ordering.
Read-Side Critical Sections Don't Partition Grace Periods
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
It is also tempting to assume that if an RCU read-side critical section
happens between a pair of grace periods, then those grace periods cannot
overlap. However, this temptation leads nowhere good, as can be
illustrated by the following, with all variables initially zero:
::
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(a, 1);
5 WRITE_ONCE(b, 1);
6 rcu_read_unlock();
7 }
8
9 void thread1(void)
10 {
11 r1 = READ_ONCE(a);
12 synchronize_rcu();
13 WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18 rcu_read_lock();
19 WRITE_ONCE(d, 1);
20 r2 = READ_ONCE(c);
21 rcu_read_unlock();
22 }
23
24 void thread3(void)
25 {
26 r3 = READ_ONCE(d);
27 synchronize_rcu();
28 WRITE_ONCE(e, 1);
29 }
30
31 void thread4(void)
32 {
33 rcu_read_lock();
34 r4 = READ_ONCE(b);
35 r5 = READ_ONCE(e);
36 rcu_read_unlock();
37 }
In this case, the outcome:
::
(r1 == 1 && r2 == 1 && r3 == 1 && r4 == 0 && r5 == 1)
is entirely possible, as illustrated below:
.. kernel-figure:: ReadersPartitionGP1.svg
Again, an RCU read-side critical section can overlap almost all of a
given grace period, just so long as it does not overlap the entire grace
period. As a result, an RCU read-side critical section cannot partition
a pair of RCU grace periods.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| How long a sequence of grace periods, each separated by an RCU |
| read-side critical section, would be required to partition the RCU |
| read-side critical sections at the beginning and end of the chain? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| In theory, an infinite number. In practice, an unknown number that is |
| sensitive to both implementation details and timing considerations. |
| Therefore, even in practice, RCU users must abide by the theoretical |
| rather than the practical answer. |
+-----------------------------------------------------------------------+
병렬 시스템의 현실
992-1041CPU와 task는 언제든 예측할 수 없는 시간 동안 지연될 수 있다. preemption이나 interrupt를 꺼도 hypervisor, ECC 처리, NMI 같은 더 높은 층의 지연은 남는다. RCU 알고리즘은 매우 긴 지연을 견뎌야 하며, 약 20초를 넘는 정체에는 진단 메시지를 내지만 무한 루프까지 해결할 수는 없다.
Compiler와 CPU는 access를 재정렬하므로 barrier와 명시적 accessor가 필요하다. 여러 CPU가 같은 cache line에 쓰면 비용이 커지므로 상태를 지역화해야 한다. 하나의 배타 락은 실질적으로 한 CPU 분량의 처리량만 허용하므로 수천 CPU에서 확장 가능한 자료구조가 필요하다.
모든 counter는 유한하므로 wraparound를 고려해야 한다. 예를 들어 dyntick nesting counter가 54비트를 쓰고 microsecond당 50만 번 interrupt된다는 극단적 가정에서도 wrap에는 약 570년이 걸리도록 설계한다. Linux는 수천 CPU의 공유 메모리 시스템을 지원하므로 이러한 범위와 확장성은 실제 요구사항이다.
현실설계 영향
임의 지연긴 reader와 CPU 정체 허용
재정렬accessor와 barrier 필요
cache-line 경쟁per-CPU 상태와 결합 트리 사용
유한 counter충분히 큰 범위와 wrap 처리
RCU 설계가 항상 고려해야 하는 제약이다.
Parallelism Facts of Life
-------------------------
These parallelism facts of life are by no means specific to RCU, but the
RCU implementation must abide by them. They therefore bear repeating:
#. Any CPU or task may be delayed at any time, and any attempts to avoid
these delays by disabling preemption, interrupts, or whatever are
completely futile. This is most obvious in preemptible user-level
environments and in virtualized environments (where a given guest
OS's VCPUs can be preempted at any time by the underlying
hypervisor), but can also happen in bare-metal environments due to
ECC errors, NMIs, and other hardware events. Although a delay of more
than about 20 seconds can result in splats, the RCU implementation is
obligated to use algorithms that can tolerate extremely long delays,
but where “extremely long” is not long enough to allow wrap-around
when incrementing a 64-bit counter.
#. Both the compiler and the CPU can reorder memory accesses. Where it
matters, RCU must use compiler directives and memory-barrier
instructions to preserve ordering.
#. Conflicting writes to memory locations in any given cache line will
result in expensive cache misses. Greater numbers of concurrent
writes and more-frequent concurrent writes will result in more
dramatic slowdowns. RCU is therefore obligated to use algorithms that
have sufficient locality to avoid significant performance and
scalability problems.
#. As a rough rule of thumb, only one CPU's worth of processing may be
carried out under the protection of any given exclusive lock. RCU
must therefore use scalable locking designs.
#. Counters are finite, especially on 32-bit systems. RCU's use of
counters must therefore tolerate counter wrap, or be designed such
that counter wrap would take way more time than a single system is
likely to run. An uptime of ten years is quite possible, a runtime of
a century much less so. As an example of the latter, RCU's
dyntick-idle nesting counter allows 54 bits for interrupt nesting
level (this counter is 64 bits even on a 32-bit system). Overflowing
this counter requires 2\ :sup:`54` half-interrupts on a given CPU
without that CPU ever going idle. If a half-interrupt happened every
microsecond, it would take 570 years of runtime to overflow this
counter, which is currently believed to be an acceptably long time.
#. Linux systems can have thousands of CPUs running a single Linux
kernel in a single shared-memory environment. RCU must therefore pay
close attention to high-end scalability.
This last parallelism fact of life means that RCU must pay special
attention to the preceding facts of life. The idea that Linux might
scale to systems with thousands of CPUs would have been met with some
skepticism in the 1990s, but these requirements would have otherwise
have been unsurprising, even in the early 1990s.
구현 품질과 read-mostly 특화
1042-1166기본 의미론만 맞아도 RCU라고 부를 수 있지만, 산업용 구현이 되려면 특화, 성능과 확장성, 전진 진행성, 조합 가능성, corner case 대응이라는 구현 품질 요구사항을 만족해야 한다. RCU는 본래 read-mostly workload를 위해 reader 비용을 최소화하고 updater 비용을 더 지불하는 방향으로 설계되었다.
오래되거나 일관되지 않은 데이터가 허용되는 read-mostly 자료에는 RCU가 매우 잘 맞는다. 일관성이 필요해도 read-mostly면 락과 결합해 잘 쓸 수 있다. read-write 비율이 비슷하면 적합성이 상황에 따라 달라지고, write-mostly 자료에는 대개 부적합하다. 예외는 갱신 친화적인 다른 기법에 존재 보장을 제공하거나 실시간 경로에 wait-free reader가 필요한 경우다.
RCU read-side critical section 안에서는 spinlock, sequence lock, atomic operation, reference count, memory barrier를 사용할 수 있다. 일반 Linux RCU reader 안의 sleeping lock은 금지되지만 userspace RCU와 SRCU에서는 허용된다. PREEMPT_RT가 spinlock을 sleeping lock으로 바꾼 경우는 특별히 지원되며, 즉시 성공하거나 실패하는 `mutex_trylock()`도 무한 재시도하지 않는 한 사용할 수 있다.
네트워크 라우팅처럼 외부 세계의 상태를 다루는 알고리즘은 빛의 속도와 통신 지연 때문에 본질적으로 일시적 불일치를 감수한다. 반면 제거된 System V semaphore를 갱신하는 일처럼 강한 일관성이 필요한 경로는 RCU로 존재를 보호한 뒤 객체 내부 spinlock을 잡는다. RCU의 강점은 모든 일관성을 혼자 제공하는 것이 아니라 다른 동기화 기법과 조합하는 데 있다.
Workload평가
Read-mostly, 불일치 허용매우 적합
Read-mostly, 일관성 필요락 등과 결합해 적합
Read-write, 일관성 필요설계에 따라 다름
Write-mostly대개 다른 기법 권장
읽기 비율과 일관성 요구를 함께 본다.
Quality-of-Implementation Requirements
--------------------------------------
These sections list quality-of-implementation requirements. Although an
RCU implementation that ignores these requirements could still be used,
it would likely be subject to limitations that would make it
inappropriate for industrial-strength production use. Classes of
quality-of-implementation requirements are as follows:
#. `Specialization`_
#. `Performance and Scalability`_
#. `Forward Progress`_
#. `Composability`_
#. `Corner Cases`_
These classes is covered in the following sections.
Specialization
~~~~~~~~~~~~~~
RCU is and always has been intended primarily for read-mostly
situations, which means that RCU's read-side primitives are optimized,
often at the expense of its update-side primitives. Experience thus far
is captured by the following list of situations:
#. Read-mostly data, where stale and inconsistent data is not a problem:
RCU works great!
#. Read-mostly data, where data must be consistent: RCU works well.
#. Read-write data, where data must be consistent: RCU *might* work OK.
Or not.
#. Write-mostly data, where data must be consistent: RCU is very
unlikely to be the right tool for the job, with the following
exceptions, where RCU can provide:
a. Existence guarantees for update-friendly mechanisms.
b. Wait-free read-side primitives for real-time use.
This focus on read-mostly situations means that RCU must interoperate
with other synchronization primitives. For example, the add_gp() and
remove_gp_synchronous() examples discussed earlier use RCU to
protect readers and locking to coordinate updaters. However, the need
extends much farther, requiring that a variety of synchronization
primitives be legal within RCU read-side critical sections, including
spinlocks, sequence locks, atomic operations, reference counters, and
memory barriers.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| What about sleeping locks? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| These are forbidden within Linux-kernel RCU read-side critical |
| sections because it is not legal to place a quiescent state (in this |
| case, voluntary context switch) within an RCU read-side critical |
| section. However, sleeping locks may be used within userspace RCU |
| read-side critical sections, and also within Linux-kernel sleepable |
| RCU `(SRCU) <Sleepable RCU_>`__ read-side critical sections. In |
| addition, the -rt patchset turns spinlocks into a sleeping locks so |
| that the corresponding critical sections can be preempted, which also |
| means that these sleeplockified spinlocks (but not other sleeping |
| locks!) may be acquire within -rt-Linux-kernel RCU read-side critical |
| sections. |
| Note that it *is* legal for a normal RCU read-side critical section |
| to conditionally acquire a sleeping locks (as in |
| mutex_trylock()), but only as long as it does not loop |
| indefinitely attempting to conditionally acquire that sleeping locks. |
| The key point is that things like mutex_trylock() either return |
| with the mutex held, or return an error indication if the mutex was |
| not immediately available. Either way, mutex_trylock() returns |
| immediately without sleeping. |
+-----------------------------------------------------------------------+
It often comes as a surprise that many algorithms do not require a
consistent view of data, but many can function in that mode, with
network routing being the poster child. Internet routing algorithms take
significant time to propagate updates, so that by the time an update
arrives at a given system, that system has been sending network traffic
the wrong way for a considerable length of time. Having a few threads
continue to send traffic the wrong way for a few more milliseconds is
clearly not a problem: In the worst case, TCP retransmissions will
eventually get the data where it needs to go. In general, when tracking
the state of the universe outside of the computer, some level of
inconsistency must be tolerated due to speed-of-light delays if nothing
else.
Furthermore, uncertainty about external state is inherent in many cases.
For example, a pair of veterinarians might use heartbeat to determine
whether or not a given cat was alive. But how long should they wait
after the last heartbeat to decide that the cat is in fact dead? Waiting
less than 400 milliseconds makes no sense because this would mean that a
relaxed cat would be considered to cycle between death and life more
than 100 times per minute. Moreover, just as with human beings, a cat's
heart might stop for some period of time, so the exact wait period is a
judgment call. One of our pair of veterinarians might wait 30 seconds
before pronouncing the cat dead, while the other might insist on waiting
a full minute. The two veterinarians would then disagree on the state of
the cat during the final 30 seconds of the minute following the last
heartbeat.
Interestingly enough, this same situation applies to hardware. When push
comes to shove, how do we tell whether or not some external server has
failed? We send messages to it periodically, and declare it failed if we
don't receive a response within a given period of time. Policy decisions
can usually tolerate short periods of inconsistency. The policy was
decided some time ago, and is only now being put into effect, so a few
milliseconds of delay is normally inconsequential.
However, there are algorithms that absolutely must see consistent data.
For example, the translation between a user-level SystemV semaphore ID
to the corresponding in-kernel data structure is protected by RCU, but
it is absolutely forbidden to update a semaphore that has just been
removed. In the Linux kernel, this need for consistency is accommodated
by acquiring spinlocks located in the in-kernel data structure from
within the RCU read-side critical section, and this is indicated by the
green box in the figure above. Many other techniques may be used, and
are in fact used within the Linux kernel.
In short, RCU is not required to maintain consistency, and other
mechanisms may be used in concert with RCU when consistency is required.
RCU's specialization allows it to do its job extremely well, and its
ability to interoperate with other synchronization mechanisms allows the
right mix of synchronization tools to be used for a given job.
성능, 확장성, 비동기 회수
1167-1410성능에는 에너지 효율도 포함된다. RCU는 idle CPU를 불필요하게 깨우지 않아야 한다. 반대로 작은 단일 CPU 시스템에서는 메모리 사용량이 중요해 Tiny RCU가 생겼고, kernel tinification 작업을 통해 필요하지 않은 커널에서는 SRCU도 선택 사항이 되었다.
`rcu_dereference()`는 몇 가지 compiler 최적화를 억제하는 정도의 비용이어야 하며, non-preemptible 환경의 `rcu_read_lock()`과 `rcu_read_unlock()`은 정확히 0의 실행 비용을 지향한다. preemptible 환경에서도 reader가 실제로 preempt되지 않았다면 atomic RMW, memory barrier 명령, preemption/interrupt disable, backward branch가 없어야 한다. 다만 preempt된 reader의 unlock 경로는 spinlock과 interrupt disable을 사용할 수 있다.
`synchronize_rcu()`는 낮은 단일 호출 지연보다 처리량을 우선하며, 여러 동시 호출을 한 grace period로 batch한다. 하나의 실제 GP가 1,000개가 넘는 호출을 처리할 수도 있다. 수 millisecond의 지연이 허용되지 않으면 `synchronize_rcu_expedited()`를 사용하지만, 4096 CPU의 호출 폭주에서도 전진해야 하고 online non-idle CPU에 scheduling-clock interrupt 정도의 제한된 실시간 지연만 허용된다.
기다리는 것 자체가 허용되지 않는 문맥에서는 `call_rcu()`를 사용한다. 예제의 `remove_gp_asynchronous()`는 포인터를 제거한 뒤 `struct rcu_head`를 `call_rcu()`에 넘기고 즉시 반환하며, callback `remove_gp_cb()`가 grace period 후 `kfree()`를 호출한다. callback은 softirq 문맥에서 실행될 수 있으므로 오래 걸리는 작업은 thread나 workqueue로 넘겨야 한다. NMI, idle CPU, offline CPU에서는 `call_rcu()`가 금지된다.
단순 해제는 `kfree_rcu()`로 줄일 수 있다. `call_rcu()`나 `kfree_rcu()`의 callback 자체는 GP를 기다리지만 updater는 등록 직후 다음 갱신으로 진행할 수 있으므로 reader에게 block된 것으로 보지 않는다. 중간에 다른 일을 한 뒤 필요할 때만 기다리려면 `get_state_synchronize_rcu()`로 cookie를 얻고 `cond_synchronize_rcu()`로 완료 여부를 확인한다.
synchronize_rcu(): batch 가능한 동기 대기→synchronize_rcu_expedited(): 더 짧은 동기 대기→call_rcu(): callback 비동기 실행→kfree_rcu(): 비동기 해제→get_state/cond_synchronize_rcu(): polling형 대기
지연, 문맥 제약, CPU 비용에 맞춰 API를 선택한다.
API호출자 대기대표 용도
synchronize_rcu()예일반 동기 회수
synchronize_rcu_expedited()예, 짧은 GP지연 민감 경로
call_rcu()아니요임의 callback
kfree_rcu()아니요객체 해제
cond_synchronize_rcu()이미 완료면 즉시대기 중 다른 작업 수행
모두 같은 수명 보장을 서로 다른 방식으로 제공한다.
Performance and Scalability
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Energy efficiency is a critical component of performance today, and
Linux-kernel RCU implementations must therefore avoid unnecessarily
awakening idle CPUs. I cannot claim that this requirement was
premeditated. In fact, I learned of it during a telephone conversation
in which I was given “frank and open” feedback on the importance of
energy efficiency in battery-powered systems and on specific
energy-efficiency shortcomings of the Linux-kernel RCU implementation.
In my experience, the battery-powered embedded community will consider
any unnecessary wakeups to be extremely unfriendly acts. So much so that
mere Linux-kernel-mailing-list posts are insufficient to vent their ire.
Memory consumption is not particularly important for in most situations,
and has become decreasingly so as memory sizes have expanded and memory
costs have plummeted. However, as I learned from Matt Mackall's
`bloatwatch <http://elinux.org/Linux_Tiny-FAQ>`__ efforts, memory
footprint is critically important on single-CPU systems with
non-preemptible (``CONFIG_PREEMPTION=n``) kernels, and thus `tiny
RCU <https://lore.kernel.org/r/[email protected]>`__
was born. Josh Triplett has since taken over the small-memory banner
with his `Linux kernel tinification <https://tiny.wiki.kernel.org/>`__
project, which resulted in `SRCU <Sleepable RCU_>`__ becoming optional
for those kernels not needing it.
The remaining performance requirements are, for the most part,
unsurprising. For example, in keeping with RCU's read-side
specialization, rcu_dereference() should have negligible overhead
(for example, suppression of a few minor compiler optimizations).
Similarly, in non-preemptible environments, rcu_read_lock() and
rcu_read_unlock() should have exactly zero overhead.
In preemptible environments, in the case where the RCU read-side
critical section was not preempted (as will be the case for the
highest-priority real-time process), rcu_read_lock() and
rcu_read_unlock() should have minimal overhead. In particular, they
should not contain atomic read-modify-write operations, memory-barrier
instructions, preemption disabling, interrupt disabling, or backwards
branches. However, in the case where the RCU read-side critical section
was preempted, rcu_read_unlock() may acquire spinlocks and disable
interrupts. This is why it is better to nest an RCU read-side critical
section within a preempt-disable region than vice versa, at least in
cases where that critical section is short enough to avoid unduly
degrading real-time latencies.
The synchronize_rcu() grace-period-wait primitive is optimized for
throughput. It may therefore incur several milliseconds of latency in
addition to the duration of the longest RCU read-side critical section.
On the other hand, multiple concurrent invocations of
synchronize_rcu() are required to use batching optimizations so that
they can be satisfied by a single underlying grace-period-wait
operation. For example, in the Linux kernel, it is not unusual for a
single grace-period-wait operation to serve more than `1,000 separate
invocations <https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response>`__
of synchronize_rcu(), thus amortizing the per-invocation overhead
down to nearly zero. However, the grace-period optimization is also
required to avoid measurable degradation of real-time scheduling and
interrupt latencies.
In some cases, the multi-millisecond synchronize_rcu() latencies are
unacceptable. In these cases, synchronize_rcu_expedited() may be
used instead, reducing the grace-period latency down to a few tens of
microseconds on small systems, at least in cases where the RCU read-side
critical sections are short. There are currently no special latency
requirements for synchronize_rcu_expedited() on large systems, but,
consistent with the empirical nature of the RCU specification, that is
subject to change. However, there most definitely are scalability
requirements: A storm of synchronize_rcu_expedited() invocations on
4096 CPUs should at least make reasonable forward progress. In return
for its shorter latencies, synchronize_rcu_expedited() is permitted
to impose modest degradation of real-time latency on non-idle online
CPUs. Here, “modest” means roughly the same latency degradation as a
scheduling-clock interrupt.
There are a number of situations where even
synchronize_rcu_expedited()'s reduced grace-period latency is
unacceptable. In these situations, the asynchronous call_rcu() can
be used in place of synchronize_rcu() as follows:
::
1 struct foo {
2 int a;
3 int b;
4 struct rcu_head rh;
5 };
6
7 static void remove_gp_cb(struct rcu_head *rhp)
8 {
9 struct foo *p = container_of(rhp, struct foo, rh);
10
11 kfree(p);
12 }
13
14 bool remove_gp_asynchronous(void)
15 {
16 struct foo *p;
17
18 spin_lock(&gp_lock);
19 p = rcu_access_pointer(gp);
20 if (!p) {
21 spin_unlock(&gp_lock);
22 return false;
23 }
24 rcu_assign_pointer(gp, NULL);
25 call_rcu(&p->rh, remove_gp_cb);
26 spin_unlock(&gp_lock);
27 return true;
28 }
A definition of ``struct foo`` is finally needed, and appears on
lines 1-5. The function remove_gp_cb() is passed to call_rcu()
on line 25, and will be invoked after the end of a subsequent grace
period. This gets the same effect as remove_gp_synchronous(), but
without forcing the updater to wait for a grace period to elapse. The
call_rcu() function may be used in a number of situations where
neither synchronize_rcu() nor synchronize_rcu_expedited() would
be legal, including within preempt-disable code, local_bh_disable()
code, interrupt-disable code, and interrupt handlers. However, even
call_rcu() is illegal within NMI handlers and from idle and offline
CPUs. The callback function (remove_gp_cb() in this case) will be
executed within softirq (software interrupt) environment within the
Linux kernel, either within a real softirq handler or under the
protection of local_bh_disable(). In both the Linux kernel and in
userspace, it is bad practice to write an RCU callback function that
takes too long. Long-running operations should be relegated to separate
threads or (in the Linux kernel) workqueues.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Why does line 19 use rcu_access_pointer()? After all, |
| call_rcu() on line 25 stores into the structure, which would |
| interact badly with concurrent insertions. Doesn't this mean that |
| rcu_dereference() is required? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Presumably the ``->gp_lock`` acquired on line 18 excludes any |
| changes, including any insertions that rcu_dereference() would |
| protect against. Therefore, any insertions will be delayed until |
| after ``->gp_lock`` is released on line 25, which in turn means that |
| rcu_access_pointer() suffices. |
+-----------------------------------------------------------------------+
However, all that remove_gp_cb() is doing is invoking kfree() on
the data element. This is a common idiom, and is supported by
kfree_rcu(), which allows “fire and forget” operation as shown
below:
::
1 struct foo {
2 int a;
3 int b;
4 struct rcu_head rh;
5 };
6
7 bool remove_gp_faf(void)
8 {
9 struct foo *p;
10
11 spin_lock(&gp_lock);
12 p = rcu_dereference(gp);
13 if (!p) {
14 spin_unlock(&gp_lock);
15 return false;
16 }
17 rcu_assign_pointer(gp, NULL);
18 kfree_rcu(p, rh);
19 spin_unlock(&gp_lock);
20 return true;
21 }
Note that remove_gp_faf() simply invokes kfree_rcu() and
proceeds, without any need to pay any further attention to the
subsequent grace period and kfree(). It is permissible to invoke
kfree_rcu() from the same environments as for call_rcu().
Interestingly enough, DYNIX/ptx had the equivalents of call_rcu()
and kfree_rcu(), but not synchronize_rcu(). This was due to the
fact that RCU was not heavily used within DYNIX/ptx, so the very few
places that needed something like synchronize_rcu() simply
open-coded it.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Earlier it was claimed that call_rcu() and kfree_rcu() |
| allowed updaters to avoid being blocked by readers. But how can that |
| be correct, given that the invocation of the callback and the freeing |
| of the memory (respectively) must still wait for a grace period to |
| elapse? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| We could define things this way, but keep in mind that this sort of |
| definition would say that updates in garbage-collected languages |
| cannot complete until the next time the garbage collector runs, which |
| does not seem at all reasonable. The key point is that in most cases, |
| an updater using either call_rcu() or kfree_rcu() can proceed |
| to the next update as soon as it has invoked call_rcu() or |
| kfree_rcu(), without having to wait for a subsequent grace |
| period. |
+-----------------------------------------------------------------------+
But what if the updater must wait for the completion of code to be
executed after the end of the grace period, but has other tasks that can
be carried out in the meantime? The polling-style
get_state_synchronize_rcu() and cond_synchronize_rcu() functions
may be used for this purpose, as shown below:
::
1 bool remove_gp_poll(void)
2 {
3 struct foo *p;
4 unsigned long s;
5
6 spin_lock(&gp_lock);
7 p = rcu_access_pointer(gp);
8 if (!p) {
9 spin_unlock(&gp_lock);
10 return false;
11 }
12 rcu_assign_pointer(gp, NULL);
13 spin_unlock(&gp_lock);
14 s = get_state_synchronize_rcu();
15 do_something_while_waiting();
16 cond_synchronize_rcu(s);
17 kfree(p);
18 return true;
19 }
On line 14, get_state_synchronize_rcu() obtains a “cookie” from RCU,
then line 15 carries out other tasks, and finally, line 16 returns
immediately if a grace period has elapsed in the meantime, but otherwise
waits as required. The need for ``get_state_synchronize_rcu`` and
cond_synchronize_rcu() has appeared quite recently, so it is too
early to tell whether they will stand the test of time.
RCU thus provides a range of tools to allow updaters to strike the
required tradeoff between latency, flexibility and CPU overhead.
전진 진행성
1411-1488grace period나 callback을 이론상 오래 늦춰도 의미론은 깨지지 않을 수 있지만, 실제 메모리는 유한하고 callback이 wakeup을 수행하기도 한다. 지나친 지연은 시스템 정지와 구분되지 않으므로 RCU는 적시에 GP와 callback이 끝나도록 적극적으로 개입한다. 다만 reader 안의 무한 루프나 63개 CPU가 한 CPU의 callback 처리 능력보다 빠르게 `call_rcu()`를 등록하는 식의 무제한 남용까지 해결할 수는 없다.
기본 `HZ=1000`에서 GP가 100ms를 넘으면 holdout CPU의 `cond_resched()`가 quiescent state를 제공하도록 하고 `need_resched()`도 다음 tick 뒤 true가 되게 한다. `nohz_full` CPU가 109ms까지 버티면 `resched_cpu()`를 보내며, `CONFIG_RCU_BOOST=y`에서 preempt된 reader가 500ms를 넘으면 priority boost를 사용한다. 10초까지 남은 CPU에는 `nohz_full` 여부와 관계없이 reschedule을 요청한다.
non-`rcu_nocbs` CPU에 callback이 10,000개 쌓이거나 지난 개입 뒤 10,000개가 더 늘면 GP를 즉시 시작하고, QS 검사를 당기고, callback에 GP 번호를 즉시 붙이며, callback batch 제한을 해제한다. 이 기본값은 조정할 수 있다. SRCU와 Tasks RCU에는 같은 전진 진행 조치가 자동으로 적용되지 않으며, `rcu_nocbs` CPU의 callback 폭주 대응도 추가 개선 여지가 있다.
조건조치
GP 100mscond_resched/need_resched로 QS 유도
nohz_full 109msresched_cpu()
preempted reader 500msRCU priority boost
holdout 10s강제 resched_cpu()
callback 10,000개GP/QS/callback 처리를 공격적으로 가속
HZ=1000 기준이며 설정에 따라 달라질 수 있다.
Forward Progress
~~~~~~~~~~~~~~~~
In theory, delaying grace-period completion and callback invocation is
harmless. In practice, not only are memory sizes finite but also
callbacks sometimes do wakeups, and sufficiently deferred wakeups can be
difficult to distinguish from system hangs. Therefore, RCU must provide
a number of mechanisms to promote forward progress.
These mechanisms are not foolproof, nor can they be. For one simple
example, an infinite loop in an RCU read-side critical section must by
definition prevent later grace periods from ever completing. For a more
involved example, consider a 64-CPU system built with
``CONFIG_RCU_NOCB_CPU=y`` and booted with ``rcu_nocbs=1-63``, where
CPUs 1 through 63 spin in tight loops that invoke call_rcu(). Even
if these tight loops also contain calls to cond_resched() (thus
allowing grace periods to complete), CPU 0 simply will not be able to
invoke callbacks as fast as the other 63 CPUs can register them, at
least not until the system runs out of memory. In both of these
examples, the Spiderman principle applies: With great power comes great
responsibility. However, short of this level of abuse, RCU is required
to ensure timely completion of grace periods and timely invocation of
callbacks.
RCU takes the following steps to encourage timely completion of grace
periods:
#. If a grace period fails to complete within 100 milliseconds, RCU
causes future invocations of cond_resched() on the holdout CPUs
to provide an RCU quiescent state. RCU also causes those CPUs'
need_resched() invocations to return ``true``, but only after the
corresponding CPU's next scheduling-clock.
#. CPUs mentioned in the ``nohz_full`` kernel boot parameter can run
indefinitely in the kernel without scheduling-clock interrupts, which
defeats the above need_resched() strategem. RCU will therefore
invoke resched_cpu() on any ``nohz_full`` CPUs still holding out
after 109 milliseconds.
#. In kernels built with ``CONFIG_RCU_BOOST=y``, if a given task that
has been preempted within an RCU read-side critical section is
holding out for more than 500 milliseconds, RCU will resort to
priority boosting.
#. If a CPU is still holding out 10 seconds into the grace period, RCU
will invoke resched_cpu() on it regardless of its ``nohz_full``
state.
The above values are defaults for systems running with ``HZ=1000``. They
will vary as the value of ``HZ`` varies, and can also be changed using
the relevant Kconfig options and kernel boot parameters. RCU currently
does not do much sanity checking of these parameters, so please use
caution when changing them. Note that these forward-progress measures
are provided only for RCU, not for `SRCU <Sleepable RCU_>`__ or `Tasks
RCU`_.
RCU takes the following steps in call_rcu() to encourage timely
invocation of callbacks when any given non-\ ``rcu_nocbs`` CPU has
10,000 callbacks, or has 10,000 more callbacks than it had the last time
encouragement was provided:
#. Starts a grace period, if one is not already in progress.
#. Forces immediate checking for quiescent states, rather than waiting
for three milliseconds to have elapsed since the beginning of the
grace period.
#. Immediately tags the CPU's callbacks with their grace period
completion numbers, rather than waiting for the ``RCU_SOFTIRQ``
handler to get around to it.
#. Lifts callback-execution batch limits, which speeds up callback
invocation at the expense of degrading realtime response.
Again, these are default values when running at ``HZ=1000``, and can be
overridden. Again, these forward-progress measures are provided only for
RCU, not for `SRCU <Sleepable RCU_>`__ or `Tasks
RCU`_. Even for RCU, callback-invocation forward
progress for ``rcu_nocbs`` CPUs is much less well-developed, in part
because workloads benefiting from ``rcu_nocbs`` CPUs tend to invoke
call_rcu() relatively infrequently. If workloads emerge that need
both ``rcu_nocbs`` CPUs and high call_rcu() invocation rates, then
additional forward-progress work will be required.
조합 가능성
1489-1537RCU read-side critical section은 서로 조합하고 임의로 중첩할 수 있다. `CONFIG_PREEMPTION=n`처럼 marker가 코드를 만들지 않는 구현에서는 실행 비용 관점의 중첩 깊이 제한이 없다. 다만 compiler가 모든 중첩을 보면 자원 고갈로 compile이 실패할 수 있고, 재귀 호출이면 stack overflow, 무한 반복이면 counter overflow나 RCU CPU stall이 생길 수 있다.
중첩 깊이를 명시적으로 추적하는 preemptible RCU는 `INT_MAX`까지 제한된다. 실용적으로 충분히 크지만, grace period를 기다리는 연산을 사이에 둔 두 read-side critical section을 더 바깥 RCU reader로 감쌀 수는 없다. RCU reader 안에서 GP를 기다리면 deadlock이 생기거나 바깥 critical section이 암묵적으로 쪼개진다.
이 제한은 RCU만의 약점이 아니다. Transactional memory도 취소할 수 없는 연산 사이의 transaction 조합을 금지할 수 있고, 락 기반 critical section도 deadlock을 피할 때만 자유롭게 조합된다. RCU는 매우 조합 가능하지만 기다림의 의존 관계는 별도로 검토해야 한다.
외부 rcu_read_lock()→내부 reader 작업→GP를 기다리지 않는 연산→내부 rcu_read_unlock()→외부 rcu_read_unlock()
중첩 자체보다 grace-period wait 의존성이 문제다.
Composability
~~~~~~~~~~~~~
Composability has received much attention in recent years, perhaps in
part due to the collision of multicore hardware with object-oriented
techniques designed in single-threaded environments for single-threaded
use. And in theory, RCU read-side critical sections may be composed, and
in fact may be nested arbitrarily deeply. In practice, as with all
real-world implementations of composable constructs, there are
limitations.
Implementations of RCU for which rcu_read_lock() and
rcu_read_unlock() generate no code, such as Linux-kernel RCU when
``CONFIG_PREEMPTION=n``, can be nested arbitrarily deeply. After all, there
is no overhead. Except that if all these instances of
rcu_read_lock() and rcu_read_unlock() are visible to the
compiler, compilation will eventually fail due to exhausting memory,
mass storage, or user patience, whichever comes first. If the nesting is
not visible to the compiler, as is the case with mutually recursive
functions each in its own translation unit, stack overflow will result.
If the nesting takes the form of loops, perhaps in the guise of tail
recursion, either the control variable will overflow or (in the Linux
kernel) you will get an RCU CPU stall warning. Nevertheless, this class
of RCU implementations is one of the most composable constructs in
existence.
RCU implementations that explicitly track nesting depth are limited by
the nesting-depth counter. For example, the Linux kernel's preemptible
RCU limits nesting to ``INT_MAX``. This should suffice for almost all
practical purposes. That said, a consecutive pair of RCU read-side
critical sections between which there is an operation that waits for a
grace period cannot be enclosed in another RCU read-side critical
section. This is because it is not legal to wait for a grace period
within an RCU read-side critical section: To do so would result either
in deadlock or in RCU implicitly splitting the enclosing RCU read-side
critical section, neither of which is conducive to a long-lived and
prosperous kernel.
It is worth noting that RCU is not alone in limiting composability. For
example, many transactional-memory implementations prohibit composing a
pair of transactions separated by an irrevocable operation (for example,
a network receive operation). For another example, lock-based critical
sections can be composed surprisingly freely, but only if deadlock is
avoided.
In short, although RCU read-side critical sections are highly
composable, care is required in some situations, just as is the case for
any other composable synchronization mechanism.
Corner case
1538-1580항상 하나 이상의 유한한 RCU reader가 실행 중인 workload라도 grace period는 끝나야 한다. RCU는 모든 reader가 동시에 사라지는 순간을 기다리지 않고, GP 시작 전에 존재한 reader만 추적하기 때문에 이를 만족한다. 단, preemptible RCU에서 reader task가 오랫동안 preempt되면 실제로 긴 reader가 되므로 priority boosting이 필요할 수 있다.
매우 높은 update rate도 정상적으로 처리해야 한다. 이 요구가 grace-period batching과 `call_rcu()` 경로의 callback 수 검사를 낳았다. `synchronize_rcu_expedited()`가 사용하는 `smp_call_function_single()` 때문에 작은 reader 지연은 생길 수 있지만, 일반적인 높은 update rate가 reader를 지연해서는 안 된다.
2000년대 초 `close(open(path))`를 tight loop로 실행한 단순 시험은 callback 폭주 문제를 실제로 드러냈다. 한 CPU에 10,000개가 넘는 callback이 쌓이면 RCU가 GP 시작과 QS 강제를 가속한다. GP는 빨라지지만 batching 기회를 줄여 CPU 비용은 늘어난다.
상황RCU 대응
reader가 끊임없이 이어짐기존 reader 집합만 기다림
reader가 장기 preemptpriority boosting
update/callback 폭주GP 시작과 QS 처리 가속
expedited GP 폭주진행은 보장하되 제한된 지연 허용
정확성과 처리량 사이의 방어 동작이다.
Corner Cases
~~~~~~~~~~~~
A given RCU workload might have an endless and intense stream of RCU
read-side critical sections, perhaps even so intense that there was
never a point in time during which there was not at least one RCU
read-side critical section in flight. RCU cannot allow this situation to
block grace periods: As long as all the RCU read-side critical sections
are finite, grace periods must also be finite.
That said, preemptible RCU implementations could potentially result in
RCU read-side critical sections being preempted for long durations,
which has the effect of creating a long-duration RCU read-side critical
section. This situation can arise only in heavily loaded systems, but
systems using real-time priorities are of course more vulnerable.
Therefore, RCU priority boosting is provided to help deal with this
case. That said, the exact requirements on RCU priority boosting will
likely evolve as more experience accumulates.
Other workloads might have very high update rates. Although one can
argue that such workloads should instead use something other than RCU,
the fact remains that RCU must handle such workloads gracefully. This
requirement is another factor driving batching of grace periods, but it
is also the driving force behind the checks for large numbers of queued
RCU callbacks in the call_rcu() code path. Finally, high update
rates should not delay RCU read-side critical sections, although some
small read-side delays can occur when using
synchronize_rcu_expedited(), courtesy of this function's use of
smp_call_function_single().
Although all three of these corner cases were understood in the early
1990s, a simple user-level test consisting of ``close(open(path))`` in a
tight loop in the early 2000s suddenly provided a much deeper
appreciation of the high-update-rate corner case. This test also
motivated addition of some RCU code to react to high update rates, for
example, if a given CPU finds itself with more than 10,000 RCU callbacks
queued, it will cause RCU to take evasive action by more aggressively
starting grace periods and more aggressively forcing completion of
grace-period processing. This evasive action causes the grace period to
complete more quickly, but at the cost of restricting RCU's batching
optimizations, thus increasing the CPU overhead incurred by that grace
period.
소프트웨어 공학과 진단
1581-1678`CONFIG_PROVE_RCU=y`는 보호 구간 밖의 `rcu_dereference()`를 lockdep 경고로 찾는다. updater는 보호 조건을 표현하는 `rcu_dereference_protected()`를, reader와 updater가 공유하는 코드는 `rcu_dereference_check()`를 사용한다. 표현하기 어려운 드문 경우에는 `rcu_dereference_raw()`가 있으며, `rcu_read_lock_held()`와 `rcu_lockdep_assert()`로 진입 전제조건을 확인할 수 있다.
RCU 포인터에 `__rcu`를 붙이면 sparse가 평범한 대입과 역참조를 경고한다. `CONFIG_DEBUG_OBJECTS_RCU_HEAD=y`는 같은 `rcu_head`를 GP 없이 두 번 `call_rcu()`에 넘기는 double-free 유사 오류를 찾는다. stack 객체는 `init_rcu_head_on_stack()`과 `destroy_rcu_head_on_stack()`, 정적 non-stack 객체는 `init_rcu_head()`와 `destroy_rcu_head()`로 수명을 알린다.
무한 reader는 `RCU_CPU_STALL_TIMEOUT` 또는 `rcupdate.rcu_cpu_stall_timeout` 뒤 stall warning을 낸다. 의도적으로 GP를 늦추는 workload는 `rcupdate.rcu_cpu_stall_suppress`로 억제할 수 있다. 긴 sysrq dump 전후에는 `rcu_sysrq_start()`와 `rcu_sysrq_end()`를 쓰고, panic 시작에는 `rcu_panic()`이 추가 경고를 막는다.
RCU reader 밖으로 새는 포인터와 락 또는 reference count로 합법적으로 handoff한 포인터를 일반적으로 구분할 방법은 아직 없다. 대신 `CONFIG_RCU_TRACE=y` event tracing, RCU list/hash API, `RCU_POINTER_INITIALIZER()`, `RCU_INIT_POINTER()` 같은 도구로 직접 accessor를 조합할 때의 오류를 줄인다. 진단 요구사항은 실제 버그가 발견되는 양상에 따라 계속 발전한다.
도구찾는 문제
lockdep / CONFIG_PROVE_RCU보호 구간과 전제조건 위반
sparse / __rcu잘못된 포인터 대입과 역참조
DEBUG_OBJECTS_RCU_HEAD중복 callback 등록과 객체 수명 오류
CPU stall warning오래 끝나지 않는 reader/GP
RCU trace events실행 중 상태 분석
오용 유형별로 compiler와 runtime 진단을 결합한다.
Software-Engineering Requirements
---------------------------------
Between Murphy's Law and “To err is human”, it is necessary to guard
against mishaps and misuse:
#. It is all too easy to forget to use rcu_read_lock() everywhere
that it is needed, so kernels built with ``CONFIG_PROVE_RCU=y`` will
splat if rcu_dereference() is used outside of an RCU read-side
critical section. Update-side code can use
rcu_dereference_protected(), which takes a `lockdep
expression <https://lwn.net/Articles/371986/>`__ to indicate what is
providing the protection. If the indicated protection is not
provided, a lockdep splat is emitted.
Code shared between readers and updaters can use
rcu_dereference_check(), which also takes a lockdep expression,
and emits a lockdep splat if neither rcu_read_lock() nor the
indicated protection is in place. In addition,
rcu_dereference_raw() is used in those (hopefully rare) cases
where the required protection cannot be easily described. Finally,
rcu_read_lock_held() is provided to allow a function to verify
that it has been invoked within an RCU read-side critical section. I
was made aware of this set of requirements shortly after Thomas
Gleixner audited a number of RCU uses.
#. A given function might wish to check for RCU-related preconditions
upon entry, before using any other RCU API. The
rcu_lockdep_assert() does this job, asserting the expression in
kernels having lockdep enabled and doing nothing otherwise.
#. It is also easy to forget to use rcu_assign_pointer() and
rcu_dereference(), perhaps (incorrectly) substituting a simple
assignment. To catch this sort of error, a given RCU-protected
pointer may be tagged with ``__rcu``, after which sparse will
complain about simple-assignment accesses to that pointer. Arnd
Bergmann made me aware of this requirement, and also supplied the
needed `patch series <https://lwn.net/Articles/376011/>`__.
#. Kernels built with ``CONFIG_DEBUG_OBJECTS_RCU_HEAD=y`` will splat if
a data element is passed to call_rcu() twice in a row, without a
grace period in between. (This error is similar to a double free.)
The corresponding ``rcu_head`` structures that are dynamically
allocated are automatically tracked, but ``rcu_head`` structures
allocated on the stack must be initialized with
init_rcu_head_on_stack() and cleaned up with
destroy_rcu_head_on_stack(). Similarly, statically allocated
non-stack ``rcu_head`` structures must be initialized with
init_rcu_head() and cleaned up with destroy_rcu_head().
Mathieu Desnoyers made me aware of this requirement, and also
supplied the needed
`patch <https://lore.kernel.org/r/20100319013024.GA28456@Krystal>`__.
#. An infinite loop in an RCU read-side critical section will eventually
trigger an RCU CPU stall warning splat, with the duration of
“eventually” being controlled by the ``RCU_CPU_STALL_TIMEOUT``
``Kconfig`` option, or, alternatively, by the
``rcupdate.rcu_cpu_stall_timeout`` boot/sysfs parameter. However, RCU
is not obligated to produce this splat unless there is a grace period
waiting on that particular RCU read-side critical section.
Some extreme workloads might intentionally delay RCU grace periods,
and systems running those workloads can be booted with
``rcupdate.rcu_cpu_stall_suppress`` to suppress the splats. This
kernel parameter may also be set via ``sysfs``. Furthermore, RCU CPU
stall warnings are counter-productive during sysrq dumps and during
panics. RCU therefore supplies the rcu_sysrq_start() and
rcu_sysrq_end() API members to be called before and after long
sysrq dumps. RCU also supplies the rcu_panic() notifier that is
automatically invoked at the beginning of a panic to suppress further
RCU CPU stall warnings.
This requirement made itself known in the early 1990s, pretty much
the first time that it was necessary to debug a CPU stall. That said,
the initial implementation in DYNIX/ptx was quite generic in
comparison with that of Linux.
#. Although it would be very good to detect pointers leaking out of RCU
read-side critical sections, there is currently no good way of doing
this. One complication is the need to distinguish between pointers
leaking and pointers that have been handed off from RCU to some other
synchronization mechanism, for example, reference counting.
#. In kernels built with ``CONFIG_RCU_TRACE=y``, RCU-related information
is provided via event tracing.
#. Open-coded use of rcu_assign_pointer() and rcu_dereference()
to create typical linked data structures can be surprisingly
error-prone. Therefore, RCU-protected `linked
lists <https://lwn.net/Articles/609973/#RCU%20List%20APIs>`__ and,
more recently, RCU-protected `hash
tables <https://lwn.net/Articles/612100/>`__ are available. Many
other special-purpose RCU-protected data structures are available in
the Linux kernel and the userspace RCU library.
#. Some linked structures are created at compile time, but still require
``__rcu`` checking. The RCU_POINTER_INITIALIZER() macro serves
this purpose.
#. It is not necessary to use rcu_assign_pointer() when creating
linked structures that are to be published via a single external
pointer. The RCU_INIT_POINTER() macro is provided for this task.
This not a hard-and-fast list: RCU's diagnostic capabilities will
continue to be guided by the number and type of usage bugs found in
real-world RCU usage.
Linux 구성과 firmware
1679-1741Linux 커널에서 RCU는 구성, firmware, 초기 부팅, interrupt/NMI, module, CPU hotplug, scheduler, tracing, user memory, 에너지, tick, 메모리, 성능과 신뢰성까지 폭넓은 환경과 맞물린다. 이 목록은 완전하지 않지만 RCU가 단순 library가 아니라 커널 전체의 실행 상태를 추적하는 subsystem임을 보여 준다.
RCU의 목표는 대부분의 사용자가 `Kconfig`를 신경 쓰지 않는 자동 구성이다. 전문적인 use case만 boot parameter와 옵션으로 노출하며, 새 옵션이 일반 사용자에게 무조건 질문되지 않도록 대부분 `CONFIG_RCU_EXPERT` 뒤에 숨긴다.
Firmware가 CPU 수를 과장하면 RCU가 존재하지 않는 CPU마다 per-CPU kthread를 만들 수 있다. 시스템은 동작해도 메모리를 낭비하고 `ps` 출력을 혼란스럽게 한다. 그래서 CPU가 실제 online이 되기 전에는 존재한다고 믿지 않으며, firmware에만 나타나고 결코 online 되지 않는 ghost CPU도 안전하게 처리한다.
Firmware가 CPU 기술→RCU는 즉시 확정하지 않음→CPU online 통지→per-CPU RCU 상태 활성화→미등장 CPU는 ghost로 유지
Firmware 정보는 후보일 뿐 실제 hotplug 사건으로 확정한다.
Linux Kernel Complications
--------------------------
The Linux kernel provides an interesting environment for all kinds of
software, including RCU. Some of the relevant points of interest are as
follows:
#. `Configuration`_
#. `Firmware Interface`_
#. `Early Boot`_
#. `Interrupts and NMIs`_
#. `Loadable Modules`_
#. `Hotplug CPU`_
#. `Scheduler and RCU`_
#. `Tracing and RCU`_
#. `Accesses to User Memory and RCU`_
#. `Energy Efficiency`_
#. `Scheduling-Clock Interrupts and RCU`_
#. `Memory Efficiency`_
#. `Performance, Scalability, Response Time, and Reliability`_
This list is probably incomplete, but it does give a feel for the most
notable Linux-kernel complications. Each of the following sections
covers one of the above topics.
Configuration
~~~~~~~~~~~~~
RCU's goal is automatic configuration, so that almost nobody needs to
worry about RCU's ``Kconfig`` options. And for almost all users, RCU
does in fact work well “out of the box.”
However, there are specialized use cases that are handled by kernel boot
parameters and ``Kconfig`` options. Unfortunately, the ``Kconfig``
system will explicitly ask users about new ``Kconfig`` options, which
requires almost all of them be hidden behind a ``CONFIG_RCU_EXPERT``
``Kconfig`` option.
This all should be quite obvious, but the fact remains that Linus
Torvalds recently had to
`remind <https://lore.kernel.org/r/CA+55aFy4wcCwaL4okTs8wXhGZ5h-ibecy_Meg9C4MNQrUnwMcg@mail.gmail.com>`__
me of this requirement.
Firmware Interface
~~~~~~~~~~~~~~~~~~
In many cases, kernel obtains information about the system from the
firmware, and sometimes things are lost in translation. Or the
translation is accurate, but the original message is bogus.
For example, some systems' firmware overreports the number of CPUs,
sometimes by a large factor. If RCU naively believed the firmware, as it
used to do, it would create too many per-CPU kthreads. Although the
resulting system will still run correctly, the extra kthreads needlessly
consume memory and can cause confusion when they show up in ``ps``
listings.
RCU must therefore wait for a given CPU to actually come online before
it can allow itself to believe that the CPU actually exists. The
resulting “ghost CPUs” (which are never going to come online) cause a
number of `interesting
complications <https://paulmck.livejournal.com/37494.html>`__.
초기 부팅
1742-1817RCU는 `rcu_init()` 이전부터 사용된다. 초기 task의 `task_struct`와 boot CPU의 per-CPU 변수가 준비되면 `rcu_read_lock()`, `rcu_read_unlock()`, `rcu_dereference()`, `rcu_access_pointer()`, `rcu_assign_pointer()`가 정상 의미로 동작한다.
`call_rcu()`는 부팅 중 언제든 등록할 수 있지만 callback 실행은 `early_initcall()` 무렵 RCU kthread가 모두 만들어진 뒤까지 늦어질 수 있다. Scheduler가 충분히 초기화되기 전에는 callback이 호출할 수 있는 기능도 제한되므로 조기 실행이 항상 이득은 아니다.
아주 이른 부팅에는 CPU가 하나이고 preemption이 꺼져 있어 `synchronize_rcu()`와 `synchronize_rcu_expedited()` 호출 자체가 quiescent state가 되므로 no-op처럼 처리할 수 있다. 하지만 scheduler가 첫 kthread를 만든 뒤 모든 RCU kthread가 준비되기 전의 dead zone에서는 preempted reader가 생길 수 있다.
이 dead zone의 synchronous GP는 expedited mechanism으로 처리하며, 평소 workqueue가 하던 진행을 요청 task가 직접 구동한다. 모든 kthread가 준비되면 expedited GP는 다시 workqueue를 사용한다. 이 구간에 임의 task로 POSIX signal을 보내는 것은 도움이 되지 않으며, 요구가 생기면 구현을 조정해야 한다.
단일 boot CPU: 동기 GP는 no-op 가능→첫 scheduler kthread 생성→Dead zone: 요청 task가 expedited GP 구동→RCU kthread 모두 준비→정상 runtime GP
초기화 진행에 따라 같은 API의 내부 경로가 바뀐다.
Early Boot
~~~~~~~~~~
The Linux kernel's boot sequence is an interesting process, and RCU is
used early, even before rcu_init() is invoked. In fact, a number of
RCU's primitives can be used as soon as the initial task's
``task_struct`` is available and the boot CPU's per-CPU variables are
set up. The read-side primitives (rcu_read_lock(),
rcu_read_unlock(), rcu_dereference(), and
rcu_access_pointer()) will operate normally very early on, as will
rcu_assign_pointer().
Although call_rcu() may be invoked at any time during boot,
callbacks are not guaranteed to be invoked until after all of RCU's
kthreads have been spawned, which occurs at early_initcall() time.
This delay in callback invocation is due to the fact that RCU does not
invoke callbacks until it is fully initialized, and this full
initialization cannot occur until after the scheduler has initialized
itself to the point where RCU can spawn and run its kthreads. In theory,
it would be possible to invoke callbacks earlier, however, this is not a
panacea because there would be severe restrictions on what operations
those callbacks could invoke.
Perhaps surprisingly, synchronize_rcu() and
synchronize_rcu_expedited(), will operate normally during very early
boot, the reason being that there is only one CPU and preemption is
disabled. This means that the call synchronize_rcu() (or friends)
itself is a quiescent state and thus a grace period, so the early-boot
implementation can be a no-op.
However, once the scheduler has spawned its first kthread, this early
boot trick fails for synchronize_rcu() (as well as for
synchronize_rcu_expedited()) in ``CONFIG_PREEMPTION=y`` kernels. The
reason is that an RCU read-side critical section might be preempted,
which means that a subsequent synchronize_rcu() really does have to
wait for something, as opposed to simply returning immediately.
Unfortunately, synchronize_rcu() can't do this until all of its
kthreads are spawned, which doesn't happen until some time during
early_initcalls() time. But this is no excuse: RCU is nevertheless
required to correctly handle synchronous grace periods during this time
period. Once all of its kthreads are up and running, RCU starts running
normally.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| How can RCU possibly handle grace periods before all of its kthreads |
| have been spawned??? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Very carefully! |
| During the “dead zone” between the time that the scheduler spawns the |
| first task and the time that all of RCU's kthreads have been spawned, |
| all synchronous grace periods are handled by the expedited |
| grace-period mechanism. At runtime, this expedited mechanism relies |
| on workqueues, but during the dead zone the requesting task itself |
| drives the desired expedited grace period. Because dead-zone |
| execution takes place within task context, everything works. Once the |
| dead zone ends, expedited grace periods go back to using workqueues, |
| as is required to avoid problems that would otherwise occur when a |
| user task received a POSIX signal while driving an expedited grace |
| period. |
| |
| And yes, this does mean that it is unhelpful to send POSIX signals to |
| random tasks between the time that the scheduler spawns its first |
| kthread and the time that RCU's kthreads have all been spawned. If |
| there ever turns out to be a good reason for sending POSIX signals |
| during that time, appropriate adjustments will be made. (If it turns |
| out that POSIX signals are sent during this time for no good reason, |
| other adjustments will be made, appropriate or otherwise.) |
+-----------------------------------------------------------------------+
I learned of these boot-time requirements as a result of a series of
system hangs.
Interrupt와 NMI
1818-1852일반 interrupt handler와 interrupt-disabled 영역에서는 RCU read-side critical section과 `call_rcu()`가 허용된다. 일부 아키텍처는 process context에서 interrupt로 들어간 뒤 명시적으로 빠져나오지 않고 다시 process context로 전환하는 half-interrupt 동작을 하므로 RCU는 nesting level을 단순 진입/이탈 쌍으로만 계산할 수 없다.
NMI handler 안의 RCU reader는 허용되지만 `call_rcu()`를 포함한 update-side primitive는 금지된다. 이름과 달리 nested NMI가 가능한 아키텍처도 있으며, NMI에서 `ct_irq_enter()`/`ct_irq_exit()`를 직접 호출해 RCU 눈에는 일반 interrupt가 NMI를 끊은 것처럼 보이는 경우도 있다.
현재 구조는 이 역설적인 중첩을 처리하기 위해 `ct_irq_enter()`가 `ct_nmi_enter()`를, `ct_irq_exit()`가 `ct_nmi_exit()`를 호출하도록 한다. RCU의 interrupt accounting은 아키텍처별 진입 관례까지 포함해야 한다.
문맥RCU readercall_rcu()
일반 process허용허용
interrupt허용허용
interrupt-disabled허용허용
NMI허용금지
Reader와 updater primitive의 제약이 다르다.
Interrupts and NMIs
~~~~~~~~~~~~~~~~~~~
The Linux kernel has interrupts, and RCU read-side critical sections are
legal within interrupt handlers and within interrupt-disabled regions of
code, as are invocations of call_rcu().
Some Linux-kernel architectures can enter an interrupt handler from
non-idle process context, and then just never leave it, instead
stealthily transitioning back to process context. This trick is
sometimes used to invoke system calls from inside the kernel. These
“half-interrupts” mean that RCU has to be very careful about how it
counts interrupt nesting levels. I learned of this requirement the hard
way during a rewrite of RCU's dyntick-idle code.
The Linux kernel has non-maskable interrupts (NMIs), and RCU read-side
critical sections are legal within NMI handlers. Thankfully, RCU
update-side primitives, including call_rcu(), are prohibited within
NMI handlers.
The name notwithstanding, some Linux-kernel architectures can have
nested NMIs, which RCU must handle correctly. Andy Lutomirski `surprised
me <https://lore.kernel.org/r/CALCETrXLq1y7e_dKFPgou-FKHB6Pu-r8+t-6Ds+8=va7anBWDA@mail.gmail.com>`__
with this requirement; he also kindly surprised me with `an
algorithm <https://lore.kernel.org/r/CALCETrXSY9JpW3uE6H8WYk81sg56qasA2aqmjMPsq5dOtzso=g@mail.gmail.com>`__
that meets this requirement.
Furthermore, NMI handlers can be interrupted by what appear to RCU to be
normal interrupts. One way that this can happen is for code that
directly invokes ct_irq_enter() and ct_irq_exit() to be called
from an NMI handler. This astonishing fact of life prompted the current
code structure, which has ct_irq_enter() invoking
ct_nmi_enter() and ct_irq_exit() invoking ct_nmi_exit().
And yes, I also learned of this requirement the hard way.
Loadable module과 rcu_barrier()
1853-1917module이 unload된 뒤 그 안의 callback 함수를 호출하면 crash한다. Timer는 `timer_shutdown_sync()`처럼 취소할 수 있지만 이미 `call_rcu()`에 등록한 callback은 취소할 수 없다. 시스템이 종료되지 않는 한 결국 호출되므로 module exit는 먼저 새 callback 등록을 막고 `rcu_barrier()`로 기존 callback이 모두 실행되기를 기다려야 한다.
`rcu_barrier()`를 module unload 공통 경로에서 무조건 호출하면 지연이 너무 커질 수 있으므로 callback을 실제 사용하는 module이 책임진다. 같은 요구는 filesystem unmount에도 적용된다.
중요하게도 `rcu_barrier()`는 새 grace period 하나 전체를 기다릴 의무가 없다. 이미 게시된 callback만 모두 호출되면 된다. callback이 기다리던 GP가 대부분 지나갔다면 남은 부분만 기다리고, 게시된 callback이 없으면 즉시 반환할 수 있다. GP 자체와 기존 callback 전체를 모두 기다려야 하면 `synchronize_rcu()`와 `rcu_barrier()`를 함께 호출하며 필요하면 workqueue로 병렬화한다.
module exit 시작→새 call_rcu() 차단→rcu_barrier()→모든 기존 callback 완료→module text/data unload
새 callback 유입을 닫은 뒤 기존 callback의 함수 실행을 끝낸다.
Loadable Modules
~~~~~~~~~~~~~~~~
The Linux kernel has loadable modules, and these modules can also be
unloaded. After a given module has been unloaded, any attempt to call
one of its functions results in a segmentation fault. The module-unload
functions must therefore cancel any delayed calls to loadable-module
functions, for example, any outstanding mod_timer() must be dealt
with via timer_shutdown_sync() or similar.
Unfortunately, there is no way to cancel an RCU callback; once you
invoke call_rcu(), the callback function is eventually going to be
invoked, unless the system goes down first. Because it is normally
considered socially irresponsible to crash the system in response to a
module unload request, we need some other way to deal with in-flight RCU
callbacks.
RCU therefore provides rcu_barrier(), which waits until all
in-flight RCU callbacks have been invoked. If a module uses
call_rcu(), its exit function should therefore prevent any future
invocation of call_rcu(), then invoke rcu_barrier(). In theory,
the underlying module-unload code could invoke rcu_barrier()
unconditionally, but in practice this would incur unacceptable
latencies.
Nikita Danilov noted this requirement for an analogous
filesystem-unmount situation, and Dipankar Sarma incorporated
rcu_barrier() into RCU. The need for rcu_barrier() for module
unloading became apparent later.
.. important::
The rcu_barrier() function is not, repeat,
*not*, obligated to wait for a grace period. It is instead only required
to wait for RCU callbacks that have already been posted. Therefore, if
there are no RCU callbacks posted anywhere in the system,
rcu_barrier() is within its rights to return immediately. Even if
there are callbacks posted, rcu_barrier() does not necessarily need
to wait for a grace period.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Wait a minute! Each RCU callbacks must wait for a grace period to |
| complete, and rcu_barrier() must wait for each pre-existing |
| callback to be invoked. Doesn't rcu_barrier() therefore need to |
| wait for a full grace period if there is even one callback posted |
| anywhere in the system? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Absolutely not!!! |
| Yes, each RCU callbacks must wait for a grace period to complete, but |
| it might well be partly (or even completely) finished waiting by the |
| time rcu_barrier() is invoked. In that case, rcu_barrier() |
| need only wait for the remaining portion of the grace period to |
| elapse. So even if there are quite a few callbacks posted, |
| rcu_barrier() might well return quite quickly. |
| |
| So if you need to wait for a grace period as well as for all |
| pre-existing callbacks, you will need to invoke both |
| synchronize_rcu() and rcu_barrier(). If latency is a concern, |
| you can always use workqueues to invoke them concurrently. |
+-----------------------------------------------------------------------+
CPU hotplug 기본 규칙
1918-2011Offline CPU에서는 SRCU reader를 제외한 RCU API를 호출하면 안 된다. CPU hotplug notifier에서는 대부분의 RCU 연산을 사용할 수 있고 `synchronize_rcu()`와 `synchronize_rcu_expedited()`도 일부 단계에서 가능하지만, `stop_machine()`으로 실행되는 `CPUHP_AP_OFFLINE`과 `CPUHP_AP_ONLINE` 사이 notifier에서는 block할 수 없어 금지된다.
`rcu_barrier()` 같은 all-callback wait는 어떤 CPU-hotplug notifier에서도 호출할 수 없다. 나가는 CPU의 callback이 hotplug 완료 뒤에야 실행되는 단계가 있어 deadlock할 수 있고, `rcu_barrier()` 자체도 CPU hotplug를 막기 때문이다.
RCU는 중앙 `cpu_online_mask`와 별개로 자체 hotplug bookkeeping을 유지하고, CPU가 offline 될 때 QS를 명시적으로 보고한다. QS는 `rcutree_report_cpu_dead()` 또는 `rcu_gp_init()`이 hotplug와 race를 발견했을 때 보고된다. Online 경로 `rcutree_report_cpu_starting()`은 미보고 상태를 발견하면 경고하지만 정상적으로 offline CPU의 QS를 보고할 필요는 없다.
관련 상태를 확인하거나 바꿀 때는 CPU의 leaf `rcu_node` lock을 잡아 hotplug hook, GP 초기화, force-QS loop 사이 race를 막는다. GP 초기화에서는 `rcu_seq_start()`로 GP 번호를 먼저 증가시킨 뒤 CPU mask를 스캔해야 새로 online 된 CPU의 reader를 놓치지 않는다. 문서의 CPU0/CPU1/CPU2 예시는 순서를 뒤집으면 polling cookie가 완료되었다고 잘못 판단해 use-after-free가 생김을 보인다.
rcu_seq_start(gp_seq)→online/offline CPU snapshot→qsmask 초기화→새 CPU reader 추적→QS 수집→rcu_seq_end(gp_seq)
GP 번호를 먼저 공개해야 새 CPU reader가 어느 GP에 속하는지 모호하지 않다.
Hotplug CPU
~~~~~~~~~~~
The Linux kernel supports CPU hotplug, which means that CPUs can come
and go. It is of course illegal to use any RCU API member from an
offline CPU, with the exception of `SRCU <Sleepable RCU_>`__ read-side
critical sections. This requirement was present from day one in
DYNIX/ptx, but on the other hand, the Linux kernel's CPU-hotplug
implementation is “interesting.”
The Linux-kernel CPU-hotplug implementation has notifiers that are used
to allow the various kernel subsystems (including RCU) to respond
appropriately to a given CPU-hotplug operation. Most RCU operations may
be invoked from CPU-hotplug notifiers, including even synchronous
grace-period operations such as (synchronize_rcu() and
synchronize_rcu_expedited()). However, these synchronous operations
do block and therefore cannot be invoked from notifiers that execute via
stop_machine(), specifically those between the ``CPUHP_AP_OFFLINE``
and ``CPUHP_AP_ONLINE`` states.
In addition, all-callback-wait operations such as rcu_barrier() may
not be invoked from any CPU-hotplug notifier. This restriction is due
to the fact that there are phases of CPU-hotplug operations where the
outgoing CPU's callbacks will not be invoked until after the CPU-hotplug
operation ends, which could also result in deadlock. Furthermore,
rcu_barrier() blocks CPU-hotplug operations during its execution,
which results in another type of deadlock when invoked from a CPU-hotplug
notifier.
Finally, RCU must avoid deadlocks due to interaction between hotplug,
timers and grace period processing. It does so by maintaining its own set
of books that duplicate the centrally maintained ``cpu_online_mask``,
and also by reporting quiescent states explicitly when a CPU goes
offline. This explicit reporting of quiescent states avoids any need
for the force-quiescent-state loop (FQS) to report quiescent states for
offline CPUs. However, as a debugging measure, the FQS loop does splat
if offline CPUs block an RCU grace period for too long.
An offline CPU's quiescent state will be reported either:
1. As the CPU goes offline using RCU's hotplug notifier (rcutree_report_cpu_dead()).
2. When grace period initialization (rcu_gp_init()) detects a
race either with CPU offlining or with a task unblocking on a leaf
``rcu_node`` structure whose CPUs are all offline.
The CPU-online path (rcutree_report_cpu_starting()) should never need to report
a quiescent state for an offline CPU. However, as a debugging measure,
it does emit a warning if a quiescent state was not already reported
for that CPU.
During the checking/modification of RCU's hotplug bookkeeping, the
corresponding CPU's leaf node lock is held. This avoids race conditions
between RCU's hotplug notifier hooks, the grace period initialization
code, and the FQS loop, all of which refer to or modify this bookkeeping.
Note that grace period initialization (rcu_gp_init()) must carefully sequence
CPU hotplug scanning with grace period state changes. For example, the
following race could occur in rcu_gp_init() if rcu_seq_start() were to happen
after the CPU hotplug scanning::
CPU0 (rcu_gp_init) CPU1 CPU2
--------------------- ---- ----
// Hotplug scan first (WRONG ORDER)
rcu_for_each_leaf_node(rnp) {
rnp->qsmaskinit = rnp->qsmaskinitnext;
}
rcutree_report_cpu_starting()
rnp->qsmaskinitnext |= mask;
rcu_read_lock()
r0 = *X;
r1 = *X;
X = NULL;
cookie = get_state_synchronize_rcu();
// cookie = 8 (future GP)
rcu_seq_start(&rcu_state.gp_seq);
// gp_seq = 5
// CPU1 now invisible to this GP!
rcu_for_each_node_breadth_first() {
rnp->qsmask = rnp->qsmaskinit;
// CPU1 not included!
}
// GP completes without CPU1
rcu_seq_end(&rcu_state.gp_seq);
// gp_seq = 8
poll_state_synchronize_rcu(cookie);
// Returns true!
kfree(r1);
r2 = *r0; // USE-AFTER-FREE!
By incrementing ``gp_seq`` first, CPU1's RCU read-side critical section
is guaranteed to not be missed by CPU2.
Offline CPU의 동시 QS 보고
2012-2096CPU offline과 새 `rcu_gp_init()`이 겹치면 offline CPU의 QS가 빠져 grace period가 영원히 멈출 수 있다. `rcutree_report_cpu_dead()`의 `rcu_report_qs_rnp()`는 GP kthread를 깨우려고 잠시 `rnp->lock`을 놓는다. 그 사이 새 GP가 `qsmaskinitnext`를 복사하면 아직 CPU bit가 남아 있어 이미 죽은 CPU를 기다리게 된다.
`ofl_lock`은 이 취약 구간을 보호한다. `rcu_gp_init()`이 각 leaf의 online CPU snapshot을 복사하는 동안 offline 경로가 상태를 바꾸지 못하게 해 첫 pass를 atomic하게 만든다.
첫 pass의 snapshot 뒤 두 번째 breadth-first pass까지 사이에 CPU가 offline 될 수도 있다. 두 번째 pass는 `rnp->lock` 아래 `qsmask = qsmaskinit`을 적용하고 `qsmask & ~qsmaskinitnext`로 그 사이 offline 된 CPU를 찾는다. Leaf에서 해당 mask를 `rcu_report_qs_rnp()`에 넘겨 대신 QS를 보고한다.
결과적으로 offline CPU의 QS는 `rcu_gp_init()` 두 번째 pass 또는 `rcutree_report_cpu_dead()` 중 정확히 한쪽에서 보고된다. 둘 다 같은 `rnp->lock`을 사용하므로 두 번 보고하거나 아무도 보고하지 않는 상태를 막는다.
ofl_lock 획득→qsmaskinitnext snapshot→ofl_lock 해제→rnp->lock 획득→snapshot 뒤 offline CPU 검출→대리 QS 보고
Snapshot과 사후 race 검사를 두 단계로 안전하게 묶는다.
Concurrent Quiescent State Reporting for Offline CPUs
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
RCU must ensure that CPUs going offline report quiescent states to avoid
blocking grace periods. This requires careful synchronization to handle
race conditions
Race condition causing Offline CPU to hang GP
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
A race between CPU offlining and new GP initialization (gp_init()) may occur
because rcu_report_qs_rnp() in rcutree_report_cpu_dead() must temporarily
release the ``rcu_node`` lock to wake the RCU grace-period kthread::
CPU1 (going offline) CPU0 (GP kthread)
-------------------- -----------------
rcutree_report_cpu_dead()
rcu_report_qs_rnp()
// Must release rnp->lock to wake GP kthread
raw_spin_unlock_irqrestore_rcu_node()
// Wakes up and starts new GP
rcu_gp_init()
// First loop:
copies qsmaskinitnext->qsmaskinit
// CPU1 still in qsmaskinitnext!
// Second loop:
rnp->qsmask = rnp->qsmaskinit
mask = rnp->qsmask & ~rnp->qsmaskinitnext
// mask is 0! CPU1 still in both masks
// Reacquire lock (but too late)
rnp->qsmaskinitnext &= ~mask // Finally clears bit
Without ``ofl_lock``, the new grace period includes the offline CPU and waits
forever for its quiescent state causing a GP hang.
A solution with ofl_lock
^^^^^^^^^^^^^^^^^^^^^^^^
The ``ofl_lock`` (offline lock) prevents rcu_gp_init() from running during
the vulnerable window when rcu_report_qs_rnp() has released ``rnp->lock``::
CPU0 (rcu_gp_init) CPU1 (rcutree_report_cpu_dead)
------------------ ------------------------------
rcu_for_each_leaf_node(rnp) {
arch_spin_lock(&ofl_lock) -----> arch_spin_lock(&ofl_lock) [BLOCKED]
// Safe: CPU1 can't interfere
rnp->qsmaskinit = rnp->qsmaskinitnext
arch_spin_unlock(&ofl_lock) ---> // Now CPU1 can proceed
} // But snapshot already taken
Another race causing GP hangs in rcu_gpu_init(): Reporting QS for Now-offline CPUs
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
After the first loop takes an atomic snapshot of online CPUs, as shown above,
the second loop in rcu_gp_init() detects CPUs that went offline between
releasing ``ofl_lock`` and acquiring the per-node ``rnp->lock``.
This detection is crucial because:
1. The CPU might have gone offline after the snapshot but before the second loop
2. The offline CPU cannot report its own QS if it's already dead
3. Without this detection, the grace period would wait forever for CPUs that
are now offline.
The second loop performs this detection safely::
rcu_for_each_node_breadth_first(rnp) {
raw_spin_lock_irqsave_rcu_node(rnp, flags);
rnp->qsmask = rnp->qsmaskinit; // Apply the snapshot
// Detect CPUs offline after snapshot
mask = rnp->qsmask & ~rnp->qsmaskinitnext;
if (mask && rcu_is_leaf_node(rnp))
rcu_report_qs_rnp(mask, ...) // Report QS for offline CPUs
}
This approach ensures atomicity: quiescent state reporting for offline CPUs
happens either in rcu_gp_init() (second loop) or in rcutree_report_cpu_dead(),
never both and never neither. The ``rnp->lock`` held throughout the sequence
prevents races - rcutree_report_cpu_dead() also acquires this lock when
clearing ``qsmaskinitnext``, ensuring mutual exclusion.
Scheduler, 재귀, tracing
2097-2132RCU는 여러 kthread를 사용하므로 context-switch-heavy workload에서 이 thread들이 과도한 CPU 시간을 쌓지 않도록 해야 한다. `CONFIG_NO_HZ_FULL` 등 구성에 따른 scheduler와 RCU accounting 경계를 정확히 지켜야 하며, scheduler 자체가 RCU를 사용하는 상황에서 파괴적 재귀를 피해야 한다.
과거에는 RCU flavor 사이 negative nesting 같은 복잡성이 있었지만 flavor 통합과 interrupt-disabled 영역을 암묵적 RCU reader로 취급하는 규칙이 interrupt handler의 RCU 사용으로 생기던 재귀 문제를 줄였다.
RCU 코드를 tracing할 수 있지만 tracing 자체도 RCU를 사용한다. `rcu_dereference_raw_check()`는 tracing이 일반 검사를 재귀적으로 다시 호출하지 않도록 한다. 일부 아키텍처의 virtualization처럼 tracing할 수 없는 환경에서 reader가 실행되는 경우에도 이 API를 사용한다.
Tracing이 RCU 코드 관찰→Tracing 내부도 RCU 사용→rcu_dereference_raw_check()→lockdep 의미는 유지→파괴적 재귀 방지
RCU를 관찰하는 도구가 다시 일반 RCU 검사 경로로 들어가지 않게 한다.
Scheduler and RCU
~~~~~~~~~~~~~~~~~
RCU makes use of kthreads, and it is necessary to avoid excessive CPU-time
accumulation by these kthreads. This requirement was no surprise, but
RCU's violation of it when running context-switch-heavy workloads when
built with ``CONFIG_NO_HZ_FULL=y`` `did come as a surprise
[PDF] <http://www.rdrop.com/users/paulmck/scalability/paper/BareMetal.2015.01.15b.pdf>`__.
RCU has made good progress towards meeting this requirement, even for
context-switch-heavy ``CONFIG_NO_HZ_FULL=y`` workloads, but there is
room for further improvement.
There is no longer any prohibition against holding any of
scheduler's runqueue or priority-inheritance spinlocks across an
rcu_read_unlock(), even if interrupts and preemption were enabled
somewhere within the corresponding RCU read-side critical section.
Therefore, it is now perfectly legal to execute rcu_read_lock()
with preemption enabled, acquire one of the scheduler locks, and hold
that lock across the matching rcu_read_unlock().
Similarly, the RCU flavor consolidation has removed the need for negative
nesting. The fact that interrupt-disabled regions of code act as RCU
read-side critical sections implicitly avoids earlier issues that used
to result in destructive recursion via interrupt handler's use of RCU.
Tracing and RCU
~~~~~~~~~~~~~~~
It is possible to use tracing on RCU code, but tracing itself uses RCU.
For this reason, rcu_dereference_raw_check() is provided for use
by tracing, which avoids the destructive recursion that could otherwise
ensue. This API is also used by virtualization in some architectures,
where RCU readers execute in environments in which tracing cannot be
used. The tracing folks both located the requirement and provided the
needed fix, so this surprise requirement was relatively painless.
User memory access와 에너지 효율
2133-2215`get_user()`는 page fault와 I/O 대기로 block할 수 있다. Compiler가 source에서 RCU reader 뒤에 있는 `get_user()`를 critical section 안으로 옮기면 `CONFIG_PREEMPTION=n`에서도 reader 중간에 quiescent state가 생겨 뒤의 `p->value`가 use-after-free가 될 수 있다. `get_user()` 내부 asm이 volatile이 아니거나 대상 access가 non-volatile이면 compiler는 순서를 유지할 이유가 없다.
따라서 Linux의 `rcu_read_lock()`과 `rcu_read_unlock()` 정의는 최소한 가장 바깥 중첩 경계에서 compiler barrier 역할을 해야 한다. 이는 CPU memory ordering이 아니라 blocking 가능한 user-memory access가 reader 안팎으로 이동하지 못하게 하는 compile-time 요구사항이다.
배터리 시스템에서 idle CPU를 깨우는 것은 허용하기 어렵다. RCU는 idle에서 interrupt된 CPU까지 추적해 불필요한 IPI를 피한다. 그 대신 idle CPU에서 일반 RCU read-side critical section을 실행하는 것은 불법이며 `CONFIG_PROVE_RCU=y`가 이를 경고한다.
`nohz_full` CPU가 userspace를 실행할 때도 방해하지 않아야 한다. RCU는 두 시점의 상태를 비교해 그 사이 CPU가 idle 또는 userspace에 있었는지 판정한다. 이 코드는 여러 차례 전면 재작성되었고 실제 하드웨어에서 측정 가능한 에너지 절약을 입증한 뒤에야 요구를 안정적으로 만족했다.
rcu_read_lock() compiler barrier→rcu_dereference(gp)→p->value 읽기→rcu_read_unlock() compiler barrier→get_user() / page fault 가능
Blocking 가능한 access는 RCU reader 안으로 이동할 수 없다.
Accesses to User Memory and RCU
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The kernel needs to access user-space memory, for example, to access data
referenced by system-call parameters. The get_user() macro does this job.
However, user-space memory might well be paged out, which means that
get_user() might well page-fault and thus block while waiting for the
resulting I/O to complete. It would be a very bad thing for the compiler to
reorder a get_user() invocation into an RCU read-side critical section.
For example, suppose that the source code looked like this:
::
1 rcu_read_lock();
2 p = rcu_dereference(gp);
3 v = p->value;
4 rcu_read_unlock();
5 get_user(user_v, user_p);
6 do_something_with(v, user_v);
The compiler must not be permitted to transform this source code into
the following:
::
1 rcu_read_lock();
2 p = rcu_dereference(gp);
3 get_user(user_v, user_p); // BUG: POSSIBLE PAGE FAULT!!!
4 v = p->value;
5 rcu_read_unlock();
6 do_something_with(v, user_v);
If the compiler did make this transformation in a ``CONFIG_PREEMPTION=n`` kernel
build, and if get_user() did page fault, the result would be a quiescent
state in the middle of an RCU read-side critical section. This misplaced
quiescent state could result in line 4 being a use-after-free access,
which could be bad for your kernel's actuarial statistics. Similar examples
can be constructed with the call to get_user() preceding the
rcu_read_lock().
Unfortunately, get_user() doesn't have any particular ordering properties,
and in some architectures the underlying ``asm`` isn't even marked
``volatile``. And even if it was marked ``volatile``, the above access to
``p->value`` is not volatile, so the compiler would not have any reason to keep
those two accesses in order.
Therefore, the Linux-kernel definitions of rcu_read_lock() and
rcu_read_unlock() must act as compiler barriers, at least for outermost
instances of rcu_read_lock() and rcu_read_unlock() within a nested set
of RCU read-side critical sections.
Energy Efficiency
~~~~~~~~~~~~~~~~~
Interrupting idle CPUs is considered socially unacceptable, especially
by people with battery-powered embedded systems. RCU therefore conserves
energy by detecting which CPUs are idle, including tracking CPUs that
have been interrupted from idle. This is a large part of the
energy-efficiency requirement, so I learned of this via an irate phone
call.
Because RCU avoids interrupting idle CPUs, it is illegal to execute an
RCU read-side critical section on an idle CPU. (Kernels built with
``CONFIG_PROVE_RCU=y`` will splat if you try it.)
It is similarly socially unacceptable to interrupt an ``nohz_full`` CPU
running in userspace. RCU must therefore track ``nohz_full`` userspace
execution. RCU must therefore be able to sample state at two points in
time, and be able to determine whether or not some other CPU spent any
time idle and/or executing in userspace.
These energy-efficiency requirements have proven quite difficult to
understand and to meet, for example, there have been more than five
clean-sheet rewrites of RCU's energy-efficiency code, the last of which
was finally able to demonstrate `real energy savings running on real
hardware
[PDF] <http://www.rdrop.com/users/paulmck/realtime/paper/AMPenergy.2013.04.19a.pdf>`__.
As noted earlier, I learned of many of these requirements via angry
phone calls: Flaming me on the Linux-kernel mailing list was apparently
not sufficient to fully vent their ire at RCU's energy-efficiency bugs!
Scheduling-clock interrupt와 RCU
2216-2330RCU는 in-kernel non-idle, userspace, idle loop 사이 전환을 알아야 한다. `HZ_PERIODIC`과 `NO_HZ_IDLE`에서는 kernel과 userspace의 scheduling-clock interrupt를 활용하고 idle은 dyntick-idle detection으로 추적한다. `NO_HZ_FULL`에서는 syscall마다 tick을 다시 켜지 않을 수 있으므로 kernel 실행 중 tick에 항상 의존할 수 없고 실행 시간을 제한하거나 IPI를 사용해야 한다.
구성In-kernelUsermodeIdle
HZ_PERIODICscheduling-clocktick과 usermode 진입 검출dyntick-idle
NO_HZ_IDLEscheduling-clocktick과 usermode 진입 검출dyntick-idle
NO_HZ_FULLtick은 일부만 가능, 실행 시간 제한/IPI 필요dyntick 상태dyntick-idle
원문의 표를 같은 상태 축으로 재구성한다.
CPU가 idle 또는 userspace인데 RCU가 non-idle로 믿으면 tick이 켜져 있어야 하며, 아니면 stall warning이나 약 11초의 긴 GP와 불필요한 IPI가 생긴다. 반대로 kernel에서 RCU reader를 실행 중인데 RCU가 idle로 믿으면 임의의 memory corruption이 생긴다. 이 오류는 반드시 `CONFIG_PROVE_RCU=y`로 시험해야 한다.
RCU reader가 절대로 없는 짧은 exception handler는 RCU 관점에서 idle로 남아 `ct_irq_enter()`/`ct_irq_exit()` 비용을 생략할 수 있다. Kernel에서 tick을 껐더라도 몇 jiffy마다 RCU 관점의 idle/QS를 통과하면 괜찮지만 간격이 길어지면 stall warning이 난다. Tick이 켜진 kernel 경로도 충분히 자주 QS를 제공해야 한다.
수초 동안 실행되는 hardware interrupt handler는 주기적으로 `ct_irq_exit(); ct_irq_enter();`를 호출해 RCU 상태를 갱신할 수 있지만, 응답 시간 자체를 위해 handler를 짧게 만드는 편이 바람직하다. 핵심은 상태 전환을 정확히 알리고 RCU가 필요로 할 때 tick을 제공하는 것이다.
실제 idle/user, RCU는 kernel→tick 없으면 GP stall→실제 kernel reader, RCU는 idle→QS를 잘못 인정→use-after-free / memory corruption
실제 CPU 상태와 RCU의 믿음이 어긋나는 방향에 따라 실패가 달라진다.
Scheduling-Clock Interrupts and RCU
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The kernel transitions between in-kernel non-idle execution, userspace
execution, and the idle loop. Depending on kernel configuration, RCU
handles these states differently:
+-----------------+------------------+------------------+-----------------+
| ``HZ`` Kconfig | In-Kernel | Usermode | Idle |
+=================+==================+==================+=================+
| ``HZ_PERIODIC`` | Can rely on | Can rely on | Can rely on |
| | scheduling-clock | scheduling-clock | RCU's |
| | interrupt. | interrupt and | dyntick-idle |
| | | its detection | detection. |
| | | of interrupt | |
| | | from usermode. | |
+-----------------+------------------+------------------+-----------------+
| ``NO_HZ_IDLE`` | Can rely on | Can rely on | Can rely on |
| | scheduling-clock | scheduling-clock | RCU's |
| | interrupt. | interrupt and | dyntick-idle |
| | | its detection | detection. |
| | | of interrupt | |
| | | from usermode. | |
+-----------------+------------------+------------------+-----------------+
| ``NO_HZ_FULL`` | Can only | Can rely on | Can rely on |
| | sometimes rely | RCU's | RCU's |
| | on | dyntick-idle | dyntick-idle |
| | scheduling-clock | detection. | detection. |
| | interrupt. In | | |
| | other cases, it | | |
| | is necessary to | | |
| | bound kernel | | |
| | execution times | | |
| | and/or use | | |
| | IPIs. | | |
+-----------------+------------------+------------------+-----------------+
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| Why can't ``NO_HZ_FULL`` in-kernel execution rely on the |
| scheduling-clock interrupt, just like ``HZ_PERIODIC`` and |
| ``NO_HZ_IDLE`` do? |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| Because, as a performance optimization, ``NO_HZ_FULL`` does not |
| necessarily re-enable the scheduling-clock interrupt on entry to each |
| and every system call. |
+-----------------------------------------------------------------------+
However, RCU must be reliably informed as to whether any given CPU is
currently in the idle loop, and, for ``NO_HZ_FULL``, also whether that
CPU is executing in usermode, as discussed
`earlier <Energy Efficiency_>`__. It also requires that the
scheduling-clock interrupt be enabled when RCU needs it to be:
#. If a CPU is either idle or executing in usermode, and RCU believes it
is non-idle, the scheduling-clock tick had better be running.
Otherwise, you will get RCU CPU stall warnings. Or at best, very long
(11-second) grace periods, with a pointless IPI waking the CPU from
time to time.
#. If a CPU is in a portion of the kernel that executes RCU read-side
critical sections, and RCU believes this CPU to be idle, you will get
random memory corruption. **DON'T DO THIS!!!**
This is one reason to test with lockdep, which will complain about
this sort of thing.
#. If a CPU is in a portion of the kernel that is absolutely positively
no-joking guaranteed to never execute any RCU read-side critical
sections, and RCU believes this CPU to be idle, no problem. This
sort of thing is used by some architectures for light-weight
exception handlers, which can then avoid the overhead of
ct_irq_enter() and ct_irq_exit() at exception entry and
exit, respectively. Some go further and avoid the entireties of
irq_enter() and irq_exit().
Just make very sure you are running some of your tests with
``CONFIG_PROVE_RCU=y``, just in case one of your code paths was in
fact joking about not doing RCU read-side critical sections.
#. If a CPU is executing in the kernel with the scheduling-clock
interrupt disabled and RCU believes this CPU to be non-idle, and if
the CPU goes idle (from an RCU perspective) every few jiffies, no
problem. It is usually OK for there to be the occasional gap between
idle periods of up to a second or so.
If the gap grows too long, you get RCU CPU stall warnings.
#. If a CPU is either idle or executing in usermode, and RCU believes it
to be idle, of course no problem.
#. If a CPU is executing in the kernel, the kernel code path is passing
through quiescent states at a reasonable frequency (preferably about
once per few jiffies, but the occasional excursion to a second or so
is usually OK) and the scheduling-clock interrupt is enabled, of
course no problem.
If the gap between a successive pair of quiescent states grows too
long, you get RCU CPU stall warnings.
+-----------------------------------------------------------------------+
| **Quick Quiz**: |
+-----------------------------------------------------------------------+
| But what if my driver has a hardware interrupt handler that can run |
| for many seconds? I cannot invoke schedule() from an hardware |
| interrupt handler, after all! |
+-----------------------------------------------------------------------+
| **Answer**: |
+-----------------------------------------------------------------------+
| One approach is to do ``ct_irq_exit();ct_irq_enter();`` every so |
| often. But given that long-running interrupt handlers can cause other |
| problems, not least for response time, shouldn't you work to keep |
| your interrupt handler's runtime within reasonable bounds? |
+-----------------------------------------------------------------------+
But as long as RCU is properly informed of kernel state transitions
between in-kernel execution, usermode execution, and idle, and as long
as the scheduling-clock interrupt is enabled when RCU needs it to be,
you can rest assured that the bugs you encounter will be in some other
part of RCU or some other part of the kernel!
메모리 효율
2331-2382작은 non-realtime 시스템은 Tiny RCU로 code size를 줄일 수 있지만 자료구조의 크기도 중요하다. `call_rcu()`와 `kfree_rcu()`가 사용하는 `rcu_head`는 포인터 두 개뿐이어도 `struct page`처럼 크기에 민감하고 많이 생성되는 객체 안에 들어간다.
RCU는 대기 중인 `rcu_head`를 hand-crafted singly linked list로 관리하고 file/line 같은 debug field를 넣지 않는다. 필요할 때 `->func`가 callback 출처를 추적하는 단서가 된다. `struct page`에서는 `rcu_head`가 수명 단계별 여러 구조와 union storage를 공유한다.
Memory-management race를 위해 `call_rcu()`로 게시한 `rcu_head->next`의 최하위 bit가 GP 처리 전체 동안 0이라는 보장을 제공한다. 이 보장은 `kfree_rcu()`나 미래의 lazy callback에는 적용되지 않을 수 있다. 모든 `rcu_head`는 최소 2-byte 정렬이어야 하며 misaligned 객체는 경고한다. m68k가 2-byte 정렬만 제공하므로 더 강한 공통 요구는 두지 않는다.
포인터 최하위 bit를 비워 두면 언젠가 에너지 절약을 위해 안전하게 늦출 수 있는 lazy callback을 표시할 수 있다. 실제 중요한 workload에서 non-lazy callback 비율이 충분히 줄어야 이 기능이 이득이지만, 현재 정렬 계약은 그 선택지를 보존한다.
항목보장/제약
필드next와 func, 포인터 두 개
Debug 위치별도 field 대신 주로 ->func 활용
정렬최소 2-byte
next 최하위 bitcall_rcu() GP 처리 중 0
향후 용도lazy callback tag 가능성
작은 객체를 위해 정보와 tag bit를 신중히 배치한다.
Memory Efficiency
~~~~~~~~~~~~~~~~~
Although small-memory non-realtime systems can simply use Tiny RCU, code
size is only one aspect of memory efficiency. Another aspect is the size
of the ``rcu_head`` structure used by call_rcu() and
kfree_rcu(). Although this structure contains nothing more than a
pair of pointers, it does appear in many RCU-protected data structures,
including some that are size critical. The ``page`` structure is a case
in point, as evidenced by the many occurrences of the ``union`` keyword
within that structure.
This need for memory efficiency is one reason that RCU uses hand-crafted
singly linked lists to track the ``rcu_head`` structures that are
waiting for a grace period to elapse. It is also the reason why
``rcu_head`` structures do not contain debug information, such as fields
tracking the file and line of the call_rcu() or kfree_rcu() that
posted them. Although this information might appear in debug-only kernel
builds at some point, in the meantime, the ``->func`` field will often
provide the needed debug information.
However, in some cases, the need for memory efficiency leads to even
more extreme measures. Returning to the ``page`` structure, the
``rcu_head`` field shares storage with a great many other structures
that are used at various points in the corresponding page's lifetime. In
order to correctly resolve certain `race
conditions <https://lore.kernel.org/r/1439976106-137226-1-git-send-email-kirill.shutemov@linux.intel.com>`__,
the Linux kernel's memory-management subsystem needs a particular bit to
remain zero during all phases of grace-period processing, and that bit
happens to map to the bottom bit of the ``rcu_head`` structure's
``->next`` field. RCU makes this guarantee as long as call_rcu() is
used to post the callback, as opposed to kfree_rcu() or some future
“lazy” variant of call_rcu() that might one day be created for
energy-efficiency purposes.
That said, there are limits. RCU requires that the ``rcu_head``
structure be aligned to a two-byte boundary, and passing a misaligned
``rcu_head`` structure to one of the call_rcu() family of functions
will result in a splat. It is therefore necessary to exercise caution
when packing structures containing fields of type ``rcu_head``. Why not
a four-byte or even eight-byte alignment requirement? Because the m68k
architecture provides only two-byte alignment, and thus acts as
alignment's least common denominator.
The reason for reserving the bottom bit of pointers to ``rcu_head``
structures is to leave the door open to “lazy” callbacks whose
invocations can safely be deferred. Deferring invocation could
potentially have energy-efficiency benefits, but only if the rate of
non-lazy callbacks decreases significantly for some important workload.
In the meantime, reserving the bottom bit keeps this option open in case
it one day becomes useful.
Linux 규모, 실시간성, 신뢰성
2383-2469RCU는 networking, security, virtualization, scheduler의 hot path에서 광범위하게 쓰이므로 특히 reader primitive가 매우 효율적이어야 한다. Preemptible RCU의 `rcu_read_lock()`을 inline하면 좋지만 `task_struct`와 include 관계 문제를 해결해야 한다.
Linux는 최대 4096 CPU 구성을 지원하므로 전역 lock이나 전역 atomic을 자주 사용하는 구현은 허용되지 않는다. RCU는 `rcu_node` combining tree와 per-CPU 상태를 사용한다. 모든 CPU가 runtime primitive를 계속 호출해도 작은 건당 비용을 유지해야 하고, `synchronize_rcu()`, `call_rcu()`, `synchronize_rcu_expedited()`, `rcu_barrier()` batching처럼 부하가 늘수록 건당 비용이 줄어드는 것이 바람직하다.
PREEMPT_RT workload에서는 reader 전체에서 preemption을 끄는 고전 방식이 부적합하다. `CONFIG_PREEMPTION=y`는 reader preemption을 허용한다. 작은 시스템의 전체 커널 목표가 20 microsecond 미만이고 큰 4096 CPU 시스템에서도 RCU 몫은 100 microsecond 미만이므로 GP kthread와 세심한 latency 제어가 필요하다.
RCU는 userspace와 kernel의 CPU-bound thread 응답성을 훼손하지 않아야 한다. 다만 kernel tight loop는 수십 millisecond마다 `cond_resched()`를 실행해 RCU가 IPI를 보낼 필요가 없게 해야 한다.
동기화 primitive의 실패는 임의 memory corruption으로 이어지므로 강한 신뢰성이 필요하며, 이를 위한 stress suite가 `rcutorture`다. Linux 설치 기반이 10억 대를 넘으면 평균 백만 년에 한 번인 race도 전체로는 하루 세 번쯤 나타난다. Safety-critical 사용까지 고려하면 검증과 형식적 확인은 부가 기능이 아니라 핵심 요구사항이다.
축목표
Reader overheadhot path에서 최소
Scalability4096 CPU 지속 부하
Realtime작은 시스템 20us, 큰 시스템에서도 100us 미만 목표
Reliabilityrcutorture와 대규모 검증
Load behaviorbatching으로 건당 비용 감소
성능과 신뢰성을 동시에 만족해야 한다.
Performance, Scalability, Response Time, and Reliability
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Expanding on the `earlier
discussion <Performance and Scalability_>`__, RCU is used heavily by
hot code paths in performance-critical portions of the Linux kernel's
networking, security, virtualization, and scheduling code paths. RCU
must therefore use efficient implementations, especially in its
read-side primitives. To that end, it would be good if preemptible RCU's
implementation of rcu_read_lock() could be inlined, however, doing
this requires resolving ``#include`` issues with the ``task_struct``
structure.
The Linux kernel supports hardware configurations with up to 4096 CPUs,
which means that RCU must be extremely scalable. Algorithms that involve
frequent acquisitions of global locks or frequent atomic operations on
global variables simply cannot be tolerated within the RCU
implementation. RCU therefore makes heavy use of a combining tree based
on the ``rcu_node`` structure. RCU is required to tolerate all CPUs
continuously invoking any combination of RCU's runtime primitives with
minimal per-operation overhead. In fact, in many cases, increasing load
must *decrease* the per-operation overhead, witness the batching
optimizations for synchronize_rcu(), call_rcu(),
synchronize_rcu_expedited(), and rcu_barrier(). As a general
rule, RCU must cheerfully accept whatever the rest of the Linux kernel
decides to throw at it.
The Linux kernel is used for real-time workloads, especially in
conjunction with the `-rt
patchset <https://wiki.linuxfoundation.org/realtime/>`__. The
real-time-latency response requirements are such that the traditional
approach of disabling preemption across RCU read-side critical sections
is inappropriate. Kernels built with ``CONFIG_PREEMPTION=y`` therefore use
an RCU implementation that allows RCU read-side critical sections to be
preempted. This requirement made its presence known after users made it
clear that an earlier `real-time
patch <https://lwn.net/Articles/107930/>`__ did not meet their needs, in
conjunction with some `RCU
issues <https://lore.kernel.org/r/[email protected]>`__
encountered by a very early version of the -rt patchset.
In addition, RCU must make do with a sub-100-microsecond real-time
latency budget. In fact, on smaller systems with the -rt patchset, the
Linux kernel provides sub-20-microsecond real-time latencies for the
whole kernel, including RCU. RCU's scalability and latency must
therefore be sufficient for these sorts of configurations. To my
surprise, the sub-100-microsecond real-time latency budget `applies to
even the largest systems
[PDF] <http://www.rdrop.com/users/paulmck/realtime/paper/bigrt.2013.01.31a.LCA.pdf>`__,
up to and including systems with 4096 CPUs. This real-time requirement
motivated the grace-period kthread, which also simplified handling of a
number of race conditions.
RCU must avoid degrading real-time response for CPU-bound threads,
whether executing in usermode (which is one use case for
``CONFIG_NO_HZ_FULL=y``) or in the kernel. That said, CPU-bound loops in
the kernel must execute cond_resched() at least once per few tens of
milliseconds in order to avoid receiving an IPI from RCU.
Finally, RCU's status as a synchronization primitive means that any RCU
failure can result in arbitrary memory corruption that can be extremely
difficult to debug. This means that RCU must be extremely reliable,
which in practice also means that RCU must have an aggressive
stress-test suite. This stress-test suite is called ``rcutorture``.
Although the need for ``rcutorture`` was no surprise, the current
immense popularity of the Linux kernel is posing interesting—and perhaps
unprecedented—validation challenges. To see this, keep in mind that
there are well over one billion instances of the Linux kernel running
today, given Android smartphones, Linux-powered televisions, and
servers. This number can be expected to increase sharply with the advent
of the celebrated Internet of Things.
Suppose that RCU contains a race condition that manifests on average
once per million years of runtime. This bug will be occurring about
three times per *day* across the installed base. RCU could simply hide
behind hardware error rates, given that no one should really expect
their smartphone to last for a million years. However, anyone taking too
much comfort from this thought should consider the fact that in most
jurisdictions, a successful multi-year test of a given mechanism, which
might include a Linux kernel, suffices for a number of types of
safety-critical certifications. In fact, rumor has it that the Linux
kernel is already being used in production for safety-critical
applications. I don't know about you, but I would feel quite bad if a
bug in RCU killed someone. Which might explain my recent focus on
validation and verification.
Bottom-half flavor의 역사
2470-2539세 RCU flavor가 하나로 통합되면서 RCU-bh의 update-side 구현은 일반 RCU로 합쳐졌다. Read-side API는 남아 softirq를 disable하고 lockdep accounting을 제공하지만 이 절의 많은 내용은 역사적 배경이다.
RCU-bh는 Robert Olsson이 연구한 network denial-of-service workload에 대응하려고 Dipankar Sarma가 만들었다. CPU가 softirq에서 계속 실행하면 당시 RCU가 QS로 쓰던 context switch가 발생하지 않아 GP가 끝나지 않고 OOM과 hang으로 이어졌다.
`rcu_read_lock_bh()`는 `local_bh_disable()`로 reader를 감싸며, 한 종류의 softirq 처리에서 다른 종류로 넘어가는 전환도 QS로 인정한다. 따라서 일부 CPU가 softirq에서 무한히 일해도 RCU-bh GP가 진행한다. Unlock 시 밀린 softirq 처리가 시작되면 profiler에는 `rcu_read_unlock_bh()`가 느린 것처럼 보일 수 있다.
남은 API는 `rcu_read_lock_bh()`, `rcu_read_unlock_bh()`, `rcu_dereference_bh()`, `rcu_dereference_bh_check()`, `rcu_read_lock_bh_held()`다. Update-side는 `synchronize_rcu()`, `synchronize_rcu_expedited()`, `call_rcu()`, `rcu_barrier()`를 사용한다. Bottom half나 interrupt를 disable하는 구간도 암묵적으로 RCU-bh reader다.
softirq type A 실행→softirq 처리 전환→RCU-bh quiescent state→다음 softirq 실행→grace period 진행
Softirq가 끝나지 않는 공격에서도 GP가 진행하도록 관찰 지점을 넓혔다.
Other RCU Flavors
-----------------
One of the more surprising things about RCU is that there are now no
fewer than five *flavors*, or API families. In addition, the primary
flavor that has been the sole focus up to this point has two different
implementations, non-preemptible and preemptible. The other four flavors
are listed below, with requirements for each described in a separate
section.
#. `Bottom-Half Flavor (Historical)`_
#. `Sched Flavor (Historical)`_
#. `Sleepable RCU`_
#. `Tasks RCU`_
#. `Tasks Trace RCU`_
Bottom-Half Flavor (Historical)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The RCU-bh flavor of RCU has since been expressed in terms of the other
RCU flavors as part of a consolidation of the three flavors into a
single flavor. The read-side API remains, and continues to disable
softirq and to be accounted for by lockdep. Much of the material in this
section is therefore strictly historical in nature.
The softirq-disable (AKA “bottom-half”, hence the “_bh” abbreviations)
flavor of RCU, or *RCU-bh*, was developed by Dipankar Sarma to provide a
flavor of RCU that could withstand the network-based denial-of-service
attacks researched by Robert Olsson. These attacks placed so much
networking load on the system that some of the CPUs never exited softirq
execution, which in turn prevented those CPUs from ever executing a
context switch, which, in the RCU implementation of that time, prevented
grace periods from ever ending. The result was an out-of-memory
condition and a system hang.
The solution was the creation of RCU-bh, which does
local_bh_disable() across its read-side critical sections, and which
uses the transition from one type of softirq processing to another as a
quiescent state in addition to context switch, idle, user mode, and
offline. This means that RCU-bh grace periods can complete even when
some of the CPUs execute in softirq indefinitely, thus allowing
algorithms based on RCU-bh to withstand network-based denial-of-service
attacks.
Because rcu_read_lock_bh() and rcu_read_unlock_bh() disable and
re-enable softirq handlers, any attempt to start a softirq handlers
during the RCU-bh read-side critical section will be deferred. In this
case, rcu_read_unlock_bh() will invoke softirq processing, which can
take considerable time. One can of course argue that this softirq
overhead should be associated with the code following the RCU-bh
read-side critical section rather than rcu_read_unlock_bh(), but the
fact is that most profiling tools cannot be expected to make this sort
of fine distinction. For example, suppose that a three-millisecond-long
RCU-bh read-side critical section executes during a time of heavy
networking load. There will very likely be an attempt to invoke at least
one softirq handler during that three milliseconds, but any such
invocation will be delayed until the time of the
rcu_read_unlock_bh(). This can of course make it appear at first
glance as if rcu_read_unlock_bh() was executing very slowly.
The `RCU-bh
API <https://lwn.net/Articles/609973/#RCU%20Per-Flavor%20API%20Table>`__
includes rcu_read_lock_bh(), rcu_read_unlock_bh(), rcu_dereference_bh(),
rcu_dereference_bh_check(), and rcu_read_lock_bh_held(). However, the
old RCU-bh update-side APIs are now gone, replaced by synchronize_rcu(),
synchronize_rcu_expedited(), call_rcu(), and rcu_barrier(). In addition,
anything that disables bottom halves also marks an RCU-bh read-side
critical section, including local_bh_disable() and local_bh_enable(),
local_irq_save() and local_irq_restore(), and so on.
Sched flavor의 역사
2540-2582RCU-sched도 flavor 통합 뒤 일반 RCU로 표현된다. Read-side API는 preemption을 disable하고 lockdep에 기록하는 형태로 남았으며 update-side API는 일반 RCU로 대체되었다.
Preemptible RCU에서는 read-side marker 밖의 어느 지점도 QS가 될 수 있어 일반 GP가 기존 interrupt와 NMI handler의 종료까지 기다린다고 보장할 수 없다. RCU-sched는 classic RCU처럼 pre-existing interrupt와 NMI handler까지 기다리는 용도로 만들어졌다. `CONFIG_PREEMPTION=n`에서는 일반 RCU와 구현이 같았다.
`CONFIG_PREEMPTION=y`에서 `rcu_read_lock_sched()`와 unlock은 preemption을 끄고 켠다. Reader 중 preemption 요청이 있었다면 unlock이 scheduler로 들어가므로 느려 보일 수 있지만 최고 우선순위 task는 preempt되지 않아 낮은 비용을 유지한다.
역사적 API에는 `rcu_read_lock_sched()`, `rcu_read_unlock_sched()`, notrace 변형, `rcu_dereference_sched()`, check/held 변형이 있다. `preempt_disable()`이나 interrupt disable 구간도 암묵적인 RCU-sched reader로 취급된다.
FlavorRead-side 특성현재 update-side
RCU-bhsoftirq disable일반 RCU API
RCU-schedpreemption disable일반 RCU API
Read-side 표시는 남고 update-side는 일반 RCU로 통합되었다.
Sched Flavor (Historical)
~~~~~~~~~~~~~~~~~~~~~~~~~
The RCU-sched flavor of RCU has since been expressed in terms of the
other RCU flavors as part of a consolidation of the three flavors into a
single flavor. The read-side API remains, and continues to disable
preemption and to be accounted for by lockdep. Much of the material in
this section is therefore strictly historical in nature.
Before preemptible RCU, waiting for an RCU grace period had the side
effect of also waiting for all pre-existing interrupt and NMI handlers.
However, there are legitimate preemptible-RCU implementations that do
not have this property, given that any point in the code outside of an
RCU read-side critical section can be a quiescent state. Therefore,
*RCU-sched* was created, which follows “classic” RCU in that an
RCU-sched grace period waits for pre-existing interrupt and NMI
handlers. In kernels built with ``CONFIG_PREEMPTION=n``, the RCU and
RCU-sched APIs have identical implementations, while kernels built with
``CONFIG_PREEMPTION=y`` provide a separate implementation for each.
Note well that in ``CONFIG_PREEMPTION=y`` kernels,
rcu_read_lock_sched() and rcu_read_unlock_sched() disable and
re-enable preemption, respectively. This means that if there was a
preemption attempt during the RCU-sched read-side critical section,
rcu_read_unlock_sched() will enter the scheduler, with all the
latency and overhead entailed. Just as with rcu_read_unlock_bh(),
this can make it look as if rcu_read_unlock_sched() was executing
very slowly. However, the highest-priority task won't be preempted, so
that task will enjoy low-overhead rcu_read_unlock_sched()
invocations.
The `RCU-sched
API <https://lwn.net/Articles/609973/#RCU%20Per-Flavor%20API%20Table>`__
includes rcu_read_lock_sched(), rcu_read_unlock_sched(),
rcu_read_lock_sched_notrace(), rcu_read_unlock_sched_notrace(),
rcu_dereference_sched(), rcu_dereference_sched_check(), and
rcu_read_lock_sched_held(). However, the old RCU-sched update-side APIs
are now gone, replaced by synchronize_rcu(), synchronize_rcu_expedited(),
call_rcu(), and rcu_barrier(). In addition, anything that disables
preemption also marks an RCU-sched read-side critical section,
including preempt_disable() and preempt_enable(), local_irq_save()
and local_irq_restore(), and so on.
Sleepable RCU
2583-2711Kernel notifier처럼 대부분은 잠들지 않지만 드물게 block해야 하는 reader를 위해 SRCU가 도입되었다. 각 SRCU domain은 `srcu_struct` 인스턴스로 정의되고 모든 API에 그 포인터를 넘긴다. 한 domain의 느린 reader는 다른 domain의 grace period를 지연시키지 않는다.
`srcu_read_lock(&ss)`는 cookie를 반환하고 같은 값을 `srcu_read_unlock(&ss, idx)`에 넘긴다. Reader 안에서 block할 수 있지만 영원히 block하면 해당 domain GP도 영원히 멈춘다. Reader 안에서 같은 domain의 `synchronize_srcu()`를 직접 기다리거나 mutex 의존성을 통해 간접 순환을 만들면 deadlock한다. 순환은 여러 SRCU domain에 걸쳐 길게 이어질 수도 있다.
SRCU reader는 idle 또는 offline CPU에서도 실행할 수 있다. 이를 위해 lock과 unlock에 memory barrier가 들어가 일반 RCU보다 느리다. `smp_mb__after_srcu_read_unlock()`은 unlock과 조합해 full barrier를 보장한다.
`synchronize_srcu()`와 `srcu_barrier()`는 CPU-hotplug notifier에서 금지된다. SRCU GP가 사용하는 timer가 outgoing CPU에 stranded되어 notifier가 GP를 기다리고 GP가 timer를 기다리는 deadlock이 생길 수 있다.
현재 SRCU의 expedited와 non-expedited GP는 같은 mechanism을 사용하므로 미래 GP를 expedite하면 아직 끝나지 않은 이전 GP도 빨라진다. `srcutree.exp_holdoff` 기본 25 microsecond보다 오래 idle이었던 SRCU를 `synchronize_srcu()`가 깨우면 자동 expedite한다. v4.12부터 callback은 per-CPU로 관리하지만 초당 CPU별 백만 callback 같은 flooding은 별도 시험이 필요하다.
기본 API 외에 `start_poll_synchronize_srcu()`는 미래 GP를 시작하고 cookie를 반환하며, `poll_state_synchronize_srcu()`는 cookie의 완료 여부를 확인한다. `get_state_synchronize_srcu()`는 cookie만 얻고 GP 시작은 보장하지 않는다. Multi-stage buffer-cache age-out에서 불필요한 GP를 피하는 데 쓰인다.
idx = srcu_read_lock(&ss)→필요하면 block→domain ss의 객체 접근→srcu_read_unlock(&ss, idx)→synchronize_srcu(&ss)가 reader 종료 관찰
Cookie가 reader의 accounting bank를 lock과 unlock 사이에 전달한다.
APIGP 시작 보장반환
start_poll_synchronize_srcu()예미래 GP cookie
poll_state_synchronize_srcu()해당 없음완료 여부 bool
get_state_synchronize_srcu()아니요현재 상태 cookie
GP 시작 여부와 완료 확인을 분리한다.
Sleepable RCU
~~~~~~~~~~~~~
For well over a decade, someone saying “I need to block within an RCU
read-side critical section” was a reliable indication that this someone
did not understand RCU. After all, if you are always blocking in an RCU
read-side critical section, you can probably afford to use a
higher-overhead synchronization mechanism. However, that changed with
the advent of the Linux kernel's notifiers, whose RCU read-side critical
sections almost never sleep, but sometimes need to. This resulted in the
introduction of `sleepable RCU <https://lwn.net/Articles/202847/>`__, or
*SRCU*.
SRCU allows different domains to be defined, with each such domain
defined by an instance of an ``srcu_struct`` structure. A pointer to
this structure must be passed in to each SRCU function, for example,
``synchronize_srcu(&ss)``, where ``ss`` is the ``srcu_struct``
structure. The key benefit of these domains is that a slow SRCU reader
in one domain does not delay an SRCU grace period in some other domain.
That said, one consequence of these domains is that read-side code must
pass a “cookie” from srcu_read_lock() to srcu_read_unlock(), for
example, as follows:
::
1 int idx;
2
3 idx = srcu_read_lock(&ss);
4 do_something();
5 srcu_read_unlock(&ss, idx);
As noted above, it is legal to block within SRCU read-side critical
sections, however, with great power comes great responsibility. If you
block forever in one of a given domain's SRCU read-side critical
sections, then that domain's grace periods will also be blocked forever.
Of course, one good way to block forever is to deadlock, which can
happen if any operation in a given domain's SRCU read-side critical
section can wait, either directly or indirectly, for that domain's grace
period to elapse. For example, this results in a self-deadlock:
::
1 int idx;
2
3 idx = srcu_read_lock(&ss);
4 do_something();
5 synchronize_srcu(&ss);
6 srcu_read_unlock(&ss, idx);
However, if line 5 acquired a mutex that was held across a
synchronize_srcu() for domain ``ss``, deadlock would still be
possible. Furthermore, if line 5 acquired a mutex that was held across a
synchronize_srcu() for some other domain ``ss1``, and if an
``ss1``-domain SRCU read-side critical section acquired another mutex
that was held across as ``ss``-domain synchronize_srcu(), deadlock
would again be possible. Such a deadlock cycle could extend across an
arbitrarily large number of different SRCU domains. Again, with great
power comes great responsibility.
Unlike the other RCU flavors, SRCU read-side critical sections can run
on idle and even offline CPUs. This ability requires that
srcu_read_lock() and srcu_read_unlock() contain memory barriers,
which means that SRCU readers will run a bit slower than would RCU
readers. It also motivates the smp_mb__after_srcu_read_unlock() API,
which, in combination with srcu_read_unlock(), guarantees a full
memory barrier.
Also unlike other RCU flavors, synchronize_srcu() may **not** be
invoked from CPU-hotplug notifiers, due to the fact that SRCU grace
periods make use of timers and the possibility of timers being
temporarily “stranded” on the outgoing CPU. This stranding of timers
means that timers posted to the outgoing CPU will not fire until late in
the CPU-hotplug process. The problem is that if a notifier is waiting on
an SRCU grace period, that grace period is waiting on a timer, and that
timer is stranded on the outgoing CPU, then the notifier will never be
awakened, in other words, deadlock has occurred. This same situation of
course also prohibits srcu_barrier() from being invoked from
CPU-hotplug notifiers.
SRCU also differs from other RCU flavors in that SRCU's expedited and
non-expedited grace periods are implemented by the same mechanism. This
means that in the current SRCU implementation, expediting a future grace
period has the side effect of expediting all prior grace periods that
have not yet completed. (But please note that this is a property of the
current implementation, not necessarily of future implementations.) In
addition, if SRCU has been idle for longer than the interval specified
by the ``srcutree.exp_holdoff`` kernel boot parameter (25 microseconds
by default), and if a synchronize_srcu() invocation ends this idle
period, that invocation will be automatically expedited.
As of v4.12, SRCU's callbacks are maintained per-CPU, eliminating a
locking bottleneck present in prior kernel versions. Although this will
allow users to put much heavier stress on call_srcu(), it is
important to note that SRCU does not yet take any special steps to deal
with callback flooding. So if you are posting (say) 10,000 SRCU
callbacks per second per CPU, you are probably totally OK, but if you
intend to post (say) 1,000,000 SRCU callbacks per second per CPU, please
run some tests first. SRCU just might need a few adjustment to deal with
that sort of load. Of course, your mileage may vary based on the speed
of your CPUs and the size of your memory.
The `SRCU
API <https://lwn.net/Articles/609973/#RCU%20Per-Flavor%20API%20Table>`__
includes srcu_read_lock(), srcu_read_unlock(),
srcu_dereference(), srcu_dereference_check(),
synchronize_srcu(), synchronize_srcu_expedited(),
call_srcu(), srcu_barrier(), and srcu_read_lock_held(). It
also includes DEFINE_SRCU(), DEFINE_STATIC_SRCU(), and
init_srcu_struct() APIs for defining and initializing
``srcu_struct`` structures.
More recently, the SRCU API has added polling interfaces:
#. start_poll_synchronize_srcu() returns a cookie identifying
the completion of a future SRCU grace period and ensures
that this grace period will be started.
#. poll_state_synchronize_srcu() returns ``true`` iff the
specified cookie corresponds to an already-completed
SRCU grace period.
#. get_state_synchronize_srcu() returns a cookie just like
start_poll_synchronize_srcu() does, but differs in that
it does nothing to ensure that any future SRCU grace period
will be started.
These functions are used to avoid unnecessary SRCU grace periods in
certain types of buffer-cache algorithms having multi-stage age-out
mechanisms. The idea is that by the time the block has aged completely
from the cache, an SRCU grace period will be very likely to have elapsed.
Tasks RCU
2712-2757Tracing trampoline은 code rewriting으로 probe를 설치한다. 어느 코드에나 들어갈 수 있어 명시적 `rcu_read_lock()` marker를 넣을 수 없고, trampoline 안에 unlock을 두어도 그 뒤 명령이 모두 끝났는지 일반 GP가 보장하지 못한다. 보호는 trampoline 진입 주소를 계산하는 앞쪽 명령까지 확장되어야 할 수도 있다.
Tasks RCU는 voluntary context switch, userspace 진입/이탈 같은 암묵적 경계를 사용한다. `schedule()`과 명시적인 Tasks-RCU QS가 critical section을 나누며 idle task는 무시한다. Involuntary preemption은 QS가 아니다. Trampoline에서 preempt된 task가 재개해 그 코드를 벗어나기 전에는 GP가 끝나면 안 된다.
Softirq에서는 `rcu_softirq_qs()`, 그 밖에서는 `rcu_tasks_classic_qs()`로 명시적인 QS를 제공한다. API는 `call_rcu_tasks()`, `synchronize_rcu_tasks()`, `rcu_barrier_tasks()`다. Non-preemptible kernel에서는 trampoline이 preempt되지 않으므로 일반 RCU API로 mapping할 수 있고, preemptible kernel은 voluntary context switch를 별도로 추적한다.
옛 trampoline을 가리킬 수 있는 실행→voluntary context switch 또는 userspace 전환→모든 task가 경계 통과→Tasks RCU grace period 완료→옛 trampoline 해제
명시적 reader marker 대신 task가 안전한 실행 경계를 통과했는지 본다.
Tasks RCU
~~~~~~~~~
Some forms of tracing use “trampolines” to handle the binary rewriting
required to install different types of probes. It would be good to be
able to free old trampolines, which sounds like a job for some form of
RCU. However, because it is necessary to be able to install a trace
anywhere in the code, it is not possible to use read-side markers such
as rcu_read_lock() and rcu_read_unlock(). In addition, it does
not work to have these markers in the trampoline itself, because there
would need to be instructions following rcu_read_unlock(). Although
synchronize_rcu() would guarantee that execution reached the
rcu_read_unlock(), it would not be able to guarantee that execution
had completely left the trampoline. Worse yet, in some situations
the trampoline's protection must extend a few instructions *prior* to
execution reaching the trampoline. For example, these few instructions
might calculate the address of the trampoline, so that entering the
trampoline would be pre-ordained a surprisingly long time before execution
actually reached the trampoline itself.
The solution, in the form of `Tasks
RCU <https://lwn.net/Articles/607117/>`__, is to have implicit read-side
critical sections that are delimited by voluntary context switches, that
is, calls to schedule(), cond_resched(), and
synchronize_rcu_tasks(). In addition, transitions to and from
userspace execution also delimit tasks-RCU read-side critical sections.
Idle tasks are ignored by Tasks RCU, and Tasks Rude RCU may be used to
interact with them.
Note well that involuntary context switches are *not* Tasks-RCU quiescent
states. After all, in preemptible kernels, a task executing code in a
trampoline might be preempted. In this case, the Tasks-RCU grace period
clearly cannot end until that task resumes and its execution leaves that
trampoline. This means, among other things, that cond_resched() does
not provide a Tasks RCU quiescent state. (Instead, use rcu_softirq_qs()
from softirq or rcu_tasks_classic_qs() otherwise.)
The tasks-RCU API is quite compact, consisting only of
call_rcu_tasks(), synchronize_rcu_tasks(), and
rcu_barrier_tasks(). In ``CONFIG_PREEMPTION=n`` kernels, trampolines
cannot be preempted, so these APIs map to call_rcu(),
synchronize_rcu(), and rcu_barrier(), respectively. In
``CONFIG_PREEMPTION=y`` kernels, trampolines can be preempted, and these
three APIs are therefore implemented by separate functions that check
for voluntary context switches.
Tasks Rude RCU
2758-2777일부 tracing은 RCU가 watching하지 않는 구간까지 포함해 모든 online CPU의 preemption-disabled region이 끝나기를 기다려야 한다. 일반 `synchronize_rcu()`로는 충분하지 않아 Tasks Rude RCU를 사용한다.
이 flavor는 각 online CPU에 workqueue 작업을 강제로 schedule한다. 이 때문에 `nohz_full` 실시간 CPU에 IPI를 보내고 idle CPU를 깨우므로 이름처럼 workload 관점에서 무례한 동작이다. Kernel entry/exit와 deep-idle 함수가 충분히 `noinstr`로 표시되면 Tasks RCU가 더 많은 idle task를 직접 추적해 이 flavor를 제거할 가능성이 있다.
Reader marker는 없고 API는 `synchronize_rcu_tasks_rude()` 하나뿐이다.
온라인 CPU 집합→CPU별 workqueue 강제 배치→각 CPU가 작업 실행→이전 disabled 구간 종료 확인→GP 완료
각 CPU에서 강제 schedule 지점을 만들어 preemption-disabled 실행이 지나갔음을 확인한다.
Tasks Rude RCU
~~~~~~~~~~~~~~
Some forms of tracing need to wait for all preemption-disabled regions
of code running on any online CPU, including those executed when RCU is
not watching. This means that synchronize_rcu() is insufficient, and
Tasks Rude RCU must be used instead. This flavor of RCU does its work by
forcing a workqueue to be scheduled on each online CPU, hence the "Rude"
moniker. And this operation is considered to be quite rude by real-time
workloads that don't want their ``nohz_full`` CPUs receiving IPIs and
by battery-powered systems that don't want their idle CPUs to be awakened.
Once kernel entry/exit and deep-idle functions have been properly tagged
``noinstr``, Tasks RCU can start paying attention to idle tasks (except
those that are idle from RCU's perspective) and then Tasks Rude RCU can
be removed from the kernel.
The tasks-rude-RCU API is also reader-marking-free and thus quite compact,
consisting solely of synchronize_rcu_tasks_rude().
Tasks Trace RCU
2778-2793일부 tracing reader는 sleep해야 하지만 `srcu_read_lock()`과 unlock 양쪽의 full memory barrier 비용을 감당할 수 없다. Tasks Trace RCU는 scheduler locking과 IPI로 reader와 동기화해 이 요구를 만족한다.
실시간 시스템이 IPI를 허용할 수 없으면 `CONFIG_TASKS_TRACE_RCU_READ_MB=y`를 사용한다. 이 구성은 IPI 대신 read-side primitive에 full memory barrier를 추가하므로 비용 위치를 updater에서 reader로 옮긴다.
API는 `rcu_read_lock_trace()`, `rcu_read_unlock_trace()`, `rcu_read_lock_trace_held()`, `call_rcu_tasks_trace()`, `synchronize_rcu_tasks_trace()`, `rcu_barrier_tasks_trace()`로 구성된다.
구성동기화 비용
기본scheduler lock과 IPI
CONFIG_TASKS_TRACE_RCU_READ_MB=yreader lock/unlock의 full memory barrier
IPI와 reader barrier 사이 tradeoff다.
Tasks Trace RCU
~~~~~~~~~~~~~~~
Some forms of tracing need to sleep in readers, but cannot tolerate
SRCU's read-side overhead, which includes a full memory barrier in both
srcu_read_lock() and srcu_read_unlock(). This need is handled by a
Tasks Trace RCU that uses scheduler locking and IPIs to synchronize with
readers. Real-time systems that cannot tolerate IPIs may build their
kernels with ``CONFIG_TASKS_TRACE_RCU_READ_MB=y``, which avoids the IPIs at
the expense of adding full memory barriers to the read-side primitives.
The tasks-trace-RCU API is also reasonably compact,
consisting of rcu_read_lock_trace(), rcu_read_unlock_trace(),
rcu_read_lock_trace_held(), call_rcu_tasks_trace(),
synchronize_rcu_tasks_trace(), and rcu_barrier_tasks_trace().
가능한 향후 변경
2794-2849RCU는 updater 확장성을 얻기 위해 CPU 수가 늘수록 grace-period latency를 키우는 기법을 사용한다. 이것이 실제 문제가 되면 추가 latency 없이 확장되도록 GP state machine을 다시 설계해야 한다.
`rcu_barrier()` 등 일부 경로는 CPU hotplug를 disable한다. Hotplug notifier에서 barrier를 써야 할 강한 이유가 생기면 이 제약을 없애야 하지만 복잡성이 커진다. Expedited GP의 latency와 다른 CPU에 보내는 IPI 수도 동시에 0으로 만들 수는 없으나 tradeoff를 더 개선할 수 있다.
`rcu_node` combining tree는 lock contention과 cache locality를 줄이지만 NUMA node, socket, core 경계에 맞춰 메모리를 분산하지는 않는다. Reader hot path와 일반 `call_rcu()`가 tree를 건드리지 않아 현재는 불필요하다고 본다. 필요하면 먼저 `rcutree.rcu_fanout_leaf`를 socket 또는 NUMA CPU 수에 맞춰 실제 workload로 검증해야 한다.
CPU 번호 remapping까지 요구하는 배치는 필요성과 대안 검토를 매우 강하게 입증해야 한다. RCU kthread와 softirq가 극단 부하를 더 우아하게 처리하도록 조정하고, callback CPU 비용을 원래 `call_rcu()` 호출자에 귀속하는 분석 기능도 고려할 수 있다. Heavy load의 GP와 callback 전진 진행 보장도 계속 개선할 영역이다.
영역잠재 변경
GP latencyCPU 수 증가에 따른 지연 완화
CPU hotplugrcu_barrier()의 hotplug disable 축소
Expedited GPIPI와 latency tradeoff 개선
NUMA topologyfanout과 배치 정렬
Accountingcallback 비용을 발생시킨 호출에 귀속
Forward progress극단 부하 보장 강화
새 복잡성은 측정된 실제 필요가 있을 때만 도입한다.
Possible Future Changes
-----------------------
One of the tricks that RCU uses to attain update-side scalability is to
increase grace-period latency with increasing numbers of CPUs. If this
becomes a serious problem, it will be necessary to rework the
grace-period state machine so as to avoid the need for the additional
latency.
RCU disables CPU hotplug in a few places, perhaps most notably in the
rcu_barrier() operations. If there is a strong reason to use
rcu_barrier() in CPU-hotplug notifiers, it will be necessary to
avoid disabling CPU hotplug. This would introduce some complexity, so
there had better be a *very* good reason.
The tradeoff between grace-period latency on the one hand and
interruptions of other CPUs on the other hand may need to be
re-examined. The desire is of course for zero grace-period latency as
well as zero interprocessor interrupts undertaken during an expedited
grace period operation. While this ideal is unlikely to be achievable,
it is quite possible that further improvements can be made.
The multiprocessor implementations of RCU use a combining tree that
groups CPUs so as to reduce lock contention and increase cache locality.
However, this combining tree does not spread its memory across NUMA
nodes nor does it align the CPU groups with hardware features such as
sockets or cores. Such spreading and alignment is currently believed to
be unnecessary because the hotpath read-side primitives do not access
the combining tree, nor does call_rcu() in the common case. If you
believe that your architecture needs such spreading and alignment, then
your architecture should also benefit from the
``rcutree.rcu_fanout_leaf`` boot parameter, which can be set to the
number of CPUs in a socket, NUMA node, or whatever. If the number of
CPUs is too large, use a fraction of the number of CPUs. If the number
of CPUs is a large prime number, well, that certainly is an
“interesting” architectural choice! More flexible arrangements might be
considered, but only if ``rcutree.rcu_fanout_leaf`` has proven
inadequate, and only if the inadequacy has been demonstrated by a
carefully run and realistic system-level workload.
Please note that arrangements that require RCU to remap CPU numbers will
require extremely good demonstration of need and full exploration of
alternatives.
RCU's various kthreads are reasonably recent additions. It is quite
likely that adjustments will be required to more gracefully handle
extreme loads. It might also be necessary to be able to relate CPU
utilization by RCU's kthreads and softirq handlers to the code that
instigated this CPU utilization. For example, RCU callback overhead
might be charged back to the originating call_rcu() instance, though
probably not in production kernels.
Additional work may be required to provide reasonable forward-progress
guarantees under heavy load for grace periods and for callback
invocation.
요약과 감사의 말
2850-2865이 문서는 20년이 넘는 기간 동안 드러난 RCU 요구사항을 모았다. 요구사항은 커널, compiler, 하드웨어, workload가 변하면서 계속 바뀌므로 최종 명세는 아니지만, 중요한 부분을 한곳에 제시한다.
문서를 사람이 읽을 수 있게 다듬는 데 Steven Rostedt, Lai Jiangshan, Ingo Molnar, Oleg Nesterov, Borislav Petkov, Peter Zijlstra, Boqun Feng, Andy Lutomirski가 도움을 주었고 Michelle Rankin이 작업을 지원했다. 그 밖의 기여는 Linux kernel git archive에 기록되어 있다.
기존 reader와 회수 분리→안전한 publish/subscribe→강한 GP ordering→확장성과 실시간성→Linux 실행 상태 통합→진단과 지속 검증
빠른 reader 하나만이 아니라 수명, 진행, 통합, 검증을 함께 만족하는 계약이다.
Summary
-------
This document has presented more than two decade's worth of RCU
requirements. Given that the requirements keep changing, this will not
be the last word on this subject, but at least it serves to get an
important subset of the requirements set forth.
Acknowledgments
---------------
I am grateful to Steven Rostedt, Lai Jiangshan, Ingo Molnar, Oleg
Nesterov, Borislav Petkov, Peter Zijlstra, Boqun Feng, and Andy
Lutomirski for their help in rendering this article human readable, and
to Michelle Rankin for her support of this effort. Other contributions
are acknowledged in the Linux kernel's git archive.
요약·해설
Requirements.rst:1-2865RCU가 제공하는 의미론적 보장과 제공하지 않는 배타성, 그리고 Linux 커널에서 그 보장을 실제로 유지하기 위한 구성·부팅·interrupt·hotplug·scheduler·에너지·실시간·신뢰성 요구사항을 함께 읽는 문서입니다.