code:
.. _memory_allocation:

=======================
Memory Allocation Guide
=======================

Linux provides a variety of APIs for memory allocation. You can
allocate small chunks using `kmalloc` or `kmem_cache_alloc` families,
large virtually contiguous areas using `vmalloc` and its derivatives,
or you can directly request pages from the page allocator with
`alloc_pages`. It is also possible to use more specialized allocators,
for instance `cma_alloc` or `zs_malloc`.

Most of the memory allocation APIs use GFP flags to express how that
memory should be allocated. The GFP acronym stands for "get free
pages", the underlying memory allocation function.

Diversity of the allocation APIs combined with the numerous GFP flags
makes the question "How should I allocate memory?" not that easy to
answer, although very likely you should use

::

  kzalloc(<size>, GFP_KERNEL);

Of course there are cases when other allocation APIs and different GFP
flags must be used.

Get Free Page flags
===================

The GFP flags control the allocators behavior. They tell what memory
zones can be used, how hard the allocator should try to find free
memory, whether the memory can be accessed by the userspace etc. The
:ref:`Documentation/core-api/mm-api.rst <mm-api-gfp-flags>` provides
reference documentation for the GFP flags and their combinations and
here we briefly outline their recommended usage:

  * Most of the time ``GFP_KERNEL`` is what you need. Memory for the
    kernel data structures, DMAable memory, inode cache, all these and
    many other allocations types can use ``GFP_KERNEL``. Note, that
    using ``GFP_KERNEL`` implies ``GFP_RECLAIM``, which means that
    direct reclaim may be triggered under memory pressure; the calling
    context must be allowed to sleep.
  * If the allocation is performed from an atomic context, e.g interrupt
    handler, use ``GFP_NOWAIT``. This flag prevents direct reclaim and
    IO or filesystem operations. Consequently, under memory pressure
    ``GFP_NOWAIT`` allocation is likely to fail. Allocations which
    have a reasonable fallback should be using ``GFP_NOWARN``.
  * If you think that accessing memory reserves is justified and the kernel
    will be stressed unless allocation succeeds, you may use ``GFP_ATOMIC``.
  * Untrusted allocations triggered from userspace should be a subject
    of kmem accounting and must have ``__GFP_ACCOUNT`` bit set. There
    is the handy ``GFP_KERNEL_ACCOUNT`` shortcut for ``GFP_KERNEL``
    allocations that should be accounted.
  * Userspace allocations should use either of the ``GFP_USER``,
    ``GFP_HIGHUSER`` or ``GFP_HIGHUSER_MOVABLE`` flags. The longer
    the flag name the less restrictive it is.

    ``GFP_HIGHUSER_MOVABLE`` does not require that allocated memory
    will be directly accessible by the kernel and implies that the
    data is movable.

    ``GFP_HIGHUSER`` means that the allocated memory is not movable,
    but it is not required to be directly accessible by the kernel. An
    example may be a hardware allocation that maps data directly into
    userspace but has no addressing limitations.

    ``GFP_USER`` means that the allocated memory is not movable and it
    must be directly accessible by the kernel.

You may notice that quite a few allocations in the existing code
specify ``GFP_NOIO`` or ``GFP_NOFS``. Historically, they were used to
prevent recursion deadlocks caused by direct memory reclaim calling
back into the FS or IO paths and blocking on already held
resources. Since 4.12 the preferred way to address this issue is to
use new scope APIs described in
:ref:`Documentation/core-api/gfp_mask-from-fs-io.rst <gfp_mask_from_fs_io>`.

Other legacy GFP flags are ``GFP_DMA`` and ``GFP_DMA32``. They are
used to ensure that the allocated memory is accessible by hardware
with limited addressing capabilities. So unless you are writing a
driver for a device with such restrictions, avoid using these flags.
And even with hardware with restrictions it is preferable to use
`dma_alloc*` APIs.

GFP flags and reclaim behavior
------------------------------
Memory allocations may trigger direct or background reclaim and it is
useful to understand how hard the page allocator will try to satisfy that
or another request.

  * ``GFP_KERNEL & ~__GFP_RECLAIM`` - optimistic allocation without _any_
    attempt to free memory at all. The most light weight mode which even
    doesn't kick the background reclaim. Should be used carefully because it
    might deplete the memory and the next user might hit the more aggressive
    reclaim.

  * ``GFP_KERNEL & ~__GFP_DIRECT_RECLAIM`` (or ``GFP_NOWAIT``)- optimistic
    allocation without any attempt to free memory from the current
    context but can wake kswapd to reclaim memory if the zone is below
    the low watermark. Can be used from either atomic contexts or when
    the request is a performance optimization and there is another
    fallback for a slow path.

  * ``(GFP_KERNEL|__GFP_HIGH) & ~__GFP_DIRECT_RECLAIM`` (aka ``GFP_ATOMIC``) -
    non sleeping allocation with an expensive fallback so it can access
    some portion of memory reserves. Usually used from interrupt/bottom-half
    context with an expensive slow path fallback.

  * ``GFP_KERNEL`` - both background and direct reclaim are allowed and the
    **default** page allocator behavior is used. That means that not costly
    allocation requests are basically no-fail but there is no guarantee of
    that behavior so failures have to be checked properly by callers
    (e.g. OOM killer victim is allowed to fail currently).

  * ``GFP_KERNEL | __GFP_NORETRY`` - overrides the default allocator behavior
    and all allocation requests fail early rather than cause disruptive
    reclaim (one round of reclaim in this implementation). The OOM killer
    is not invoked.

  * ``GFP_KERNEL | __GFP_RETRY_MAYFAIL`` - overrides the default allocator
    behavior and all allocation requests try really hard. The request
    will fail if the reclaim cannot make any progress. The OOM killer
    won't be triggered.

  * ``GFP_KERNEL | __GFP_NOFAIL`` - overrides the default allocator behavior
    and all allocation requests will loop endlessly until they succeed.
    This might be really dangerous especially for larger orders.

Selecting memory allocator
==========================

The most straightforward way to allocate memory is to use a function
from the kmalloc() family. And, to be on the safe side it's best to use
routines that set memory to zero, like kzalloc(). If you need to
allocate memory for an array, there are kmalloc_array() and kcalloc()
helpers. The helpers struct_size(), array_size() and array3_size() can
be used to safely calculate object sizes without overflowing.

The maximal size of a chunk that can be allocated with `kmalloc` is
limited. The actual limit depends on the hardware and the kernel
configuration, but it is a good practice to use `kmalloc` for objects
smaller than page size.

The address of a chunk allocated with `kmalloc` is aligned to at least
ARCH_KMALLOC_MINALIGN bytes.  For sizes which are a power of two, the
alignment is also guaranteed to be at least the respective size.

Chunks allocated with kmalloc() can be resized with krealloc(). Similarly
to kmalloc_array(): a helper for resizing arrays is provided in the form of
krealloc_array().

For large allocations you can use vmalloc() and vzalloc(), or directly
request pages from the page allocator. The memory allocated by `vmalloc`
and related functions is not physically contiguous.

If you are not sure whether the allocation size is too large for
`kmalloc`, it is possible to use kvmalloc() and its derivatives. It will
try to allocate memory with `kmalloc` and if the allocation fails it
will be retried with `vmalloc`. There are restrictions on which GFP
flags can be used with `kvmalloc`; please see kvmalloc_node() reference
documentation. Note that `kvmalloc` may return memory that is not
physically contiguous.

If you need to allocate many identical objects you can use the slab
cache allocator. The cache should be set up with kmem_cache_create() or
kmem_cache_create_usercopy() before it can be used. The second function
should be used if a part of the cache might be copied to the userspace.
After the cache is created kmem_cache_alloc() and its convenience
wrappers can allocate memory from that cache.

When the allocated memory is no longer needed it must be freed. You can
use kvfree() for the memory allocated with `kmalloc`, `vmalloc` and
`kvmalloc`. The slab caches should be freed with kmem_cache_free(). And
don't forget to destroy the cache with kmem_cache_destroy().


code:
.. _memory_hotplug:

==============
Memory hotplug
==============

Memory hotplug event notifier
=============================

Hotplugging events are sent to a notification queue.

There are six types of notification defined in ``include/linux/memory.h``:

MEM_GOING_ONLINE
  Generated before new memory becomes available in order to be able to
  prepare subsystems to handle memory. The page allocator is still unable
  to allocate from the new memory.

MEM_CANCEL_ONLINE
  Generated if MEM_GOING_ONLINE fails.

MEM_ONLINE
  Generated when memory has successfully brought online. The callback may
  allocate pages from the new memory.

MEM_GOING_OFFLINE
  Generated to begin the process of offlining memory. Allocations are no
  longer possible from the memory but some of the memory to be offlined
  is still in use. The callback can be used to free memory known to a
  subsystem from the indicated memory block.

MEM_CANCEL_OFFLINE
  Generated if MEM_GOING_OFFLINE fails. Memory is available again from
  the memory block that we attempted to offline.

MEM_OFFLINE
  Generated after offlining memory is complete.

A callback routine can be registered by calling::

  hotplug_memory_notifier(callback_func, priority)

Callback functions with higher values of priority are called before callback
functions with lower values.

A callback function must have the following prototype::

  int callback_func(
    struct notifier_block *self, unsigned long action, void *arg);

The first argument of the callback function (self) is a pointer to the block
of the notifier chain that points to the callback function itself.
The second argument (action) is one of the event types described above.
The third argument (arg) passes a pointer of struct memory_notify::

	struct memory_notify {
		unsigned long start_pfn;
		unsigned long nr_pages;
		int status_change_nid_normal;
		int status_change_nid;
	}

- start_pfn is start_pfn of online/offline memory.
- nr_pages is # of pages of online/offline memory.
- status_change_nid_normal is set node id when N_NORMAL_MEMORY of nodemask
  is (will be) set/clear, if this is -1, then nodemask status is not changed.
- status_change_nid is set node id when N_MEMORY of nodemask is (will be)
  set/clear. It means a new(memoryless) node gets new memory by online and a
  node loses all memory. If this is -1, then nodemask status is not changed.

  If status_changed_nid* >= 0, callback should create/discard structures for the
  node if necessary.

The callback routine shall return one of the values
NOTIFY_DONE, NOTIFY_OK, NOTIFY_BAD, NOTIFY_STOP
defined in ``include/linux/notifier.h``

NOTIFY_DONE and NOTIFY_OK have no effect on the further processing.

NOTIFY_BAD is used as response to the MEM_GOING_ONLINE, MEM_GOING_OFFLINE,
MEM_ONLINE, or MEM_OFFLINE action to cancel hotplugging. It stops
further processing of the notification queue.

NOTIFY_STOP stops further processing of the notification queue.

Locking Internals
=================

