code:
===================================================
Scalable Vector Extension support for AArch64 Linux
===================================================

Author: Dave Martin <Dave.Martin@arm.com>

Date:   4 August 2017

This document outlines briefly the interface provided to userspace by Linux in
order to support use of the ARM Scalable Vector Extension (SVE), including
interactions with Streaming SVE mode added by the Scalable Matrix Extension
(SME).

This is an outline of the most important features and issues only and not
intended to be exhaustive.

This document does not aim to describe the SVE architecture or programmer's
model.  To aid understanding, a minimal description of relevant programmer's
model features for SVE is included in Appendix A.

1.  General
-----------

* SVE registers Z0..Z31, P0..P15 and FFR and the current vector length VL, are
  tracked per-thread.

* In streaming mode FFR is not accessible unless HWCAP2_SME_FA64 is present
  in the system, when it is not supported and these interfaces are used to
  access streaming mode FFR is read and written as zero.

* The presence of SVE is reported to userspace via HWCAP_SVE in the aux vector
  AT_HWCAP entry.  Presence of this flag implies the presence of the SVE
  instructions and registers, and the Linux-specific system interfaces
  described in this document.  SVE is reported in /proc/cpuinfo as "sve".

* Support for the execution of SVE instructions in userspace can also be
  detected by reading the CPU ID register ID_AA64PFR0_EL1 using an MRS
  instruction, and checking that the value of the SVE field is nonzero. [3]

  It does not guarantee the presence of the system interfaces described in the
  following sections: software that needs to verify that those interfaces are
  present must check for HWCAP_SVE instead.

* On hardware that supports the SVE2 extensions, HWCAP2_SVE2 will also
  be reported in the AT_HWCAP2 aux vector entry.  In addition to this,
  optional extensions to SVE2 may be reported by the presence of:

	HWCAP2_SVE2
	HWCAP2_SVEAES
	HWCAP2_SVEPMULL
	HWCAP2_SVEBITPERM
	HWCAP2_SVESHA3
	HWCAP2_SVESM4
	HWCAP2_SVE2P1

  This list may be extended over time as the SVE architecture evolves.

  These extensions are also reported via the CPU ID register ID_AA64ZFR0_EL1,
  which userspace can read using an MRS instruction.  See elf_hwcaps.txt and
  cpu-feature-registers.txt for details.

* On hardware that supports the SME extensions, HWCAP2_SME will also be
  reported in the AT_HWCAP2 aux vector entry.  Among other things SME adds
  streaming mode which provides a subset of the SVE feature set using a
  separate SME vector length and the same Z/V registers.  See sme.rst
  for more details.

* Debuggers should restrict themselves to interacting with the target via the
  NT_ARM_SVE regset.  The recommended way of detecting support for this regset
  is to connect to a target process first and then attempt a
  ptrace(PTRACE_GETREGSET, pid, NT_ARM_SVE, &iov).  Note that when SME is
  present and streaming SVE mode is in use the FPSIMD subset of registers
  will be read via NT_ARM_SVE and NT_ARM_SVE writes will exit streaming mode
  in the target.

* Whenever SVE scalable register values (Zn, Pn, FFR) are exchanged in memory
  between userspace and the kernel, the register value is encoded in memory in
  an endianness-invariant layout, with bits [(8 * i + 7) : (8 * i)] encoded at
  byte offset i from the start of the memory representation.  This affects for
  example the signal frame (struct sve_context) and ptrace interface
  (struct user_sve_header) and associated data.

  Beware that on big-endian systems this results in a different byte order than
  for the FPSIMD V-registers, which are stored as single host-endian 128-bit
  values, with bits [(127 - 8 * i) : (120 - 8 * i)] of the register encoded at
  byte offset i.  (struct fpsimd_context, struct user_fpsimd_state).

2.  Vector length terminology
-----------------------------

The size of an SVE vector (Z) register is referred to as the "vector length".

To avoid confusion about the units used to express vector length, the kernel
adopts the following conventions:

* Vector length (VL) = size of a Z-register in bytes

* Vector quadwords (VQ) = size of a Z-register in units of 128 bits

(So, VL = 16 * VQ.)

The VQ convention is used where the underlying granularity is important, such
as in data structure definitions.  In most other situations, the VL convention
is used.  This is consistent with the meaning of the "VL" pseudo-register in
the SVE instruction set architecture.

3.  System call behaviour
-------------------------

* On syscall, V0..V31 are preserved (as without SVE).  Thus, bits [127:0] of
  Z0..Z31 are preserved.  All other bits of Z0..Z31, and all of P0..P15 and FFR
  become zero on return from a syscall.

* The SVE registers are not used to pass arguments to or receive results from
  any syscall.

* In practice the affected registers/bits will be preserved or will be replaced
  with zeros on return from a syscall, but userspace should not make
  assumptions about this.  The kernel behaviour may vary on a case-by-case
  basis.

* All other SVE state of a thread, including the currently configured vector
  length, the state of the PR_SVE_VL_INHERIT flag, and the deferred vector
  length (if any), is preserved across all syscalls, subject to the specific
  exceptions for execve() described in section 6.

  In particular, on return from a fork() or clone(), the parent and new child
  process or thread share identical SVE configuration, matching that of the
  parent before the call.

4.  Signal handling
-------------------

* A new signal frame record sve_context encodes the SVE registers on signal
  delivery. [1]

* This record is supplementary to fpsimd_context.  The FPSR and FPCR registers
  are only present in fpsimd_context.  For convenience, the content of V0..V31
  is duplicated between sve_context and fpsimd_context.

* The record contains a flag field which includes a flag SVE_SIG_FLAG_SM which
  if set indicates that the thread is in streaming mode and the vector length
  and register data (if present) describe the streaming SVE data and vector
  length.

* The signal frame record for SVE always contains basic metadata, in particular
  the thread's vector length (in sve_context.vl).

* The SVE registers may or may not be included in the record, depending on
  whether the registers are live for the thread.  The registers are present if
  and only if:
  sve_context.head.size >= SVE_SIG_CONTEXT_SIZE(sve_vq_from_vl(sve_context.vl)).

* If the registers are present, the remainder of the record has a vl-dependent
  size and layout.  Macros SVE_SIG_* are defined [1] to facilitate access to
  the members.

* Each scalable register (Zn, Pn, FFR) is stored in an endianness-invariant
  layout, with bits [(8 * i + 7) : (8 * i)] stored at byte offset i from the
  start of the register's representation in memory.

* If the SVE context is too big to fit in sigcontext.__reserved[], then extra
  space is allocated on the stack, an extra_context record is written in
  __reserved[] referencing this space.  sve_context is then written in the
  extra space.  Refer to [1] for further details about this mechanism.

5.  Signal return
-----------------

When returning from a signal handler:

* If there is no sve_context record in the signal frame, or if the record is
  present but contains no register data as desribed in the previous section,
  then the SVE registers/bits become non-live and take unspecified values.

* If sve_context is present in the signal frame and contains full register
  data, the SVE registers become live and are populated with the specified
  data.  However, for backward compatibility reasons, bits [127:0] of Z0..Z31
  are always restored from the corresponding members of fpsimd_context.vregs[]
  and not from sve_context.  The remaining bits are restored from sve_context.

* Inclusion of fpsimd_context in the signal frame remains mandatory,
  irrespective of whether sve_context is present or not.

* The vector length cannot be changed via signal return.  If sve_context.vl in
  the signal frame does not match the current vector length, the signal return
  attempt is treated as illegal, resulting in a forced SIGSEGV.

* It is permitted to enter or leave streaming mode by setting or clearing
  the SVE_SIG_FLAG_SM flag but applications should take care to ensure that
  when doing so sve_context.vl and any register data are appropriate for the
  vector length in the new mode.

6.  prctl extensions
--------------------

Some new prctl() calls are added to allow programs to manage the SVE vector
length:

prctl(PR_SVE_SET_VL, unsigned long arg)

    Sets the vector length of the calling thread and related flags, where
    arg == vl | flags.  Other threads of the calling process are unaffected.

    vl is the desired vector length, where sve_vl_valid(vl) must be true.

    flags:

	PR_SVE_VL_INHERIT

	    Inherit the current vector length across execve().  Otherwise, the
	    vector length is reset to the system default at execve().  (See
	    Section 9.)

	PR_SVE_SET_VL_ONEXEC

	    Defer the requested vector length change until the next execve()
	    performed by this thread.

	    The effect is equivalent to implicit exceution of the following
	    call immediately after the next execve() (if any) by the thread:

		prctl(PR_SVE_SET_VL, arg & ~PR_SVE_SET_VL_ONEXEC)

	    This allows launching of a new program with a different vector
	    length, while avoiding runtime side effects in the caller.

	    Without PR_SVE_SET_VL_ONEXEC, the requested change takes effect
	    immediately.

    Return value: a nonnegative on success, or a negative value on error:
	EINVAL: SVE not supported, invalid vector length requested, or
	    invalid flags.

    On success:

    * Either the calling thread's vector length or the deferred vector length
      to be applied at the next execve() by the thread (dependent on whether
      PR_SVE_SET_VL_ONEXEC is present in arg), is set to the largest value
      supported by the system that is less than or equal to vl.  If vl ==
      SVE_VL_MAX, the value set will be the largest value supported by the
      system.

    * Any previously outstanding deferred vector length change in the calling
      thread is cancelled.

    * The returned value describes the resulting configuration, encoded as for
      PR_SVE_GET_VL.  The vector length reported in this value is the new
      current vector length for this thread if PR_SVE_SET_VL_ONEXEC was not
      present in arg; otherwise, the reported vector length is the deferred
      vector length that will be applied at the next execve() by the calling
      thread.

    * Changing the vector length causes all of P0..P15, FFR and all bits of
      Z0..Z31 except for Z0 bits [127:0] .. Z31 bits [127:0] to become
      unspecified.  Calling PR_SVE_SET_VL with vl equal to the thread's current
      vector length, or calling PR_SVE_SET_VL with the PR_SVE_SET_VL_ONEXEC
      flag, does not constitute a change to the vector length for this purpose.

