File management in the Linux kernel

기존 lock model과 RCU fdtable

이 문서는 file object인 `struct file`과 file descriptor table인 `struct files`의 locking을 설명합니다.

Linux 2.6.12까지 fd table은 `files->file_lock`과 `files->count`로 보호했습니다. `file_lock`은 table의 모든 file-related field 접근을 직렬화하고, `count`는 `CLONE_FILES`로 복제된 task, 보통 POSIX thread 사이의 table 공유를 추적했습니다. 마지막 task의 `put_files_struct()`가 fd table을 해제하며 각 `struct file` 자체는 `f_count` reference count로 보호됩니다.

새 lock-free fd management에서도 reference counting은 비슷하지만 locking은 RCU 기반입니다. fd set인 `open_fds`, `close_on_exec`, file pointer array, set·array size를 모두 별도 `struct fdtable`에 모아 lock-free reader에게 update 전체가 atomic하게 보이게 합니다.

`files_struct`는 `fdtable` pointer를 통해 실제 table에 접근합니다. 처음에는 fdtable이 `files_struct` 안에 embedded되어 있고, 확장 시 새 `fdtable`을 할당해 `files->fdtab`이 가리키게 합니다. 이전 structure는 RCU로 해제되므로 reader는 old 또는 new table 중 완전한 하나만 봅니다.

.. SPDX-License-Identifier: GPL-2.0

===================================
File management in the Linux kernel
===================================

This document describes how locking for files (struct file)
and file descriptor table (struct files) works.

Up until 2.6.12, the file descriptor table has been protected
with a lock (files->file_lock) and reference count (files->count).
->file_lock protected accesses to all the file related fields
of the table. ->count was used for sharing the file descriptor
table between tasks cloned with CLONE_FILES flag. Typically
this would be the case for posix threads. As with the common
refcounting model in the kernel, the last task doing
a put_files_struct() frees the file descriptor (fd) table.
The files (struct file) themselves are protected using
reference count (->f_count).

In the new lock-free model of file descriptor management,
the reference counting is similar, but the locking is
based on RCU. The file descriptor table contains multiple
elements - the fd sets (open_fds and close_on_exec, the
array of file pointers, the sizes of the sets and the array
etc.). In order for the updates to appear atomic to
a lock-free reader, all the elements of the file descriptor
table are in a separate structure - struct fdtable.
files_struct contains a pointer to struct fdtable through
which the actual fd table is accessed. Initially the
fdtable is embedded in files_struct itself. On a subsequent
expansion of fdtable, a new fdtable structure is allocated
and files->fdtab points to the new structure. The fdtable
structure is freed with RCU and lock-free readers either
see the old fdtable or the new fdtable making the update
appear atomic. Here are the locking rules for
the fdtable structure -

RCU read와 fd lookup 규칙 1~5

모든 fdtable reference는 `files_fdtable()` macro를 통해 얻어야 합니다. 이 macro는 lock-free dereference에 필요한 memory barrier를 처리하는 `rcu_dereference()`를 사용하므로 pointer read는 `rcu_read_lock()`과 `rcu_read_unlock()` 사이에서 해야 합니다.

struct fdtable *fdt;

rcu_read_lock();
fdt = files_fdtable(files);
...
rcu_read_unlock();

fd table을 읽을 때는 RCU read-side critical section이 필수이고, update할 때는 `files->file_lock`을 잡아야 합니다.

fd로 `struct file`을 찾는 reader는 `lookup_fdget_rcu()` 또는 `files_lookup_fdget_rcu()`를 사용해야 합니다. 두 API가 lock-free lookup에 필요한 barrier와 reference 획득을 처리합니다. 반환된 file은 사용 뒤 `fput(file)`로 놓습니다.

struct file *file;

rcu_read_lock();
file = lookup_fdget_rcu(fd);
rcu_read_unlock();
if (file) {
        ...
        fput(file);
}

fdtable과 file structure는 lock-free lookup 대상이므로 설치할 때 `rcu_assign_pointer()`, 직접 lookup할 때 `rcu_dereference()`를 써야 합니다. 실무에서는 세부 조건을 처리하는 `files_fdtable()`과 `lookup_fdget_rcu()` 계열을 사용하는 것이 권장됩니다.

1. All references to the fdtable must be done through
   the files_fdtable() macro::

        struct fdtable *fdt;

        rcu_read_lock();

        fdt = files_fdtable(files);
        ....
        if (n <= fdt->max_fds)
                ....
        ...
        rcu_read_unlock();

   files_fdtable() uses rcu_dereference() macro which takes care of
   the memory barrier requirements for lock-free dereference.
   The fdtable pointer must be read within the read-side
   critical section.

