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

======
Design
======

Configurable Layers
===================

DAMON provides data access monitoring functionality while making the accuracy
and the overhead controllable.  The fundamental access monitorings require
primitives that dependent on and optimized for the target address space.  On
the other hand, the accuracy and overhead tradeoff mechanism, which is the core
of DAMON, is in the pure logic space.  DAMON separates the two parts in
different layers and defines its interface to allow various low level
primitives implementations configurable with the core logic.  We call the low
level primitives implementations monitoring operations.

Due to this separated design and the configurable interface, users can extend
DAMON for any address space by configuring the core logics with appropriate
monitoring operations.  If appropriate one is not provided, users can implement
the operations on their own.

For example, physical memory, virtual memory, swap space, those for specific
processes, NUMA nodes, files, and backing memory devices would be supportable.
Also, if some architectures or devices support special optimized access check
primitives, those will be easily configurable.

Reference Implementations of Address Space Specific Monitoring Operations
=========================================================================

The monitoring operations are defined in two parts:

1. Identification of the monitoring target address range for the address space.
2. Access check of specific address range in the target space.

DAMON currently provides the implementations of the operations for the physical
and virtual address spaces. Below two subsections describe how those work.

VMA-based Target Address Range Construction
-------------------------------------------

This is only for the virtual address space monitoring operations
implementation.  That for the physical address space simply asks users to
manually set the monitoring target address ranges.

Only small parts in the super-huge virtual address space of the processes are
mapped to the physical memory and accessed.  Thus, tracking the unmapped
address regions is just wasteful.  However, because DAMON can deal with some
level of noise using the adaptive regions adjustment mechanism, tracking every
mapping is not strictly required but could even incur a high overhead in some
cases.  That said, too huge unmapped areas inside the monitoring target should
be removed to not take the time for the adaptive mechanism.

For the reason, this implementation converts the complex mappings to three
distinct regions that cover every mapped area of the address space.  The two
gaps between the three regions are the two biggest unmapped areas in the given
address space.  The two biggest unmapped areas would be the gap between the
heap and the uppermost mmap()-ed region, and the gap between the lowermost
mmap()-ed region and the stack in most of the cases.  Because these gaps are
exceptionally huge in usual address spaces, excluding these will be sufficient
to make a reasonable trade-off.  Below shows this in detail::

    <heap>
    <BIG UNMAPPED REGION 1>
    <uppermost mmap()-ed region>
    (small mmap()-ed regions and munmap()-ed regions)
    <lowermost mmap()-ed region>
    <BIG UNMAPPED REGION 2>
    <stack>

PTE Accessed-bit Based Access Check
-----------------------------------

Both of the implementations for physical and virtual address spaces use PTE
Accessed-bit for basic access checks.  Only one difference is the way of
finding the relevant PTE Accessed bit(s) from the address.  While the
implementation for the virtual address walks the page table for the target task
of the address, the implementation for the physical address walks every page
table having a mapping to the address.  In this way, the implementations find
and clear the bit(s) for next sampling target address and checks whether the
bit(s) set again after one sampling period.  This could disturb other kernel
subsystems using the Accessed bits, namely Idle page tracking and the reclaim
logic.  DAMON does nothing to avoid disturbing Idle page tracking, so handling
the interference is the responsibility of sysadmins.  However, it solves the
conflict with the reclaim logic using ``PG_idle`` and ``PG_young`` page flags,
as Idle page tracking does.

Address Space Independent Core Mechanisms
=========================================

Below four sections describe each of the DAMON core mechanisms and the five
monitoring attributes, ``sampling interval``, ``aggregation interval``,
``update interval``, ``minimum number of regions``, and ``maximum number of
regions``.

Access Frequency Monitoring
---------------------------

The output of DAMON says what pages are how frequently accessed for a given
duration.  The resolution of the access frequency is controlled by setting
``sampling interval`` and ``aggregation interval``.  In detail, DAMON checks
access to each page per ``sampling interval`` and aggregates the results.  In
other words, counts the number of the accesses to each page.  After each
``aggregation interval`` passes, DAMON calls callback functions that previously
registered by users so that users can read the aggregated results and then
clears the results.  This can be described in below simple pseudo-code::

    while monitoring_on:
        for page in monitoring_target:
            if accessed(page):
                nr_accesses[page] += 1
        if time() % aggregation_interval == 0:
            for callback in user_registered_callbacks:
                callback(monitoring_target, nr_accesses)
            for page in monitoring_target:
                nr_accesses[page] = 0
        sleep(sampling interval)

The monitoring overhead of this mechanism will arbitrarily increase as the
size of the target workload grows.

Region Based Sampling
---------------------

To avoid the unbounded increase of the overhead, DAMON groups adjacent pages
that assumed to have the same access frequencies into a region.  As long as the
assumption (pages in a region have the same access frequencies) is kept, only
one page in the region is required to be checked.  Thus, for each ``sampling
interval``, DAMON randomly picks one page in each region, waits for one
``sampling interval``, checks whether the page is accessed meanwhile, and
increases the access frequency of the region if so.  Therefore, the monitoring
overhead is controllable by setting the number of regions.  DAMON allows users
to set the minimum and the maximum number of regions for the trade-off.

This scheme, however, cannot preserve the quality of the output if the
assumption is not guaranteed.

Adaptive Regions Adjustment
---------------------------

Even somehow the initial monitoring target regions are well constructed to
fulfill the assumption (pages in same region have similar access frequencies),
the data access pattern can be dynamically changed.  This will result in low
monitoring quality.  To keep the assumption as much as possible, DAMON
adaptively merges and splits each region based on their access frequency.

For each ``aggregation interval``, it compares the access frequencies of
adjacent regions and merges those if the frequency difference is small.  Then,
after it reports and clears the aggregated access frequency of each region, it
splits each region into two or three regions if the total number of regions
will not exceed the user-specified maximum number of regions after the split.

In this way, DAMON provides its best-effort quality and minimal overhead while
keeping the bounds users set for their trade-off.

Dynamic Target Space Updates Handling
-------------------------------------

The monitoring target address range could dynamically changed.  For example,
virtual memory could be dynamically mapped and unmapped.  Physical memory could
be hot-plugged.

As the changes could be quite frequent in some cases, DAMON allows the
monitoring operations to check dynamic changes including memory mapping changes
and applies it to monitoring operations-related data structures such as the
abstracted monitoring target memory area only for each of a user-specified time
interval (``update interval``).


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

==========================
Frequently Asked Questions
==========================

Why a new subsystem, instead of extending perf or other user space tools?
=========================================================================

First, because it needs to be lightweight as much as possible so that it can be
used online, any unnecessary overhead such as kernel - user space context
switching cost should be avoided.  Second, DAMON aims to be used by other
programs including the kernel.  Therefore, having a dependency on specific
tools like perf is not desirable.  These are the two biggest reasons why DAMON
is implemented in the kernel space.

Can 'idle pages tracking' or 'perf mem' substitute DAMON?
=========================================================

Idle page tracking is a low level primitive for access check of the physical
address space.  'perf mem' is similar, though it can use sampling to minimize
the overhead.  On the other hand, DAMON is a higher-level framework for the
monitoring of various address spaces.  It is focused on memory management
optimization and provides sophisticated accuracy/overhead handling mechanisms.
Therefore, 'idle pages tracking' and 'perf mem' could provide a subset of
DAMON's output, but cannot substitute DAMON.

Does DAMON support virtual memory only?
=======================================

No.  The core of the DAMON is address space independent.  The address space
specific monitoring operations including monitoring target regions
constructions and actual access checks can be implemented and configured on the
DAMON core by the users.  In this way, DAMON users can monitor any address
space with any access check technique.

Nonetheless, DAMON provides vma/rmap tracking and PTE Accessed bit check based
implementations of the address space dependent functions for the virtual memory
and the physical memory by default, for a reference and convenient use.

Can I simply monitor page granularity?
======================================

Yes.  You can do so by setting the ``min_nr_regions`` attribute higher than the
working set size divided by the page size.  Because the monitoring target
regions size is forced to be ``>=page size``, the region split will make no
effect.

repo_name: angery/linux


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

==========================
DAMON: Data Access MONitor
==========================

DAMON is a data access monitoring framework subsystem for the Linux kernel.
The core mechanisms of DAMON (refer to :doc:`design` for the detail) make it

 - *accurate* (the monitoring output is useful enough for DRAM level memory
   management; It might not appropriate for CPU Cache levels, though),
 - *light-weight* (the monitoring overhead is low enough to be applied online),
   and
 - *scalable* (the upper-bound of the overhead is in constant range regardless
   of the size of target workloads).

Using this framework, therefore, the kernel's memory management mechanisms can
make advanced decisions.  Experimental memory management optimization works
that incurring high data accesses monitoring overhead could implemented again.
In user space, meanwhile, users who have some special workloads can write
personalized applications for better understanding and optimizations of their
workloads and systems.

.. toctree::
   :maxdepth: 2

   faq
   design
   api


code:
.. _free_page_reporting:

=====================
Free Page Reporting
=====================

Free page reporting is an API by which a device can register to receive
lists of pages that are currently unused by the system. This is useful in
the case of virtualization where a guest is then able to use this data to
notify the hypervisor that it is no longer using certain pages in memory.

For the driver, typically a balloon driver, to use of this functionality
it will allocate and initialize a page_reporting_dev_info structure. The
field within the structure it will populate is the "report" function
pointer used to process the scatterlist. It must also guarantee that it can
handle at least PAGE_REPORTING_CAPACITY worth of scatterlist entries per
call to the function. A call to page_reporting_register will register the
page reporting interface with the reporting framework assuming no other
page reporting devices are already registered.

Once registered the page reporting API will begin reporting batches of
pages to the driver. The API will start reporting pages 2 seconds after
the interface is registered and will continue to do so 2 seconds after any
page of a sufficiently high order is freed.

Pages reported will be stored in the scatterlist passed to the reporting
function with the final entry having the end bit set in entry nent - 1.
While pages are being processed by the report function they will not be
accessible to the allocator. Once the report function has been completed
the pages will be returned to the free area from which they were obtained.