When adding/removing memory that uses memory block devices (i.e. ordinary RAM),
the device_hotplug_lock should be held to:

- synchronize against online/offline requests (e.g. via sysfs). This way, memory
  block devices can only be accessed (.online/.state attributes) by user
  space once memory has been fully added. And when removing memory, we
  know nobody is in critical sections.
- synchronize against CPU hotplug and similar (e.g. relevant for ACPI and PPC)

Especially, there is a possible lock inversion that is avoided using
device_hotplug_lock when adding memory and user space tries to online that
memory faster than expected:

- device_online() will first take the device_lock(), followed by
  mem_hotplug_lock
- add_memory_resource() will first take the mem_hotplug_lock, followed by
  the device_lock() (while creating the devices, during bus_add_device()).

As the device is visible to user space before taking the device_lock(), this
can result in a lock inversion.

onlining/offlining of memory should be done via device_online()/
device_offline() - to make sure it is properly synchronized to actions
via sysfs. Holding device_hotplug_lock is advised (to e.g. protect online_type)

When adding/removing/onlining/offlining memory or adding/removing
heterogeneous/device memory, we should always hold the mem_hotplug_lock in
write mode to serialise memory hotplug (e.g. access to global/zone
variables).

In addition, mem_hotplug_lock (in contrast to device_hotplug_lock) in read
mode allows for a quite efficient get_online_mems/put_online_mems
implementation, so code accessing memory can protect from that memory
vanishing.

repo_name: angery/linux


code:
======================
Memory Management APIs
======================

User Space Memory Access
========================

.. kernel-doc:: arch/x86/include/asm/uaccess.h
   :internal:

.. kernel-doc:: arch/x86/lib/usercopy_32.c
   :export:

.. kernel-doc:: mm/gup.c
   :functions: get_user_pages_fast

.. _mm-api-gfp-flags:

Memory Allocation Controls
==========================

.. kernel-doc:: include/linux/gfp_types.h
   :doc: Page mobility and placement hints

.. kernel-doc:: include/linux/gfp_types.h
   :doc: Watermark modifiers

.. kernel-doc:: include/linux/gfp_types.h
   :doc: Reclaim modifiers

.. kernel-doc:: include/linux/gfp_types.h
   :doc: Useful GFP flag combinations

The Slab Cache
==============

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

.. kernel-doc:: mm/slab.c
   :export:

.. kernel-doc:: mm/slab_common.c
   :export:

.. kernel-doc:: mm/util.c
   :functions: kfree_const kvmalloc_node kvfree

Virtually Contiguous Mappings
=============================

.. kernel-doc:: mm/vmalloc.c
   :export:

File Mapping and Page Cache
===========================

Filemap
-------

.. kernel-doc:: mm/filemap.c
   :export:

Readahead
---------

.. kernel-doc:: mm/readahead.c
   :doc: Readahead Overview

.. kernel-doc:: mm/readahead.c
   :export:

Writeback
---------

.. kernel-doc:: mm/page-writeback.c
   :export:

Truncate
--------

.. kernel-doc:: mm/truncate.c
   :export:

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

Memory pools
============

.. kernel-doc:: mm/mempool.c
   :export:

DMA pools
=========

.. kernel-doc:: mm/dmapool.c
   :export:

More Memory Management Functions
================================

.. kernel-doc:: mm/memory.c
   :export:

.. kernel-doc:: mm/page_alloc.c
.. kernel-doc:: mm/mempolicy.c
.. kernel-doc:: include/linux/mm_types.h
   :internal:
.. kernel-doc:: include/linux/mm_inline.h
.. kernel-doc:: include/linux/page-flags.h
.. kernel-doc:: include/linux/mm.h
   :internal:
.. kernel-doc:: include/linux/page_ref.h
.. kernel-doc:: include/linux/mmzone.h
.. kernel-doc:: mm/util.c
   :functions: folio_mapping


code:
================================================
Generic bitfield packing and unpacking functions
================================================

Problem statement
-----------------

When working with hardware, one has to choose between several approaches of
interfacing with it.
One can memory-map a pointer to a carefully crafted struct over the hardware
device's memory region, and access its fields as struct members (potentially
declared as bitfields). But writing code this way would make it less portable,
due to potential endianness mismatches between the CPU and the hardware device.
Additionally, one has to pay close attention when translating register
definitions from the hardware documentation into bit field indices for the
structs. Also, some hardware (typically networking equipment) tends to group
its register fields in ways that violate any reasonable word boundaries
(sometimes even 64 bit ones). This creates the inconvenience of having to
define "high" and "low" portions of register fields within the struct.
A more robust alternative to struct field definitions would be to extract the
required fields by shifting the appropriate number of bits. But this would
still not protect from endianness mismatches, except if all memory accesses
were performed byte-by-byte. Also the code can easily get cluttered, and the
high-level idea might get lost among the many bit shifts required.
Many drivers take the bit-shifting approach and then attempt to reduce the
clutter with tailored macros, but more often than not these macros take
shortcuts that still prevent the code from being truly portable.

The solution
------------

This API deals with 2 basic operations:

  - Packing a CPU-usable number into a memory buffer (with hardware
    constraints/quirks)
  - Unpacking a memory buffer (which has hardware constraints/quirks)
    into a CPU-usable number.

The API offers an abstraction over said hardware constraints and quirks,
over CPU endianness and therefore between possible mismatches between
the two.

The basic unit of these API functions is the u64. From the CPU's
perspective, bit 63 always means bit offset 7 of byte 7, albeit only
logically. The question is: where do we lay this bit out in memory?

The following examples cover the memory layout of a packed u64 field.
The byte offsets in the packed buffer are always implicitly 0, 1, ... 7.
What the examples show is where the logical bytes and bits sit.

1. Normally (no quirks), we would do it like this:

::

  63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32
  7                       6                       5                        4
  31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
  3                       2                       1                        0

That is, the MSByte (7) of the CPU-usable u64 sits at memory offset 0, and the
LSByte (0) of the u64 sits at memory offset 7.
This corresponds to what most folks would regard to as "big endian", where
bit i corresponds to the number 2^i. This is also referred to in the code
comments as "logical" notation.

2. If QUIRK_MSB_ON_THE_RIGHT is set, we do it like this:

::

  56 57 58 59 60 61 62 63 48 49 50 51 52 53 54 55 40 41 42 43 44 45 46 47 32 33 34 35 36 37 38 39
  7                       6                        5                       4
  24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7
  3                       2                        1                       0

That is, QUIRK_MSB_ON_THE_RIGHT does not affect byte positioning, but
inverts bit offsets inside a byte.

3. If QUIRK_LITTLE_ENDIAN is set, we do it like this:

::

  39 38 37 36 35 34 33 32 47 46 45 44 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56
  4                       5                       6                       7
  7  6  5  4  3  2  1  0  15 14 13 12 11 10  9  8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24
  0                       1                       2                       3

Therefore, QUIRK_LITTLE_ENDIAN means that inside the memory region, every
byte from each 4-byte word is placed at its mirrored position compared to
the boundary of that word.

4. If QUIRK_MSB_ON_THE_RIGHT and QUIRK_LITTLE_ENDIAN are both set, we do it
   like this:

::

  32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
  4                       5                       6                       7
  0  1  2  3  4  5  6  7  8   9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
  0                       1                       2                       3

5. If just QUIRK_LSW32_IS_FIRST is set, we do it like this:

::

  31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
  3                       2                       1                        0
  63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32
  7                       6                       5                        4

In this case the 8 byte memory region is interpreted as follows: first
4 bytes correspond to the least significant 4-byte word, next 4 bytes to
the more significant 4-byte word.

6. If QUIRK_LSW32_IS_FIRST and QUIRK_MSB_ON_THE_RIGHT are set, we do it like
   this:

::

  24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7
  3                       2                        1                       0
  56 57 58 59 60 61 62 63 48 49 50 51 52 53 54 55 40 41 42 43 44 45 46 47 32 33 34 35 36 37 38 39
  7                       6                        5                       4

7. If QUIRK_LSW32_IS_FIRST and QUIRK_LITTLE_ENDIAN are set, it looks like
   this:

::

  7  6  5  4  3  2  1  0  15 14 13 12 11 10  9  8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24
  0                       1                       2                       3
  39 38 37 36 35 34 33 32 47 46 45 44 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56
  4                       5                       6                       7

8. If QUIRK_LSW32_IS_FIRST, QUIRK_LITTLE_ENDIAN and QUIRK_MSB_ON_THE_RIGHT
   are set, it looks like this:

::

  0  1  2  3  4  5  6  7  8   9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
  0                       1                       2                       3
  32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
  4                       5                       6                       7

We always think of our offsets as if there were no quirk, and we translate
them afterwards, before accessing the memory region.

Intended use
------------

Drivers that opt to use this API first need to identify which of the above 3
quirk combinations (for a total of 8) match what the hardware documentation
describes. Then they should wrap the packing() function, creating a new
xxx_packing() that calls it using the proper QUIRK_* one-hot bits set.

The packing() function returns an int-encoded error code, which protects the
programmer against incorrect API use.  The errors are not expected to occur
durring runtime, therefore it is reasonable for xxx_packing() to return void
and simply swallow those errors. Optionally it can dump stack or print the
error description.


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

=======================================
The padata parallel execution mechanism
=======================================

:Date: May 2020

Padata is a mechanism by which the kernel can farm jobs out to be done in
parallel on multiple CPUs while optionally retaining their ordering.

It was originally developed for IPsec, which needs to perform encryption and
decryption on large numbers of packets without reordering those packets.  This
is currently the sole consumer of padata's serialized job support.

Padata also supports multithreaded jobs, splitting up the job evenly while load
balancing and coordinating between threads.

Running Serialized Jobs
=======================

Initializing
------------

The first step in using padata to run serialized jobs is to set up a
padata_instance structure for overall control of how jobs are to be run::

    #include <linux/padata.h>

    struct padata_instance *padata_alloc(const char *name);

'name' simply identifies the instance.

Then, complete padata initialization by allocating a padata_shell::

   struct padata_shell *padata_alloc_shell(struct padata_instance *pinst);

A padata_shell is used to submit a job to padata and allows a series of such
jobs to be serialized independently.  A padata_instance may have one or more
padata_shells associated with it, each allowing a separate series of jobs.

Modifying cpumasks
------------------

The CPUs used to run jobs can be changed in two ways, programatically with
padata_set_cpumask() or via sysfs.  The former is defined::

    int padata_set_cpumask(struct padata_instance *pinst, int cpumask_type,
			   cpumask_var_t cpumask);

Here cpumask_type is one of PADATA_CPU_PARALLEL or PADATA_CPU_SERIAL, where a
parallel cpumask describes which processors will be used to execute jobs
submitted to this instance in parallel and a serial cpumask defines which
processors are allowed to be used as the serialization callback processor.
cpumask specifies the new cpumask to use.

