RCU와 unload 가능한 module

IRQ에서 비동기 callback 게시

RCU updater는 `call_rcu()`로 grace period를 비동기적으로 기다릴 수 있다. 이 API는 보호 객체 안의 `struct rcu_head`와 나중에 객체를 해제할 callback 함수 pointer를 받는다.

IRQ context에서 `list_del_rcu(p)`로 원소를 제거하고 `call_rcu(&p->rcu, p_callback)`을 호출할 수 있다. `call_rcu()`는 block하지 않으므로 IRQ에 안전하다. Callback은 `container_of()`로 `rcu_head`에서 원래 `struct pstruct`를 찾고 `kfree(p)`를 수행한다.

.. _rcu_barrier:

RCU and Unloadable Modules
==========================

[Originally published in LWN Jan. 14, 2007: http://lwn.net/Articles/217484/]

RCU updaters sometimes use call_rcu() to initiate an asynchronous wait for
a grace period to elapse.  This primitive takes a pointer to an rcu_head
struct placed within the RCU-protected data structure and another pointer
to a function that may be invoked later to free that structure. Code to
delete an element p from the linked list from IRQ context might then be
as follows::

        list_del_rcu(p);
        call_rcu(&p->rcu, p_callback);

Since call_rcu() never blocks, this code can safely be used from within
IRQ context. The function p_callback() might be defined as follows::

        static void p_callback(struct rcu_head *rp)
        {
                struct pstruct *p = container_of(rp, struct pstruct, rcu);

                kfree(p);
        }

synchronize_rcu()만으로 module unload가 안전하지 않은 이유

Callback 함수가 unload 가능한 module text 안에 있으면 module을 먼저 내린 뒤 pending callback이 실행될 때 존재하지 않는 코드를 호출해 crash한다.

Module exit에서 `synchronize_rcu()` 하나를 호출해도 충분하지 않다. 이 함수는 grace period가 끝나기를 기다리지만 callback 함수 실행 완료까지 기다리지는 않는다. 여러 GP를 연속 호출해도 callback load가 높으면 실시간 latency를 위해 callback batch가 지연될 수 있어 보장이 없다.

Unloading Modules That Use call_rcu()
-------------------------------------

But what if the p_callback() function is defined in an unloadable module?

If we unload the module while some RCU callbacks are pending,
the CPUs executing these callbacks are going to be severely
disappointed when they are later invoked, as fancifully depicted at
http://lwn.net/images/ns/kernel/rcu-drop.jpg.

We could try placing a synchronize_rcu() in the module-exit code path,
but this is not sufficient. Although synchronize_rcu() does wait for a
grace period to elapse, it does not wait for the callbacks to complete.

One might be tempted to try several back-to-back synchronize_rcu()
calls, but this is still not guaranteed to work. If there is a very
heavy RCU-callback load, then some of the callbacks might be deferred in
order to allow other processing to proceed. For but one example, such
deferral is required in realtime kernels in order to avoid excessive
scheduling latencies.

rcu_barrier()와 SRCU flavor 대응

`rcu_barrier()`는 새 grace period 하나를 기다리는 대신 시스템에 이미 outstanding인 모든 RCU callback이 완료될 때까지 기다린다. Queue가 비어 있으면 GP를 기다리지 않고 즉시 반환할 수 있으므로 `synchronize_rcu()`를 함축하지 않는다.

안전한 unload 순서는 새 callback 게시를 먼저 막고, `rcu_barrier()`를 실행한 뒤 module을 내리는 것이다. 이 순서를 거꾸로 하면 barrier가 반환하는 동안 새 callback이 추가될 수 있다.

SRCU callback에는 같은 `srcu_struct`의 `srcu_barrier()`를 사용한다. Module이 `call_rcu()`와 두 SRCU domain의 `call_srcu()`를 쓴다면 `rcu_barrier()` 한 번과 domain별 `srcu_barrier()` 두 번이 필요하다. Latency가 중요하면 workqueue에서 세 barrier를 동시에 실행할 수 있다.

rcu_barrier()
-------------

This situation can be handled by the rcu_barrier() primitive.  Rather
than waiting for a grace period to elapse, rcu_barrier() waits for all
outstanding RCU callbacks to complete.  Please note that rcu_barrier()
does **not** imply synchronize_rcu(), in particular, if there are no RCU
callbacks queued anywhere, rcu_barrier() is within its rights to return
immediately, without waiting for anything, let alone a grace period.

Pseudo-code using rcu_barrier() is as follows:

   1. Prevent any new RCU callbacks from being posted.
   2. Execute rcu_barrier().
   3. Allow the module to be unloaded.

There is also an srcu_barrier() function for SRCU, and you of course
must match the flavor of srcu_barrier() with that of call_srcu().
If your module uses multiple srcu_struct structures, then it must also
use multiple invocations of srcu_barrier() when unloading that module.
For example, if it uses call_rcu(), call_srcu() on srcu_struct_1, and
call_srcu() on srcu_struct_2, then the following three lines of code
will be required when unloading::

  1  rcu_barrier();
  2  srcu_barrier(&srcu_struct_1);
  3  srcu_barrier(&srcu_struct_2);

If latency is of the essence, workqueues could be used to run these
three functions concurrently.

An ancient version of the rcutorture module makes use of rcu_barrier()
in its exit function as follows::

  1  static void
  2  rcu_torture_cleanup(void)
  3  {
  4    int i;
  5
  6    fullstop = 1;
  7    if (shuffler_task != NULL) {
  8      VERBOSE_PRINTK_STRING("Stopping rcu_torture_shuffle task");
  9      kthread_stop(shuffler_task);
 10    }
 11    shuffler_task = NULL;
 12
 13    if (writer_task != NULL) {
 14      VERBOSE_PRINTK_STRING("Stopping rcu_torture_writer task");
 15      kthread_stop(writer_task);
 16    }
 17    writer_task = NULL;
 18

rcutorture cleanup과 producer 정지

과거 `rcutorture` cleanup은 line 6에서 `fullstop=1`로 callback이 자신을 다시 게시하지 못하게 한다. 일반 callback은 드물게만 `call_rcu()`를 재호출하지만 rcutorture는 의도적으로 예외이므로 이 전역 gate가 필요하다.

Lines 7-50은 shuffler, writer, reader, fakewriter, stats kthread를 모두 `kthread_stop()`으로 정지하고 배열 메모리를 해제한다. Line 53에 도달하면 새 rcutorture callback을 만들 실행 주체가 없다.

Line 53의 `rcu_barrier()`가 기존 callback을 전부 끝낸 뒤 lines 55-62가 통계와 operation-specific cleanup을 수행한다. 이 ordering은 callback이 module state 또는 text를 참조하는 동안 cleanup이 먼저 진행되지 않게 한다.

Timer가 `call_rcu()`를 게시하는 module은 먼저 새 timer 게시를 막고 이미 게시된 timer를 취소하거나 완료까지 기다린 뒤 barrier를 호출해야 한다. Filesystem unmount처럼 module unload가 아닌 수명 경계에서도 같은 요구가 생긴다.

 19    if (reader_tasks != NULL) {
 20      for (i = 0; i < nrealreaders; i++) {
 21        if (reader_tasks[i] != NULL) {
 22          VERBOSE_PRINTK_STRING(
 23            "Stopping rcu_torture_reader task");
 24          kthread_stop(reader_tasks[i]);
 25        }
 26        reader_tasks[i] = NULL;
 27      }
 28      kfree(reader_tasks);
 29      reader_tasks = NULL;
 30    }
 31    rcu_torture_current = NULL;
 32
 33    if (fakewriter_tasks != NULL) {
 34      for (i = 0; i < nfakewriters; i++) {
 35        if (fakewriter_tasks[i] != NULL) {
 36          VERBOSE_PRINTK_STRING(
 37            "Stopping rcu_torture_fakewriter task");
 38          kthread_stop(fakewriter_tasks[i]);
 39        }
 40        fakewriter_tasks[i] = NULL;
 41      }
 42      kfree(fakewriter_tasks);
 43      fakewriter_tasks = NULL;
 44    }
 45
 46    if (stats_task != NULL) {
 47      VERBOSE_PRINTK_STRING("Stopping rcu_torture_stats task");
 48      kthread_stop(stats_task);
 49    }
 50    stats_task = NULL;
 51
 52    /* Wait for all RCU callbacks to fire. */
 53    rcu_barrier();
 54
 55    rcu_torture_stats_print(); /* -After- the stats thread is stopped! */
 56
 57    if (cur_ops->cleanup != NULL)
 58      cur_ops->cleanup();
 59    if (atomic_read(&n_rcu_torture_error))
 60      rcu_torture_print_module_parms("End of test: FAILURE");
 61    else
 62      rcu_torture_print_module_parms("End of test: SUCCESS");
 63  }

Line 6 sets a global variable that prevents any RCU callbacks from
re-posting themselves. This will not be necessary in most cases, since
RCU callbacks rarely include calls to call_rcu(). However, the rcutorture
module is an exception to this rule, and therefore needs to set this
global variable.

Lines 7-50 stop all the kernel tasks associated with the rcutorture
module. Therefore, once execution reaches line 53, no more rcutorture
RCU callbacks will be posted. The rcu_barrier() call on line 53 waits
for any pre-existing callbacks to complete.

Then lines 55-62 print status and do operation-specific cleanup, and
then return, permitting the module-unload operation to be completed.

.. _rcubarrier_quiz_1:

Quick Quiz #1:
        Is there any other situation where rcu_barrier() might
        be required?

:ref:`Answer to Quick Quiz #1 <answer_rcubarrier_quiz_1>`

Your module might have additional complications. For example, if your
module invokes call_rcu() from timers, you will need to first refrain
from posting new timers, cancel (or wait for) all the already-posted
timers, and only then invoke rcu_barrier() to wait for any remaining
RCU callbacks to complete.

Of course, if your module uses call_rcu(), you will need to invoke
rcu_barrier() before unloading.  Similarly, if your module uses
call_srcu(), you will need to invoke srcu_barrier() before unloading,
and on the same srcu_struct structure.  If your module uses call_rcu()
**and** call_srcu(), then (as noted above) you will need to invoke
rcu_barrier() **and** srcu_barrier().

Per-CPU sentinel callback 구현

Dipankar Sarma의 구현은 한 per-CPU callback queue 안에서 RCU callback 순서가 바뀌지 않는다는 성질을 이용한다. 각 CPU queue 뒤에 sentinel callback을 하나씩 추가하고 모든 sentinel이 실행되기를 기다리면, 그보다 앞에 있던 모든 callback도 끝났다고 알 수 있다.

초기 `rcu_barrier()`는 interrupt context가 아님을 확인하고 `rcu_barrier_mutex`로 전역 completion과 counter를 한 호출만 사용하게 한다. Counter를 1로 초기화한 뒤 `on_each_cpu(rcu_barrier_func, NULL, 0, 1)`를 실행하고 초기 count를 감소시켜 0이면 completion을 완료한다. 마지막으로 `wait_for_completion()`한다.

`on_each_cpu()`의 wait flag 1은 각 CPU의 `rcu_barrier_func()` 호출 자체가 끝날 때까지 반환하지 않게 한다. Mutex는 CPU-hotplug와 동시 barrier의 전역 상태 경쟁을 막는 초기 설계의 중요한 경계다. 현재 구현은 이후 여러 차례 재작성되었지만 sentinel 원리는 유지된다.

Implementing rcu_barrier()
--------------------------

Dipankar Sarma's implementation of rcu_barrier() makes use of the fact
that RCU callbacks are never reordered once queued on one of the per-CPU
queues. His implementation queues an RCU callback on each of the per-CPU
callback queues, and then waits until they have all started executing, at
which point, all earlier RCU callbacks are guaranteed to have completed.

The original code for rcu_barrier() was roughly as follows::

  1  void rcu_barrier(void)
  2  {
  3    BUG_ON(in_interrupt());
  4    /* Take cpucontrol mutex to protect against CPU hotplug */
  5    mutex_lock(&rcu_barrier_mutex);
  6    init_completion(&rcu_barrier_completion);
  7    atomic_set(&rcu_barrier_cpu_count, 1);
  8    on_each_cpu(rcu_barrier_func, NULL, 0, 1);
  9    if (atomic_dec_and_test(&rcu_barrier_cpu_count))
 10      complete(&rcu_barrier_completion);
 11    wait_for_completion(&rcu_barrier_completion);
 12    mutex_unlock(&rcu_barrier_mutex);
 13  }

Line 3 verifies that the caller is in process context, and lines 5 and 12
use rcu_barrier_mutex to ensure that only one rcu_barrier() is using the
global completion and counters at a time, which are initialized on lines
6 and 7. Line 8 causes each CPU to invoke rcu_barrier_func(), which is
shown below. Note that the final "1" in on_each_cpu()'s argument list
ensures that all the calls to rcu_barrier_func() will have completed
before on_each_cpu() returns. Line 9 removes the initial count from
rcu_barrier_cpu_count, and if this count is now zero, line 10 finalizes
the completion, which prevents line 11 from blocking.  Either way,
line 11 then waits (if needed) for the completion.

.. _rcubarrier_quiz_2:

초기 count와 조기 반환 race

`rcu_barrier_func()`는 현재 CPU의 `struct rcu_data`에서 barrier용 `rcu_head`를 가져오고 global counter를 증가시킨 뒤 `call_rcu(head, rcu_barrier_callback)`을 등록한다. Callback은 counter를 감소시키고 0이면 completion을 끝낸다.

Counter를 0으로 시작하면 CPU0 sentinel이 CPU1의 `rcu_barrier_func()` 시작 전에 GP를 지나 실행되어 counter를 0으로 만들 수 있다. Waiter가 즉시 반환하면 아직 CPU1 queue에 있던 old callback을 기다리지 못한다. 초기 여분 count 1은 모든 CPU에 sentinel을 게시하는 단계가 끝나기 전에 0이 되는 것을 막는다.

`on_each_cpu()`의 wait flag와 preemption disable도 보호를 제공한다. 각 cross-CPU 함수가 끝날 때까지 기다리고 호출 전체를 preemption-disabled region으로 감싸므로 최근 RCU에서는 첫 GP가 모든 sentinel 게시 전에 끝날 수 없다. 그러나 이 동작이 real-time latency 이유로 바뀔 수 있으므로 초기 count에 의존하는 명시적 방어가 더 견고하다.

현행 구현은 idle CPU를 깨우지 않고 real-time CPU 방해를 줄이기 위해 더 복잡하고 많은 최적화를 포함한다. 이 pseudo-code는 정확한 현재 코드가 아니라 queue ordering, sentinel, completion이라는 개념을 설명한다.

Quick Quiz #2:
        Why doesn't line 8 initialize rcu_barrier_cpu_count to zero,
        thereby avoiding the need for lines 9 and 10?

:ref:`Answer to Quick Quiz #2 <answer_rcubarrier_quiz_2>`

This code was rewritten in 2008 and several times thereafter, but this
still gives the general idea.

The rcu_barrier_func() runs on each CPU, where it invokes call_rcu()
to post an RCU callback, as follows::

  1  static void rcu_barrier_func(void *notused)
  2  {
  3    int cpu = smp_processor_id();
  4    struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
  5    struct rcu_head *head;
  6
  7    head = &rdp->barrier;
  8    atomic_inc(&rcu_barrier_cpu_count);
  9    call_rcu(head, rcu_barrier_callback);
 10  }

Lines 3 and 4 locate RCU's internal per-CPU rcu_data structure,
which contains the struct rcu_head that needed for the later call to
call_rcu(). Line 7 picks up a pointer to this struct rcu_head, and line
8 increments the global counter. This counter will later be decremented
by the callback. Line 9 then registers the rcu_barrier_callback() on
the current CPU's queue.

The rcu_barrier_callback() function simply atomically decrements the
rcu_barrier_cpu_count variable and finalizes the completion when it
reaches zero, as follows::

  1  static void rcu_barrier_callback(struct rcu_head *notused)
  2  {
  3    if (atomic_dec_and_test(&rcu_barrier_cpu_count))
  4      complete(&rcu_barrier_completion);
  5  }

.. _rcubarrier_quiz_3:

Quick Quiz #3:
        What happens if CPU 0's rcu_barrier_func() executes
        immediately (thus incrementing rcu_barrier_cpu_count to the
        value one), but the other CPU's rcu_barrier_func() invocations
        are delayed for a full grace period? Couldn't this result in
        rcu_barrier() returning prematurely?

:ref:`Answer to Quick Quiz #3 <answer_rcubarrier_quiz_3>`

The current rcu_barrier() implementation is more complex, due to the need
to avoid disturbing idle CPUs (especially on battery-powered systems)
and the need to minimally disturb non-idle CPUs in real-time systems.
In addition, a great many optimizations have been applied.  However,
the code above illustrates the concepts.

rcu_barrier() 요약

Core kernel 코드보다 unload 가능한 module에서 `rcu_barrier()`가 더 중요하다. Module이 RCU callback 함수를 제공한다면 unload 전에 새 callback을 차단하고 기존 callback을 모두 완료시켜야 한다.

Barrier 호출 빈도는 낮지만 누락 시 이미 unload된 text로 비동기 제어가 이동하므로 치명적이다. API 선택은 module이 실제로 사용한 RCU/SRCU flavor와 domain에 정확히 맞춘다.

rcu_barrier() Summary
---------------------

The rcu_barrier() primitive is used relatively infrequently, since most
code using RCU is in the core kernel rather than in modules. However, if
you are using RCU from an unloadable module, you need to use rcu_barrier()
so that your module may be safely unloaded.

Quick Quiz 해답

Quiz 1: `rcu_barrier()`는 처음 module unload용으로 만들어진 것이 아니다. Nikita Danilov가 filesystem에서 RCU를 사용하면서 unmount 시 callback 수명 문제가 생겼고 Dipankar Sarma가 이를 위해 구현했다. 이후 rcutorture module unload에도 같은 해법이 적용되었다.

Quiz 2: Counter를 0으로 시작하면 CPU0의 sentinel callback이 CPU1의 등록 전에 실행되어 completion을 너무 일찍 끝낼 수 있다. 2005년 당시 `on_each_cpu()`의 preemption disable이 GP를 막아 우연히 안전했고 v4.20 flavor 통합 뒤에도 nonpreemptible region을 기다리지만, 구현의 우연한 성질에 의존하면 미래 변경에서 bug가 된다.

Quiz 3: `on_each_cpu()`의 마지막 wait flag가 1이므로 `smp_call_function_on_cpu()`가 각 원격 호출 완료까지 spin한다. 또한 local과 remote 호출을 포함한 전체 구간에서 preemption을 disable해 RCU reader로 취급되므로 첫 sentinel callback은 모든 CPU가 `rcu_barrier_func()`를 실행하기 전에 실행될 수 없다.

향후 `on_each_cpu()`가 실시간 latency를 위해 preemption disable을 없애더라도 초기 count 1은 안전성을 유지한다. 이 예는 명시적 protocol이 현재 구현의 부수 효과보다 오래 살아남는 이유를 보여 준다.

Answers to Quick Quizzes
------------------------

.. _answer_rcubarrier_quiz_1:

Quick Quiz #1:
        Is there any other situation where rcu_barrier() might
        be required?

Answer:
        Interestingly enough, rcu_barrier() was not originally
        implemented for module unloading. Nikita Danilov was using
        RCU in a filesystem, which resulted in a similar situation at
        filesystem-unmount time. Dipankar Sarma coded up rcu_barrier()
        in response, so that Nikita could invoke it during the
        filesystem-unmount process.

        Much later, yours truly hit the RCU module-unload problem when
        implementing rcutorture, and found that rcu_barrier() solves
        this problem as well.

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

.. _answer_rcubarrier_quiz_2:

Quick Quiz #2:
        Why doesn't line 8 initialize rcu_barrier_cpu_count to zero,
        thereby avoiding the need for lines 9 and 10?

Answer:
        Suppose that the on_each_cpu() function shown on line 8 was
        delayed, so that CPU 0's rcu_barrier_func() executed and
        the corresponding grace period elapsed, all before CPU 1's
        rcu_barrier_func() started executing.  This would result in
        rcu_barrier_cpu_count being decremented to zero, so that line
        11's wait_for_completion() would return immediately, failing to
        wait for CPU 1's callbacks to be invoked.

        Note that this was not a problem when the rcu_barrier() code
        was first added back in 2005.  This is because on_each_cpu()
        disables preemption, which acted as an RCU read-side critical
        section, thus preventing CPU 0's grace period from completing
        until on_each_cpu() had dealt with all of the CPUs.

        However, with the RCU flavor consolidation around v4.20, this
        possibility was once again ruled out, because the consolidated
        RCU once again waits on nonpreemptible regions of code.

        Nevertheless, that extra count might still be a good idea.
        Relying on these sort of accidents of implementation can result
        in later surprise bugs when the implementation changes.

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

.. _answer_rcubarrier_quiz_3:

Quick Quiz #3:
        What happens if CPU 0's rcu_barrier_func() executes
        immediately (thus incrementing rcu_barrier_cpu_count to the
        value one), but the other CPU's rcu_barrier_func() invocations
        are delayed for a full grace period? Couldn't this result in
        rcu_barrier() returning prematurely?

Answer:
        This cannot happen. The reason is that on_each_cpu() has its last
        argument, the wait flag, set to "1". This flag is passed through
        to smp_call_function() and further to smp_call_function_on_cpu(),
        causing this latter to spin until the cross-CPU invocation of
        rcu_barrier_func() has completed. This by itself would prevent
        a grace period from completing on non-CONFIG_PREEMPTION kernels,
        since each CPU must undergo a context switch (or other quiescent
        state) before the grace period can complete. However, this is
        of no use in CONFIG_PREEMPTION kernels.

        Therefore, on_each_cpu() disables preemption across its call
        to smp_call_function() and also across the local call to
        rcu_barrier_func(). Because recent RCU implementations treat
        preemption-disabled regions of code as RCU read-side critical
        sections, this prevents grace periods from completing. This
        means that all CPUs have executed rcu_barrier_func() before
        the first rcu_barrier_callback() can possibly execute, in turn
        preventing rcu_barrier_cpu_count from prematurely reaching zero.

        But if on_each_cpu() ever decides to forgo disabling preemption,
        as might well happen due to real-time latency considerations,
        initializing rcu_barrier_cpu_count to one will save the day.

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