RCU란 무엇인가: Read, Copy, Update

학습 경로와 removal/reclamation 모델

RCU를 처음 배울 때는 LWN의 `What is RCU?` 시리즈가 좋은 출발점이다. 문서는 2007년의 근본 개념·사용법·API부터 2010, 2014, 2019, 2024 API 개정판과 큰 API 표, Linux Foundation의 두 영상 강의까지 링크한다.

RCU는 Linux 2.5 개발 과정에서 들어온 읽기 위주 상황에 최적화된 동기화 방식이다. 원리는 단순하지만 기존 lock 중심 코드와 다른 관점이 필요하다. 개념부터 배우는 독자는 1장, API로 실험하려는 독자는 2장, 예제로 배우려는 독자는 3~4장, 구현을 이해하려는 독자는 5장, 비유가 편한 독자는 6~7장부터 시작할 수 있다. 8장은 API 색인, 9장은 퀴즈 해설이다.

RCU 갱신은 removal과 reclamation의 두 단계로 나뉜다. Removal은 자료 구조 안에서 기존 항목을 가리키는 참조를 없애거나 새 버전으로 바꾼다. 정렬된 단일 포인터 쓰기가 원자적이라는 현대 CPU의 성질 덕분에 독자는 부분적으로 갱신된 포인터가 아니라 이전 또는 새 버전을 본다. 이 단계는 독자와 동시에 실행될 수 있다.

Reclamation은 제거된 항목의 메모리를 실제로 회수한다. 아직 해당 항목을 참조하는 독자가 있으면 해제가 use-after-free를 만들므로 removal 당시 활동 중이던 모든 독자가 끝난 뒤에만 시작한다. Removal 뒤에 시작한 독자는 이미 제거된 항목에 새 참조를 얻을 수 없으므로 기다릴 대상이 아니다.

일반적인 순서는 포인터 제거, 기존 RCU read-side critical section의 종료 대기, 안전한 `kfree()`다. 두 번째 단계인 grace period 대기가 deferred destruction의 핵심이다. 독자는 updater가 메모리를 갑자기 해제하지 못하도록 무거운 lock을 잡을 필요가 없고, 많은 경우 atomic operation·memory barrier·cache-line 통신도 피할 수 있다.

Removal과 reclamation은 같은 thread가 수행할 수도 있고 dcache처럼 다른 thread가 맡을 수도 있다. Reader와 updater는 직접 통신하지 않아도 되지만 RCU infrastructure가 reader와 reclaimer 사이의 저비용 암묵적 통신을 제공한다.

.. _whatisrcu_doc:

What is RCU?  --  "Read, Copy, Update"
======================================

Please note that the "What is RCU?" LWN series is an excellent place
to start learning about RCU:

| 1.        What is RCU, Fundamentally?  https://lwn.net/Articles/262464/
| 2.        What is RCU? Part 2: Usage   https://lwn.net/Articles/263130/
| 3.        RCU part 3: the RCU API      https://lwn.net/Articles/264090/
| 4.        The RCU API, 2010 Edition    https://lwn.net/Articles/418853/
|         2010 Big API Table           https://lwn.net/Articles/419086/
| 5.        The RCU API, 2014 Edition    https://lwn.net/Articles/609904/
|        2014 Big API Table           https://lwn.net/Articles/609973/
| 6.        The RCU API, 2019 Edition    https://lwn.net/Articles/777036/
|        2019 Big API Table           https://lwn.net/Articles/777165/
| 7.        The RCU API, 2024 Edition    https://lwn.net/Articles/988638/
|       2024 Background Information  https://lwn.net/Articles/988641/
|        2024 Big API Table           https://lwn.net/Articles/988666/

For those preferring video:

| 1.        Unraveling RCU Mysteries: Fundamentals          https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries
| 2.        Unraveling RCU Mysteries: Additional Use Cases  https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries-additional-use-cases


What is RCU?

RCU is a synchronization mechanism that was added to the Linux kernel
during the 2.5 development effort that is optimized for read-mostly
situations.  Although RCU is actually quite simple, making effective use
of it requires you to think differently about your code.  Another part
of the problem is the mistaken assumption that there is "one true way" to
describe and to use RCU.  Instead, the experience has been that different
people must take different paths to arrive at an understanding of RCU,
depending on their experiences and use cases.  This document provides
several different paths, as follows:

:ref:`1.        RCU OVERVIEW <1_whatisRCU>`

:ref:`2.        WHAT IS RCU'S CORE API? <2_whatisRCU>`

:ref:`3.        WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>`

:ref:`4.        WHAT IF MY UPDATING THREAD CANNOT BLOCK? <4_whatisRCU>`

:ref:`5.        WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>`

:ref:`6.        ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>`

:ref:`7.        ANALOGY WITH REFERENCE COUNTING <7_whatisRCU>`

:ref:`8.        FULL LIST OF RCU APIs <8_whatisRCU>`

:ref:`9.        ANSWERS TO QUICK QUIZZES <9_whatisRCU>`

People who prefer starting with a conceptual overview should focus on
Section 1, though most readers will profit by reading this section at
some point.  People who prefer to start with an API that they can then
experiment with should focus on Section 2.  People who prefer to start
with example uses should focus on Sections 3 and 4.  People who need to
understand the RCU implementation should focus on Section 5, then dive
into the kernel source code.  People who reason best by analogy should
focus on Section 6 and 7.  Section 8 serves as an index to the docbook
API documentation, and Section 9 is the traditional answer key.

So, start with the section that makes the most sense to you and your
preferred method of learning.  If you need to know everything about
everything, feel free to read the whole thing -- but if you are really
that type of person, you have perused the source code and will therefore
never need this document anyway.  ;-)

.. _1_whatisRCU:

1.  RCU OVERVIEW
----------------

The basic idea behind RCU is to split updates into "removal" and
"reclamation" phases.  The removal phase removes references to data items
within a data structure (possibly by replacing them with references to
new versions of these data items), and can run concurrently with readers.
The reason that it is safe to run the removal phase concurrently with
readers is the semantics of modern CPUs guarantee that readers will see
either the old or the new version of the data structure rather than a
partially updated reference.  The reclamation phase does the work of reclaiming
(e.g., freeing) the data items removed from the data structure during the
removal phase.  Because reclaiming data items can disrupt any readers
concurrently referencing those data items, the reclamation phase must
not start until readers no longer hold references to those data items.

Splitting the update into removal and reclamation phases permits the
updater to perform the removal phase immediately, and to defer the
reclamation phase until all readers active during the removal phase have
completed, either by blocking until they finish or by registering a
callback that is invoked after they finish.  Only readers that are active
during the removal phase need be considered, because any reader starting
after the removal phase will be unable to gain a reference to the removed
data items, and therefore cannot be disrupted by the reclamation phase.

So the typical RCU update sequence goes something like the following:

a.        Remove pointers to a data structure, so that subsequent
        readers cannot gain a reference to it.

b.        Wait for all previous readers to complete their RCU read-side
        critical sections.

c.        At this point, there cannot be any readers who hold references
        to the data structure, so it now may safely be reclaimed
        (e.g., kfree()d).

Step (b) above is the key idea underlying RCU's deferred destruction.
The ability to wait until all readers are done allows RCU readers to
use much lighter-weight synchronization, in some cases, absolutely no
synchronization at all.  In contrast, in more conventional lock-based
schemes, readers must use heavy-weight synchronization in order to
prevent an updater from deleting the data structure out from under them.
This is because lock-based updaters typically update data items in place,
and must therefore exclude readers.  In contrast, RCU-based updaters
typically take advantage of the fact that writes to single aligned
pointers are atomic on modern CPUs, allowing atomic insertion, removal,
and replacement of data items in a linked structure without disrupting
readers.  Concurrent RCU readers can then continue accessing the old
versions, and can dispense with the atomic operations, memory barriers,
and communications cache misses that are so expensive on present-day
SMP computer systems, even in absence of lock contention.

In the three-step procedure shown above, the updater is performing both
the removal and the reclamation step, but it is often helpful for an
entirely different thread to do the reclamation, as is in fact the case
in the Linux kernel's directory-entry cache (dcache).  Even if the same
thread performs both the update step (step (a) above) and the reclamation
step (step (c) above), it is often helpful to think of them separately.
For example, RCU readers and updaters need not communicate at all,
but RCU provides implicit low-overhead communication between readers
and reclaimers, namely, in step (b) above.

So how the heck can a reclaimer tell when a reader is done, given
that readers are not doing any sort of synchronization operations???
Read on to learn about how RCU's API makes this easy.

핵심 API와 읽기 임계 구역

핵심 API는 `rcu_read_lock()`, `rcu_read_unlock()`, `synchronize_rcu()` 또는 `call_rcu()`, `rcu_assign_pointer()`, `rcu_dereference()` 다섯 종류다. 나머지 API는 개념적으로 이들로 표현할 수 있으며 실제 구현은 흔히 동기 API인 `synchronize_rcu()`를 callback 기반 `call_rcu()`로 구성한다.

`rcu_read_lock()`은 reader가 RCU read-side critical section에 들어간다는 시간적 표지다. 이 구간에서 접근한 RCU 보호 객체는 구간이 끝날 때까지 회수되지 않는다. 더 오래 보관하려면 별도 reference count를 얻어야 한다.

일반 RCU 읽기 구간에서 block하는 것은 불법이지만 `CONFIG_PREEMPT_RCU`에서는 선점될 수 있다. Bottom half, preemption, interrupt를 끄는 구간과 spinlock 임계 구역도 RCU read-side critical section으로 취급된다. `CONFIG_PREEMPT_RT=y`에서 spinlock이 선점을 직접 끄지 않더라도 이 규칙은 유지된다. 반면 sleeplock은 RCU 읽기 구간을 만들지 않는다.