prctl(PR_SVE_GET_VL)

    Gets the vector length of the calling thread.

    The following flag may be OR-ed into the result:

	PR_SVE_VL_INHERIT

	    Vector length will be inherited across execve().

    There is no way to determine whether there is an outstanding deferred
    vector length change (which would only normally be the case between a
    fork() or vfork() and the corresponding execve() in typical use).

    To extract the vector length from the result, bitwise and it with
    PR_SVE_VL_LEN_MASK.

    Return value: a nonnegative value on success, or a negative value on error:
	EINVAL: SVE not supported.

7.  ptrace extensions
---------------------

* New regsets NT_ARM_SVE and NT_ARM_SSVE are defined for use with
  PTRACE_GETREGSET and PTRACE_SETREGSET. NT_ARM_SSVE describes the
  streaming mode SVE registers and NT_ARM_SVE describes the
  non-streaming mode SVE registers.

  In this description a register set is referred to as being "live" when
  the target is in the appropriate streaming or non-streaming mode and is
  using data beyond the subset shared with the FPSIMD Vn registers.

  Refer to [2] for definitions.

The regset data starts with struct user_sve_header, containing:

    size

	Size of the complete regset, in bytes.
	This depends on vl and possibly on other things in the future.

	If a call to PTRACE_GETREGSET requests less data than the value of
	size, the caller can allocate a larger buffer and retry in order to
	read the complete regset.

    max_size

	Maximum size in bytes that the regset can grow to for the target
	thread.  The regset won't grow bigger than this even if the target
	thread changes its vector length etc.

    vl

	Target thread's current vector length, in bytes.

    max_vl

	Maximum possible vector length for the target thread.

    flags

	at most one of

	    SVE_PT_REGS_FPSIMD

		SVE registers are not live (GETREGSET) or are to be made
		non-live (SETREGSET).

		The payload is of type struct user_fpsimd_state, with the same
		meaning as for NT_PRFPREG, starting at offset
		SVE_PT_FPSIMD_OFFSET from the start of user_sve_header.

		Extra data might be appended in the future: the size of the
		payload should be obtained using SVE_PT_FPSIMD_SIZE(vq, flags).

		vq should be obtained using sve_vq_from_vl(vl).

		or

	    SVE_PT_REGS_SVE

		SVE registers are live (GETREGSET) or are to be made live
		(SETREGSET).

		The payload contains the SVE register data, starting at offset
		SVE_PT_SVE_OFFSET from the start of user_sve_header, and with
		size SVE_PT_SVE_SIZE(vq, flags);

	... OR-ed with zero or more of the following flags, which have the same
	meaning and behaviour as the corresponding PR_SET_VL_* flags:

	    SVE_PT_VL_INHERIT

	    SVE_PT_VL_ONEXEC (SETREGSET only).

	If neither FPSIMD nor SVE flags are provided then no register
	payload is available, this is only possible when SME is implemented.

* The effects of changing the vector length and/or flags are equivalent to
  those documented for PR_SVE_SET_VL.

  The caller must make a further GETREGSET call if it needs to know what VL is
  actually set by SETREGSET, unless is it known in advance that the requested
  VL is supported.

* In the SVE_PT_REGS_SVE case, the size and layout of the payload depends on
  the header fields.  The SVE_PT_SVE_*() macros are provided to facilitate
  access to the members.

* In either case, for SETREGSET it is permissible to omit the payload, in which
  case only the vector length and flags are changed (along with any
  consequences of those changes).

* In systems supporting SME when in streaming mode a GETREGSET for
  NT_REG_SVE will return only the user_sve_header with no register data,
  similarly a GETREGSET for NT_REG_SSVE will not return any register data
  when not in streaming mode.

* A GETREGSET for NT_ARM_SSVE will never return SVE_PT_REGS_FPSIMD.

* For SETREGSET, if an SVE_PT_REGS_SVE payload is present and the
  requested VL is not supported, the effect will be the same as if the
  payload were omitted, except that an EIO error is reported.  No
  attempt is made to translate the payload data to the correct layout
  for the vector length actually set.  The thread's FPSIMD state is
  preserved, but the remaining bits of the SVE registers become
  unspecified.  It is up to the caller to translate the payload layout
  for the actual VL and retry.

* Where SME is implemented it is not possible to GETREGSET the register
  state for normal SVE when in streaming mode, nor the streaming mode
  register state when in normal mode, regardless of the implementation defined
  behaviour of the hardware for sharing data between the two modes.

* Any SETREGSET of NT_ARM_SVE will exit streaming mode if the target was in
  streaming mode and any SETREGSET of NT_ARM_SSVE will enter streaming mode
  if the target was not in streaming mode.

* The effect of writing a partial, incomplete payload is unspecified.

8.  ELF coredump extensions
---------------------------

* NT_ARM_SVE and NT_ARM_SSVE notes will be added to each coredump for
  each thread of the dumped process.  The contents will be equivalent to the
  data that would have been read if a PTRACE_GETREGSET of the corresponding
  type were executed for each thread when the coredump was generated.

9.  System runtime configuration
--------------------------------

* To mitigate the ABI impact of expansion of the signal frame, a policy
  mechanism is provided for administrators, distro maintainers and developers
  to set the default vector length for userspace processes:

/proc/sys/abi/sve_default_vector_length

    Writing the text representation of an integer to this file sets the system
    default vector length to the specified value, unless the value is greater
    than the maximum vector length supported by the system in which case the
    default vector length is set to that maximum.

    The result can be determined by reopening the file and reading its
    contents.

    At boot, the default vector length is initially set to 64 or the maximum
    supported vector length, whichever is smaller.  This determines the initial
    vector length of the init process (PID 1).

    Reading this file returns the current system default vector length.

* At every execve() call, the new vector length of the new process is set to
  the system default vector length, unless

    * PR_SVE_VL_INHERIT (or equivalently SVE_PT_VL_INHERIT) is set for the
      calling thread, or

    * a deferred vector length change is pending, established via the
      PR_SVE_SET_VL_ONEXEC flag (or SVE_PT_VL_ONEXEC).

* Modifying the system default vector length does not affect the vector length
  of any existing process or thread that does not make an execve() call.

10.  Perf extensions
--------------------------------

* The arm64 specific DWARF standard [5] added the VG (Vector Granule) register
  at index 46. This register is used for DWARF unwinding when variable length
  SVE registers are pushed onto the stack.

* Its value is equivalent to the current SVE vector length (VL) in bits divided
  by 64.

* The value is included in Perf samples in the regs[46] field if
  PERF_SAMPLE_REGS_USER is set and the sample_regs_user mask has bit 46 set.

* The value is the current value at the time the sample was taken, and it can
  change over time.

* If the system doesn't support SVE when perf_event_open is called with these
  settings, the event will fail to open.

Appendix A.  SVE programmer's model (informative)
=================================================

This section provides a minimal description of the additions made by SVE to the
ARMv8-A programmer's model that are relevant to this document.

Note: This section is for information only and not intended to be complete or
to replace any architectural specification.

A.1.  Registers
---------------

In A64 state, SVE adds the following:

* 32 8VL-bit vector registers Z0..Z31
  For each Zn, Zn bits [127:0] alias the ARMv8-A vector register Vn.

  A register write using a Vn register name zeros all bits of the corresponding
  Zn except for bits [127:0].

* 16 VL-bit predicate registers P0..P15

* 1 VL-bit special-purpose predicate register FFR (the "first-fault register")

* a VL "pseudo-register" that determines the size of each vector register

  The SVE instruction set architecture provides no way to write VL directly.
  Instead, it can be modified only by EL1 and above, by writing appropriate
  system registers.

* The value of VL can be configured at runtime by EL1 and above:
  16 <= VL <= VLmax, where VL must be a multiple of 16.

* The maximum vector length is determined by the hardware:
  16 <= VLmax <= 256.

  (The SVE architecture specifies 256, but permits future architecture
  revisions to raise this limit.)

* FPSR and FPCR are retained from ARMv8-A, and interact with SVE floating-point
  operations in a similar way to the way in which they interact with ARMv8
  floating-point operations::

         8VL-1                       128               0  bit index
        +----          ////            -----------------+
     Z0 |                               :       V0      |
      :                                          :
     Z7 |                               :       V7      |
     Z8 |                               :     * V8      |
      :                                       :  :
    Z15 |                               :     *V15      |
    Z16 |                               :      V16      |
      :                                          :
    Z31 |                               :      V31      |
        +----          ////            -----------------+
                                                 31    0
         VL-1                  0                +-------+
        +----       ////      --+          FPSR |       |
     P0 |                       |               +-------+
      : |                       |         *FPCR |       |
    P15 |                       |               +-------+
        +----       ////      --+
    FFR |                       |               +-----+
        +----       ////      --+            VL |     |
                                                +-----+

(*) callee-save:
    This only applies to bits [63:0] of Z-/V-registers.
    FPCR contains callee-save and caller-save bits.  See [4] for details.

A.2.  Procedure call standard
-----------------------------

The ARMv8-A base procedure call standard is extended as follows with respect to
the additional SVE register state:

* All SVE register bits that are not shared with FP/SIMD are caller-save.

* Z8 bits [63:0] .. Z15 bits [63:0] are callee-save.

  This follows from the way these bits are mapped to V8..V15, which are caller-
  save in the base procedure call standard.

Appendix B.  ARMv8-A FP/SIMD programmer's model
===============================================

Note: This section is for information only and not intended to be complete or
to replace any architectural specification.

Refer to [4] for more information.