Prior to removing a driver that is making use of free page reporting it
is necessary to call page_reporting_unregister to have the
page_reporting_dev_info structure that is currently in use by free page
reporting removed. Doing this will prevent further reports from being
issued via the interface. If another driver or the same driver is
registered it is possible for it to resume where the previous driver had
left off in terms of reporting free pages.

Alexander Duyck, Dec 04, 2019


code:
.. _frontswap:

=========
Frontswap
=========

Frontswap provides a "transcendent memory" interface for swap pages.
In some environments, dramatic performance savings may be obtained because
swapped pages are saved in RAM (or a RAM-like device) instead of a swap disk.

.. _Transcendent memory in a nutshell: https://lwn.net/Articles/454795/

Frontswap is so named because it can be thought of as the opposite of
a "backing" store for a swap device.  The storage is assumed to be
a synchronous concurrency-safe page-oriented "pseudo-RAM device" conforming
to the requirements of transcendent memory (such as Xen's "tmem", or
in-kernel compressed memory, aka "zcache", or future RAM-like devices);
this pseudo-RAM device is not directly accessible or addressable by the
kernel and is of unknown and possibly time-varying size.  The driver
links itself to frontswap by calling frontswap_register_ops to set the
frontswap_ops funcs appropriately and the functions it provides must
conform to certain policies as follows:

An "init" prepares the device to receive frontswap pages associated
with the specified swap device number (aka "type").  A "store" will
copy the page to transcendent memory and associate it with the type and
offset associated with the page. A "load" will copy the page, if found,
from transcendent memory into kernel memory, but will NOT remove the page
from transcendent memory.  An "invalidate_page" will remove the page
from transcendent memory and an "invalidate_area" will remove ALL pages
associated with the swap type (e.g., like swapoff) and notify the "device"
to refuse further stores with that swap type.

Once a page is successfully stored, a matching load on the page will normally
succeed.  So when the kernel finds itself in a situation where it needs
to swap out a page, it first attempts to use frontswap.  If the store returns
success, the data has been successfully saved to transcendent memory and
a disk write and, if the data is later read back, a disk read are avoided.
If a store returns failure, transcendent memory has rejected the data, and the
page can be written to swap as usual.

Note that if a page is stored and the page already exists in transcendent memory
(a "duplicate" store), either the store succeeds and the data is overwritten,
or the store fails AND the page is invalidated.  This ensures stale data may
never be obtained from frontswap.

If properly configured, monitoring of frontswap is done via debugfs in
the `/sys/kernel/debug/frontswap` directory.  The effectiveness of
frontswap can be measured (across all swap devices) with:

``failed_stores``
	how many store attempts have failed

``loads``
	how many loads were attempted (all should succeed)

``succ_stores``
	how many store attempts have succeeded

``invalidates``
	how many invalidates were attempted

A backend implementation may provide additional metrics.

FAQ
===

* Where's the value?

When a workload starts swapping, performance falls through the floor.
Frontswap significantly increases performance in many such workloads by
providing a clean, dynamic interface to read and write swap pages to
"transcendent memory" that is otherwise not directly addressable to the kernel.
This interface is ideal when data is transformed to a different form
and size (such as with compression) or secretly moved (as might be
useful for write-balancing for some RAM-like devices).  Swap pages (and
evicted page-cache pages) are a great use for this kind of slower-than-RAM-
but-much-faster-than-disk "pseudo-RAM device".

Frontswap with a fairly small impact on the kernel,
provides a huge amount of flexibility for more dynamic, flexible RAM
utilization in various system configurations:

In the single kernel case, aka "zcache", pages are compressed and
stored in local memory, thus increasing the total anonymous pages
that can be safely kept in RAM.  Zcache essentially trades off CPU
cycles used in compression/decompression for better memory utilization.
Benchmarks have shown little or no impact when memory pressure is
low while providing a significant performance improvement (25%+)
on some workloads under high memory pressure.

"RAMster" builds on zcache by adding "peer-to-peer" transcendent memory
support for clustered systems.  Frontswap pages are locally compressed
as in zcache, but then "remotified" to another system's RAM.  This
allows RAM to be dynamically load-balanced back-and-forth as needed,
i.e. when system A is overcommitted, it can swap to system B, and
vice versa.  RAMster can also be configured as a memory server so
many servers in a cluster can swap, dynamically as needed, to a single
server configured with a large amount of RAM... without pre-configuring
how much of the RAM is available for each of the clients!

In the virtual case, the whole point of virtualization is to statistically
multiplex physical resources across the varying demands of multiple
virtual machines.  This is really hard to do with RAM and efforts to do
it well with no kernel changes have essentially failed (except in some
well-publicized special-case workloads).
Specifically, the Xen Transcendent Memory backend allows otherwise
"fallow" hypervisor-owned RAM to not only be "time-shared" between multiple
virtual machines, but the pages can be compressed and deduplicated to
optimize RAM utilization.  And when guest OS's are induced to surrender
underutilized RAM (e.g. with "selfballooning"), sudden unexpected
memory pressure may result in swapping; frontswap allows those pages
to be swapped to and from hypervisor RAM (if overall host system memory
conditions allow), thus mitigating the potentially awful performance impact
of unplanned swapping.

A KVM implementation is underway and has been RFC'ed to lkml.  And,
using frontswap, investigation is also underway on the use of NVM as
a memory extension technology.

* Sure there may be performance advantages in some situations, but
  what's the space/time overhead of frontswap?

If CONFIG_FRONTSWAP is disabled, every frontswap hook compiles into
nothingness and the only overhead is a few extra bytes per swapon'ed
swap device.  If CONFIG_FRONTSWAP is enabled but no frontswap "backend"
registers, there is one extra global variable compared to zero for
every swap page read or written.  If CONFIG_FRONTSWAP is enabled
AND a frontswap backend registers AND the backend fails every "store"
request (i.e. provides no memory despite claiming it might),
CPU overhead is still negligible -- and since every frontswap fail
precedes a swap page write-to-disk, the system is highly likely
to be I/O bound and using a small fraction of a percent of a CPU
will be irrelevant anyway.

As for space, if CONFIG_FRONTSWAP is enabled AND a frontswap backend
registers, one bit is allocated for every swap page for every swap
device that is swapon'd.  This is added to the EIGHT bits (which
was sixteen until about 2.6.34) that the kernel already allocates
for every swap page for every swap device that is swapon'd.  (Hugh
Dickins has observed that frontswap could probably steal one of
the existing eight bits, but let's worry about that minor optimization
later.)  For very large swap disks (which are rare) on a standard
4K pagesize, this is 1MB per 32GB swap.

When swap pages are stored in transcendent memory instead of written
out to disk, there is a side effect that this may create more memory
pressure that can potentially outweigh the other advantages.  A
backend, such as zcache, must implement policies to carefully (but
dynamically) manage memory limits to ensure this doesn't happen.

* OK, how about a quick overview of what this frontswap patch does
  in terms that a kernel hacker can grok?

Let's assume that a frontswap "backend" has registered during
kernel initialization; this registration indicates that this
frontswap backend has access to some "memory" that is not directly
accessible by the kernel.  Exactly how much memory it provides is
entirely dynamic and random.

Whenever a swap-device is swapon'd frontswap_init() is called,
passing the swap device number (aka "type") as a parameter.
This notifies frontswap to expect attempts to "store" swap pages
associated with that number.

Whenever the swap subsystem is readying a page to write to a swap
device (c.f swap_writepage()), frontswap_store is called.  Frontswap
consults with the frontswap backend and if the backend says it does NOT
have room, frontswap_store returns -1 and the kernel swaps the page
to the swap device as normal.  Note that the response from the frontswap
backend is unpredictable to the kernel; it may choose to never accept a
page, it could accept every ninth page, or it might accept every
page.  But if the backend does accept a page, the data from the page
has already been copied and associated with the type and offset,
and the backend guarantees the persistence of the data.  In this case,
frontswap sets a bit in the "frontswap_map" for the swap device
corresponding to the page offset on the swap device to which it would
otherwise have written the data.

When the swap subsystem needs to swap-in a page (swap_readpage()),
it first calls frontswap_load() which checks the frontswap_map to
see if the page was earlier accepted by the frontswap backend.  If
it was, the page of data is filled from the frontswap backend and
the swap-in is complete.  If not, the normal swap-in code is
executed to obtain the page of data from the real swap device.

So every time the frontswap backend accepts a page, a swap device read
and (potentially) a swap device write are replaced by a "frontswap backend
store" and (possibly) a "frontswap backend loads", which are presumably much
faster.

* Can't frontswap be configured as a "special" swap device that is
  just higher priority than any real swap device (e.g. like zswap,
  or maybe swap-over-nbd/NFS)?

No.  First, the existing swap subsystem doesn't allow for any kind of
swap hierarchy.  Perhaps it could be rewritten to accommodate a hierarchy,
but this would require fairly drastic changes.  Even if it were
rewritten, the existing swap subsystem uses the block I/O layer which
assumes a swap device is fixed size and any page in it is linearly
addressable.  Frontswap barely touches the existing swap subsystem,
and works around the constraints of the block I/O subsystem to provide
a great deal of flexibility and dynamicity.

For example, the acceptance of any swap page by the frontswap backend is
entirely unpredictable. This is critical to the definition of frontswap
backends because it grants completely dynamic discretion to the
backend.  In zcache, one cannot know a priori how compressible a page is.
"Poorly" compressible pages can be rejected, and "poorly" can itself be
defined dynamically depending on current memory constraints.

Further, frontswap is entirely synchronous whereas a real swap
device is, by definition, asynchronous and uses block I/O.  The
block I/O layer is not only unnecessary, but may perform "optimizations"
that are inappropriate for a RAM-oriented device including delaying
the write of some pages for a significant amount of time.  Synchrony is
required to ensure the dynamicity of the backend and to avoid thorny race
conditions that would unnecessarily and greatly complicate frontswap
and/or the block I/O subsystem.  That said, only the initial "store"
and "load" operations need be synchronous.  A separate asynchronous thread
is free to manipulate the pages stored by frontswap.  For example,
the "remotification" thread in RAMster uses standard asynchronous
kernel sockets to move compressed frontswap pages to a remote machine.
Similarly, a KVM guest-side implementation could do in-guest compression
and use "batched" hypercalls.