There may be sysfs files for an instance's cpumasks.  For example, pcrypt's
live in /sys/kernel/pcrypt/<instance-name>.  Within an instance's directory
there are two files, parallel_cpumask and serial_cpumask, and either cpumask
may be changed by echoing a bitmask into the file, for example::

    echo f > /sys/kernel/pcrypt/pencrypt/parallel_cpumask

Reading one of these files shows the user-supplied cpumask, which may be
different from the 'usable' cpumask.

Padata maintains two pairs of cpumasks internally, the user-supplied cpumasks
and the 'usable' cpumasks.  (Each pair consists of a parallel and a serial
cpumask.)  The user-supplied cpumasks default to all possible CPUs on instance
allocation and may be changed as above.  The usable cpumasks are always a
subset of the user-supplied cpumasks and contain only the online CPUs in the
user-supplied masks; these are the cpumasks padata actually uses.  So it is
legal to supply a cpumask to padata that contains offline CPUs.  Once an
offline CPU in the user-supplied cpumask comes online, padata is going to use
it.

Changing the CPU masks are expensive operations, so it should not be done with
great frequency.

Running A Job
-------------

Actually submitting work to the padata instance requires the creation of a
padata_priv structure, which represents one job::

    struct padata_priv {
        /* Other stuff here... */
	void                    (*parallel)(struct padata_priv *padata);
	void                    (*serial)(struct padata_priv *padata);
    };

This structure will almost certainly be embedded within some larger
structure specific to the work to be done.  Most of its fields are private to
padata, but the structure should be zeroed at initialisation time, and the
parallel() and serial() functions should be provided.  Those functions will
be called in the process of getting the work done as we will see
momentarily.

The submission of the job is done with::

    int padata_do_parallel(struct padata_shell *ps,
		           struct padata_priv *padata, int *cb_cpu);

The ps and padata structures must be set up as described above; cb_cpu
points to the preferred CPU to be used for the final callback when the job is
done; it must be in the current instance's CPU mask (if not the cb_cpu pointer
is updated to point to the CPU actually chosen).  The return value from
padata_do_parallel() is zero on success, indicating that the job is in
progress. -EBUSY means that somebody, somewhere else is messing with the
instance's CPU mask, while -EINVAL is a complaint about cb_cpu not being in the
serial cpumask, no online CPUs in the parallel or serial cpumasks, or a stopped
instance.

Each job submitted to padata_do_parallel() will, in turn, be passed to
exactly one call to the above-mentioned parallel() function, on one CPU, so
true parallelism is achieved by submitting multiple jobs.  parallel() runs with
software interrupts disabled and thus cannot sleep.  The parallel()
function gets the padata_priv structure pointer as its lone parameter;
information about the actual work to be done is probably obtained by using
container_of() to find the enclosing structure.

Note that parallel() has no return value; the padata subsystem assumes that
parallel() will take responsibility for the job from this point.  The job
need not be completed during this call, but, if parallel() leaves work
outstanding, it should be prepared to be called again with a new job before
the previous one completes.

Serializing Jobs
----------------

When a job does complete, parallel() (or whatever function actually finishes
the work) should inform padata of the fact with a call to::

    void padata_do_serial(struct padata_priv *padata);

At some point in the future, padata_do_serial() will trigger a call to the
serial() function in the padata_priv structure.  That call will happen on
the CPU requested in the initial call to padata_do_parallel(); it, too, is
run with local software interrupts disabled.
Note that this call may be deferred for a while since the padata code takes
pains to ensure that jobs are completed in the order in which they were
submitted.

Destroying
----------

Cleaning up a padata instance predictably involves calling the two free
functions that correspond to the allocation in reverse::

    void padata_free_shell(struct padata_shell *ps);
    void padata_free(struct padata_instance *pinst);

It is the user's responsibility to ensure all outstanding jobs are complete
before any of the above are called.

Running Multithreaded Jobs
==========================

A multithreaded job has a main thread and zero or more helper threads, with the
main thread participating in the job and then waiting until all helpers have
finished.  padata splits the job into units called chunks, where a chunk is a
piece of the job that one thread completes in one call to the thread function.

A user has to do three things to run a multithreaded job.  First, describe the
job by defining a padata_mt_job structure, which is explained in the Interface
section.  This includes a pointer to the thread function, which padata will
call each time it assigns a job chunk to a thread.  Then, define the thread
function, which accepts three arguments, ``start``, ``end``, and ``arg``, where
the first two delimit the range that the thread operates on and the last is a
pointer to the job's shared state, if any.  Prepare the shared state, which is
typically allocated on the main thread's stack.  Last, call
padata_do_multithreaded(), which will return once the job is finished.

Interface
=========

.. kernel-doc:: include/linux/padata.h
.. kernel-doc:: kernel/padata.c


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

====================================================
pin_user_pages() and related calls
====================================================

.. contents:: :local:

Overview
========

This document describes the following functions::

 pin_user_pages()
 pin_user_pages_fast()
 pin_user_pages_remote()

Basic description of FOLL_PIN
=============================

FOLL_PIN and FOLL_LONGTERM are flags that can be passed to the get_user_pages*()
("gup") family of functions. FOLL_PIN has significant interactions and
interdependencies with FOLL_LONGTERM, so both are covered here.

FOLL_PIN is internal to gup, meaning that it should not appear at the gup call
sites. This allows the associated wrapper functions  (pin_user_pages*() and
others) to set the correct combination of these flags, and to check for problems
as well.

FOLL_LONGTERM, on the other hand, *is* allowed to be set at the gup call sites.
This is in order to avoid creating a large number of wrapper functions to cover
all combinations of get*(), pin*(), FOLL_LONGTERM, and more. Also, the
pin_user_pages*() APIs are clearly distinct from the get_user_pages*() APIs, so
that's a natural dividing line, and a good point to make separate wrapper calls.
In other words, use pin_user_pages*() for DMA-pinned pages, and
get_user_pages*() for other cases. There are five cases described later on in
this document, to further clarify that concept.

FOLL_PIN and FOLL_GET are mutually exclusive for a given gup call. However,
multiple threads and call sites are free to pin the same struct pages, via both
FOLL_PIN and FOLL_GET. It's just the call site that needs to choose one or the
other, not the struct page(s).

The FOLL_PIN implementation is nearly the same as FOLL_GET, except that FOLL_PIN
uses a different reference counting technique.

FOLL_PIN is a prerequisite to FOLL_LONGTERM. Another way of saying that is,
FOLL_LONGTERM is a specific case, more restrictive case of FOLL_PIN.

Which flags are set by each wrapper
===================================

For these pin_user_pages*() functions, FOLL_PIN is OR'd in with whatever gup
flags the caller provides. The caller is required to pass in a non-null struct
pages* array, and the function then pins pages by incrementing each by a special
value: GUP_PIN_COUNTING_BIAS.

For compound pages, the GUP_PIN_COUNTING_BIAS scheme is not used. Instead,
an exact form of pin counting is achieved, by using the 2nd struct page
in the compound page. A new struct page field, compound_pincount, has
been added in order to support this.

This approach for compound pages avoids the counting upper limit problems that
are discussed below. Those limitations would have been aggravated severely by
huge pages, because each tail page adds a refcount to the head page. And in
fact, testing revealed that, without a separate compound_pincount field,
page overflows were seen in some huge page stress tests.

This also means that huge pages and compound pages do not suffer
from the false positives problem that is mentioned below.::

 Function
 --------
 pin_user_pages          FOLL_PIN is always set internally by this function.
 pin_user_pages_fast     FOLL_PIN is always set internally by this function.
 pin_user_pages_remote   FOLL_PIN is always set internally by this function.

For these get_user_pages*() functions, FOLL_GET might not even be specified.
Behavior is a little more complex than above. If FOLL_GET was *not* specified,
but the caller passed in a non-null struct pages* array, then the function
sets FOLL_GET for you, and proceeds to pin pages by incrementing the refcount
of each page by +1.::

 Function
 --------
 get_user_pages           FOLL_GET is sometimes set internally by this function.
 get_user_pages_fast      FOLL_GET is sometimes set internally by this function.
 get_user_pages_remote    FOLL_GET is sometimes set internally by this function.

Tracking dma-pinned pages
=========================

Some of the key design constraints, and solutions, for tracking dma-pinned
pages:

* An actual reference count, per struct page, is required. This is because
  multiple processes may pin and unpin a page.

* False positives (reporting that a page is dma-pinned, when in fact it is not)
  are acceptable, but false negatives are not.

* struct page may not be increased in size for this, and all fields are already
  used.

* Given the above, we can overload the page->_refcount field by using, sort of,
  the upper bits in that field for a dma-pinned count. "Sort of", means that,
  rather than dividing page->_refcount into bit fields, we simple add a medium-
  large value (GUP_PIN_COUNTING_BIAS, initially chosen to be 1024: 10 bits) to
  page->_refcount. This provides fuzzy behavior: if a page has get_page() called
  on it 1024 times, then it will appear to have a single dma-pinned count.
  And again, that's acceptable.

This also leads to limitations: there are only 31-10==21 bits available for a
counter that increments 10 bits at a time.

* Callers must specifically request "dma-pinned tracking of pages". In other
  words, just calling get_user_pages() will not suffice; a new set of functions,
  pin_user_page() and related, must be used.

FOLL_PIN, FOLL_GET, FOLL_LONGTERM: when to use which flags
==========================================================

Thanks to Jan Kara, Vlastimil Babka and several other -mm people, for describing
these categories:

CASE 1: Direct IO (DIO)
-----------------------
There are GUP references to pages that are serving
as DIO buffers. These buffers are needed for a relatively short time (so they
are not "long term"). No special synchronization with page_mkclean() or
munmap() is provided. Therefore, flags to set at the call site are: ::

    FOLL_PIN

...but rather than setting FOLL_PIN directly, call sites should use one of
the pin_user_pages*() routines that set FOLL_PIN.

CASE 2: RDMA
------------
There are GUP references to pages that are serving as DMA
buffers. These buffers are needed for a long time ("long term"). No special
synchronization with page_mkclean() or munmap() is provided. Therefore, flags
to set at the call site are: ::

    FOLL_PIN | FOLL_LONGTERM

NOTE: Some pages, such as DAX pages, cannot be pinned with longterm pins. That's
because DAX pages do not have a separate page cache, and so "pinning" implies
locking down file system blocks, which is not (yet) supported in that way.

CASE 3: MMU notifier registration, with or without page faulting hardware
-------------------------------------------------------------------------
Device drivers can pin pages via get_user_pages*(), and register for mmu
notifier callbacks for the memory range. Then, upon receiving a notifier
"invalidate range" callback , stop the device from using the range, and unpin
the pages. There may be other possible schemes, such as for example explicitly
synchronizing against pending IO, that accomplish approximately the same thing.