ARMv8-A defines the following floating-point / SIMD register state:

* 32 128-bit vector registers V0..V31
* 2 32-bit status/control registers FPSR, FPCR

::

         127           0  bit index
        +---------------+
     V0 |               |
      : :               :
     V7 |               |
   * V8 |               |
   :  : :               :
   *V15 |               |
    V16 |               |
      : :               :
    V31 |               |
        +---------------+

                 31    0
                +-------+
           FPSR |       |
                +-------+
          *FPCR |       |
                +-------+

(*) callee-save:
    This only applies to bits [63:0] of V-registers.
    FPCR contains a mixture of callee-save and caller-save bits.

References
==========

[1] arch/arm64/include/uapi/asm/sigcontext.h
    AArch64 Linux signal ABI definitions

[2] arch/arm64/include/uapi/asm/ptrace.h
    AArch64 Linux ptrace ABI definitions

[3] Documentation/arm64/cpu-feature-registers.rst

[4] ARM IHI0055C
    http://infocenter.arm.com/help/topic/com.arm.doc.ihi0055c/IHI0055C_beta_aapcs64.pdf
    http://infocenter.arm.com/help/topic/com.arm.doc.subset.swdev.abi/index.html
    Procedure Call Standard for the ARM 64-bit Architecture (AArch64)

[5] https://github.com/ARM-software/abi-aa/blob/main/aadwarf64/aadwarf64.rst


code:
==========================
AArch64 TAGGED ADDRESS ABI
==========================

Authors: Vincenzo Frascino <vincenzo.frascino@arm.com>
         Catalin Marinas <catalin.marinas@arm.com>

Date: 21 August 2019

This document describes the usage and semantics of the Tagged Address
ABI on AArch64 Linux.

1. Introduction
---------------

On AArch64 the ``TCR_EL1.TBI0`` bit is set by default, allowing
userspace (EL0) to perform memory accesses through 64-bit pointers with
a non-zero top byte. This document describes the relaxation of the
syscall ABI that allows userspace to pass certain tagged pointers to
kernel syscalls.

2. AArch64 Tagged Address ABI
-----------------------------

From the kernel syscall interface perspective and for the purposes of
this document, a "valid tagged pointer" is a pointer with a potentially
non-zero top-byte that references an address in the user process address
space obtained in one of the following ways:

- ``mmap()`` syscall where either:

  - flags have the ``MAP_ANONYMOUS`` bit set or
  - the file descriptor refers to a regular file (including those
    returned by ``memfd_create()``) or ``/dev/zero``

- ``brk()`` syscall (i.e. the heap area between the initial location of
  the program break at process creation and its current location).

- any memory mapped by the kernel in the address space of the process
  during creation and with the same restrictions as for ``mmap()`` above
  (e.g. data, bss, stack).

The AArch64 Tagged Address ABI has two stages of relaxation depending on
how the user addresses are used by the kernel:

1. User addresses not accessed by the kernel but used for address space
   management (e.g. ``mprotect()``, ``madvise()``). The use of valid
   tagged pointers in this context is allowed with these exceptions:

   - ``brk()``, ``mmap()`` and the ``new_address`` argument to
     ``mremap()`` as these have the potential to alias with existing
     user addresses.

     NOTE: This behaviour changed in v5.6 and so some earlier kernels may
     incorrectly accept valid tagged pointers for the ``brk()``,
     ``mmap()`` and ``mremap()`` system calls.

   - The ``range.start``, ``start`` and ``dst`` arguments to the
     ``UFFDIO_*`` ``ioctl()``s used on a file descriptor obtained from
     ``userfaultfd()``, as fault addresses subsequently obtained by reading
     the file descriptor will be untagged, which may otherwise confuse
     tag-unaware programs.

     NOTE: This behaviour changed in v5.14 and so some earlier kernels may
     incorrectly accept valid tagged pointers for this system call.

2. User addresses accessed by the kernel (e.g. ``write()``). This ABI
   relaxation is disabled by default and the application thread needs to
   explicitly enable it via ``prctl()`` as follows:

   - ``PR_SET_TAGGED_ADDR_CTRL``: enable or disable the AArch64 Tagged
     Address ABI for the calling thread.

     The ``(unsigned int) arg2`` argument is a bit mask describing the
     control mode used:

     - ``PR_TAGGED_ADDR_ENABLE``: enable AArch64 Tagged Address ABI.
       Default status is disabled.

     Arguments ``arg3``, ``arg4``, and ``arg5`` must be 0.

   - ``PR_GET_TAGGED_ADDR_CTRL``: get the status of the AArch64 Tagged
     Address ABI for the calling thread.

     Arguments ``arg2``, ``arg3``, ``arg4``, and ``arg5`` must be 0.

   The ABI properties described above are thread-scoped, inherited on
   clone() and fork() and cleared on exec().

   Calling ``prctl(PR_SET_TAGGED_ADDR_CTRL, PR_TAGGED_ADDR_ENABLE, 0, 0, 0)``
   returns ``-EINVAL`` if the AArch64 Tagged Address ABI is globally
   disabled by ``sysctl abi.tagged_addr_disabled=1``. The default
   ``sysctl abi.tagged_addr_disabled`` configuration is 0.

When the AArch64 Tagged Address ABI is enabled for a thread, the
following behaviours are guaranteed:

- All syscalls except the cases mentioned in section 3 can accept any
  valid tagged pointer.

- The syscall behaviour is undefined for invalid tagged pointers: it may
  result in an error code being returned, a (fatal) signal being raised,
  or other modes of failure.

- The syscall behaviour for a valid tagged pointer is the same as for
  the corresponding untagged pointer.

A definition of the meaning of tagged pointers on AArch64 can be found
in Documentation/arm64/tagged-pointers.rst.

3. AArch64 Tagged Address ABI Exceptions
-----------------------------------------

The following system call parameters must be untagged regardless of the
ABI relaxation:

- ``prctl()`` other than pointers to user data either passed directly or
  indirectly as arguments to be accessed by the kernel.

- ``ioctl()`` other than pointers to user data either passed directly or
  indirectly as arguments to be accessed by the kernel.

- ``shmat()`` and ``shmdt()``.

- ``brk()`` (since kernel v5.6).

- ``mmap()`` (since kernel v5.6).

- ``mremap()``, the ``new_address`` argument (since kernel v5.6).

Any attempt to use non-zero tagged pointers may result in an error code
being returned, a (fatal) signal being raised, or other modes of
failure.