In a virtualized environment, the dynamicity allows the hypervisor
(or host OS) to do "intelligent overcommit".  For example, it can
choose to accept pages only until host-swapping might be imminent,
then force guests to do their own swapping.

There is a downside to the transcendent memory specifications for
frontswap:  Since any "store" might fail, there must always be a real
slot on a real swap device to swap the page.  Thus frontswap must be
implemented as a "shadow" to every swapon'd device with the potential
capability of holding every page that the swap device might have held
and the possibility that it might hold no pages at all.  This means
that frontswap cannot contain more pages than the total of swapon'd
swap devices.  For example, if NO swap device is configured on some
installation, frontswap is useless.  Swapless portable devices
can still use frontswap but a backend for such devices must configure
some kind of "ghost" swap device and ensure that it is never used.

* Why this weird definition about "duplicate stores"?  If a page
  has been previously successfully stored, can't it always be
  successfully overwritten?

Nearly always it can, but no, sometimes it cannot.  Consider an example
where data is compressed and the original 4K page has been compressed
to 1K.  Now an attempt is made to overwrite the page with data that
is non-compressible and so would take the entire 4K.  But the backend
has no more space.  In this case, the store must be rejected.  Whenever
frontswap rejects a store that would overwrite, it also must invalidate
the old data and ensure that it is no longer accessible.  Since the
swap subsystem then writes the new data to the read swap device,
this is the correct course of action to ensure coherency.

* Why does the frontswap patch create the new include file swapfile.h?

The frontswap code depends on some swap-subsystem-internal data
structures that have, over the years, moved back and forth between
static and global.  This seemed a reasonable compromise:  Define
them as global but declare them in a new include file that isn't
included by the large number of source files that include swap.h.

Dan Magenheimer, last updated April 9, 2012


code:
.. _highmem:

====================
High Memory Handling
====================

By: Peter Zijlstra <a.p.zijlstra@chello.nl>

.. contents:: :local:

What Is High Memory?
====================

High memory (highmem) is used when the size of physical memory approaches or
exceeds the maximum size of virtual memory.  At that point it becomes
impossible for the kernel to keep all of the available physical memory mapped
at all times.  This means the kernel needs to start using temporary mappings of
the pieces of physical memory that it wants to access.

The part of (physical) memory not covered by a permanent mapping is what we
refer to as 'highmem'.  There are various architecture dependent constraints on
where exactly that border lies.

In the i386 arch, for example, we choose to map the kernel into every process's
VM space so that we don't have to pay the full TLB invalidation costs for
kernel entry/exit.  This means the available virtual memory space (4GiB on
i386) has to be divided between user and kernel space.

The traditional split for architectures using this approach is 3:1, 3GiB for
userspace and the top 1GiB for kernel space::

		+--------+ 0xffffffff
		| Kernel |
		+--------+ 0xc0000000
		|        |
		| User   |
		|        |
		+--------+ 0x00000000

This means that the kernel can at most map 1GiB of physical memory at any one
time, but because we need virtual address space for other things - including
temporary maps to access the rest of the physical memory - the actual direct
map will typically be less (usually around ~896MiB).

Other architectures that have mm context tagged TLBs can have separate kernel
and user maps.  Some hardware (like some ARMs), however, have limited virtual
space when they use mm context tags.

Temporary Virtual Mappings
==========================

The kernel contains several ways of creating temporary mappings. The following
list shows them in order of preference of use.

* kmap_local_page().  This function is used to require short term mappings.
  It can be invoked from any context (including interrupts) but the mappings
  can only be used in the context which acquired them.

  This function should be preferred, where feasible, over all the others.

  These mappings are thread-local and CPU-local, meaning that the mapping
  can only be accessed from within this thread and the thread is bound to the
  CPU while the mapping is active. Although preemption is never disabled by
  this function, the CPU can not be unplugged from the system via
  CPU-hotplug until the mapping is disposed.

  It's valid to take pagefaults in a local kmap region, unless the context
  in which the local mapping is acquired does not allow it for other reasons.

  As said, pagefaults and preemption are never disabled. There is no need to
  disable preemption because, when context switches to a different task, the
  maps of the outgoing task are saved and those of the incoming one are
  restored.

  kmap_local_page() always returns a valid virtual address and it is assumed
  that kunmap_local() will never fail.

  On CONFIG_HIGHMEM=n kernels and for low memory pages this returns the
  virtual address of the direct mapping. Only real highmem pages are
  temporarily mapped. Therefore, users may call a plain page_address()
  for pages which are known to not come from ZONE_HIGHMEM. However, it is
  always safe to use kmap_local_page() / kunmap_local().

  While it is significantly faster than kmap(), for the higmem case it
  comes with restrictions about the pointers validity. Contrary to kmap()
  mappings, the local mappings are only valid in the context of the caller
  and cannot be handed to other contexts. This implies that users must
  be absolutely sure to keep the use of the return address local to the
  thread which mapped it.

  Most code can be designed to use thread local mappings. User should
  therefore try to design their code to avoid the use of kmap() by mapping
  pages in the same thread the address will be used and prefer
  kmap_local_page().

  Nesting kmap_local_page() and kmap_atomic() mappings is allowed to a certain
  extent (up to KMAP_TYPE_NR) but their invocations have to be strictly ordered
  because the map implementation is stack based. See kmap_local_page() kdocs
  (included in the "Functions" section) for details on how to manage nested
  mappings.

* kmap_atomic().  This permits a very short duration mapping of a single
  page.  Since the mapping is restricted to the CPU that issued it, it
  performs well, but the issuing task is therefore required to stay on that
  CPU until it has finished, lest some other task displace its mappings.

  kmap_atomic() may also be used by interrupt contexts, since it does not
  sleep and the callers too may not sleep until after kunmap_atomic() is
  called.

  Each call of kmap_atomic() in the kernel creates a non-preemptible section
  and disable pagefaults. This could be a source of unwanted latency. Therefore
  users should prefer kmap_local_page() instead of kmap_atomic().

  It is assumed that k[un]map_atomic() won't fail.

* kmap().  This should be used to make short duration mapping of a single
  page with no restrictions on preemption or migration. It comes with an
  overhead as mapping space is restricted and protected by a global lock
  for synchronization. When mapping is no longer needed, the address that
  the page was mapped to must be released with kunmap().

  Mapping changes must be propagated across all the CPUs. kmap() also
  requires global TLB invalidation when the kmap's pool wraps and it might
  block when the mapping space is fully utilized until a slot becomes
  available. Therefore, kmap() is only callable from preemptible context.

  All the above work is necessary if a mapping must last for a relatively
  long time but the bulk of high-memory mappings in the kernel are
  short-lived and only used in one place. This means that the cost of
  kmap() is mostly wasted in such cases. kmap() was not intended for long
  term mappings but it has morphed in that direction and its use is
  strongly discouraged in newer code and the set of the preceding functions
  should be preferred.

  On 64-bit systems, calls to kmap_local_page(), kmap_atomic() and kmap() have
  no real work to do because a 64-bit address space is more than sufficient to
  address all the physical memory whose pages are permanently mapped.

* vmap().  This can be used to make a long duration mapping of multiple
  physical pages into a contiguous virtual space.  It needs global
  synchronization to unmap.

Cost of Temporary Mappings
==========================

The cost of creating temporary mappings can be quite high.  The arch has to
manipulate the kernel's page tables, the data TLB and/or the MMU's registers.

If CONFIG_HIGHMEM is not set, then the kernel will try and create a mapping
simply with a bit of arithmetic that will convert the page struct address into
a pointer to the page contents rather than juggling mappings about.  In such a
case, the unmap operation may be a null operation.

If CONFIG_MMU is not set, then there can be no temporary mappings and no
highmem.  In such a case, the arithmetic approach will also be used.

i386 PAE
========

The i386 arch, under some circumstances, will permit you to stick up to 64GiB
of RAM into your 32-bit machine.  This has a number of consequences:

* Linux needs a page-frame structure for each page in the system and the
  pageframes need to live in the permanent mapping, which means:

* you can have 896M/sizeof(struct page) page-frames at most; with struct
  page being 32-bytes that would end up being something in the order of 112G
  worth of pages; the kernel, however, needs to store more than just
  page-frames in that memory...

* PAE makes your page tables larger - which slows the system down as more
  data has to be accessed to traverse in TLB fills and the like.  One
  advantage is that PAE has more PTE bits and can provide advanced features
  like NX and PAT.

The general recommendation is that you don't use more than 8GiB on a 32-bit
machine - although more might work for you and your workload, you're pretty
much on your own - don't expect kernel developers to really care much if things
come apart.

Functions
=========

.. kernel-doc:: include/linux/highmem.h
.. kernel-doc:: include/linux/highmem-internal.h


code:
.. _hmm:

=====================================
Heterogeneous Memory Management (HMM)
=====================================

Provide infrastructure and helpers to integrate non-conventional memory (device
memory like GPU on board memory) into regular kernel path, with the cornerstone
of this being specialized struct page for such memory (see sections 5 to 7 of
this document).

HMM also provides optional helpers for SVM (Share Virtual Memory), i.e.,
allowing a device to transparently access program addresses coherently with
the CPU meaning that any valid pointer on the CPU is also a valid pointer
for the device. This is becoming mandatory to simplify the use of advanced
heterogeneous computing where GPU, DSP, or FPGA are used to perform various
computations on behalf of a process.

This document is divided as follows: in the first section I expose the problems
related to using device specific memory allocators. In the second section, I
expose the hardware limitations that are inherent to many platforms. The third
section gives an overview of the HMM design. The fourth section explains how
CPU page-table mirroring works and the purpose of HMM in this context. The
fifth section deals with how device memory is represented inside the kernel.
Finally, the last section presents a new migration helper that allows
leveraging the device DMA engine.

.. contents:: :local:

Problems of using a device specific memory allocator
====================================================