Or, if the hardware supports replayable page faults, then the device driver can
avoid pinning entirely (this is ideal), as follows: register for mmu notifier
callbacks as above, but instead of stopping the device and unpinning in the
callback, simply remove the range from the device's page tables.

Either way, as long as the driver unpins the pages upon mmu notifier callback,
then there is proper synchronization with both filesystem and mm
(page_mkclean(), munmap(), etc). Therefore, neither flag needs to be set.

CASE 4: Pinning for struct page manipulation only
-------------------------------------------------
If only struct page data (as opposed to the actual memory contents that a page
is tracking) is affected, then normal GUP calls are sufficient, and neither flag
needs to be set.

CASE 5: Pinning in order to write to the data within the page
-------------------------------------------------------------
Even though neither DMA nor Direct IO is involved, just a simple case of "pin,
write to a page's data, unpin" can cause a problem. Case 5 may be considered a
superset of Case 1, plus Case 2, plus anything that invokes that pattern. In
other words, if the code is neither Case 1 nor Case 2, it may still require
FOLL_PIN, for patterns like this:

Correct (uses FOLL_PIN calls):
    pin_user_pages()
    write to the data within the pages
    unpin_user_pages()

INCORRECT (uses FOLL_GET calls):
    get_user_pages()
    write to the data within the pages
    put_page()

page_maybe_dma_pinned(): the whole point of pinning
===================================================

The whole point of marking pages as "DMA-pinned" or "gup-pinned" is to be able
to query, "is this page DMA-pinned?" That allows code such as page_mkclean()
(and file system writeback code in general) to make informed decisions about
what to do when a page cannot be unmapped due to such pins.

What to do in those cases is the subject of a years-long series of discussions
and debates (see the References at the end of this document). It's a TODO item
here: fill in the details once that's worked out. Meanwhile, it's safe to say
that having this available: ::

        static inline bool page_maybe_dma_pinned(struct page *page)

...is a prerequisite to solving the long-running gup+DMA problem.

Another way of thinking about FOLL_GET, FOLL_PIN, and FOLL_LONGTERM
===================================================================

Another way of thinking about these flags is as a progression of restrictions:
FOLL_GET is for struct page manipulation, without affecting the data that the
struct page refers to. FOLL_PIN is a *replacement* for FOLL_GET, and is for
short term pins on pages whose data *will* get accessed. As such, FOLL_PIN is
a "more severe" form of pinning. And finally, FOLL_LONGTERM is an even more
restrictive case that has FOLL_PIN as a prerequisite: this is for pages that
will be pinned longterm, and whose data will be accessed.

Unit testing
============
This file::

 tools/testing/selftests/vm/gup_test.c

has the following new calls to exercise the new pin*() wrapper functions:

* PIN_FAST_BENCHMARK (./gup_test -a)
* PIN_BASIC_TEST (./gup_test -b)

You can monitor how many total dma-pinned pages have been acquired and released
since the system was booted, via two new /proc/vmstat entries: ::

    /proc/vmstat/nr_foll_pin_acquired
    /proc/vmstat/nr_foll_pin_released

Under normal conditions, these two values will be equal unless there are any
long-term [R]DMA pins in place, or during pin/unpin transitions.

* nr_foll_pin_acquired: This is the number of logical pins that have been
  acquired since the system was powered on. For huge pages, the head page is
  pinned once for each page (head page and each tail page) within the huge page.
  This follows the same sort of behavior that get_user_pages() uses for huge
  pages: the head page is refcounted once for each tail or head page in the huge
  page, when get_user_pages() is applied to a huge page.

* nr_foll_pin_released: The number of logical pins that have been released since
  the system was powered on. Note that pages are released (unpinned) on a
  PAGE_SIZE granularity, even if the original pin was applied to a huge page.
  Becaused of the pin count behavior described above in "nr_foll_pin_acquired",
  the accounting balances out, so that after doing this::

    pin_user_pages(huge_page);
    for (each page in huge_page)
        unpin_user_page(page);

...the following is expected::

    nr_foll_pin_released == nr_foll_pin_acquired

(...unless it was already out of balance due to a long-term RDMA pin being in
place.)

Other diagnostics
=================

dump_page() has been enhanced slightly, to handle these new counting
fields, and to better report on compound pages in general. Specifically,
for compound pages, the exact (compound_pincount) pincount is reported.

References
==========

* `Some slow progress on get_user_pages() (Apr 2, 2019) <https://lwn.net/Articles/784574/>`_
* `DMA and get_user_pages() (LPC: Dec 12, 2018) <https://lwn.net/Articles/774411/>`_
* `The trouble with get_user_pages() (Apr 30, 2018) <https://lwn.net/Articles/753027/>`_
* `LWN kernel index: get_user_pages() <https://lwn.net/Kernel/Index/#Memory_management-get_user_pages>`_

John Hubbard, October, 2019


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

===========================
Message logging with printk
===========================

printk() is one of the most widely known functions in the Linux kernel. It's the
standard tool we have for printing messages and usually the most basic way of
tracing and debugging. If you're familiar with printf(3) you can tell printk()
is based on it, although it has some functional differences:

  - printk() messages can specify a log level.

  - the format string, while largely compatible with C99, doesn't follow the
    exact same specification. It has some extensions and a few limitations
    (no ``%n`` or floating point conversion specifiers). See :ref:`How to get
    printk format specifiers right <printk-specifiers>`.

All printk() messages are printed to the kernel log buffer, which is a ring
buffer exported to userspace through /dev/kmsg. The usual way to read it is
using ``dmesg``.

printk() is typically used like this::

  printk(KERN_INFO "Message: %s\n", arg);

where ``KERN_INFO`` is the log level (note that it's concatenated to the format
string, the log level is not a separate argument). The available log levels are:

+----------------+--------+-----------------------------------------------+
| Name           | String |  Alias function                               |
+================+========+===============================================+
| KERN_EMERG     | "0"    | pr_emerg()                                    |
+----------------+--------+-----------------------------------------------+
| KERN_ALERT     | "1"    | pr_alert()                                    |
+----------------+--------+-----------------------------------------------+
| KERN_CRIT      | "2"    | pr_crit()                                     |
+----------------+--------+-----------------------------------------------+
| KERN_ERR       | "3"    | pr_err()                                      |
+----------------+--------+-----------------------------------------------+
| KERN_WARNING   | "4"    | pr_warn()                                     |
+----------------+--------+-----------------------------------------------+
| KERN_NOTICE    | "5"    | pr_notice()                                   |
+----------------+--------+-----------------------------------------------+
| KERN_INFO      | "6"    | pr_info()                                     |
+----------------+--------+-----------------------------------------------+
| KERN_DEBUG     | "7"    | pr_debug() and pr_devel() if DEBUG is defined |
+----------------+--------+-----------------------------------------------+
| KERN_DEFAULT   | ""     |                                               |
+----------------+--------+-----------------------------------------------+
| KERN_CONT      | "c"    | pr_cont()                                     |
+----------------+--------+-----------------------------------------------+

The log level specifies the importance of a message. The kernel decides whether
to show the message immediately (printing it to the current console) depending
on its log level and the current *console_loglevel* (a kernel variable). If the
message priority is higher (lower log level value) than the *console_loglevel*
the message will be printed to the console.

If the log level is omitted, the message is printed with ``KERN_DEFAULT``
level.

You can check the current *console_loglevel* with::

  $ cat /proc/sys/kernel/printk
  4        4        1        7

The result shows the *current*, *default*, *minimum* and *boot-time-default* log
levels.

To change the current console_loglevel simply write the desired level to
``/proc/sys/kernel/printk``. For example, to print all messages to the console::

  # echo 8 > /proc/sys/kernel/printk

Another way, using ``dmesg``::

  # dmesg -n 5

sets the console_loglevel to print KERN_WARNING (4) or more severe messages to
console. See ``dmesg(1)`` for more information.

As an alternative to printk() you can use the ``pr_*()`` aliases for
logging. This family of macros embed the log level in the macro names. For
example::

  pr_info("Info message no. %d\n", msg_num);

prints a ``KERN_INFO`` message.

Besides being more concise than the equivalent printk() calls, they can use a
common definition for the format string through the pr_fmt() macro. For
instance, defining this at the top of a source file (before any ``#include``
directive)::

  #define pr_fmt(fmt) "%s:%s: " fmt, KBUILD_MODNAME, __func__

would prefix every pr_*() message in that file with the module and function name
that originated the message.

For debugging purposes there are also two conditionally-compiled macros:
pr_debug() and pr_devel(), which are compiled-out unless ``DEBUG`` (or
also ``CONFIG_DYNAMIC_DEBUG`` in the case of pr_debug()) is defined.

Function reference
==================

.. kernel-doc:: include/linux/printk.h
   :functions: printk pr_emerg pr_alert pr_crit pr_err pr_warn pr_notice pr_info
      pr_fmt pr_debug pr_devel pr_cont


code:
=========================================
How to get printk format specifiers right
=========================================

.. _printk-specifiers:

:Author: Randy Dunlap <rdunlap@infradead.org>
:Author: Andrew Murray <amurray@mpc-data.co.uk>

Integer types
=============

::

	If variable is of Type,		use printk format specifier:
	------------------------------------------------------------
		char			%d or %x
		unsigned char		%u or %x
		short int		%d or %x
		unsigned short int	%u or %x
		int			%d or %x
		unsigned int		%u or %x
		long			%ld or %lx
		unsigned long		%lu or %lx
		long long		%lld or %llx
		unsigned long long	%llu or %llx
		size_t			%zu or %zx
		ssize_t			%zd or %zx
		s8			%d or %x
		u8			%u or %x
		s16			%d or %x
		u16			%u or %x
		s32			%d or %x
		u32			%u or %x
		s64			%lld or %llx
		u64			%llu or %llx

If <type> is architecture-dependent for its size (e.g., cycles_t, tcflag_t) or
is dependent on a config option for its size (e.g., blk_status_t), use a format
specifier of its largest possible type and explicitly cast to it.

Example::

	printk("test: latency: %llu cycles\n", (unsigned long long)time);

Reminder: sizeof() returns type size_t.

The kernel's printf does not support %n. Floating point formats (%e, %f,
%g, %a) are also not recognized, for obvious reasons. Use of any
unsupported specifier or length qualifier results in a WARN and early
return from vsnprintf().

Pointer types
=============

A raw pointer value may be printed with %p which will hash the address
before printing. The kernel also supports extended specifiers for printing
pointers of different types.

Some of the extended specifiers print the data on the given address instead
of printing the address itself. In this case, the following error messages
might be printed instead of the unreachable information::

	(null)	 data on plain NULL address
	(efault) data on invalid address
	(einval) invalid data on a valid address

