단일 프로세서 시스템의 RCU

예제 1: softirq에서 즉시 callback을 실행하면 안 되는 이유

UP 시스템에는 CPU가 하나뿐이므로 `call_rcu()`가 callback을 즉시 호출해도 된다는 생각은 잘못이다. 다른 CPU가 없어도 한 CPU 안에서 process, softirq, hardware interrupt 실행 문맥이 서로를 중단할 수 있고, RCU 독자가 아직 객체를 참조하는 동안 삭제 경로가 실행될 수 있다.

Process context가 A-B-C 목록을 순회하며 B를 참조하는 순간 softirq가 끼어들어 B를 삭제하고 `call_rcu()`로 해제를 예약한다고 하자. `call_rcu()`가 즉시 callback을 실행하면 softirq에서 돌아온 순회 코드는 이미 해제된 B를 계속 참조한다. hardware interrupt handler에서 호출하는 경우도 같다.

.. _up_doc:

RCU on Uniprocessor Systems
===========================

A common misconception is that, on UP systems, the call_rcu() primitive
may immediately invoke its function.  The basis of this misconception
is that since there is only one CPU, it should not be necessary to
wait for anything else to get done, since there are no other CPUs for
anything else to be happening on.  Although this approach will *sort of*
work a surprising amount of the time, it is a very bad idea in general.
This document presents three examples that demonstrate exactly how bad
an idea this is.

Example 1: softirq Suicide
--------------------------

Suppose that an RCU-based algorithm scans a linked list containing
elements A, B, and C in process context, and can delete elements from
this same list in softirq context.  Suppose that the process-context scan
is referencing element B when it is interrupted by softirq processing,
which deletes element B, and then invokes call_rcu() to free element B
after a grace period.

Now, if call_rcu() were to directly invoke its arguments, then upon return
from softirq, the list scan would find itself referencing a newly freed
element B.  This situation can greatly decrease the life expectancy of
your kernel.

This same problem can occur if call_rcu() is invoked from a hardware
interrupt handler.

예제 2: 함수 호출 안의 삭제

즉시 callback을 process context에서만 허용해도 안전하지 않다. Process context에서 목록을 순회하면서 각 원소에 함수를 호출하고, 그 함수가 현재 B를 삭제해 `call_rcu()`에 넘기는 것은 합법적인 RCU 사용이다.

하지만 이때 callback을 즉시 실행하면 바깥 순회 함수의 RCU read-side critical section이 아직 끝나지 않았는데 B를 해제한다. 이는 `call_rcu()`가 예약 당시 실행 중이던 모든 RCU 읽기 임계 구역이 끝날 때까지 callback을 미룬다는 핵심 보장을 위반한다.

이 함수 안에서 `synchronize_rcu()`를 호출하는 것도 합법적이지 않다. 호출자는 RCU 보호 목록을 순회 중이므로 read-side critical section 안에 있고, 그 안에서는 block할 수 없다.

Example 2: Function-Call Fatality
---------------------------------

Of course, one could avert the suicide described in the preceding example
by having call_rcu() directly invoke its arguments only if it was called
from process context.  However, this can fail in a similar manner.

Suppose that an RCU-based algorithm again scans a linked list containing
elements A, B, and C in process context, but that it invokes a function
on each element as it is scanned.  Suppose further that this function
deletes element B from the list, then passes it to call_rcu() for deferred
freeing.  This may be a bit unconventional, but it is perfectly legal
RCU usage, since call_rcu() must wait for a grace period to elapse.
Therefore, in this case, allowing call_rcu() to immediately invoke
its arguments would cause it to fail to make the fundamental guarantee
underlying RCU, namely that call_rcu() defers invoking its arguments until
all RCU read-side critical sections currently executing have completed.

Quick Quiz #1:
        Why is it *not* legal to invoke synchronize_rcu() in this case?

:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`

예제 3: callback 즉시 실행과 자기 교착

`call_rcu()`를 어떤 잠금 아래 호출하고 callback도 같은 잠금을 획득한다면, 즉시 callback 실행은 자기 교착을 만든다. 심지어 그 callback이 한 grace period 뒤의 다른 `call_rcu()` 호출에서 실행되더라도 호출자의 잠금 문맥이 같다면 문제가 된다.

잠금을 놓은 뒤에만 `call_rcu()`하도록 재구성할 수 있는 경우도 있지만, 한 임계 구역에서 여러 항목을 예약하면 별도 목록을 만들고 나중에 다시 순회해야 한다. 잠금이 공통 kernel API 호출 전체에 걸쳐 유지된다면 임의 데이터를 상위 계층으로 전달하도록 API 자체를 바꿔야 할 수도 있다. callback은 잠금이 없는 알려진 환경에서 실행된다는 보장을 유지하는 편이 낫다.

RCU callback이 획득하는 잠금은 process context의 다른 획득 지점에서 `spin_lock_bh()` 같은 `_bh` variant로 잡아야 한다. callback은 softirq context에서 실행되어 단순 `spin_lock()` 임계 구역을 중단할 수 있기 때문이다. `_irq` variant인 `spin_lock_irqsave()`도 사용할 수 있다. callback이 `kfree()` 같은 함수를 통해 간접적으로 잠금을 얻는 경우도 고려해야 한다.

일부 제약이 큰 userspace RCU는 callback이 queue된 뒤 완전한 GP가 이미 지났다면 `call_rcu()` 안에서 직접 실행할 수 있게 한다. 그래도 deadlock 회피 이점을 얻기 위해 직접 실행을 피하는 것이 강하게 권장된다.

Example 3: Death by Deadlock
----------------------------

Suppose that call_rcu() is invoked while holding a lock, and that the
callback function must acquire this same lock.  In this case, if
call_rcu() were to directly invoke the callback, the result would
be self-deadlock *even if* this invocation occurred from a later
call_rcu() invocation a full grace period later.

In some cases, it would possible to restructure to code so that
the call_rcu() is delayed until after the lock is released.  However,
there are cases where this can be quite ugly:

1.        If a number of items need to be passed to call_rcu() within
        the same critical section, then the code would need to create
        a list of them, then traverse the list once the lock was
        released.

2.        In some cases, the lock will be held across some kernel API,
        so that delaying the call_rcu() until the lock is released
        requires that the data item be passed up via a common API.
        It is far better to guarantee that callbacks are invoked
        with no locks held than to have to modify such APIs to allow
        arbitrary data items to be passed back up through them.

If call_rcu() directly invokes the callback, painful locking restrictions
or API changes would be required.

Quick Quiz #2:
        What locking restriction must RCU callbacks respect?

:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`