Devices with a large amount of on board memory (several gigabytes) like GPUs
have historically managed their memory through dedicated driver specific APIs.
This creates a disconnect between memory allocated and managed by a device
driver and regular application memory (private anonymous, shared memory, or
regular file backed memory). From here on I will refer to this aspect as split
address space. I use shared address space to refer to the opposite situation:
i.e., one in which any application memory region can be used by a device
transparently.

Split address space happens because devices can only access memory allocated
through a device specific API. This implies that all memory objects in a program
are not equal from the device point of view which complicates large programs
that rely on a wide set of libraries.

Concretely, this means that code that wants to leverage devices like GPUs needs
to copy objects between generically allocated memory (malloc, mmap private, mmap
share) and memory allocated through the device driver API (this still ends up
with an mmap but of the device file).

For flat data sets (array, grid, image, ...) this isn't too hard to achieve but
for complex data sets (list, tree, ...) it's hard to get right. Duplicating a
complex data set needs to re-map all the pointer relations between each of its
elements. This is error prone and programs get harder to debug because of the
duplicate data set and addresses.

Split address space also means that libraries cannot transparently use data
they are getting from the core program or another library and thus each library
might have to duplicate its input data set using the device specific memory
allocator. Large projects suffer from this and waste resources because of the
various memory copies.

Duplicating each library API to accept as input or output memory allocated by
each device specific allocator is not a viable option. It would lead to a
combinatorial explosion in the library entry points.

Finally, with the advance of high level language constructs (in C++ but in
other languages too) it is now possible for the compiler to leverage GPUs and
other devices without programmer knowledge. Some compiler identified patterns
are only do-able with a shared address space. It is also more reasonable to use
a shared address space for all other patterns.

I/O bus, device memory characteristics
======================================

I/O buses cripple shared address spaces due to a few limitations. Most I/O
buses only allow basic memory access from device to main memory; even cache
coherency is often optional. Access to device memory from a CPU is even more
limited. More often than not, it is not cache coherent.

If we only consider the PCIE bus, then a device can access main memory (often
through an IOMMU) and be cache coherent with the CPUs. However, it only allows
a limited set of atomic operations from the device on main memory. This is worse
in the other direction: the CPU can only access a limited range of the device
memory and cannot perform atomic operations on it. Thus device memory cannot
be considered the same as regular memory from the kernel point of view.

Another crippling factor is the limited bandwidth (~32GBytes/s with PCIE 4.0
and 16 lanes). This is 33 times less than the fastest GPU memory (1 TBytes/s).
The final limitation is latency. Access to main memory from the device has an
order of magnitude higher latency than when the device accesses its own memory.

Some platforms are developing new I/O buses or additions/modifications to PCIE
to address some of these limitations (OpenCAPI, CCIX). They mainly allow
two-way cache coherency between CPU and device and allow all atomic operations the
architecture supports. Sadly, not all platforms are following this trend and
some major architectures are left without hardware solutions to these problems.

So for shared address space to make sense, not only must we allow devices to
access any memory but we must also permit any memory to be migrated to device
memory while the device is using it (blocking CPU access while it happens).

Shared address space and migration
==================================

HMM intends to provide two main features. The first one is to share the address
space by duplicating the CPU page table in the device page table so the same
address points to the same physical memory for any valid main memory address in
the process address space.

To achieve this, HMM offers a set of helpers to populate the device page table
while keeping track of CPU page table updates. Device page table updates are
not as easy as CPU page table updates. To update the device page table, you must
allocate a buffer (or use a pool of pre-allocated buffers) and write GPU
specific commands in it to perform the update (unmap, cache invalidations, and
flush, ...). This cannot be done through common code for all devices. Hence
why HMM provides helpers to factor out everything that can be while leaving the
hardware specific details to the device driver.

The second mechanism HMM provides is a new kind of ZONE_DEVICE memory that
allows allocating a struct page for each page of device memory. Those pages
are special because the CPU cannot map them. However, they allow migrating
main memory to device memory using existing migration mechanisms and everything
looks like a page that is swapped out to disk from the CPU point of view. Using a
struct page gives the easiest and cleanest integration with existing mm
mechanisms. Here again, HMM only provides helpers, first to hotplug new ZONE_DEVICE
memory for the device memory and second to perform migration. Policy decisions
of what and when to migrate is left to the device driver.

Note that any CPU access to a device page triggers a page fault and a migration
back to main memory. For example, when a page backing a given CPU address A is
migrated from a main memory page to a device page, then any CPU access to
address A triggers a page fault and initiates a migration back to main memory.

With these two features, HMM not only allows a device to mirror process address
space and keeps both CPU and device page tables synchronized, but also
leverages device memory by migrating the part of the data set that is actively being
used by the device.

Address space mirroring implementation and API
==============================================

Address space mirroring's main objective is to allow duplication of a range of
CPU page table into a device page table; HMM helps keep both synchronized. A
device driver that wants to mirror a process address space must start with the
registration of a mmu_interval_notifier::

 int mmu_interval_notifier_insert(struct mmu_interval_notifier *interval_sub,
				  struct mm_struct *mm, unsigned long start,
				  unsigned long length,
				  const struct mmu_interval_notifier_ops *ops);

During the ops->invalidate() callback the device driver must perform the
update action to the range (mark range read only, or fully unmap, etc.). The
device must complete the update before the driver callback returns.

When the device driver wants to populate a range of virtual addresses, it can
use::

  int hmm_range_fault(struct hmm_range *range);

It will trigger a page fault on missing or read-only entries if write access is
requested (see below). Page faults use the generic mm page fault code path just
like a CPU page fault.

Both functions copy CPU page table entries into their pfns array argument. Each
entry in that array corresponds to an address in the virtual range. HMM
provides a set of flags to help the driver identify special CPU page table
entries.

