Review Checklist for RCU Patches

RCU patch 검토 checklist의 목적

이 문서는 RCU를 사용하는 patch를 작성하고 review할 때 확인할 checklist입니다. 아래 규칙을 어기면 필요한 lock primitive를 빠뜨린 것과 같은 종류의 문제가 생깁니다. 오랜 기간의 patch review 경험을 바탕으로 작성됐으며 개선 제안은 언제든 환영합니다.

.. SPDX-License-Identifier: GPL-2.0

================================
Review Checklist for RCU Patches
================================


This document contains a checklist for producing and reviewing patches
that make use of RCU.  Violating any of the rules listed below will
result in the same sorts of problems that leaving out a locking primitive
would cause.  This list is based on experiences reviewing such patches
over a rather long period of time, but improvements are always welcome!

0. RCU가 적합한 read-mostly workload인가

Data structure update 비율이 약 10%보다 높으면 상세 성능 측정이 RCU의 우위를 입증하지 않는 한 다른 방법을 강하게 고려해야 합니다. RCU는 read-side 비용을 낮추는 대신 write-side 비용을 늘리므로 일반적인 사용처는 update보다 read가 훨씬 많습니다.

예외는 성능이 중요하지 않고 RCU가 구현을 단순하게 만드는 경우입니다. 예로 NMI가 드문 architecture의 Linux 2.6 dynamic NMI code가 있습니다. RCU read primitive의 낮은 real-time latency가 결정적인 경우도 예외입니다.

또 다른 예외는 lockless update의 ABA problem을 막기 위해 RCU reader를 쓰는 경우입니다. `rcu_read_lock()`과 `rcu_read_unlock()`이 update를 보호하는 모양이 직관에 어긋나 보이지만, 일부 lockless algorithm에 garbage collector와 비슷한 단순화를 제공합니다.