4. Example of correct usage
---------------------------
.. code-block:: c

   #include <stdlib.h>
   #include <string.h>
   #include <unistd.h>
   #include <sys/mman.h>
   #include <sys/prctl.h>

   #define PR_SET_TAGGED_ADDR_CTRL	55
   #define PR_TAGGED_ADDR_ENABLE	(1UL << 0)

   #define TAG_SHIFT		56

   int main(void)
   {
   	int tbi_enabled = 0;
   	unsigned long tag = 0;
   	char *ptr;

   	/* check/enable the tagged address ABI */
   	if (!prctl(PR_SET_TAGGED_ADDR_CTRL, PR_TAGGED_ADDR_ENABLE, 0, 0, 0))
   		tbi_enabled = 1;

   	/* memory allocation */
   	ptr = mmap(NULL, sysconf(_SC_PAGE_SIZE), PROT_READ | PROT_WRITE,
   		   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
   	if (ptr == MAP_FAILED)
   		return 1;

   	/* set a non-zero tag if the ABI is available */
   	if (tbi_enabled)
   		tag = rand() & 0xff;
   	ptr = (char *)((unsigned long)ptr | (tag << TAG_SHIFT));

   	/* memory access to a tagged address */
   	strcpy(ptr, "tagged pointer\n");

   	/* syscall with a tagged pointer */
   	write(1, ptr, strlen(ptr));

   	return 0;
   }

repo_name: angery/linux


code:
=========================================
Tagged virtual addresses in AArch64 Linux
=========================================

Author: Will Deacon <will.deacon@arm.com>

Date  : 12 June 2013

This document briefly describes the provision of tagged virtual
addresses in the AArch64 translation system and their potential uses
in AArch64 Linux.

The kernel configures the translation tables so that translations made
via TTBR0 (i.e. userspace mappings) have the top byte (bits 63:56) of
the virtual address ignored by the translation hardware. This frees up
this byte for application use.

Passing tagged addresses to the kernel
--------------------------------------

All interpretation of userspace memory addresses by the kernel assumes
an address tag of 0x00, unless the application enables the AArch64
Tagged Address ABI explicitly
(Documentation/arm64/tagged-address-abi.rst).

This includes, but is not limited to, addresses found in:

 - pointer arguments to system calls, including pointers in structures
   passed to system calls,

 - the stack pointer (sp), e.g. when interpreting it to deliver a
   signal,

 - the frame pointer (x29) and frame records, e.g. when interpreting
   them to generate a backtrace or call graph.

Using non-zero address tags in any of these locations when the
userspace application did not enable the AArch64 Tagged Address ABI may
result in an error code being returned, a (fatal) signal being raised,
or other modes of failure.

For these reasons, when the AArch64 Tagged Address ABI is disabled,
passing non-zero address tags to the kernel via system calls is
forbidden, and using a non-zero address tag for sp is strongly
discouraged.

Programs maintaining a frame pointer and frame records that use non-zero
address tags may suffer impaired or inaccurate debug and profiling
visibility.

Preserving tags
---------------

When delivering signals, non-zero tags are not preserved in
siginfo.si_addr unless the flag SA_EXPOSE_TAGBITS was set in
sigaction.sa_flags when the signal handler was installed. This means
that signal handlers in applications making use of tags cannot rely
on the tag information for user virtual addresses being maintained
in these fields unless the flag was set.

Due to architecture limitations, bits 63:60 of the fault address
are not preserved in response to synchronous tag check faults
(SEGV_MTESERR) even if SA_EXPOSE_TAGBITS was set. Applications should
treat the values of these bits as undefined in order to accommodate
future architecture revisions which may preserve the bits.

For signals raised in response to watchpoint debug exceptions, the
tag information will be preserved regardless of the SA_EXPOSE_TAGBITS
flag setting.

Non-zero tags are never preserved in sigcontext.fault_address
regardless of the SA_EXPOSE_TAGBITS flag setting.

The architecture prevents the use of a tagged PC, so the upper byte will
be set to a sign-extension of bit 55 on exception return.

This behaviour is maintained when the AArch64 Tagged Address ABI is
enabled.

Other considerations
--------------------

Special care should be taken when using tagged pointers, since it is
likely that C compilers will not hazard two virtual addresses differing
only in the upper byte.


code:
=============
Atomic bitops
=============

While our bitmap_{}() functions are non-atomic, we have a number of operations
operating on single bits in a bitmap that are atomic.

API
---

The single bit operations are:

Non-RMW ops:

  test_bit()

RMW atomic operations without return value:

  {set,clear,change}_bit()
  clear_bit_unlock()

RMW atomic operations with return value:

  test_and_{set,clear,change}_bit()
  test_and_set_bit_lock()

Barriers:

  smp_mb__{before,after}_atomic()

All RMW atomic operations have a '__' prefixed variant which is non-atomic.

SEMANTICS
---------

Non-atomic ops:

In particular __clear_bit_unlock() suffers the same issue as atomic_set(),
which is why the generic version maps to clear_bit_unlock(), see atomic_t.txt.

RMW ops:

The test_and_{}_bit() operations return the original value of the bit.

ORDERING
--------

Like with atomic_t, the rule of thumb is:

 - non-RMW operations are unordered;

 - RMW operations that have no return value are unordered;

 - RMW operations that have a return value are fully ordered.

 - RMW operations that are conditional are fully ordered.

Except for a successful test_and_set_bit_lock() which has ACQUIRE semantics,
clear_bit_unlock() which has RELEASE semantics and test_bit_acquire which has
ACQUIRE semantics.

Since a platform only has a single means of achieving atomic operations
the same barriers as for atomic_t are used, see atomic_t.txt.


code:
On atomic types (atomic_t atomic64_t and atomic_long_t).

The atomic type provides an interface to the architecture's means of atomic
RMW operations between CPUs (atomic operations on MMIO are not supported and
can lead to fatal traps on some platforms).

API
---

The 'full' API consists of (atomic64_ and atomic_long_ prefixes omitted for
brevity):

Non-RMW ops:

  atomic_read(), atomic_set()
  atomic_read_acquire(), atomic_set_release()

RMW atomic operations:

Arithmetic:

  atomic_{add,sub,inc,dec}()
  atomic_{add,sub,inc,dec}_return{,_relaxed,_acquire,_release}()
  atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()

Bitwise:

  atomic_{and,or,xor,andnot}()
  atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()

Swap:

  atomic_xchg{,_relaxed,_acquire,_release}()
  atomic_cmpxchg{,_relaxed,_acquire,_release}()
  atomic_try_cmpxchg{,_relaxed,_acquire,_release}()

Reference count (but please see refcount_t):

  atomic_add_unless(), atomic_inc_not_zero()
  atomic_sub_and_test(), atomic_dec_and_test()

Misc:

  atomic_inc_and_test(), atomic_add_negative()
  atomic_dec_unless_positive(), atomic_inc_unless_negative()

Barriers:

  smp_mb__{before,after}_atomic()

TYPES (signed vs unsigned)
-----

While atomic_t, atomic_long_t and atomic64_t use int, long and s64
respectively (for hysterical raisins), the kernel uses -fno-strict-overflow
(which implies -fwrapv) and defines signed overflow to behave like
2s-complement.

Therefore, an explicitly unsigned variant of the atomic ops is strictly
unnecessary and we can simply cast, there is no UB.

There was a bug in UBSAN prior to GCC-8 that would generate UB warnings for
signed types.

With this we also conform to the C/C++ _Atomic behaviour and things like
P1236R1.

SEMANTICS
---------

Non-RMW ops:

The non-RMW ops are (typically) regular LOADs and STOREs and are canonically
implemented using READ_ONCE(), WRITE_ONCE(), smp_load_acquire() and
smp_store_release() respectively. Therefore, if you find yourself only using
the Non-RMW operations of atomic_t, you do not in fact need atomic_t at all
and are doing it wrong.

A note for the implementation of atomic_set{}() is that it must not break the
atomicity of the RMW ops. That is:

  C Atomic-RMW-ops-are-atomic-WRT-atomic_set

  {
    atomic_t v = ATOMIC_INIT(1);
  }

  P0(atomic_t *v)
  {
    (void)atomic_add_unless(v, 1, 0);
  }

  P1(atomic_t *v)
  {
    atomic_set(v, 0);
  }

  exists
  (v=2)

In this case we would expect the atomic_set() from CPU1 to either happen
before the atomic_add_unless(), in which case that latter one would no-op, or
_after_ in which case we'd overwrite its result. In no case is "2" a valid
outcome.

This is typically true on 'normal' platforms, where a regular competing STORE
will invalidate a LL/SC or fail a CMPXCHG.

The obvious case where this is not so is when we need to implement atomic ops
with a lock:

  CPU0						CPU1

  atomic_add_unless(v, 1, 0);
    lock();
    ret = READ_ONCE(v->counter); // == 1
						atomic_set(v, 0);
    if (ret != u)				  WRITE_ONCE(v->counter, 0);
      WRITE_ONCE(v->counter, ret + 1);
    unlock();

the typical solution is to then implement atomic_set{}() with atomic_xchg().

RMW ops:

These come in various forms:

 - plain operations without return value: atomic_{}()

 - operations which return the modified value: atomic_{}_return()

   these are limited to the arithmetic operations because those are
   reversible. Bitops are irreversible and therefore the modified value
   is of dubious utility.

 - operations which return the original value: atomic_fetch_{}()

 - swap operations: xchg(), cmpxchg() and try_cmpxchg()

 - misc; the special purpose operations that are commonly used and would,
   given the interface, normally be implemented using (try_)cmpxchg loops but
   are time critical and can, (typically) on LL/SC architectures, be more
   efficiently implemented.

All these operations are SMP atomic; that is, the operations (for a single
atomic variable) can be fully ordered and no intermediate state is lost or
visible.

ORDERING  (go read memory-barriers.txt first)
--------

The rule of thumb:

 - non-RMW operations are unordered;

 - RMW operations that have no return value are unordered;

 - RMW operations that have a return value are fully ordered;

 - RMW operations that are conditional are unordered on FAILURE,
   otherwise the above rules apply.

Except of course when an operation has an explicit ordering like:

 {}_relaxed: unordered
 {}_acquire: the R of the RMW (or atomic_read) is an ACQUIRE
 {}_release: the W of the RMW (or atomic_set)  is a  RELEASE

Where 'unordered' is against other memory locations. Address dependencies are
not defeated.

Fully ordered primitives are ordered against everything prior and everything
subsequent. Therefore a fully ordered primitive is like having an smp_mb()
before and an smp_mb() after the primitive.

The barriers:

  smp_mb__{before,after}_atomic()

only apply to the RMW atomic ops and can be used to augment/upgrade the
ordering inherent to the op. These barriers act almost like a full smp_mb():
smp_mb__before_atomic() orders all earlier accesses against the RMW op
itself and all accesses following it, and smp_mb__after_atomic() orders all
later accesses against the RMW op and all accesses preceding it. However,
accesses between the smp_mb__{before,after}_atomic() and the RMW op are not
ordered, so it is advisable to place the barrier right next to the RMW atomic
op whenever possible.

These helper barriers exist because architectures have varying implicit
ordering on their SMP atomic primitives. For example our TSO architectures
provide full ordered atomics and these barriers are no-ops.

NOTE: when the atomic RmW ops are fully ordered, they should also imply a
compiler barrier.

Thus:

  atomic_fetch_add();

is equivalent to:

  smp_mb__before_atomic();
  atomic_fetch_add_relaxed();
  smp_mb__after_atomic();

However the atomic_fetch_add() might be implemented more efficiently.

Further, while something like:

  smp_mb__before_atomic();
  atomic_dec(&X);

is a 'typical' RELEASE pattern, the barrier is strictly stronger than
a RELEASE because it orders preceding instructions against both the read
and write parts of the atomic_dec(), and against all following instructions
as well. Similarly, something like:

  atomic_inc(&X);
  smp_mb__after_atomic();

is an ACQUIRE pattern (though very much not typical), but again the barrier is
strictly stronger than ACQUIRE. As illustrated:

  C Atomic-RMW+mb__after_atomic-is-stronger-than-acquire

  {
  }

  P0(int *x, atomic_t *y)
  {
    r0 = READ_ONCE(*x);
    smp_rmb();
    r1 = atomic_read(y);
  }

  P1(int *x, atomic_t *y)
  {
    atomic_inc(y);
    smp_mb__after_atomic();
    WRITE_ONCE(*x, 1);
  }

  exists
  (0:r0=1 /\ 0:r1=0)

This should not happen; but a hypothetical atomic_inc_acquire() --
(void)atomic_fetch_inc_acquire() for instance -- would allow the outcome,
because it would not order the W part of the RMW against the following
WRITE_ONCE.  Thus:

  P0			P1

			t = LL.acq *y (0)
			t++;
			*x = 1;
  r0 = *x (1)
  RMB
  r1 = *y (0)
			SC *y, t;

is allowed.

CMPXCHG vs TRY_CMPXCHG
----------------------

  int atomic_cmpxchg(atomic_t *ptr, int old, int new);
  bool atomic_try_cmpxchg(atomic_t *ptr, int *oldp, int new);

Both provide the same functionality, but try_cmpxchg() can lead to more
compact code. The functions relate like:

  bool atomic_try_cmpxchg(atomic_t *ptr, int *oldp, int new)
  {
    int ret, old = *oldp;
    ret = atomic_cmpxchg(ptr, old, new);
    if (ret != old)
      *oldp = ret;
    return ret == old;
  }

and:

  int atomic_cmpxchg(atomic_t *ptr, int old, int new)
  {
    (void)atomic_try_cmpxchg(ptr, &old, new);
    return old;
  }

Usage:

  old = atomic_read(&v);			old = atomic_read(&v);
  for (;;) {					do {
    new = func(old);				  new = func(old);
    tmp = atomic_cmpxchg(&v, old, new);		} while (!atomic_try_cmpxchg(&v, &old, new));
    if (tmp == old)
      break;
    old = tmp;
  }

NB. try_cmpxchg() also generates better code on some platforms (notably x86)
where the function more closely matches the hardware instruction.

FORWARD PROGRESS
----------------

In general strong forward progress is expected of all unconditional atomic
operations -- those in the Arithmetic and Bitwise classes and xchg(). However
a fair amount of code also requires forward progress from the conditional
atomic operations.

Specifically 'simple' cmpxchg() loops are expected to not starve one another
indefinitely. However, this is not evident on LL/SC architectures, because
while an LL/SC architecure 'can/should/must' provide forward progress
guarantees between competing LL/SC sections, such a guarantee does not
transfer to cmpxchg() implemented using LL/SC. Consider:

  old = atomic_read(&v);
  do {
    new = func(old);
  } while (!atomic_try_cmpxchg(&v, &old, new));

which on LL/SC becomes something like:

  old = atomic_read(&v);
  do {
    new = func(old);
  } while (!({
    volatile asm ("1: LL  %[oldval], %[v]\n"
                  "   CMP %[oldval], %[old]\n"
                  "   BNE 2f\n"
                  "   SC  %[new], %[v]\n"
                  "   BNE 1b\n"
                  "2:\n"
                  : [oldval] "=&r" (oldval), [v] "m" (v)
		  : [old] "r" (old), [new] "r" (new)
                  : "memory");
    success = (oldval == old);
    if (!success)
      old = oldval;
    success; }));

However, even the forward branch from the failed compare can cause the LL/SC
to fail on some architectures, let alone whatever the compiler makes of the C
loop body. As a result there is no guarantee what so ever the cacheline
containing @v will stay on the local CPU and progress is made.

Even native CAS architectures can fail to provide forward progress for their
primitive (See Sparc64 for an example).

Such implementations are strongly encouraged to add exponential backoff loops
to a failed CAS in order to ensure some progress. Affected architectures are
also strongly encouraged to inspect/audit the atomic fallbacks, refcount_t and
their locking primitives.


code:
==========================
BFQ (Budget Fair Queueing)
==========================

BFQ is a proportional-share I/O scheduler, with some extra
low-latency capabilities. In addition to cgroups support (blkio or io
controllers), BFQ's main features are:

- BFQ guarantees a high system and application responsiveness, and a
  low latency for time-sensitive applications, such as audio or video
  players;
- BFQ distributes bandwidth, and not just time, among processes or
  groups (switching back to time distribution when needed to keep
  throughput high).

In its default configuration, BFQ privileges latency over
throughput. So, when needed for achieving a lower latency, BFQ builds
schedules that may lead to a lower throughput. If your main or only
goal, for a given device, is to achieve the maximum-possible
throughput at all times, then do switch off all low-latency heuristics
for that device, by setting low_latency to 0. See Section 3 for
details on how to configure BFQ for the desired tradeoff between
latency and throughput, or on how to maximize throughput.

As every I/O scheduler, BFQ adds some overhead to per-I/O-request
processing. To give an idea of this overhead, the total,
single-lock-protected, per-request processing time of BFQ---i.e., the
sum of the execution times of the request insertion, dispatch and
completion hooks---is, e.g., 1.9 us on an Intel Core i7-2760QM@2.40GHz
(dated CPU for notebooks; time measured with simple code
instrumentation, and using the throughput-sync.sh script of the S
suite [1], in performance-profiling mode). To put this result into
context, the total, single-lock-protected, per-request execution time
of the lightest I/O scheduler available in blk-mq, mq-deadline, is 0.7
us (mq-deadline is ~800 LOC, against ~10500 LOC for BFQ).

Scheduling overhead further limits the maximum IOPS that a CPU can
process (already limited by the execution of the rest of the I/O
stack). To give an idea of the limits with BFQ, on slow or average
CPUs, here are, first, the limits of BFQ for three different CPUs, on,
respectively, an average laptop, an old desktop, and a cheap embedded
system, in case full hierarchical support is enabled (i.e.,
CONFIG_BFQ_GROUP_IOSCHED is set), but CONFIG_BFQ_CGROUP_DEBUG is not
set (Section 4-2):
- Intel i7-4850HQ: 400 KIOPS
- AMD A8-3850: 250 KIOPS
- ARM CortexTM-A53 Octa-core: 80 KIOPS

If CONFIG_BFQ_CGROUP_DEBUG is set (and of course full hierarchical
support is enabled), then the sustainable throughput with BFQ
decreases, because all blkio.bfq* statistics are created and updated
(Section 4-2). For BFQ, this leads to the following maximum
sustainable throughputs, on the same systems as above:
- Intel i7-4850HQ: 310 KIOPS
- AMD A8-3850: 200 KIOPS
- ARM CortexTM-A53 Octa-core: 56 KIOPS

BFQ works for multi-queue devices too.

.. The table of contents follow. Impatients can just jump to Section 3.

.. CONTENTS

   1. When may BFQ be useful?
    1-1 Personal systems
    1-2 Server systems
   2. How does BFQ work?
   3. What are BFQ's tunables and how to properly configure BFQ?
   4. BFQ group scheduling
    4-1 Service guarantees provided
    4-2 Interface

1. When may BFQ be useful?
==========================

BFQ provides the following benefits on personal and server systems.

1-1 Personal systems
--------------------

Low latency for interactive applications
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Regardless of the actual background workload, BFQ guarantees that, for
interactive tasks, the storage device is virtually as responsive as if
it was idle. For example, even if one or more of the following
background workloads are being executed:

- one or more large files are being read, written or copied,
- a tree of source files is being compiled,
- one or more virtual machines are performing I/O,
- a software update is in progress,
- indexing daemons are scanning filesystems and updating their
  databases,

starting an application or loading a file from within an application
takes about the same time as if the storage device was idle. As a
comparison, with CFQ, NOOP or DEADLINE, and in the same conditions,
applications experience high latencies, or even become unresponsive
until the background workload terminates (also on SSDs).

Low latency for soft real-time applications
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Also soft real-time applications, such as audio and video
players/streamers, enjoy a low latency and a low drop rate, regardless
of the background I/O workload. As a consequence, these applications
do not suffer from almost any glitch due to the background workload.

Higher speed for code-development tasks
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

If some additional workload happens to be executed in parallel, then
BFQ executes the I/O-related components of typical code-development
tasks (compilation, checkout, merge, ...) much more quickly than CFQ,
NOOP or DEADLINE.

High throughput
^^^^^^^^^^^^^^^

On hard disks, BFQ achieves up to 30% higher throughput than CFQ, and
up to 150% higher throughput than DEADLINE and NOOP, with all the
sequential workloads considered in our tests. With random workloads,
and with all the workloads on flash-based devices, BFQ achieves,
instead, about the same throughput as the other schedulers.

Strong fairness, bandwidth and delay guarantees
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

BFQ distributes the device throughput, and not just the device time,
among I/O-bound applications in proportion their weights, with any
workload and regardless of the device parameters. From these bandwidth
guarantees, it is possible to compute tight per-I/O-request delay
guarantees by a simple formula. If not configured for strict service
guarantees, BFQ switches to time-based resource sharing (only) for
applications that would otherwise cause a throughput loss.

1-2 Server systems
------------------

Most benefits for server systems follow from the same service
properties as above. In particular, regardless of whether additional,
possibly heavy workloads are being served, BFQ guarantees:

* audio and video-streaming with zero or very low jitter and drop
  rate;

* fast retrieval of WEB pages and embedded objects;

* real-time recording of data in live-dumping applications (e.g.,
  packet logging);

* responsiveness in local and remote access to a server.

2. How does BFQ work?
=====================

BFQ is a proportional-share I/O scheduler, whose general structure,
plus a lot of code, are borrowed from CFQ.

- Each process doing I/O on a device is associated with a weight and a
  `(bfq_)queue`.

- BFQ grants exclusive access to the device, for a while, to one queue
  (process) at a time, and implements this service model by
  associating every queue with a budget, measured in number of
  sectors.

  - After a queue is granted access to the device, the budget of the
    queue is decremented, on each request dispatch, by the size of the
    request.

  - The in-service queue is expired, i.e., its service is suspended,
    only if one of the following events occurs: 1) the queue finishes
    its budget, 2) the queue empties, 3) a "budget timeout" fires.

    - The budget timeout prevents processes doing random I/O from
      holding the device for too long and dramatically reducing
      throughput.

    - Actually, as in CFQ, a queue associated with a process issuing
      sync requests may not be expired immediately when it empties. In
      contrast, BFQ may idle the device for a short time interval,
      giving the process the chance to go on being served if it issues
      a new request in time. Device idling typically boosts the
      throughput on rotational devices and on non-queueing flash-based
      devices, if processes do synchronous and sequential I/O. In
      addition, under BFQ, device idling is also instrumental in
      guaranteeing the desired throughput fraction to processes
      issuing sync requests (see the description of the slice_idle
      tunable in this document, or [1, 2], for more details).

      - With respect to idling for service guarantees, if several
	processes are competing for the device at the same time, but
	all processes and groups have the same weight, then BFQ
	guarantees the expected throughput distribution without ever
	idling the device. Throughput is thus as high as possible in
	this common scenario.

     - On flash-based storage with internal queueing of commands
       (typically NCQ), device idling happens to be always detrimental
       for throughput. So, with these devices, BFQ performs idling
       only when strictly needed for service guarantees, i.e., for
       guaranteeing low latency or fairness. In these cases, overall
       throughput may be sub-optimal. No solution currently exists to
       provide both strong service guarantees and optimal throughput
       on devices with internal queueing.

  - If low-latency mode is enabled (default configuration), BFQ
    executes some special heuristics to detect interactive and soft
    real-time applications (e.g., video or audio players/streamers),
    and to reduce their latency. The most important action taken to
    achieve this goal is to give to the queues associated with these
    applications more than their fair share of the device
    throughput. For brevity, we call just "weight-raising" the whole
    sets of actions taken by BFQ to privilege these queues. In
    particular, BFQ provides a milder form of weight-raising for
    interactive applications, and a stronger form for soft real-time
    applications.

  - BFQ automatically deactivates idling for queues born in a burst of
    queue creations. In fact, these queues are usually associated with
    the processes of applications and services that benefit mostly
    from a high throughput. Examples are systemd during boot, or git
    grep.

  - As CFQ, BFQ merges queues performing interleaved I/O, i.e.,
    performing random I/O that becomes mostly sequential if
    merged. Differently from CFQ, BFQ achieves this goal with a more
    reactive mechanism, called Early Queue Merge (EQM). EQM is so
    responsive in detecting interleaved I/O (cooperating processes),
    that it enables BFQ to achieve a high throughput, by queue
    merging, even for queues for which CFQ needs a different
    mechanism, preemption, to get a high throughput. As such EQM is a
    unified mechanism to achieve a high throughput with interleaved
    I/O.

  - Queues are scheduled according to a variant of WF2Q+, named
    B-WF2Q+, and implemented using an augmented rb-tree to preserve an
    O(log N) overall complexity.  See [2] for more details. B-WF2Q+ is
    also ready for hierarchical scheduling, details in Section 4.

  - B-WF2Q+ guarantees a tight deviation with respect to an ideal,
    perfectly fair, and smooth service. In particular, B-WF2Q+
    guarantees that each queue receives a fraction of the device
    throughput proportional to its weight, even if the throughput
    fluctuates, and regardless of: the device parameters, the current
    workload and the budgets assigned to the queue.

  - The last, budget-independence, property (although probably
    counterintuitive in the first place) is definitely beneficial, for
    the following reasons:

    - First, with any proportional-share scheduler, the maximum
      deviation with respect to an ideal service is proportional to
      the maximum budget (slice) assigned to queues. As a consequence,
      BFQ can keep this deviation tight not only because of the
      accurate service of B-WF2Q+, but also because BFQ *does not*
      need to assign a larger budget to a queue to let the queue
      receive a higher fraction of the device throughput.

    - Second, BFQ is free to choose, for every process (queue), the
      budget that best fits the needs of the process, or best
      leverages the I/O pattern of the process. In particular, BFQ
      updates queue budgets with a simple feedback-loop algorithm that
      allows a high throughput to be achieved, while still providing
      tight latency guarantees to time-sensitive applications. When
      the in-service queue expires, this algorithm computes the next
      budget of the queue so as to:

      - Let large budgets be eventually assigned to the queues
	associated with I/O-bound applications performing sequential
	I/O: in fact, the longer these applications are served once
	got access to the device, the higher the throughput is.

      - Let small budgets be eventually assigned to the queues
	associated with time-sensitive applications (which typically
	perform sporadic and short I/O), because, the smaller the
	budget assigned to a queue waiting for service is, the sooner
	B-WF2Q+ will serve that queue (Subsec 3.3 in [2]).