Locking within the sync_cpu_device_pagetables() callback is the most important
aspect the driver must respect in order to keep things properly synchronized.
The usage pattern is::

 int driver_populate_range(...)
 {
      struct hmm_range range;
      ...

      range.notifier = &interval_sub;
      range.start = ...;
      range.end = ...;
      range.hmm_pfns = ...;

      if (!mmget_not_zero(interval_sub->notifier.mm))
          return -EFAULT;

 again:
      range.notifier_seq = mmu_interval_read_begin(&interval_sub);
      mmap_read_lock(mm);
      ret = hmm_range_fault(&range);
      if (ret) {
          mmap_read_unlock(mm);
          if (ret == -EBUSY)
                 goto again;
          return ret;
      }
      mmap_read_unlock(mm);

      take_lock(driver->update);
      if (mmu_interval_read_retry(&ni, range.notifier_seq) {
          release_lock(driver->update);
          goto again;
      }

      /* Use pfns array content to update device page table,
       * under the update lock */

      release_lock(driver->update);
      return 0;
 }

The driver->update lock is the same lock that the driver takes inside its
invalidate() callback. That lock must be held before calling
mmu_interval_read_retry() to avoid any race with a concurrent CPU page table
update.

Leverage default_flags and pfn_flags_mask
=========================================

The hmm_range struct has 2 fields, default_flags and pfn_flags_mask, that specify
fault or snapshot policy for the whole range instead of having to set them
for each entry in the pfns array.

For instance if the device driver wants pages for a range with at least read
permission, it sets::

    range->default_flags = HMM_PFN_REQ_FAULT;
    range->pfn_flags_mask = 0;

and calls hmm_range_fault() as described above. This will fill fault all pages
in the range with at least read permission.

Now let's say the driver wants to do the same except for one page in the range for
which it wants to have write permission. Now driver set::

    range->default_flags = HMM_PFN_REQ_FAULT;
    range->pfn_flags_mask = HMM_PFN_REQ_WRITE;
    range->pfns[index_of_write] = HMM_PFN_REQ_WRITE;

With this, HMM will fault in all pages with at least read (i.e., valid) and for the
address == range->start + (index_of_write << PAGE_SHIFT) it will fault with
write permission i.e., if the CPU pte does not have write permission set then HMM
will call handle_mm_fault().

After hmm_range_fault completes the flag bits are set to the current state of
the page tables, ie HMM_PFN_VALID | HMM_PFN_WRITE will be set if the page is
writable.

Represent and manage device memory from core kernel point of view
=================================================================

Several different designs were tried to support device memory. The first one
used a device specific data structure to keep information about migrated memory
and HMM hooked itself in various places of mm code to handle any access to
addresses that were backed by device memory. It turns out that this ended up
replicating most of the fields of struct page and also needed many kernel code
paths to be updated to understand this new kind of memory.

Most kernel code paths never try to access the memory behind a page
but only care about struct page contents. Because of this, HMM switched to
directly using struct page for device memory which left most kernel code paths
unaware of the difference. We only need to make sure that no one ever tries to
map those pages from the CPU side.

Migration to and from device memory
===================================

Because the CPU cannot access device memory directly, the device driver must
use hardware DMA or device specific load/store instructions to migrate data.
The migrate_vma_setup(), migrate_vma_pages(), and migrate_vma_finalize()
functions are designed to make drivers easier to write and to centralize common
code across drivers.

Before migrating pages to device private memory, special device private
``struct page`` need to be created. These will be used as special "swap"
page table entries so that a CPU process will fault if it tries to access
a page that has been migrated to device private memory.

These can be allocated and freed with::

    struct resource *res;
    struct dev_pagemap pagemap;

    res = request_free_mem_region(&iomem_resource, /* number of bytes */,
                                  "name of driver resource");
    pagemap.type = MEMORY_DEVICE_PRIVATE;
    pagemap.range.start = res->start;
    pagemap.range.end = res->end;
    pagemap.nr_range = 1;
    pagemap.ops = &device_devmem_ops;
    memremap_pages(&pagemap, numa_node_id());

    memunmap_pages(&pagemap);
    release_mem_region(pagemap.range.start, range_len(&pagemap.range));

There are also devm_request_free_mem_region(), devm_memremap_pages(),
devm_memunmap_pages(), and devm_release_mem_region() when the resources can
be tied to a ``struct device``.

The overall migration steps are similar to migrating NUMA pages within system
memory (see :ref:`Page migration <page_migration>`) but the steps are split
between device driver specific code and shared common code:

1. ``mmap_read_lock()``

   The device driver has to pass a ``struct vm_area_struct`` to
   migrate_vma_setup() so the mmap_read_lock() or mmap_write_lock() needs to
   be held for the duration of the migration.

2. ``migrate_vma_setup(struct migrate_vma *args)``

   The device driver initializes the ``struct migrate_vma`` fields and passes
   the pointer to migrate_vma_setup(). The ``args->flags`` field is used to
   filter which source pages should be migrated. For example, setting
   ``MIGRATE_VMA_SELECT_SYSTEM`` will only migrate system memory and
   ``MIGRATE_VMA_SELECT_DEVICE_PRIVATE`` will only migrate pages residing in
   device private memory. If the latter flag is set, the ``args->pgmap_owner``
   field is used to identify device private pages owned by the driver. This
   avoids trying to migrate device private pages residing in other devices.
   Currently only anonymous private VMA ranges can be migrated to or from
   system memory and device private memory.

   One of the first steps migrate_vma_setup() does is to invalidate other
   device's MMUs with the ``mmu_notifier_invalidate_range_start(()`` and
   ``mmu_notifier_invalidate_range_end()`` calls around the page table
   walks to fill in the ``args->src`` array with PFNs to be migrated.
   The ``invalidate_range_start()`` callback is passed a
   ``struct mmu_notifier_range`` with the ``event`` field set to
   ``MMU_NOTIFY_MIGRATE`` and the ``owner`` field set to
   the ``args->pgmap_owner`` field passed to migrate_vma_setup(). This is
   allows the device driver to skip the invalidation callback and only
   invalidate device private MMU mappings that are actually migrating.
   This is explained more in the next section.

   While walking the page tables, a ``pte_none()`` or ``is_zero_pfn()``
   entry results in a valid "zero" PFN stored in the ``args->src`` array.
   This lets the driver allocate device private memory and clear it instead
   of copying a page of zeros. Valid PTE entries to system memory or
   device private struct pages will be locked with ``lock_page()``, isolated
   from the LRU (if system memory since device private pages are not on
   the LRU), unmapped from the process, and a special migration PTE is
   inserted in place of the original PTE.
   migrate_vma_setup() also clears the ``args->dst`` array.

3. The device driver allocates destination pages and copies source pages to
   destination pages.

   The driver checks each ``src`` entry to see if the ``MIGRATE_PFN_MIGRATE``
   bit is set and skips entries that are not migrating. The device driver
   can also choose to skip migrating a page by not filling in the ``dst``
   array for that page.

   The driver then allocates either a device private struct page or a
   system memory page, locks the page with ``lock_page()``, and fills in the
   ``dst`` array entry with::

     dst[i] = migrate_pfn(page_to_pfn(dpage));

   Now that the driver knows that this page is being migrated, it can
   invalidate device private MMU mappings and copy device private memory
   to system memory or another device private page. The core Linux kernel
   handles CPU page table invalidations so the device driver only has to
   invalidate its own MMU mappings.

   The driver can use ``migrate_pfn_to_page(src[i])`` to get the
   ``struct page`` of the source and either copy the source page to the
   destination or clear the destination device private memory if the pointer
   is ``NULL`` meaning the source page was not populated in system memory.

4. ``migrate_vma_pages()``

   This step is where the migration is actually "committed".

   If the source page was a ``pte_none()`` or ``is_zero_pfn()`` page, this
   is where the newly allocated page is inserted into the CPU's page table.
   This can fail if a CPU thread faults on the same page. However, the page
   table is locked and only one of the new pages will be inserted.
   The device driver will see that the ``MIGRATE_PFN_MIGRATE`` bit is cleared
   if it loses the race.

   If the source page was locked, isolated, etc. the source ``struct page``
   information is now copied to destination ``struct page`` finalizing the
   migration on the CPU side.

5. Device driver updates device MMU page tables for pages still migrating,
   rolling back pages not migrating.

   If the ``src`` entry still has ``MIGRATE_PFN_MIGRATE`` bit set, the device
   driver can update the device MMU and set the write enable bit if the
   ``MIGRATE_PFN_WRITE`` bit is set.

6. ``migrate_vma_finalize()``

   This step replaces the special migration page table entry with the new
   page's page table entry and releases the reference to the source and
   destination ``struct page``.

7. ``mmap_read_unlock()``

   The lock can now be released.

Exclusive access memory
=======================

Some devices have features such as atomic PTE bits that can be used to implement
atomic access to system memory. To support atomic operations to a shared virtual
memory page such a device needs access to that page which is exclusive of any
userspace access from the CPU. The ``make_device_exclusive_range()`` function
can be used to make a memory range inaccessible from userspace.

This replaces all mappings for pages in the given range with special swap
entries. Any attempt to access the swap entry results in a fault which is
resovled by replacing the entry with the original mapping. A driver gets
notified that the mapping has been changed by MMU notifiers, after which point
it will no longer have exclusive access to the page. Exclusive access is
guranteed to last until the driver drops the page lock and page reference, at
which point any CPU faults on the page may proceed as described.

Memory cgroup (memcg) and rss accounting
========================================

For now, device memory is accounted as any regular page in rss counters (either
anonymous if device page is used for anonymous, file if device page is used for
file backed page, or shmem if device page is used for shared memory). This is a
deliberate choice to keep existing applications, that might start using device
memory without knowing about it, running unimpacted.

A drawback is that the OOM killer might kill an application using a lot of
device memory and not a lot of regular system memory and thus not freeing much
system memory. We want to gather more real world experience on how applications
and system react under memory pressure in the presence of device memory before
deciding to account device memory differently.

Same decision was made for memory cgroup. Device memory pages are accounted
against same memory cgroup a regular page would be accounted to. This does
simplify migration to and from device memory. This also means that migration
back from device memory to regular memory cannot fail because it would
go above memory cgroup limit. We might revisit this choice latter on once we
get more experience in how device memory is used and its impact on memory
resource control.

Note that device memory can never be pinned by a device driver nor through GUP
and thus such memory is always free upon process exit. Or when last reference
is dropped in case of shared memory or file backed memory.


code:
.. _hugetlbfs_reserve:

=====================
Hugetlbfs Reservation
=====================

Overview
========

Huge pages as described at :ref:`hugetlbpage` are typically
preallocated for application use.  These huge pages are instantiated in a
task's address space at page fault time if the VMA indicates huge pages are
to be used.  If no huge page exists at page fault time, the task is sent
a SIGBUS and often dies an unhappy death.  Shortly after huge page support
was added, it was determined that it would be better to detect a shortage
of huge pages at mmap() time.  The idea is that if there were not enough
huge pages to cover the mapping, the mmap() would fail.  This was first
done with a simple check in the code at mmap() time to determine if there
were enough free huge pages to cover the mapping.  Like most things in the
kernel, the code has evolved over time.  However, the basic idea was to
'reserve' huge pages at mmap() time to ensure that huge pages would be
available for page faults in that mapping.  The description below attempts to
describe how huge page reserve processing is done in the v4.10 kernel.

Audience
========
This description is primarily targeted at kernel developers who are modifying
hugetlbfs code.

The Data Structures
===================

resv_huge_pages
	This is a global (per-hstate) count of reserved huge pages.  Reserved
	huge pages are only available to the task which reserved them.
	Therefore, the number of huge pages generally available is computed
	as (``free_huge_pages - resv_huge_pages``).
Reserve Map
	A reserve map is described by the structure::

		struct resv_map {
			struct kref refs;
			spinlock_t lock;
			struct list_head regions;
			long adds_in_progress;
			struct list_head region_cache;
			long region_cache_count;
		};

	There is one reserve map for each huge page mapping in the system.
	The regions list within the resv_map describes the regions within
	the mapping.  A region is described as::

		struct file_region {
			struct list_head link;
			long from;
			long to;
		};

	The 'from' and 'to' fields of the file region structure are huge page
	indices into the mapping.  Depending on the type of mapping, a
	region in the reserv_map may indicate reservations exist for the
	range, or reservations do not exist.
Flags for MAP_PRIVATE Reservations
	These are stored in the bottom bits of the reservation map pointer.

	``#define HPAGE_RESV_OWNER    (1UL << 0)``
		Indicates this task is the owner of the reservations
		associated with the mapping.
	``#define HPAGE_RESV_UNMAPPED (1UL << 1)``
		Indicates task originally mapping this range (and creating
		reserves) has unmapped a page from this task (the child)
		due to a failed COW.
Page Flags
	The PagePrivate page flag is used to indicate that a huge page
	reservation must be restored when the huge page is freed.  More
	details will be discussed in the "Freeing huge pages" section.

Reservation Map Location (Private or Shared)
============================================

A huge page mapping or segment is either private or shared.  If private,
it is typically only available to a single address space (task).  If shared,
it can be mapped into multiple address spaces (tasks).  The location and
semantics of the reservation map is significantly different for the two types
of mappings.  Location differences are:

- For private mappings, the reservation map hangs off the VMA structure.
  Specifically, vma->vm_private_data.  This reserve map is created at the
  time the mapping (mmap(MAP_PRIVATE)) is created.
- For shared mappings, the reservation map hangs off the inode.  Specifically,
  inode->i_mapping->private_data.  Since shared mappings are always backed
  by files in the hugetlbfs filesystem, the hugetlbfs code ensures each inode
  contains a reservation map.  As a result, the reservation map is allocated
  when the inode is created.

Creating Reservations
=====================
Reservations are created when a huge page backed shared memory segment is
created (shmget(SHM_HUGETLB)) or a mapping is created via mmap(MAP_HUGETLB).
These operations result in a call to the routine hugetlb_reserve_pages()::

	int hugetlb_reserve_pages(struct inode *inode,
				  long from, long to,
				  struct vm_area_struct *vma,
				  vm_flags_t vm_flags)

The first thing hugetlb_reserve_pages() does is check if the NORESERVE
flag was specified in either the shmget() or mmap() call.  If NORESERVE
was specified, then this routine returns immediately as no reservations
are desired.

The arguments 'from' and 'to' are huge page indices into the mapping or
underlying file.  For shmget(), 'from' is always 0 and 'to' corresponds to
the length of the segment/mapping.  For mmap(), the offset argument could
be used to specify the offset into the underlying file.  In such a case,
the 'from' and 'to' arguments have been adjusted by this offset.

One of the big differences between PRIVATE and SHARED mappings is the way
in which reservations are represented in the reservation map.

- For shared mappings, an entry in the reservation map indicates a reservation
  exists or did exist for the corresponding page.  As reservations are
  consumed, the reservation map is not modified.
- For private mappings, the lack of an entry in the reservation map indicates
  a reservation exists for the corresponding page.  As reservations are
  consumed, entries are added to the reservation map.  Therefore, the
  reservation map can also be used to determine which reservations have
  been consumed.

For private mappings, hugetlb_reserve_pages() creates the reservation map and
hangs it off the VMA structure.  In addition, the HPAGE_RESV_OWNER flag is set
to indicate this VMA owns the reservations.

The reservation map is consulted to determine how many huge page reservations
are needed for the current mapping/segment.  For private mappings, this is
always the value (to - from).  However, for shared mappings it is possible that
some reservations may already exist within the range (to - from).  See the
section :ref:`Reservation Map Modifications <resv_map_modifications>`
for details on how this is accomplished.

The mapping may be associated with a subpool.  If so, the subpool is consulted
to ensure there is sufficient space for the mapping.  It is possible that the
subpool has set aside reservations that can be used for the mapping.  See the
section :ref:`Subpool Reservations <sub_pool_resv>` for more details.

After consulting the reservation map and subpool, the number of needed new
reservations is known.  The routine hugetlb_acct_memory() is called to check
for and take the requested number of reservations.  hugetlb_acct_memory()
calls into routines that potentially allocate and adjust surplus page counts.
However, within those routines the code is simply checking to ensure there
are enough free huge pages to accommodate the reservation.  If there are,
the global reservation count resv_huge_pages is adjusted something like the
following::

	if (resv_needed <= (resv_huge_pages - free_huge_pages))
		resv_huge_pages += resv_needed;

Note that the global lock hugetlb_lock is held when checking and adjusting
these counters.

If there were enough free huge pages and the global count resv_huge_pages
was adjusted, then the reservation map associated with the mapping is
modified to reflect the reservations.  In the case of a shared mapping, a
file_region will exist that includes the range 'from' - 'to'.  For private
mappings, no modifications are made to the reservation map as lack of an
entry indicates a reservation exists.

If hugetlb_reserve_pages() was successful, the global reservation count and
reservation map associated with the mapping will be modified as required to
ensure reservations exist for the range 'from' - 'to'.

.. _consume_resv:

Consuming Reservations/Allocating a Huge Page
=============================================

Reservations are consumed when huge pages associated with the reservations
are allocated and instantiated in the corresponding mapping.  The allocation
is performed within the routine alloc_huge_page()::

	struct page *alloc_huge_page(struct vm_area_struct *vma,
				     unsigned long addr, int avoid_reserve)

alloc_huge_page is passed a VMA pointer and a virtual address, so it can
consult the reservation map to determine if a reservation exists.  In addition,
alloc_huge_page takes the argument avoid_reserve which indicates reserves
should not be used even if it appears they have been set aside for the
specified address.  The avoid_reserve argument is most often used in the case
of Copy on Write and Page Migration where additional copies of an existing
page are being allocated.

The helper routine vma_needs_reservation() is called to determine if a
reservation exists for the address within the mapping(vma).  See the section
:ref:`Reservation Map Helper Routines <resv_map_helpers>` for detailed
information on what this routine does.
The value returned from vma_needs_reservation() is generally
0 or 1.  0 if a reservation exists for the address, 1 if no reservation exists.
If a reservation does not exist, and there is a subpool associated with the
mapping the subpool is consulted to determine if it contains reservations.
If the subpool contains reservations, one can be used for this allocation.
However, in every case the avoid_reserve argument overrides the use of
a reservation for the allocation.  After determining whether a reservation
exists and can be used for the allocation, the routine dequeue_huge_page_vma()
is called.  This routine takes two arguments related to reservations:

- avoid_reserve, this is the same value/argument passed to alloc_huge_page()
- chg, even though this argument is of type long only the values 0 or 1 are
  passed to dequeue_huge_page_vma.  If the value is 0, it indicates a
  reservation exists (see the section "Memory Policy and Reservations" for
  possible issues).  If the value is 1, it indicates a reservation does not
  exist and the page must be taken from the global free pool if possible.

The free lists associated with the memory policy of the VMA are searched for
a free page.  If a page is found, the value free_huge_pages is decremented
when the page is removed from the free list.  If there was a reservation
associated with the page, the following adjustments are made::

	SetPagePrivate(page);	/* Indicates allocating this page consumed
				 * a reservation, and if an error is
				 * encountered such that the page must be
				 * freed, the reservation will be restored. */
	resv_huge_pages--;	/* Decrement the global reservation count */

Note, if no huge page can be found that satisfies the VMA's memory policy
an attempt will be made to allocate one using the buddy allocator.  This
brings up the issue of surplus huge pages and overcommit which is beyond
the scope reservations.  Even if a surplus page is allocated, the same
reservation based adjustments as above will be made: SetPagePrivate(page) and
resv_huge_pages--.

After obtaining a new huge page, (page)->private is set to the value of
the subpool associated with the page if it exists.  This will be used for
subpool accounting when the page is freed.

The routine vma_commit_reservation() is then called to adjust the reserve
map based on the consumption of the reservation.  In general, this involves
ensuring the page is represented within a file_region structure of the region
map.  For shared mappings where the reservation was present, an entry
in the reserve map already existed so no change is made.  However, if there
was no reservation in a shared mapping or this was a private mapping a new
entry must be created.

It is possible that the reserve map could have been changed between the call
to vma_needs_reservation() at the beginning of alloc_huge_page() and the
call to vma_commit_reservation() after the page was allocated.  This would
be possible if hugetlb_reserve_pages was called for the same page in a shared
mapping.  In such cases, the reservation count and subpool free page count
will be off by one.  This rare condition can be identified by comparing the
return value from vma_needs_reservation and vma_commit_reservation.  If such
a race is detected, the subpool and global reserve counts are adjusted to
compensate.  See the section
:ref:`Reservation Map Helper Routines <resv_map_helpers>` for more
information on these routines.

Instantiate Huge Pages
======================

After huge page allocation, the page is typically added to the page tables
of the allocating task.  Before this, pages in a shared mapping are added
to the page cache and pages in private mappings are added to an anonymous
reverse mapping.  In both cases, the PagePrivate flag is cleared.  Therefore,
when a huge page that has been instantiated is freed no adjustment is made
to the global reservation count (resv_huge_pages).

Freeing Huge Pages
==================

Huge page freeing is performed by the routine free_huge_page().  This routine
is the destructor for hugetlbfs compound pages.  As a result, it is only
passed a pointer to the page struct.  When a huge page is freed, reservation
accounting may need to be performed.  This would be the case if the page was
associated with a subpool that contained reserves, or the page is being freed
on an error path where a global reserve count must be restored.

The page->private field points to any subpool associated with the page.
If the PagePrivate flag is set, it indicates the global reserve count should
be adjusted (see the section
:ref:`Consuming Reservations/Allocating a Huge Page <consume_resv>`
for information on how these are set).

The routine first calls hugepage_subpool_put_pages() for the page.  If this
routine returns a value of 0 (which does not equal the value passed 1) it
indicates reserves are associated with the subpool, and this newly free page
must be used to keep the number of subpool reserves above the minimum size.
Therefore, the global resv_huge_pages counter is incremented in this case.

If the PagePrivate flag was set in the page, the global resv_huge_pages counter
will always be incremented.

.. _sub_pool_resv:

Subpool Reservations
====================

There is a struct hstate associated with each huge page size.  The hstate
tracks all huge pages of the specified size.  A subpool represents a subset
of pages within a hstate that is associated with a mounted hugetlbfs
filesystem.

When a hugetlbfs filesystem is mounted a min_size option can be specified
which indicates the minimum number of huge pages required by the filesystem.
If this option is specified, the number of huge pages corresponding to
min_size are reserved for use by the filesystem.  This number is tracked in
the min_hpages field of a struct hugepage_subpool.  At mount time,
hugetlb_acct_memory(min_hpages) is called to reserve the specified number of
huge pages.  If they can not be reserved, the mount fails.

The routines hugepage_subpool_get/put_pages() are called when pages are
obtained from or released back to a subpool.  They perform all subpool
accounting, and track any reservations associated with the subpool.
hugepage_subpool_get/put_pages are passed the number of huge pages by which
to adjust the subpool 'used page' count (down for get, up for put).  Normally,
they return the same value that was passed or an error if not enough pages
exist in the subpool.

However, if reserves are associated with the subpool a return value less
than the passed value may be returned.  This return value indicates the
number of additional global pool adjustments which must be made.  For example,
suppose a subpool contains 3 reserved huge pages and someone asks for 5.
The 3 reserved pages associated with the subpool can be used to satisfy part
of the request.  But, 2 pages must be obtained from the global pools.  To
relay this information to the caller, the value 2 is returned.  The caller
is then responsible for attempting to obtain the additional two pages from
the global pools.

COW and Reservations
====================

Since shared mappings all point to and use the same underlying pages, the
biggest reservation concern for COW is private mappings.  In this case,
two tasks can be pointing at the same previously allocated page.  One task
attempts to write to the page, so a new page must be allocated so that each
task points to its own page.

When the page was originally allocated, the reservation for that page was
consumed.  When an attempt to allocate a new page is made as a result of
COW, it is possible that no free huge pages are free and the allocation
will fail.

When the private mapping was originally created, the owner of the mapping
was noted by setting the HPAGE_RESV_OWNER bit in the pointer to the reservation
map of the owner.  Since the owner created the mapping, the owner owns all
the reservations associated with the mapping.  Therefore, when a write fault
occurs and there is no page available, different action is taken for the owner
and non-owner of the reservation.

In the case where the faulting task is not the owner, the fault will fail and
the task will typically receive a SIGBUS.

If the owner is the faulting task, we want it to succeed since it owned the
original reservation.  To accomplish this, the page is unmapped from the
non-owning task.  In this way, the only reference is from the owning task.
In addition, the HPAGE_RESV_UNMAPPED bit is set in the reservation map pointer
of the non-owning task.  The non-owning task may receive a SIGBUS if it later
faults on a non-present page.  But, the original owner of the
mapping/reservation will behave as expected.

.. _resv_map_modifications:

Reservation Map Modifications
=============================

The following low level routines are used to make modifications to a
reservation map.  Typically, these routines are not called directly.  Rather,
a reservation map helper routine is called which calls one of these low level
routines.  These low level routines are fairly well documented in the source
code (mm/hugetlb.c).  These routines are::

	long region_chg(struct resv_map *resv, long f, long t);
	long region_add(struct resv_map *resv, long f, long t);
	void region_abort(struct resv_map *resv, long f, long t);
	long region_count(struct resv_map *resv, long f, long t);

Operations on the reservation map typically involve two operations:

1) region_chg() is called to examine the reserve map and determine how
   many pages in the specified range [f, t) are NOT currently represented.

   The calling code performs global checks and allocations to determine if
   there are enough huge pages for the operation to succeed.