Plain Pointers
--------------

::

	%p	abcdef12 or 00000000abcdef12

Pointers printed without a specifier extension (i.e unadorned %p) are
hashed to prevent leaking information about the kernel memory layout. This
has the added benefit of providing a unique identifier. On 64-bit machines
the first 32 bits are zeroed. The kernel will print ``(ptrval)`` until it
gathers enough entropy.

When possible, use specialised modifiers such as %pS or %pB (described below)
to avoid the need of providing an unhashed address that has to be interpreted
post-hoc. If not possible, and the aim of printing the address is to provide
more information for debugging, use %p and boot the kernel with the
``no_hash_pointers`` parameter during debugging, which will print all %p
addresses unmodified. If you *really* always want the unmodified address, see
%px below.

If (and only if) you are printing addresses as a content of a virtual file in
e.g. procfs or sysfs (using e.g. seq_printf(), not printk()) read by a
userspace process, use the %pK modifier described below instead of %p or %px.

Error Pointers
--------------

::

	%pe	-ENOSPC

For printing error pointers (i.e. a pointer for which IS_ERR() is true)
as a symbolic error name. Error values for which no symbolic name is
known are printed in decimal, while a non-ERR_PTR passed as the
argument to %pe gets treated as ordinary %p.

Symbols/Function Pointers
-------------------------

::

	%pS	versatile_init+0x0/0x110
	%ps	versatile_init
	%pSR	versatile_init+0x9/0x110
		(with __builtin_extract_return_addr() translation)
	%pB	prev_fn_of_versatile_init+0x88/0x88

The ``S`` and ``s`` specifiers are used for printing a pointer in symbolic
format. They result in the symbol name with (S) or without (s)
offsets. If KALLSYMS are disabled then the symbol address is printed instead.

The ``B`` specifier results in the symbol name with offsets and should be
used when printing stack backtraces. The specifier takes into
consideration the effect of compiler optimisations which may occur
when tail-calls are used and marked with the noreturn GCC attribute.

If the pointer is within a module, the module name and optionally build ID is
printed after the symbol name with an extra ``b`` appended to the end of the
specifier.

::

	%pS	versatile_init+0x0/0x110 [module_name]
	%pSb	versatile_init+0x0/0x110 [module_name ed5019fdf5e53be37cb1ba7899292d7e143b259e]
	%pSRb	versatile_init+0x9/0x110 [module_name ed5019fdf5e53be37cb1ba7899292d7e143b259e]
		(with __builtin_extract_return_addr() translation)
	%pBb	prev_fn_of_versatile_init+0x88/0x88 [module_name ed5019fdf5e53be37cb1ba7899292d7e143b259e]

Probed Pointers from BPF / tracing
----------------------------------

::

	%pks	kernel string
	%pus	user string

The ``k`` and ``u`` specifiers are used for printing prior probed memory from
either kernel memory (k) or user memory (u). The subsequent ``s`` specifier
results in printing a string. For direct use in regular vsnprintf() the (k)
and (u) annotation is ignored, however, when used out of BPF's bpf_trace_printk(),
for example, it reads the memory it is pointing to without faulting.

Kernel Pointers
---------------

::

	%pK	01234567 or 0123456789abcdef

For printing kernel pointers which should be hidden from unprivileged
users. The behaviour of %pK depends on the kptr_restrict sysctl - see
Documentation/admin-guide/sysctl/kernel.rst for more details.

This modifier is *only* intended when producing content of a file read by
userspace from e.g. procfs or sysfs, not for dmesg. Please refer to the
section about %p above for discussion about how to manage hashing pointers
in printk().

Unmodified Addresses
--------------------

::

	%px	01234567 or 0123456789abcdef

For printing pointers when you *really* want to print the address. Please
consider whether or not you are leaking sensitive information about the
kernel memory layout before printing pointers with %px. %px is functionally
equivalent to %lx (or %lu). %px is preferred because it is more uniquely
grep'able. If in the future we need to modify the way the kernel handles
printing pointers we will be better equipped to find the call sites.

Before using %px, consider if using %p is sufficient together with enabling the
``no_hash_pointers`` kernel parameter during debugging sessions (see the %p
description above). One valid scenario for %px might be printing information
immediately before a panic, which prevents any sensitive information to be
exploited anyway, and with %px there would be no need to reproduce the panic
with no_hash_pointers.

Pointer Differences
-------------------

::

	%td	2560
	%tx	a00

For printing the pointer differences, use the %t modifier for ptrdiff_t.

Example::

	printk("test: difference between pointers: %td\n", ptr2 - ptr1);

Struct Resources
----------------

::

	%pr	[mem 0x60000000-0x6fffffff flags 0x2200] or
		[mem 0x0000000060000000-0x000000006fffffff flags 0x2200]
	%pR	[mem 0x60000000-0x6fffffff pref] or
		[mem 0x0000000060000000-0x000000006fffffff pref]

For printing struct resources. The ``R`` and ``r`` specifiers result in a
printed resource with (R) or without (r) a decoded flags member.

Passed by reference.

Physical address types phys_addr_t
----------------------------------

::

	%pa[p]	0x01234567 or 0x0123456789abcdef

For printing a phys_addr_t type (and its derivatives, such as
resource_size_t) which can vary based on build options, regardless of the
width of the CPU data path.

Passed by reference.

DMA address types dma_addr_t
----------------------------

::

	%pad	0x01234567 or 0x0123456789abcdef

For printing a dma_addr_t type which can vary based on build options,
regardless of the width of the CPU data path.

Passed by reference.

Raw buffer as an escaped string
-------------------------------

::

	%*pE[achnops]

For printing raw buffer as an escaped string. For the following buffer::

		1b 62 20 5c 43 07 22 90 0d 5d

A few examples show how the conversion would be done (excluding surrounding
quotes)::

		%*pE		"\eb \C\a"\220\r]"
		%*pEhp		"\x1bb \C\x07"\x90\x0d]"
		%*pEa		"\e\142\040\\\103\a\042\220\r\135"

The conversion rules are applied according to an optional combination
of flags (see :c:func:`string_escape_mem` kernel documentation for the
details):

	- a - ESCAPE_ANY
	- c - ESCAPE_SPECIAL
	- h - ESCAPE_HEX
	- n - ESCAPE_NULL
	- o - ESCAPE_OCTAL
	- p - ESCAPE_NP
	- s - ESCAPE_SPACE

By default ESCAPE_ANY_NP is used.

ESCAPE_ANY_NP is the sane choice for many cases, in particularly for
printing SSIDs.

If field width is omitted then 1 byte only will be escaped.

Raw buffer as a hex string
--------------------------

::

	%*ph	00 01 02  ...  3f
	%*phC	00:01:02: ... :3f
	%*phD	00-01-02- ... -3f
	%*phN	000102 ... 3f

For printing small buffers (up to 64 bytes long) as a hex string with a
certain separator. For larger buffers consider using
:c:func:`print_hex_dump`.

MAC/FDDI addresses
------------------

::

	%pM	00:01:02:03:04:05
	%pMR	05:04:03:02:01:00
	%pMF	00-01-02-03-04-05
	%pm	000102030405
	%pmR	050403020100

For printing 6-byte MAC/FDDI addresses in hex notation. The ``M`` and ``m``
specifiers result in a printed address with (M) or without (m) byte
separators. The default byte separator is the colon (:).

Where FDDI addresses are concerned the ``F`` specifier can be used after
the ``M`` specifier to use dash (-) separators instead of the default
separator.

For Bluetooth addresses the ``R`` specifier shall be used after the ``M``
specifier to use reversed byte order suitable for visual interpretation
of Bluetooth addresses which are in the little endian order.

Passed by reference.

IPv4 addresses
--------------

::

	%pI4	1.2.3.4
	%pi4	001.002.003.004
	%p[Ii]4[hnbl]

For printing IPv4 dot-separated decimal addresses. The ``I4`` and ``i4``
specifiers result in a printed address with (i4) or without (I4) leading
zeros.

The additional ``h``, ``n``, ``b``, and ``l`` specifiers are used to specify
host, network, big or little endian order addresses respectively. Where
no specifier is provided the default network/big endian order is used.

Passed by reference.

IPv6 addresses
--------------

::

	%pI6	0001:0002:0003:0004:0005:0006:0007:0008
	%pi6	00010002000300040005000600070008
	%pI6c	1:2:3:4:5:6:7:8

For printing IPv6 network-order 16-bit hex addresses. The ``I6`` and ``i6``
specifiers result in a printed address with (I6) or without (i6)
colon-separators. Leading zeros are always used.

The additional ``c`` specifier can be used with the ``I`` specifier to
print a compressed IPv6 address as described by
https://tools.ietf.org/html/rfc5952

Passed by reference.

IPv4/IPv6 addresses (generic, with port, flowinfo, scope)
---------------------------------------------------------

::

	%pIS	1.2.3.4		or 0001:0002:0003:0004:0005:0006:0007:0008
	%piS	001.002.003.004	or 00010002000300040005000600070008
	%pISc	1.2.3.4		or 1:2:3:4:5:6:7:8
	%pISpc	1.2.3.4:12345	or [1:2:3:4:5:6:7:8]:12345
	%p[Ii]S[pfschnbl]

For printing an IP address without the need to distinguish whether it's of
type AF_INET or AF_INET6. A pointer to a valid struct sockaddr,
specified through ``IS`` or ``iS``, can be passed to this format specifier.

The additional ``p``, ``f``, and ``s`` specifiers are used to specify port
(IPv4, IPv6), flowinfo (IPv6) and scope (IPv6). Ports have a ``:`` prefix,
flowinfo a ``/`` and scope a ``%``, each followed by the actual value.

In case of an IPv6 address the compressed IPv6 address as described by
https://tools.ietf.org/html/rfc5952 is being used if the additional
specifier ``c`` is given. The IPv6 address is surrounded by ``[``, ``]`` in
case of additional specifiers ``p``, ``f`` or ``s`` as suggested by
https://tools.ietf.org/html/draft-ietf-6man-text-addr-representation-07

In case of IPv4 addresses, the additional ``h``, ``n``, ``b``, and ``l``
specifiers can be used as well and are ignored in case of an IPv6
address.

Passed by reference.

Further examples::

	%pISfc		1.2.3.4		or [1:2:3:4:5:6:7:8]/123456789
	%pISsc		1.2.3.4		or [1:2:3:4:5:6:7:8]%1234567890
	%pISpfc		1.2.3.4:12345	or [1:2:3:4:5:6:7:8]:12345/123456789

UUID/GUID addresses
-------------------