`rcu_read_unlock()`은 읽기 구간의 종료를 알린다. Bottom half, preemption, interrupt를 다시 켜거나 spinlock을 놓는 것도 해당 RCU 읽기 구간을 끝낸다. 읽기 구간은 중첩되거나 서로 겹칠 수 있으며, 가장 바깥 구간이 끝날 때 그 실행 문맥의 보호가 사라진다.

.. _2_whatisRCU:

2.  WHAT IS RCU'S CORE API?
---------------------------

The core RCU API is quite small:

a.        rcu_read_lock()
b.        rcu_read_unlock()
c.        synchronize_rcu() / call_rcu()
d.        rcu_assign_pointer()
e.        rcu_dereference()

There are many other members of the RCU API, but the rest can be
expressed in terms of these five, though most implementations instead
express synchronize_rcu() in terms of the call_rcu() callback API.

The five core RCU APIs are described below, the other 18 will be enumerated
later.  See the kernel docbook documentation for more info, or look directly
at the function header comments.

rcu_read_lock()
^^^^^^^^^^^^^^^
        void rcu_read_lock(void);

        This temporal primitive is used by a reader to inform the
        reclaimer that the reader is entering an RCU read-side critical
        section.  It is illegal to block while in an RCU read-side
        critical section, though kernels built with CONFIG_PREEMPT_RCU
        can preempt RCU read-side critical sections.  Any RCU-protected
        data structure accessed during an RCU read-side critical section
        is guaranteed to remain unreclaimed for the full duration of that
        critical section.  Reference counts may be used in conjunction
        with RCU to maintain longer-term references to data structures.

        Note that anything that disables bottom halves, preemption,
        or interrupts also enters an RCU read-side critical section.
        Acquiring a spinlock also enters an RCU read-side critical
        sections, even for spinlocks that do not disable preemption,
        as is the case in kernels built with CONFIG_PREEMPT_RT=y.
        Sleeplocks do *not* enter RCU read-side critical sections.

rcu_read_unlock()
^^^^^^^^^^^^^^^^^
        void rcu_read_unlock(void);

        This temporal primitives is used by a reader to inform the
        reclaimer that the reader is exiting an RCU read-side critical
        section.  Anything that enables bottom halves, preemption,
        or interrupts also exits an RCU read-side critical section.
        Releasing a spinlock also exits an RCU read-side critical section.

        Note that RCU read-side critical sections may be nested and/or
        overlapping.

synchronize_rcu()와 call_rcu()

`synchronize_rcu()`는 updater 코드의 끝과 reclaimer 코드의 시작을 나눈다. 호출 시점에 이미 실행 중이던 모든 CPU의 RCU read-side critical section이 끝날 때까지 block한다. 호출 뒤에 새로 시작한 읽기 구간까지 반드시 기다리는 것은 아니다.

예제 시간선에서 CPU 0의 reader가 먼저 시작하고 CPU 1이 `synchronize_rcu()`에 들어간 뒤 CPU 2의 reader가 시작한다. CPU 0이 unlock하면 동기화 호출은 반환할 수 있고 CPU 2의 reader는 그 뒤에도 계속될 수 있다. Removal 뒤에 시작한 CPU 2는 제거된 객체를 새로 얻지 못하기 때문이다.

마지막 기존 reader가 끝나자마자 반드시 즉시 반환하는 것도 아니다. Scheduler 지연과 효율을 위한 request batching이 추가 지연을 만들 수 있다. RCU의 실용성은 이 GP 판정 비용을 작게 유지하고 많은 요청에 overhead를 나눠 갖는 데 달려 있다.

`call_rcu()`는 `synchronize_rcu()`의 비동기 callback 형태다. 기다리는 대신 함수와 `rcu_head`를 등록하고 기존 reader가 끝난 뒤 callback을 호출한다. Block할 수 없는 문맥이나 update latency가 중요한 곳에 유용하지만 동기 API보다 코드가 복잡하다.

`synchronize_rcu()`는 GP가 지연될 때 updater도 자연스럽게 느려져 update rate를 제한하는 장점이 있다. 이는 denial-of-service 상황에서 callback과 미회수 객체가 무한히 쌓이는 것을 막는 backpressure다. `call_rcu()` 사용 코드는 `checklist.rst`의 방법처럼 update rate를 별도로 제한해야 같은 복원력을 얻는다.

synchronize_rcu()
^^^^^^^^^^^^^^^^^
        void synchronize_rcu(void);

        This temporal primitive marks the end of updater code and the
        beginning of reclaimer code.  It does this by blocking until
        all pre-existing RCU read-side critical sections on all CPUs
        have completed.  Note that synchronize_rcu() will **not**
        necessarily wait for any subsequent RCU read-side critical
        sections to complete.  For example, consider the following
        sequence of events::

                 CPU 0                  CPU 1                 CPU 2
             ----------------- ------------------------- ---------------
         1.  rcu_read_lock()
         2.                    enters synchronize_rcu()
         3.                                               rcu_read_lock()
         4.  rcu_read_unlock()
         5.                     exits synchronize_rcu()
         6.                                              rcu_read_unlock()

        To reiterate, synchronize_rcu() waits only for ongoing RCU
        read-side critical sections to complete, not necessarily for
        any that begin after synchronize_rcu() is invoked.

        Of course, synchronize_rcu() does not necessarily return
        **immediately** after the last pre-existing RCU read-side critical
        section completes.  For one thing, there might well be scheduling
        delays.  For another thing, many RCU implementations process
        requests in batches in order to improve efficiencies, which can
        further delay synchronize_rcu().

        Since synchronize_rcu() is the API that must figure out when
        readers are done, its implementation is key to RCU.  For RCU
        to be useful in all but the most read-intensive situations,
        synchronize_rcu()'s overhead must also be quite small.

        The call_rcu() API is an asynchronous callback form of
        synchronize_rcu(), and is described in more detail in a later
        section.  Instead of blocking, it registers a function and
        argument which are invoked after all ongoing RCU read-side
        critical sections have completed.  This callback variant is
        particularly useful in situations where it is illegal to block
        or where update-side performance is critically important.

        However, the call_rcu() API should not be used lightly, as use
        of the synchronize_rcu() API generally results in simpler code.
        In addition, the synchronize_rcu() API has the nice property
        of automatically limiting update rate should grace periods
        be delayed.  This property results in system resilience in face
        of denial-of-service attacks.  Code using call_rcu() should limit
        update rate in order to gain this same sort of resilience.  See
        checklist.rst for some approaches to limiting the update rate.

포인터 게시와 역참조

`rcu_assign_pointer(p, v)`는 updater가 초기화한 객체를 RCU 보호 포인터에 게시하는 공간적 macro다. 필요한 compiler directive와 CPU memory barrier를 제공하며 store-release처럼 동작한다. 객체를 초기화하는 이전 load와 store가 포인터 게시보다 앞서 관찰되도록 보장한다.

이 macro는 어느 포인터가 RCU 보호 대상인지, 새 구조가 다른 CPU에 보이기 시작하는 정확한 지점이 어디인지 문서화한다. 실제 코드에서는 `list_add_rcu()` 같은 `_rcu` 목록 primitive 안에서 간접적으로 쓰이는 경우가 많다.

`rcu_dereference(p)`는 reader가 RCU 보호 포인터 값을 가져와 이후 안전하게 역참조할 수 있도록 하는 macro다. 이름과 달리 자체가 객체 필드를 역참조하지는 않는다. Alpha에는 memory barrier가 필요하고 다른 CPU에서는 volatile load로 줄어들지만, C compiler가 address dependency를 보존하지 않으므로 volatile cast와 `rcu_dereference.rst`의 코딩 규칙으로 dependency 파괴를 막는다.

한 필드만 읽으면 `rcu_dereference(head.next)->data`처럼 결합할 수 있지만 여러 필드를 읽을 때는 한 번 가져온 포인터를 지역 변수에 저장한다. 반복 호출은 보기 어렵고 update가 끼면 서로 다른 포인터를 돌려줄 수 있으며 Alpha에서 불필요한 비용도 만든다.

반환 포인터는 해당 RCU read-side critical section 안에서만 유효하다. Unlock 뒤 같은 포인터를 사용하거나 다음 read-side section으로 들고 가는 것은 lock 임계 구역 밖으로 보호 포인터를 유출하는 것과 같은 버그다. 장기 보관이 필요하면 구간 안에서 별도 reference count를 획득한다.

Updater lock을 이미 잡아 객체 수명을 보호한다면 `rcu_dereference_protected()`와 `lockdep_is_held()` 표현식을 사용할 수 있다. 이 형태는 lockdep 경고를 피하고 일반 `rcu_dereference()`가 금지해야 하는 compiler 최적화도 허용한다. 보호 조건이 거짓이면 lockdep splat이 나온다. Reader와 updater 양쪽에서 쓰는 `list_for_each_entry_rcu()`에도 추가 lockdep 조건을 줄 수 있다.

rcu_assign_pointer()
^^^^^^^^^^^^^^^^^^^^
        void rcu_assign_pointer(p, typeof(p) v);

        Yes, rcu_assign_pointer() **is** implemented as a macro, though
        it would be cool to be able to declare a function in this manner.
        (And there has been some discussion of adding overloaded functions
        to the C language, so who knows?)

        The updater uses this spatial macro to assign a new value to an
        RCU-protected pointer, in order to safely communicate the change
        in value from the updater to the reader.  This is a spatial (as
        opposed to temporal) macro.  It does not evaluate to an rvalue,
        but it does provide any compiler directives and memory-barrier
        instructions required for a given compile or CPU architecture.
        Its ordering properties are that of a store-release operation,
        that is, any prior loads and stores required to initialize the
        structure are ordered before the store that publishes the pointer
        to that structure.

        Perhaps just as important, rcu_assign_pointer() serves to document
        (1) which pointers are protected by RCU and (2) the point at which
        a given structure becomes accessible to other CPUs.  That said,
        rcu_assign_pointer() is most frequently used indirectly, via
        the _rcu list-manipulation primitives such as list_add_rcu().

