Process Addresses

Process address space와 VMA model

Kernel은 userspace memory range를 `struct vm_area_struct` 유형의 Virtual Memory Area, 즉 VMA로 추적합니다.

각 VMA object는 attribute가 동일한 virtual-contiguous memory range 하나를 설명합니다. 인접한 stack VMA를 accessed address까지 확장할 수 있는 경우를 제외하면, VMA 밖의 userspace access는 invalid입니다.

모든 VMA는 정확히 하나의 virtual-address space에 속합니다. 이 address space는 `struct mm_struct` object가 설명하며, 같은 virtual-address space를 공유하는 모든 task, 즉 thread가 이를 참조합니다. 문서에서는 이 object를 `mm`이라고 부릅니다.

각 `mm` object는 virtual-address space 안의 모든 VMA를 설명하는 maple-tree 자료 구조를 포함합니다.

예외는 `vsyscall`을 사용하는 architecture가 제공하는 `gate` VMA입니다. 이는 특정 `mm`에 속하지 않는 global static object입니다.

.. SPDX-License-Identifier: GPL-2.0

=================
Process Addresses
=================

.. toctree::
   :maxdepth: 3


Userland memory ranges are tracked by the kernel via Virtual Memory Areas or
'VMA's of type :c:struct:`!struct vm_area_struct`.

Each VMA describes a virtually contiguous memory range with identical
attributes, each described by a :c:struct:`!struct vm_area_struct`
object. Userland access outside of VMAs is invalid except in the case where an
adjacent stack VMA could be extended to contain the accessed address.

All VMAs are contained within one and only one virtual address space, described
by a :c:struct:`!struct mm_struct` object which is referenced by all tasks (that is,
threads) which share the virtual address space. We refer to this as the
:c:struct:`!mm`.

Each mm object contains a maple tree data structure which describes all VMAs
within the virtual address space.

.. note:: An exception to this is the 'gate' VMA which is provided by
          architectures which use :c:struct:`!vsyscall` and is a global static
          object which does not belong to any specific mm.

VMA metadata lock 용어

Kernel은 VMA metadata에 대한 concurrent read operation이 잘 확장되도록 설계됐습니다. Memory corruption을 막기 위해 복잡한 lock set이 필요합니다. VMA metadata를 lock해도 VMA가 설명하는 memory나 이를 mapping하는 page table에는 영향을 주지 않습니다.

• `mmap lock`: 각 MM의 process-address-space 단위 read/write semaphore인 `mmap_lock`입니다. `mmap_read_lock`, `mmap_write_lock`과 variant로 획득합니다.
• `VMA lock`: VMA 단위이며 실제로 read/write semaphore처럼 동작합니다. Read lock은 `lock_vma_under_rcu`로 얻고 `vma_end_read`로 놓습니다. Write lock은 `vma_start_write`로 얻으며 mmap write lock을 놓을 때 모든 VMA write lock이 자동 해제됩니다. VMA write lock을 얻기 전에 반드시 `mmap_write_lock`을 획득해야 합니다.
• `rmap lock`: Folio의 `folio->mapping`에서 도달할 수 있는 `struct address_space` 또는 `struct anon_vma`를 통해 reverse mapping으로 VMA에 접근할 때 사용합니다. Anonymous memory는 `anon_vma_[try]lock_read/write`, file-backed memory는 `i_mmap_[try]lock_read/write`로 VMA를 안정화합니다.

Page-table lock은 뒤의 전용 section에서 별도로 설명합니다.

이 lock들이 가장 먼저 보장하는 것은 MM tree 안에서 VMA를 안정화하는 것입니다. 즉 VMA object가 접근 중 삭제되거나 아래에서 설명하는 일부 field를 제외하고 수정되지 않음을 보장합니다. VMA 안정화는 그 VMA가 설명하는 address space도 계속 존재하게 합니다.

-------
Locking
-------

The kernel is designed to be highly scalable against concurrent read operations
on VMA **metadata** so a complicated set of locks are required to ensure memory
corruption does not occur.

.. note:: Locking VMAs for their metadata does not have any impact on the memory
          they describe nor the page tables that map them.

Terminology
-----------

* **mmap locks** - Each MM has a read/write semaphore :c:member:`!mmap_lock`
  which locks at a process address space granularity which can be acquired via
  :c:func:`!mmap_read_lock`, :c:func:`!mmap_write_lock` and variants.
* **VMA locks** - The VMA lock is at VMA granularity (of course) which behaves
  as a read/write semaphore in practice. A VMA read lock is obtained via
  :c:func:`!lock_vma_under_rcu` (and unlocked via :c:func:`!vma_end_read`) and a
  write lock via :c:func:`!vma_start_write` (all VMA write locks are unlocked
  automatically when the mmap write lock is released). To take a VMA write lock
  you **must** have already acquired an :c:func:`!mmap_write_lock`.
* **rmap locks** - When trying to access VMAs through the reverse mapping via a
  :c:struct:`!struct address_space` or :c:struct:`!struct anon_vma` object
  (reachable from a folio via :c:member:`!folio->mapping`). VMAs must be stabilised via
  :c:func:`!anon_vma_[try]lock_read` or :c:func:`!anon_vma_[try]lock_write` for
  anonymous memory and :c:func:`!i_mmap_[try]lock_read` or
  :c:func:`!i_mmap_[try]lock_write` for file-backed memory. We refer to these
  locks as the reverse mapping locks, or 'rmap locks' for brevity.

We discuss page table locks separately in the dedicated section below.

The first thing **any** of these locks achieve is to **stabilise** the VMA
within the MM tree. That is, guaranteeing that the VMA object will not be
deleted from under you nor modified (except for some specific fields
described below).

Stabilising a VMA also keeps the address space described by it around.

Read·write lock 사용과 유효 상태

VMA metadata를 읽거나 VMA를 stable하게 유지하려면 다음 중 하나를 수행합니다.

• `mmap_read_lock` 또는 알맞은 variant로 MM 단위 mmap read lock을 얻고, 작업 후 대응하는 `mmap_read_unlock`으로 놓습니다.
• `lock_vma_under_rcu`로 VMA read lock을 시도합니다. Atomic하게 획득하므로 실패할 수 있습니다. `NULL`을 반환하면 fallback logic으로 mmap read lock을 얻어야 합니다.
• Anonymous 또는 file-backed locked interval tree를 순회하기 전에 rmap lock을 얻고 필요한 VMA를 찾습니다.

VMA metadata 대부분을 write하려면 다음 lock을 함께 사용합니다.

• `mmap_write_lock` 또는 variant로 MM 단위 mmap write lock을 얻고 작업 후 `mmap_write_unlock`으로 놓습니다.
• 수정할 각 VMA에 `vma_start_write`를 호출해 VMA write lock을 얻습니다. `mmap_write_unlock` 때 자동 해제됩니다.
• 어떤 field든 제한 없이 write하려면 rmap write lock을 얻어 reverse mapping에서 VMA를 숨겨야 합니다.

VMA write lock을 얻으려면 mmap write lock을 먼저 얻어야 합니다. 반면 VMA read lock은 다른 lock 없이 얻을 수 있습니다. `lock_vma_under_rcu`가 VMA lookup을 위해 RCU lock을 얻었다가 놓습니다. 이 방식은 writer가 한 VMA를 다루는 동안 reader가 다른 VMA를 동시에 다룰 수 있게 해 writer의 영향을 제한합니다.

VMA read lock의 주 사용자는 page-fault handler입니다. 따라서 VMA write lock이 없으면 수행 중인 작업과 page fault가 동시에 실행될 수 있습니다.

유효 lock-state 표의 의미는 다음과 같습니다. Lock이 전혀 없으면 stable·read·write 모두 불가능합니다. VMA read 또는 rmap read/write만 있어도 stable과 read가 가능합니다. Mmap read/write가 있으면 VMA와 rmap lock 조합에 관계없이 stable과 read가 가능합니다. Mmap write와 VMA write가 있으면 대부분 field를 write할 수 있고, rmap write까지 있으면 모든 field를 write할 수 있습니다.

Mmap read lock을 가진 채 VMA lock을 얻을 수는 있지만, 반대로 VMA read lock을 가진 채 mmap lock을 얻으려 하면 deadlock이 생길 수 있어 invalid입니다. 다른 task가 mmap write lock을 가진 상태에서 VMA write lock을 기다리면 현재 VMA read lock과 서로 막힐 수 있습니다.

세 lock은 실제로 read/write semaphore처럼 동작합니다. 여러 reader는 concurrent하지만 writer는 모든 reader가 critical region을 떠날 때까지 기다리며 pending reader도 대기시킵니다. 따라서 read lock끼리는 concurrent이고 write lock은 다른 모든 holder에 대해 exclusive입니다.

Lock usage
----------

If you want to **read** VMA metadata fields or just keep the VMA stable, you
must do one of the following:

* Obtain an mmap read lock at the MM granularity via :c:func:`!mmap_read_lock` (or a
  suitable variant), unlocking it with a matching :c:func:`!mmap_read_unlock` when
  you're done with the VMA, *or*