- If several processes are competing for the device at the same time,
  but all processes and groups have the same weight, then BFQ
  guarantees the expected throughput distribution without ever idling
  the device. It uses preemption instead. Throughput is then much
  higher in this common scenario.

- ioprio classes are served in strict priority order, i.e.,
  lower-priority queues are not served as long as there are
  higher-priority queues.  Among queues in the same class, the
  bandwidth is distributed in proportion to the weight of each
  queue. A very thin extra bandwidth is however guaranteed to
  the Idle class, to prevent it from starving.

3. What are BFQ's tunables and how to properly configure BFQ?
=============================================================

Most BFQ tunables affect service guarantees (basically latency and
fairness) and throughput. For full details on how to choose the
desired tradeoff between service guarantees and throughput, see the
parameters slice_idle, strict_guarantees and low_latency. For details
on how to maximise throughput, see slice_idle, timeout_sync and
max_budget. The other performance-related parameters have been
inherited from, and have been preserved mostly for compatibility with
CFQ. So far, no performance improvement has been reported after
changing the latter parameters in BFQ.

In particular, the tunables back_seek-max, back_seek_penalty,
fifo_expire_async and fifo_expire_sync below are the same as in
CFQ. Their description is just copied from that for CFQ. Some
considerations in the description of slice_idle are copied from CFQ
too.

