code:
.. SPDX-License-Identifier: GPL-2.0

.. _physical_memory_model:

=====================
Physical Memory Model
=====================

Physical memory in a system may be addressed in different ways. The
simplest case is when the physical memory starts at address 0 and
spans a contiguous range up to the maximal address. It could be,
however, that this range contains small holes that are not accessible
for the CPU. Then there could be several contiguous ranges at
completely distinct addresses. And, don't forget about NUMA, where
different memory banks are attached to different CPUs.

Linux abstracts this diversity using one of the two memory models:
FLATMEM and SPARSEMEM. Each architecture defines what
memory models it supports, what the default memory model is and
whether it is possible to manually override that default.

All the memory models track the status of physical page frames using
struct page arranged in one or more arrays.

Regardless of the selected memory model, there exists one-to-one
mapping between the physical page frame number (PFN) and the
corresponding `struct page`.

Each memory model defines :c:func:`pfn_to_page` and :c:func:`page_to_pfn`
helpers that allow the conversion from PFN to `struct page` and vice
versa.

FLATMEM
=======

The simplest memory model is FLATMEM. This model is suitable for
non-NUMA systems with contiguous, or mostly contiguous, physical
memory.

In the FLATMEM memory model, there is a global `mem_map` array that
maps the entire physical memory. For most architectures, the holes
have entries in the `mem_map` array. The `struct page` objects
corresponding to the holes are never fully initialized.

To allocate the `mem_map` array, architecture specific setup code should
call :c:func:`free_area_init` function. Yet, the mappings array is not
usable until the call to :c:func:`memblock_free_all` that hands all the
memory to the page allocator.

An architecture may free parts of the `mem_map` array that do not cover the
actual physical pages. In such case, the architecture specific
:c:func:`pfn_valid` implementation should take the holes in the
`mem_map` into account.

With FLATMEM, the conversion between a PFN and the `struct page` is
straightforward: `PFN - ARCH_PFN_OFFSET` is an index to the
`mem_map` array.

The `ARCH_PFN_OFFSET` defines the first page frame number for
systems with physical memory starting at address different from 0.

SPARSEMEM
=========

SPARSEMEM is the most versatile memory model available in Linux and it
is the only memory model that supports several advanced features such
as hot-plug and hot-remove of the physical memory, alternative memory
maps for non-volatile memory devices and deferred initialization of
the memory map for larger systems.

The SPARSEMEM model presents the physical memory as a collection of
sections. A section is represented with struct mem_section
that contains `section_mem_map` that is, logically, a pointer to an
array of struct pages. However, it is stored with some other magic
that aids the sections management. The section size and maximal number
of section is specified using `SECTION_SIZE_BITS` and
`MAX_PHYSMEM_BITS` constants defined by each architecture that
supports SPARSEMEM. While `MAX_PHYSMEM_BITS` is an actual width of a
physical address that an architecture supports, the
`SECTION_SIZE_BITS` is an arbitrary value.

The maximal number of sections is denoted `NR_MEM_SECTIONS` and
defined as

.. math::

   NR\_MEM\_SECTIONS = 2 ^ {(MAX\_PHYSMEM\_BITS - SECTION\_SIZE\_BITS)}

The `mem_section` objects are arranged in a two-dimensional array
called `mem_sections`. The size and placement of this array depend
on `CONFIG_SPARSEMEM_EXTREME` and the maximal possible number of
sections:

* When `CONFIG_SPARSEMEM_EXTREME` is disabled, the `mem_sections`
  array is static and has `NR_MEM_SECTIONS` rows. Each row holds a
  single `mem_section` object.
* When `CONFIG_SPARSEMEM_EXTREME` is enabled, the `mem_sections`
  array is dynamically allocated. Each row contains PAGE_SIZE worth of
  `mem_section` objects and the number of rows is calculated to fit
  all the memory sections.

The architecture setup code should call sparse_init() to
initialize the memory sections and the memory maps.

With SPARSEMEM there are two possible ways to convert a PFN to the
corresponding `struct page` - a "classic sparse" and "sparse
vmemmap". The selection is made at build time and it is determined by
the value of `CONFIG_SPARSEMEM_VMEMMAP`.

The classic sparse encodes the section number of a page in page->flags
and uses high bits of a PFN to access the section that maps that page
frame. Inside a section, the PFN is the index to the array of pages.

The sparse vmemmap uses a virtually mapped memory map to optimize
pfn_to_page and page_to_pfn operations. There is a global `struct
page *vmemmap` pointer that points to a virtually contiguous array of
`struct page` objects. A PFN is an index to that array and the
offset of the `struct page` from `vmemmap` is the PFN of that
page.

To use vmemmap, an architecture has to reserve a range of virtual
addresses that will map the physical pages containing the memory
map and make sure that `vmemmap` points to that range. In addition,
the architecture should implement :c:func:`vmemmap_populate` method
that will allocate the physical memory and create page tables for the
virtual memory map. If an architecture does not have any special
requirements for the vmemmap mappings, it can use default
:c:func:`vmemmap_populate_basepages` provided by the generic memory
management.

The virtually mapped memory map allows storing `struct page` objects
for persistent memory devices in pre-allocated storage on those
devices. This storage is represented with struct vmem_altmap
that is eventually passed to vmemmap_populate() through a long chain
of function calls. The vmemmap_populate() implementation may use the
`vmem_altmap` along with :c:func:`vmemmap_alloc_block_buf` helper to
allocate memory map on the persistent memory device.

ZONE_DEVICE
===========
The `ZONE_DEVICE` facility builds upon `SPARSEMEM_VMEMMAP` to offer
`struct page` `mem_map` services for device driver identified physical
address ranges. The "device" aspect of `ZONE_DEVICE` relates to the fact
that the page objects for these address ranges are never marked online,
and that a reference must be taken against the device, not just the page
to keep the memory pinned for active use. `ZONE_DEVICE`, via
:c:func:`devm_memremap_pages`, performs just enough memory hotplug to
turn on :c:func:`pfn_to_page`, :c:func:`page_to_pfn`, and
:c:func:`get_user_pages` service for the given range of pfns. Since the
page reference count never drops below 1 the page is never tracked as
free memory and the page's `struct list_head lru` space is repurposed
for back referencing to the host device / driver that mapped the memory.

While `SPARSEMEM` presents memory as a collection of sections,
optionally collected into memory blocks, `ZONE_DEVICE` users have a need
for smaller granularity of populating the `mem_map`. Given that
`ZONE_DEVICE` memory is never marked online it is subsequently never
subject to its memory ranges being exposed through the sysfs memory
hotplug api on memory block boundaries. The implementation relies on
this lack of user-api constraint to allow sub-section sized memory
ranges to be specified to :c:func:`arch_add_memory`, the top-half of
memory hotplug. Sub-section support allows for 2MB as the cross-arch
common alignment granularity for :c:func:`devm_memremap_pages`.

The users of `ZONE_DEVICE` are:

* pmem: Map platform persistent memory to be used as a direct-I/O target
  via DAX mappings.

* hmm: Extend `ZONE_DEVICE` with `->page_fault()` and `->page_free()`
  event callbacks to allow a device-driver to coordinate memory management
  events related to device-memory, typically GPU memory. See
  Documentation/mm/hmm.rst.

* p2pdma: Create `struct page` objects to allow peer devices in a
  PCI/-E topology to coordinate direct-DMA operations between themselves,
  i.e. bypass host memory.


code:
.. _mmu_notifier:

When do you need to notify inside page table lock ?
===================================================

When clearing a pte/pmd we are given a choice to notify the event through
(notify version of \*_clear_flush call mmu_notifier_invalidate_range) under
the page table lock. But that notification is not necessary in all cases.

For secondary TLB (non CPU TLB) like IOMMU TLB or device TLB (when device use
thing like ATS/PASID to get the IOMMU to walk the CPU page table to access a
process virtual address space). There is only 2 cases when you need to notify
those secondary TLB while holding page table lock when clearing a pte/pmd:

  A) page backing address is free before mmu_notifier_invalidate_range_end()
  B) a page table entry is updated to point to a new page (COW, write fault
     on zero page, __replace_page(), ...)

Case A is obvious you do not want to take the risk for the device to write to
a page that might now be used by some completely different task.

Case B is more subtle. For correctness it requires the following sequence to
happen:

  - take page table lock
  - clear page table entry and notify ([pmd/pte]p_huge_clear_flush_notify())
  - set page table entry to point to new page

If clearing the page table entry is not followed by a notify before setting
the new pte/pmd value then you can break memory model like C11 or C++11 for
the device.

Consider the following scenario (device use a feature similar to ATS/PASID):

Two address addrA and addrB such that \|addrA - addrB\| >= PAGE_SIZE we assume
they are write protected for COW (other case of B apply too).