2)
  a) If the operation can succeed, region_add() is called to actually modify
     the reservation map for the same range [f, t) previously passed to
     region_chg().
  b) If the operation can not succeed, region_abort is called for the same
     range [f, t) to abort the operation.

Note that this is a two step process where region_add() and region_abort()
are guaranteed to succeed after a prior call to region_chg() for the same
range.  region_chg() is responsible for pre-allocating any data structures
necessary to ensure the subsequent operations (specifically region_add()))
will succeed.

As mentioned above, region_chg() determines the number of pages in the range
which are NOT currently represented in the map.  This number is returned to
the caller.  region_add() returns the number of pages in the range added to
the map.  In most cases, the return value of region_add() is the same as the
return value of region_chg().  However, in the case of shared mappings it is
possible for changes to the reservation map to be made between the calls to
region_chg() and region_add().  In this case, the return value of region_add()
will not match the return value of region_chg().  It is likely that in such
cases global counts and subpool accounting will be incorrect and in need of
adjustment.  It is the responsibility of the caller to check for this condition
and make the appropriate adjustments.

The routine region_del() is called to remove regions from a reservation map.
It is typically called in the following situations:

- When a file in the hugetlbfs filesystem is being removed, the inode will
  be released and the reservation map freed.  Before freeing the reservation
  map, all the individual file_region structures must be freed.  In this case
  region_del is passed the range [0, LONG_MAX).
