RCU 보호 원소의 참조 카운트 설계

잠금 기반 참조 카운트

RCU와 참조 카운트를 결합할 때는 먼저 `percpu-ref`를 검토하고 `include/linux/percpu-refcount.h`를 참고한다. 다만 percpu 참조가 메모리를 지나치게 소비하는 드문 경우에는 이 문서의 패턴을 사용할 수 있다.

전통적인 reader/writer spinlock이나 semaphore로 목록을 보호하면 참조 카운트는 단순하다. `add()`는 객체를 할당하고 `rc=1`로 초기화한 뒤 쓰기 잠금 아래 목록에 넣는다. `search_and_reference()`는 읽기 잠금 아래 항목을 찾아 `atomic_inc()`한다.

기존 참조를 놓는 `release_referenced()`와 목록에서 제거하는 `delete()`는 각각 `atomic_dec_and_test()` 결과가 참일 때 객체를 해제한다. 검색과 삭제가 같은 목록 잠금으로 직렬화되므로 이미 0이 된 객체의 참조를 독자가 되살릴 수 없다.

.. SPDX-License-Identifier: GPL-2.0

====================================================================
Reference-count design for elements of lists/arrays protected by RCU
====================================================================


Please note that the percpu-ref feature is likely your first
stop if you need to combine reference counts and RCU.  Please see
include/linux/percpu-refcount.h for more information.  However, in
those unusual cases where percpu-ref would consume too much memory,
please read on.

------------------------------------------------------------------------

Reference counting on elements of lists which are protected by traditional
reader/writer spinlocks or semaphores are straightforward:

CODE LISTING A::

    1.                                            2.
    add()                                    search_and_reference()
    {                                            {
        alloc_object                                read_lock(&list_lock);
        ...                                        search_for_element
        atomic_set(&el->rc, 1);                        atomic_inc(&el->rc);
        write_lock(&list_lock);                         ...
        add_element                                read_unlock(&list_lock);
        ...                                        ...
        write_unlock(&list_lock);           }
    }

    3.                                            4.
    release_referenced()                    delete()
    {                                            {
        ...                                        write_lock(&list_lock);
        if(atomic_dec_and_test(&el->rc))        ...
            kfree(el);
        ...                                        remove_element
    }                                                write_unlock(&list_lock);
                                                ...
                                                if (atomic_dec_and_test(&el->rc))
                                                    kfree(el);
                                                ...
                                            }

RCU 검색에서 0이 아닌 참조만 획득하기

목록을 RCU 읽기 방식으로 바꾸면 검색의 `atomic_inc()`가 이미 목록에서 삭제된 원소를 붙잡을 수 있다. 이 경우 코드 목록 B처럼 `atomic_inc_not_zero()`를 사용해야 한다. 카운터가 0이면 객체가 종료 단계이므로 RCU 읽기 잠금을 풀고 실패를 반환한다.

마지막 참조를 놓는 경로와 삭제 경로는 즉시 `kfree()`하는 대신 `call_rcu(&el->head, el_free)`를 예약한다. 이렇게 하면 삭제 전에 시작한 독자가 메모리에 접근하는 동안 객체가 물리적으로 해제되지 않는다.

갱신 측 spinlock을 이미 보유한 상태에서 참조를 얻는다면 삭제와 직렬화되어 있으므로 `atomic_inc_not_zero()`는 불필요하게 강할 수 있고 `atomic_inc()`를 사용할 수 있다. 다만 이 판단은 해당 갱신 잠금이 객체의 0 전환과 제거를 실제로 보호할 때만 유효하다.

If this list/array is made lock free using RCU as in changing the
write_lock() in add() and delete() to spin_lock() and changing read_lock()
in search_and_reference() to rcu_read_lock(), the atomic_inc() in
search_and_reference() could potentially hold reference to an element which
has already been deleted from the list/array.  Use atomic_inc_not_zero()
in this scenario as follows:

CODE LISTING B::

    1.                                            2.
    add()                                    search_and_reference()
    {                                            {
        alloc_object                                rcu_read_lock();
        ...                                        search_for_element
        atomic_set(&el->rc, 1);                        if (!atomic_inc_not_zero(&el->rc)) {
        spin_lock(&list_lock);                            rcu_read_unlock();
                                                    return FAIL;
        add_element                                }
        ...                                        ...
        spin_unlock(&list_lock);                rcu_read_unlock();
    }                                            }
    3.                                            4.
    release_referenced()                    delete()
    {                                            {
        ...                                        spin_lock(&list_lock);
        if (atomic_dec_and_test(&el->rc))        ...
            call_rcu(&el->head, el_free);        remove_element
        ...                                        spin_unlock(&list_lock);
    }                                                ...
                                                if (atomic_dec_and_test(&el->rc))
                                                    call_rcu(&el->head, el_free);
                                                ...
                                            }