::

 [Time N] --------------------------------------------------------------------
 CPU-thread-0  {try to write to addrA}
 CPU-thread-1  {try to write to addrB}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {read addrA and populate device TLB}
 DEV-thread-2  {read addrB and populate device TLB}
 [Time N+1] ------------------------------------------------------------------
 CPU-thread-0  {COW_step0: {mmu_notifier_invalidate_range_start(addrA)}}
 CPU-thread-1  {COW_step0: {mmu_notifier_invalidate_range_start(addrB)}}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+2] ------------------------------------------------------------------
 CPU-thread-0  {COW_step1: {update page table to point to new page for addrA}}
 CPU-thread-1  {COW_step1: {update page table to point to new page for addrB}}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+3] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {preempted}
 CPU-thread-2  {write to addrA which is a write to new page}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+3] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {preempted}
 CPU-thread-2  {}
 CPU-thread-3  {write to addrB which is a write to new page}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+4] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {COW_step3: {mmu_notifier_invalidate_range_end(addrB)}}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {}
 DEV-thread-2  {}
 [Time N+5] ------------------------------------------------------------------
 CPU-thread-0  {preempted}
 CPU-thread-1  {}
 CPU-thread-2  {}
 CPU-thread-3  {}
 DEV-thread-0  {read addrA from old page}
 DEV-thread-2  {read addrB from new page}

So here because at time N+2 the clear page table entry was not pair with a
notification to invalidate the secondary TLB, the device see the new value for
addrB before seeing the new value for addrA. This break total memory ordering
for the device.

When changing a pte to write protect or to point to a new write protected page
with same content (KSM) it is fine to delay the mmu_notifier_invalidate_range
call to mmu_notifier_invalidate_range_end() outside the page table lock. This
is true even if the thread doing the page table update is preempted right after
releasing page table lock but before call mmu_notifier_invalidate_range_end().

repo_name: angery/linux


code:
.. SPDX-License-Identifier: GPL-2.0

=============
Multi-Gen LRU
=============
The multi-gen LRU is an alternative LRU implementation that optimizes
page reclaim and improves performance under memory pressure. Page
reclaim decides the kernel's caching policy and ability to overcommit
memory. It directly impacts the kswapd CPU usage and RAM efficiency.

Design overview
===============
Objectives
----------
The design objectives are:

* Good representation of access recency
* Try to profit from spatial locality
* Fast paths to make obvious choices
* Simple self-correcting heuristics

The representation of access recency is at the core of all LRU
implementations. In the multi-gen LRU, each generation represents a
group of pages with similar access recency. Generations establish a
(time-based) common frame of reference and therefore help make better
choices, e.g., between different memcgs on a computer or different
computers in a data center (for job scheduling).

Exploiting spatial locality improves efficiency when gathering the
accessed bit. A rmap walk targets a single page and does not try to
profit from discovering a young PTE. A page table walk can sweep all
the young PTEs in an address space, but the address space can be too
sparse to make a profit. The key is to optimize both methods and use
them in combination.

Fast paths reduce code complexity and runtime overhead. Unmapped pages
do not require TLB flushes; clean pages do not require writeback.
These facts are only helpful when other conditions, e.g., access
recency, are similar. With generations as a common frame of reference,
additional factors stand out. But obvious choices might not be good
choices; thus self-correction is necessary.

The benefits of simple self-correcting heuristics are self-evident.
Again, with generations as a common frame of reference, this becomes
attainable. Specifically, pages in the same generation can be
categorized based on additional factors, and a feedback loop can
statistically compare the refault percentages across those categories
and infer which of them are better choices.

Assumptions
-----------
The protection of hot pages and the selection of cold pages are based
on page access channels and patterns. There are two access channels:

* Accesses through page tables
* Accesses through file descriptors

The protection of the former channel is by design stronger because:

1. The uncertainty in determining the access patterns of the former
   channel is higher due to the approximation of the accessed bit.
2. The cost of evicting the former channel is higher due to the TLB
   flushes required and the likelihood of encountering the dirty bit.
3. The penalty of underprotecting the former channel is higher because
   applications usually do not prepare themselves for major page
   faults like they do for blocked I/O. E.g., GUI applications
   commonly use dedicated I/O threads to avoid blocking rendering
   threads.

There are also two access patterns:

* Accesses exhibiting temporal locality
* Accesses not exhibiting temporal locality

For the reasons listed above, the former channel is assumed to follow
the former pattern unless ``VM_SEQ_READ`` or ``VM_RAND_READ`` is
present, and the latter channel is assumed to follow the latter
pattern unless outlying refaults have been observed.

Workflow overview
=================
Evictable pages are divided into multiple generations for each
``lruvec``. The youngest generation number is stored in
``lrugen->max_seq`` for both anon and file types as they are aged on
an equal footing. The oldest generation numbers are stored in
``lrugen->min_seq[]`` separately for anon and file types as clean file
pages can be evicted regardless of swap constraints. These three
variables are monotonically increasing.

Generation numbers are truncated into ``order_base_2(MAX_NR_GENS+1)``
bits in order to fit into the gen counter in ``folio->flags``. Each
truncated generation number is an index to ``lrugen->lists[]``. The
sliding window technique is used to track at least ``MIN_NR_GENS`` and
at most ``MAX_NR_GENS`` generations. The gen counter stores a value
within ``[1, MAX_NR_GENS]`` while a page is on one of
``lrugen->lists[]``; otherwise it stores zero.

Each generation is divided into multiple tiers. A page accessed ``N``
times through file descriptors is in tier ``order_base_2(N)``. Unlike
generations, tiers do not have dedicated ``lrugen->lists[]``. In
contrast to moving across generations, which requires the LRU lock,
moving across tiers only involves atomic operations on
``folio->flags`` and therefore has a negligible cost. A feedback loop
modeled after the PID controller monitors refaults over all the tiers
from anon and file types and decides which tiers from which types to
evict or protect.

There are two conceptually independent procedures: the aging and the
eviction. They form a closed-loop system, i.e., the page reclaim.

Aging
-----
The aging produces young generations. Given an ``lruvec``, it
increments ``max_seq`` when ``max_seq-min_seq+1`` approaches
``MIN_NR_GENS``. The aging promotes hot pages to the youngest
generation when it finds them accessed through page tables; the
demotion of cold pages happens consequently when it increments
``max_seq``. The aging uses page table walks and rmap walks to find
young PTEs. For the former, it iterates ``lruvec_memcg()->mm_list``
and calls ``walk_page_range()`` with each ``mm_struct`` on this list
to scan PTEs, and after each iteration, it increments ``max_seq``. For
the latter, when the eviction walks the rmap and finds a young PTE,
the aging scans the adjacent PTEs. For both, on finding a young PTE,
the aging clears the accessed bit and updates the gen counter of the
page mapped by this PTE to ``(max_seq%MAX_NR_GENS)+1``.

Eviction
--------
The eviction consumes old generations. Given an ``lruvec``, it
increments ``min_seq`` when ``lrugen->lists[]`` indexed by
``min_seq%MAX_NR_GENS`` becomes empty. To select a type and a tier to
evict from, it first compares ``min_seq[]`` to select the older type.
If both types are equally old, it selects the one whose first tier has
a lower refault percentage. The first tier contains single-use
unmapped clean pages, which are the best bet. The eviction sorts a
page according to its gen counter if the aging has found this page
accessed through page tables and updated its gen counter. It also
moves a page to the next generation, i.e., ``min_seq+1``, if this page
was accessed multiple times through file descriptors and the feedback
loop has detected outlying refaults from the tier this page is in. To
this end, the feedback loop uses the first tier as the baseline, for
the reason stated earlier.

Summary
-------
The multi-gen LRU can be disassembled into the following parts:

* Generations
* Rmap walks
* Page table walks
* Bloom filters
* PID controller

The aging and the eviction form a producer-consumer model;
specifically, the latter drives the former by the sliding window over
generations. Within the aging, rmap walks drive page table walks by
inserting hot densely populated page tables to the Bloom filters.
Within the eviction, the PID controller uses refaults as the feedback
to select types to evict and tiers to protect.


code:
.. _numa:

Started Nov 1999 by Kanoj Sarcar <kanoj@sgi.com>

=============
What is NUMA?
=============

This question can be answered from a couple of perspectives:  the
hardware view and the Linux software view.

From the hardware perspective, a NUMA system is a computer platform that
comprises multiple components or assemblies each of which may contain 0
or more CPUs, local memory, and/or IO buses.  For brevity and to
disambiguate the hardware view of these physical components/assemblies
from the software abstraction thereof, we'll call the components/assemblies
'cells' in this document.

Each of the 'cells' may be viewed as an SMP [symmetric multi-processor] subset
of the system--although some components necessary for a stand-alone SMP system
may not be populated on any given cell.   The cells of the NUMA system are
connected together with some sort of system interconnect--e.g., a crossbar or
point-to-point link are common types of NUMA system interconnects.  Both of
these types of interconnects can be aggregated to create NUMA platforms with
cells at multiple distances from other cells.

For Linux, the NUMA platforms of interest are primarily what is known as Cache
Coherent NUMA or ccNUMA systems.   With ccNUMA systems, all memory is visible
to and accessible from any CPU attached to any cell and cache coherency
is handled in hardware by the processor caches and/or the system interconnect.

Memory access time and effective memory bandwidth varies depending on how far
away the cell containing the CPU or IO bus making the memory access is from the
cell containing the target memory.  For example, access to memory by CPUs
attached to the same cell will experience faster access times and higher
bandwidths than accesses to memory on other, remote cells.  NUMA platforms
can have cells at multiple remote distances from any given cell.