- When a hugetlbfs file is being truncated.  In this case, all allocated pages
  after the new file size must be freed.  In addition, any file_region entries
  in the reservation map past the new end of file must be deleted.  In this
  case, region_del is passed the range [new_end_of_file, LONG_MAX).
- When a hole is being punched in a hugetlbfs file.  In this case, huge pages
  are removed from the middle of the file one at a time.  As the pages are
  removed, region_del() is called to remove the corresponding entry from the
  reservation map.  In this case, region_del is passed the range
  [page_idx, page_idx + 1).

In every case, region_del() will return the number of pages removed from the
reservation map.  In VERY rare cases, region_del() can fail.  This can only
happen in the hole punch case where it has to split an existing file_region
entry and can not allocate a new structure.  In this error case, region_del()
will return -ENOMEM.  The problem here is that the reservation map will
indicate that there is a reservation for the page.  However, the subpool and
global reservation counts will not reflect the reservation.  To handle this
situation, the routine hugetlb_fix_reserve_counts() is called to adjust the
counters so that they correspond with the reservation map entry that could
not be deleted.

region_count() is called when unmapping a private huge page mapping.  In
private mappings, the lack of a entry in the reservation map indicates that
a reservation exists.  Therefore, by counting the number of entries in the
reservation map we know how many reservations were consumed and how many are
outstanding (outstanding = (end - start) - region_count(resv, start, end)).
Since the mapping is going away, the subpool and global reservation counts
are decremented by the number of outstanding reservations.

.. _resv_map_helpers:

Reservation Map Helper Routines
===============================

Several helper routines exist to query and modify the reservation maps.
These routines are only interested with reservations for a specific huge
page, so they just pass in an address instead of a range.  In addition,
they pass in the associated VMA.  From the VMA, the type of mapping (private
or shared) and the location of the reservation map (inode or VMA) can be
determined.  These routines simply call the underlying routines described
in the section "Reservation Map Modifications".  However, they do take into
account the 'opposite' meaning of reservation map entries for private and
shared mappings and hide this detail from the caller::

	long vma_needs_reservation(struct hstate *h,
				   struct vm_area_struct *vma,
				   unsigned long addr)

This routine calls region_chg() for the specified page.  If no reservation
exists, 1 is returned.  If a reservation exists, 0 is returned::

	long vma_commit_reservation(struct hstate *h,
				    struct vm_area_struct *vma,
				    unsigned long addr)

This calls region_add() for the specified page.  As in the case of region_chg
and region_add, this routine is to be called after a previous call to
vma_needs_reservation.  It will add a reservation entry for the page.  It
returns 1 if the reservation was added and 0 if not.  The return value should
be compared with the return value of the previous call to
vma_needs_reservation.  An unexpected difference indicates the reservation
map was modified between calls::

	void vma_end_reservation(struct hstate *h,
				 struct vm_area_struct *vma,
				 unsigned long addr)

This calls region_abort() for the specified page.  As in the case of region_chg
and region_abort, this routine is to be called after a previous call to
vma_needs_reservation.  It will abort/end the in progress reservation add
operation::

	long vma_add_reservation(struct hstate *h,
				 struct vm_area_struct *vma,
				 unsigned long addr)

This is a special wrapper routine to help facilitate reservation cleanup
on error paths.  It is only called from the routine restore_reserve_on_error().
This routine is used in conjunction with vma_needs_reservation in an attempt
to add a reservation to the reservation map.  It takes into account the
different reservation map semantics for private and shared mappings.  Hence,
region_add is called for shared mappings (as an entry present in the map
indicates a reservation), and region_del is called for private mappings (as
the absence of an entry in the map indicates a reservation).  See the section
"Reservation cleanup in error paths" for more information on what needs to
be done on error paths.

Reservation Cleanup in Error Paths
==================================

As mentioned in the section
:ref:`Reservation Map Helper Routines <resv_map_helpers>`, reservation
map modifications are performed in two steps.  First vma_needs_reservation
is called before a page is allocated.  If the allocation is successful,
then vma_commit_reservation is called.  If not, vma_end_reservation is called.
Global and subpool reservation counts are adjusted based on success or failure
of the operation and all is well.

Additionally, after a huge page is instantiated the PagePrivate flag is
cleared so that accounting when the page is ultimately freed is correct.

However, there are several instances where errors are encountered after a huge
page is allocated but before it is instantiated.  In this case, the page
allocation has consumed the reservation and made the appropriate subpool,
reservation map and global count adjustments.  If the page is freed at this
time (before instantiation and clearing of PagePrivate), then free_huge_page
will increment the global reservation count.  However, the reservation map
indicates the reservation was consumed.  This resulting inconsistent state
will cause the 'leak' of a reserved huge page.  The global reserve count will
be  higher than it should and prevent allocation of a pre-allocated page.

The routine restore_reserve_on_error() attempts to handle this situation.  It
is fairly well documented.  The intention of this routine is to restore
the reservation map to the way it was before the page allocation.   In this
way, the state of the reservation map will correspond to the global reservation
count after the page is freed.

The routine restore_reserve_on_error itself may encounter errors while
attempting to restore the reservation map entry.  In this case, it will
simply clear the PagePrivate flag of the page.  In this way, the global
reserve count will not be incremented when the page is freed.  However, the
reservation map will continue to look as though the reservation was consumed.
A page can still be allocated for the address, but it will not use a reserved
page as originally intended.

There is some code (most notably userfaultfd) which can not call
restore_reserve_on_error.  In this case, it simply modifies the PagePrivate
so that a reservation will not be leaked when the huge page is freed.

Reservations and Memory Policy
==============================
Per-node huge page lists existed in struct hstate when git was first used
to manage Linux code.  The concept of reservations was added some time later.
When reservations were added, no attempt was made to take memory policy
into account.  While cpusets are not exactly the same as memory policy, this
comment in hugetlb_acct_memory sums up the interaction between reservations
and cpusets/memory policy::

	/*
	 * When cpuset is configured, it breaks the strict hugetlb page
	 * reservation as the accounting is done on a global variable. Such
	 * reservation is completely rubbish in the presence of cpuset because
	 * the reservation is not checked against page availability for the
	 * current cpuset. Application can still potentially OOM'ed by kernel
	 * with lack of free htlb page in cpuset that the task is in.
	 * Attempt to enforce strict accounting with cpuset is almost
	 * impossible (or too ugly) because cpuset is too fluid that
	 * task or memory node can be dynamically moved between cpusets.
	 *
	 * The change of semantics for shared hugetlb mapping with cpuset is
	 * undesirable. However, in order to preserve some of the semantics,
	 * we fall back to check against current free page availability as
	 * a best attempt and hopefully to minimize the impact of changing
	 * semantics that cpuset has.
	 */

Huge page reservations were added to prevent unexpected page allocation
failures (OOM) at page fault time.  However, if an application makes use
of cpusets or memory policy there is no guarantee that huge pages will be
available on the required nodes.  This is true even if there are a sufficient
number of global reservations.

Hugetlbfs regression testing
============================

The most complete set of hugetlb tests are in the libhugetlbfs repository.
If you modify any hugetlb related code, use the libhugetlbfs test suite
to check for regressions.  In addition, if you add any new hugetlb
functionality, please add appropriate tests to libhugetlbfs.

--
Mike Kravetz, 7 April 2017


code:
.. hwpoison:

========
hwpoison
========

What is hwpoison?
=================

Upcoming Intel CPUs have support for recovering from some memory errors
(``MCA recovery``). This requires the OS to declare a page "poisoned",
kill the processes associated with it and avoid using it in the future.

This patchkit implements the necessary infrastructure in the VM.