rcu_dereference()
^^^^^^^^^^^^^^^^^
        typeof(p) rcu_dereference(p);

        Like rcu_assign_pointer(), rcu_dereference() must be implemented
        as a macro.

        The reader uses the spatial rcu_dereference() macro to fetch
        an RCU-protected pointer, which returns a value that may
        then be safely dereferenced.  Note that rcu_dereference()
        does not actually dereference the pointer, instead, it
        protects the pointer for later dereferencing.  It also
        executes any needed memory-barrier instructions for a given
        CPU architecture.  Currently, only Alpha needs memory barriers
        within rcu_dereference() -- on other CPUs, it compiles to a
        volatile load.        However, no mainstream C compilers respect
        address dependencies, so rcu_dereference() uses volatile casts,
        which, in combination with the coding guidelines listed in
        rcu_dereference.rst, prevent current compilers from breaking
        these dependencies.

        Common coding practice uses rcu_dereference() to copy an
        RCU-protected pointer to a local variable, then dereferences
        this local variable, for example as follows::

                p = rcu_dereference(head.next);
                return p->data;

        However, in this case, one could just as easily combine these
        into one statement::

                return rcu_dereference(head.next)->data;

        If you are going to be fetching multiple fields from the
        RCU-protected structure, using the local variable is of
        course preferred.  Repeated rcu_dereference() calls look
        ugly, do not guarantee that the same pointer will be returned
        if an update happened while in the critical section, and incur
        unnecessary overhead on Alpha CPUs.

        Note that the value returned by rcu_dereference() is valid
        only within the enclosing RCU read-side critical section [1]_.
        For example, the following is **not** legal::

                rcu_read_lock();
                p = rcu_dereference(head.next);
                rcu_read_unlock();
                x = p->address;        /* BUG!!! */
                rcu_read_lock();
                y = p->data;        /* BUG!!! */
                rcu_read_unlock();

        Holding a reference from one RCU read-side critical section
        to another is just as illegal as holding a reference from
        one lock-based critical section to another!  Similarly,
        using a reference outside of the critical section in which
        it was acquired is just as illegal as doing so with normal
        locking.

        As with rcu_assign_pointer(), an important function of
        rcu_dereference() is to document which pointers are protected by
        RCU, in particular, flagging a pointer that is subject to changing
        at any time, including immediately after the rcu_dereference().
        And, again like rcu_assign_pointer(), rcu_dereference() is
        typically used indirectly, via the _rcu list-manipulation
        primitives, such as list_for_each_entry_rcu() [2]_.

..         [1] The variant rcu_dereference_protected() can be used outside
        of an RCU read-side critical section as long as the usage is
        protected by locks acquired by the update-side code.  This variant
        avoids the lockdep warning that would happen when using (for
        example) rcu_dereference() without rcu_read_lock() protection.
        Using rcu_dereference_protected() also has the advantage
        of permitting compiler optimizations that rcu_dereference()
        must prohibit.        The rcu_dereference_protected() variant takes
        a lockdep expression to indicate which locks must be acquired
        by the caller. If the indicated protection is not provided,
        a lockdep splat is emitted.  See Design/Requirements/Requirements.rst
        and the API's code comments for more details and example usage.

..         [2] If the list_for_each_entry_rcu() instance might be used by
        update-side code as well as by RCU readers, then an additional
        lockdep expression can be added to its list of arguments.
        For example, given an additional "lock_is_held(&mylock)" argument,
        the RCU lockdep code would complain only if this instance was
        invoked outside of an RCU read-side critical section and without
        the protection of mylock.

Reader·updater·reclaimer 통신과 RCU flavor

원문의 그림은 세 역할의 통신을 보여 준다. Updater는 `rcu_assign_pointer()`로 reader에게 새 공간 상태를 게시하고 reader는 `rcu_dereference()`로 그 상태를 읽는다. Reader는 `rcu_read_lock()`/`unlock()`으로 reclaimer에게 시간적 수명을 알리며 updater는 `synchronize_rcu()` 또는 `call_rcu()`로 reclaim을 GP 뒤로 미룬다.

RCU infrastructure는 lock/unlock, synchronize/call의 시간 순서를 관찰해 동기 호출의 반환과 callback 실행 시점을 결정한다. 효율적 구현은 많은 요청을 batch로 묶어 overhead를 분산한다. 반면 assign/dereference는 RCU 보호 포인터의 store와 load를 통해 공간적 변화를 전달한다.

일반 RCU flavor는 `rcu_read_lock()`과 `rcu_dereference()`를 사용한다. BH flavor는 `rcu_read_lock_bh()` 또는 `local_bh_disable()`과 `rcu_dereference_bh()`를 사용하며 remote DoS를 받을 수 있는 networking 자료 구조에 적합하다.

Sched flavor는 `rcu_read_lock_sched()`, `preempt_disable()`, irq/NMI enter 구간과 `rcu_dereference_sched()`를 사용해 scheduler 및 interrupt/NMI handler를 보호한다. 보통은 일반 RCU를 사용하고 BH와 sched는 특수 상황에만 쓴다. SRCU와 RCU-Tasks 계열도 각 primitive 사이에 비슷한 시간·공간 관계를 갖는다.

The following diagram shows how each API communicates among the
reader, updater, and reclaimer.
::


            rcu_assign_pointer()
                                    +--------+
            +---------------------->| reader |---------+
            |                       +--------+         |
            |                           |              |
            |                           |              | Protect:
            |                           |              | rcu_read_lock()
            |                           |              | rcu_read_unlock()
            |        rcu_dereference()  |              |
            +---------+                 |              |
            | updater |<----------------+              |
            +---------+                                V
            |                                    +-----------+
            +----------------------------------->| reclaimer |
                                                 +-----------+
              Defer:
              synchronize_rcu() & call_rcu()


The RCU infrastructure observes the temporal sequence of rcu_read_lock(),
rcu_read_unlock(), synchronize_rcu(), and call_rcu() invocations in
order to determine when (1) synchronize_rcu() invocations may return
to their callers and (2) call_rcu() callbacks may be invoked.  Efficient
implementations of the RCU infrastructure make heavy use of batching in
order to amortize their overhead over many uses of the corresponding APIs.
The rcu_assign_pointer() and rcu_dereference() invocations communicate
spatial changes via stores to and loads from the RCU-protected pointer in
question.

There are at least three flavors of RCU usage in the Linux kernel. The diagram
above shows the most common one. On the updater side, the rcu_assign_pointer(),
synchronize_rcu() and call_rcu() primitives used are the same for all three
flavors. However for protection (on the reader side), the primitives used vary
depending on the flavor:

a.        rcu_read_lock() / rcu_read_unlock()
        rcu_dereference()

b.        rcu_read_lock_bh() / rcu_read_unlock_bh()
        local_bh_disable() / local_bh_enable()
        rcu_dereference_bh()

c.        rcu_read_lock_sched() / rcu_read_unlock_sched()
        preempt_disable() / preempt_enable()
        local_irq_save() / local_irq_restore()
        hardirq enter / hardirq exit
        NMI enter / NMI exit
        rcu_dereference_sched()

These three flavors are used as follows:

a.        RCU applied to normal data structures.

b.        RCU applied to networking data structures that may be subjected
        to remote denial-of-service attacks.

c.        RCU applied to scheduler and interrupt/NMI-handler tasks.

Again, most uses will be of (a).  The (b) and (c) cases are important
for specialized uses, but are relatively uncommon.  The SRCU, RCU-Tasks,
RCU-Tasks-Rude, and RCU-Tasks-Trace have similar relationships among
their assorted primitives.

.. _3_whatisRCU:

전역 포인터 copy-update 예제

예제는 동적 `struct foo`를 가리키는 `struct foo __rcu *gbl_foo`를 보호한다. Updater `foo_update_a()`는 새 구조를 할당하고 `foo_mutex`를 잡은 뒤, `rcu_dereference_protected()`로 이전 포인터를 읽어 전체 구조를 복사하고 필드 `a`만 바꾼다.

`rcu_assign_pointer(gbl_foo, new_fp)`가 완전히 초기화된 새 객체를 reader에게 게시한다. 이후 updater lock을 놓고 `synchronize_rcu()`를 기다린 뒤 old object를 `kfree()`한다. 할당은 lock 전에 수행해 긴 sleep이나 실패 처리를 update 임계 구역과 분리한다.

Reader `foo_get_a()`는 `rcu_read_lock()` 안에서 `rcu_dereference(gbl_foo)->a`를 읽고 unlock한 뒤 값의 복사본만 반환한다. 이 조합은 객체가 읽는 도중 해제되지 않게 하고 Alpha와 compiler를 포함해 초기화된 버전을 보게 한다.

RCU read-side section은 lock/unlock으로 감싸고 그 안의 RCU 포인터는 dereference accessor로 읽는다. 동시 updater끼리는 spinlock이나 semaphore 같은 별도 설계로 직렬화해야 한다. `rcu_assign_pointer()`는 updater와 reader 사이를 보호할 뿐 여러 updater 사이의 경쟁을 해결하지 않는다.