Platform vendors don't build NUMA systems just to make software developers'
lives interesting.  Rather, this architecture is a means to provide scalable
memory bandwidth.  However, to achieve scalable memory bandwidth, system and
application software must arrange for a large majority of the memory references
[cache misses] to be to "local" memory--memory on the same cell, if any--or
to the closest cell with memory.

This leads to the Linux software view of a NUMA system:

Linux divides the system's hardware resources into multiple software
abstractions called "nodes".  Linux maps the nodes onto the physical cells
of the hardware platform, abstracting away some of the details for some
architectures.  As with physical cells, software nodes may contain 0 or more
CPUs, memory and/or IO buses.  And, again, memory accesses to memory on
"closer" nodes--nodes that map to closer cells--will generally experience
faster access times and higher effective bandwidth than accesses to more
remote cells.

For some architectures, such as x86, Linux will "hide" any node representing a
physical cell that has no memory attached, and reassign any CPUs attached to
that cell to a node representing a cell that does have memory.  Thus, on
these architectures, one cannot assume that all CPUs that Linux associates with
a given node will see the same local memory access times and bandwidth.

In addition, for some architectures, again x86 is an example, Linux supports
the emulation of additional nodes.  For NUMA emulation, linux will carve up
the existing nodes--or the system memory for non-NUMA platforms--into multiple
nodes.  Each emulated node will manage a fraction of the underlying cells'
physical memory.  NUMA emluation is useful for testing NUMA kernel and
application features on non-NUMA platforms, and as a sort of memory resource
management mechanism when used together with cpusets.
[see Documentation/admin-guide/cgroup-v1/cpusets.rst]

For each node with memory, Linux constructs an independent memory management
subsystem, complete with its own free page lists, in-use page lists, usage
statistics and locks to mediate access.  In addition, Linux constructs for
each memory zone [one or more of DMA, DMA32, NORMAL, HIGH_MEMORY, MOVABLE],
an ordered "zonelist".  A zonelist specifies the zones/nodes to visit when a
selected zone/node cannot satisfy the allocation request.  This situation,
when a zone has no available memory to satisfy a request, is called
"overflow" or "fallback".

Because some nodes contain multiple zones containing different types of
memory, Linux must decide whether to order the zonelists such that allocations
fall back to the same zone type on a different node, or to a different zone
type on the same node.  This is an important consideration because some zones,
such as DMA or DMA32, represent relatively scarce resources.  Linux chooses
a default Node ordered zonelist. This means it tries to fallback to other zones
from the same node before using remote nodes which are ordered by NUMA distance.

By default, Linux will attempt to satisfy memory allocation requests from the
node to which the CPU that executes the request is assigned.  Specifically,
Linux will attempt to allocate from the first node in the appropriate zonelist
for the node where the request originates.  This is called "local allocation."
If the "local" node cannot satisfy the request, the kernel will examine other
nodes' zones in the selected zonelist looking for the first zone in the list
that can satisfy the request.

Local allocation will tend to keep subsequent access to the allocated memory
"local" to the underlying physical resources and off the system interconnect--
as long as the task on whose behalf the kernel allocated some memory does not
later migrate away from that memory.  The Linux scheduler is aware of the
NUMA topology of the platform--embodied in the "scheduling domains" data
structures [see Documentation/scheduler/sched-domains.rst]--and the scheduler
attempts to minimize task migration to distant scheduling domains.  However,
the scheduler does not take a task's NUMA footprint into account directly.
Thus, under sufficient imbalance, tasks can migrate between nodes, remote
from their initial node and kernel data structures.

System administrators and application designers can restrict a task's migration
to improve NUMA locality using various CPU affinity command line interfaces,
such as taskset(1) and numactl(1), and program interfaces such as
sched_setaffinity(2).  Further, one can modify the kernel's default local
allocation behavior using Linux NUMA memory policy. [see
:ref:`Documentation/admin-guide/mm/numa_memory_policy.rst <numa_memory_policy>`].

System administrators can restrict the CPUs and nodes' memories that a non-
privileged user can specify in the scheduling or NUMA commands and functions
using control groups and CPUsets.  [see Documentation/admin-guide/cgroup-v1/cpusets.rst]

On architectures that do not hide memoryless nodes, Linux will include only
zones [nodes] with memory in the zonelists.  This means that for a memoryless
node the "local memory node"--the node of the first zone in CPU's node's
zonelist--will not be the node itself.  Rather, it will be the node that the
kernel selected as the nearest node with memory when it built the zonelists.
So, default, local allocations will succeed with the kernel supplying the
closest available memory.  This is a consequence of the same mechanism that
allows such allocations to fallback to other nearby nodes when a node that
does contain memory overflows.

Some kernel allocations do not want or cannot tolerate this allocation fallback
behavior.  Rather they want to be sure they get memory from the specified node
or get notified that the node has no free memory.  This is usually the case when
a subsystem allocates per CPU memory resources, for example.

A typical model for making such an allocation is to obtain the node id of the
node to which the "current CPU" is attached using one of the kernel's
numa_node_id() or CPU_to_node() functions and then request memory from only
the node id returned.  When such an allocation fails, the requesting subsystem
may revert to its own fallback path.  The slab kernel memory allocator is an
example of this.  Or, the subsystem may choose to disable or not to enable
itself on allocation failure.  The kernel profiling subsystem is an example of
this.

If the architecture supports--does not hide--memoryless nodes, then CPUs
attached to memoryless nodes would always incur the fallback path overhead
or some subsystems would fail to initialize if they attempted to allocated
memory exclusively from a node without memory.  To support such
architectures transparently, kernel subsystems can use the numa_mem_id()
or cpu_to_mem() function to locate the "local memory node" for the calling or
specified CPU.  Again, this is the same node from which default, local page
allocations will be attempted.


code:
=====================
Overcommit Accounting
=====================

The Linux kernel supports the following overcommit handling modes

0
	Heuristic overcommit handling. Obvious overcommits of address
	space are refused. Used for a typical system. It ensures a
	seriously wild allocation fails while allowing overcommit to
	reduce swap usage.  root is allowed to allocate slightly more
	memory in this mode. This is the default.

1
	Always overcommit. Appropriate for some scientific
	applications. Classic example is code using sparse arrays and
	just relying on the virtual memory consisting almost entirely
	of zero pages.

2
	Don't overcommit. The total address space commit for the
	system is not permitted to exceed swap + a configurable amount
	(default is 50%) of physical RAM.  Depending on the amount you
	use, in most situations this means a process will not be
	killed while accessing pages but will receive errors on memory
	allocation as appropriate.

	Useful for applications that want to guarantee their memory
	allocations will be available in the future without having to
	initialize every page.

The overcommit policy is set via the sysctl ``vm.overcommit_memory``.

The overcommit amount can be set via ``vm.overcommit_ratio`` (percentage)
or ``vm.overcommit_kbytes`` (absolute value). These only have an effect
when ``vm.overcommit_memory`` is set to 2.

The current overcommit limit and amount committed are viewable in
``/proc/meminfo`` as CommitLimit and Committed_AS respectively.

Gotchas
=======

The C language stack growth does an implicit mremap. If you want absolute
guarantees and run close to the edge you MUST mmap your stack for the
largest size you think you will need. For typical stack usage this does
not matter much but it's a corner case if you really really care

In mode 2 the MAP_NORESERVE flag is ignored.

How It Works
============

The overcommit is based on the following rules

For a file backed map
	| SHARED or READ-only	-	0 cost (the file is the map not swap)
	| PRIVATE WRITABLE	-	size of mapping per instance

For an anonymous or ``/dev/zero`` map
	| SHARED			-	size of mapping
	| PRIVATE READ-only	-	0 cost (but of little use)
	| PRIVATE WRITABLE	-	size of mapping per instance

Additional accounting
	| Pages made writable copies by mmap
	| shmfs memory drawn from the same pool

Status
======

*	We account mmap memory mappings
*	We account mprotect changes in commit
*	We account mremap changes in size
*	We account brk
*	We account munmap
*	We report the commit status in /proc
*	Account and check on fork
*	Review stack handling/building on exec
*	SHMfs accounting
*	Implement actual limit enforcement

To Do
=====
*	Account ptrace pages (this is hard)


code:
.. SPDX-License-Identifier: GPL-2.0

==========
Page Cache
==========


code:
.. _page_frags:

==============
Page fragments
==============

A page fragment is an arbitrary-length arbitrary-offset area of memory
which resides within a 0 or higher order compound page.  Multiple
fragments within that page are individually refcounted, in the page's
reference counter.

The page_frag functions, page_frag_alloc and page_frag_free, provide a
simple allocation framework for page fragments.  This is used by the
network stack and network device drivers to provide a backing region of
memory for use as either an sk_buff->head, or to be used in the "frags"
portion of skb_shared_info.

In order to make use of the page fragment APIs a backing page fragment
cache is needed.  This provides a central point for the fragment allocation
and tracks allows multiple calls to make use of a cached page.  The
advantage to doing this is that multiple calls to get_page can be avoided
which can be expensive at allocation time.  However due to the nature of
this caching it is required that any calls to the cache be protected by
either a per-cpu limitation, or a per-cpu limitation and forcing interrupts
to be disabled when executing the fragment allocation.