It is important to note that userspace RCU implementations *do*
permit call_rcu() to directly invoke callbacks, but only if a full
grace period has elapsed since those callbacks were queued.  This is
the case because some userspace environments are extremely constrained.
Nevertheless, people writing userspace RCU implementations are strongly
encouraged to avoid invoking callbacks from call_rcu(), thus obtaining
the deadlock-avoidance benefits called out above.

UP에서도 필요한 grace period

UP 시스템에서도 `call_rcu()`가 인수를 즉시 호출하게 하면 RCU가 깨진다. RCU 기반 구조는 grace period를 지켜야 하며 callback은 어떤 잠금도 잡혀 있지 않은 알려진 실행 환경에서 호출되어야 한다.

반면 비선점 UP 시스템에서는 `synchronize_rcu()`가 즉시 반환해도 안전할 수 있고, UP 하드웨어에서 실행되는 PREEMPT SMP build도 해당 구현의 조건에 따라 최적화될 수 있다. 그러나 preemptible RCU에는 다른 태스크가 RCU 읽기 구간 중간에서 선점되어 있을 수 있으므로 단순한 즉시 반환은 허용되지 않는다.

Summary
-------

Permitting call_rcu() to immediately invoke its arguments breaks RCU,
even on a UP system.  So do not do it!  Even on a UP system, the RCU
infrastructure *must* respect grace periods, and *must* invoke callbacks
from a known environment in which no locks are held.

Note that it *is* safe for synchronize_rcu() to return immediately on
UP systems, including PREEMPT SMP builds running on UP systems.

Quick Quiz #3:
        Why can't synchronize_rcu() return immediately on UP systems running
        preemptible RCU?

Quick Quiz 해설

Quiz 1의 답: 호출 함수가 RCU 보호 목록을 순회 중이므로 호출된 삭제 함수도 RCU read-side critical section 안에서 실행된다. 이 구간에서는 block할 수 없으므로 `synchronize_rcu()`를 호출할 수 없다.

Quiz 2의 답: callback이 획득하는 모든 잠금은 다른 곳에서 `_bh` spinlock variant 또는 더 강한 `_irq` variant로 획득해야 한다. 그렇지 않으면 process context가 단순 `spin_lock()`을 잡은 상태에서 softirq callback이 끼어들어 같은 잠금을 기다리는 자기 교착이 생긴다. 직접 잠금을 잡지 않는 callback도 `kfree()` 등을 통해 간접적으로 잡을 수 있다.

Quiz 3의 답: preemptible RCU에서는 다른 태스크가 read-side critical section 중간에 선점되어 있을 수 있다. `synchronize_rcu()`가 즉시 반환하면 GP 종료를 너무 일찍 알리고, 나중에 재개된 태스크는 이미 회수된 객체를 만날 수 있다.

.. _answer_quick_quiz_up:

Answer to Quick Quiz #1:
        Why is it *not* legal to invoke synchronize_rcu() in this case?

        Because the calling function is scanning an RCU-protected linked
        list, and is therefore within an RCU read-side critical section.
        Therefore, the called function has been invoked within an RCU
        read-side critical section, and is not permitted to block.

Answer to Quick Quiz #2:
        What locking restriction must RCU callbacks respect?

        Any lock that is acquired within an RCU callback must be acquired
        elsewhere using an _bh variant of the spinlock primitive.
        For example, if "mylock" is acquired by an RCU callback, then
        a process-context acquisition of this lock must use something
        like spin_lock_bh() to acquire the lock.  Please note that
        it is also OK to use _irq variants of spinlocks, for example,
        spin_lock_irqsave().

        If the process-context code were to simply use spin_lock(),
        then, since RCU callbacks can be invoked from softirq context,
        the callback might be called from a softirq that interrupted
        the process-context critical section.  This would result in
        self-deadlock.

        This restriction might seem gratuitous, since very few RCU
        callbacks acquire locks directly.  However, a great many RCU
        callbacks do acquire locks *indirectly*, for example, via
        the kfree() primitive.

Answer to Quick Quiz #3:
        Why can't synchronize_rcu() return immediately on UP systems
        running preemptible RCU?

        Because some other task might have been preempted in the middle
        of an RCU read-side critical section.  If synchronize_rcu()
        simply immediately returned, it would prematurely signal the
        end of the grace period, which would come as a nasty shock to
        that other thread when it started running again.