자료 구조에서 항목을 제거한 뒤 실제 해제 전에 `synchronize_rcu()`를 두어 그 항목을 참조할 수 있었던 모든 기존 reader가 끝나기를 기다린다. 더 일반적인 목록과 NMI 예제는 `listRCU.rst`, `NMI-RCU.rst`, 세부 검토 규칙은 `checklist.rst`에 있다.

3.  WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
-----------------------------------------------

This section shows a simple use of the core RCU API to protect a
global pointer to a dynamically allocated structure.  More-typical
uses of RCU may be found in listRCU.rst and NMI-RCU.rst.
::

        struct foo {
                int a;
                char b;
                long c;
        };
        DEFINE_SPINLOCK(foo_mutex);

        struct foo __rcu *gbl_foo;

        /*
         * Create a new struct foo that is the same as the one currently
         * pointed to by gbl_foo, except that field "a" is replaced
         * with "new_a".  Points gbl_foo to the new structure, and
         * frees up the old structure after a grace period.
         *
         * Uses rcu_assign_pointer() to ensure that concurrent readers
         * see the initialized version of the new structure.
         *
         * Uses synchronize_rcu() to ensure that any readers that might
         * have references to the old structure complete before freeing
         * the old structure.
         */
        void foo_update_a(int new_a)
        {
                struct foo *new_fp;
                struct foo *old_fp;

                new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
                spin_lock(&foo_mutex);
                old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
                *new_fp = *old_fp;
                new_fp->a = new_a;
                rcu_assign_pointer(gbl_foo, new_fp);
                spin_unlock(&foo_mutex);
                synchronize_rcu();
                kfree(old_fp);
        }

        /*
         * Return the value of field "a" of the current gbl_foo
         * structure.  Use rcu_read_lock() and rcu_read_unlock()
         * to ensure that the structure does not get deleted out
         * from under us, and use rcu_dereference() to ensure that
         * we see the initialized version of the structure (important
         * for DEC Alpha and for people reading the code).
         */
        int foo_get_a(void)
        {
                int retval;

                rcu_read_lock();
                retval = rcu_dereference(gbl_foo)->a;
                rcu_read_unlock();
                return retval;
        }

So, to sum up:

-        Use rcu_read_lock() and rcu_read_unlock() to guard RCU
        read-side critical sections.

-        Within an RCU read-side critical section, use rcu_dereference()
        to dereference RCU-protected pointers.

-        Use some solid design (such as locks or semaphores) to
        keep concurrent updates from interfering with each other.

-        Use rcu_assign_pointer() to update an RCU-protected pointer.
        This primitive protects concurrent readers from the updater,
        **not** concurrent updates from each other!  You therefore still
        need to use locking (or something similar) to keep concurrent
        rcu_assign_pointer() primitives from interfering with each other.

-        Use synchronize_rcu() **after** removing a data element from an
        RCU-protected data structure, but **before** reclaiming/freeing
        the data element, in order to wait for the completion of all
        RCU read-side critical sections that might be referencing that
        data item.

See checklist.rst for additional rules to follow when using RCU.
And again, more-typical uses of RCU may be found in listRCU.rst
and NMI-RCU.rst.

.. _4_whatisRCU:

Block할 수 없는 updater와 callback 회수

Updater가 GP 동안 기다릴 수 없다면 `synchronize_rcu()` 대신 `call_rcu(struct rcu_head *head, rcu_callback_t func)`를 사용한다. 이 함수는 GP가 지난 뒤 `func(head)`를 호출한다. Callback은 softirq 또는 process context에서 실행될 수 있으므로 block하면 안 된다.

객체 안에 `struct rcu_head rcu`를 넣고 update 경로는 copy와 게시까지 수행한 뒤 `call_rcu(&old_fp->rcu, foo_reclaim)`를 예약하고 즉시 반환한다. Callback은 `container_of(rp, struct foo, rcu)`로 `rcu_head`에서 원래 객체 주소를 구하고 필요한 cleanup 뒤 `kfree()`한다.

이 구조는 updater인 `foo_update_a()`와 reclaimer인 `foo_reclaim()`을 명확히 분리한다. 호출자는 이전 버전의 후속 수명을 직접 관리하지 않고 높은 우선순위 작업을 계속할 수 있다.

Callback이 단순히 객체를 `kfree()`하기만 한다면 별도 함수를 쓰지 않고 `kfree_rcu(old_fp, rcu)`를 사용할 수 있다. 가끔 sleep해도 된다면 객체에 `rcu_head`를 넣지 않는 단일 인수 `kfree_rcu_mightsleep(old_fp)`도 가능하다. 이 형태는 거의 block하지 않지만 메모리 할당 실패 때 `synchronize_rcu()`를 호출해 sleep할 수 있다.

비동기 회수에서도 순서는 같다. 먼저 자료 구조에서 항목을 제거하고, 그 다음 callback을 등록한다. Callback은 제거 전에 시작해 객체를 볼 수 있던 모든 RCU reader가 끝난 뒤 실행된다.

4.  WHAT IF MY UPDATING THREAD CANNOT BLOCK?
--------------------------------------------

In the example above, foo_update_a() blocks until a grace period elapses.
This is quite simple, but in some cases one cannot afford to wait so
long -- there might be other high-priority work to be done.

In such cases, one uses call_rcu() rather than synchronize_rcu().
The call_rcu() API is as follows::

        void call_rcu(struct rcu_head *head, rcu_callback_t func);

This function invokes func(head) after a grace period has elapsed.
This invocation might happen from either softirq or process context,
so the function is not permitted to block.  The foo struct needs to
have an rcu_head structure added, perhaps as follows::

        struct foo {
                int a;
                char b;
                long c;
                struct rcu_head rcu;
        };

The foo_update_a() function might then be written as follows::

        /*
         * Create a new struct foo that is the same as the one currently
         * pointed to by gbl_foo, except that field "a" is replaced
         * with "new_a".  Points gbl_foo to the new structure, and
         * frees up the old structure after a grace period.
         *
         * Uses rcu_assign_pointer() to ensure that concurrent readers
         * see the initialized version of the new structure.
         *
         * Uses call_rcu() to ensure that any readers that might have
         * references to the old structure complete before freeing the
         * old structure.
         */
        void foo_update_a(int new_a)
        {
                struct foo *new_fp;
                struct foo *old_fp;

                new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
                spin_lock(&foo_mutex);
                old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
                *new_fp = *old_fp;
                new_fp->a = new_a;
                rcu_assign_pointer(gbl_foo, new_fp);
                spin_unlock(&foo_mutex);
                call_rcu(&old_fp->rcu, foo_reclaim);
        }

The foo_reclaim() function might appear as follows::

        void foo_reclaim(struct rcu_head *rp)
        {
                struct foo *fp = container_of(rp, struct foo, rcu);

                foo_cleanup(fp->a);

                kfree(fp);
        }

The container_of() primitive is a macro that, given a pointer into a
struct, the type of the struct, and the pointed-to field within the
struct, returns a pointer to the beginning of the struct.

The use of call_rcu() permits the caller of foo_update_a() to
immediately regain control, without needing to worry further about the
old version of the newly updated element.  It also clearly shows the
RCU distinction between updater, namely foo_update_a(), and reclaimer,
namely foo_reclaim().

The summary of advice is the same as for the previous section, except
that we are now using call_rcu() rather than synchronize_rcu():

-        Use call_rcu() **after** removing a data element from an
        RCU-protected data structure in order to register a callback
        function that will be invoked after the completion of all RCU
        read-side critical sections that might be referencing that
        data item.

If the callback for call_rcu() is not doing anything more than calling
kfree() on the structure, you can use kfree_rcu() instead of call_rcu()
to avoid having to write your own callback::

        kfree_rcu(old_fp, rcu);

If the occasional sleep is permitted, the single-argument form may
be used, omitting the rcu_head structure from struct foo.

        kfree_rcu_mightsleep(old_fp);

This variant almost never blocks, but might do so by invoking
synchronize_rcu() in response to memory-allocation failure.

Again, see checklist.rst for additional rules governing the use of RCU.

.. _5_whatisRCU:

Toy 구현 1: reader-writer lock

RCU의 toy 구현은 실제 kernel 구현을 이해하는 첫 단계다. 여기의 두 구현은 기능과 성능이 부족해 제품에 쓸 수 없으며, 실제 구현은 `kernel/rcu/update.c`와 연결된 설계 논문을 참고해야 한다.

첫 toy 구현은 전역 recursive reader-writer lock `rcu_gp_mutex`를 사용한다. `rcu_read_lock()`과 unlock은 read lock을 잡고 놓으며, `synchronize_rcu()`는 같은 lock을 write로 한 번 획득하고 `smp_mb__after_spinlock()` 뒤 놓는다. Write 획득에 성공했다는 사실이 호출 전에 존재한 모든 reader가 read lock을 놓았음을 보장한다.

`smp_mb__after_spinlock()`은 `synchronize_rcu()`를 full memory barrier로 승격해 Requirements 문서의 memory-barrier 보장을 만족시킨다. 단순 assign은 `smp_store_release()`, dereference는 `READ_ONCE()`로 표현할 수 있지만 실제 patch에서는 정식 accessor를 생략하면 안 된다.

이 구현은 recursive read lock을 전제하므로 비재귀 lock으로 중첩 `rcu_read_lock()`을 허용하면 자기 교착한다. 확장성이 없고 realtime에서는 한 reader의 scheduling latency가 synchronize waiter를 거쳐 다른 reader에게 전파될 수 있다.

표면적으로는 read lock을 막는 주체가 `synchronize_rcu()`뿐이고 동기화 함수가 write lock을 잡은 채 다른 lock을 얻지 않으므로 deadlock cycle이 없어 보인다. 그러나 실제 kernel에서는 unrelated irq lock과 interrupt handler가 결합해 cycle을 만들 수 있으며 퀴즈 해설이 이를 보여 준다.