The network stack uses two separate caches per CPU to handle fragment
allocation.  The netdev_alloc_cache is used by callers making use of the
netdev_alloc_frag and __netdev_alloc_skb calls.  The napi_alloc_cache is
used by callers of the __napi_alloc_frag and __napi_alloc_skb calls.  The
main difference between these two calls is the context in which they may be
called.  The "netdev" prefixed functions are usable in any context as these
functions will disable interrupts, while the "napi" prefixed functions are
only usable within the softirq context.

Many network device drivers use a similar methodology for allocating page
fragments, but the page fragments are cached at the ring or descriptor
level.  In order to enable these cases it is necessary to provide a generic
way of tearing down a page cache.  For this reason __page_frag_cache_drain
was implemented.  It allows for freeing multiple references from a single
page via a single call.  The advantage to doing this is that it allows for
cleaning up the multiple references that were added to a page in order to
avoid calling get_page per allocation.

Alexander Duyck, Nov 29, 2016.


code:
.. _page_migration:

==============
Page migration
==============

Page migration allows moving the physical location of pages between
nodes in a NUMA system while the process is running. This means that the
virtual addresses that the process sees do not change. However, the
system rearranges the physical location of those pages.

Also see :ref:`Heterogeneous Memory Management (HMM) <hmm>`
for migrating pages to or from device private memory.

The main intent of page migration is to reduce the latency of memory accesses
by moving pages near to the processor where the process accessing that memory
is running.

Page migration allows a process to manually relocate the node on which its
pages are located through the MF_MOVE and MF_MOVE_ALL options while setting
a new memory policy via mbind(). The pages of a process can also be relocated
from another process using the sys_migrate_pages() function call. The
migrate_pages() function call takes two sets of nodes and moves pages of a
process that are located on the from nodes to the destination nodes.
Page migration functions are provided by the numactl package by Andi Kleen
(a version later than 0.9.3 is required. Get it from
https://github.com/numactl/numactl.git). numactl provides libnuma
which provides an interface similar to other NUMA functionality for page
migration.  cat ``/proc/<pid>/numa_maps`` allows an easy review of where the
pages of a process are located. See also the numa_maps documentation in the
proc(5) man page.

Manual migration is useful if for example the scheduler has relocated
a process to a processor on a distant node. A batch scheduler or an
administrator may detect the situation and move the pages of the process
nearer to the new processor. The kernel itself only provides
manual page migration support. Automatic page migration may be implemented
through user space processes that move pages. A special function call
"move_pages" allows the moving of individual pages within a process.
For example, A NUMA profiler may obtain a log showing frequent off-node
accesses and may use the result to move pages to more advantageous
locations.

Larger installations usually partition the system using cpusets into
sections of nodes. Paul Jackson has equipped cpusets with the ability to
move pages when a task is moved to another cpuset (See
:ref:`CPUSETS <cpusets>`).
Cpusets allow the automation of process locality. If a task is moved to
a new cpuset then also all its pages are moved with it so that the
performance of the process does not sink dramatically. Also the pages
of processes in a cpuset are moved if the allowed memory nodes of a
cpuset are changed.

Page migration allows the preservation of the relative location of pages
within a group of nodes for all migration techniques which will preserve a
particular memory allocation pattern generated even after migrating a
process. This is necessary in order to preserve the memory latencies.
Processes will run with similar performance after migration.

Page migration occurs in several steps. First a high level
description for those trying to use migrate_pages() from the kernel
(for userspace usage see the Andi Kleen's numactl package mentioned above)
and then a low level description of how the low level details work.

In kernel use of migrate_pages()
================================

1. Remove pages from the LRU.

   Lists of pages to be migrated are generated by scanning over
   pages and moving them into lists. This is done by
   calling isolate_lru_page().
   Calling isolate_lru_page() increases the references to the page
   so that it cannot vanish while the page migration occurs.
   It also prevents the swapper or other scans from encountering
   the page.

2. We need to have a function of type new_page_t that can be
   passed to migrate_pages(). This function should figure out
   how to allocate the correct new page given the old page.

3. The migrate_pages() function is called which attempts
   to do the migration. It will call the function to allocate
   the new page for each page that is considered for
   moving.

How migrate_pages() works
=========================

migrate_pages() does several passes over its list of pages. A page is moved
if all references to a page are removable at the time. The page has
already been removed from the LRU via isolate_lru_page() and the refcount
is increased so that the page cannot be freed while page migration occurs.

Steps:

1. Lock the page to be migrated.

2. Ensure that writeback is complete.

3. Lock the new page that we want to move to. It is locked so that accesses to
   this (not yet up-to-date) page immediately block while the move is in progress.

4. All the page table references to the page are converted to migration
   entries. This decreases the mapcount of a page. If the resulting
   mapcount is not zero then we do not migrate the page. All user space
   processes that attempt to access the page will now wait on the page lock
   or wait for the migration page table entry to be removed.

5. The i_pages lock is taken. This will cause all processes trying
   to access the page via the mapping to block on the spinlock.

6. The refcount of the page is examined and we back out if references remain.
   Otherwise, we know that we are the only one referencing this page.

7. The radix tree is checked and if it does not contain the pointer to this
   page then we back out because someone else modified the radix tree.

8. The new page is prepped with some settings from the old page so that
   accesses to the new page will discover a page with the correct settings.

9. The radix tree is changed to point to the new page.

10. The reference count of the old page is dropped because the address space
    reference is gone. A reference to the new page is established because
    the new page is referenced by the address space.

11. The i_pages lock is dropped. With that lookups in the mapping
    become possible again. Processes will move from spinning on the lock
    to sleeping on the locked new page.

12. The page contents are copied to the new page.

13. The remaining page flags are copied to the new page.

14. The old page flags are cleared to indicate that the page does
    not provide any information anymore.

15. Queued up writeback on the new page is triggered.

16. If migration entries were inserted into the page table, then replace them
    with real ptes. Doing so will enable access for user space processes not
    already waiting for the page lock.

17. The page locks are dropped from the old and new page.
    Processes waiting on the page lock will redo their page faults
    and will reach the new page.

18. The new page is moved to the LRU and can be scanned by the swapper,
    etc. again.

Non-LRU page migration
======================

Although migration originally aimed for reducing the latency of memory
accesses for NUMA, compaction also uses migration to create high-order
pages.  For compaction purposes, it is also useful to be able to move
non-LRU pages, such as zsmalloc and virtio-balloon pages.

If a driver wants to make its pages movable, it should define a struct
movable_operations.  It then needs to call __SetPageMovable() on each
page that it may be able to move.  This uses the ``page->mapping`` field,
so this field is not available for the driver to use for other purposes.

Monitoring Migration
=====================

The following events (counters) can be used to monitor page migration.

1. PGMIGRATE_SUCCESS: Normal page migration success. Each count means that a
   page was migrated. If the page was a non-THP and non-hugetlb page, then
   this counter is increased by one. If the page was a THP or hugetlb, then
   this counter is increased by the number of THP or hugetlb subpages.
   For example, migration of a single 2MB THP that has 4KB-size base pages
   (subpages) will cause this counter to increase by 512.

2. PGMIGRATE_FAIL: Normal page migration failure. Same counting rules as for
   PGMIGRATE_SUCCESS, above: this will be increased by the number of subpages,
   if it was a THP or hugetlb.

3. THP_MIGRATION_SUCCESS: A THP was migrated without being split.

4. THP_MIGRATION_FAIL: A THP could not be migrated nor it could be split.

5. THP_MIGRATION_SPLIT: A THP was migrated, but not as such: first, the THP had
   to be split. After splitting, a migration retry was used for it's sub-pages.

THP_MIGRATION_* events also update the appropriate PGMIGRATE_SUCCESS or
PGMIGRATE_FAIL events. For example, a THP migration failure will cause both
THP_MIGRATION_FAIL and PGMIGRATE_FAIL to increase.

Christoph Lameter, May 8, 2006.
Minchan Kim, Mar 28, 2016.

.. kernel-doc:: include/linux/migrate.h


code:
.. _page_owner:

==================================================
page owner: Tracking about who allocated each page
==================================================

Introduction
============

page owner is for the tracking about who allocated each page.
It can be used to debug memory leak or to find a memory hogger.
When allocation happens, information about allocation such as call stack
and order of pages is stored into certain storage for each page.
When we need to know about status of all pages, we can get and analyze
this information.

Although we already have tracepoint for tracing page allocation/free,
using it for analyzing who allocate each page is rather complex. We need
to enlarge the trace buffer for preventing overlapping until userspace
program launched. And, launched program continually dump out the trace
buffer for later analysis and it would change system behaviour with more
possibility rather than just keeping it in memory, so bad for debugging.

page owner can also be used for various purposes. For example, accurate
fragmentation statistics can be obtained through gfp flag information of
each page. It is already implemented and activated if page owner is
enabled. Other usages are more than welcome.

page owner is disabled by default. So, if you'd like to use it, you need
to add "page_owner=on" to your boot cmdline. If the kernel is built
with page owner and page owner is disabled in runtime due to not enabling
boot option, runtime overhead is marginal. If disabled in runtime, it
doesn't require memory to store owner information, so there is no runtime
memory overhead. And, page owner inserts just two unlikely branches into
the page allocator hotpath and if not enabled, then allocation is done
like as the kernel without page owner. These two unlikely branches should
not affect to allocation performance, especially if the static keys jump
label patching functionality is available. Following is the kernel's code
size change due to this facility.

Although enabling page owner increases kernel size by several kilobytes,
most of this code is outside page allocator and its hot path. Building
the kernel with page owner and turning it on if needed would be great
option to debug kernel memory problem.

There is one notice that is caused by implementation detail. page owner
stores information into the memory from struct page extension. This memory
is initialized some time later than that page allocator starts in sparse
memory system, so, until initialization, many pages can be allocated and
they would have no owner information. To fix it up, these early allocated
pages are investigated and marked as allocated in initialization phase.
Although it doesn't mean that they have the right owner information,
at least, we can tell whether the page is allocated or not,
more accurately. On 2GB memory x86-64 VM box, 13343 early allocated pages
are catched and marked, although they are mostly allocated from struct
page extension feature. Anyway, after that, no page is left in
un-tracking state.

Usage
=====

1) Build user-space helper::

	cd tools/vm
	make page_owner_sort

2) Enable page owner: add "page_owner=on" to boot cmdline.

