path: root/Documentation/mm/process_addrs.rst

.. 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.

-------
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 vma_start_write() or vma_start_write_killable()
  (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.

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 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 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