::

	%pUb	00010203-0405-0607-0809-0a0b0c0d0e0f
	%pUB	00010203-0405-0607-0809-0A0B0C0D0E0F
	%pUl	03020100-0504-0706-0809-0a0b0c0e0e0f
	%pUL	03020100-0504-0706-0809-0A0B0C0E0E0F

For printing 16-byte UUID/GUIDs addresses. The additional ``l``, ``L``,
``b`` and ``B`` specifiers are used to specify a little endian order in
lower (l) or upper case (L) hex notation - and big endian order in lower (b)
or upper case (B) hex notation.

Where no additional specifiers are used the default big endian
order with lower case hex notation will be printed.

Passed by reference.

dentry names
------------

::

	%pd{,2,3,4}
	%pD{,2,3,4}

For printing dentry name; if we race with :c:func:`d_move`, the name might
be a mix of old and new ones, but it won't oops.  %pd dentry is a safer
equivalent of %s dentry->d_name.name we used to use, %pd<n> prints ``n``
last components.  %pD does the same thing for struct file.

Passed by reference.

block_device names
------------------

::

	%pg	sda, sda1 or loop0p1

For printing name of block_device pointers.

struct va_format
----------------

::

	%pV

For printing struct va_format structures. These contain a format string
and va_list as follows::

	struct va_format {
		const char *fmt;
		va_list *va;
	};

Implements a "recursive vsnprintf".

Do not use this feature without some mechanism to verify the
correctness of the format string and va_list arguments.

Passed by reference.

Device tree nodes
-----------------

::

	%pOF[fnpPcCF]

For printing device tree node structures. Default behaviour is
equivalent to %pOFf.

	- f - device node full_name
	- n - device node name
	- p - device node phandle
	- P - device node path spec (name + @unit)
	- F - device node flags
	- c - major compatible string
	- C - full compatible string

The separator when using multiple arguments is ':'

Examples::

	%pOF	/foo/bar@0			- Node full name
	%pOFf	/foo/bar@0			- Same as above
	%pOFfp	/foo/bar@0:10			- Node full name + phandle
	%pOFfcF	/foo/bar@0:foo,device:--P-	- Node full name +
	                                          major compatible string +
						  node flags
							D - dynamic
							d - detached
							P - Populated
							B - Populated bus

Passed by reference.

Fwnode handles
--------------

::

	%pfw[fP]

For printing information on fwnode handles. The default is to print the full
node name, including the path. The modifiers are functionally equivalent to
%pOF above.

	- f - full name of the node, including the path
	- P - the name of the node including an address (if there is one)

Examples (ACPI)::

	%pfwf	\_SB.PCI0.CIO2.port@1.endpoint@0	- Full node name
	%pfwP	endpoint@0				- Node name

Examples (OF)::

	%pfwf	/ocp@68000000/i2c@48072000/camera@10/port/endpoint - Full name
	%pfwP	endpoint				- Node name

Time and date
-------------

::

	%pt[RT]			YYYY-mm-ddTHH:MM:SS
	%pt[RT]s		YYYY-mm-dd HH:MM:SS
	%pt[RT]d		YYYY-mm-dd
	%pt[RT]t		HH:MM:SS
	%pt[RT][dt][r][s]

For printing date and time as represented by::

	R  struct rtc_time structure
	T  time64_t type

in human readable format.

By default year will be incremented by 1900 and month by 1.
Use %pt[RT]r (raw) to suppress this behaviour.

The %pt[RT]s (space) will override ISO 8601 separator by using ' ' (space)
instead of 'T' (Capital T) between date and time. It won't have any effect
when date or time is omitted.

Passed by reference.

struct clk
----------

::

	%pC	pll1
	%pCn	pll1

For printing struct clk structures. %pC and %pCn print the name of the clock
(Common Clock Framework) or a unique 32-bit ID (legacy clock framework).

Passed by reference.

bitmap and its derivatives such as cpumask and nodemask
-------------------------------------------------------

::

	%*pb	0779
	%*pbl	0,3-6,8-10

For printing bitmap and its derivatives such as cpumask and nodemask,
%*pb outputs the bitmap with field width as the number of bits and %*pbl
output the bitmap as range list with field width as the number of bits.

The field width is passed by value, the bitmap is passed by reference.
Helper macros cpumask_pr_args() and nodemask_pr_args() are available to ease
printing cpumask and nodemask.

Flags bitfields such as page flags, gfp_flags
---------------------------------------------

::

	%pGp	0x17ffffc0002036(referenced|uptodate|lru|active|private|node=0|zone=2|lastcpupid=0x1fffff)
	%pGg	GFP_USER|GFP_DMA32|GFP_NOWARN
	%pGv	read|exec|mayread|maywrite|mayexec|denywrite

For printing flags bitfields as a collection of symbolic constants that
would construct the value. The type of flags is given by the third
character. Currently supported are [p]age flags, [v]ma_flags (both
expect ``unsigned long *``) and [g]fp_flags (expects ``gfp_t *``). The flag
names and print order depends on the particular	type.

Note that this format should not be used directly in the
:c:func:`TP_printk()` part of a tracepoint. Instead, use the show_*_flags()
functions from <trace/events/mmflags.h>.

Passed by reference.

Network device features
-----------------------

::

	%pNF	0x000000000000c000

For printing netdev_features_t.

Passed by reference.

V4L2 and DRM FourCC code (pixel format)
---------------------------------------

::

	%p4cc

Print a FourCC code used by V4L2 or DRM, including format endianness and
its numerical value as hexadecimal.

Passed by reference.

Examples::

	%p4cc	BG12 little-endian (0x32314742)
	%p4cc	Y10  little-endian (0x20303159)
	%p4cc	NV12 big-endian (0xb231564e)

Rust
----

::

	%pA

Only intended to be used from Rust code to format ``core::fmt::Arguments``.
Do *not* use it from C.

Thanks
======

If you add other %p extensions, please extend <lib/test_printf.c> with
one or more test cases, if at all feasible.

Thank you for your cooperation and attention.


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

============
Printk Index
============

There are many ways how to monitor the state of the system. One important
source of information is the system log. It provides a lot of information,
including more or less important warnings and error messages.

There are monitoring tools that filter and take action based on messages
logged.

The kernel messages are evolving together with the code. As a result,
particular kernel messages are not KABI and never will be!

It is a huge challenge for maintaining the system log monitors. It requires
knowing what messages were updated in a particular kernel version and why.
Finding these changes in the sources would require non-trivial parsers.
Also it would require matching the sources with the binary kernel which
is not always trivial. Various changes might be backported. Various kernel
versions might be used on different monitored systems.

This is where the printk index feature might become useful. It provides
a dump of printk formats used all over the source code used for the kernel
and modules on the running system. It is accessible at runtime via debugfs.

The printk index helps to find changes in the message formats. Also it helps
to track the strings back to the kernel sources and the related commit.

User Interface
==============

The index of printk formats are split in into separate files. The files are
named according to the binaries where the printk formats are built-in. There
is always "vmlinux" and optionally also modules, for example::

   /sys/kernel/debug/printk/index/vmlinux
   /sys/kernel/debug/printk/index/ext4
   /sys/kernel/debug/printk/index/scsi_mod

Note that only loaded modules are shown. Also printk formats from a module
might appear in "vmlinux" when the module is built-in.

The content is inspired by the dynamic debug interface and looks like::

   $> head -1 /sys/kernel/debug/printk/index/vmlinux; shuf -n 5 vmlinux
   # <level[,flags]> filename:line function "format"
   <5> block/blk-settings.c:661 disk_stack_limits "%s: Warning: Device %s is misaligned\n"
   <4> kernel/trace/trace.c:8296 trace_create_file "Could not create tracefs '%s' entry\n"
   <6> arch/x86/kernel/hpet.c:144 _hpet_print_config "hpet: %s(%d):\n"
   <6> init/do_mounts.c:605 prepare_namespace "Waiting for root device %s...\n"
   <6> drivers/acpi/osl.c:1410 acpi_no_auto_serialize_setup "ACPI: auto-serialization disabled\n"

, where the meaning is:

   - :level: log level value: 0-7 for particular severity, -1 as default,
	'c' as continuous line without an explicit log level
   - :flags: optional flags: currently only 'c' for KERN_CONT
   - :filename\:line: source filename and line number of the related
	printk() call. Note that there are many wrappers, for example,
	pr_warn(), pr_warn_once(), dev_warn().
   - :function: function name where the printk() call is used.
   - :format: format string

The extra information makes it a bit harder to find differences
between various kernels. Especially the line number might change
very often. On the other hand, it helps a lot to confirm that
it is the same string or find the commit that is responsible
for eventual changes.

printk() Is Not a Stable KABI
=============================

Several developers are afraid that exporting all these implementation
details into the user space will transform particular printk() calls
into KABI.

But it is exactly the opposite. printk() calls must _not_ be KABI.
And the printk index helps user space tools to deal with this.

Subsystem specific printk wrappers
==================================

The printk index is generated using extra metadata that are stored in
a dedicated .elf section ".printk_index". It is achieved using macro
wrappers doing __printk_index_emit() together with the real printk()
call. The same technique is used also for the metadata used by
the dynamic debug feature.

The metadata are stored for a particular message only when it is printed
using these special wrappers. It is implemented for the commonly
used printk() calls, including, for example, pr_warn(), or pr_once().

Additional changes are necessary for various subsystem specific wrappers
that call the original printk() via a common helper function. These needs
their own wrappers adding __printk_index_emit().

Only few subsystem specific wrappers have been updated so far,
for example, dev_printk(). As a result, the printk formats from
some subsystes can be missing in the printk index.

Subsystem specific prefix
=========================

The macro pr_fmt() macro allows to define a prefix that is printed
before the string generated by the related printk() calls.

Subsystem specific wrappers usually add even more complicated
prefixes.

These prefixes can be stored into the printk index metadata
by an optional parameter of __printk_index_emit(). The debugfs
interface might then show the printk formats including these prefixes.
For example, drivers/acpi/osl.c contains::

  #define pr_fmt(fmt) "ACPI: OSL: " fmt

  static int __init acpi_no_auto_serialize_setup(char *str)
  {
	acpi_gbl_auto_serialize_methods = FALSE;
	pr_info("Auto-serialization disabled\n");

	return 1;
  }

This results in the following printk index entry::

  <6> drivers/acpi/osl.c:1410 acpi_no_auto_serialize_setup "ACPI: auto-serialization disabled\n"

It helps matching messages from the real log with printk index.
Then the source file name, line number, and function name can
be used to match the string with the source code.


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

======================
Memory Protection Keys
======================

Memory Protection Keys provide a mechanism for enforcing page-based
protections, but without requiring modification of the page tables when an
application changes protection domains.

Pkeys Userspace (PKU) is a feature which can be found on:
        * Intel server CPUs, Skylake and later
        * Intel client CPUs, Tiger Lake (11th Gen Core) and later
        * Future AMD CPUs