3) Do the job that you want to debug.

4) Analyze information from page owner::

	cat /sys/kernel/debug/page_owner > page_owner_full.txt
	./page_owner_sort page_owner_full.txt sorted_page_owner.txt

   The general output of ``page_owner_full.txt`` is as follows::

	Page allocated via order XXX, ...
	PFN XXX ...
	// Detailed stack

	Page allocated via order XXX, ...
	PFN XXX ...
	// Detailed stack
    By default, it will do full pfn dump, to start with a given pfn,
    page_owner supports fseek.

    FILE *fp = fopen("/sys/kernel/debug/page_owner", "r");
    fseek(fp, pfn_start, SEEK_SET);

   The ``page_owner_sort`` tool ignores ``PFN`` rows, puts the remaining rows
   in buf, uses regexp to extract the page order value, counts the times
   and pages of buf, and finally sorts them according to the parameter(s).

   See the result about who allocated each page
   in the ``sorted_page_owner.txt``. General output::

	XXX times, XXX pages:
	Page allocated via order XXX, ...
	// Detailed stack

   By default, ``page_owner_sort`` is sorted according to the times of buf.
   If you want to sort by the page nums of buf, use the ``-m`` parameter.
   The detailed parameters are:

   fundamental function::

	Sort:
		-a		Sort by memory allocation time.
		-m		Sort by total memory.
		-p		Sort by pid.
		-P		Sort by tgid.
		-n		Sort by task command name.
		-r		Sort by memory release time.
		-s		Sort by stack trace.
		-t		Sort by times (default).
		--sort <order>	Specify sorting order.  Sorting syntax is [+|-]key[,[+|-]key[,...]].
				Choose a key from the **STANDARD FORMAT SPECIFIERS** section. The "+" is
				optional since default direction is increasing numerical or lexicographic
				order. Mixed use of abbreviated and complete-form of keys is allowed.

		Examples:
				./page_owner_sort <input> <output> --sort=n,+pid,-tgid
				./page_owner_sort <input> <output> --sort=at

   additional function::

	Cull:
		--cull <rules>
				Specify culling rules.Culling syntax is key[,key[,...]].Choose a
				multi-letter key from the **STANDARD FORMAT SPECIFIERS** section.

		<rules> is a single argument in the form of a comma-separated list,
		which offers a way to specify individual culling rules.  The recognized
		keywords are described in the **STANDARD FORMAT SPECIFIERS** section below.
		<rules> can be specified by the sequence of keys k1,k2, ..., as described in
		the STANDARD SORT KEYS section below. Mixed use of abbreviated and
		complete-form of keys is allowed.

		Examples:
				./page_owner_sort <input> <output> --cull=stacktrace
				./page_owner_sort <input> <output> --cull=st,pid,name
				./page_owner_sort <input> <output> --cull=n,f

	Filter:
		-f		Filter out the information of blocks whose memory has been released.

	Select:
		--pid <pidlist>		Select by pid. This selects the blocks whose process ID
					numbers appear in <pidlist>.
		--tgid <tgidlist>	Select by tgid. This selects the blocks whose thread
					group ID numbers appear in <tgidlist>.
		--name <cmdlist>	Select by task command name. This selects the blocks whose
					task command name appear in <cmdlist>.

		<pidlist>, <tgidlist>, <cmdlist> are single arguments in the form of a comma-separated list,
		which offers a way to specify individual selecting rules.

		Examples:
				./page_owner_sort <input> <output> --pid=1
				./page_owner_sort <input> <output> --tgid=1,2,3
				./page_owner_sort <input> <output> --name name1,name2

STANDARD FORMAT SPECIFIERS
==========================
::

  For --sort option:

	KEY		LONG		DESCRIPTION
	p		pid		process ID
	tg		tgid		thread group ID
	n		name		task command name
	st		stacktrace	stack trace of the page allocation
	T		txt		full text of block
	ft		free_ts		timestamp of the page when it was released
	at		alloc_ts	timestamp of the page when it was allocated
	ator		allocator	memory allocator for pages

  For --curl option:

	KEY		LONG		DESCRIPTION
	p		pid		process ID
	tg		tgid		thread group ID
	n		name		task command name
	f		free		whether the page has been released or not
	st		stacktrace	stack trace of the page allocation
	ator		allocator	memory allocator for pages


code:
.. SPDX-License-Identifier: GPL-2.0

============
Page Reclaim
============


code:
.. SPDX-License-Identifier: GPL-2.0

.. _page_table_check:

================
Page Table Check
================

Introduction
============

Page table check allows to harden the kernel by ensuring that some types of
the memory corruptions are prevented.

Page table check performs extra verifications at the time when new pages become
accessible from the userspace by getting their page table entries (PTEs PMDs
etc.) added into the table.

In case of detected corruption, the kernel is crashed. There is a small
performance and memory overhead associated with the page table check. Therefore,
it is disabled by default, but can be optionally enabled on systems where the
extra hardening outweighs the performance costs. Also, because page table check
is synchronous, it can help with debugging double map memory corruption issues,
by crashing kernel at the time wrong mapping occurs instead of later which is
often the case with memory corruptions bugs.

Double mapping detection logic
==============================

+-------------------+-------------------+-------------------+------------------+
| Current Mapping   | New mapping       | Permissions       | Rule             |
+===================+===================+===================+==================+
| Anonymous         | Anonymous         | Read              | Allow            |
+-------------------+-------------------+-------------------+------------------+
| Anonymous         | Anonymous         | Read / Write      | Prohibit         |
+-------------------+-------------------+-------------------+------------------+
| Anonymous         | Named             | Any               | Prohibit         |
+-------------------+-------------------+-------------------+------------------+
| Named             | Anonymous         | Any               | Prohibit         |
+-------------------+-------------------+-------------------+------------------+
| Named             | Named             | Any               | Allow            |
+-------------------+-------------------+-------------------+------------------+

Enabling Page Table Check
=========================

Build kernel with:

- PAGE_TABLE_CHECK=y
  Note, it can only be enabled on platforms where ARCH_SUPPORTS_PAGE_TABLE_CHECK
  is available.

- Boot with 'page_table_check=on' kernel parameter.

Optionally, build kernel with PAGE_TABLE_CHECK_ENFORCED in order to have page
table support without extra kernel parameter.


code:
.. SPDX-License-Identifier: GPL-2.0

===========
Page Tables
===========


code:
.. _remap_file_pages:

==============================
remap_file_pages() system call
==============================

The remap_file_pages() system call is used to create a nonlinear mapping,
that is, a mapping in which the pages of the file are mapped into a
nonsequential order in memory. The advantage of using remap_file_pages()
over using repeated calls to mmap(2) is that the former approach does not
require the kernel to create additional VMA (Virtual Memory Area) data
structures.

Supporting of nonlinear mapping requires significant amount of non-trivial
code in kernel virtual memory subsystem including hot paths. Also to get
nonlinear mapping work kernel need a way to distinguish normal page table
entries from entries with file offset (pte_file). Kernel reserves flag in
PTE for this purpose. PTE flags are scarce resource especially on some CPU
architectures. It would be nice to free up the flag for other usage.

Fortunately, there are not many users of remap_file_pages() in the wild.
It's only known that one enterprise RDBMS implementation uses the syscall
on 32-bit systems to map files bigger than can linearly fit into 32-bit
virtual address space. This use-case is not critical anymore since 64-bit
systems are widely available.

The syscall is deprecated and replaced it with an emulation now. The
emulation creates new VMAs instead of nonlinear mappings. It's going to
work slower for rare users of remap_file_pages() but ABI is preserved.

One side effect of emulation (apart from performance) is that user can hit
vm.max_map_count limit more easily due to additional VMAs. See comment for
DEFAULT_MAX_MAP_COUNT for more details on the limit.


code:
.. _slub:

==========================
Short users guide for SLUB
==========================

The basic philosophy of SLUB is very different from SLAB. SLAB
requires rebuilding the kernel to activate debug options for all
slab caches. SLUB always includes full debugging but it is off by default.
SLUB can enable debugging only for selected slabs in order to avoid
an impact on overall system performance which may make a bug more
difficult to find.