5.  WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
------------------------------------------------

One of the nice things about RCU is that it has extremely simple "toy"
implementations that are a good first step towards understanding the
production-quality implementations in the Linux kernel.  This section
presents two such "toy" implementations of RCU, one that is implemented
in terms of familiar locking primitives, and another that more closely
resembles "classic" RCU.  Both are way too simple for real-world use,
lacking both functionality and performance.  However, they are useful
in getting a feel for how RCU works.  See kernel/rcu/update.c for a
production-quality implementation, and see:

        https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit

for papers describing the Linux kernel RCU implementation.  The OLS'01
and OLS'02 papers are a good introduction, and the dissertation provides
more details on the current implementation as of early 2004.


5A.  "TOY" IMPLEMENTATION #1: LOCKING
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This section presents a "toy" RCU implementation that is based on
familiar locking primitives.  Its overhead makes it a non-starter for
real-life use, as does its lack of scalability.  It is also unsuitable
for realtime use, since it allows scheduling latency to "bleed" from
one read-side critical section to another.  It also assumes recursive
reader-writer locks:  If you try this with non-recursive locks, and
you allow nested rcu_read_lock() calls, you can deadlock.

However, it is probably the easiest implementation to relate to, so is
a good starting point.

It is extremely simple::

        static DEFINE_RWLOCK(rcu_gp_mutex);

        void rcu_read_lock(void)
        {
                read_lock(&rcu_gp_mutex);
        }

        void rcu_read_unlock(void)
        {
                read_unlock(&rcu_gp_mutex);
        }

        void synchronize_rcu(void)
        {
                write_lock(&rcu_gp_mutex);
                smp_mb__after_spinlock();
                write_unlock(&rcu_gp_mutex);
        }