per-process ioprio and weight
-----------------------------

Unless the cgroups interface is used (see "4. BFQ group scheduling"),
weights can be assigned to processes only indirectly, through I/O
priorities, and according to the relation:
weight = (IOPRIO_BE_NR - ioprio) * 10.

Beware that, if low-latency is set, then BFQ automatically raises the
weight of the queues associated with interactive and soft real-time
applications. Unset this tunable if you need/want to control weights.

slice_idle
----------

This parameter specifies how long BFQ should idle for next I/O
request, when certain sync BFQ queues become empty. By default
slice_idle is a non-zero value. Idling has a double purpose: boosting
throughput and making sure that the desired throughput distribution is
respected (see the description of how BFQ works, and, if needed, the
papers referred there).

As for throughput, idling can be very helpful on highly seeky media
like single spindle SATA/SAS disks where we can cut down on overall
number of seeks and see improved throughput.

Setting slice_idle to 0 will remove all the idling on queues and one
should see an overall improved throughput on faster storage devices
like multiple SATA/SAS disks in hardware RAID configuration, as well
as flash-based storage with internal command queueing (and
parallelism).

So depending on storage and workload, it might be useful to set
slice_idle=0.  In general for SATA/SAS disks and software RAID of
SATA/SAS disks keeping slice_idle enabled should be useful. For any
configurations where there are multiple spindles behind single LUN
(Host based hardware RAID controller or for storage arrays), or with
flash-based fast storage, setting slice_idle=0 might end up in better
throughput and acceptable latencies.

Idling is however necessary to have service guarantees enforced in
case of differentiated weights or differentiated I/O-request lengths.
To see why, suppose that a given BFQ queue A must get several I/O
requests served for each request served for another queue B. Idling
ensures that, if A makes a new I/O request slightly after becoming
empty, then no request of B is dispatched in the middle, and thus A
does not lose the possibility to get more than one request dispatched
before the next request of B is dispatched. Note that idling
guarantees the desired differentiated treatment of queues only in
terms of I/O-request dispatches. To guarantee that the actual service
order then corresponds to the dispatch order, the strict_guarantees
tunable must be set too.

There is an important flipside for idling: apart from the above cases
where it is beneficial also for throughput, idling can severely impact
throughput. One important case is random workload. Because of this
issue, BFQ tends to avoid idling as much as possible, when it is not
beneficial also for throughput (as detailed in Section 2). As a
consequence of this behavior, and of further issues described for the
strict_guarantees tunable, short-term service guarantees may be
occasionally violated. And, in some cases, these guarantees may be
more important than guaranteeing maximum throughput. For example, in
video playing/streaming, a very low drop rate may be more important
than maximum throughput. In these cases, consider setting the
strict_guarantees parameter.

slice_idle_us
-------------

Controls the same tuning parameter as slice_idle, but in microseconds.
Either tunable can be used to set idling behavior.  Afterwards, the
other tunable will reflect the newly set value in sysfs.

strict_guarantees
-----------------

If this parameter is set (default: unset), then BFQ

- always performs idling when the in-service queue becomes empty;

- forces the device to serve one I/O request at a time, by dispatching a
  new request only if there is no outstanding request.

In the presence of differentiated weights or I/O-request sizes, both
the above conditions are needed to guarantee that every BFQ queue
receives its allotted share of the bandwidth. The first condition is
needed for the reasons explained in the description of the slice_idle
tunable.  The second condition is needed because all modern storage
devices reorder internally-queued requests, which may trivially break
the service guarantees enforced by the I/O scheduler.

Setting strict_guarantees may evidently affect throughput.

back_seek_max
-------------

This specifies, given in Kbytes, the maximum "distance" for backward seeking.
The distance is the amount of space from the current head location to the
sectors that are backward in terms of distance.

This parameter allows the scheduler to anticipate requests in the "backward"
direction and consider them as being the "next" if they are within this
distance from the current head location.

back_seek_penalty
-----------------

This parameter is used to compute the cost of backward seeking. If the
backward distance of request is just 1/back_seek_penalty from a "front"
request, then the seeking cost of two requests is considered equivalent.

So scheduler will not bias toward one or the other request (otherwise scheduler
will bias toward front request). Default value of back_seek_penalty is 2.

fifo_expire_async
-----------------

This parameter is used to set the timeout of asynchronous requests. Default
value of this is 250ms.

fifo_expire_sync
----------------

This parameter is used to set the timeout of synchronous requests. Default
value of this is 125ms. In case to favor synchronous requests over asynchronous
one, this value should be decreased relative to fifo_expire_async.

low_latency
-----------

This parameter is used to enable/disable BFQ's low latency mode. By
default, low latency mode is enabled. If enabled, interactive and soft
real-time applications are privileged and experience a lower latency,
as explained in more detail in the description of how BFQ works.