In order to switch debugging on one can add an option ``slub_debug``
to the kernel command line. That will enable full debugging for
all slabs.

Typically one would then use the ``slabinfo`` command to get statistical
data and perform operation on the slabs. By default ``slabinfo`` only lists
slabs that have data in them. See "slabinfo -h" for more options when
running the command. ``slabinfo`` can be compiled with
::

	gcc -o slabinfo tools/vm/slabinfo.c

Some of the modes of operation of ``slabinfo`` require that slub debugging
be enabled on the command line. F.e. no tracking information will be
available without debugging on and validation can only partially
be performed if debugging was not switched on.

Some more sophisticated uses of slub_debug:
-------------------------------------------

Parameters may be given to ``slub_debug``. If none is specified then full
debugging is enabled. Format:

slub_debug=<Debug-Options>
	Enable options for all slabs

slub_debug=<Debug-Options>,<slab name1>,<slab name2>,...
	Enable options only for select slabs (no spaces
	after a comma)

Multiple blocks of options for all slabs or selected slabs can be given, with
blocks of options delimited by ';'. The last of "all slabs" blocks is applied
to all slabs except those that match one of the "select slabs" block. Options
of the first "select slabs" blocks that matches the slab's name are applied.

Possible debug options are::

	F		Sanity checks on (enables SLAB_DEBUG_CONSISTENCY_CHECKS
			Sorry SLAB legacy issues)
	Z		Red zoning
	P		Poisoning (object and padding)
	U		User tracking (free and alloc)
	T		Trace (please only use on single slabs)
	A		Enable failslab filter mark for the cache
	O		Switch debugging off for caches that would have
			caused higher minimum slab orders
	-		Switch all debugging off (useful if the kernel is
			configured with CONFIG_SLUB_DEBUG_ON)

F.e. in order to boot just with sanity checks and red zoning one would specify::

	slub_debug=FZ

Trying to find an issue in the dentry cache? Try::

	slub_debug=,dentry

to only enable debugging on the dentry cache.  You may use an asterisk at the
end of the slab name, in order to cover all slabs with the same prefix.  For
example, here's how you can poison the dentry cache as well as all kmalloc
slabs::

	slub_debug=P,kmalloc-*,dentry

Red zoning and tracking may realign the slab.  We can just apply sanity checks
to the dentry cache with::

	slub_debug=F,dentry

Debugging options may require the minimum possible slab order to increase as
a result of storing the metadata (for example, caches with PAGE_SIZE object
sizes).  This has a higher liklihood of resulting in slab allocation errors
in low memory situations or if there's high fragmentation of memory.  To
switch off debugging for such caches by default, use::

	slub_debug=O

You can apply different options to different list of slab names, using blocks
of options. This will enable red zoning for dentry and user tracking for
kmalloc. All other slabs will not get any debugging enabled::

	slub_debug=Z,dentry;U,kmalloc-*

You can also enable options (e.g. sanity checks and poisoning) for all caches
except some that are deemed too performance critical and don't need to be
debugged by specifying global debug options followed by a list of slab names
with "-" as options::

	slub_debug=FZ;-,zs_handle,zspage

The state of each debug option for a slab can be found in the respective files
under::

	/sys/kernel/slab/<slab name>/

If the file contains 1, the option is enabled, 0 means disabled. The debug
options from the ``slub_debug`` parameter translate to the following files::

	F	sanity_checks
	Z	red_zone
	P	poison
	U	store_user
	T	trace
	A	failslab

failslab file is writable, so writing 1 or 0 will enable or disable
the option at runtime. Write returns -EINVAL if cache is an alias.
Careful with tracing: It may spew out lots of information and never stop if
used on the wrong slab.

Slab merging
============

If no debug options are specified then SLUB may merge similar slabs together
in order to reduce overhead and increase cache hotness of objects.
``slabinfo -a`` displays which slabs were merged together.

Slab validation
===============

SLUB can validate all object if the kernel was booted with slub_debug. In
order to do so you must have the ``slabinfo`` tool. Then you can do
::

	slabinfo -v

which will test all objects. Output will be generated to the syslog.

This also works in a more limited way if boot was without slab debug.
In that case ``slabinfo -v`` simply tests all reachable objects. Usually
these are in the cpu slabs and the partial slabs. Full slabs are not
tracked by SLUB in a non debug situation.

Getting more performance
========================

To some degree SLUB's performance is limited by the need to take the
list_lock once in a while to deal with partial slabs. That overhead is
governed by the order of the allocation for each slab. The allocations
can be influenced by kernel parameters:

.. slub_min_objects=x		(default 4)
.. slub_min_order=x		(default 0)
.. slub_max_order=x		(default 3 (PAGE_ALLOC_COSTLY_ORDER))

``slub_min_objects``
	allows to specify how many objects must at least fit into one
	slab in order for the allocation order to be acceptable.  In
	general slub will be able to perform this number of
	allocations on a slab without consulting centralized resources
	(list_lock) where contention may occur.

``slub_min_order``
	specifies a minimum order of slabs. A similar effect like
	``slub_min_objects``.

``slub_max_order``
	specified the order at which ``slub_min_objects`` should no
	longer be checked. This is useful to avoid SLUB trying to
	generate super large order pages to fit ``slub_min_objects``
	of a slab cache with large object sizes into one high order
	page. Setting command line parameter
	``debug_guardpage_minorder=N`` (N > 0), forces setting
	``slub_max_order`` to 0, what cause minimum possible order of
	slabs allocation.

SLUB Debug output
=================

Here is a sample of slub debug output::

 ====================================================================
 BUG kmalloc-8: Right Redzone overwritten
 --------------------------------------------------------------------

 INFO: 0xc90f6d28-0xc90f6d2b. First byte 0x00 instead of 0xcc
 INFO: Slab 0xc528c530 flags=0x400000c3 inuse=61 fp=0xc90f6d58
 INFO: Object 0xc90f6d20 @offset=3360 fp=0xc90f6d58
 INFO: Allocated in get_modalias+0x61/0xf5 age=53 cpu=1 pid=554

 Bytes b4 (0xc90f6d10): 00 00 00 00 00 00 00 00 5a 5a 5a 5a 5a 5a 5a 5a ........ZZZZZZZZ
 Object   (0xc90f6d20): 31 30 31 39 2e 30 30 35                         1019.005
 Redzone  (0xc90f6d28): 00 cc cc cc                                     .
 Padding  (0xc90f6d50): 5a 5a 5a 5a 5a 5a 5a 5a                         ZZZZZZZZ

   [<c010523d>] dump_trace+0x63/0x1eb
   [<c01053df>] show_trace_log_lvl+0x1a/0x2f
   [<c010601d>] show_trace+0x12/0x14
   [<c0106035>] dump_stack+0x16/0x18
   [<c017e0fa>] object_err+0x143/0x14b
   [<c017e2cc>] check_object+0x66/0x234
   [<c017eb43>] __slab_free+0x239/0x384
   [<c017f446>] kfree+0xa6/0xc6
   [<c02e2335>] get_modalias+0xb9/0xf5
   [<c02e23b7>] dmi_dev_uevent+0x27/0x3c
   [<c027866a>] dev_uevent+0x1ad/0x1da
   [<c0205024>] kobject_uevent_env+0x20a/0x45b
   [<c020527f>] kobject_uevent+0xa/0xf
   [<c02779f1>] store_uevent+0x4f/0x58
   [<c027758e>] dev_attr_store+0x29/0x2f
   [<c01bec4f>] sysfs_write_file+0x16e/0x19c
   [<c0183ba7>] vfs_write+0xd1/0x15a
   [<c01841d7>] sys_write+0x3d/0x72
   [<c0104112>] sysenter_past_esp+0x5f/0x99
   [<b7f7b410>] 0xb7f7b410
   =======================

 FIX kmalloc-8: Restoring Redzone 0xc90f6d28-0xc90f6d2b=0xcc

If SLUB encounters a corrupted object (full detection requires the kernel
to be booted with slub_debug) then the following output will be dumped
into the syslog:

1. Description of the problem encountered

   This will be a message in the system log starting with::

     ===============================================
     BUG <slab cache affected>: <What went wrong>
     -----------------------------------------------

     INFO: <corruption start>-<corruption_end> <more info>
     INFO: Slab <address> <slab information>
     INFO: Object <address> <object information>
     INFO: Allocated in <kernel function> age=<jiffies since alloc> cpu=<allocated by
	cpu> pid=<pid of the process>
     INFO: Freed in <kernel function> age=<jiffies since free> cpu=<freed by cpu>
	pid=<pid of the process>

   (Object allocation / free information is only available if SLAB_STORE_USER is
   set for the slab. slub_debug sets that option)