* Try to obtain a VMA read lock via :c:func:`!lock_vma_under_rcu`. This tries to
  acquire the lock atomically so might fail, in which case fall-back logic is
  required to instead obtain an mmap read lock if this returns :c:macro:`!NULL`,
  *or*
* Acquire an rmap lock before traversing the locked interval tree (whether
  anonymous or file-backed) to obtain the required VMA.

If you want to **write** VMA metadata fields, then things vary depending on the
field (we explore each VMA field in detail below). For the majority you must:

* Obtain an mmap write lock at the MM granularity via :c:func:`!mmap_write_lock` (or a
  suitable variant), unlocking it with a matching :c:func:`!mmap_write_unlock` when
  you're done with the VMA, *and*
* Obtain a VMA write lock via :c:func:`!vma_start_write` for each VMA you wish to
  modify, which will be released automatically when :c:func:`!mmap_write_unlock` is
  called.
* If you want to be able to write to **any** field, you must also hide the VMA
  from the reverse mapping by obtaining an **rmap write lock**.

VMA locks are special in that you must obtain an mmap **write** lock **first**
in order to obtain a VMA **write** lock. A VMA **read** lock however can be
obtained without any other lock (:c:func:`!lock_vma_under_rcu` will acquire then
release an RCU lock to lookup the VMA for you).

This constrains the impact of writers on readers, as a writer can interact with
one VMA while a reader interacts with another simultaneously.

.. note:: The primary users of VMA read locks are page fault handlers, which
          means that without a VMA write lock, page faults will run concurrent with
          whatever you are doing.

Examining all valid lock states:

.. table::

   ========= ======== ========= ======= ===== =========== ==========
   mmap lock VMA lock rmap lock Stable? Read? Write most? Write all?
   ========= ======== ========= ======= ===== =========== ==========
   \-        \-       \-        N       N     N           N
   \-        R        \-        Y       Y     N           N
   \-        \-       R/W       Y       Y     N           N
   R/W       \-/R     \-/R/W    Y       Y     N           N
   W         W        \-/R      Y       Y     Y           N
   W         W        W         Y       Y     Y           Y
   ========= ======== ========= ======= ===== =========== ==========

.. warning:: While it's possible to obtain a VMA lock while holding an mmap read lock,
             attempting to do the reverse is invalid as it can result in deadlock - if
             another task already holds an mmap write lock and attempts to acquire a VMA
             write lock that will deadlock on the VMA read lock.

All of these locks behave as read/write semaphores in practice, so you can
obtain either a read or a write lock for each of these.

.. note:: Generally speaking, a read/write semaphore is a class of lock which
          permits concurrent readers. However a write lock can only be obtained
          once all readers have left the critical region (and pending readers
          made to wait).

          This renders read locks on a read/write semaphore concurrent with other
          readers and write locks exclusive against all others holding the semaphore.

VMA field와 write-lock 요구

`struct vm_area_struct` field를 목적별로 나누면 locking 특성을 이해하기 쉽습니다. 내부 구현 detail인 VMA-lock 전용 field는 제외합니다.

Virtual-layout field는 다음과 같습니다.

• `vm_start`: VMA range의 inclusive 시작 virtual address입니다. Write에는 mmap write, VMA write, rmap write가 모두 필요합니다.
• `vm_end`: VMA range의 exclusive 끝 virtual address입니다. Write에는 mmap write, VMA write, rmap write가 모두 필요합니다.
• `vm_pgoff`: File 안의 page offset, `mremap` 전 virtual-address space의 original page offset, 또는 PFN map이면서 architecture가 `CONFIG_ARCH_HAS_PTE_SPECIAL`을 지원하지 않을 때 PFN을 설명합니다. Write에는 mmap write, VMA write, rmap write가 모두 필요합니다.

이 field는 VMA의 크기·시작·끝을 나타내며 reverse-mapping interval tree에서 VMA를 찾는 데 사용됩니다. 따라서 reverse mapping에서 VMA를 숨기기 전에는 수정할 수 없습니다.

Core field는 다음과 같습니다.

• `vm_mm`: VMA를 포함하는 `mm_struct`입니다. Initial map 때 한 번만 쓰므로 별도 write lock이 없습니다.
• `vm_page_prot`: VMA flag에서 결정된 architecture-specific page-table protection bit입니다. Mmap write와 VMA write가 필요합니다.
• `vm_flags`: VMA attribute를 설명하는 read-only VMA flag access이며 private writable `__vm_flags`와 union입니다. 직접 write 대상이 아닙니다.
• `__vm_flags`: Private writable VMA-flag field이며 `vm_flags_*` 함수로 갱신합니다. Mmap write와 VMA write가 필요합니다.
• `vm_file`: File-backed VMA이면 underlying file을 설명하는 `struct file` pointer이고 anonymous이면 `NULL`입니다. Initial map 때 한 번만 씁니다.
• `vm_ops`: File-backed VMA에서 driver 또는 filesystem이 VMA-lifetime event callback을 설명하는 `struct vm_operations_struct`를 제공합니다. Initial map 때 `f_ops->mmap()`이 한 번 씁니다.
• `vm_private_data`: Driver-specific metadata용 `void *` field이며 driver가 locking을 처리합니다.

Kernel config에 따라 존재하는 field는 다음과 같습니다.

• `anon_name` (`CONFIG_ANON_VMA_NAME`): Anonymous mapping 이름을 제공하는 reference-counted `struct anon_vma_name`입니다. 이름이 없거나 file-backed이면 `NULL`이며 확장성을 위해 여러 VMA가 공유할 수 있습니다. Mmap write와 VMA write가 필요합니다.
• `swap_readahead_info` (`CONFIG_SWAP`): Swap readahead용 metadata이며 atomic하게 접근합니다. Mmap read와 swap-specific lock이 필요합니다.
• `vm_policy` (`CONFIG_NUMA`): VMA의 NUMA behavior를 설명하는 reference-counted `mempolicy`입니다. Mmap write와 VMA write가 필요합니다.
• `numab_state` (`CONFIG_NUMA_BALANCING`): 이 VMA와 관련된 현재 NUMA-balancing state를 설명하는 `vma_numab_state`입니다. `task_numa_work`가 mmap read lock 아래에서 갱신하며 mmap read와 numab-specific lock을 사용합니다.
• `vm_userfaultfd_ctx` (`CONFIG_USERFAULTFD`): `vm_userfaultfd_ctx` wrapper입니다. Userfaultfd가 disable되면 크기 0이고, enable되면 metadata를 설명하는 underlying `userfaultfd_ctx` pointer를 담습니다. Mmap write와 VMA write가 필요합니다.

Reverse-mapping field는 다음과 같습니다.

• `shared.rb`: File-backed mapping이면 VMA를 `struct address_space->i_mmap` red/black interval tree에 넣는 red/black-tree node입니다. Mmap write, VMA write, i_mmap write가 필요합니다.
• `shared.rb_subtree_last`: File-backed VMA interval-tree 관리 metadata입니다. Mmap write, VMA write, i_mmap write가 필요합니다.
• `anon_vma_chain`: Fork·CoW된 `anon_vma` object와 non-NULL인 `vma->anon_vma`를 모두 가리키는 pointer list입니다. Mmap read와 anon_vma write가 필요합니다.
• `anon_vma`: 이 VMA에 exclusive하게 mapping된 anonymous folio가 속할 `anon_vma`입니다. Page 하나라도 fault-in되면 set됩니다. 처음에는 `anon_vma_prepare`가 `page_table_lock`으로 serialize해 설정합니다. NULL에서 non-NULL로 바꿀 때는 mmap read와 page-table lock, non-NULL에서 NULL로 바꿀 때는 mmap write·VMA write·anon_vma write가 필요합니다.

이 field들은 VMA를 reverse mapping에 배치하고, anonymous mapping에서 관련 `anon_vma`와 exclusive folio용 `anon_vma`에 접근하는 데 사용합니다. File-backed mapping에 `MAP_PRIVATE`가 set되면 `anon_vma`와 `i_mmap` tree에 동시에 들어갈 수 있어 모든 reverse-mapping field를 한꺼번에 사용할 수 있습니다.

VMA fields
^^^^^^^^^^

We can subdivide :c:struct:`!struct vm_area_struct` fields by their purpose, which makes it
easier to explore their locking characteristics:

.. note:: We exclude VMA lock-specific fields here to avoid confusion, as these
          are in effect an internal implementation detail.

.. table:: Virtual layout fields

   ===================== ======================================== ===========
   Field                 Description                              Write lock
   ===================== ======================================== ===========
   :c:member:`!vm_start` Inclusive start virtual address of range mmap write,
                         VMA describes.                           VMA write,
                                                                  rmap write.
   :c:member:`!vm_end`   Exclusive end virtual address of range   mmap write,
                         VMA describes.                           VMA write,
                                                                  rmap write.
   :c:member:`!vm_pgoff` Describes the page offset into the file, mmap write,
                         the original page offset within the      VMA write,
                         virtual address space (prior to any      rmap write.
                         :c:func:`!mremap`), or PFN if a PFN map
                         and the architecture does not support
                         :c:macro:`!CONFIG_ARCH_HAS_PTE_SPECIAL`.
   ===================== ======================================== ===========