DISABLE this mode if you need full control on bandwidth
distribution. In fact, if it is enabled, then BFQ automatically
increases the bandwidth share of privileged applications, as the main
means to guarantee a lower latency to them.

In addition, as already highlighted at the beginning of this document,
DISABLE this mode if your only goal is to achieve a high throughput.
In fact, privileging the I/O of some application over the rest may
entail a lower throughput. To achieve the highest-possible throughput
on a non-rotational device, setting slice_idle to 0 may be needed too
(at the cost of giving up any strong guarantee on fairness and low
latency).

timeout_sync
------------

Maximum amount of device time that can be given to a task (queue) once
it has been selected for service. On devices with costly seeks,
increasing this time usually increases maximum throughput. On the
opposite end, increasing this time coarsens the granularity of the
short-term bandwidth and latency guarantees, especially if the
following parameter is set to zero.

max_budget
----------

Maximum amount of service, measured in sectors, that can be provided
to a BFQ queue once it is set in service (of course within the limits
of the above timeout). According to what said in the description of
the algorithm, larger values increase the throughput in proportion to
the percentage of sequential I/O requests issued. The price of larger
values is that they coarsen the granularity of short-term bandwidth
and latency guarantees.

The default value is 0, which enables auto-tuning: BFQ sets max_budget
to the maximum number of sectors that can be served during
timeout_sync, according to the estimated peak rate.

For specific devices, some users have occasionally reported to have
reached a higher throughput by setting max_budget explicitly, i.e., by
setting max_budget to a higher value than 0. In particular, they have
set max_budget to higher values than those to which BFQ would have set
it with auto-tuning. An alternative way to achieve this goal is to
just increase the value of timeout_sync, leaving max_budget equal to 0.

4. Group scheduling with BFQ
============================

BFQ supports both cgroups-v1 and cgroups-v2 io controllers, namely
blkio and io. In particular, BFQ supports weight-based proportional
share. To activate cgroups support, set BFQ_GROUP_IOSCHED.

4-1 Service guarantees provided
-------------------------------

With BFQ, proportional share means true proportional share of the
device bandwidth, according to group weights. For example, a group
with weight 200 gets twice the bandwidth, and not just twice the time,
of a group with weight 100.

BFQ supports hierarchies (group trees) of any depth. Bandwidth is
distributed among groups and processes in the expected way: for each
group, the children of the group share the whole bandwidth of the
group in proportion to their weights. In particular, this implies
that, for each leaf group, every process of the group receives the
same share of the whole group bandwidth, unless the ioprio of the
process is modified.

The resource-sharing guarantee for a group may partially or totally
switch from bandwidth to time, if providing bandwidth guarantees to
the group lowers the throughput too much. This switch occurs on a
per-process basis: if a process of a leaf group causes throughput loss
if served in such a way to receive its share of the bandwidth, then
BFQ switches back to just time-based proportional share for that
process.

4-2 Interface
-------------

To get proportional sharing of bandwidth with BFQ for a given device,
BFQ must of course be the active scheduler for that device.

Within each group directory, the names of the files associated with
BFQ-specific cgroup parameters and stats begin with the "bfq."
prefix. So, with cgroups-v1 or cgroups-v2, the full prefix for
BFQ-specific files is "blkio.bfq." or "io.bfq." For example, the group
parameter to set the weight of a group with BFQ is blkio.bfq.weight
or io.bfq.weight.

As for cgroups-v1 (blkio controller), the exact set of stat files
created, and kept up-to-date by bfq, depends on whether
CONFIG_BFQ_CGROUP_DEBUG is set. If it is set, then bfq creates all
the stat files documented in
Documentation/admin-guide/cgroup-v1/blkio-controller.rst. If, instead,
CONFIG_BFQ_CGROUP_DEBUG is not set, then bfq creates only the files::

  blkio.bfq.io_service_bytes
  blkio.bfq.io_service_bytes_recursive
  blkio.bfq.io_serviced
  blkio.bfq.io_serviced_recursive

The value of CONFIG_BFQ_CGROUP_DEBUG greatly influences the maximum
throughput sustainable with bfq, because updating the blkio.bfq.*
stats is rather costly, especially for some of the stats enabled by
CONFIG_BFQ_CGROUP_DEBUG.

Parameters
----------

For each group, the following parameters can be set:

  weight
        This specifies the default weight for the cgroup inside its parent.
        Available values: 1..1000 (default: 100).

        For cgroup v1, it is set by writing the value to `blkio.bfq.weight`.

        For cgroup v2, it is set by writing the value to `io.bfq.weight`.
        (with an optional prefix of `default` and a space).

        The linear mapping between ioprio and weights, described at the beginning
        of the tunable section, is still valid, but all weights higher than
        IOPRIO_BE_NR*10 are mapped to ioprio 0.

        Recall that, if low-latency is set, then BFQ automatically raises the
        weight of the queues associated with interactive and soft real-time
        applications. Unset this tunable if you need/want to control weights.

  weight_device
        This specifies a per-device weight for the cgroup. The syntax is
        `minor:major weight`. A weight of `0` may be used to reset to the default
        weight.

        For cgroup v1, it is set by writing the value to `blkio.bfq.weight_device`.

        For cgroup v2, the file name is `io.bfq.weight`.

[1]
    P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O
    Scheduler", Proceedings of the First Workshop on Mobile System
    Technologies (MST-2015), May 2015.

    http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf

[2]
    P. Valente and M. Andreolini, "Improving Application
    Responsiveness with the BFQ Disk I/O Scheduler", Proceedings of
    the 5th Annual International Systems and Storage Conference
    (SYSTOR '12), June 2012.

    Slightly extended version:

    http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-results.pdf

[3]
   https://github.com/Algodev-github/S


code:
======================================
Immutable biovecs and biovec iterators
======================================

Kent Overstreet <kmo@daterainc.com>

As of 3.13, biovecs should never be modified after a bio has been submitted.
Instead, we have a new struct bvec_iter which represents a range of a biovec -
the iterator will be modified as the bio is completed, not the biovec.

More specifically, old code that needed to partially complete a bio would
update bi_sector and bi_size, and advance bi_idx to the next biovec. If it
ended up partway through a biovec, it would increment bv_offset and decrement
bv_len by the number of bytes completed in that biovec.

In the new scheme of things, everything that must be mutated in order to
partially complete a bio is segregated into struct bvec_iter: bi_sector,
bi_size and bi_idx have been moved there; and instead of modifying bv_offset
and bv_len, struct bvec_iter has bi_bvec_done, which represents the number of
bytes completed in the current bvec.

There are a bunch of new helper macros for hiding the gory details - in
particular, presenting the illusion of partially completed biovecs so that
normal code doesn't have to deal with bi_bvec_done.

 * Driver code should no longer refer to biovecs directly; we now have
   bio_iovec() and bio_iter_iovec() macros that return literal struct biovecs,
   constructed from the raw biovecs but taking into account bi_bvec_done and
   bi_size.

   bio_for_each_segment() has been updated to take a bvec_iter argument
   instead of an integer (that corresponded to bi_idx); for a lot of code the
   conversion just required changing the types of the arguments to
   bio_for_each_segment().

 * Advancing a bvec_iter is done with bio_advance_iter(); bio_advance() is a
   wrapper around bio_advance_iter() that operates on bio->bi_iter, and also
   advances the bio integrity's iter if present.

   There is a lower level advance function - bvec_iter_advance() - which takes
   a pointer to a biovec, not a bio; this is used by the bio integrity code.

As of 5.12 bvec segments with zero bv_len are not supported.

What's all this get us?
=======================

Having a real iterator, and making biovecs immutable, has a number of
advantages:

 * Before, iterating over bios was very awkward when you weren't processing
   exactly one bvec at a time - for example, bio_copy_data() in block/bio.c,
   which copies the contents of one bio into another. Because the biovecs
   wouldn't necessarily be the same size, the old code was tricky convoluted -
   it had to walk two different bios at the same time, keeping both bi_idx and
   and offset into the current biovec for each.

   The new code is much more straightforward - have a look. This sort of
   pattern comes up in a lot of places; a lot of drivers were essentially open
   coding bvec iterators before, and having common implementation considerably
   simplifies a lot of code.

 * Before, any code that might need to use the biovec after the bio had been
   completed (perhaps to copy the data somewhere else, or perhaps to resubmit
   it somewhere else if there was an error) had to save the entire bvec array
   - again, this was being done in a fair number of places.

 * Biovecs can be shared between multiple bios - a bvec iter can represent an
   arbitrary range of an existing biovec, both starting and ending midway
   through biovecs. This is what enables efficient splitting of arbitrary
   bios. Note that this means we _only_ use bi_size to determine when we've
   reached the end of a bio, not bi_vcnt - and the bio_iovec() macro takes
   bi_size into account when constructing biovecs.

 * Splitting bios is now much simpler. The old bio_split() didn't even work on
   bios with more than a single bvec! Now, we can efficiently split arbitrary
   size bios - because the new bio can share the old bio's biovec.

   Care must be taken to ensure the biovec isn't freed while the split bio is
   still using it, in case the original bio completes first, though. Using
   bio_chain() when splitting bios helps with this.

 * Submitting partially completed bios is now perfectly fine - this comes up
   occasionally in stacking block drivers and various code (e.g. md and
   bcache) had some ugly workarounds for this.

   It used to be the case that submitting a partially completed bio would work
   fine to _most_ devices, but since accessing the raw bvec array was the
   norm, not all drivers would respect bi_idx and those would break. Now,
   since all drivers _must_ go through the bvec iterator - and have been
   audited to make sure they are - submitting partially completed bios is
   perfectly fine.

Other implications:
===================

 * Almost all usage of bi_idx is now incorrect and has been removed; instead,
   where previously you would have used bi_idx you'd now use a bvec_iter,
   probably passing it to one of the helper macros.

   I.e. instead of using bio_iovec_idx() (or bio->bi_iovec[bio->bi_idx]), you
   now use bio_iter_iovec(), which takes a bvec_iter and returns a
   literal struct bio_vec - constructed on the fly from the raw biovec but
   taking into account bi_bvec_done (and bi_size).

 * bi_vcnt can't be trusted or relied upon by driver code - i.e. anything that
   doesn't actually own the bio. The reason is twofold: firstly, it's not
   actually needed for iterating over the bio anymore - we only use bi_size.
   Secondly, when cloning a bio and reusing (a portion of) the original bio's
   biovec, in order to calculate bi_vcnt for the new bio we'd have to iterate
   over all the biovecs in the new bio - which is silly as it's not needed.

   So, don't use bi_vcnt anymore.

 * The current interface allows the block layer to split bios as needed, so we
   could eliminate a lot of complexity particularly in stacked drivers. Code
   that creates bios can then create whatever size bios are convenient, and
   more importantly stacked drivers don't have to deal with both their own bio
   size limitations and the limitations of the underlying devices. Thus
   there's no need to define ->merge_bvec_fn() callbacks for individual block
   drivers.

Usage of helpers:
=================

* The following helpers whose names have the suffix of `_all` can only be used
  on non-BIO_CLONED bio. They are usually used by filesystem code. Drivers
  shouldn't use them because the bio may have been split before it reached the
  driver.

::

	bio_for_each_segment_all()
	bio_for_each_bvec_all()
	bio_first_bvec_all()
	bio_first_page_all()
	bio_last_bvec_all()

* The following helpers iterate over single-page segment. The passed 'struct
  bio_vec' will contain a single-page IO vector during the iteration::

	bio_for_each_segment()
	bio_for_each_segment_all()

* The following helpers iterate over multi-page bvec. The passed 'struct
  bio_vec' will contain a multi-page IO vector during the iteration::

	bio_for_each_bvec()
	bio_for_each_bvec_all()
	rq_for_each_bvec()


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

================================================
Multi-Queue Block IO Queueing Mechanism (blk-mq)
================================================

The Multi-Queue Block IO Queueing Mechanism is an API to enable fast storage
devices to achieve a huge number of input/output operations per second (IOPS)
through queueing and submitting IO requests to block devices simultaneously,
benefiting from the parallelism offered by modern storage devices.

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

Background
----------

Magnetic hard disks have been the de facto standard from the beginning of the
development of the kernel. The Block IO subsystem aimed to achieve the best
performance possible for those devices with a high penalty when doing random
access, and the bottleneck was the mechanical moving parts, a lot slower than
any layer on the storage stack. One example of such optimization technique
involves ordering read/write requests according to the current position of the
hard disk head.

However, with the development of Solid State Drives and Non-Volatile Memories
without mechanical parts nor random access penalty and capable of performing
high parallel access, the bottleneck of the stack had moved from the storage
device to the operating system. In order to take advantage of the parallelism
in those devices' design, the multi-queue mechanism was introduced.

The former design had a single queue to store block IO requests with a single
lock. That did not scale well in SMP systems due to dirty data in cache and the
bottleneck of having a single lock for multiple processors. This setup also
suffered with congestion when different processes (or the same process, moving
to different CPUs) wanted to perform block IO. Instead of this, the blk-mq API
spawns multiple queues with individual entry points local to the CPU, removing
the need for a lock. A deeper explanation on how this works is covered in the
following section (`Operation`_).

Operation
---------

When the userspace performs IO to a block device (reading or writing a file,
for instance), blk-mq takes action: it will store and manage IO requests to
the block device, acting as middleware between the userspace (and a file
system, if present) and the block device driver.

blk-mq has two group of queues: software staging queues and hardware dispatch
queues. When the request arrives at the block layer, it will try the shortest
path possible: send it directly to the hardware queue. However, there are two
cases that it might not do that: if there's an IO scheduler attached at the
layer or if we want to try to merge requests. In both cases, requests will be
sent to the software queue.

Then, after the requests are processed by software queues, they will be placed
at the hardware queue, a second stage queue where the hardware has direct access
to process those requests. However, if the hardware does not have enough
resources to accept more requests, blk-mq will places requests on a temporary
queue, to be sent in the future, when the hardware is able.

Software staging queues
~~~~~~~~~~~~~~~~~~~~~~~

The block IO subsystem adds requests in the software staging queues
(represented by struct blk_mq_ctx) in case that they weren't sent
directly to the driver. A request is one or more BIOs. They arrived at the
block layer through the data structure struct bio. The block layer
will then build a new structure from it, the struct request that will
be used to communicate with the device driver. Each queue has its own lock and
the number of queues is defined by a per-CPU or per-node basis.

The staging queue can be used to merge requests for adjacent sectors. For
instance, requests for sector 3-6, 6-7, 7-9 can become one request for 3-9.
Even if random access to SSDs and NVMs have the same time of response compared
to sequential access, grouped requests for sequential access decreases the
number of individual requests. This technique of merging requests is called
plugging.

Along with that, the requests can be reordered to ensure fairness of system
resources (e.g. to ensure that no application suffers from starvation) and/or to
improve IO performance, by an IO scheduler.

IO Schedulers
^^^^^^^^^^^^^

There are several schedulers implemented by the block layer, each one following
a heuristic to improve the IO performance. They are "pluggable" (as in plug
and play), in the sense of they can be selected at run time using sysfs. You
can read more about Linux's IO schedulers `here
<https://www.kernel.org/doc/html/latest/block/index.html>`_. The scheduling
happens only between requests in the same queue, so it is not possible to merge
requests from different queues, otherwise there would be cache trashing and a
need to have a lock for each queue. After the scheduling, the requests are
eligible to be sent to the hardware. One of the possible schedulers to be
selected is the NONE scheduler, the most straightforward one. It will just
place requests on whatever software queue the process is running on, without
any reordering. When the device starts processing requests in the hardware
queue (a.k.a. run the hardware queue), the software queues mapped to that
hardware queue will be drained in sequence according to their mapping.

Hardware dispatch queues
~~~~~~~~~~~~~~~~~~~~~~~~

The hardware queue (represented by struct blk_mq_hw_ctx) is a struct
used by device drivers to map the device submission queues (or device DMA ring
buffer), and are the last step of the block layer submission code before the
low level device driver taking ownership of the request. To run this queue, the
block layer removes requests from the associated software queues and tries to
dispatch to the hardware.

If it's not possible to send the requests directly to hardware, they will be
added to a linked list (``hctx->dispatch``) of requests. Then,
next time the block layer runs a queue, it will send the requests laying at the
``dispatch`` list first, to ensure a fairness dispatch with those
requests that were ready to be sent first. The number of hardware queues
depends on the number of hardware contexts supported by the hardware and its
device driver, but it will not be more than the number of cores of the system.
There is no reordering at this stage, and each software queue has a set of
hardware queues to send requests for.

.. note::

        Neither the block layer nor the device protocols guarantee
        the order of completion of requests. This must be handled by
        higher layers, like the filesystem.

Tag-based completion
~~~~~~~~~~~~~~~~~~~~

In order to indicate which request has been completed, every request is
identified by an integer, ranging from 0 to the dispatch queue size. This tag
is generated by the block layer and later reused by the device driver, removing
the need to create a redundant identifier. When a request is completed in the
driver, the tag is sent back to the block layer to notify it of the finalization.
This removes the need to do a linear search to find out which IO has been
completed.

Further reading
---------------

- `Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems <http://kernel.dk/blk-mq.pdf>`_

- `NOOP scheduler <https://en.wikipedia.org/wiki/Noop_scheduler>`_

- `Null block device driver <https://www.kernel.org/doc/html/latest/block/null_blk.html>`_

Source code documentation
=========================

.. kernel-doc:: include/linux/blk-mq.h

.. kernel-doc:: block/blk-mq.c


code:
===============================
Generic Block Device Capability
===============================

This file documents the sysfs file ``block/<disk>/capability``.

``capability`` is a bitfield, printed in hexadecimal, indicating which
capabilities a specific block device supports:

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


code:
==============================================
Embedded device command line partition parsing
==============================================

The "blkdevparts" command line option adds support for reading the
block device partition table from the kernel command line.

It is typically used for fixed block (eMMC) embedded devices.
It has no MBR, so saves storage space. Bootloader can be easily accessed
by absolute address of data on the block device.
Users can easily change the partition.

The format for the command line is just like mtdparts:

blkdevparts=<blkdev-def>[;<blkdev-def>]
  <blkdev-def> := <blkdev-id>:<partdef>[,<partdef>]
    <partdef> := <size>[@<offset>](part-name)

<blkdev-id>
    block device disk name. Embedded device uses fixed block device.
    Its disk name is also fixed, such as: mmcblk0, mmcblk1, mmcblk0boot0.

<size>
    partition size, in bytes, such as: 512, 1m, 1G.
    size may contain an optional suffix of (upper or lower case):

      K, M, G, T, P, E.

    "-" is used to denote all remaining space.

<offset>
    partition start address, in bytes.
    offset may contain an optional suffix of (upper or lower case):

      K, M, G, T, P, E.

(part-name)
    partition name. Kernel sends uevent with "PARTNAME". Application can
    create a link to block device partition with the name "PARTNAME".
    User space application can access partition by partition name.

Example:

    eMMC disk names are "mmcblk0" and "mmcblk0boot0".

  bootargs::

    'blkdevparts=mmcblk0:1G(data0),1G(data1),-;mmcblk0boot0:1m(boot),-(kernel)'

  dmesg::

    mmcblk0: p1(data0) p2(data1) p3()
    mmcblk0boot0: p1(boot) p2(kernel)