2. The object contents if an object was involved.

   Various types of lines can follow the BUG SLUB line:

   Bytes b4 <address> : <bytes>
	Shows a few bytes before the object where the problem was detected.
	Can be useful if the corruption does not stop with the start of the
	object.

   Object <address> : <bytes>
	The bytes of the object. If the object is inactive then the bytes
	typically contain poison values. Any non-poison value shows a
	corruption by a write after free.

   Redzone <address> : <bytes>
	The Redzone following the object. The Redzone is used to detect
	writes after the object. All bytes should always have the same
	value. If there is any deviation then it is due to a write after
	the object boundary.

	(Redzone information is only available if SLAB_RED_ZONE is set.
	slub_debug sets that option)

   Padding <address> : <bytes>
	Unused data to fill up the space in order to get the next object
	properly aligned. In the debug case we make sure that there are
	at least 4 bytes of padding. This allows the detection of writes
	before the object.

3. A stackdump

   The stackdump describes the location where the error was detected. The cause
   of the corruption is may be more likely found by looking at the function that
   allocated or freed the object.

4. Report on how the problem was dealt with in order to ensure the continued
   operation of the system.

   These are messages in the system log beginning with::

	FIX <slab cache affected>: <corrective action taken>

   In the above sample SLUB found that the Redzone of an active object has
   been overwritten. Here a string of 8 characters was written into a slab that
   has the length of 8 characters. However, a 8 character string needs a
   terminating 0. That zero has overwritten the first byte of the Redzone field.
   After reporting the details of the issue encountered the FIX SLUB message
   tells us that SLUB has restored the Redzone to its proper value and then
   system operations continue.

Emergency operations
====================

Minimal debugging (sanity checks alone) can be enabled by booting with::

	slub_debug=F

This will be generally be enough to enable the resiliency features of slub
which will keep the system running even if a bad kernel component will
keep corrupting objects. This may be important for production systems.
Performance will be impacted by the sanity checks and there will be a
continual stream of error messages to the syslog but no additional memory
will be used (unlike full debugging).

No guarantees. The kernel component still needs to be fixed. Performance
may be optimized further by locating the slab that experiences corruption
and enabling debugging only for that cache

I.e.::

	slub_debug=F,dentry

If the corruption occurs by writing after the end of the object then it
may be advisable to enable a Redzone to avoid corrupting the beginning
of other objects::

	slub_debug=FZ,dentry

Extended slabinfo mode and plotting
===================================

The ``slabinfo`` tool has a special 'extended' ('-X') mode that includes:
 - Slabcache Totals
 - Slabs sorted by size (up to -N <num> slabs, default 1)
 - Slabs sorted by loss (up to -N <num> slabs, default 1)