To quote the overview comment::

	High level machine check handler. Handles pages reported by the
	hardware as being corrupted usually due to a 2bit ECC memory or cache
	failure.

	This focusses on pages detected as corrupted in the background.
	When the current CPU tries to consume corruption the currently
	running process can just be killed directly instead. This implies
	that if the error cannot be handled for some reason it's safe to
	just ignore it because no corruption has been consumed yet. Instead
	when that happens another machine check will happen.

	Handles page cache pages in various states. The tricky part
	here is that we can access any page asynchronous to other VM
	users, because memory failures could happen anytime and anywhere,
	possibly violating some of their assumptions. This is why this code
	has to be extremely careful. Generally it tries to use normal locking
	rules, as in get the standard locks, even if that means the
	error handling takes potentially a long time.

	Some of the operations here are somewhat inefficient and have non
	linear algorithmic complexity, because the data structures have not
	been optimized for this case. This is in particular the case
	for the mapping from a vma to a process. Since this case is expected
	to be rare we hope we can get away with this.

The code consists of a the high level handler in mm/memory-failure.c,
a new page poison bit and various checks in the VM to handle poisoned
pages.

The main target right now is KVM guests, but it works for all kinds
of applications. KVM support requires a recent qemu-kvm release.

For the KVM use there was need for a new signal type so that
KVM can inject the machine check into the guest with the proper
address. This in theory allows other applications to handle
memory failures too. The expection is that near all applications
won't do that, but some very specialized ones might.

Failure recovery modes
======================

There are two (actually three) modes memory failure recovery can be in:

vm.memory_failure_recovery sysctl set to zero:
	All memory failures cause a panic. Do not attempt recovery.

early kill
	(can be controlled globally and per process)
	Send SIGBUS to the application as soon as the error is detected
	This allows applications who can process memory errors in a gentle
	way (e.g. drop affected object)
	This is the mode used by KVM qemu.

late kill
	Send SIGBUS when the application runs into the corrupted page.
	This is best for memory error unaware applications and default
	Note some pages are always handled as late kill.

User control
============

vm.memory_failure_recovery
	See sysctl.txt

vm.memory_failure_early_kill
	Enable early kill mode globally

PR_MCE_KILL
	Set early/late kill mode/revert to system default

	arg1: PR_MCE_KILL_CLEAR:
		Revert to system default
	arg1: PR_MCE_KILL_SET:
		arg2 defines thread specific mode

		PR_MCE_KILL_EARLY:
			Early kill
		PR_MCE_KILL_LATE:
			Late kill
		PR_MCE_KILL_DEFAULT
			Use system global default

	Note that if you want to have a dedicated thread which handles
	the SIGBUS(BUS_MCEERR_AO) on behalf of the process, you should
	call prctl(PR_MCE_KILL_EARLY) on the designated thread. Otherwise,
	the SIGBUS is sent to the main thread.

PR_MCE_KILL_GET
	return current mode

Testing
=======

* madvise(MADV_HWPOISON, ....) (as root) - Poison a page in the
  process for testing

* hwpoison-inject module through debugfs ``/sys/kernel/debug/hwpoison/``

  corrupt-pfn
	Inject hwpoison fault at PFN echoed into this file. This does
	some early filtering to avoid corrupted unintended pages in test suites.

  unpoison-pfn
	Software-unpoison page at PFN echoed into this file. This way
	a page can be reused again.  This only works for Linux
	injected failures, not for real memory failures. Once any hardware
	memory failure happens, this feature is disabled.

  Note these injection interfaces are not stable and might change between
  kernel versions

  corrupt-filter-dev-major, corrupt-filter-dev-minor
	Only handle memory failures to pages associated with the file
	system defined by block device major/minor.  -1U is the
	wildcard value.  This should be only used for testing with
	artificial injection.

  corrupt-filter-memcg
	Limit injection to pages owned by memgroup. Specified by inode
	number of the memcg.

	Example::

		mkdir /sys/fs/cgroup/mem/hwpoison

	        usemem -m 100 -s 1000 &
		echo `jobs -p` > /sys/fs/cgroup/mem/hwpoison/tasks

		memcg_ino=$(ls -id /sys/fs/cgroup/mem/hwpoison | cut -f1 -d' ')
		echo $memcg_ino > /debug/hwpoison/corrupt-filter-memcg

		page-types -p `pidof init`   --hwpoison  # shall do nothing
		page-types -p `pidof usemem` --hwpoison  # poison its pages

  corrupt-filter-flags-mask, corrupt-filter-flags-value
	When specified, only poison pages if ((page_flags & mask) ==
	value).  This allows stress testing of many kinds of
	pages. The page_flags are the same as in /proc/kpageflags. The
	flag bits are defined in include/linux/kernel-page-flags.h and
	documented in Documentation/admin-guide/mm/pagemap.rst

* Architecture specific MCE injector

  x86 has mce-inject, mce-test

  Some portable hwpoison test programs in mce-test, see below.

References
==========

http://halobates.de/mce-lc09-2.pdf
	Overview presentation from LinuxCon 09

git://git.kernel.org/pub/scm/utils/cpu/mce/mce-test.git
	Test suite (hwpoison specific portable tests in tsrc)

git://git.kernel.org/pub/scm/utils/cpu/mce/mce-inject.git
	x86 specific injector

Limitations
===========
- Not all page types are supported and never will. Most kernel internal
  objects cannot be recovered, only LRU pages for now.

---
Andi Kleen, Oct 2009


code:
=====================================
Linux Memory Management Documentation
=====================================

Memory Management Guide
=======================

This is a guide to understanding the memory management subsystem
of Linux.  If you are looking for advice on simply allocating memory,
see the :ref:`memory_allocation`.  For controlling and tuning guides,
see the :doc:`admin guide <../admin-guide/mm/index>`.

.. toctree::
   :maxdepth: 1

   physical_memory
   page_tables
   process_addrs
   bootmem
   page_allocation
   vmalloc
   slab
   highmem
   page_reclaim
   swap
   page_cache
   shmfs
   oom

Legacy Documentation
====================

This is a collection of older documents about the Linux memory management
(MM) subsystem internals with different level of details ranging from
notes and mailing list responses for elaborating descriptions of data
structures and algorithms.  It should all be integrated nicely into the
above structured documentation, or deleted if it has served its purpose.

.. toctree::
   :maxdepth: 1

   active_mm
   arch_pgtable_helpers
   balance
   damon/index
   free_page_reporting
   frontswap
   hmm
   hwpoison
   hugetlbfs_reserv
   ksm
   memory-model
   mmu_notifier
   multigen_lru
   numa
   overcommit-accounting
   page_migration
   page_frags
   page_owner
   page_table_check
   remap_file_pages
   slub
   split_page_table_lock
   transhuge
   unevictable-lru
   vmalloced-kernel-stacks
   vmemmap_dedup
   z3fold
   zsmalloc


code:
.. _ksm:

=======================
Kernel Samepage Merging
=======================

KSM is a memory-saving de-duplication feature, enabled by CONFIG_KSM=y,
added to the Linux kernel in 2.6.32.  See ``mm/ksm.c`` for its implementation,
and http://lwn.net/Articles/306704/ and https://lwn.net/Articles/330589/

The userspace interface of KSM is described in :ref:`Documentation/admin-guide/mm/ksm.rst <admin_guide_ksm>`

Design
======

Overview
--------

.. kernel-doc:: mm/ksm.c
   :DOC: Overview

Reverse mapping
---------------
KSM maintains reverse mapping information for KSM pages in the stable
tree.

If a KSM page is shared between less than ``max_page_sharing`` VMAs,
the node of the stable tree that represents such KSM page points to a
list of struct ksm_rmap_item and the ``page->mapping`` of the
KSM page points to the stable tree node.

When the sharing passes this threshold, KSM adds a second dimension to
the stable tree. The tree node becomes a "chain" that links one or
more "dups". Each "dup" keeps reverse mapping information for a KSM
page with ``page->mapping`` pointing to that "dup".

Every "chain" and all "dups" linked into a "chain" enforce the
invariant that they represent the same write protected memory content,
even if each "dup" will be pointed by a different KSM page copy of
that content.

This way the stable tree lookup computational complexity is unaffected
if compared to an unlimited list of reverse mappings. It is still
enforced that there cannot be KSM page content duplicates in the
stable tree itself.

The deduplication limit enforced by ``max_page_sharing`` is required
to avoid the virtual memory rmap lists to grow too large. The rmap
walk has O(N) complexity where N is the number of rmap_items
(i.e. virtual mappings) that are sharing the page, which is in turn
capped by ``max_page_sharing``. So this effectively spreads the linear
O(N) computational complexity from rmap walk context over different
KSM pages. The ksmd walk over the stable_node "chains" is also O(N),
but N is the number of stable_node "dups", not the number of
rmap_items, so it has not a significant impact on ksmd performance. In
practice the best stable_node "dup" candidate will be kept and found
at the head of the "dups" list.

High values of ``max_page_sharing`` result in faster memory merging
(because there will be fewer stable_node dups queued into the
stable_node chain->hlist to check for pruning) and higher
deduplication factor at the expense of slower worst case for rmap
walks for any KSM page which can happen during swapping, compaction,
NUMA balancing and page migration.

The ``stable_node_dups/stable_node_chains`` ratio is also affected by the
``max_page_sharing`` tunable, and an high ratio may indicate fragmentation
in the stable_node dups, which could be solved by introducing
fragmentation algorithms in ksmd which would refile rmap_items from
one stable_node dup to another stable_node dup, in order to free up
stable_node "dups" with few rmap_items in them, but that may increase
the ksmd CPU usage and possibly slowdown the readonly computations on
the KSM pages of the applications.

The whole list of stable_node "dups" linked in the stable_node
"chains" is scanned periodically in order to prune stale stable_nodes.
The frequency of such scans is defined by
``stable_node_chains_prune_millisecs`` sysfs tunable.

Reference
---------
.. kernel-doc:: mm/ksm.c
   :functions: mm_slot ksm_scan stable_node rmap_item

--
Izik Eidus,
Hugh Dickins, 17 Nov 2009