Pkeys work by dedicating 4 previously Reserved bits in each page table entry to
a "protection key", giving 16 possible keys.

Protections for each key are defined with a per-CPU user-accessible register
(PKRU).  Each of these is a 32-bit register storing two bits (Access Disable
and Write Disable) for each of 16 keys.

Being a CPU register, PKRU is inherently thread-local, potentially giving each
thread a different set of protections from every other thread.

There are two instructions (RDPKRU/WRPKRU) for reading and writing to the
register.  The feature is only available in 64-bit mode, even though there is
theoretically space in the PAE PTEs.  These permissions are enforced on data
access only and have no effect on instruction fetches.

Syscalls
========

There are 3 system calls which directly interact with pkeys::

	int pkey_alloc(unsigned long flags, unsigned long init_access_rights)
	int pkey_free(int pkey);
	int pkey_mprotect(unsigned long start, size_t len,
			  unsigned long prot, int pkey);

Before a pkey can be used, it must first be allocated with
pkey_alloc().  An application calls the WRPKRU instruction
directly in order to change access permissions to memory covered
with a key.  In this example WRPKRU is wrapped by a C function
called pkey_set().
::

	int real_prot = PROT_READ|PROT_WRITE;
	pkey = pkey_alloc(0, PKEY_DISABLE_WRITE);
	ptr = mmap(NULL, PAGE_SIZE, PROT_NONE, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);
	ret = pkey_mprotect(ptr, PAGE_SIZE, real_prot, pkey);
	... application runs here

Now, if the application needs to update the data at 'ptr', it can
gain access, do the update, then remove its write access::

	pkey_set(pkey, 0); // clear PKEY_DISABLE_WRITE
	*ptr = foo; // assign something
	pkey_set(pkey, PKEY_DISABLE_WRITE); // set PKEY_DISABLE_WRITE again

Now when it frees the memory, it will also free the pkey since it
is no longer in use::

	munmap(ptr, PAGE_SIZE);
	pkey_free(pkey);

.. note:: pkey_set() is a wrapper for the RDPKRU and WRPKRU instructions.
          An example implementation can be found in
          tools/testing/selftests/x86/protection_keys.c.

Behavior
========

The kernel attempts to make protection keys consistent with the
behavior of a plain mprotect().  For instance if you do this::

	mprotect(ptr, size, PROT_NONE);
	something(ptr);

you can expect the same effects with protection keys when doing this::

	pkey = pkey_alloc(0, PKEY_DISABLE_WRITE | PKEY_DISABLE_READ);
	pkey_mprotect(ptr, size, PROT_READ|PROT_WRITE, pkey);
	something(ptr);

That should be true whether something() is a direct access to 'ptr'
like::

	*ptr = foo;

or when the kernel does the access on the application's behalf like
with a read()::

	read(fd, ptr, 1);

The kernel will send a SIGSEGV in both cases, but si_code will be set
to SEGV_PKERR when violating protection keys versus SEGV_ACCERR when
the plain mprotect() permissions are violated.


code:
=================================
Red-black Trees (rbtree) in Linux
=================================

:Date: January 18, 2007
:Author: Rob Landley <rob@landley.net>

What are red-black trees, and what are they for?
------------------------------------------------

Red-black trees are a type of self-balancing binary search tree, used for
storing sortable key/value data pairs.  This differs from radix trees (which
are used to efficiently store sparse arrays and thus use long integer indexes
to insert/access/delete nodes) and hash tables (which are not kept sorted to
be easily traversed in order, and must be tuned for a specific size and
hash function where rbtrees scale gracefully storing arbitrary keys).

Red-black trees are similar to AVL trees, but provide faster real-time bounded
worst case performance for insertion and deletion (at most two rotations and
three rotations, respectively, to balance the tree), with slightly slower
(but still O(log n)) lookup time.

To quote Linux Weekly News:

    There are a number of red-black trees in use in the kernel.
    The deadline and CFQ I/O schedulers employ rbtrees to
    track requests; the packet CD/DVD driver does the same.
    The high-resolution timer code uses an rbtree to organize outstanding
    timer requests.  The ext3 filesystem tracks directory entries in a
    red-black tree.  Virtual memory areas (VMAs) are tracked with red-black
    trees, as are epoll file descriptors, cryptographic keys, and network
    packets in the "hierarchical token bucket" scheduler.

This document covers use of the Linux rbtree implementation.  For more
information on the nature and implementation of Red Black Trees,  see:

  Linux Weekly News article on red-black trees
    https://lwn.net/Articles/184495/

  Wikipedia entry on red-black trees
    https://en.wikipedia.org/wiki/Red-black_tree

Linux implementation of red-black trees
---------------------------------------

Linux's rbtree implementation lives in the file "lib/rbtree.c".  To use it,
"#include <linux/rbtree.h>".

The Linux rbtree implementation is optimized for speed, and thus has one
less layer of indirection (and better cache locality) than more traditional
tree implementations.  Instead of using pointers to separate rb_node and data
structures, each instance of struct rb_node is embedded in the data structure
it organizes.  And instead of using a comparison callback function pointer,
users are expected to write their own tree search and insert functions
which call the provided rbtree functions.  Locking is also left up to the
user of the rbtree code.

Creating a new rbtree
---------------------

Data nodes in an rbtree tree are structures containing a struct rb_node member::

  struct mytype {
  	struct rb_node node;
  	char *keystring;
  };

When dealing with a pointer to the embedded struct rb_node, the containing data
structure may be accessed with the standard container_of() macro.  In addition,
individual members may be accessed directly via rb_entry(node, type, member).

At the root of each rbtree is an rb_root structure, which is initialized to be
empty via:

  struct rb_root mytree = RB_ROOT;

Searching for a value in an rbtree
----------------------------------

Writing a search function for your tree is fairly straightforward: start at the
root, compare each value, and follow the left or right branch as necessary.

Example::

  struct mytype *my_search(struct rb_root *root, char *string)
  {
  	struct rb_node *node = root->rb_node;

  	while (node) {
  		struct mytype *data = container_of(node, struct mytype, node);
		int result;

		result = strcmp(string, data->keystring);

		if (result < 0)
  			node = node->rb_left;
		else if (result > 0)
  			node = node->rb_right;
		else
  			return data;
	}
	return NULL;
  }

Inserting data into an rbtree
-----------------------------

Inserting data in the tree involves first searching for the place to insert the
new node, then inserting the node and rebalancing ("recoloring") the tree.

The search for insertion differs from the previous search by finding the
location of the pointer on which to graft the new node.  The new node also
needs a link to its parent node for rebalancing purposes.

Example::

  int my_insert(struct rb_root *root, struct mytype *data)
  {
  	struct rb_node **new = &(root->rb_node), *parent = NULL;

  	/* Figure out where to put new node */
  	while (*new) {
  		struct mytype *this = container_of(*new, struct mytype, node);
  		int result = strcmp(data->keystring, this->keystring);

		parent = *new;
  		if (result < 0)
  			new = &((*new)->rb_left);
  		else if (result > 0)
  			new = &((*new)->rb_right);
  		else
  			return FALSE;
  	}

  	/* Add new node and rebalance tree. */
  	rb_link_node(&data->node, parent, new);
  	rb_insert_color(&data->node, root);

	return TRUE;
  }

Removing or replacing existing data in an rbtree
------------------------------------------------

To remove an existing node from a tree, call::

  void rb_erase(struct rb_node *victim, struct rb_root *tree);

Example::

  struct mytype *data = mysearch(&mytree, "walrus");

  if (data) {
  	rb_erase(&data->node, &mytree);
  	myfree(data);
  }

To replace an existing node in a tree with a new one with the same key, call::

  void rb_replace_node(struct rb_node *old, struct rb_node *new,
  			struct rb_root *tree);

Replacing a node this way does not re-sort the tree: If the new node doesn't
have the same key as the old node, the rbtree will probably become corrupted.

Iterating through the elements stored in an rbtree (in sort order)
------------------------------------------------------------------

Four functions are provided for iterating through an rbtree's contents in
sorted order.  These work on arbitrary trees, and should not need to be
modified or wrapped (except for locking purposes)::

  struct rb_node *rb_first(struct rb_root *tree);
  struct rb_node *rb_last(struct rb_root *tree);
  struct rb_node *rb_next(struct rb_node *node);
  struct rb_node *rb_prev(struct rb_node *node);

To start iterating, call rb_first() or rb_last() with a pointer to the root
of the tree, which will return a pointer to the node structure contained in
the first or last element in the tree.  To continue, fetch the next or previous
node by calling rb_next() or rb_prev() on the current node.  This will return
NULL when there are no more nodes left.

The iterator functions return a pointer to the embedded struct rb_node, from
which the containing data structure may be accessed with the container_of()
macro, and individual members may be accessed directly via
rb_entry(node, type, member).

Example::

  struct rb_node *node;
  for (node = rb_first(&mytree); node; node = rb_next(node))
	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

Cached rbtrees
--------------

Computing the leftmost (smallest) node is quite a common task for binary
search trees, such as for traversals or users relying on a the particular
order for their own logic. To this end, users can use 'struct rb_root_cached'
to optimize O(logN) rb_first() calls to a simple pointer fetch avoiding
potentially expensive tree iterations. This is done at negligible runtime
overhead for maintenance; albeit larger memory footprint.

Similar to the rb_root structure, cached rbtrees are initialized to be
empty via::

  struct rb_root_cached mytree = RB_ROOT_CACHED;

Cached rbtree is simply a regular rb_root with an extra pointer to cache the
leftmost node. This allows rb_root_cached to exist wherever rb_root does,
which permits augmented trees to be supported as well as only a few extra
interfaces::

  struct rb_node *rb_first_cached(struct rb_root_cached *tree);
  void rb_insert_color_cached(struct rb_node *, struct rb_root_cached *, bool);
  void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);

Both insert and erase calls have their respective counterpart of augmented
trees::

  void rb_insert_augmented_cached(struct rb_node *node, struct rb_root_cached *,
				  bool, struct rb_augment_callbacks *);
  void rb_erase_augmented_cached(struct rb_node *, struct rb_root_cached *,
				 struct rb_augment_callbacks *);

Support for Augmented rbtrees
-----------------------------

Augmented rbtree is an rbtree with "some" additional data stored in
each node, where the additional data for node N must be a function of
the contents of all nodes in the subtree rooted at N. This data can
be used to augment some new functionality to rbtree. Augmented rbtree
is an optional feature built on top of basic rbtree infrastructure.
An rbtree user who wants this feature will have to call the augmentation
functions with the user provided augmentation callback when inserting
and erasing nodes.