These fields describes the size, start and end of the VMA, and as such cannot be
modified without first being hidden from the reverse mapping since these fields
are used to locate VMAs within the reverse mapping interval trees.

.. table:: Core fields

   ============================ ======================================== =========================
   Field                        Description                              Write lock
   ============================ ======================================== =========================
   :c:member:`!vm_mm`           Containing mm_struct.                    None - written once on
                                                                         initial map.
   :c:member:`!vm_page_prot`    Architecture-specific page table         mmap write, VMA write.
                                protection bits determined from VMA
                                flags.
   :c:member:`!vm_flags`        Read-only access to VMA flags describing N/A
                                attributes of the VMA, in union with
                                private writable
                                :c:member:`!__vm_flags`.
   :c:member:`!__vm_flags`      Private, writable access to VMA flags    mmap write, VMA write.
                                field, updated by
                                :c:func:`!vm_flags_*` functions.
   :c:member:`!vm_file`         If the VMA is file-backed, points to a   None - written once on
                                struct file object describing the        initial map.
                                underlying file, if anonymous then
                                :c:macro:`!NULL`.
   :c:member:`!vm_ops`          If the VMA is file-backed, then either   None - Written once on
                                the driver or file-system provides a     initial map by
                                :c:struct:`!struct vm_operations_struct` :c:func:`!f_ops->mmap()`.
                                object describing callbacks to be
                                invoked on VMA lifetime events.
   :c:member:`!vm_private_data` A :c:member:`!void *` field for          Handled by driver.
                                driver-specific metadata.
   ============================ ======================================== =========================

These are the core fields which describe the MM the VMA belongs to and its attributes.

.. table:: Config-specific fields

   ================================= ===================== ======================================== ===============
   Field                             Configuration option  Description                              Write lock
   ================================= ===================== ======================================== ===============
   :c:member:`!anon_name`            CONFIG_ANON_VMA_NAME  A field for storing a                    mmap write,
                                                           :c:struct:`!struct anon_vma_name`        VMA write.
                                                           object providing a name for anonymous
                                                           mappings, or :c:macro:`!NULL` if none
                                                           is set or the VMA is file-backed. The
                                                           underlying object is reference counted
                                                           and can be shared across multiple VMAs
                                                           for scalability.
   :c:member:`!swap_readahead_info`  CONFIG_SWAP           Metadata used by the swap mechanism      mmap read,
                                                           to perform readahead. This field is      swap-specific
                                                           accessed atomically.                     lock.
   :c:member:`!vm_policy`            CONFIG_NUMA           :c:type:`!mempolicy` object which        mmap write,
                                                           describes the NUMA behaviour of the      VMA write.
                                                           VMA. The underlying object is reference
                                                           counted.
   :c:member:`!numab_state`          CONFIG_NUMA_BALANCING :c:type:`!vma_numab_state` object which  mmap read,
                                                           describes the current state of           numab-specific
                                                           NUMA balancing in relation to this VMA.  lock.
                                                           Updated under mmap read lock by
                                                           :c:func:`!task_numa_work`.
   :c:member:`!vm_userfaultfd_ctx`   CONFIG_USERFAULTFD    Userfaultfd context wrapper object of    mmap write,
                                                           type :c:type:`!vm_userfaultfd_ctx`,      VMA write.
                                                           either of zero size if userfaultfd is
                                                           disabled, or containing a pointer
                                                           to an underlying
                                                           :c:type:`!userfaultfd_ctx` object which
                                                           describes userfaultfd metadata.
   ================================= ===================== ======================================== ===============

These fields are present or not depending on whether the relevant kernel
configuration option is set.

.. table:: Reverse mapping fields

   =================================== ========================================= ============================
   Field                               Description                               Write lock
   =================================== ========================================= ============================
   :c:member:`!shared.rb`              A red/black tree node used, if the        mmap write, VMA write,
                                       mapping is file-backed, to place the VMA  i_mmap write.
                                       in the
                                       :c:member:`!struct address_space->i_mmap`
                                       red/black interval tree.
   :c:member:`!shared.rb_subtree_last` Metadata used for management of the       mmap write, VMA write,
                                       interval tree if the VMA is file-backed.  i_mmap write.
   :c:member:`!anon_vma_chain`         List of pointers to both forked/CoW’d     mmap read, anon_vma write.
                                       :c:type:`!anon_vma` objects and
                                       :c:member:`!vma->anon_vma` if it is
                                       non-:c:macro:`!NULL`.
   :c:member:`!anon_vma`               :c:type:`!anon_vma` object used by        When :c:macro:`NULL` and
                                       anonymous folios mapped exclusively to    setting non-:c:macro:`NULL`:
                                       this VMA. Initially set by                mmap read, page_table_lock.
                                       :c:func:`!anon_vma_prepare` serialised
                                       by the :c:macro:`!page_table_lock`. This  When non-:c:macro:`NULL` and
                                       is set as soon as any page is faulted in. setting :c:macro:`NULL`:
                                                                                 mmap write, VMA write,
                                                                                 anon_vma write.
   =================================== ========================================= ============================

These fields are used to both place the VMA within the reverse mapping, and for
anonymous mappings, to be able to access both related :c:struct:`!struct anon_vma` objects
and the :c:struct:`!struct anon_vma` in which folios mapped exclusively to this VMA should
reside.

.. note:: If a file-backed mapping is mapped with :c:macro:`!MAP_PRIVATE` set
          then it can be in both the :c:type:`!anon_vma` and :c:type:`!i_mmap`
          trees at the same time, so all of these fields might be utilised at
          once.

Page-table model과 네 가지 operation

Page table은 여러 단계 table을 통해 virtual address를 physical address에 mapping합니다. 각 non-leaf entry는 flag와 함께 다음 level table의 physical address를 담습니다. Leaf entry는 physical data page 주소 또는 swap entry, migration entry, 그 밖의 special marker를 담습니다. 각 page 안의 offset은 virtual address 자체가 제공합니다.

Linux는 PGD, P4D, PUD, PMD, PTE의 5단계로 나눕니다. Huge page가 한두 단계를 없앨 수 있지만 그 경우에도 보통 leaf level을 PTE level이라고 부릅니다. 5단계보다 적은 architecture에서는 빠진 level의 함수를 stub 처리하는 `folding`으로 항상 5단계인 것처럼 다룹니다. Compiler는 실제로 없는 단계의 code를 제거할 수 있습니다.

• `Traversing`: Page table을 읽어 순회합니다. VMA를 stable하게 유지하는 lock 하나면 충분합니다. `gup_fast`처럼 이 요구도 없애는 lockless variant가 있습니다. Non-VMA 영역은 별도로 다룹니다.
• `Installing`: 새 mapping을 만들거나 기존 mapping의 identity를 바꾸는 수정입니다. Rmap lock이 아니라 mmap 또는 VMA lock으로 VMA를 stable하게 유지해야 합니다.
• `Zapping/unmapping`: Page table 자체는 남기고 leaf mapping만 clear합니다. File truncation, `madvise`의 `MADV_DONTNEED` 등에 흔히 사용하며 `unmap_mapping_range`, `unmap_mapping_pages` 등이 수행합니다. VMA를 stable하게만 유지하면 됩니다.
• `Freeing`: 보통 `free_pgtables`로 userspace process에서 page table 자체를 제거합니다. Range를 이미 zap했고 추가 fault나 수정이 없도록 막았다고 가정한 채 existing leaf entry를 무시하고 모든 table을 free하므로 매우 조심해야 합니다.

Reclaim 또는 migration을 위한 mapping 수정은 mapping identity를 근본적으로 바꾸지 않으므로 zapping처럼 rmap lock 아래에서 수행합니다.

Traversal과 zapping은 mmap, VMA, rmap lock 중 하나로 VMA를 stable하게 유지하면 수행할 수 있습니다. Write를 수행하는 내부 kernel operation은 serialize를 위해 page-table lock도 얻습니다. Zap 중 빈 PTE table은 RCU 아래에서 free하지만 이 사실은 zapping의 앞선 lock 요구를 바꾸지 않습니다.

Entry installation에는 mmap 또는 VMA lock이 필요합니다. Page-table freeing은 특수한 internal operation입니다. Free하려는 table이 mapping하는 range를 포함하는 VMA에 reverse mapping으로 접근할 수 없어야 합니다. `free_pgtables`가 관련 VMA를 rmap에서 제거하지만, 다른 접근 가능한 VMA가 해당 range와 겹쳐서도 안 됩니다.

Page tables
-----------

We won't speak exhaustively on the subject but broadly speaking, page tables map
virtual addresses to physical ones through a series of page tables, each of
which contain entries with physical addresses for the next page table level
(along with flags), and at the leaf level the physical addresses of the
underlying physical data pages or a special entry such as a swap entry,
migration entry or other special marker. Offsets into these pages are provided
by the virtual address itself.

In Linux these are divided into five levels - PGD, P4D, PUD, PMD and PTE. Huge
pages might eliminate one or two of these levels, but when this is the case we
typically refer to the leaf level as the PTE level regardless.