2. Reading of the fdtable as described above must be protected
   by rcu_read_lock()/rcu_read_unlock().

3. For any update to the fd table, files->file_lock must
   be held.

4. To look up the file structure given an fd, a reader
   must use either lookup_fdget_rcu() or files_lookup_fdget_rcu() APIs. These
   take care of barrier requirements due to lock-free lookup.

   An example::

        struct file *file;

        rcu_read_lock();
        file = lookup_fdget_rcu(fd);
        rcu_read_unlock();
        if (file) {
                ...
                fput(file);
        }
        ....

5. Since both fdtable and file structures can be looked up
   lock-free, they must be installed using rcu_assign_pointer()
   API. If they are looked up lock-free, rcu_dereference()
   must be used. However it is advisable to use files_fdtable()
   and lookup_fdget_rcu()/files_lookup_fdget_rcu() which take care of these
   issues.

Update 중 stale pointer와 object 재사용

fdtable을 update할 때 pointer는 `files->file_lock`을 잡은 상태에서 다시 얻어야 합니다. lock을 놓는 동안 다른 thread가 table을 확장하면 예전 pointer는 stale이 됩니다.

특히 `locate_fd()`는 `file_lock`을 놓았다가 다시 잡을 수 있으므로 호출 뒤에 `files_fdtable(files)`로 `fdt`를 다시 load한 다음 `__set_open_fd()`와 `__clear_close_on_exec()`를 수행해야 합니다.

spin_lock(&files->file_lock);
fd = locate_fd(files, file, start);
if (fd >= 0) {
        /* locate_fd() may have expanded fdtable, load the ptr */
        fdt = files_fdtable(files);
        __set_open_fd(fd, fdt);
        __clear_close_on_exec(fd, fdt);
        spin_unlock(&files->file_lock);
        ...
}

최신 kernel의 RCU file lookup은 `call_rcu()` 대신 `SLAB_TYPESAFE_BY_RCU`에 의존합니다. object가 이미 recycle되어 새 user가 reference를 올렸을 수 있으므로 RCU 안에서 `atomic_long_inc_not_zero()`만 성공했다고 원래 file reference를 얻었다고 볼 수 없습니다.

따라서 reference count를 올리기 전과 뒤의 pointer가 같은지 검증해야 합니다. 이 pattern은 `get_file_rcu()`와 `__files_get_rcu()`에서 볼 수 있습니다.

RCU lookup에서 reference를 먼저 획득하지 않고 `struct file` field에 접근하거나 검사할 수 없습니다. 예전에도 non-pointer data에만 간신히 적용할 수 있는 위험한 방식이었고, `SLAB_TYPESAFE_BY_RCU`에서는 caller가 reference를 먼저 얻거나 fdtable의 `files_lock`을 보유해야 합니다.

6. While updating, the fdtable pointer must be looked up while
   holding files->file_lock. If ->file_lock is dropped, then
   another thread expand the files thereby creating a new
   fdtable and making the earlier fdtable pointer stale.

   For example::

        spin_lock(&files->file_lock);
        fd = locate_fd(files, file, start);
        if (fd >= 0) {
                /* locate_fd() may have expanded fdtable, load the ptr */
                fdt = files_fdtable(files);
                __set_open_fd(fd, fdt);
                __clear_close_on_exec(fd, fdt);
                spin_unlock(&files->file_lock);
        .....

   Since locate_fd() can drop ->file_lock (and reacquire ->file_lock),
   the fdtable pointer (fdt) must be loaded after locate_fd().

On newer kernels rcu based file lookup has been switched to rely on
SLAB_TYPESAFE_BY_RCU instead of call_rcu(). It isn't sufficient anymore
to just acquire a reference to the file in question under rcu using
atomic_long_inc_not_zero() since the file might have already been
recycled and someone else might have bumped the reference. In other
words, callers might see reference count bumps from newer users. For
this is reason it is necessary to verify that the pointer is the same
before and after the reference count increment. This pattern can be seen
in get_file_rcu() and __files_get_rcu().

In addition, it isn't possible to access or check fields in struct file
without first acquiring a reference on it under rcu lookup. Not doing
that was always very dodgy and it was only usable for non-pointer data
in struct file. With SLAB_TYPESAFE_BY_RCU it is necessary that callers
either first acquire a reference or they must hold the files_lock of the
fdtable.