C files implementing augmented rbtree manipulation must include
<linux/rbtree_augmented.h> instead of <linux/rbtree.h>. Note that
linux/rbtree_augmented.h exposes some rbtree implementations details
you are not expected to rely on; please stick to the documented APIs
there and do not include <linux/rbtree_augmented.h> from header files
either so as to minimize chances of your users accidentally relying on
such implementation details.

On insertion, the user must update the augmented information on the path
leading to the inserted node, then call rb_link_node() as usual and
rb_augment_inserted() instead of the usual rb_insert_color() call.
If rb_augment_inserted() rebalances the rbtree, it will callback into
a user provided function to update the augmented information on the
affected subtrees.

When erasing a node, the user must call rb_erase_augmented() instead of
rb_erase(). rb_erase_augmented() calls back into user provided functions
to updated the augmented information on affected subtrees.

In both cases, the callbacks are provided through struct rb_augment_callbacks.
3 callbacks must be defined:

- A propagation callback, which updates the augmented value for a given
  node and its ancestors, up to a given stop point (or NULL to update
  all the way to the root).

- A copy callback, which copies the augmented value for a given subtree
  to a newly assigned subtree root.

- A tree rotation callback, which copies the augmented value for a given
  subtree to a newly assigned subtree root AND recomputes the augmented
  information for the former subtree root.

The compiled code for rb_erase_augmented() may inline the propagation and
copy callbacks, which results in a large function, so each augmented rbtree
user should have a single rb_erase_augmented() call site in order to limit
compiled code size.

Sample usage
^^^^^^^^^^^^

Interval tree is an example of augmented rb tree. Reference -
"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein.
More details about interval trees:

Classical rbtree has a single key and it cannot be directly used to store
interval ranges like [lo:hi] and do a quick lookup for any overlap with a new
lo:hi or to find whether there is an exact match for a new lo:hi.

However, rbtree can be augmented to store such interval ranges in a structured
way making it possible to do efficient lookup and exact match.

This "extra information" stored in each node is the maximum hi
(max_hi) value among all the nodes that are its descendants. This
information can be maintained at each node just be looking at the node
and its immediate children. And this will be used in O(log n) lookup
for lowest match (lowest start address among all possible matches)
with something like::

  struct interval_tree_node *
  interval_tree_first_match(struct rb_root *root,
			    unsigned long start, unsigned long last)
  {
	struct interval_tree_node *node;

	if (!root->rb_node)
		return NULL;
	node = rb_entry(root->rb_node, struct interval_tree_node, rb);

	while (true) {
		if (node->rb.rb_left) {
			struct interval_tree_node *left =
				rb_entry(node->rb.rb_left,
					 struct interval_tree_node, rb);
			if (left->__subtree_last >= start) {
				/*
				 * Some nodes in left subtree satisfy Cond2.
				 * Iterate to find the leftmost such node N.
				 * If it also satisfies Cond1, that's the match
				 * we are looking for. Otherwise, there is no
				 * matching interval as nodes to the right of N
				 * can't satisfy Cond1 either.
				 */
				node = left;
				continue;
			}
		}
		if (node->start <= last) {		/* Cond1 */
			if (node->last >= start)	/* Cond2 */
				return node;	/* node is leftmost match */
			if (node->rb.rb_right) {
				node = rb_entry(node->rb.rb_right,
					struct interval_tree_node, rb);
				if (node->__subtree_last >= start)
					continue;
			}
		}
		return NULL;	/* No match */
	}
  }

Insertion/removal are defined using the following augmented callbacks::

  static inline unsigned long
  compute_subtree_last(struct interval_tree_node *node)
  {
	unsigned long max = node->last, subtree_last;
	if (node->rb.rb_left) {
		subtree_last = rb_entry(node->rb.rb_left,
			struct interval_tree_node, rb)->__subtree_last;
		if (max < subtree_last)
			max = subtree_last;
	}
	if (node->rb.rb_right) {
		subtree_last = rb_entry(node->rb.rb_right,
			struct interval_tree_node, rb)->__subtree_last;
		if (max < subtree_last)
			max = subtree_last;
	}
	return max;
  }

  static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
  {
	while (rb != stop) {
		struct interval_tree_node *node =
			rb_entry(rb, struct interval_tree_node, rb);
		unsigned long subtree_last = compute_subtree_last(node);
		if (node->__subtree_last == subtree_last)
			break;
		node->__subtree_last = subtree_last;
		rb = rb_parent(&node->rb);
	}
  }

  static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
  {
	struct interval_tree_node *old =
		rb_entry(rb_old, struct interval_tree_node, rb);
	struct interval_tree_node *new =
		rb_entry(rb_new, struct interval_tree_node, rb);

	new->__subtree_last = old->__subtree_last;
  }

  static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
  {
	struct interval_tree_node *old =
		rb_entry(rb_old, struct interval_tree_node, rb);
	struct interval_tree_node *new =
		rb_entry(rb_new, struct interval_tree_node, rb);

	new->__subtree_last = old->__subtree_last;
	old->__subtree_last = compute_subtree_last(old);
  }

  static const struct rb_augment_callbacks augment_callbacks = {
	augment_propagate, augment_copy, augment_rotate
  };

  void interval_tree_insert(struct interval_tree_node *node,
			    struct rb_root *root)
  {
	struct rb_node **link = &root->rb_node, *rb_parent = NULL;
	unsigned long start = node->start, last = node->last;
	struct interval_tree_node *parent;

	while (*link) {
		rb_parent = *link;
		parent = rb_entry(rb_parent, struct interval_tree_node, rb);
		if (parent->__subtree_last < last)
			parent->__subtree_last = last;
		if (start < parent->start)
			link = &parent->rb.rb_left;
		else
			link = &parent->rb.rb_right;
	}

	node->__subtree_last = last;
	rb_link_node(&node->rb, rb_parent, link);
	rb_insert_augmented(&node->rb, root, &augment_callbacks);
  }

  void interval_tree_remove(struct interval_tree_node *node,
			    struct rb_root *root)
  {
	rb_erase_augmented(&node->rb, root, &augment_callbacks);
  }


code:
===================================
refcount_t API compared to atomic_t
===================================

.. contents:: :local:

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

The goal of refcount_t API is to provide a minimal API for implementing
an object's reference counters. While a generic architecture-independent
implementation from lib/refcount.c uses atomic operations underneath,
there are a number of differences between some of the ``refcount_*()`` and
``atomic_*()`` functions with regards to the memory ordering guarantees.
This document outlines the differences and provides respective examples
in order to help maintainers validate their code against the change in
these memory ordering guarantees.

The terms used through this document try to follow the formal LKMM defined in
tools/memory-model/Documentation/explanation.txt.

memory-barriers.txt and atomic_t.txt provide more background to the
memory ordering in general and for atomic operations specifically.

Relevant types of memory ordering
=================================

.. note:: The following section only covers some of the memory
   ordering types that are relevant for the atomics and reference
   counters and used through this document. For a much broader picture
   please consult memory-barriers.txt document.

In the absence of any memory ordering guarantees (i.e. fully unordered)
atomics & refcounters only provide atomicity and
program order (po) relation (on the same CPU). It guarantees that
each ``atomic_*()`` and ``refcount_*()`` operation is atomic and instructions
are executed in program order on a single CPU.
This is implemented using READ_ONCE()/WRITE_ONCE() and
compare-and-swap primitives.

A strong (full) memory ordering guarantees that all prior loads and
stores (all po-earlier instructions) on the same CPU are completed
before any po-later instruction is executed on the same CPU.
It also guarantees that all po-earlier stores on the same CPU
and all propagated stores from other CPUs must propagate to all
other CPUs before any po-later instruction is executed on the original
CPU (A-cumulative property). This is implemented using smp_mb().

A RELEASE memory ordering guarantees that all prior loads and
stores (all po-earlier instructions) on the same CPU are completed
before the operation. It also guarantees that all po-earlier
stores on the same CPU and all propagated stores from other CPUs
must propagate to all other CPUs before the release operation
(A-cumulative property). This is implemented using
smp_store_release().

An ACQUIRE memory ordering guarantees that all post loads and
stores (all po-later instructions) on the same CPU are
completed after the acquire operation. It also guarantees that all
po-later stores on the same CPU must propagate to all other CPUs
after the acquire operation executes. This is implemented using
smp_acquire__after_ctrl_dep().

A control dependency (on success) for refcounters guarantees that
if a reference for an object was successfully obtained (reference
counter increment or addition happened, function returned true),
then further stores are ordered against this operation.
Control dependency on stores are not implemented using any explicit
barriers, but rely on CPU not to speculate on stores. This is only
a single CPU relation and provides no guarantees for other CPUs.

Comparison of functions
=======================

case 1) - non-"Read/Modify/Write" (RMW) ops
-------------------------------------------

Function changes:

 * atomic_set() --> refcount_set()
 * atomic_read() --> refcount_read()

Memory ordering guarantee changes:

 * none (both fully unordered)

case 2) - increment-based ops that return no value
--------------------------------------------------

Function changes:

 * atomic_inc() --> refcount_inc()
 * atomic_add() --> refcount_add()

Memory ordering guarantee changes:

 * none (both fully unordered)

case 3) - decrement-based RMW ops that return no value
------------------------------------------------------

Function changes:

 * atomic_dec() --> refcount_dec()

Memory ordering guarantee changes:

 * fully unordered --> RELEASE ordering

case 4) - increment-based RMW ops that return a value
-----------------------------------------------------

Function changes:

 * atomic_inc_not_zero() --> refcount_inc_not_zero()
 * no atomic counterpart --> refcount_add_not_zero()

Memory ordering guarantees changes:

 * fully ordered --> control dependency on success for stores

.. note:: We really assume here that necessary ordering is provided as a
   result of obtaining pointer to the object!

case 5) - generic dec/sub decrement-based RMW ops that return a value
---------------------------------------------------------------------

Function changes:

 * atomic_dec_and_test() --> refcount_dec_and_test()
 * atomic_sub_and_test() --> refcount_sub_and_test()

Memory ordering guarantees changes:

 * fully ordered --> RELEASE ordering + ACQUIRE ordering on success

case 6) other decrement-based RMW ops that return a value
---------------------------------------------------------

Function changes:

 * no atomic counterpart --> refcount_dec_if_one()
 * ``atomic_add_unless(&var, -1, 1)`` --> ``refcount_dec_not_one(&var)``

Memory ordering guarantees changes:

 * fully ordered --> RELEASE ordering + control dependency

.. note:: atomic_add_unless() only provides full order on success.

case 7) - lock-based RMW
------------------------

Function changes:

 * atomic_dec_and_lock() --> refcount_dec_and_lock()
 * atomic_dec_and_mutex_lock() --> refcount_dec_and_mutex_lock()

Memory ordering guarantees changes:

 * fully ordered --> RELEASE ordering + control dependency + hold
   spin_lock() on success