.. note:: In instances where the architecture supports fewer page tables than
          five the kernel cleverly 'folds' page table levels, that is stubbing
          out functions related to the skipped levels. This allows us to
          conceptually act as if there were always five levels, even if the
          compiler might, in practice, eliminate any code relating to missing
          ones.

There are four key operations typically performed on page tables:

1. **Traversing** page tables - Simply reading page tables in order to traverse
   them. This only requires that the VMA is kept stable, so a lock which
   establishes this suffices for traversal (there are also lockless variants
   which eliminate even this requirement, such as :c:func:`!gup_fast`). There is
   also a special case of page table traversal for non-VMA regions which we
   consider separately below.
2. **Installing** page table mappings - Whether creating a new mapping or
   modifying an existing one in such a way as to change its identity. This
   requires that the VMA is kept stable via an mmap or VMA lock (explicitly not
   rmap locks).
3. **Zapping/unmapping** page table entries - This is what the kernel calls
   clearing page table mappings at the leaf level only, whilst leaving all page
   tables in place. This is a very common operation in the kernel performed on
   file truncation, the :c:macro:`!MADV_DONTNEED` operation via
   :c:func:`!madvise`, and others. This is performed by a number of functions
   including :c:func:`!unmap_mapping_range` and :c:func:`!unmap_mapping_pages`.
   The VMA need only be kept stable for this operation.
4. **Freeing** page tables - When finally the kernel removes page tables from a
   userland process (typically via :c:func:`!free_pgtables`) extreme care must
   be taken to ensure this is done safely, as this logic finally frees all page
   tables in the specified range, ignoring existing leaf entries (it assumes the
   caller has both zapped the range and prevented any further faults or
   modifications within it).

.. note:: Modifying mappings for reclaim or migration is performed under rmap
          lock as it, like zapping, does not fundamentally modify the identity
          of what is being mapped.

**Traversing** and **zapping** ranges can be performed holding any one of the
locks described in the terminology section above - that is the mmap lock, the
VMA lock or either of the reverse mapping locks.

That is - as long as you keep the relevant VMA **stable** - you are good to go
ahead and perform these operations on page tables (though internally, kernel
operations that perform writes also acquire internal page table locks to
serialise - see the page table implementation detail section for more details).

.. note:: We free empty PTE tables on zap under the RCU lock - this does not
          change the aforementioned locking requirements around zapping.

When **installing** page table entries, the mmap or VMA lock must be held to
keep the VMA stable. We explore why this is in the page table locking details
section below.

**Freeing** page tables is an entirely internal memory management operation and
has special requirements (see the page freeing section below for more details).

.. warning:: When **freeing** page tables, it must not be possible for VMAs
             containing the ranges those page tables map to be accessible via
             the reverse mapping.

             The :c:func:`!free_pgtables` function removes the relevant VMAs
             from the reverse mappings, but no other VMAs can be permitted to be
             accessible and span the specified range.

Non-VMA traversal과 lock ordering

VMA가 나타내지 않는 page table도 순회할 수 있습니다. Kernel page-table mapping은 이를 만든 subsystem이 자체 lock으로 관리하므로 앞의 VMA lock 규칙이 적용되지 않습니다. 예를 들어 vmalloc은 page table 생성과 해제에 자체 lock set을 사용합니다.

편의를 위해 `walk_kernel_page_table_range`를 제공하며, kernel `mm_struct` instance인 `init_mm`의 mmap lock으로 synchronize합니다. Exclusive access가 필요하면 write lock을, 아니면 read lock을 사용하며 최소 read lock 획득을 assert합니다. Vmalloc과 memory hotplug 외에는 kernel page table을 자주 해제하지 않으므로 대체로 충분하지만 caller가 필요한 추가 lock을 미리 얻어야 합니다.

`walk_page_range_debug`는 userspace range의 non-VMA 영역을 순회하는 매우 이례적인 경우를 지원합니다. 유일한 사용자는 `mm/ptdump.c`의 일반 page-table dump logic으로, architecture-specific일 수 있고 VMA backing이 없는 mapping까지 debug 목적으로 노출합니다.

`munmap`은 mmap write lock 아래에서 VMA를 detach한 뒤 downgraded mmap read lock 아래에서 page table을 해제합니다. Debug traversal이 이 과정과 race할 수 있으므로 mmap write lock이 필요합니다.

여러 lock을 함께 쓸 수 있어 lock inversion을 피하려면 획득·해제 순서가 중요합니다. Thread 1이 A를 들고 B를 기다리는 동안 thread 2가 B를 들고 A를 기다리면 mutual deadlock입니다. 같은 순서로 lock을 얻었다면 한쪽이 다른 쪽 완료를 기다려 deadlock을 피할 수 있습니다.

`mm/rmap.c`가 제시하는 주 lock-order chain은 다음 순서입니다.

inode->i_rwsem
  mm->mmap_lock
    mapping->invalidate_lock
      folio_lock
        hugetlbfs_i_mmap_rwsem_key
          vma_start_write
            mapping->i_mmap_rwsem
              anon_vma->rwsem
                mm->page_table_lock or pte_lock
                  swap_lock
                    mmlist_lock / mapping->private_lock / inode->i_lock / bdi.wb->list_lock
                      i_pages lock / sb_lock / lruvec->lru_lock

`mm/filemap.c`에는 filesystem-specific lock-order 조합이 별도로 나옵니다. `i_mmap_rwsem → private_lock → swap_lock → i_pages`, `i_rwsem → invalidate_lock → i_mmap_rwsem`, `mmap_lock → i_mmap_rwsem → page_table_lock 또는 pte_lock → i_pages`, `mmap_lock → invalidate_lock → lock_page`, `i_rwsem → mmap_lock`, `bdi->wb.list_lock → sb_lock 또는 i_pages`, `i_mmap_rwsem → anon_vma.lock`, `anon_vma.lock → page_table_lock 또는 pte_lock` 순서를 포함합니다.

`page_table_lock` 또는 `pte_lock` 아래에서는 `swap_lock`, `private_lock`, `i_pages`, `lruvec->lru_lock`, `bdi.wb->list_lock`, `inode->i_lock`을 여러 unmap·dirty path에서 얻을 수 있습니다. 문서 작성 뒤 comment가 바뀌었을 수 있으므로 현재 source comment 상태를 확인해야 합니다.

Traversing non-VMA page tables
------------------------------

We've focused above on traversal of page tables belonging to VMAs. It is also
possible to traverse page tables which are not represented by VMAs.

Kernel page table mappings themselves are generally managed but whatever part of
the kernel established them and the aforementioned locking rules do not apply -
for instance vmalloc has its own set of locks which are utilised for
establishing and tearing down page its page tables.

However, for convenience we provide the :c:func:`!walk_kernel_page_table_range`
function which is synchronised via the mmap lock on the :c:macro:`!init_mm`
kernel instantiation of the :c:struct:`!struct mm_struct` metadata object.

If an operation requires exclusive access, a write lock is used, but if not, a
read lock suffices - we assert only that at least a read lock has been acquired.

Since, aside from vmalloc and memory hot plug, kernel page tables are not torn
down all that often - this usually suffices, however any caller of this
functionality must ensure that any additionally required locks are acquired in
advance.

We also permit a truly unusual case is the traversal of non-VMA ranges in
**userland** ranges, as provided for by :c:func:`!walk_page_range_debug`.

This has only one user - the general page table dumping logic (implemented in
:c:macro:`!mm/ptdump.c`) - which seeks to expose all mappings for debug purposes
even if they are highly unusual (possibly architecture-specific) and are not
backed by a VMA.

We must take great care in this case, as the :c:func:`!munmap` implementation
detaches VMAs under an mmap write lock before tearing down page tables under a
downgraded mmap read lock.

This means such an operation could race with this, and thus an mmap **write**
lock is required.

Lock ordering
-------------

As we have multiple locks across the kernel which may or may not be taken at the
same time as explicit mm or VMA locks, we have to be wary of lock inversion, and
the **order** in which locks are acquired and released becomes very important.

.. note:: Lock inversion occurs when two threads need to acquire multiple locks,
   but in doing so inadvertently cause a mutual deadlock.

   For example, consider thread 1 which holds lock A and tries to acquire lock B,
   while thread 2 holds lock B and tries to acquire lock A.

   Both threads are now deadlocked on each other. However, had they attempted to
   acquire locks in the same order, one would have waited for the other to
   complete its work and no deadlock would have occurred.

The opening comment in :c:macro:`!mm/rmap.c` describes in detail the required
ordering of locks within memory management code:

.. code-block::

  inode->i_rwsem        (while writing or truncating, not reading or faulting)
    mm->mmap_lock
      mapping->invalidate_lock (in filemap_fault)
        folio_lock
          hugetlbfs_i_mmap_rwsem_key (in huge_pmd_share, see hugetlbfs below)
            vma_start_write
              mapping->i_mmap_rwsem
                anon_vma->rwsem
                  mm->page_table_lock or pte_lock
                    swap_lock (in swap_duplicate, swap_info_get)
                      mmlist_lock (in mmput, drain_mmlist and others)
                      mapping->private_lock (in block_dirty_folio)
                          i_pages lock (widely used)
                            lruvec->lru_lock (in folio_lruvec_lock_irq)
                      inode->i_lock (in set_page_dirty's __mark_inode_dirty)
                      bdi.wb->list_lock (in set_page_dirty's __mark_inode_dirty)
                        sb_lock (within inode_lock in fs/fs-writeback.c)
                        i_pages lock (widely used, in set_page_dirty,
                                  in arch-dependent flush_dcache_mmap_lock,
                                  within bdi.wb->list_lock in __sync_single_inode)

There is also a file-system specific lock ordering comment located at the top of
:c:macro:`!mm/filemap.c`:

.. code-block::

  ->i_mmap_rwsem                        (truncate_pagecache)
    ->private_lock                      (__free_pte->block_dirty_folio)
      ->swap_lock                       (exclusive_swap_page, others)
        ->i_pages lock

  ->i_rwsem
    ->invalidate_lock                   (acquired by fs in truncate path)
      ->i_mmap_rwsem                    (truncate->unmap_mapping_range)

  ->mmap_lock
    ->i_mmap_rwsem
      ->page_table_lock or pte_lock     (various, mainly in memory.c)
        ->i_pages lock                  (arch-dependent flush_dcache_mmap_lock)

  ->mmap_lock
    ->invalidate_lock                   (filemap_fault)
      ->lock_page                       (filemap_fault, access_process_vm)

  ->i_rwsem                             (generic_perform_write)
    ->mmap_lock                         (fault_in_readable->do_page_fault)

  bdi->wb.list_lock
    sb_lock                             (fs/fs-writeback.c)
    ->i_pages lock                      (__sync_single_inode)

  ->i_mmap_rwsem
    ->anon_vma.lock                     (vma_merge)

  ->anon_vma.lock
    ->page_table_lock or pte_lock       (anon_vma_prepare and various)

  ->page_table_lock or pte_lock
    ->swap_lock                         (try_to_unmap_one)
    ->private_lock                      (try_to_unmap_one)
    ->i_pages lock                      (try_to_unmap_one)
    ->lruvec->lru_lock                  (follow_page_mask->mark_page_accessed)
    ->lruvec->lru_lock                  (check_pte_range->folio_isolate_lru)
    ->private_lock                      (folio_remove_rmap_pte->set_page_dirty)
    ->i_pages lock                      (folio_remove_rmap_pte->set_page_dirty)
    bdi.wb->list_lock                   (folio_remove_rmap_pte->set_page_dirty)
    ->inode->i_lock                     (folio_remove_rmap_pte->set_page_dirty)
    bdi.wb->list_lock                   (zap_pte_range->set_page_dirty)
    ->inode->i_lock                     (zap_pte_range->set_page_dirty)
    ->private_lock                      (zap_pte_range->block_dirty_folio)

Please check the current state of these comments which may have changed since
the time of writing of this document.

Page-table locking 규칙과 atomicity

PTE-level page table의 locking 규칙은 다른 level과 매우 다릅니다. 이 section은 VMA가 포함하는 page table만 다룹니다.

• `Higher-level page-table lock`: PGD, P4D, PUD를 수정할 때 process-address-space 단위 `mm->page_table_lock`을 사용합니다.
• `Fine-grained page-table lock`: PMD와 PTE는 page-table folio 안에 둔 lock을 쓰거나 `ALLOC_SPLIT_PTLOCKS`가 set되면 별도로 할당해 folio가 가리키게 합니다. PMD spinlock은 `pmd_lock`, PTE는 32bit system의 high memory에 mapping한 뒤 `pte_offset_map_lock`으로 조심스럽게 lock합니다.

이 lock은 각 level과 상호작용하는 최소 요구입니다. Traversal에서는 아무 page-table lock도 얻지 않을 수 있습니다. 다만 PTE level에서는 적어도 RCU로 concurrent deletion을 막고 high memory의 table을 mapping해야 합니다. Entry read에 추가 조치가 필요한지는 architecture에 따라 다릅니다.

• Page-table entry를 바꿀 때는 `free_pgtables`처럼 concurrent access가 없다고 안전하게 가정할 수 있는 경우를 제외하고 해당 table의 page-table lock을 반드시 가져야 합니다.
• Entry read와 write는 적절히 atomic해야 합니다.
• 비어 있던 entry를 populate하려면 read 또는 write mode의 mmap 또는 VMA lock이 필요합니다. Rmap lock만으로 수행하면 위험합니다.
• Zapping은 mmap, VMA, rmap lock 중 하나로 VMA를 stable하게 유지한 채 수행할 수 있습니다.

VMA unmap 때 `vms_clear_ptes`에는 `unmap_vmas`의 zap과 `free_pgtables`의 table free 사이에 VMA가 rmap tree에 여전히 보이는 window가 있습니다. `free_pgtables`는 zap이 끝났다고 가정해 PTE와 range의 다른 table을 무조건 제거합니다. 이 사이에 새 PTE를 install하면 memory leak과 예기치 않은 위험한 동작이 생길 수 있습니다.

PTE-level table은 32bit architecture에서 high memory에 있을 수 있어 kernel memory에 mapping해야 합니다. Empty PTE table은 mmap 또는 rmap read lock과 PTE·PMD lock을 함께 든 채 unlink하고 RCU-free할 수 있습니다. `MADV_COLLAPSE`를 처리하는 `retract_page_tables`가 그 예입니다.

따라서 PTE-level table 접근에는 최소 RCU read lock이 필요합니다. 그러나 이는 detached되어 RCU free 예정인 table의 empty PTE를 보는 동시에 같은 위치에 새 table이 설치돼 채워지는 race를 허용할 수 있는 reader에만 충분합니다. Writer는 보통 PTE lock을 얻고 PMD가 같은 PTE table을 가리키는지 revalidate해야 합니다. 동일 table인지 중요하지 않다면 PMD lock을 얻고 PMD entry 내용이 요구를 충족하는지 다시 확인할 수 있습니다.

Stability 요구에 따라 `pte_offset_map_lock` 또는 `pte_offset_map` helper를 사용합니다. 필요하면 kernel memory에 table을 mapping하고 RCU lock을 얻으며 variant에 따라 PTE lock lookup 또는 획득도 수행합니다. `__pte_offset_map_lock` comment를 참조하십시오.

Page-table lock과 무관하게 MMU hardware는 accessed·dirty bit를 concurrent하게 갱신합니다. Stable VMA를 둔 parallel traversal과 VMA 안정화 없이 lockless하게 읽는 GUP-fast도 동시에 동작합니다.

Stable VMA 아래 traversal read가 정확히 한 번만 이뤄져야 하는지는 architecture에 따라 다르며 x86-64는 특별한 조치가 필요 없습니다. 그러나 write하거나 read 결과가 write 여부를 결정하는 `__pud_install` 같은 경우에는 entry를 정확히 한 번 가져와야 합니다. Page-table lock이 완전한 exclusive access를 준다고 가정할 수 없습니다.

Read에서는 compiler load 재배치를 막기 위해 `pgdp_get`, `p4dp_get`, `pudp_get`, `pmdp_get`, `ptep_get`이라는 `pXXp_get` 함수를 사용합니다. 각 함수는 `READ_ONCE`로 entry를 한 번만 읽게 합니다.

기존 entry를 조작하면서 저장된 이전 data가 중요하면 `ptep_get_and_clear` 같은 hardware atomic operation이 필요합니다. VMA stability에 의존하지 않는 GUP-fast와 `gup_fast_pte_range` 같은 handler는 `ptep_get_lockless` 및 higher-level 대응 함수를 사용해 매우 조심스럽게 entry와 상호작용해야 합니다.

Write는 `set_pgd`, `set_p4d`, `set_pud`, `set_pmd`, `set_pte` 같은 `set_pXX` 함수로 atomic하게 수행합니다. Clear도 `pgd_clear`, `p4d_clear`, `pud_clear`, `pmd_clear`, `pte_clear` 같은 `pXX_clear` 함수로 atomic하게 수행해야 합니다.

------------------------------
Locking Implementation Details
------------------------------

.. warning:: Locking rules for PTE-level page tables are very different from
             locking rules for page tables at other levels.

Page table locking details
--------------------------

.. note:: This section explores page table locking requirements for page tables
          encompassed by a VMA. See the above section on non-VMA page table
          traversal for details on how we handle that case.

In addition to the locks described in the terminology section above, we have
additional locks dedicated to page tables:

* **Higher level page table locks** - Higher level page tables, that is PGD, P4D
  and PUD each make use of the process address space granularity
  :c:member:`!mm->page_table_lock` lock when modified.

* **Fine-grained page table locks** - PMDs and PTEs each have fine-grained locks
  either kept within the folios describing the page tables or allocated
  separated and pointed at by the folios if :c:macro:`!ALLOC_SPLIT_PTLOCKS` is
  set. The PMD spin lock is obtained via :c:func:`!pmd_lock`, however PTEs are
  mapped into higher memory (if a 32-bit system) and carefully locked via
  :c:func:`!pte_offset_map_lock`.

These locks represent the minimum required to interact with each page table
level, but there are further requirements.

Importantly, note that on a **traversal** of page tables, sometimes no such
locks are taken. However, at the PTE level, at least concurrent page table
deletion must be prevented (using RCU) and the page table must be mapped into
high memory, see below.

Whether care is taken on reading the page table entries depends on the
architecture, see the section on atomicity below.

Locking rules
^^^^^^^^^^^^^

We establish basic locking rules when interacting with page tables:

* When changing a page table entry the page table lock for that page table
  **must** be held, except if you can safely assume nobody can access the page
  tables concurrently (such as on invocation of :c:func:`!free_pgtables`).
* Reads from and writes to page table entries must be *appropriately*
  atomic. See the section on atomicity below for details.
* Populating previously empty entries requires that the mmap or VMA locks are
  held (read or write), doing so with only rmap locks would be dangerous (see
  the warning below).
* As mentioned previously, zapping can be performed while simply keeping the VMA
  stable, that is holding any one of the mmap, VMA or rmap locks.

.. warning:: Populating previously empty entries is dangerous as, when unmapping
             VMAs, :c:func:`!vms_clear_ptes` has a window of time between
             zapping (via :c:func:`!unmap_vmas`) and freeing page tables (via
             :c:func:`!free_pgtables`), where the VMA is still visible in the
             rmap tree. :c:func:`!free_pgtables` assumes that the zap has
             already been performed and removes PTEs unconditionally (along with
             all other page tables in the freed range), so installing new PTE
             entries could leak memory and also cause other unexpected and
             dangerous behaviour.

There are additional rules applicable when moving page tables, which we discuss
in the section on this topic below.

PTE-level page tables are different from page tables at other levels, and there
are extra requirements for accessing them:

* On 32-bit architectures, they may be in high memory (meaning they need to be
  mapped into kernel memory to be accessible).
* When empty, they can be unlinked and RCU-freed while holding an mmap lock or
  rmap lock for reading in combination with the PTE and PMD page table locks.
  In particular, this happens in :c:func:`!retract_page_tables` when handling
  :c:macro:`!MADV_COLLAPSE`.
  So accessing PTE-level page tables requires at least holding an RCU read lock;
  but that only suffices for readers that can tolerate racing with concurrent
  page table updates such that an empty PTE is observed (in a page table that
  has actually already been detached and marked for RCU freeing) while another
  new page table has been installed in the same location and filled with
  entries. Writers normally need to take the PTE lock and revalidate that the
  PMD entry still refers to the same PTE-level page table.
  If the writer does not care whether it is the same PTE-level page table, it
  can take the PMD lock and revalidate that the contents of pmd entry still meet
  the requirements. In particular, this also happens in :c:func:`!retract_page_tables`
  when handling :c:macro:`!MADV_COLLAPSE`.

To access PTE-level page tables, a helper like :c:func:`!pte_offset_map_lock` or
:c:func:`!pte_offset_map` can be used depending on stability requirements.
These map the page table into kernel memory if required, take the RCU lock, and
depending on variant, may also look up or acquire the PTE lock.
See the comment on :c:func:`!__pte_offset_map_lock`.

Atomicity
^^^^^^^^^

Regardless of page table locks, the MMU hardware concurrently updates accessed
and dirty bits (perhaps more, depending on architecture). Additionally, page
table traversal operations in parallel (though holding the VMA stable) and
functionality like GUP-fast locklessly traverses (that is reads) page tables,
without even keeping the VMA stable at all.

When performing a page table traversal and keeping the VMA stable, whether a
read must be performed once and only once or not depends on the architecture
(for instance x86-64 does not require any special precautions).

If a write is being performed, or if a read informs whether a write takes place
(on an installation of a page table entry say, for instance in
:c:func:`!__pud_install`), special care must always be taken. In these cases we
can never assume that page table locks give us entirely exclusive access, and
must retrieve page table entries once and only once.

If we are reading page table entries, then we need only ensure that the compiler
does not rearrange our loads. This is achieved via :c:func:`!pXXp_get`
functions - :c:func:`!pgdp_get`, :c:func:`!p4dp_get`, :c:func:`!pudp_get`,
:c:func:`!pmdp_get`, and :c:func:`!ptep_get`.

Each of these uses :c:func:`!READ_ONCE` to guarantee that the compiler reads
the page table entry only once.

However, if we wish to manipulate an existing page table entry and care about
the previously stored data, we must go further and use an hardware atomic
operation as, for example, in :c:func:`!ptep_get_and_clear`.

Equally, operations that do not rely on the VMA being held stable, such as
GUP-fast (see :c:func:`!gup_fast` and its various page table level handlers like
:c:func:`!gup_fast_pte_range`), must very carefully interact with page table
entries, using functions such as :c:func:`!ptep_get_lockless` and equivalent for
higher level page table levels.

Writes to page table entries must also be appropriately atomic, as established
by :c:func:`!set_pXX` functions - :c:func:`!set_pgd`, :c:func:`!set_p4d`,
:c:func:`!set_pud`, :c:func:`!set_pmd`, and :c:func:`!set_pte`.

Equally functions which clear page table entries must be appropriately atomic,
as in :c:func:`!pXX_clear` functions - :c:func:`!pgd_clear`,
:c:func:`!p4d_clear`, :c:func:`!pud_clear`, :c:func:`!pmd_clear`, and
:c:func:`!pte_clear`.

Page-table installation

Page-table installation은 read 또는 write mode의 mmap 또는 VMA lock으로 VMA를 명시적으로 stable하게 유지한 상태에서 수행합니다.

P4D, PUD, PMD를 할당하고 상위 PGD, P4D, PUD에 대응 entry를 set할 때 `mm->page_table_lock`을 가져야 합니다. `__p4d_alloc`, `__pud_alloc`, `__pmd_alloc`이 각각 이 lock을 얻습니다. `__pmd_alloc`은 `pud_lock`과 `pud_lockptr`을 호출하지만 문서 작성 시점에는 결국 `mm->page_table_lock`을 참조합니다.

PTE allocation은 `mm->page_table_lock`을 사용하거나, `USE_SPLIT_PMD_PTLOCKS`가 정의되면 PMD physical-page metadata의 `struct ptdesc`에 embedded된 lock을 사용합니다. 이 lock은 `pmd_lock`이 호출한 `pmd_ptdesc`를 거쳐 최종적으로 `__pte_alloc`에서 얻습니다.

PTE 내용을 수정하려면 stable하고 exclusive한 access를 위해 PTE page-table lock을 얻어야 합니다. `pte_offset_map_lock`이 PTE가 아래에서 바뀌지 않았는지 확인하고, physical PTE page의 `struct ptdesc`에 든 PTE-granularity spinlock을 `pte_lockptr`로 얻습니다. `pte_unmap_unlock`으로 놓아야 합니다. Stable PTE를 이미 보유한 경우의 `pte_offset_map_rw_nolock` 같은 variant도 있습니다.

Range data를 수정할 때는 보통 필요한 higher table만 할당하고 lock으로 race와 overwrite를 막은 뒤 page fault 또는 zap 요구에 따라 PTE level data를 set 또는 clear합니다.

새 mapping 설치를 위한 전형적인 pattern은 상위 table entry가 empty인지 optimistic하게 보고, empty일 때만 page-table lock을 얻어 그 사이 allocation됐는지 다시 확인하는 것입니다. `__pud_alloc`이 예입니다. 필요한 때만 lock을 얻어 순회할 수 있습니다.

Leaf PTE에서는 PMD lock과 PTE lock이 분리되어 있고 THP collapse가 PMD entry와 PTE를 아래에서 없앨 수 있어 이 pattern만 믿을 수 없습니다. `__pte_offset_map_lock`은 lockless하게 PMD entry를 가져와 예상값인지 확인하고 PTE-specific lock을 얻은 뒤 PMD를 다시 확인합니다. THP collapse는 두 page lock을 모두 필요로 하므로 PTE lock을 든 동안 막을 수 있습니다. 이 방식으로 entry를 설치하면 write mutual exclusion을 보장합니다.

Page table installation
^^^^^^^^^^^^^^^^^^^^^^^

Page table installation is performed with the VMA held stable explicitly by an
mmap or VMA lock in read or write mode (see the warning in the locking rules
section for details as to why).

When allocating a P4D, PUD or PMD and setting the relevant entry in the above
PGD, P4D or PUD, the :c:member:`!mm->page_table_lock` must be held. This is
acquired in :c:func:`!__p4d_alloc`, :c:func:`!__pud_alloc` and
:c:func:`!__pmd_alloc` respectively.

.. note:: :c:func:`!__pmd_alloc` actually invokes :c:func:`!pud_lock` and
   :c:func:`!pud_lockptr` in turn, however at the time of writing it ultimately
   references the :c:member:`!mm->page_table_lock`.

Allocating a PTE will either use the :c:member:`!mm->page_table_lock` or, if
:c:macro:`!USE_SPLIT_PMD_PTLOCKS` is defined, a lock embedded in the PMD
physical page metadata in the form of a :c:struct:`!struct ptdesc`, acquired by
:c:func:`!pmd_ptdesc` called from :c:func:`!pmd_lock` and ultimately
:c:func:`!__pte_alloc`.

Finally, modifying the contents of the PTE requires special treatment, as the
PTE page table lock must be acquired whenever we want stable and exclusive
access to entries contained within a PTE, especially when we wish to modify
them.

This is performed via :c:func:`!pte_offset_map_lock` which carefully checks to
ensure that the PTE hasn't changed from under us, ultimately invoking
:c:func:`!pte_lockptr` to obtain a spin lock at PTE granularity contained within
the :c:struct:`!struct ptdesc` associated with the physical PTE page. The lock
must be released via :c:func:`!pte_unmap_unlock`.

.. note:: There are some variants on this, such as
   :c:func:`!pte_offset_map_rw_nolock` when we know we hold the PTE stable but
   for brevity we do not explore this.  See the comment for
   :c:func:`!__pte_offset_map_lock` for more details.

When modifying data in ranges we typically only wish to allocate higher page
tables as necessary, using these locks to avoid races or overwriting anything,
and set/clear data at the PTE level as required (for instance when page faulting
or zapping).

A typical pattern taken when traversing page table entries to install a new
mapping is to optimistically determine whether the page table entry in the table
above is empty, if so, only then acquiring the page table lock and checking
again to see if it was allocated underneath us.

This allows for a traversal with page table locks only being taken when
required. An example of this is :c:func:`!__pud_alloc`.

At the leaf page table, that is the PTE, we can't entirely rely on this pattern
as we have separate PMD and PTE locks and a THP collapse for instance might have
eliminated the PMD entry as well as the PTE from under us.

This is why :c:func:`!__pte_offset_map_lock` locklessly retrieves the PMD entry
for the PTE, carefully checking it is as expected, before acquiring the
PTE-specific lock, and then *again* checking that the PMD entry is as expected.

If a THP collapse (or similar) were to occur then the lock on both pages would
be acquired, so we can ensure this is prevented while the PTE lock is held.

Installing entries this way ensures mutual exclusion on write.

Page-table freeing

Page table 자체를 해제할 때는 제거 대상 table을 concurrent task가 순회하거나 참조할 방법이 전혀 없어야 합니다.

Mmap write lock과 VMA lock만으로는 충분하지 않습니다. 이 lock은 racing fault와 rmap operation을 막지만 file-backed mapping은 `struct address_space->i_mmap_rwsem`만으로 truncate될 수 있습니다.

따라서 `struct anon_vma->rb_root` 또는 `struct address_space->i_mmap` interval tree를 통해 reverse mapping으로 접근할 수 있는 VMA의 page table은 해제하면 안 됩니다.

보통 `free_pgtables`가 수행하며, `mm_wr_locked` parameter가 나타내듯 mmap write lock을 얻었거나 VMA가 이미 unreachable하다고 가정합니다. VMA를 모든 reverse mapping에서 조심스럽게 제거하고, 새 VMA가 겹치거나 해제 range 주소에 접근할 route가 남지 않아야 합니다.

또한 zap이 이미 끝났고 zap과 `free_pgtables` 사이에 추가 entry를 설치할 수 없도록 조치했다고 가정합니다. 그러므로 `pgd_clear`, `p4d_clear`, `pud_clear`, `pmd_clear`는 page-table lock 없이 entry를 clear합니다.

`retract_page_tables`처럼 leaf table만 상위 table과 독립적으로 해제할 수는 있습니다. 이 경우 i_mmap read lock, PMD와 PTE page-table lock 아래에서 수행하므로 같은 수준의 전체 조치는 필요하지 않습니다.

Page table freeing
^^^^^^^^^^^^^^^^^^

Tearing down page tables themselves is something that requires significant
care. There must be no way that page tables designated for removal can be
traversed or referenced by concurrent tasks.

It is insufficient to simply hold an mmap write lock and VMA lock (which will
prevent racing faults, and rmap operations), as a file-backed mapping can be
truncated under the :c:struct:`!struct address_space->i_mmap_rwsem` alone.

As a result, no VMA which can be accessed via the reverse mapping (either
through the :c:struct:`!struct anon_vma->rb_root` or the :c:member:`!struct
address_space->i_mmap` interval trees) can have its page tables torn down.

The operation is typically performed via :c:func:`!free_pgtables`, which assumes
either the mmap write lock has been taken (as specified by its
:c:member:`!mm_wr_locked` parameter), or that the VMA is already unreachable.

It carefully removes the VMA from all reverse mappings, however it's important
that no new ones overlap these or any route remain to permit access to addresses
within the range whose page tables are being torn down.

Additionally, it assumes that a zap has already been performed and steps have
been taken to ensure that no further page table entries can be installed between
the zap and the invocation of :c:func:`!free_pgtables`.

Since it is assumed that all such steps have been taken, page table entries are
cleared without page table locks (in the :c:func:`!pgd_clear`, :c:func:`!p4d_clear`,
:c:func:`!pud_clear`, and :c:func:`!pmd_clear` functions.

.. note:: It is possible for leaf page tables to be torn down independent of
          the page tables above it as is done by
          :c:func:`!retract_page_tables`, which is performed under the i_mmap
          read lock, PMD, and PTE page table locks, without this level of care.

Page-table moving

일부 함수는 PMD보다 높은 PUD, P4D, PGD page table을 조작합니다. 대표적으로 `mremap`은 higher-level page table을 이동할 수 있습니다.

이 경우 mmap lock, VMA lock, 관련 rmap lock을 모두 얻어야 합니다. `mremap` 구현에서 `move_page_tables`가 최종 호출하는 `take_rmap_locks`와 `drop_rmap_locks`가 rmap 쪽 lock 획득과 해제를 수행합니다.

Page table moving
^^^^^^^^^^^^^^^^^

Some functions manipulate page table levels above PMD (that is PUD, P4D and PGD
page tables). Most notable of these is :c:func:`!mremap`, which is capable of
moving higher level page tables.

In these instances, it is required that **all** locks are taken, that is
the mmap lock, the VMA lock and the relevant rmap locks.

You can observe this in the :c:func:`!mremap` implementation in the functions
:c:func:`!take_rmap_locks` and :c:func:`!drop_rmap_locks` which perform the rmap
side of lock acquisition, invoked ultimately by :c:func:`!move_page_tables`.

VMA lock 내부 동작

VMA read locking은 완전히 optimistic합니다. Lock이 contended되거나 경쟁 write가 시작되면 read lock을 얻지 않습니다.

`lock_vma_under_rcu`는 먼저 `rcu_read_lock`으로 RCU critical section에서 VMA를 lookup하고 `vma_start_read`로 VMA lock을 시도한 뒤 `rcu_read_unlock`으로 RCU lock을 놓습니다. Caller가 mmap read lock을 이미 가진 경우 `vma_start_read_locked`와 nested variant를 쓸 수 있습니다. Contention으로 실패하지 않지만 다른 이유의 실패는 return value로 검사해야 합니다.

VMA read lock은 유지되는 동안 `vma.vm_refcnt`를 증가시킵니다. `lock_vma_under_rcu` caller는 `vma_end_read`로 이를 내려야 합니다.

VMA 수정 전에는 `vma_start_write`로 write lock을 얻으며 read와 달리 항상 획득합니다. 유지 시간 내내 mmap write lock이 필요하고, mmap write lock을 놓거나 downgrade하면 VMA write lock도 놓이므로 `vma_end_write`는 없습니다. Write lock을 얻는 동안 reader가 writer 존재를 감지하도록 `vma.vm_refcnt`를 잠시 수정하고 serialization sequence number를 갱신한 뒤 복원합니다.

VMA lock은 contention이 심한 mmap lock 사용을 피하는 가벼운 mechanism입니다. Containing `mm_struct`와 VMA의 reference counter 및 sequence number 조합으로 구현합니다.

`vma_start_read`는 optimistic하게 read lock을 시도하고 실패하면 false를 반환합니다. 작업 후 `vma_end_read`로 놓습니다. 호출 전 `rcu_read_lock`이 필요하지만 RCU는 lookup에만 필요하므로 VMA lock 획득 뒤 놓을 수 있습니다. User-facing interface는 이를 추상화한 `lock_vma_under_rcu`입니다.

Write에는 mmap write lock과 `vma_start_write`가 필요합니다. Mmap write lock 종료나 downgrade가 VMA write lock을 해제합니다. 여러 VMA를 동시에 write-lock하는 operation의 복잡성을 줄이려고 per-mm과 per-VMA sequence count를 사용합니다.

`mm->mm_lock_seq`와 `vma->vm_lock_seq`가 같으면 VMA가 write-locked이고 다르면 아닙니다. `mmap_write_unlock` 또는 `mmap_write_downgrade` 때 `vma_end_write_all`이 호출되고 `mm_lock_seqcount_end`로 `mm->mm_lock_seq`도 증가합니다. 따라서 VMA sequence 값과 무관하게 write-lock 상태를 잘못 표시하지 않으며 mmap의 모든 VMA write lock을 한꺼번에 효율적으로 놓습니다.

Mmap write lock은 holder끼리 exclusive이므로 별도 write operation 사이까지 VMA lock을 유지할 이유가 없고, 자동 해제가 올바른 lock ordering도 보존합니다.

VMA read lock 획득 때 `vma.vm_refcnt`를 증가시키고 VMA sequence가 mm sequence와 다른지 확인합니다. 같으면 writer가 있으므로 실패하고 refcount를 내립니다. 다르면 refcount를 높인 채 writer를 배제하고 RCU 아래 다른 reader의 동시 획득을 허용합니다. `lock_vma_under_rcu`의 maple-tree operation도 RCU-safe입니다.

Writer는 reader가 수정할 수 없는 bit를 `vma.vm_refcnt`에 set하고 모든 reader가 refcount를 내릴 때까지 기다립니다. Reader가 사라지면 mmap write lock을 든 채 VMA sequence를 mm sequence와 같게 합니다. 이 때문에 read lock이 있으면 `vma_start_write`가 완료를 기다려 mutual exclusion을 얻습니다. 그 뒤 writer bit를 clear하고, mmap write lock을 놓거나 downgrade할 때까지 sequence가 write-locked 상태를 나타냅니다.

Reference counter와 sequence count의 조합은 특히 page fault에서 빠른 RCU 기반 per-VMA lock 획득을 제공하면서 lock-ordering 복잡성을 최소화합니다.

VMA lock internals
------------------

Overview
^^^^^^^^

VMA read locking is entirely optimistic - if the lock is contended or a competing
write has started, then we do not obtain a read lock.

A VMA **read** lock is obtained by :c:func:`!lock_vma_under_rcu`, which first
calls :c:func:`!rcu_read_lock` to ensure that the VMA is looked up in an RCU
critical section, then attempts to VMA lock it via :c:func:`!vma_start_read`,
before releasing the RCU lock via :c:func:`!rcu_read_unlock`.

In cases when the user already holds mmap read lock, :c:func:`!vma_start_read_locked`
and :c:func:`!vma_start_read_locked_nested` can be used. These functions do not
fail due to lock contention but the caller should still check their return values
in case they fail for other reasons.

VMA read locks increment :c:member:`!vma.vm_refcnt` reference counter for their
duration and the caller of :c:func:`!lock_vma_under_rcu` must drop it via
:c:func:`!vma_end_read`.

VMA **write** locks are acquired via :c:func:`!vma_start_write` in instances where a
VMA is about to be modified, unlike :c:func:`!vma_start_read` the lock is always
acquired. An mmap write lock **must** be held for the duration of the VMA write
lock, releasing or downgrading the mmap write lock also releases the VMA write
lock so there is no :c:func:`!vma_end_write` function.

Note that when write-locking a VMA lock, the :c:member:`!vma.vm_refcnt` is temporarily
modified so that readers can detect the presense of a writer. The reference counter is
restored once the vma sequence number used for serialisation is updated.

This ensures the semantics we require - VMA write locks provide exclusive write
access to the VMA.

Implementation details
^^^^^^^^^^^^^^^^^^^^^^

The VMA lock mechanism is designed to be a lightweight means of avoiding the use
of the heavily contended mmap lock. It is implemented using a combination of a
reference counter and sequence numbers belonging to the containing
:c:struct:`!struct mm_struct` and the VMA.

Read locks are acquired via :c:func:`!vma_start_read`, which is an optimistic
operation, i.e. it tries to acquire a read lock but returns false if it is
unable to do so. At the end of the read operation, :c:func:`!vma_end_read` is
called to release the VMA read lock.

Invoking :c:func:`!vma_start_read` requires that :c:func:`!rcu_read_lock` has
been called first, establishing that we are in an RCU critical section upon VMA
read lock acquisition. Once acquired, the RCU lock can be released as it is only
required for lookup. This is abstracted by :c:func:`!lock_vma_under_rcu` which
is the interface a user should use.

Writing requires the mmap to be write-locked and the VMA lock to be acquired via
:c:func:`!vma_start_write`, however the write lock is released by the termination or
downgrade of the mmap write lock so no :c:func:`!vma_end_write` is required.

All this is achieved by the use of per-mm and per-VMA sequence counts, which are
used in order to reduce complexity, especially for operations which write-lock
multiple VMAs at once.

If the mm sequence count, :c:member:`!mm->mm_lock_seq` is equal to the VMA
sequence count :c:member:`!vma->vm_lock_seq` then the VMA is write-locked. If
they differ, then it is not.

Each time the mmap write lock is released in :c:func:`!mmap_write_unlock` or
:c:func:`!mmap_write_downgrade`, :c:func:`!vma_end_write_all` is invoked which
also increments :c:member:`!mm->mm_lock_seq` via
:c:func:`!mm_lock_seqcount_end`.

This way, we ensure that, regardless of the VMA's sequence number, a write lock
is never incorrectly indicated and that when we release an mmap write lock we
efficiently release **all** VMA write locks contained within the mmap at the
same time.

Since the mmap write lock is exclusive against others who hold it, the automatic
release of any VMA locks on its release makes sense, as you would never want to
keep VMAs locked across entirely separate write operations. It also maintains
correct lock ordering.

Each time a VMA read lock is acquired, we increment :c:member:`!vma.vm_refcnt`
reference counter and check that the sequence count of the VMA does not match
that of the mm.

If it does, the read lock fails and :c:member:`!vma.vm_refcnt` is dropped.
If it does not, we keep the reference counter raised, excluding writers, but
permitting other readers, who can also obtain this lock under RCU.

Importantly, maple tree operations performed in :c:func:`!lock_vma_under_rcu`
are also RCU safe, so the whole read lock operation is guaranteed to function
correctly.

On the write side, we set a bit in :c:member:`!vma.vm_refcnt` which can't be
modified by readers and wait for all readers to drop their reference count.
Once there are no readers, the VMA's sequence number is set to match that of
the mm. During this entire operation mmap write lock is held.

This way, if any read locks are in effect, :c:func:`!vma_start_write` will sleep
until these are finished and mutual exclusion is achieved.

After setting the VMA's sequence number, the bit in :c:member:`!vma.vm_refcnt`
indicating a writer is cleared. From this point on, VMA's sequence number will
indicate VMA's write-locked state until mmap write lock is dropped or downgraded.

This clever combination of a reference counter and sequence count allows for
fast RCU-based per-VMA lock acquisition (especially on page fault, though
utilised elsewhere) with minimal complexity around lock ordering.

mmap write-lock downgrade

Mmap write lock을 가지면 mmap 안 resource에 exclusive access가 있습니다. 다만 VMA read-lock holder와 race하지 않으려면 VMA write lock이 필요하다는 일반 주의는 그대로입니다.

`mmap_write_downgrade`로 write lock을 read lock으로 downgrade할 수 있습니다. `mmap_write_unlock`과 마찬가지로 `vma_end_write_all`을 통해 모든 VMA write lock을 암시적으로 끝내지만, downgrade 동안 mmap lock 자체는 놓지 않으므로 locked virtual-address space는 stable하게 유지됩니다.

흥미롭게도 downgraded lock끼리는 서로 exclusive입니다. 경쟁 task가 downgraded lock을 얻으려면 먼저 write lock을 얻어야 하지만 기존 downgraded lock이 새 write lock을 막기 때문입니다.

Exclusivity matrix에서 read(R)와 read, read와 downgraded(D)는 서로 배제하지 않습니다. R과 W는 배제합니다. D와 D, D와 W는 배제합니다. W는 R·D·W 모두와 배제합니다. 원문 표의 Y는 mutual exclusion, N은 비배제를 뜻합니다.

mmap write lock downgrading
---------------------------

When an mmap write lock is held one has exclusive access to resources within the
mmap (with the usual caveats about requiring VMA write locks to avoid races with
tasks holding VMA read locks).

It is then possible to **downgrade** from a write lock to a read lock via
:c:func:`!mmap_write_downgrade` which, similar to :c:func:`!mmap_write_unlock`,
implicitly terminates all VMA write locks via :c:func:`!vma_end_write_all`, but
importantly does not relinquish the mmap lock while downgrading, therefore
keeping the locked virtual address space stable.

An interesting consequence of this is that downgraded locks are exclusive
against any other task possessing a downgraded lock (since a racing task would
have to acquire a write lock first to downgrade it, and the downgraded lock
prevents a new write lock from being obtained until the original lock is
released).

For clarity, we map read (R)/downgraded write (D)/write (W) locks against one
another showing which locks exclude the others:

.. list-table:: Lock exclusivity
   :widths: 5 5 5 5
   :header-rows: 1
   :stub-columns: 1

   * -
     - R
     - D
     - W
   * - R
     - N
     - N
     - Y
   * - D
     - N
     - Y
     - Y
   * - W
     - Y
     - Y
     - Y

Here a Y indicates the locks in the matching row/column are mutually exclusive,
and N indicates that they are not.

Stack expansion

Stack expansion은 racing page fault를 허용할 수 없다는 추가 복잡성을 만듭니다. `expand_downwards` 또는 `expand_upwards`에서 이를 막기 위해 `vma_start_write`를 호출합니다.

Stack expansion
---------------

Stack expansion throws up additional complexities in that we cannot permit there
to be racing page faults, as a result we invoke :c:func:`!vma_start_write` to
prevent this in :c:func:`!expand_downwards` or :c:func:`!expand_upwards`.