Sometimes, a reference to the element needs to be obtained in the
update (write) stream.        In such cases, atomic_inc_not_zero() might be
overkill, since we hold the update-side spinlock.  One might instead
use atomic_inc() in such cases.

It is not always convenient to deal with "FAIL" in the
search_and_reference() code path.  In such cases, the
atomic_dec_and_test() may be moved from delete() to el_free()
as follows:

초기 참조를 grace period 뒤에 놓기

검색 경로에서 실패 처리가 불편하면 코드 목록 C를 사용할 수 있다. `add()`가 만든 초기 참조를 `delete()`에서 바로 놓지 않고, 목록 제거 뒤 예약한 `el_free()` callback이 grace period 이후 `release_referenced()`를 호출하도록 한다. 그러면 객체를 찾은 독자는 단순 `atomic_inc()`로 항상 참조를 얻을 수 있다.

핵심 불변식은 초기 참조가 목록 제거 뒤 grace period가 끝날 때까지 유지된다는 것이다. 이 기간이 끝나면 새 검색자는 더 이상 객체를 찾을 수 없고, 이후 참조 카운터는 증가할 수 없다. 따라서 카운터가 0에 도달했을 때 현재 또는 미래의 어떤 독자도 그 객체를 참조할 수 없으므로 안전하게 해제할 수 있다.

목록 C는 같은 객체의 `delete()`가 동시에 실행되어도 찾기에 성공한 모든 `search_and_reference()`가 참조 획득에 성공한다는 장점이 있다. 목록 B와 C는 검색자가 아무리 많아도 `delete()` 자체를 지연시키지 않고 최종 `kfree()`만 늦춘다.

`delete()`가 sleep할 수 있다면 `call_rcu()` callback 대신 제거 후 `synchronize_rcu()`를 호출하고 초기 참조를 직접 감소시킬 수 있다. 커널에서는 목록 C 패턴을 `struct pid` 참조 카운트에, 목록 B 패턴을 `struct posix_acl`에 사용한다.

CODE LISTING C::

    1.                                            2.
    add()                                    search_and_reference()
    {                                            {
        alloc_object                                rcu_read_lock();
        ...                                        search_for_element
        atomic_set(&el->rc, 1);                        atomic_inc(&el->rc);
        spin_lock(&list_lock);                        ...

        add_element                                rcu_read_unlock();
        ...                                    }
        spin_unlock(&list_lock);            4.
    }                                            delete()
    3.                                            {
    release_referenced()                        spin_lock(&list_lock);
    {                                                ...
        ...                                        remove_element
        if (atomic_dec_and_test(&el->rc))        spin_unlock(&list_lock);
            kfree(el);                                ...
        ...                                        call_rcu(&el->head, el_free);
    }                                                ...
    5.                                            }
    void el_free(struct rcu_head *rhp)
    {
        release_referenced();
    }

The key point is that the initial reference added by add() is not removed
until after a grace period has elapsed following removal.  This means that
search_and_reference() cannot find this element, which means that the value
of el->rc cannot increase.  Thus, once it reaches zero, there are no
readers that can or ever will be able to reference the element.         The
element can therefore safely be freed.        This in turn guarantees that if
any reader finds the element, that reader may safely acquire a reference
without checking the value of the reference counter.

A clear advantage of the RCU-based pattern in listing C over the one
in listing B is that any call to search_and_reference() that locates
a given object will succeed in obtaining a reference to that object,
even given a concurrent invocation of delete() for that same object.
Similarly, a clear advantage of both listings B and C over listing A is
that a call to delete() is not delayed even if there are an arbitrarily
large number of calls to search_and_reference() searching for the same
object that delete() was invoked on.  Instead, all that is delayed is
the eventual invocation of kfree(), which is usually not a problem on
modern computer systems, even the small ones.

In cases where delete() can sleep, synchronize_rcu() can be called from
delete(), so that el_free() can be subsumed into delete as follows::

    4.
    delete()
    {
        spin_lock(&list_lock);
        ...
        remove_element
        spin_unlock(&list_lock);
        ...
        synchronize_rcu();
        if (atomic_dec_and_test(&el->rc))
            kfree(el);
        ...
    }

As additional examples in the kernel, the pattern in listing C is used by
reference counting of struct pid, while the pattern in listing B is used by
struct posix_acl.