Additionally, in this mode ``slabinfo`` does not dynamically scale
sizes (G/M/K) and reports everything in bytes (this functionality is
also available to other slabinfo modes via '-B' option) which makes
reporting more precise and accurate. Moreover, in some sense the `-X'
mode also simplifies the analysis of slabs' behaviour, because its
output can be plotted using the ``slabinfo-gnuplot.sh`` script. So it
pushes the analysis from looking through the numbers (tons of numbers)
to something easier -- visual analysis.

To generate plots:

a) collect slabinfo extended records, for example::

	while [ 1 ]; do slabinfo -X >> FOO_STATS; sleep 1; done

b) pass stats file(-s) to ``slabinfo-gnuplot.sh`` script::

	slabinfo-gnuplot.sh FOO_STATS [FOO_STATS2 .. FOO_STATSN]

   The ``slabinfo-gnuplot.sh`` script will pre-processes the collected records
   and generates 3 png files (and 3 pre-processing cache files) per STATS
   file:
   - Slabcache Totals: FOO_STATS-totals.png
   - Slabs sorted by size: FOO_STATS-slabs-by-size.png
   - Slabs sorted by loss: FOO_STATS-slabs-by-loss.png

Another use case, when ``slabinfo-gnuplot.sh`` can be useful, is when you
need to compare slabs' behaviour "prior to" and "after" some code
modification.  To help you out there, ``slabinfo-gnuplot.sh`` script
can 'merge' the `Slabcache Totals` sections from different
measurements. To visually compare N plots:

a) Collect as many STATS1, STATS2, .. STATSN files as you need::

	while [ 1 ]; do slabinfo -X >> STATS<X>; sleep 1; done

b) Pre-process those STATS files::

	slabinfo-gnuplot.sh STATS1 STATS2 .. STATSN

c) Execute ``slabinfo-gnuplot.sh`` in '-t' mode, passing all of the
   generated pre-processed \*-totals::

	slabinfo-gnuplot.sh -t STATS1-totals STATS2-totals .. STATSN-totals

   This will produce a single plot (png file).

   Plots, expectedly, can be large so some fluctuations or small spikes
   can go unnoticed. To deal with that, ``slabinfo-gnuplot.sh`` has two
   options to 'zoom-in'/'zoom-out':

   a) ``-s %d,%d`` -- overwrites the default image width and height
   b) ``-r %d,%d`` -- specifies a range of samples to use (for example,
      in ``slabinfo -X >> FOO_STATS; sleep 1;`` case, using a ``-r
      40,60`` range will plot only samples collected between 40th and
      60th seconds).

DebugFS files for SLUB
======================

For more information about current state of SLUB caches with the user tracking
debug option enabled, debugfs files are available, typically under
/sys/kernel/debug/slab/<cache>/ (created only for caches with enabled user
tracking). There are 2 types of these files with the following debug
information:

1. alloc_traces::

    Prints information about unique allocation traces of the currently
    allocated objects. The output is sorted by frequency of each trace.

    Information in the output:
    Number of objects, allocating function, possible memory wastage of
    kmalloc objects(total/per-object), minimal/average/maximal jiffies
    since alloc, pid range of the allocating processes, cpu mask of
    allocating cpus, numa node mask of origins of memory, and stack trace.

    Example:::

    338 pci_alloc_dev+0x2c/0xa0 waste=521872/1544 age=290837/291891/293509 pid=1 cpus=106 nodes=0-1
        __kmem_cache_alloc_node+0x11f/0x4e0
        kmalloc_trace+0x26/0xa0
        pci_alloc_dev+0x2c/0xa0
        pci_scan_single_device+0xd2/0x150
        pci_scan_slot+0xf7/0x2d0
        pci_scan_child_bus_extend+0x4e/0x360
        acpi_pci_root_create+0x32e/0x3b0
        pci_acpi_scan_root+0x2b9/0x2d0
        acpi_pci_root_add.cold.11+0x110/0xb0a
        acpi_bus_attach+0x262/0x3f0
        device_for_each_child+0xb7/0x110
        acpi_dev_for_each_child+0x77/0xa0
        acpi_bus_attach+0x108/0x3f0
        device_for_each_child+0xb7/0x110
        acpi_dev_for_each_child+0x77/0xa0
        acpi_bus_attach+0x108/0x3f0

2. free_traces::

    Prints information about unique freeing traces of the currently allocated
    objects. The freeing traces thus come from the previous life-cycle of the
    objects and are reported as not available for objects allocated for the first
    time. The output is sorted by frequency of each trace.

    Information in the output:
    Number of objects, freeing function, minimal/average/maximal jiffies since free,
    pid range of the freeing processes, cpu mask of freeing cpus, and stack trace.

    Example:::

    1980 <not-available> age=4294912290 pid=0 cpus=0
    51 acpi_ut_update_ref_count+0x6a6/0x782 age=236886/237027/237772 pid=1 cpus=1
	kfree+0x2db/0x420
	acpi_ut_update_ref_count+0x6a6/0x782
	acpi_ut_update_object_reference+0x1ad/0x234
	acpi_ut_remove_reference+0x7d/0x84
	acpi_rs_get_prt_method_data+0x97/0xd6
	acpi_get_irq_routing_table+0x82/0xc4
	acpi_pci_irq_find_prt_entry+0x8e/0x2e0
	acpi_pci_irq_lookup+0x3a/0x1e0
	acpi_pci_irq_enable+0x77/0x240
	pcibios_enable_device+0x39/0x40
	do_pci_enable_device.part.0+0x5d/0xe0
	pci_enable_device_flags+0xfc/0x120
	pci_enable_device+0x13/0x20
	virtio_pci_probe+0x9e/0x170
	local_pci_probe+0x48/0x80
	pci_device_probe+0x105/0x1c0

Christoph Lameter, May 30, 2007
Sergey Senozhatsky, October 23, 2015


code:
.. _split_page_table_lock:

=====================
Split page table lock
=====================

Originally, mm->page_table_lock spinlock protected all page tables of the
mm_struct. But this approach leads to poor page fault scalability of
multi-threaded applications due high contention on the lock. To improve
scalability, split page table lock was introduced.

With split page table lock we have separate per-table lock to serialize
access to the table. At the moment we use split lock for PTE and PMD
tables. Access to higher level tables protected by mm->page_table_lock.

There are helpers to lock/unlock a table and other accessor functions:

 - pte_offset_map_lock()
	maps pte and takes PTE table lock, returns pointer to the taken
	lock;
 - pte_unmap_unlock()
	unlocks and unmaps PTE table;
 - pte_alloc_map_lock()
	allocates PTE table if needed and take the lock, returns pointer
	to taken lock or NULL if allocation failed;
 - pte_lockptr()
	returns pointer to PTE table lock;
 - pmd_lock()
	takes PMD table lock, returns pointer to taken lock;
 - pmd_lockptr()
	returns pointer to PMD table lock;

Split page table lock for PTE tables is enabled compile-time if
CONFIG_SPLIT_PTLOCK_CPUS (usually 4) is less or equal to NR_CPUS.
If split lock is disabled, all tables are guarded by mm->page_table_lock.

Split page table lock for PMD tables is enabled, if it's enabled for PTE
tables and the architecture supports it (see below).

Hugetlb and split page table lock
=================================

Hugetlb can support several page sizes. We use split lock only for PMD
level, but not for PUD.

Hugetlb-specific helpers:

 - huge_pte_lock()
	takes pmd split lock for PMD_SIZE page, mm->page_table_lock
	otherwise;
 - huge_pte_lockptr()
	returns pointer to table lock;

Support of split page table lock by an architecture
===================================================

There's no need in special enabling of PTE split page table lock: everything
required is done by pgtable_pte_page_ctor() and pgtable_pte_page_dtor(), which
must be called on PTE table allocation / freeing.

Make sure the architecture doesn't use slab allocator for page table
allocation: slab uses page->slab_cache for its pages.
This field shares storage with page->ptl.

PMD split lock only makes sense if you have more than two page table
levels.

PMD split lock enabling requires pgtable_pmd_page_ctor() call on PMD table
allocation and pgtable_pmd_page_dtor() on freeing.

Allocation usually happens in pmd_alloc_one(), freeing in pmd_free() and
pmd_free_tlb(), but make sure you cover all PMD table allocation / freeing
paths: i.e X86_PAE preallocate few PMDs on pgd_alloc().

With everything in place you can set CONFIG_ARCH_ENABLE_SPLIT_PMD_PTLOCK.

NOTE: pgtable_pte_page_ctor() and pgtable_pmd_page_ctor() can fail -- it must
be handled properly.

page->ptl
=========

page->ptl is used to access split page table lock, where 'page' is struct
page of page containing the table. It shares storage with page->private
(and few other fields in union).

To avoid increasing size of struct page and have best performance, we use a
trick:

 - if spinlock_t fits into long, we use page->ptr as spinlock, so we
   can avoid indirect access and save a cache line.
 - if size of spinlock_t is bigger then size of long, we use page->ptl as
   pointer to spinlock_t and allocate it dynamically. This allows to use
   split lock with enabled DEBUG_SPINLOCK or DEBUG_LOCK_ALLOC, but costs
   one more cache line for indirect access;

The spinlock_t allocated in pgtable_pte_page_ctor() for PTE table and in
pgtable_pmd_page_ctor() for PMD table.

Please, never access page->ptl directly -- use appropriate helper.


code:
.. SPDX-License-Identifier: GPL-2.0

====
Swap
====


code:
.. _transhuge:

============================
Transparent Hugepage Support
============================

This document describes design principles for Transparent Hugepage (THP)
support and its interaction with other parts of the memory management
system.

Design principles
=================

- "graceful fallback": mm components which don't have transparent hugepage
  knowledge fall back to breaking huge pmd mapping into table of ptes and,
  if necessary, split a transparent hugepage. Therefore these components
  can continue working on the regular pages or regular pte mappings.

- if a hugepage allocation fails because of memory fragmentation,
  regular pages should be gracefully allocated instead and mixed in
  the same vma without any failure or significant delay and without
  userland noticing

- if some task quits and more hugepages become available (either
  immediately in the buddy or through the VM), guest physical memory
  backed by regular pages should be relocated on hugepages
  automatically (with khugepaged)

- it doesn't require memory reservation and in turn it uses hugepages
  whenever possible (the only possible reservation here is kernelcore=
  to avoid unmovable pages to fragment all the memory but such a tweak
  is not specific to transparent hugepage support and it's a generic
  feature that applies to all dynamic high order allocations in the
  kernel)

get_user_pages and follow_page
==============================

get_user_pages and follow_page if run on a hugepage, will return the
head or tail pages as usual (exactly as they would do on
hugetlbfs). Most GUP users will only care about the actual physical
address of the page and its temporary pinning to release after the I/O
is complete, so they won't ever notice the fact the page is huge. But
if any driver is going to mangle over the page structure of the tail
page (like for checking page->mapping or other bits that are relevant
for the head page and not the tail page), it should be updated to jump
to check head page instead. Taking a reference on any head/tail page would
prevent the page from being split by anyone.

.. note::
   these aren't new constraints to the GUP API, and they match the
   same constraints that apply to hugetlbfs too, so any driver capable
   of handling GUP on hugetlbfs will also work fine on transparent
   hugepage backed mappings.

Graceful fallback
=================

Code walking pagetables but unaware about huge pmds can simply call
split_huge_pmd(vma, pmd, addr) where the pmd is the one returned by
pmd_offset. It's trivial to make the code transparent hugepage aware
by just grepping for "pmd_offset" and adding split_huge_pmd where
missing after pmd_offset returns the pmd. Thanks to the graceful
fallback design, with a one liner change, you can avoid to write
hundreds if not thousands of lines of complex code to make your code
hugepage aware.

If you're not walking pagetables but you run into a physical hugepage
that you can't handle natively in your code, you can split it by
calling split_huge_page(page). This is what the Linux VM does before
it tries to swapout the hugepage for example. split_huge_page() can fail
if the page is pinned and you must handle this correctly.

Example to make mremap.c transparent hugepage aware with a one liner
change::

	diff --git a/mm/mremap.c b/mm/mremap.c
	--- a/mm/mremap.c
	+++ b/mm/mremap.c
	@@ -41,6 +41,7 @@ static pmd_t *get_old_pmd(struct mm_stru
			return NULL;

		pmd = pmd_offset(pud, addr);
	+	split_huge_pmd(vma, pmd, addr);
		if (pmd_none_or_clear_bad(pmd))
			return NULL;

Locking in hugepage aware code
==============================

We want as much code as possible hugepage aware, as calling
split_huge_page() or split_huge_pmd() has a cost.

To make pagetable walks huge pmd aware, all you need to do is to call
pmd_trans_huge() on the pmd returned by pmd_offset. You must hold the
mmap_lock in read (or write) mode to be sure a huge pmd cannot be
created from under you by khugepaged (khugepaged collapse_huge_page
takes the mmap_lock in write mode in addition to the anon_vma lock). If
pmd_trans_huge returns false, you just fallback in the old code
paths. If instead pmd_trans_huge returns true, you have to take the
page table lock (pmd_lock()) and re-run pmd_trans_huge. Taking the
page table lock will prevent the huge pmd being converted into a
regular pmd from under you (split_huge_pmd can run in parallel to the
pagetable walk). If the second pmd_trans_huge returns false, you
should just drop the page table lock and fallback to the old code as
before. Otherwise, you can proceed to process the huge pmd and the
hugepage natively. Once finished, you can drop the page table lock.

Refcounts and transparent huge pages
====================================

Refcounting on THP is mostly consistent with refcounting on other compound
pages:

  - get_page()/put_page() and GUP operate on head page's ->_refcount.

  - ->_refcount in tail pages is always zero: get_page_unless_zero() never
    succeeds on tail pages.

  - map/unmap of PMD entry for the whole compound page increment/decrement
    ->compound_mapcount, stored in the first tail page of the compound page;
    and also increment/decrement ->subpages_mapcount (also in the first tail)
    by COMPOUND_MAPPED when compound_mapcount goes from -1 to 0 or 0 to -1.

  - map/unmap of sub-pages with PTE entry increment/decrement ->_mapcount
    on relevant sub-page of the compound page, and also increment/decrement
    ->subpages_mapcount, stored in first tail page of the compound page, when
    _mapcount goes from -1 to 0 or 0 to -1: counting sub-pages mapped by PTE.

split_huge_page internally has to distribute the refcounts in the head
page to the tail pages before clearing all PG_head/tail bits from the page
structures. It can be done easily for refcounts taken by page table
entries, but we don't have enough information on how to distribute any
additional pins (i.e. from get_user_pages). split_huge_page() fails any
requests to split pinned huge pages: it expects page count to be equal to
the sum of mapcount of all sub-pages plus one (split_huge_page caller must
have a reference to the head page).

split_huge_page uses migration entries to stabilize page->_refcount and
page->_mapcount of anonymous pages. File pages just get unmapped.

We are safe against physical memory scanners too: the only legitimate way
a scanner can get a reference to a page is get_page_unless_zero().

All tail pages have zero ->_refcount until atomic_add(). This prevents the
scanner from getting a reference to the tail page up to that point. After the
atomic_add() we don't care about the ->_refcount value. We already know how
many references should be uncharged from the head page.

For head page get_page_unless_zero() will succeed and we don't mind. It's
clear where references should go after split: it will stay on the head page.

Note that split_huge_pmd() doesn't have any limitations on refcounting:
pmd can be split at any point and never fails.

Partial unmap and deferred_split_huge_page()
============================================

Unmapping part of THP (with munmap() or other way) is not going to free
memory immediately. Instead, we detect that a subpage of THP is not in use
in page_remove_rmap() and queue the THP for splitting if memory pressure
comes. Splitting will free up unused subpages.

Splitting the page right away is not an option due to locking context in
the place where we can detect partial unmap. It also might be
counterproductive since in many cases partial unmap happens during exit(2) if
a THP crosses a VMA boundary.

The function deferred_split_huge_page() is used to queue a page for splitting.
The splitting itself will happen when we get memory pressure via shrinker
interface.