[You can ignore rcu_assign_pointer() and rcu_dereference() without missing
much.  But here are simplified versions anyway.  And whatever you do,
don't forget about them when submitting patches making use of RCU!]::

        #define rcu_assign_pointer(p, v) \
        ({ \
                smp_store_release(&(p), (v)); \
        })

        #define rcu_dereference(p) \
        ({ \
                typeof(p) _________p1 = READ_ONCE(p); \
                (_________p1); \
        })


The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
and release a global reader-writer lock.  The synchronize_rcu()
primitive write-acquires this same lock, then releases it.  This means
that once synchronize_rcu() exits, all RCU read-side critical sections
that were in progress before synchronize_rcu() was called are guaranteed
to have completed -- there is no way that synchronize_rcu() would have
been able to write-acquire the lock otherwise.  The smp_mb__after_spinlock()
promotes synchronize_rcu() to a full memory barrier in compliance with
the "Memory-Barrier Guarantees" listed in:

        Design/Requirements/Requirements.rst

It is possible to nest rcu_read_lock(), since reader-writer locks may
be recursively acquired.  Note also that rcu_read_lock() is immune
from deadlock (an important property of RCU).  The reason for this is
that the only thing that can block rcu_read_lock() is a synchronize_rcu().
But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex,
so there can be no deadlock cycle.

.. _quiz_1:

Quick Quiz #1:
                Why is this argument naive?  How could a deadlock
                occur when using this algorithm in a real-world Linux
                kernel?  How could this deadlock be avoided?

:ref:`Answers to Quick Quiz <9_whatisRCU>`

Toy 구현 2: classic RCU

두 번째 toy 구현은 classic RCU를 닮았다. CPU hotplug와 `CONFIG_PREEMPTION`을 지원하지 않고 update 성능도 낮지만 non-preemptive kernel에서 reader가 왜 거의 공짜인지 보여 준다.

`rcu_read_lock()`과 `rcu_read_unlock()`은 아무 동작도 하지 않는다. 따라서 non-Alpha CPU에서 read-side overhead는 정확히 0이고 reader가 lock을 기다리지 않으므로 deadlock cycle에 참여할 수도 없다.

`synchronize_rcu()`는 `for_each_possible_cpu()`로 각 CPU에서 한 번씩 `run_on(cpu)`되도록 자신을 scheduling한다. Toy `run_on()`은 `sched_setaffinity()`로 만들 수 있으며 예제는 완료 후 affinity를 복구하지 않을 만큼 의도적으로 단순하다.

RCU read-side critical section 안에서 block하는 것이 불법이므로 한 CPU가 context switch를 했다면 그 CPU에서 switch 이전에 시작한 모든 RCU 읽기 구간은 끝났다. 모든 CPU가 한 번씩 context switch를 하면 모든 기존 reader가 끝났고 removal한 객체를 안전하게 회수할 수 있다.

실제 classic RCU는 CPU마다 작업을 직접 scheduling하는 이 비효율적 방식 대신 scheduler와 quiescent-state 보고를 결합한다. 하지만 실행 이력으로 reader 종료를 추론한다는 핵심은 같다.

5B.  "TOY" EXAMPLE #2: CLASSIC RCU
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This section presents a "toy" RCU implementation that is based on
"classic RCU".  It is also short on performance (but only for updates) and
on features such as hotplug CPU and the ability to run in CONFIG_PREEMPTION
kernels.  The definitions of rcu_dereference() and rcu_assign_pointer()
are the same as those shown in the preceding section, so they are omitted.
::

        void rcu_read_lock(void) { }

        void rcu_read_unlock(void) { }

        void synchronize_rcu(void)
        {
                int cpu;

                for_each_possible_cpu(cpu)
                        run_on(cpu);
        }

Note that rcu_read_lock() and rcu_read_unlock() do absolutely nothing.
This is the great strength of classic RCU in a non-preemptive kernel:
read-side overhead is precisely zero, at least on non-Alpha CPUs.
And there is absolutely no way that rcu_read_lock() can possibly
participate in a deadlock cycle!

The implementation of synchronize_rcu() simply schedules itself on each
CPU in turn.  The run_on() primitive can be implemented straightforwardly
in terms of the sched_setaffinity() primitive.  Of course, a somewhat less
"toy" implementation would restore the affinity upon completion rather
than just leaving all tasks running on the last CPU, but when I said
"toy", I meant **toy**!

So how the heck is this supposed to work???

Remember that it is illegal to block while in an RCU read-side critical
section.  Therefore, if a given CPU executes a context switch, we know
that it must have completed all preceding RCU read-side critical sections.
Once **all** CPUs have executed a context switch, then **all** preceding
RCU read-side critical sections will have completed.

So, suppose that we remove a data item from its structure and then invoke
synchronize_rcu().  Once synchronize_rcu() returns, we are guaranteed
that there are no RCU read-side critical sections holding a reference
to that data item, so we can safely reclaim it.

.. _quiz_2:

Quick Quiz #2:
                Give an example where Classic RCU's read-side
                overhead is **negative**.

:ref:`Answers to Quick Quiz <9_whatisRCU>`

.. _quiz_3:

Quick Quiz #3:
                If it is illegal to block in an RCU read-side
                critical section, what the heck do you do in
                CONFIG_PREEMPT_RT, where normal spinlocks can block???

:ref:`Answers to Quick Quiz <9_whatisRCU>`

.. _6_whatisRCU:

Reader-writer lock과의 비유

RCU의 흔한 사용은 reader-writer lock과 유사하다. 원문의 unified diff에서 자료 구조 정의는 거의 같고 전역 `rwlock_t`가 updater용 `spinlock_t`로 바뀐다. Reader의 `read_lock()`과 일반 목록 순회는 `rcu_read_lock()`과 `list_for_each_entry_rcu()`로 교체된다.

Delete 경로는 `write_lock()` 대신 updater spinlock을 잡고 `list_del_rcu()`로 항목을 논리적으로 제거한다. Lock을 놓은 뒤 `synchronize_rcu()`를 기다리고 나서 `kfree()`한다. Callback 방식이 필요하면 `call_rcu()` 또는 `kfree_rcu()`로 동기 대기를 바꿀 수 있다.

차이는 작아 보이지만 reader와 updater 임계 구역이 이제 동시에 실행된다는 중요한 변화가 있다. 일반적인 독립 항목 추가·삭제에는 문제가 없지만 여러 목록 변경을 하나의 atomic update로 보여야 한다면 reader가 중간 상태를 볼 수 있으므로 copy-replace, 추가 sequence, lock 등의 설계가 필요하다.

또한 기존 delete가 nonblocking이었더라도 `synchronize_rcu()`를 넣으면 sleep할 수 있다. 호출 문맥과 latency 요구를 점검해 callback 기반 회수를 선택해야 한다.

6.  ANALOGY WITH READER-WRITER LOCKING
--------------------------------------

Although RCU can be used in many different ways, a very common use of
RCU is analogous to reader-writer locking.  The following unified
diff shows how closely related RCU and reader-writer locking can be.
::

        @@ -5,5 +5,5 @@ struct el {
                 int data;
                 /* Other data fields */
         };
        -rwlock_t listmutex;
        +spinlock_t listmutex;
         struct el head;

        @@ -13,15 +14,15 @@
                struct list_head *lp;
                struct el *p;

        -        read_lock(&listmutex);
        -        list_for_each_entry(p, head, lp) {
        +        rcu_read_lock();
        +        list_for_each_entry_rcu(p, head, lp) {
                        if (p->key == key) {
                                *result = p->data;
        -                        read_unlock(&listmutex);
        +                        rcu_read_unlock();
                                return 1;
                        }
                }
        -        read_unlock(&listmutex);
        +        rcu_read_unlock();
                return 0;
         }

        @@ -29,15 +30,16 @@
         {
                struct el *p;

        -        write_lock(&listmutex);
        +        spin_lock(&listmutex);
                list_for_each_entry(p, head, lp) {
                        if (p->key == key) {
        -                        list_del(&p->list);
        -                        write_unlock(&listmutex);
        +                        list_del_rcu(&p->list);
        +                        spin_unlock(&listmutex);
        +                        synchronize_rcu();
                                kfree(p);
                                return 1;
                        }
                }
        -        write_unlock(&listmutex);
        +        spin_unlock(&listmutex);
                return 0;
         }

Or, for those who prefer a side-by-side listing::

 1 struct el {                          1 struct el {
 2   struct list_head list;             2   struct list_head list;
 3   long key;                          3   long key;
 4   spinlock_t mutex;                  4   spinlock_t mutex;
 5   int data;                          5   int data;
 6   /* Other data fields */            6   /* Other data fields */
 7 };                                   7 };
 8 rwlock_t listmutex;                  8 spinlock_t listmutex;
 9 struct el head;                      9 struct el head;

::

  1 int search(long key, int *result)    1 int search(long key, int *result)
  2 {                                    2 {
  3   struct list_head *lp;              3   struct list_head *lp;
  4   struct el *p;                      4   struct el *p;
  5                                      5
  6   read_lock(&listmutex);             6   rcu_read_lock();
  7   list_for_each_entry(p, head, lp) { 7   list_for_each_entry_rcu(p, head, lp) {
  8     if (p->key == key) {             8     if (p->key == key) {
  9       *result = p->data;             9       *result = p->data;
 10       read_unlock(&listmutex);      10       rcu_read_unlock();
 11       return 1;                     11       return 1;
 12     }                               12     }
 13   }                                 13   }
 14   read_unlock(&listmutex);          14   rcu_read_unlock();
 15   return 0;                         15   return 0;
 16 }                                   16 }

::

  1 int delete(long key)                 1 int delete(long key)
  2 {                                    2 {
  3   struct el *p;                      3   struct el *p;
  4                                      4
  5   write_lock(&listmutex);            5   spin_lock(&listmutex);
  6   list_for_each_entry(p, head, lp) { 6   list_for_each_entry(p, head, lp) {
  7     if (p->key == key) {             7     if (p->key == key) {
  8       list_del(&p->list);            8       list_del_rcu(&p->list);
  9       write_unlock(&listmutex);      9       spin_unlock(&listmutex);
                                        10       synchronize_rcu();
 10       kfree(p);                     11       kfree(p);
 11       return 1;                     12       return 1;
 12     }                               13     }
 13   }                                 14   }
 14   write_unlock(&listmutex);         15   spin_unlock(&listmutex);
 15   return 0;                         16   return 0;
 16 }                                   17 }

Either way, the differences are quite small.  Read-side locking moves
to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
a reader-writer lock to a simple spinlock, and a synchronize_rcu()
precedes the kfree().

However, there is one potential catch: the read-side and update-side
critical sections can now run concurrently.  In many cases, this will
not be a problem, but it is necessary to check carefully regardless.
For example, if multiple independent list updates must be seen as
a single atomic update, converting to RCU will require special care.

Also, the presence of synchronize_rcu() means that the RCU version of
delete() can now block.  If this is a problem, there is a callback-based
mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can
be used in place of synchronize_rcu().

.. _7_whatisRCU:

참조 카운트와의 비유

RCU를 보호 범위 전체에 대한 효율적인 임시 reference count로 생각할 수도 있다. Reference count는 일반적으로 객체 필드의 변경을 막지 않고 메모리가 해제되어 완전히 다른 type으로 재사용되는 큰 type 변화를 막는다. 필드 정합성에는 spinlock, `smp_load_acquire()`, atomic read-modify-write 같은 별도 ordering이 필요하다.

`rcu_read_lock()`과 unlock 사이에서 `__rcu` 포인터를 `rcu_dereference()`해 얻은 참조는 객체의 임시 참조 카운트를 올린 것처럼 취급할 수 있다. 이 동안 object type이 유지되므로 내부 spinlock을 잡거나 일반 reference count를 조작하고 다른 `__rcu` 포인터를 역참조할 수 있다.

일반적인 작업은 type상 안정적인 데이터를 복사하거나, `kref_get_unless_zero()`로 장기 참조를 얻거나, 객체 내부 spinlock을 잡은 뒤 identity를 재확인하고 수정하는 것이다. 장기 참조 획득은 이미 종료 중이면 실패할 수 있다.

`SLAB_TYPESAFE_BY_RCU` cache에서는 RCU가 identity조차 보장하지 않는다. 메모리가 해제된 뒤 같은 type의 다른 객체로 재할당될 수 있으므로 reader가 찾은 주소는 기대한 객체가 아닐 수 있다. 먼저 reference count를 안전하게 얻은 뒤 key나 identity를 재검사해야 한다.

재할당할 때마다 내부 spinlock을 다시 초기화해야 하므로 참조 없이 그 lock부터 잡는 것은 안전하지 않다. `refcount_{add|inc}_not_zero_acquire()`는 참조 획득 뒤 identity 검사가 오도록 acquire fence를 제공하고, 완전 초기화 뒤 `refcount_set_release()`를 호출하면 새 값이 참조 획득 가능 상태보다 먼저 보인다. 이 호출 뒤 객체는 다른 task에 visible한 것으로 취급한다.

전통적인 `kref_put()`의 마지막 참조 callback도 모든 전역 `__rcu` 포인터가 객체를 더 이상 가리키지 않고 GP가 지난 뒤에만 실행해야 한다. 전역 RCU 포인터 하나하나를 잠재적 counted reference로 보고 먼저 모두 교체한 뒤 `call_rcu()`로 finalization을 수행한다.

Reader-writer lock 비유는 목록처럼 여러 부분으로 이루어진 큰 구조에서 항목 추가·삭제의 동시성을 설명하기 좋다. Reference-count 비유는 그 안의 개별 객체를 read-side lifetime 동안 어떻게 안전하게 다루는지 설명하기 좋다.

7.  ANALOGY WITH REFERENCE COUNTING
-----------------------------------

The reader-writer analogy (illustrated by the previous section) is not
always the best way to think about using RCU.  Another helpful analogy
considers RCU an effective reference count on everything which is
protected by RCU.

A reference count typically does not prevent the referenced object's
values from changing, but does prevent changes to type -- particularly the
gross change of type that happens when that object's memory is freed and
re-allocated for some other purpose.  Once a type-safe reference to the
object is obtained, some other mechanism is needed to ensure consistent
access to the data in the object.  This could involve taking a spinlock,
but with RCU the typical approach is to perform reads with SMP-aware
operations such as smp_load_acquire(), to perform updates with atomic
read-modify-write operations, and to provide the necessary ordering.
RCU provides a number of support functions that embed the required
operations and ordering, such as the list_for_each_entry_rcu() macro
used in the previous section.

A more focused view of the reference counting behavior is that,
between rcu_read_lock() and rcu_read_unlock(), any reference taken with
rcu_dereference() on a pointer marked as ``__rcu`` can be treated as
though a reference-count on that object has been temporarily increased.
This prevents the object from changing type.  Exactly what this means
will depend on normal expectations of objects of that type, but it
typically includes that spinlocks can still be safely locked, normal
reference counters can be safely manipulated, and ``__rcu`` pointers
can be safely dereferenced.

Some operations that one might expect to see on an object for
which an RCU reference is held include:

 - Copying out data that is guaranteed to be stable by the object's type.
 - Using kref_get_unless_zero() or similar to get a longer-term
   reference.  This may fail of course.
 - Acquiring a spinlock in the object, and checking if the object still
   is the expected object and if so, manipulating it freely.

The understanding that RCU provides a reference that only prevents a
change of type is particularly visible with objects allocated from a
slab cache marked ``SLAB_TYPESAFE_BY_RCU``.  RCU operations may yield a
reference to an object from such a cache that has been concurrently freed
and the memory reallocated to a completely different object, though of
the same type.  In this case RCU doesn't even protect the identity of the
object from changing, only its type.  So the object found may not be the
one expected, but it will be one where it is safe to take a reference
(and then potentially acquiring a spinlock), allowing subsequent code
to check whether the identity matches expectations.  It is tempting
to simply acquire the spinlock without first taking the reference, but
unfortunately any spinlock in a ``SLAB_TYPESAFE_BY_RCU`` object must be
initialized after each and every call to kmem_cache_alloc(), which renders
reference-free spinlock acquisition completely unsafe.  Therefore, when
using ``SLAB_TYPESAFE_BY_RCU``, make proper use of a reference counter.
If using refcount_t, the specialized refcount_{add|inc}_not_zero_acquire()
and refcount_set_release() APIs should be used to ensure correct operation
ordering when verifying object identity and when initializing newly
allocated objects. Acquire fence in refcount_{add|inc}_not_zero_acquire()
ensures that identity checks happen *after* reference count is taken.
refcount_set_release() should be called after a newly allocated object is
fully initialized and release fence ensures that new values are visible
*before* refcount can be successfully taken by other users. Once
refcount_set_release() is called, the object should be considered visible
by other tasks.
(Those willing to initialize their locks in a kmem_cache constructor
may also use locking, including cache-friendly sequence locking.)

With traditional reference counting -- such as that implemented by the
kref library in Linux -- there is typically code that runs when the last
reference to an object is dropped.  With kref, this is the function
passed to kref_put().  When RCU is being used, such finalization code
must not be run until all ``__rcu`` pointers referencing the object have
been updated, and then a grace period has passed.  Every remaining
globally visible pointer to the object must be considered to be a
potential counted reference, and the finalization code is typically run
using call_rcu() only after all those pointers have been changed.

To see how to choose between these two analogies -- of RCU as a
reader-writer lock and RCU as a reference counting system -- it is useful
to reflect on the scale of the thing being protected.  The reader-writer
lock analogy looks at larger multi-part objects such as a linked list
and shows how RCU can facilitate concurrency while elements are added
to, and removed from, the list.  The reference-count analogy looks at
the individual objects and looks at how they can be accessed safely
within whatever whole they are a part of.

.. _8_whatisRCU:

전체 API 분류와 flavor 선택

이 장은 source의 kerneldoc header comment에 흩어진 RCU API를 범주별로 모은다. 목록 순회에는 `list_*_rcu`, `hlist_*_rcu`, `hlist_nulls_*`, `hlist_bl_*` 계열이 있고, 갱신에는 `rcu_assign_pointer`, `rcu_replace_pointer`, `list_add/del/replace/splice_rcu`, hlist와 nulls 변형이 있다.

일반 RCU 표는 critical section, grace period, barrier를 나눈다. Reader 측에는 lock/unlock, guard, dereference와 lockdep 검사 API가 있다. GP 측에는 `synchronize_rcu`, expedited·mult 변형, `call_rcu`, `kfree_rcu`, 조건부 동기화와 state polling API가 있다. `rcu_barrier()`는 예약된 callback 완료를 기다린다.

BH와 sched reader는 각각 bottom-half disable 구간과 preemption/irq 구간을 포함하며 v4.20 이후 update primitive는 일반 RCU와 공유한다. 초기화·정리에는 `RCU_INIT_POINTER`, initializer, `rcu_head` on-stack 관리, `SLAB_TYPESAFE_BY_RCU`가 있고, quiescent-state/control API는 reschedule, GP expedite, stall reset, watching 상태를 다룬다.

RCU-sync는 idle 판정과 enter/exit lifecycle을 제공한다. RCU-Tasks, Rude, Trace는 task 실행 이력과 tracing reader를 위한 별도 GP와 barrier를 갖는다. Trace에는 explicit read lock과 guard가 있지만 기본 Tasks와 Rude에는 일반 자료 구조용 critical section API가 없다.

SRCU는 list traversal, sleep 가능한 read lock, fast·NMI-safe·notrace 변형, down/up read, guard, dereference, GP polling, barrier를 제공한다. `DEFINE_SRCU`, `init_srcu_struct`, cleanup과 unlock 뒤 memory barrier가 lifecycle을 담당한다.

모든 flavor에 공통인 lockdep utility는 `RCU_LOCKDEP_WARN`, `rcu_sleep_check`다. 보호를 검사하지 않는 pointer fetch는 `rcu_dereference_raw`, 값만 검사하고 역참조하지 않는 접근은 `rcu_access_pointer`를 사용한다.

Reader가 실제로 block해야 하면 SRCU를 선택한다. Tracing과 함께 block하는 reader는 RCU-Tasks 계열이 필요할 수 있다. PREEMPT_RT에서 spinlock이 sleeplock으로 바뀌어 block하는 것만으로는 SRCU가 필요하지 않으며 non-RT에서도 block할 논리라면 SRCU가 필요하다.

NMI·hardirq·preemption-disabled 구간을 명시적 reader처럼 다루려면 sched reader 의미가 필요하다. Softirq 독점이나 network DoS 중에도 GP를 진행해야 하면 reader 전체에서 BH를 끈다. Update가 너무 잦다면 신중하게 `SLAB_TYPESAFE_BY_RCU`를 검토한다. Deep idle, user-mode 전환, offline CPU에서도 존중되는 reader가 필요하면 SRCU를 우선 선택하고 특수 tracing에는 Tasks Trace를 고려한다. 나머지는 일반 RCU를 쓴다.

8.  FULL LIST OF RCU APIs
-------------------------

The RCU APIs are documented in docbook-format header comments in the
Linux-kernel source code, but it helps to have a full list of the
APIs, since there does not appear to be a way to categorize them
in docbook.  Here is the list, by category.

RCU list traversal::

        list_entry_rcu
        list_entry_lockless
        list_first_entry_rcu
        list_first_or_null_rcu
        list_tail_rcu
        list_next_rcu
        list_next_or_null_rcu
        list_for_each_entry_rcu
        list_for_each_entry_continue_rcu
        list_for_each_entry_from_rcu
        list_for_each_entry_lockless
        hlist_first_rcu
        hlist_next_rcu
        hlist_pprev_rcu
        hlist_for_each_entry_rcu
        hlist_for_each_entry_rcu_notrace
        hlist_for_each_entry_rcu_bh
        hlist_for_each_entry_from_rcu
        hlist_for_each_entry_continue_rcu
        hlist_for_each_entry_continue_rcu_bh
        hlist_nulls_first_rcu
        hlist_nulls_next_rcu
        hlist_nulls_for_each_entry_rcu
        hlist_nulls_for_each_entry_safe
        hlist_bl_first_rcu
        hlist_bl_for_each_entry_rcu

RCU pointer/list update::

        rcu_assign_pointer
        rcu_replace_pointer
        INIT_LIST_HEAD_RCU
        list_add_rcu
        list_add_tail_rcu
        list_del_rcu
        list_replace_rcu
        list_splice_init_rcu
        list_splice_tail_init_rcu
        hlist_add_behind_rcu
        hlist_add_before_rcu
        hlist_add_head_rcu
        hlist_add_tail_rcu
        hlist_del_rcu
        hlist_del_init_rcu
        hlist_replace_rcu
        hlist_nulls_del_init_rcu
        hlist_nulls_del_rcu
        hlist_nulls_add_head_rcu
        hlist_nulls_add_tail_rcu
        hlist_nulls_add_fake
        hlists_swap_heads_rcu
        hlist_bl_add_head_rcu
        hlist_bl_del_rcu
        hlist_bl_set_first_rcu

RCU::

        Critical sections                Grace period                Barrier

        rcu_read_lock                        synchronize_net                rcu_barrier
        rcu_read_unlock                        synchronize_rcu
        guard(rcu)()                        synchronize_rcu_expedited
        scoped_guard(rcu)                synchronize_rcu_mult
        rcu_dereference                        call_rcu
        rcu_dereference_check                call_rcu_hurry
        rcu_dereference_protected        kfree_rcu
        rcu_read_lock_held                kvfree_rcu
        rcu_read_lock_any_held                kfree_rcu_mightsleep
        rcu_pointer_handoff                cond_synchronize_rcu
        unrcu_pointer                        cond_synchronize_rcu_full
                                        cond_synchronize_rcu_expedited
                                        cond_synchronize_rcu_expedited_full
                                        get_completed_synchronize_rcu
                                        get_completed_synchronize_rcu_full
                                        get_state_synchronize_rcu
                                        get_state_synchronize_rcu_full
                                        poll_state_synchronize_rcu
                                        poll_state_synchronize_rcu_full
                                        same_state_synchronize_rcu
                                        same_state_synchronize_rcu_full
                                        start_poll_synchronize_rcu
                                        start_poll_synchronize_rcu_full
                                        start_poll_synchronize_rcu_expedited
                                        start_poll_synchronize_rcu_expedited_full

bh::

        Critical sections        Grace period                Barrier

        rcu_read_lock_bh        [Same as RCU]                [Same as RCU]
        rcu_read_unlock_bh
        [local_bh_disable]
        [and friends]
        rcu_dereference_bh
        rcu_dereference_bh_check
        rcu_dereference_bh_protected
        rcu_read_lock_bh_held

sched::

        Critical sections        Grace period                Barrier

        rcu_read_lock_sched        [Same as RCU]                [Same as RCU]
        rcu_read_unlock_sched
        [preempt_disable]
        [and friends]
        rcu_read_lock_sched_notrace
        rcu_read_unlock_sched_notrace
        rcu_dereference_sched
        rcu_dereference_sched_check
        rcu_dereference_sched_protected
        rcu_read_lock_sched_held


RCU: Initialization/cleanup/ordering::

        RCU_INIT_POINTER
        RCU_INITIALIZER
        RCU_POINTER_INITIALIZER
        init_rcu_head
        destroy_rcu_head
        init_rcu_head_on_stack
        destroy_rcu_head_on_stack
        SLAB_TYPESAFE_BY_RCU


RCU: Quiescents states and control::

        cond_resched_tasks_rcu_qs
        rcu_all_qs
        rcu_softirq_qs_periodic
        rcu_end_inkernel_boot
        rcu_expedite_gp
        rcu_gp_is_expedited
        rcu_unexpedite_gp
        rcu_cpu_stall_reset
        rcu_head_after_call_rcu
        rcu_is_watching


RCU-sync primitive::

        rcu_sync_is_idle
        rcu_sync_init
        rcu_sync_enter
        rcu_sync_exit
        rcu_sync_dtor


RCU-Tasks::

        Critical sections        Grace period                        Barrier

        N/A                        call_rcu_tasks                        rcu_barrier_tasks
                                synchronize_rcu_tasks


RCU-Tasks-Rude::

        Critical sections        Grace period                        Barrier

        N/A                        synchronize_rcu_tasks_rude        rcu_barrier_tasks_rude
                                call_rcu_tasks_rude


RCU-Tasks-Trace::

        Critical sections        Grace period                        Barrier

        rcu_read_lock_trace        call_rcu_tasks_trace                rcu_barrier_tasks_trace
        rcu_read_unlock_trace        synchronize_rcu_tasks_trace
        guard(rcu_tasks_trace)()
        scoped_guard(rcu_tasks_trace)


SRCU list traversal::
        list_for_each_entry_srcu
        hlist_for_each_entry_srcu


SRCU::

        Critical sections                Grace period                Barrier

        srcu_read_lock                        call_srcu                srcu_barrier
        srcu_read_unlock                synchronize_srcu
        srcu_read_lock_fast                synchronize_srcu_expedited
        srcu_read_unlock_fast                get_state_synchronize_srcu
        srcu_read_lock_nmisafe                start_poll_synchronize_srcu
        srcu_read_unlock_nmisafe        start_poll_synchronize_srcu_expedited
        srcu_read_lock_notrace                poll_state_synchronize_srcu
        srcu_read_unlock_notrace
        srcu_down_read
        srcu_up_read
        srcu_down_read_fast
        srcu_up_read_fast
        guard(srcu)()
        scoped_guard(srcu)
        srcu_read_lock_held
        srcu_dereference
        srcu_dereference_check
        srcu_dereference_notrace
        srcu_read_lock_held


SRCU: Initialization/cleanup/ordering::

        DEFINE_SRCU
        DEFINE_STATIC_SRCU
        init_srcu_struct
        cleanup_srcu_struct
        smp_mb__after_srcu_read_unlock

All: lockdep-checked RCU utility APIs::

        RCU_LOCKDEP_WARN
        rcu_sleep_check

All: Unchecked RCU-protected pointer access::

        rcu_dereference_raw

All: Unchecked RCU-protected pointer access with dereferencing prohibited::

        rcu_access_pointer

See the comment headers in the source code (or the docbook generated
from them) for more information.

However, given that there are no fewer than four families of RCU APIs
in the Linux kernel, how do you choose which one to use?  The following
list can be helpful:

a.        Will readers need to block?  If so, you need SRCU.

b.        Will readers need to block and are you doing tracing, for
        example, ftrace or BPF?  If so, you need RCU-tasks,
        RCU-tasks-rude, and/or RCU-tasks-trace.

c.        What about the -rt patchset?  If readers would need to block in
        an non-rt kernel, you need SRCU.  If readers would block when
        acquiring spinlocks in a -rt kernel, but not in a non-rt kernel,
        SRCU is not necessary.        (The -rt patchset turns spinlocks into
        sleeplocks, hence this distinction.)

d.        Do you need to treat NMI handlers, hardirq handlers,
        and code segments with preemption disabled (whether
        via preempt_disable(), local_irq_save(), local_bh_disable(),
        or some other mechanism) as if they were explicit RCU readers?
        If so, RCU-sched readers are the only choice that will work
        for you, but since about v4.20 you use can use the vanilla RCU
        update primitives.

e.        Do you need RCU grace periods to complete even in the face of
        softirq monopolization of one or more of the CPUs?  For example,
        is your code subject to network-based denial-of-service attacks?
        If so, you should disable softirq across your readers, for
        example, by using rcu_read_lock_bh().  Since about v4.20 you
        use can use the vanilla RCU update primitives.

f.        Is your workload too update-intensive for normal use of
        RCU, but inappropriate for other synchronization mechanisms?
        If so, consider SLAB_TYPESAFE_BY_RCU (which was originally
        named SLAB_DESTROY_BY_RCU).  But please be careful!

g.        Do you need read-side critical sections that are respected even
        on CPUs that are deep in the idle loop, during entry to or exit
        from user-mode execution, or on an offlined CPU?  If so, SRCU
        and RCU Tasks Trace are the only choices that will work for you,
        with SRCU being strongly preferred in almost all cases.

h.        Otherwise, use RCU.

Of course, this all assumes that you have determined that RCU is in fact
the right tool for your job.

.. _9_whatisRCU:

Quick Quiz 해설과 실시간 RCU

Quiz 1은 lock 기반 toy 구현이 실제 kernel에서 왜 deadlock될 수 있는지 묻는다. CPU 0이 `spin_lock_irqsave()`로 `problematic_lock`을 잡고, CPU 1이 `synchronize_rcu()`에서 `rcu_gp_mutex` write lock을 잡는다. CPU 0은 `rcu_read_lock()`의 read lock을 기다리고, CPU 1에 들어온 interrupt handler는 `problematic_lock`을 기다리므로 cycle이 완성된다.

`CONFIG_PREEMPT_RT`처럼 일반 spinlock을 blocking lock으로 바꾸고 interrupt handler를 특수 task context에서 실행하면 handler가 block되어 CPU 1이 `rcu_gp_mutex`를 놓을 기회를 얻을 수 있다. 그러나 deadlock이 없어도 task A의 긴 reader가 synchronize waiter B를 막고, B의 write 대기가 새 reader C를 막는 latency bleed가 남는다. Realtime RCU는 counter 기반으로 synchronize 수행자가 reader 진입을 막지 않게 한다.

Quiz 2의 negative overhead 예는 non-preemptive 단일 CPU에서 process가 routing table을 읽고 irq가 ICMP REDIRECT로 갱신하는 경우다. 전통 방식은 process 검색 중 interrupt를 꺼야 하지만 classic RCU reader는 아무 동작도 하지 않는다. Interrupt disable의 양수 비용을 0으로 없앴다는 의미에서 RCU overhead가 음수라고 표현할 수 있다.

Quiz 3은 `CONFIG_PREEMPT_RT`에서 spinlock이 block할 수 있는데 RCU read-side section에서 block 금지 규칙과 모순되지 않는지 묻는다. RT는 spinlock 임계 구역과 RCU reader 모두 선점될 수 있게 하고 reader 안에서 spinlock 대기도 허용한다.

이 block은 priority boosting으로 GP가 필요할 때 reader를 실행시켜 끝낼 수 있기 때문에 통제 가능하다. 반면 network 수신이나 사용자 입력처럼 외부 사건을 기다리는 임의 block은 어느 task를 boost해도 사건을 만들 수 없으므로 허용되지 않는다. 문서는 가독성을 높인 Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, Alan Stern에게 감사를 전한다.

9.  ANSWERS TO QUICK QUIZZES
----------------------------

Quick Quiz #1:
                Why is this argument naive?  How could a deadlock
                occur when using this algorithm in a real-world Linux
                kernel?  [Referring to the lock-based "toy" RCU
                algorithm.]

Answer:
                Consider the following sequence of events:

                1.        CPU 0 acquires some unrelated lock, call it
                        "problematic_lock", disabling irq via
                        spin_lock_irqsave().

                2.        CPU 1 enters synchronize_rcu(), write-acquiring
                        rcu_gp_mutex.

                3.        CPU 0 enters rcu_read_lock(), but must wait
                        because CPU 1 holds rcu_gp_mutex.

                4.        CPU 1 is interrupted, and the irq handler
                        attempts to acquire problematic_lock.

                The system is now deadlocked.

                One way to avoid this deadlock is to use an approach like
                that of CONFIG_PREEMPT_RT, where all normal spinlocks
                become blocking locks, and all irq handlers execute in
                the context of special tasks.  In this case, in step 4
                above, the irq handler would block, allowing CPU 1 to
                release rcu_gp_mutex, avoiding the deadlock.

                Even in the absence of deadlock, this RCU implementation
                allows latency to "bleed" from readers to other
                readers through synchronize_rcu().  To see this,
                consider task A in an RCU read-side critical section
                (thus read-holding rcu_gp_mutex), task B blocked
                attempting to write-acquire rcu_gp_mutex, and
                task C blocked in rcu_read_lock() attempting to
                read_acquire rcu_gp_mutex.  Task A's RCU read-side
                latency is holding up task C, albeit indirectly via
                task B.

                Realtime RCU implementations therefore use a counter-based
                approach where tasks in RCU read-side critical sections
                cannot be blocked by tasks executing synchronize_rcu().

:ref:`Back to Quick Quiz #1 <quiz_1>`

Quick Quiz #2:
                Give an example where Classic RCU's read-side
                overhead is **negative**.

Answer:
                Imagine a single-CPU system with a non-CONFIG_PREEMPTION
                kernel where a routing table is used by process-context
                code, but can be updated by irq-context code (for example,
                by an "ICMP REDIRECT" packet).        The usual way of handling
                this would be to have the process-context code disable
                interrupts while searching the routing table.  Use of
                RCU allows such interrupt-disabling to be dispensed with.
                Thus, without RCU, you pay the cost of disabling interrupts,
                and with RCU you don't.

                One can argue that the overhead of RCU in this
                case is negative with respect to the single-CPU
                interrupt-disabling approach.  Others might argue that
                the overhead of RCU is merely zero, and that replacing
                the positive overhead of the interrupt-disabling scheme
                with the zero-overhead RCU scheme does not constitute
                negative overhead.

                In real life, of course, things are more complex.  But
                even the theoretical possibility of negative overhead for
                a synchronization primitive is a bit unexpected.  ;-)

:ref:`Back to Quick Quiz #2 <quiz_2>`

Quick Quiz #3:
                If it is illegal to block in an RCU read-side
                critical section, what the heck do you do in
                CONFIG_PREEMPT_RT, where normal spinlocks can block???

Answer:
                Just as CONFIG_PREEMPT_RT permits preemption of spinlock
                critical sections, it permits preemption of RCU
                read-side critical sections.  It also permits
                spinlocks blocking while in RCU read-side critical
                sections.

                Why the apparent inconsistency?  Because it is
                possible to use priority boosting to keep the RCU
                grace periods short if need be (for example, if running
                short of memory).  In contrast, if blocking waiting
                for (say) network reception, there is no way to know
                what should be boosted.  Especially given that the
                process we need to boost might well be a human being
                who just went out for a pizza or something.  And although
                a computer-operated cattle prod might arouse serious
                interest, it might also provoke serious objections.
                Besides, how does the computer know what pizza parlor
                the human being went to???

:ref:`Back to Quick Quiz #3 <quiz_3>`

ACKNOWLEDGEMENTS

My thanks to the people who helped make this human-readable, including
Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern.


For more information, see http://www.rdrop.com/users/paulmck/RCU.