0.        Is RCU being applied to a read-mostly situation?  If the data
        structure is updated more than about 10% of the time, then you
        should strongly consider some other approach, unless detailed
        performance measurements show that RCU is nonetheless the right
        tool for the job.  Yes, RCU does reduce read-side overhead by
        increasing write-side overhead, which is exactly why normal uses
        of RCU will do much more reading than updating.

        Another exception is where performance is not an issue, and RCU
        provides a simpler implementation.  An example of this situation
        is the dynamic NMI code in the Linux 2.6 kernel, at least on
        architectures where NMIs are rare.

        Yet another exception is where the low real-time latency of RCU's
        read-side primitives is critically important.

        One final exception is where RCU readers are used to prevent
        the ABA problem (https://en.wikipedia.org/wiki/ABA_problem)
        for lockless updates.  This does result in the mildly
        counter-intuitive situation where rcu_read_lock() and
        rcu_read_unlock() are used to protect updates, however, this
        approach can provide the same simplifications to certain types
        of lockless algorithms that garbage collectors do.

1. Updater의 mutual exclusion

RCU reader는 거의 아무 동기화 없이 실행할 수 있지만 writer에는 여전히 mutual exclusion이 필요합니다. 선택지는 lock, atomic operation, 또는 update를 하나의 task로 제한하는 것입니다.

Atomic operation을 선택하면 weakly ordered machine에서 memory barrier를 어떻게 처리했는지, 그 복잡성이 왜 필요한지 설명해야 합니다. X86도 뒤 load가 앞 store보다 먼저 보이도록 reorder할 수 있습니다.

Single updater task를 선택하면 큰 system에서 bottleneck이 되지 않는 이유를 설명해야 합니다. Task가 자기 정보만 갱신하고 다른 task가 읽는 경우처럼 본질적으로 bottleneck이 없는 구조도 있습니다. 문서가 강조하듯 '큰 system'의 기준은 시대에 따라 달라집니다.

1.        Does the update code have proper mutual exclusion?

        RCU does allow *readers* to run (almost) naked, but *writers* must
        still use some sort of mutual exclusion, such as:

        a.        locking,
        b.        atomic operations, or
        c.        restricting updates to a single task.

        If you choose #b, be prepared to describe how you have handled
        memory barriers on weakly ordered machines (pretty much all of
        them -- even x86 allows later loads to be reordered to precede
        earlier stores), and be prepared to explain why this added
        complexity is worthwhile.  If you choose #c, be prepared to
        explain how this single task does not become a major bottleneck
        on large systems (for example, if the task is updating information
        relating to itself that other tasks can read, there by definition
        can be no bottleneck).        Note that the definition of "large" has
        changed significantly:        Eight CPUs was "large" in the year 2000,
        but a hundred CPUs was unremarkable in 2017.

2. Read-side critical section과 pointer lifetime

`rcu_read_lock()` 계열은 grace period가 너무 일찍 끝나 reader가 사용하는 data가 해제되는 일을 막습니다. 대략적인 원칙은 RCU-protected pointer의 모든 dereference를 `rcu_read_lock()`, `rcu_read_lock_bh()`, `rcu_read_lock_sched()` 또는 적절한 update-side lock으로 감싸는 것입니다.

`preempt_disable()` 같은 명시적 preemption disable은 `rcu_read_lock_sched()` 역할을 할 수 있지만 가독성이 낮고 lockdep의 locking 검출을 막습니다. Raw spinlock 획득도 RCU read-side critical section에 진입합니다.

`guard(rcu)()`는 현재 scope의 나머지를, `scoped_guard(rcu)`는 다음 statement를 RCU read-side critical section으로 지정합니다. Guard는 수동 lock/unlock pair보다 오류 가능성을 줄일 수 있습니다.

Non-preemptible kernel에서만 build된다는 가정에 의존하면 안 됩니다. 특히 `CONFIG_PREEMPT_COUNT=y`에서 깨질 수 있습니다. RCU-protected pointer를 critical section 밖으로 내보내려면 그 전에 lock이나 reference count 같은 별도 보호를 확보해야 합니다.

2.        Do the RCU read-side critical sections make proper use of
        rcu_read_lock() and friends?  These primitives are needed
        to prevent grace periods from ending prematurely, which
        could result in data being unceremoniously freed out from
        under your read-side code, which can greatly increase the
        actuarial risk of your kernel.

        As a rough rule of thumb, any dereference of an RCU-protected
        pointer must be covered by rcu_read_lock(), rcu_read_lock_bh(),
        rcu_read_lock_sched(), or by the appropriate update-side lock.
        Explicit disabling of preemption (preempt_disable(), for example)
        can serve as rcu_read_lock_sched(), but is less readable and
        prevents lockdep from detecting locking issues.  Acquiring a
        raw spinlock also enters an RCU read-side critical section.

        The guard(rcu)() and scoped_guard(rcu) primitives designate
        the remainder of the current scope or the next statement,
        respectively, as the RCU read-side critical section.  Use of
        these guards can be less error-prone than rcu_read_lock(),
        rcu_read_unlock(), and friends.

        Please note that you *cannot* rely on code known to be built
        only in non-preemptible kernels.  Such code can and will break,
        especially in kernels built with CONFIG_PREEMPT_COUNT=y.

        Letting RCU-protected pointers "leak" out of an RCU read-side
        critical section is every bit as bad as letting them leak out
        from under a lock.  Unless, of course, you have arranged some
        other means of protection, such as a lock or a reference count
        *before* letting them out of the RCU read-side critical section.

3. Concurrent reader가 보는 update 상태

RCU의 목적은 reader가 lock이나 atomic operation 없이 update와 동시에 실행되게 하는 것입니다. 가장 좋은 방법은 RCU용 list·hlist update primitive 또는 kernel의 다른 RCU-protected data structure로 element를 추가·제거·교체하는 것입니다.

Element별 state도 reader와 writer가 함께 접근한다면 per-element lock을 둘 수 있습니다. Reader가 보지 않는 field는 updater만 획득하는 별도 lock으로 보호할 수 있습니다.

Update를 reader에게 atomic하게 보이게 할 수도 있습니다. 정렬된 pointer 하나나 개별 atomic primitive는 atomic하게 보이지만 lock 안에서 수행한 여러 operation 또는 여러 atomic primitive의 sequence는 RCU reader에게 하나의 atomic update로 보이지 않습니다. 여러 field를 별도 structure로 묶고 pointer 하나를 바꾸면 이 문제를 해결할 수 있습니다.

Update와 read 순서를 정교하게 설계해 모든 중간 단계가 valid하게 보이도록 할 수도 있지만 CPU reorder 때문에 어렵습니다. 가능하면 `smp_store_release()`와 `smp_load_acquire()`를 쓰고 필요한 경우 `smp_mb()` full barrier를 사용합니다. 보통은 변경 data를 새 structure에 모아 pointer 교체를 atomic하게 보이게 하는 편이 낫습니다.

3.        Does the update code tolerate concurrent accesses?

        The whole point of RCU is to permit readers to run without
        any locks or atomic operations.  This means that readers will
        be running while updates are in progress.  There are a number
        of ways to handle this concurrency, depending on the situation:

        a.        Use the RCU variants of the list and hlist update
                primitives to add, remove, and replace elements on
                an RCU-protected list.        Alternatively, use the other
                RCU-protected data structures that have been added to
                the Linux kernel.

                This is almost always the best approach.

        b.        Proceed as in (a) above, but also maintain per-element
                locks (that are acquired by both readers and writers)
                that guard per-element state.  Fields that the readers
                refrain from accessing can be guarded by some other lock
                acquired only by updaters, if desired.

                This also works quite well.

        c.        Make updates appear atomic to readers.        For example,
                pointer updates to properly aligned fields will
                appear atomic, as will individual atomic primitives.
                Sequences of operations performed under a lock will *not*
                appear to be atomic to RCU readers, nor will sequences
                of multiple atomic primitives.        One alternative is to
                move multiple individual fields to a separate structure,
                thus solving the multiple-field problem by imposing an
                additional level of indirection.

                This can work, but is starting to get a bit tricky.

        d.        Carefully order the updates and the reads so that readers
                see valid data at all phases of the update.  This is often
                more difficult than it sounds, especially given modern
                CPUs' tendency to reorder memory references.  One must
                usually liberally sprinkle memory-ordering operations
                through the code, making it difficult to understand and
                to test.  Where it works, it is better to use things
                like smp_store_release() and smp_load_acquire(), but in
                some cases the smp_mb() full memory barrier is required.

                As noted earlier, it is usually better to group the
                changing data into a separate structure, so that the
                change may be made to appear atomic by updating a pointer
                to reference a new structure containing updated values.

4. Weak memory ordering과 RCU primitive

거의 모든 CPU는 weakly ordered이며 x86도 뒤 load가 앞 store보다 먼저 실행되는 reorder를 허용합니다. Reader는 `rcu_dereference()`로 pointer를 먼저 얻고 그 pointer가 가리키는 data를 나중에 읽도록 순서를 보장해야 합니다. Alpha에서는 특히 필수입니다.

`rcu_dereference()`는 RCU 보호 pointer를 표시하는 문서화 수단이자 공격적인 compiler optimization을 막는 장치입니다. 반환값을 잘못 다룰 여지는 있으므로 `rcu_dereference.rst`를 참조해야 합니다.

`list_for_each_entry_rcu()` 같은 `_rcu()` traversal primitive도 내부에서 `rcu_dereference()`를 사용합니다. Reader와 updater가 공유하는 code에서는 updater도 이를 써도 되지만 RCU read section 밖이면 lockdep이 경고할 수 있으므로 `lockdep.rst`의 조건 표현을 사용해야 합니다. 이 primitive들이 여러 updater 사이의 올바른 concurrency design을 대신하지는 않습니다.

List 삽입에는 `list_add_tail_rcu()` 또는 `list_add_rcu()`, hlist 삽입에는 `hlist_add_head_rcu()`를 써서 structure initialization과 pointer publication의 reorder를 막습니다. 삭제에는 pointer poisoning이 reader를 해치지 않도록 `list_del_rcu()` 또는 `hlist_del_rcu()`를 씁니다. 교체에는 `list_replace_rcu()`와 `hlist_replace_rcu()`를 사용하며 `hlist_nulls`에도 같은 원칙이 적용됩니다.

새 structure를 가리키는 pointer는 structure initialization이 모두 끝난 뒤 공개해야 하며, RCU reader가 순회할 수 있는 pointer의 publication에는 `rcu_assign_pointer()`를 사용합니다.

4.        Weakly ordered CPUs pose special challenges.  Almost all CPUs
        are weakly ordered -- even x86 CPUs allow later loads to be
        reordered to precede earlier stores.  RCU code must take all of
        the following measures to prevent memory-corruption problems:

        a.        Readers must maintain proper ordering of their memory
                accesses.  The rcu_dereference() primitive ensures that
                the CPU picks up the pointer before it picks up the data
                that the pointer points to.  This really is necessary
                on Alpha CPUs.

                The rcu_dereference() primitive is also an excellent
                documentation aid, letting the person reading the
                code know exactly which pointers are protected by RCU.
                Please note that compilers can also reorder code, and
                they are becoming increasingly aggressive about doing
                just that.  The rcu_dereference() primitive therefore also
                prevents destructive compiler optimizations.  However,
                with a bit of devious creativity, it is possible to
                mishandle the return value from rcu_dereference().
                Please see rcu_dereference.rst for more information.

                The rcu_dereference() primitive is used by the
                various "_rcu()" list-traversal primitives, such
                as the list_for_each_entry_rcu().  Note that it is
                perfectly legal (if redundant) for update-side code to
                use rcu_dereference() and the "_rcu()" list-traversal
                primitives.  This is particularly useful in code that
                is common to readers and updaters.  However, lockdep
                will complain if you access rcu_dereference() outside
                of an RCU read-side critical section.  See lockdep.rst
                to learn what to do about this.

                Of course, neither rcu_dereference() nor the "_rcu()"
                list-traversal primitives can substitute for a good
                concurrency design coordinating among multiple updaters.

        b.        If the list macros are being used, the list_add_tail_rcu()
                and list_add_rcu() primitives must be used in order
                to prevent weakly ordered machines from misordering
                structure initialization and pointer planting.
                Similarly, if the hlist macros are being used, the
                hlist_add_head_rcu() primitive is required.

        c.        If the list macros are being used, the list_del_rcu()
                primitive must be used to keep list_del()'s pointer
                poisoning from inflicting toxic effects on concurrent
                readers.  Similarly, if the hlist macros are being used,
                the hlist_del_rcu() primitive is required.

                The list_replace_rcu() and hlist_replace_rcu() primitives
                may be used to replace an old structure with a new one
                in their respective types of RCU-protected lists.

        d.        Rules similar to (4b) and (4c) apply to the "hlist_nulls"
                type of RCU-protected linked lists.

        e.        Updates must ensure that initialization of a given
                structure happens before pointers to that structure are
                publicized.  Use the rcu_assign_pointer() primitive
                when publicizing a pointer to a structure that can
                be traversed by an RCU read-side critical section.

5. RCU callback은 block할 수 없다

`call_rcu()`, `call_srcu()`, `call_rcu_tasks()`, `call_rcu_tasks_trace()` callback은 softirq context에서 호출될 수 있고 항상 bottom half가 disable된 상태로 실행됩니다. 따라서 callback은 block하면 안 됩니다. Block이 필요하면 callback에서 workqueue handler를 schedule하고, `call_rcu()`에는 이를 대신하는 `queue_rcu_work()`를 사용할 수 있습니다.

5.        If any of call_rcu(), call_srcu(), call_rcu_tasks(), or
        call_rcu_tasks_trace() is used, the callback function may be
        invoked from softirq context, and in any case with bottom halves
        disabled.  In particular, this callback function cannot block.
        If you need the callback to block, run that code in a workqueue
        handler scheduled from the callback.  The queue_rcu_work()
        function does this for you in the case of call_rcu().

6. synchronize 계열의 context와 expedited 사용 제한

`synchronize_rcu()`는 block할 수 있으므로 어떤 irq context에서도 호출할 수 없습니다. 같은 규칙이 `synchronize_srcu()`, `synchronize_rcu_expedited()`, `synchronize_srcu_expedited()`, `synchronize_rcu_tasks()`, `synchronize_rcu_tasks_rude()`, `synchronize_rcu_tasks_trace()`에 적용됩니다.

Expedited form은 일반 form과 semantics는 같지만 CPU 비용이 더 큽니다. Real-time workload 중에는 보통 수행하지 않는 드문 configuration change에만 제한해야 합니다. IPI에 민감한 RT workload는 `rcupdate.rcu_normal` boot parameter로 expedited grace period를 완전히 disable할 수 있지만 성능 영향이 있을 수 있습니다.

Expedited primitive를 loop에서 반복 호출하지 말고 update를 batch하여 일반 primitive 한 번으로 전체를 기다리는 편이 대개 더 빠르고 system과 RT workload에 부담이 적습니다. 또는 `call_rcu()` 같은 asynchronous primitive를 사용합니다.

6.        Since synchronize_rcu() can block, it cannot be called
        from any sort of irq context.  The same rule applies
        for synchronize_srcu(), synchronize_rcu_expedited(),
        synchronize_srcu_expedited(), synchronize_rcu_tasks(),
        synchronize_rcu_tasks_rude(), and synchronize_rcu_tasks_trace().

        The expedited forms of these primitives have the same semantics
        as the non-expedited forms, but expediting is more CPU intensive.
        Use of the expedited primitives should be restricted to rare
        configuration-change operations that would not normally be
        undertaken while a real-time workload is running.  Note that
        IPI-sensitive real-time workloads can use the rcupdate.rcu_normal
        kernel boot parameter to completely disable expedited grace
        periods, though this might have performance implications.

        In particular, if you find yourself invoking one of the expedited
        primitives repeatedly in a loop, please do everyone a favor:
        Restructure your code so that it batches the updates, allowing
        a single non-expedited primitive to cover the entire batch.
        This will very likely be faster than the loop containing the
        expedited primitive, and will be much much easier on the rest
        of the system, especially to real-time workloads running on the
        rest of the system.  Alternatively, instead use asynchronous
        primitives such as call_rcu().

7. Updater와 reader의 RCU flavor 짝

v4.20 이후 한 kernel은 `PREEMPTION=n`이면 RCU-sched, `PREEMPTION=y`이면 RCU-preempt라는 하나의 기본 RCU flavor를 구현합니다. Updater가 `call_rcu()` 또는 `synchronize_rcu()`를 쓰면 reader는 `rcu_read_lock()` pair, BH disable/enable pair, 또는 preemption disable/enable pair를 사용할 수 있습니다.

Updater가 `synchronize_srcu()`나 `call_srcu()`를 쓰면 reader는 같은 `srcu_struct`를 전달한 `srcu_read_lock()`과 `srcu_read_unlock()`을 써야 합니다. Expedited wait도 일반 counterpart와 같은 pairing rule을 가집니다.

RCU Tasks에서는 `synchronize_rcu_tasks()`/`call_rcu_tasks()`에 대응하는 reader가 voluntary context switch, 즉 blocking을 하지 않아야 합니다. `call_rcu_tasks_trace()`/`synchronize_rcu_tasks_trace()`에는 `rcu_read_lock_trace()`/`rcu_read_unlock_trace()`가 필요합니다. `synchronize_rcu_tasks_rude()` reader는 `preempt_disable()`처럼 preemption을 disable해야 합니다.

Pair를 혼동하면 kernel이 깨지고 보안 취약점까지 생길 수 있으므로 비명확한 조합에는 주석이 필수입니다. XDP는 NAPI softirq의 하나의 `local_bh_disable()` 구간 안에서 BPF program을 호출하므로 기본 RCU updater와 안전하게 짝을 이룰 수 있는 사례입니다.

7.        As of v4.20, a given kernel implements only one RCU flavor, which
        is RCU-sched for PREEMPTION=n and RCU-preempt for PREEMPTION=y.
        If the updater uses call_rcu() or synchronize_rcu(), then
        the corresponding readers may use:  (1) rcu_read_lock() and
        rcu_read_unlock(), (2) any pair of primitives that disables
        and re-enables softirq, for example, rcu_read_lock_bh() and
        rcu_read_unlock_bh(), or (3) any pair of primitives that disables
        and re-enables preemption, for example, rcu_read_lock_sched() and
        rcu_read_unlock_sched().  If the updater uses synchronize_srcu()
        or call_srcu(), then the corresponding readers must use
        srcu_read_lock() and srcu_read_unlock(), and with the same
        srcu_struct.  The rules for the expedited RCU grace-period-wait
        primitives are the same as for their non-expedited counterparts.

        Similarly, it is necessary to correctly use the RCU Tasks flavors:

        a.        If the updater uses synchronize_rcu_tasks() or
                call_rcu_tasks(), then the readers must refrain from
                executing voluntary context switches, that is, from
                blocking.

        b.        If the updater uses call_rcu_tasks_trace()
                or synchronize_rcu_tasks_trace(), then the
                corresponding readers must use rcu_read_lock_trace()
                and rcu_read_unlock_trace().

        c.        If an updater uses synchronize_rcu_tasks_rude(),
                then the corresponding readers must use anything that
                disables preemption, for example, preempt_disable()
                and preempt_enable().

        Mixing things up will result in confusion and broken kernels, and
        has even resulted in an exploitable security issue.  Therefore,
        when using non-obvious pairs of primitives, commenting is
        of course a must.  One example of non-obvious pairing is
        the XDP feature in networking, which calls BPF programs from
        network-driver NAPI (softirq) context.        BPF relies heavily on RCU
        protection for its data structures, but because the BPF program
        invocation happens entirely within a single local_bh_disable()
        section in a NAPI poll cycle, this usage is safe.  The reason
        that this usage is safe is that readers can use anything that
        disables BH when updaters use call_rcu() or synchronize_rcu().

8. Reclamation API와 update backpressure

`synchronize_rcu()`는 `call_rcu()`보다 느리지만 code가 단순합니다. Update 성능이 결정적이거나 updater가 block할 수 없거나 latency가 userspace에 보이는 경우가 아니라면 `synchronize_rcu()`를 우선합니다. `kfree_rcu()`와 `kvfree_rcu()`는 multi-millisecond wait 없이 fire-and-forget free를 제공해 더 단순할 수 있습니다.

`synchronize_rcu()`는 grace period가 지연되면 update도 함께 늦어지는 자동 backpressure가 있습니다. `call_rcu()`는 명시적으로 update rate를 제한하지 않으면 RT latency 증가나 OOM을 일으킬 수 있습니다.

Backpressure 방법은 네 가지입니다. 첫째, grace period를 기다리는 element까지 포함한 수를 세고 상한을 넘으면 update를 stall합니다. Update-side mutex로 기다릴 수 있지만 spinlock waiter가 grace period 종료를 막을 수 있으므로 spinlock은 쓰면 안 됩니다. Allocator wrapper가 대기 memory가 많을 때 OOM을 흉내 내는 방법도 있습니다.

둘째, update 빈도 자체를 제한합니다. 시간당 한 번처럼 매우 드물면 별도 제한이 필요 없습니다. 셋째, superuser 같은 trusted user만 update할 수 있다면 자동 제한을 생략할 수 있습니다. 넷째, 주기적으로 `rcu_barrier()`를 호출해 grace period당 update 수를 제한합니다.

`call_srcu()`, `call_rcu_tasks()`, `call_rcu_tasks_trace()`에도 각각 `srcu_barrier()`, `rcu_barrier_tasks()`, `rcu_barrier_tasks_trace()`로 같은 주의를 적용합니다. Per-CPU callback 과다를 완화하는 장치가 있어도 많은 CPU의 callback을 한 CPU로 offload하거나 free memory가 적으면 의도적인 사용자가 memory를 고갈시킬 수 있습니다.

8.        Although synchronize_rcu() is slower than is call_rcu(),
        it usually results in simpler code.  So, unless update
        performance is critically important, the updaters cannot block,
        or the latency of synchronize_rcu() is visible from userspace,
        synchronize_rcu() should be used in preference to call_rcu().
        Furthermore, kfree_rcu() and kvfree_rcu() usually result
        in even simpler code than does synchronize_rcu() without
        synchronize_rcu()'s multi-millisecond latency.        So please take
        advantage of kfree_rcu()'s and kvfree_rcu()'s "fire and forget"
        memory-freeing capabilities where it applies.

        An especially important property of the synchronize_rcu()
        primitive is that it automatically self-limits: if grace periods
        are delayed for whatever reason, then the synchronize_rcu()
        primitive will correspondingly delay updates.  In contrast,
        code using call_rcu() should explicitly limit update rate in
        cases where grace periods are delayed, as failing to do so can
        result in excessive realtime latencies or even OOM conditions.

        Ways of gaining this self-limiting property when using call_rcu(),
        kfree_rcu(), or kvfree_rcu() include:

        a.        Keeping a count of the number of data-structure elements
                used by the RCU-protected data structure, including
                those waiting for a grace period to elapse.  Enforce a
                limit on this number, stalling updates as needed to allow
                previously deferred frees to complete.        Alternatively,
                limit only the number awaiting deferred free rather than
                the total number of elements.

                One way to stall the updates is to acquire the update-side
                mutex.        (Don't try this with a spinlock -- other CPUs
                spinning on the lock could prevent the grace period
                from ever ending.)  Another way to stall the updates
                is for the updates to use a wrapper function around
                the memory allocator, so that this wrapper function
                simulates OOM when there is too much memory awaiting an
                RCU grace period.  There are of course many other
                variations on this theme.

        b.        Limiting update rate.  For example, if updates occur only
                once per hour, then no explicit rate limiting is
                required, unless your system is already badly broken.
                Older versions of the dcache subsystem take this approach,
                guarding updates with a global lock, limiting their rate.

        c.        Trusted update -- if updates can only be done manually by
                superuser or some other trusted user, then it might not
                be necessary to automatically limit them.  The theory
                here is that superuser already has lots of ways to crash
                the machine.

        d.        Periodically invoke rcu_barrier(), permitting a limited
                number of updates per grace period.

        The same cautions apply to call_srcu(), call_rcu_tasks(), and
        call_rcu_tasks_trace().  This is why there is an srcu_barrier(),
        rcu_barrier_tasks(), and rcu_barrier_tasks_trace(), respectively.

        Note that although these primitives do take action to avoid
        memory exhaustion when any given CPU has too many callbacks,
        a determined user or administrator can still exhaust memory.
        This is especially the case if a system with a large number of
        CPUs has been configured to offload all of its RCU callbacks onto
        a single CPU, or if the system has relatively little free memory.

9. RCU traversal primitive의 보호 context

`rcu_dereference()`, `list_for_each_entry_rcu()`, `list_for_each_safe_rcu()`를 포함한 모든 RCU traversal primitive는 RCU read-side critical section 안이거나 적절한 update-side lock 아래 있어야 합니다. `rcu_read_lock_bh()`를 썼다면 lockdep을 위해 `rcu_dereference_bh()`처럼 matching dereference variant를 사용합니다.

Update-side lock 아래에서 RCU traversal을 허용하면 reader와 updater가 공통 code를 공유해 code bloat를 줄일 수 있으며 `lockdep.rst`는 이 조건을 표현하는 primitive를 설명합니다.

예외는 reader가 접근하는 동안 linked structure에 element를 추가하기만 하고 절대 제거하지 않는 경우입니다. 이때는 `rcu_dereference()` 대신 `READ_ONCE()`를 쓸 수 있고 read-side marker도 생략할 수 있습니다.

9.        All RCU list-traversal primitives, which include
        rcu_dereference(), list_for_each_entry_rcu(), and
        list_for_each_safe_rcu(), must be either within an RCU read-side
        critical section or must be protected by appropriate update-side
        locks.        RCU read-side critical sections are delimited by
        rcu_read_lock() and rcu_read_unlock(), or by similar primitives
        such as rcu_read_lock_bh() and rcu_read_unlock_bh(), in which
        case the matching rcu_dereference() primitive must be used in
        order to keep lockdep happy, in this case, rcu_dereference_bh().

        The reason that it is permissible to use RCU list-traversal
        primitives when the update-side lock is held is that doing so
        can be quite helpful in reducing code bloat when common code is
        shared between readers and updaters.  Additional primitives
        are provided for this case, as discussed in lockdep.rst.

        One exception to this rule is when data is only ever added to
        the linked data structure, and is never removed during any
        time that readers might be accessing that structure.  In such
        cases, READ_ONCE() may be used in place of rcu_dereference()
        and the read-side markers (rcu_read_lock() and rcu_read_unlock(),
        for example) may be omitted.

10. Reader는 _rcu list macro를 사용한다

RCU read-side critical section 안에서 적절한 update-side lock을 보유하지 않았다면 list macro의 `_rcu()` variant를 반드시 사용해야 합니다. 일반 variant를 쓰면 Alpha에서 깨지고 공격적인 compiler가 잘못된 code를 만들 수 있으며, code를 읽는 사람도 보호 방식을 이해하기 어렵습니다.

10.        Conversely, if you are in an RCU read-side critical section,
        and you don't hold the appropriate update-side lock, you *must*
        use the "_rcu()" variants of the list macros.  Failing to do so
        will break Alpha, cause aggressive compilers to generate bad code,
        and confuse people trying to understand your code.

11. Callback이 획득하는 lock과 softirq

RCU callback이 획득하는 lock은 다른 모든 획득 지점에서도 `spin_lock_bh()` 같은 방식으로 softirq를 disable한 채 획득해야 합니다. 그렇지 않으면 해당 critical section을 interrupt한 RCU softirq handler가 callback에서 같은 lock을 기다리며 deadlock됩니다.

11.        Any lock acquired by an RCU callback must be acquired elsewhere
        with softirq disabled, e.g., via spin_lock_bh().  Failing to
        disable softirq on a given acquisition of that lock will result
        in deadlock as soon as the RCU softirq handler happens to run
        your RCU callback while interrupting that acquisition's critical
        section.

12. Callback의 CPU, 순서와 병렬 실행을 가정하지 않는다

RCU callback은 병렬 실행될 수 있습니다. 단순 `kfree()` wrapper라면 allocator locking이 처리하지만 shared data structure를 조작하면 필요한 lock이나 다른 synchronization을 직접 사용해야 합니다.

Callback이 해당 `call_rcu()` 계열을 호출한 CPU에서 실행된다고 가정하면 안 됩니다. Pending callback이 있는 CPU가 offline되면 surviving CPU에서 실행됩니다. `rcu_nocbs=`로 지정한 CPU의 callback은 RT workload를 위해 다른 CPU에서 항상 실행될 수도 있습니다.

같은 CPU에서 특정 순서로 queue한 callback이 그 순서대로, 또는 직렬로 실행된다고 가정해서도 안 됩니다. CPU를 callback offload와 de-offload 사이에서 전환하는 동안 softirq handler와 `rcuo` kthread가 같은 CPU의 callback을 동시에, 순서 밖으로 실행할 수 있습니다.

12.        RCU callbacks can be and are executed in parallel.  In many cases,
        the callback code simply wrappers around kfree(), so that this
        is not an issue (or, more accurately, to the extent that it is
        an issue, the memory-allocator locking handles it).  However,
        if the callbacks do manipulate a shared data structure, they
        must use whatever locking or other synchronization is required
        to safely access and/or modify that data structure.

        Do not assume that RCU callbacks will be executed on the same
        CPU that executed the corresponding call_rcu(), call_srcu(),
        call_rcu_tasks(), or call_rcu_tasks_trace().  For example, if
        a given CPU goes offline while having an RCU callback pending,
        then that RCU callback will execute on some surviving CPU.
        (If this was not the case, a self-spawning RCU callback would
        prevent the victim CPU from ever going offline.)  Furthermore,
        CPUs designated by rcu_nocbs= might well *always* have their
        RCU callbacks executed on some other CPUs, in fact, for some
        real-time workloads, this is the whole point of using the
        rcu_nocbs= kernel boot parameter.

        In addition, do not assume that callbacks queued in a given order
        will be invoked in that order, even if they all are queued on the
        same CPU.  Furthermore, do not assume that same-CPU callbacks will
        be invoked serially.  For example, in recent kernels, CPUs can be
        switched between offloaded and de-offloaded callback invocation,
        and while a given CPU is undergoing such a switch, its callbacks
        might be concurrently invoked by that CPU's softirq handler and
        that CPU's rcuo kthread.  At such times, that CPU's callbacks
        might be executed both concurrently and out of order.

13. SRCU의 sleep, domain과 비용

대부분의 RCU와 달리 `srcu_read_lock()`/`srcu_read_unlock()`으로 구분한 SRCU read-side critical section에서는 block할 수 있습니다. `guard(srcu)()`와 `scoped_guard(srcu)`도 사용할 수 있습니다. Sleep이 필요 없다면 거의 항상 더 빠르고 쉬운 기본 RCU를 사용해야 합니다.

SRCU는 build time의 `DEFINE_SRCU()`/`DEFINE_STATIC_SRCU()` 또는 runtime의 `init_srcu_struct()`로 명시적 초기화하고 `cleanup_srcu_struct()`로 정리해야 합니다. `struct srcu_struct`가 domain 범위를 정의하며 read lock/unlock, synchronize, expedited synchronize, `call_srcu()`에 같은 object를 전달합니다.

`synchronize_srcu()`는 같은 `srcu_struct`가 관리하는 기존 reader만 기다립니다. 한 subsystem의 sleeping reader가 다른 SRCU subsystem의 update를 늦추지 않으므로, RCU reader가 sleep할 수 있다고 가정했을 때보다 system-wide OOM 위험이 작습니다.

대가는 같은 `srcu_struct`를 lock과 unlock에 정확히 전달해야 하고 grace-period detection 비용이 해당 domain update끼리만 amortize된다는 점입니다. 따라서 매우 read-intensive하거나 read-side deadlock immunity 또는 낮은 RT latency가 필요한 경우에만 `rw_semaphore`보다 SRCU를 우선합니다. 가벼운 reader에는 `percpu_rw_semaphore`도 고려합니다.

`synchronize_srcu_expedited()`는 다른 CPU에 IPI를 보내지 않아 `synchronize_rcu_expedited()`보다 RT workload에 부담이 적습니다. RCU Tasks Trace reader도 sleep할 수 있지만 전문 flavor이므로 현재 사용자와 상의해야 하며 대부분은 SRCU가 낫습니다. `guard(rcu_tasks_trace)()` 계열도 제공됩니다.

SRCU에서도 publication은 `rcu_assign_pointer()`를 사용하지만 dereference는 lockdep 경고를 피하도록 `srcu_dereference()`를 사용합니다.

13.        Unlike most flavors of RCU, it *is* permissible to block in an
        SRCU read-side critical section (demarked by srcu_read_lock()
        and srcu_read_unlock()), hence the "SRCU": "sleepable RCU".
        As with RCU, guard(srcu)() and scoped_guard(srcu) forms are
        available, and often provide greater ease of use.  Please note
        that if you don't need to sleep in read-side critical sections,
        you should be using RCU rather than SRCU, because RCU is almost
        always faster and easier to use than is SRCU.

        Also unlike other forms of RCU, explicit initialization and
        cleanup is required either at build time via DEFINE_SRCU()
        or DEFINE_STATIC_SRCU() or at runtime via init_srcu_struct()
        and cleanup_srcu_struct().  These last two are passed a
        "struct srcu_struct" that defines the scope of a given
        SRCU domain.  Once initialized, the srcu_struct is passed
        to srcu_read_lock(), srcu_read_unlock() synchronize_srcu(),
        synchronize_srcu_expedited(), and call_srcu().        A given
        synchronize_srcu() waits only for SRCU read-side critical
        sections governed by srcu_read_lock() and srcu_read_unlock()
        calls that have been passed the same srcu_struct.  This property
        is what makes sleeping read-side critical sections tolerable --
        a given subsystem delays only its own updates, not those of other
        subsystems using SRCU.        Therefore, SRCU is less prone to OOM the
        system than RCU would be if RCU's read-side critical sections
        were permitted to sleep.

        The ability to sleep in read-side critical sections does not
        come for free.        First, corresponding srcu_read_lock() and
        srcu_read_unlock() calls must be passed the same srcu_struct.
        Second, grace-period-detection overhead is amortized only
        over those updates sharing a given srcu_struct, rather than
        being globally amortized as they are for other forms of RCU.
        Therefore, SRCU should be used in preference to rw_semaphore
        only in extremely read-intensive situations, or in situations
        requiring SRCU's read-side deadlock immunity or low read-side
        realtime latency.  You should also consider percpu_rw_semaphore
        when you need lightweight readers.

        SRCU's expedited primitive (synchronize_srcu_expedited())
        never sends IPIs to other CPUs, so it is easier on
        real-time workloads than is synchronize_rcu_expedited().

        It is also permissible to sleep in RCU Tasks Trace read-side
        critical section, which are delimited by rcu_read_lock_trace()
        and rcu_read_unlock_trace().  However, this is a specialized
        flavor of RCU, and you should not use it without first checking
        with its current users.  In most cases, you should instead
        use SRCU.  As with RCU and SRCU, guard(rcu_tasks_trace)() and
        scoped_guard(rcu_tasks_trace) are available, and often provide
        greater ease of use.

        Note that rcu_assign_pointer() relates to SRCU just as it does to
        other forms of RCU, but instead of rcu_dereference() you should
        use srcu_dereference() in order to avoid lockdep splats.

14. Reader 경로를 먼저 제거한 뒤 grace period를 기다린다

`call_rcu()`, `synchronize_rcu()` 계열의 목적은 기존 reader가 모두 끝난 뒤 destructive operation을 수행하는 것입니다. 따라서 파괴될 object로 reader가 들어가는 경로를 먼저 제거하고, 그 다음에 grace-period primitive를 호출해야 합니다.

이 primitive는 호출 전에 이미 존재한 reader만 기다립니다. 이후 새 reader가 안전하게 실행되도록 보장하는 책임은 caller에게 있습니다.

14.        The whole point of call_rcu(), synchronize_rcu(), and friends
        is to wait until all pre-existing readers have finished before
        carrying out some otherwise-destructive operation.  It is
        therefore critically important to *first* remove any path
        that readers can follow that could be affected by the
        destructive operation, and *only then* invoke call_rcu(),
        synchronize_rcu(), or friends.

        Because these primitives only wait for pre-existing readers, it
        is the caller's responsibility to guarantee that any subsequent
        readers will execute safely.

15. Read-side marker는 memory barrier가 아니다

여러 RCU read-side primitive에는 memory barrier가 반드시 들어 있지 않습니다. CPU와 compiler가 code를 critical section 안팎으로 reorder할 수 있다고 가정해야 하며, 이를 처리하는 책임은 RCU update-side primitive에 있습니다.

SRCU reader는 `srcu_read_unlock()` 직후 `smp_mb__after_srcu_read_unlock()`을 호출해 full barrier를 얻을 수 있습니다.

15.        The various RCU read-side primitives do *not* necessarily contain
        memory barriers.  You should therefore plan for the CPU
        and the compiler to freely reorder code into and out of RCU
        read-side critical sections.  It is the responsibility of the
        RCU update-side primitives to deal with this.

        For SRCU readers, you can use smp_mb__after_srcu_read_unlock()
        immediately after an srcu_read_unlock() to get a full barrier.

16. Lockdep, debug object, strict GP와 sparse 검증

`CONFIG_PROVE_LOCKING`, `CONFIG_DEBUG_OBJECTS_RCU_HEAD`, `CONFIG_RCU_STRICT_GRACE_PERIOD`와 `__rcu` sparse check로 RCU code를 검증해야 합니다.

`CONFIG_PROVE_LOCKING`은 RCU-protected data access가 적절한 read-side section, 올바른 lock 조합 또는 명시된 조건 아래 수행되는지 검사합니다. `CONFIG_DEBUG_OBJECTS_RCU_HEAD`는 같은 object를 이전 grace period가 끝나기 전에 `call_rcu()` 계열에 다시 전달하는 오류를 찾습니다.

`CONFIG_RCU_STRICT_GRACE_PERIOD`를 KASAN과 함께 쓰면 read-side section 밖으로 유출된 pointer를 찾을 수 있습니다. 성능과 scalability 비용이 매우 커 four-CPU system으로 제한됩니다.

Pointer에 `__rcu` annotation을 붙이면 sparse가 적절한 `rcu_dereference()` variant 없이 접근할 때 경고합니다. 이런 도구는 눈으로 찾기 매우 어려운 문제를 검출합니다.

16.        Use CONFIG_PROVE_LOCKING, CONFIG_DEBUG_OBJECTS_RCU_HEAD, and the
        __rcu sparse checks to validate your RCU code.        These can help
        find problems as follows:

        CONFIG_PROVE_LOCKING:
                check that accesses to RCU-protected data structures
                are carried out under the proper RCU read-side critical
                section, while holding the right combination of locks,
                or whatever other conditions are appropriate.

        CONFIG_DEBUG_OBJECTS_RCU_HEAD:
                check that you don't pass the same object to call_rcu()
                (or friends) before an RCU grace period has elapsed
                since the last time that you passed that same object to
                call_rcu() (or friends).

        CONFIG_RCU_STRICT_GRACE_PERIOD:
                combine with KASAN to check for pointers leaked out
                of RCU read-side critical sections.  This Kconfig
                option is tough on both performance and scalability,
                and so is limited to four-CPU systems.

        __rcu sparse checks:
                tag the pointer to the RCU-protected data structure
                with __rcu, and sparse will warn you if you access that
                pointer without the services of one of the variants
                of rcu_dereference().

        These debugging aids can help you find problems that are
        otherwise extremely difficult to spot.

17. Module unload 전 callback barrier

Module 안에 정의된 callback을 `call_rcu()`, `call_srcu()`, `call_rcu_tasks()`, `call_rcu_tasks_trace()`에 넘겼다면 module unload 전에 pending callback이 모두 실행될 때까지 기다려야 합니다. Grace period 하나를 기다리는 것만으로는 부족합니다. `synchronize_rcu()`는 다른 CPU 또는 최근 offline/online된 현재 CPU에 등록된 callback까지 기다린다고 보장하지 않습니다.

Callback 종류에 맞는 barrier를 사용합니다. `call_rcu()`에는 `rcu_barrier()`, `call_srcu()`에는 `srcu_barrier()`, `call_rcu_tasks()`에는 `rcu_barrier_tasks()`, `call_rcu_tasks_trace()`에는 `rcu_barrier_tasks_trace()`가 대응합니다.

반대로 barrier는 grace period를 기다린다고 보장하지 않습니다. Queue된 callback이 없으면 `rcu_barrier()`는 즉시 반환할 수 있습니다. Grace period와 기존 callback 완료가 둘 다 필요하면 flavor에 맞는 synchronize 함수와 barrier를 모두 호출해야 합니다.

두 함수를 동시에 실행해야 한다면 workqueue 같은 mechanism을 사용할 수 있습니다. 자세한 내용은 `rcubarrier.rst`를 참조합니다.

17.        If you pass a callback function defined within a module
        to one of call_rcu(), call_srcu(), call_rcu_tasks(), or
        call_rcu_tasks_trace(), then it is necessary to wait for all
        pending callbacks to be invoked before unloading that module.
        Note that it is absolutely *not* sufficient to wait for a grace
        period!  For example, synchronize_rcu() implementation is *not*
        guaranteed to wait for callbacks registered on other CPUs via
        call_rcu().  Or even on the current CPU if that CPU recently
        went offline and came back online.

        You instead need to use one of the barrier functions:

        -        call_rcu() -> rcu_barrier()
        -        call_srcu() -> srcu_barrier()
        -        call_rcu_tasks() -> rcu_barrier_tasks()
        -        call_rcu_tasks_trace() -> rcu_barrier_tasks_trace()

        However, these barrier functions are absolutely *not* guaranteed
        to wait for a grace period.  For example, if there are no
        call_rcu() callbacks queued anywhere in the system, rcu_barrier()
        can and will return immediately.

        So if you need to wait for both a grace period and for all
        pre-existing callbacks, you will need to invoke both functions,
        with the pair depending on the flavor of RCU:

        -        Either synchronize_rcu() or synchronize_rcu_expedited(),
                together with rcu_barrier()
        -        Either synchronize_srcu() or synchronize_srcu_expedited(),
                together with and srcu_barrier()
        -        synchronize_rcu_tasks() and rcu_barrier_tasks()
        -        synchronize_tasks_trace() and rcu_barrier_tasks_trace()

        If necessary, you can use something like workqueues to execute
        the requisite pair of functions concurrently.

        See rcubarrier.rst for more information.